Cramersche Regel - www2.inf.h

Transcrição

2. Mathematische Grundlagen der Linearen Programmierung
Algorithmen zur Lösung von linearen Gleichungssystemen
Cramersche Regel
Satz 2.14. Es sei A ∈ Rn×n eine quadratische Matrix mit det(A) 6= 0.
Für ein LGS Ax = b sei
Aj := (a1, . . . , aj−1 , b, aj+1, . . . , an)
also die Matrix, die entsteht, wenn in A die j-Spalte durch den Vektor b
ersetzt wird.
Dann gilt für die eindeutige Lösung x = (xj ) ∈ Rn des Gleichungssystems
Ax = b:
det(Aj )
xj =
det(A)
Operations Research I — Hochschule Bonn-Rhein-Sieg, SS 2013
119
Beispiel 2.15. Wir betrachten das LGS aus Beispiel 2.11 (a). Die Determinate det(A) = 6 haben wir bereits in Beispiel 2.14 berechnet.




1
0 1
2 1 =2+0−6+2+2−0=0
det(A1) = det  3
−1 −2 1
3
1 1
3 1 =9−3−6+9+3−6=6
det(A2) = det  6
−3 −1 1


3
0
1
2
3  = −6 + 0 − 12 + 6 + 18 − 0 = 6
det(A3) = det  6
−3 −2 −1
120
Daraus folgt
0
x1 = = 0,
6
6
x2 = = 1,
6
6
x3 = = 1
6
Beispiel 2.16. Java-Methode zur Lösung von LGS der Größe 3 × 3, siehe
Homepage.
121
Gaußsches Eliminationsverfahren
Beispiel 2.17.
4x1 + 2x2 + x3 = 2
2x1 + 6x2 + x3 = 4
x1 + x2 + 8x3 = 1
=⇒
(2) − 12 (1)
(3) − 14 (1)
=⇒
1
(3) − 10
(2)
4x1 + 2x2 +
5x2 +
1
2 x2 +
x3 = 2
1
2 x3 = 3
31
1
x
=
3
4
2
4x1 + 2x2 +
5x2 +
x3 = 2
1
2 x3 = 3
77
1
x
=
3
10
5
122
Daraus ergibt sich
2
x3 = ,
77
1
1
46
x2 = (3 − ) = ,
5
77
77
1
92
2
15
x1 = (2 −
− )=
4
77 77
77
123
Pivotisierung
• Für a, b ∈ R mit |a| groß und |b| klein ist die Berechnung von
konditioniert, d.h.
a
b
schlecht
• ein Rundungsfehler bei der Darstellung von b wird verstärkt.
• Deshalb: Pivotisierung durch Zeilenvertauschung
• Für die verbleibenden Zeilen sucht man in der zu bearbeitenden Spalte nach dem betragsgrößten Element (Pivotelement) und führt eine
Zeilenvertauschung durch.
• Die Zeile, die das Pivotelement enthält, heißt Pivotzeile.
Bemerkung: In Beispiel 2.17 war keine Pivotisierung erforderlich.
124
Gaußscher Algorithmus
Äquivalente Umformungen eines LGS:
• Addition des Vielfachen einer Zeile (Gleichung) zu einer anderen,
• Vertauschung von Zeilen (Gleichungen),
• Multiplikation einer Zeile (Gleichung) mit einer Zahl ungleich null.
Bemerkung:
• Wir wollen mit dem Gaußschen Algorithmus auch r(A) bzw. r(A|b)
bestimmen.
• Deshalb schränken wir A nicht weiter ein, insbesondere sind auch Nullspalten und nicht-quadratische Matrizen zugelassen.
125
Algorithmus 2.1.
1. Initialisiere den Zeilenzähler k = 1.
2. Suche nach der ersten Spalte j mit (akj , . . . , amj ) =
6 0 und tausche die
Pivotzeile mit der k-ten Zeile. Anschließend ist akj das Kopfelement der
k-ten Zeile.
3. Für i = k + 1, . . . , m: Durch
aij
ai := ai −
· ak
akj
Nullen unter dem Kopfelement akj erzeugen.
4. Falls k < m, dann k := k + 1 und weiter mit 2. Ansonsten weiter mit 5.
5. Dividiere alle Nicht-Null-Zeilen durch deren Kopfelement.
126
Zeilen-Stufen-Form












0
0
0
..
0
0
..
0
··· 0 # ∗ ··· ∗ ∗ ∗ ··· ∗ ∗ ∗ ··· ∗ ∗
···
··· 0 # ∗ ··· ∗ ∗ ∗ ··· ∗ ∗
···
··· 0 # ∗ ··· ∗ ∗
···
· · · .. ..
···
··· 0 #
···
···
···
∗
∗
∗
..
∗
···
···
···
···
···
···
∗
∗
∗
..
∗
0
..
··· 0
b1
b2
b3
..
br
br+1
..
bm
# Kopfelement, ∗ beliebige Zahlen
r(A) = r(A|b) = r gdw. br+1 = · · · = bm = 0.
127












Beispiel 2.18. Wir betrachten das LGS
2x1
x1
x1
3x1
+
+
+
+
4x2
2x2
2x2
6x2
−
−
−
−
8x3
3x3
2x3
6x3
+ 6x4
+ 6x4
+ 7x4
+ 21x4
+ 2x5
+ 2x5
+ x5
+ 3x5
= 4
= 6
= 9
= 27
Mit dem Gaußschen Algorithmus ergibt sich

2
 1

 1
3
4
2
2
6
−8 6
−3 6
−2 7
−6 21


2 4
2 4 −8 6

2 6 
1 3
 =⇒  0 0
 0 0
1 9 
2 4
3 27
0 0
6 12

2 4
1 4 

0 7 
0 21
128

2
 0
=⇒ 
 0
0


4
4 −8
6
2


0
1
3
1
4 
 =⇒ 

0
0 −2 −2 −1 


0
0 −6 −6 −3
2
4
0 0
0 0
0 0
−8
1
0
0
6

2
4 

3
1
4 


-2 −2 −1 
0
0
0
Die eingerahmten Elemente sind die Kopfelemente. Nicht-Kopfspalten sind
die Spalten 2 und 5, so dass wir x2 = s und x5 = t als freie Parameter
wählen. Damit ergibt sich
1
1
−2x4 − 2x5 = −1 ⇔ x4 = (1 − 2t) = − t
2
2
5
1
x3 + 3x4 + x5 = 4 ⇔ x3 = 4 − 3( − t) − t = + 2t
2
2
129
1
2x1 + 4x2 − 8x3 + 6x4 + 2x5 = 4 ⇔ x1 = (4 − 4s + 20 + 16t − 3 + 6t − 2t)
2
21
− 2s + 10t
=
2
also



x=


21
2
− 2s + 10t
s
5
2 + 2t
1
2 −t
t


21
2


  0 

  5 

=
 +s
  21 

 


2
0
−2
1
0
0
0






 + t




10
0
2
−1
1






s, t ∈ R
130
Gaußscher Algorithmus für reguläre Matrizen
Für eine quadratische Matrix A ∈ Rn×n mit det(A) 6= 0 (eine sogenannte
reguläre Matrix) entsteht beim Gaußalgorithmus ein Dreiecksschema






· · · a1,n−1 a1,n
· · · a2,n−1 a2,n
· · · a3,n−1 a3,n
..
..
···
0
an,n
a1,1 a1,2
0
a2,2
0
0
..
..
0
0
b1
b2
b3
..
bn






mit ak,k 6= 0 für k = 1, . . . , n. Daraus ergeben sich die Lösungen
xk =
bk −
Pn
j=k+1 ak,j xj
ak,k
für k = n, . . . , 1
131
Matrixzerlegung
Die beiden Operationen
(a) Addition des Vielfachen einer Zeile zu einer anderen und
(b) Vertauschung von Zeilen
entsprechen der Multiplikation von A mit sogenannten Elementarmatrizen.
Alle Elementarmatrizen von Operation (a) zusammen ergeben eine untere
Dreiecksmatrix L, das Ergebnis ist eine obere Dreiecksmatrix R. In diesem
Fall gilt daher
LA = R
bzw.
A = L−1R
132
(LR-Zerlegung). Nutzt man zusätzlich Pivotisierung, kann dies durch eine
Matrix P ausgedrückt werden. Es gilt dann
LPA = R
bzw.
PA = L−1R
Hierbei gilt
• det(L) = det(L−1) = 1
• det(P) = ±1
Qn
• det(R) = i=1 ri,i
womit det(A) einfach berechnet werden kann.
133
Elementarmatrizen
Definition 2.16. Die Elementarmatrix Rk,l(α) = (rij ) ∈ Rn×n mit k 6= l
ist definiert durch:

 1 für i = j
α für i = k und j = l
rij =

0 sonst
Beispiel 2.19.


1 0 0
1
R2,1(− ) =  − 12 1 0  ,
2
0 0 1

1
R3,1(− ) = 
4

1 0 0
0 1 0 
− 14 0 1
134
Wirkungsweise:
• Rk,l(α) · A addiert das α-fache der l-ten Zeile zu Zeile k.
• A · Rk,l(α) addiert das α-fache der k-ten Spalte zu Spalte l.
Eigenschaften:
• det(Rk,l(α)) = 1
• Das Matrixprodukt von Elementarmatrizen Rk,l(α) mit k > l ist eine
untere Dreiecksmatrix mit 1en auf der Hauptdiagonale.
• Die Matrix L für die Zerlegung LA = R ensteht durch die Multiplikation
von Elemantarmatrizen mit k, l und α gemäß Gaußschem Algorithmus.
135
• Es gilt
(Rk,l(α))
−1
= Rk,l(−α)
Damit lässt sich die inverse der Matrix L sehr leicht bestimmen.
Beispiel 2.20. Zerlegung der Koeffizientenmatrix A von Beispiel 2.17:



4 2
4 2 1
1
1 
1
2 6 1 = 0 5
R3,2(− ) · R3,1(− ) · R2,1(− ) ·
10
4
2
1 1 8
0 0

1
⇔  − 12
− 15



4 2 1
4 2
0 0
1 0  2 6 1  =  0 5
1
1 1 8
0 0
− 10
1
1
1
2
77
10
1
1
2
77
10




Die linke Matrix ist die Matrix L der Zerlegung, die rechte Matrix die Matrix
R.
136
Wegen det(L) = 1 folgt auch
det(A) =
n
Y
ri,i = 4 · 5 ·
i=1
77
= 154
10
Weiterhin ergibt sich



4 2
4 2 1
1
1
1
A =  2 6 1  = R2,1( ) · R3,1( ) · R3,2( ) ·  0 5
2
4
10
1 1 8
0 0

=
1
1
2
1
4

4 2
0 0
1 0  0 5
1
0 0
10 1
1
1
2
77
10
1
1
2
77
10




137
Zusammenfassung
Zusammenfassung
• Vektorraum als Basisstruktur für Berechnungen
• Bestimmung der Lösbarkeit von LGS mit Hilfe von r(A) bzw. r(A|b)
• Determinante und Cramersche Regel für sehr kleine, eindeutig lösbare
LGS
• Allgemeiner Lösungsalgorithmus: Gaußscher-Algorithmus
138

Cramersche Regel - www2.inf.h

Transcrição

Documentos relacionados

Sonstiges

Mathematische Modellierungstage am Erasmus-Grasser

Klausur zur Vorlesung Lineare Algebra I

Profil - Diplom-Informatiker Frank Seitz

Cramersche Regel - Prof. Dr. habil. Lubov Vassilevskaya, Math

Textaufgaben, die auf quadratische Gleichungen führen

CV als PDF

Musterlösung 14

eXtensive ATM Position Optimizer

Musterklausur

Projekt-Steckbrief Konsortium

Rendering von Landschaften