Coates Formel
a33
a22
a32
Ziel
x3
x2
a23
a31
a12
a21
a13
Die L¨
osungen des Gleichungssystems wie z. B.
a11
a21
a31
a12
a22
a32
x1
x1
a13
1
a23 x2 = 0
x3
a33
0
Start
a11
k¨
onnen dem zugeh¨
origen Flussgraphen entnommen werden.
Nach der Cramerschen Regel gilt z. B.
x3 =
a11
a21
a31
x3 = −
a12
a22
a32
det G
1
0
0
a11
det G = a21
a31
mit
a12
a22
a32
a13
a23
a33
a21 a32 − a31 a22
−a21 a32 a13 − a31 a23 a12 +a22 a31 a13 + a11 a23 a32 + a21 a12 a33 − a11 a22 a33
|
{z
}|
{z
} | {z }
jeweils 1 Schleife
jeweils 2 Schleifen
(mit −1 erweitert)
3 Schleifen
Wie in der Mason-Formel f¨
uhrt die Berechnung der Determinanten zu Pfaden und Schleifen im Graphen,
Start x1 (1 steht an erster Stelle), Ziel x3 . a21 a32 a13 ist das Produkt der Schleife 1 −→ 2 −→ 3 −→ 1.
x3 = −
X
[ direktes Pfadprodukt1→3( −
−
X
Sk +
X
Sk Sm −
X
X
Sk∗ +
X
∗
Sk∗ Sm
− . . . +) ], Si∗ jeweils disjunkt zum Pfad
Sk Sm Sn − . . . + , disjunkte Schleifenprodukte
Bis auf die Einschr¨
ankung im Z¨
ahler umfasst jedes Schleifenprodukt im Gegensatz zur Mason-Formel
(siehe absorbierende Markow-Ketten) alle Knoten. Dies trifft auch f¨
ur Pfadprodukte zu, falls keine disjunkten Si∗ existieren. St¨
ande auf der rechten Seite des Gleichungssystems an erster Stelle statt einer 1
allgemeiner ein d, so w¨
are die L¨
osung mit d zu multiplizieren. St¨
ande d an zweiter Stelle, so w¨
aren f¨
u r x3
die Pfade 2 −→ 3 zu betrachten. F¨
ur z. B. d1 an erster Stelle und d2 an zweiter w¨
aren die Berechnungen
einzeln durchzuf¨
uhren und zu addieren.
c Roolfs
1
Coates Formel
a34
Ziel
Start
x3
x4
a43
a41
a32
a24
a14
a21
x2
x1
a12
a22
a11
Betrachten wir ein weiteres Gleichungssystems
a12
a22
a32
0
a11
a21
0
a41
0
0
0
a43
a14
a24
a34
0
x1
x
2
=
x3
x4
0
0
0
1
,
z. B. gilt:
x3 =
x3 = −
a11
a21
0
a41
a12
0
a22
0
a32
0
0
1
det G
a14
a24
a34
0
det G = mit
a11
a21
0
a41
a12
a22
a32
0
0
0
0
a43
a14
a24
a34
0
a14 a21 a32 − a24 a32 a11 − a34 a21 a12 + a34 a11 a22
−a21 a32 a43 a14 + a11 a32 a43 a24 + a21 a12 a43 a34 − a11 a22 a34 a43
|
{z
} |
{z
} |
{z
}
1 Schleife
jeweils 2 Schleifen
3 Schleifen
a14 a21 a32 ist das Produkt des direkten Pfades 4 −→ 1 −→ 2 −→ 3, Start x4 , Ziel x3 (1 an 4. Stelle).
x3 = −
X
[ direktes Pfadprodukt1→3( −
−
X
Sk +
X
Sk Sm −
X
X
Sk∗ +
X
∗
Sk∗ Sm
− . . . +) ], Si∗ jeweils disjunkt zum Pfad
Sk Sm Sn + . . . − , disjunkte Schleifenprodukte
Um das Minus-Zeichen vor dem Bruch einzusparen, kann ein neuer Anfangsknoten mit der Belegung
−1 (bzw. −d) eingef¨
ugt werden, Coates 1958.
c Roolfs
2
Begru
¨ndungen
a33
a22
a32
x3
a23
a31
a12
x2
a21
a13
x1
Stellen wir zun¨
achst den Bezug der Determinante
a11 a12 a13 det G = a21 a22 a23 a31 a32 a33 a11
zum Graphen her und erinnern an die Definition einer Determinante.
a11 a12 a13
a21 a22 a23
= a11 a22 a33 − a11 a32 a23 + a21 a32 a13 − a21 a12 a33 + a31 a12 a23 − a31 a22 a13
a31 a32 a33
Aus jeder Spalte und Zeile ist ein Element zu entnehmen.
Das Vorzeichen lassen wir zun¨
achst außer Acht.
a11 a12 a13
a21 a22 a23
a31 a32 a33
a11 a12 a13
a21 a22 a23
a31 a32 a33
ergibt die Schleife a31 a23 a12 .
ergibt das Schleifenpaar a31 a13 und a22 .
c Roolfs
3
Vorzeichen
F¨
ur die Bestimmung des Vorzeichens eines Summanden betrachten wir die an 1. Stelle stehenden
(schwarzen) Zeilenindizes. Also z. B. f¨
ur a11 a32 a23 (1,3,2). Diese Reihenfolge geht in (1,2,3) u
¨ber,
indem 2 Zahlen vertauscht werden (1 Transposition).
F¨
ur (2,3,1) werden 2 Transpositionen ben¨
otigt. Das Vorzeichen der Determinantensummanden wird durch
(−1)Anzahl der ben¨otigten Transpositionen
!
!
1
2
3
1
2
3
1
3
2
2
3
bestimmt.
1
Sei eine Schleife (losgel¨
ost vom Beispiel) f¨
ur n = 4 (Anzahl der Variablen)
durch a31 a43 a24 a12 gegeben, d. h.
1
2
3
4
3
1
4
2
!
Hier sind n − 1 = 3 Transpositionen erforderlich.
F¨
ur ein Schleifenpaar sind es (n1 − 1) + (n2 − 1) = n − 2 Transpositionen (n1 + n2 = n),
f¨
ur ein Schleifentripel n − 3.
Der Nenner der Coates-Formel lautet daher ((−1)n−l = (−1)n · (−1)l , l Anzahl der Schleifen):
X
X
X
X
(−1)n · (−
Sk +
Sk Sm −
Sk Sm Sn +
Sk Sm Sn Sp − . . . + )
Umgekehrt sind alle Summanden in der Determinante enthalten.
Der Z¨
ahler
a11
a
21
a31
a
41
a51
hat die Form (hier wird x4 beim Start in x3 ermittelt):
a12 a13
0
a15 a22 a23
0
a25 a32 a33
1
a35 a42 a43
0
a45 a52 a53
0
a55 Es entstehen Terme wie (beachte
a11 a12 a15
1
(−1) a43 a34 a21 a22 a25
|
{z
}
a51 a52 a55
a43
a22
(−1)2 a13 a41 a34 |
{z
} a52
a13 a41
a25 a55 a34 = 1 und (−1)Anzahl der ben¨otigten Transpositionen ):
oder
oder
(−1)3 a53 a15 a41 a34 a22
|
{z
}
a53 a15 a41
Im Z¨
ahler taucht daher der Faktor (−1)n−1 auf. (−1)n und kann gek¨
urzt werden,
verbleibt.
X ein −Zeichen
X
∗
∗ ∗
−P (direkter Pfad (Knoten werden nicht mehrfach passiert) von 3 nach 4)( −
Sk +
Sk Sm − . . . + )
Si∗ wie im Nenner, jedoch disjunkt zum Pfad. (Bei mehreren Pfaden sind die Terme zu summieren.)
c Roolfs
4
Coates Formel
a
Ziel
Start
x3
x4
b
g
d
h
c
e
x2
x1
f
i
j
e
0
d
x3 = −
f
i
g
0
0
0
0
b
c
h
a
0
x1
x
2
=
x3
x4
0
0
0
1
ceg − hgj − aef + aji
−egbc + jgbh + ef ba − jiab
| {z }
|
{z
}
|{z}
1 Schleife
jeweils 2 Schleifen
3 Schleifen
c Roolfs
5
j
Coates Formel
a
Start/Ziel
x3
x4
b
g
d
h
c
e
x2
x1
f
i
j
e
0
d
x3 = −
f
i
g
0
0
0
0
b
c
h
a
0
x1
x
2
=
x3
x4
−hf d + icd
−egbc + jgbh + ef ba −
| {z }
|
{z
}
1 Schleife
jeweils 2 Schleifen
0
0
1
0
jiab
|{z}
3 Schleifen
c Roolfs
6
j
Coates Formel
a
x3
Ziel
x4
b
g
d
h
c
e
Start
x2
x1
f
i
j
e
0
d
x4 = −
f
i
g
0
0
0
0
b
c
h
a
0
x1
x
2
=
x3
x4
gbj
−egbc + jgbh + ef ba −
| {z }
|
{z
}
1 Schleife
jeweils 2 Schleifen
0
1
0
0
jiab
|{z}
3 Schleifen
c Roolfs
7
j
Coates Formel
a
x3
Start
x4
b
g
d
h
c
e
Ziel
x2
x1
f
i
j
e
0
d
x2 = −
f
i
g
0
0
0
0
b
c
h
a
0
x1
x
2
=
x3
x4
0
−egbc + jgbh + ef ba −
| {z }
|
{z
}
1 Schleife
jeweils 2 Schleifen
0
0
0
1
jiab
|{z}
=0
3 Schleifen
Es gibt keine Pfadprodukte (mit disjunkten Schleifen), die alle Knoten ber¨
ucksichtigen.
c Roolfs
8
j
Coates Formel
a
x3
x4
b
e
d
k
c
f
g
x2
x1
h
i
j
g
0
d
x2 = −
h
i
e
k
0
f
0
b
c
0
a
0
x1
x
2
=
x3
x4
d1
d2
d3
0
(daf − gab)d1 + abjd2 + (bcg − f cd)d3
−af hd − bcge + cdef + abgh + af kj −ijab
|
{z
} |
{z
} | {z }
jeweils 1 Schleife
jeweils 2 Schleifen
3 Schleifen
c Roolfs
9
j
© Copyright 2024 ExpyDoc
