4. Beschreibung der Algorithmen; Mathe Definitionen

Eine bessere Beschreibung der Mathematik in tkmatrix befindet sich als PDF oder PS Datei mathe1.ps mit in der Distribution des Programms. Html Vesion hat keinen guten Zeichensatz (Es is eben nicht möglich in html) und hat ein paar Fehler, die in der Latex Vesion korrigiert wurden.

Das ist eine Zusammenfassung meiner Vorlesungsunterlagen aus Mathe I. Es werden alle Algorithmen grob beschreiben, ohne jegliche Beweise. Es geht vor allem darum zu beschreiben wie die Algorithmen funktionieren und welche mathematische Probleme man mit ihnen lösen kann. Diese Beschreibung kann aber ein gutes Skript oder ein Mathebuch nicht ersetzen. Die Reihenfolge entspricht eher der Gliederung der Algorithmen als der beim wirklichen Vorlesung.

4.1 Eine Matrix

Def: Def.: eine m× n Matrix (m mal n): m-Zeilenzahl; n-Spaltenzahl

a11	a12	a13	...	a1n
a21	a22	a23	...	a2n
:	:	:	:	:
am1	am2	am2	...	amn

Alle Matrizen werden hier ohne Klammer geschrieben. Auch Vektoren werden in der html Version ohne den gewöhnten Pfeil geschrieben. (also "a" kann auch bedeuten "a-Vektor"). Es soll es den Kontext ersichtlich sein um welche Bedeutung es sich gerade handelt.

4.2 Grundliegende Algorithmen

Treppenform

Def.: c=c_ij ist in Treppenform, falls c die Nullmatrix ist, oder es eine Folge
1<= j₁ < j₂ < ... < j_r <= l von r Sprungstellen gibt mit

1. unterhalb der r Zeile stehen nur Nullen
2. An dem Sprungstellen stehen Elemente c_ij <> 0
3. Links von dem Sprungstellen stehen nur Nullen

Treppennormallform

Def.: Eine Matrix ist in Treppennormalform c=(c_ij) wenn sie in Treppenform ist und wenn zusätzlich

1. Alle Sprungstellen c_ij=1
2. In jeder Sprungstellen Spalte sind alle Elemente bis auf das Sprungstellen Element gleich Null

4.3 Gauss Algorithmus

Benutzt um Lösung LOESUNG des linearen Gleichungsystem LGS zu finden. k-Spaltenzahl. Bringt die Matrix auf Treppenform TREPPENFORM

1. Suche die erste Spalte Matrix c, die nicht nur Nullen erhält. Dies ist die j1-Spalte. Darin sei das Element c_ij1<> 0 Dann vertausche die i-te Zeile mit der ersten Zeile.
2. Für i=2,... .,k addiere der i-ten Zeilen das -cij1c1j1 fache der 1. Zeile.
3. Wende Schritt 1 und 2 auf Matrix c2, das entsteht wenn man aus Matrix c nur die Zeile 2 bis k nimmt und j ersten Stellen abschneidet.

Es gibt viele Möglichkeiten eine Matrix auf Treppenform zu bringen (Treppenform ist nicht eindeutig). Man kann, um sich die Rechnungen zu erleichtern, auch Zeilen wechseln oder Zeilen mit verschiedene Faktoren multiplizieren. Für den Rechner ist das aber keine Erleichterung. Der Algorithmus in dieser Form ändern nicht die Determinante DETERMINANTE von Matrix.

4.4 Gauss-Jordan Algorithmus

Benutzt um Lösung LOESUNG des linearen Gleichungsystem LGS zu finden. Weiterentwicklung von Gauss Algorithmus GAUSS . Bringt die Matrix auf Treppennormallform TREPPENNORMALFORM . k-Spaltenzahl

1. Suche die erste Spalte Matrix c, die nicht nur Nullen erhält. Dies ist die j1-Spalte. Darin sei das Element c_ij1<> 0 Dann vertausche die i-te Zeile mit der ersten Zeile. Dann dividiere die Zeile durch c_ij1
2. Für i=2,... .,k addiere der i-ten Zeilen das -c_ij1 fache der 1. Zeile. Mache alle Einträge unterhalb c_ij1 zu Nullen.
3. Für alle Zeilen d=1,... ,i bilde 1.Zeile=1.Zeile-c_dj1*(i-te Zeile). Mache alle Einträge oberhalb c_ij1 zu Nullen.
4. Wende Schritt 1 und 2 auf Matrix c2, das entsteht wenn man aus Matrix c nur die Zeile 2 bis k nimmt und j ersten Stellen abschneidet.

4.5 Lineare Gleichungssysteme

Definition

Def.: Ein lineares Gleichungssystem mit n Gleichungen hat die Form

a11*x1 + a12*x2 + a13*x3 + ... + a1n*xn	=	b1
a21*x1 + a22*x2 + a23*x3 + ... + a2n*xn	=	b2
a31*x1 + a32*x2 + a33*x3 + ... + a3n*xn	=	b3
:	=	:
an1*x1 + an2*x2 + an3*x3 + ... + ann*xn	=	bn

a_ij sind die Koeffizienten wenn b_i>= 0 dann ist das ein homogenes Gleichungssystem, andernfalls inhomogenes

2.Die Matrix der Form

a11	a12	...	a1n	b1
a21	a22	...	a2n	b2
:	:	:	:
an1	an2	an3	ann	bn

heißt erweiterte Koeffizientenmatrix (ohne b_i einfach Koeffizientenmatrix)

Man kann mit Hilfe der elementaren Umformungen (sie ändern nicht die Lösungsmenge) die Matrix in die Form bringen, in dem die Lösung des Gleichungssystem ersichtlich (leicht zu berechnen) ist. Gauss und Gauss-Jordan Algorithmus benutzen nur solche Umformungen. Zu solchen Umformungen gehören:

• Vertauschen zwei Zeilen
• Multiplikation einer Zeile mit Zahl <> 0
• Addition eines Vielfachen einer Zeile zu einer anderen Zeile

Lösungstypen von linearen Gleichungsystemen (LGS)

Es gibt drei möglichen Lösungstypen von Linearen Gleichungssystemen (LGS)

1. LGS hat keine Lösung, dann Ergebnissmatrix ist leer.
2. LGS hat eine Lösung, wenn Ausgangsmatrix m× n dann Ergebnissmatrix (n-1)*1
   

   x1

   x2

   :

   xn-1

3. LGS hat mehrere Lösungen dann ist das Ergebnissmatrix (Bezogen auf Programm Matrix ) (n*k k< n) zusammengesetzt aus mehreren Spaltenvektoren, wobei das erste eine Lösung des LGS ist und die anderen die Basis des linearen Unterraums für das Lösung des zugehörigen homogenen Gleichungssystems. Jede mögliche Lösung des LGS kann man erreichen aus
   x=a+u₁*b₁+... +u_k-1*b_k-1
   • x : Vektor für alle Lösungen
   • a : Erstes Spaltenvektor des Ergebnissmatrix (Eine Lösung)
   • u_i : Weiter Spaltenvektoren
   • b_i : Freie Variablen

Lösung von LGS

Algorithmus:

1. Bringe die erweiterte Koeffizientenmatrix auf Treppennormal Form mit Hilfe des Gauss-Jordan Algorithmus.
2. Falls die Letzte Spalte eine Sprungsstelle ist dann keine Lösung. Ende.
3. Es gibt nur Sprungstellen außer letzten Spalte dann ist die letzte Spalte die einzige Lösung des LGS. Ende.
4. Es gibt mehrere Lösungen.
5. Eine Lösung erhält man indem man für alle x für nicht-Sprungstellen Variablen Null einsetzt und für anderen nacheinander die Einträge der letzten Spalte
6. Finde die Lösung eines homogenen Gleichungssystems. Es gibt frei wählbare Variablen (Parameter) nämlich, die an dem Nichsprugstellen. Setzt man nacheinander eine dieser frei wählbaren Variablen gleich 1 und die anderen frei wählbaren Variablen gleich 0 und löst auf, so erhält man eine Basis des Lösungsraumes.

4.6 Lineare Abbildungen und Matrizen

Sei A eine m× n Matrix, sei definiert die Abbildung Æ
Kⁿ -> K^m Kⁿ - lineares Unterraum von Dimension n
x -> A*x = Æ A(x)
x=ein Vektor (n× 1)
x=

x1

x2

:

xn

Die Abbildung Æ ist linear LINEAR

Def.: Die Menge { Æ A(x) | x Element Kⁿ } heißt Bild von Æ A. Sie ist Teilmenge von Kⁿ und ein linearer Unterraum von Kⁿ .

Das Finden von Bild von A BILD

Def.: Die Menge { x Element Kⁿ | Æ A(x)=0 } heißt Kern von Æ A. Sie ist Teilmenge von Kⁿ und ein linearer Unterraum von Kⁿ .

Das Finden von Kern von A KERN

Satz: Sei
Æ A Kⁿ -> K^m (A eine m× n Matrix) (A eine m× n Matrix)

Dann gilt: dim Kern Æ A + dim Bild Æ A = n

4.7 Errechnen von Bild von Matrix

Man muß die Basis des auf den Spalten Vektoren aufgespannten linearen Unterraums finden. Am einfachsten geht man vor, wenn man die Matrix auf Treppenform LGS bringt und alle Spaltenvektoren aus Ursprungsmatrix zur Lösung nimmt, die Sprungstellen haben. z.B.

0	1	2
1	2	3
0	1	2
2	3	4
0	1	2

Nach Anwendung von Gauss-Jordan Algorithmus

1	0	1
0	1	2
0	0	0
0	0	0
0	0	0

Sprungstellen beim 1. und 2.Spalte kommen zur Lösung

0	1
1	2
0	1
2	3
0	1

Die beiden Vektoren sind linear unabhängig und sind eine Basis des Bildes des Matrix

4.8 Errechnen von Kern von Matrix

Kern Æ A ist die Lösung der Abbildung Æ A(x)=0

Der Nullvektor gehört immer zur Lösung also z.B. der Kern von

1	2	3
2	1	0
2	4	6

ist die Lösungsmenge von LGS LGS

x1+2*x2+3*x3	=	0
2*x1+1*x2	=	0
2*x1+4*x2+6*x3	=	0

Hier in Programm wird zum Matrix eine Nullspalte addiert und durch GaussJordan JORDAN Algorithmus die Lösungsmenge LOESUNG ausgerechnet. Weil Kern ein lineares Unterraum ist, wird die eine spezielle Lösung (immer Nullvektor) abgeschnitten. Die übrigen Vektoren (wenn vorhanden) bilden die Basis des gesuchten Kerns. Hier:

1	2	3	0
2	1	0	0
2	4	6	0

nach Gauss-Jordan

1	0	13	0
0	1	113	0
0	0	0	0

eine Lösung ist Nullvektor; Kern ist

-13

-113

0

der Kern ist nicht eindeutig (Es gibt viele unterschiedliche Kerne von einer Matrix)

4.9 Lösung von (LGS) und lineare Abbildungen

Ein LGS kann man als lineare Abbildung betrachten

a11*x1 + a12*x2 + a13*x3 + ... + a1n*xn	=	b1
a21*x1 + a22*x2 + a23*x3 + ... + a2n*xn	=	b2
a31*x1 + a32*x2 + a33*x3 + ... + a3n*xn	=	b3
:	=	:
an1*x1 + an2*x2 + an3*x3 + ... + ann*xn	=	bn

als A*x=b wo A die Koeffizienten Matrix LGS

betrachte A: Æ A(x)=A*x : Kⁿ -> K^m dann Æ A(x) = b

Dann gilt:

• LGS ist genau dann lösbar, wenn b in Bild BILD von Æ A(x)
• Lösungsmenge=spezielle Lösung+Kern KERN Æ A(x)

4.10 Weitere Operationen auf Matrizen

Matrix-Multiplikation

Sei A eine m× n Matrix

sei B eine n*t Matrix

A=

a11	...	a1n
:	:	:
am1	...	amn

B=

b11	...	b1t
:	:	:
bn1	...	ant

Dann ist C=A*B eine m× t Matrix mit
C=

c11	...	c1t
:	:	:
cm1	...	cmt

c_ij- i_te Zeile von A; j_te Spalte von B
c_ij=a_i1*b_1j+a_i2*b_2j+a_i3*b _3j+... +a_inb_nj

Matrix-Addition

Sei A eine m× n Matrix sei B eine m× n Matrix
A=

a11	...	a1n
:	:	:
am1	...	amn

B=

b11	...	b1n
:	:	:
bm1	...	amn

Dann ist C=A+B eine m× n Matrix mit
C=

c11	...	c1n
:	:	:
cm1	...	cmn

c_ij- i_te Zeile von A,B; j_te Spalte von A,B
c_ij=a_ij+b_ij

Matrixsubstraktion

Sei A eine m× n Matrix sei B eine m× n Matrix
A=

a11	...	a1n
:	:	:
am1	...	amn

B=

b11	...	b1n
:	:	:
bm1	...	amn

Dann ist C=A-B eine m× n Matrix mit
C=

c11	...	c1n
:	:	:
cm1	...	cmn

c_ij- i_te Zeile von A,B; j_te Spalte von A,B
c_ij=a_ij-b_ij

4.11 linearer Unterraum

Def.: linearer Unterrau

Eine Teilmenge U von Kⁿ heißt linearer Unterraum wenn gilt,

• für alle a Element von K und u Element von U gilt a*u ist ein Element in U
• für alle u1 und u2 Element von U, u1+u2 ist wieder in U

4.12 Inverse der Matrix

Es gibt nur eine Inverse von n× n Matrizen A-1 ist Eine Inverse von A wenn gilt A-1 * A=I_n wobei In ist eine Einheitsmatrix wie folgt
I_n=

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

für n=4

I_n ist ein neutrales Element bezüglich Multiplikation MULTIPLIKATION Matrix A heißt dann inventierbar Man findet eine Inverse, indem man zur gegebenen Matrix eine Einheitsmatrix dazu fügt und anschließend mit Gauss-Jordan JORDAN behandelt z.B zur Matrix

5	10	20
1	1	1
12	12	20

eine Einheitsmatrix zufügt

5	10	20	1	0	0
1	1	1	0	1	0
12	12	20	0	0	1

nach Gauss-Jordan

1	0	0	-15	-1	14
0	1	0	15	72	-3 8
0	0	1	0	-32	18

Die Inverse ist dann

-15	-1	14
15	72	-38
0	-32	18

Eine Matrix ist nicht inventierbar wenn nach Gauss-Jordan am Anfang der Matrix keine Einheitsmatrix ersichtlich wird.

4.13 Determinante der Matrix

Die Determinante ist nur auf n× n Matrizen definiert. Im Programm kann auch eine Determinante aus n× (n+1) Matrix ausgerechnet werden. Die letzte Spalte wird einfach ignoriert. Es soll noch Leute geben, die mit Hilfe der Determinanten LGS LGS lösen. Ohne hier drauf genauer anzugehen muß man sagen Determinanten sind OUT.

Es gibt grundsätzlich zwei Methoden um eine Determinante auszurechnen

• Rekursiv (In dem Programm nicht implementiert), sie ist wegen exponential wachsenden Aufwand nicht bevorzuziehen.
• Durch Hilfe von Gauss-Algorithmus GAUSS . Man benutzt dabei zwei Eigenschaften:
  • Addiert man das x-Fache einer Zeile zu einer anderen Zeile, dann ändert sich die Determinante nicht.
  • Vertauscht man zwei Zeilen, dann ändert sich die Determinante um Faktor -1.

4.14 Optimierungsverfahren von linearen Ungleichungssystemen (Simplex)

Problem: Suche die beste (optimale) Lösung eines Ungleicheungssystem bezüglich einer zu maximierenden Funktion G(x) .

1. Bringe alle Ungleichungen in die Form
   

   a11*x1 + a12*x2 + a13*x3 + ... + a1n*xn	>=	b1
   a21*x1 + a22*x2 + a23*x3 + ... + a2n*xn	>=	b2
   a31*x1 + a32*x2 + a33*x3 + ... + a3n*xn	>=	b3
   :	:	:
   am1*x1 + am2*x2 + am3*x3 + ... + amn*xn	>=	bm

   evtl. durch Multiplikation mit -1 und Einsetzen von Gleichungen in die Ungleichungen
2. sei gegeben eine zu maximierende Funktion G
   G(x₁+... +x_n>)=G(vx/)=g₀+g₁*x₁+g₂*x₂+& hellip; +g_n*x_n=g₀+g(x) (wenn G zu Minimieren ist, dann durch -1 Multiplizieren)
3. Die Ausgangsmatrix zum Simplex Algorithmus hat das Aussehen
   

   a11	a12	a13	...	a1n	b1
   a21	a22	a23	...	a2n	b2
   :	:	:	:	:	b3
   am1	am2	am2	...	amn	bm
   g1	g2	g3	...	gn	G

   Letzte Spalte heißt Gewinnspalte

   Allgemein:
   

   A	b
   g	G

   Bedeutet A(x)>= b und G=g₀

4. Finde eine Lösung des Ungleichungsystems EINELOESUNG sei u diese Lösung A*u <= b, dann k=Ax-b Vektor k hat Einträge nur größer oder gleich Null Ausgangsmatrix zum Eckenfindungsalgorithmus (m+1)*(n+1)
   

   a11	a12	a13	...	a1n	k1
   a21	a22	a23	...	a2n	k2
   :	:	:	:	:	k3
   am1	am2	am2	...	amn	km
   g1	g2	g3	...	gn	G

   
   G=G(u)= g₀+g₁*u₁+g₂*u₂+... +g_n*u_n
5. Benutze Ekenfindung-Algorithmus ECKENFINDUNG
6. Wenn der Eckenfindung Algorithmus beim Maximumkriterium (1. Schritt) abbricht dann gilt.

   Wir haben l verschiedene Spalten verarbeitet und daher l verschiedene Zeilen erhalten, die jetzt Standartbasis Vektoren sind (0,... ,1,... ,0) mit n+1 Koordinaten und mit "1" an einer der ersten n-Stellen. Es seien i₁,... ,i_l diese Zeilenindizies. Wir setzen zusätzlich voraus, daß die Gewinnzeile g(l) von B(l) nur negative Einträge erhält
   g_i(l)>= 0 Wenn nicht dann fahre fort mit Schritt 8 Dann gibt es eine optimale Lösung(en) auf Ax>= b diese erhält man folgendermaßen. Man nehme die Zeile i1... il von A und b der Ausgangsmatirx und betrachtet
   (^A) * x = (^b) Dies ist lösbar und jede Lösung LOESUNG y davon erfühlt A*y>= und G(v/y/) ist ein Maximum von A*y>= b.

7. Wenn der Eckenfindung-Algorithmus beim Quotientenkriterium endet (2. Schritt) (zwar Spalte keine Zeile), dann ist die Gewinnfunktion G auf der Lösung Menge A*x>= b nach oben unbeschränkt (kein Maximum)
8. Benutze Eckenaustausch-Algorithmus Beim ihm gelten die Selbe Regel wie beim Eckenfindung-Algorithmus ECKENFINDUNG . Nur die Spalten werden nicht markiert und der Algorithmus endet wenn alle Einträge in der Gewinnzeile g_i negativ sind. Es kann passieren, daß dieser Algorithmus nicht endet (nicht terminiert). Ich konnte leider keine Abbruchbedingung in der Literatur finden, obwohl solche existiert. Im Programm endet der Algorithmus nach n Schritten.

4.15 Pivotieren

Spaltenpivotierung an der Stelle _ij

b11	b12	b13	...	b1n
b21	b22	b23	...	b2n
:	:	:	:	:
bm1	bm2	bm2	...	bmn

sei das Element b_ij<> 0

1. Multipliziere die i-te Spalte mit ¹_bij. Dann steht an der Stelle 1
2. Für alle Spalten verschieden von j-ten Führe aus
   k-te Spalte = k-te Spalte - b_ik * j-te Spalte, dann stehen an allen (i,k)-ten Stellen (mit k<> j ) nur Nullen

4.16 Eckenfindung-Algorithmus

Ein Teil von Simplex Algorithmus

1. Schritt (Maximumkriterium) Wähle einen Spaltenindex j mit 1 <= j<= n (letzte Spalte mit b's ausgeschlossen), derart daß die j-te Spalte von B <> 0 (Nullvektor) ist und, daß | g_j| den größten Wert hat. Markiere diese Spalte. Wenn ein solches j nicht existiert dann ende des Algorithmus. (Wenn mehrere j mit dieser Eigenschaft dann kleinste j)
2. Schritt (Quotientenkriterium) Ist die j-te Spalte von 1. Schritt
   

   a1j

   a2j

   :

   anj

   gj

   Dann betrachte die "relevante Zeilenmenge" R
   R={ i | a_ij <> 0 UND a_ijgj<= 0 } Wenn R die leere Menge, dann Ende des Algorithmus

   Wenn R nicht leer ist, dann wähle i Element Reell aus, so daß
   ki | aij| <= kl | aij| für alle l Element R

   ( Wenn mehrere i dann nimmt das kleinste )

3. Schritt. Führe für B Spaltenpivotierung PIVOTIEREN an der Stelle (i,j) Man erhält neue Matrix B2 wobei Zeilenvektor von B2 so aussieht

   0... 1... 0 i-te Zeile 1 in der j-ten Spalte

4. Schritt: gehe zum 1. Schritt . Laß allerdings die zuvor markierten Spalten bei der Auswahl von j-Außer Betracht.

4.17 Das Suchen nach einer speziellen Lösung von Ax >= b

1. wenn alle b_i<= 0 (i=1,..,m) dann ist u=0 (Vektor) eine Lösung von A*x>= b sonst,
2. Betrachte die Matrix
   ^A=A

   -1

   -1

   :

   -1

   Man fügt zu Matrix A einfach eine Spalte mit nur "-1" zu
3. füge zu x eine neue Koordinate
   x =

   x1

   x2

   :

   xn

   xn+1

   Betrachte A  * x  >= b
4. Sei w = max ( b_i ) 1 <= i <= m

   dann ist
   u =

   0

   0

   :

   -w

   eine Lösung von A  * x  >= b

5. Ist
   v =

   v1

   v2

   :

   vn+1

   eine Lösung von A  * x  >= b ( Suche nach dieser Lösung mit Eckenfindung evtl. Eckenaustauschalgorithmus SIMPLEX ) mit v_n+1 >= 0 dann ist
   v =

   v1

   v2

   :

   vn

   eine Lösung von A * x >= b
6. Wenn für alle Lösungen v  von A  * x  >= b immer gilt v_n+1 < 0 dann hat A * x >= b keine Lösung

4.18 Nährungslösung

Sei A eine m× n Matrix und b Element Rm dann gilt für das Gleichungssystem
(A^t * A) * x = A^t * b A^t ist eine Trasponente von A

ist immer lösbar und die Lösungen sind die besten Lösungen von A * x = b

"beste Lösung" Das heißt wenn u diese Lösung ist dann für alle v
| A*u-b| < | Av - b| also ist | A*u-b| minimal. | a| ist die Länge von a und ist definiert als
| a| = (a₁+a₂+... +a_n)^½

4.19 Trasponente

Die Transponente von A m× n Matrix ist eine At n× m Matrix, wo die Spalten von At die Zeilen von A sind.

4.20 Matrixspiele

Matrixspiele lassen sich mit Hilfe von Simplexverfahren lösen. D.h zu jedem Matrixspiel, bei dem kein Sattelpunkt existiert, läßt sich mit Hilfe von Simplexverfahren eine optimale gemischte Strategie finden. Auch jedes Optiemirungsproblem hat eine Entsprechung als Matrixspiel (Duealitätsatz). Im Program wurde das Verfahren aus dem Buch (Georg Schrage, Rüdeger Baumann, "Strategiespiele; Computerorientierte Einfürung in Algorithmen der Spieltheorie", R. Oldenbourg Verlag, München Wien 1984) benutzt.

Dazugehörige Simpexverfahren ist unterschiedlich zu dem übrigen im Program benutzten Verfahren. Zu den übrigen Erläuterungen verweise ich auf das obige Buch.

Das Programm berechnet den Wert des Spieles und die optimale Strategien für beide Spieler. Ergebnismatrix wird die optimale Strategie des ersten Spielers.