Matrizeneigenwertaufgaben

Kapitel 10
Matrizeneigenwertaufgaben
10.1
Aufgabenstellung, Vorbemerkungen
Gegeben sei A ∈ IRN ×N bzw. A ∈ CN ×N . Gesucht sind die Eigenwerte λ ∈ C
und die zugehörigen Eigenvektoren ϕ ∈ CN (ϕ 6= 0), so daß Aϕ = λϕ.
Die Bestimmung von λ und ϕ ist i.a. ein nichtlineares (also infinites)
Problem (λ und ϕ werden miteinander multipliziert): G(λ, ϕ) = Aϕ − λϕ =
0. Die Lösung dieses Problems ist nicht eindeutig bestimmt. Es gibt i.a. mehr
als einen Eigenwert, und jeder Eigenvektor ist nur bis auf eine Konstante
bestimmt (man kann z.B. zusätzlich kϕk = 1 fordern).
Falls ein Eigenwert λ bekannt ist, ist die Bestimmung eines zugehörigen
Eigenvektors ein lineares Problem. Man erhält einen solchen durch Lösung
des unterbestimmten linearen Gleichungssystems (A − λI)ϕ = 0.
Bei bekanntem Eigenvektor ϕ ergibt sich der Eigenwert λ bereits durch
Betrachtung einer einzelnen (skalaren) Gleichung von Aϕ = λϕ.
Bemerkung 10.1 (Charakteristisches Polynom). PA (λ) := det(A −
λI) ist das charakteristische Polynom von A. Es ist ein Polynom N -ten Grades. Die Nullstellen von PA (λ) sind gerade die Eigenwerte von A: PA (λ) =
0 ⇔ λ ist Eigenwert von A.
Die Bestimmung der Nullstellen des charakteristischen Polynoms ist eine Möglichkeit, die Eigenwerte einer Matrix A zu berechnen (z.B. mit dem
Newton-Verfahren). Dieser Zugang ist – außer in Spezialfällen – jedoch numerisch nicht besonders interessant.
Beim Ansatz von Verfahren zur Bestimmung der Eigenwerte einer Matrix
sollte man die Aufgabenstellung und die eventuell bekannten Eigenschaften
der Matrix berücksichtigen.
153
Matrizeneigenwertaufgaben
154
Typische Aufgabenstellungen:
1. Gesucht ist ein spezieller Eigenwert (z.B. betraglich größter oder kleinster Eigenwert) und der zugehörige Eigenvektor (vgl. Abschnitt 10.2).
2. Gesucht sind mehrere Eigenwerte (vgl. Abschnitt 10.3).
3. Gesucht sind alle Eigenwerte (vgl. Abschnitt 10.4, 10.5).
In der Praxis auftretende Matrizen:
Praktisch auftretende Matrizen sind oft diagonalisierbar, z.B. reell-symmetrisch,
positiv definit o.ä. Hierfür gibt es sehr effiziente Spezialverfahren. Häufig
weisen die Matrizen auch eine spezielle Struktur auf und werden zur numerischen Lösung einer Eigenwertaufgabe bei Differentialgleichungen benötigt.
Ein (triviales, numerisch uninteressantes) Beispiel ist:
−u00 = λu
(0 ≤ x ≤ 1),
u(0) = u(1) = 0.
Durch Diskretisierung von −u00 entsteht eine Matrixeigenwertaufgabe. Typischerweise erhält man dünnbesetzte (“sparse”) Matrizen.
Typische Anwendungsbereiche, in denen Eigenwertaufgaben eine Rolle
spielen, sind etwa
– Strukturmechanik (Vibrationen, Resonanz)
– Akustik
– elektrische Netze
– Quantenmechanik (Schrödinger-Gleichung, Eigenzustände)
– Stabilität (dynamischer Systeme, Chaostheorie, Bifurkation) oder
– chemische Reaktionen.
Ein Beispiel einer Brücke (Tacoma Narrows Bridge), die durch Wind in
Eigenschwingungen gerät und zusammenstürzt, findet man im Web z.B. bei
YouTube.
Bemerkung 10.2 (Diagonalisierbare Matrizen). Wir betrachten spezielle Typen diagonalisierbarer Matrizen (vgl. Lineare Algebra):
A diagonalisierbar ⇔ Die Jordansche Normalforn besteht nur aus der
Hauptdiagonalen.
⇔ Es gibt eine Basis aus Eigenvektoren (weitere
Hauptvektoren gibt es nicht).
A normal
⇔ A∗ A = AA∗ (A∗ : konjugiert adjungierte Matrix
von A )
A normal
⇒ A diagonalisierbar
A normal
⇔ Es gibt eine Orthonormalbasis aus Eigenvektoren.
Matrizeneigenwertaufgaben
155
Mit anderen Worten: Ist A normal, so ist A “unitär diagonalisierbar”, d.h.
es existiert eine unitäre Matrix U , so daß U ∗ AU eine Diagonalmatrix ist.
A hermitesch (selbstadjungiert) ⇔ A = A∗ (⇒ nur reelle Eigenwerte und
A ist normal)
A reell-symmetrisch
⇔
A = A∗ = AT ∈ IRN ×N
(⇒ nur reelle Eigenwerte)
A unitär
⇔
A∗ = A−1
(⇒ |λ| = 1 für alle Eigenwerte λ).
Bemerkung 10.3 (Vorbehandlung von Matrizen). Vor der Berechnung der Eigenwerte einer Matrix überführt man die Matrix in der Regel
in eine geeignetere Form. Die Bestimmung der Jordanschen Normalform ist
hierbei ungeeignet, da dies ein nichtlineares Problem darstellt. Jede hermitesche Matrix A ist allerdings (finit, d.h. nach endlich vielen Schritten) durch
Ähnlichkeitstransformationen in eine tridiagonale Matrix überführbar, jede
quadratische Matrix ist (finit) in Hessenbergform (vgl. Abb. 10.1) überführbar. Für solche Transformationen sind effiziente Algorithmen verfügbar.
*
0
Abbildung 10.1: Hessenbergform einer Matrix
Einschub: Zur Jordanschen Normalform von Matrizen
Die Gesamtheit der Eigenvektoren von A zum Eigenwert λ bildet einen
linearen Raum, den Eigenraum Eλ (von A) zum Eigenwert λ. Die Dimension
dieses Eigenraumes Eλ heißt geometrische Vielfachheit vλ des Eigenwertes
λ.
Matrizeneigenwertaufgaben
156
Eigenvektoren zu verschiedenen Eigenwerten von A sind linear unabhängig.
Ein Vektor ϕ ∈ CN mit (A − λI)j ϕ = 0, (A − λI)j−1 ϕ 6= 0 heißt
Hauptvektor j-ter Stufe von A (zum Eigenwert λ). Die Hauptvektoren 1.
Stufe sind gerade die Eigenvektoren. Die Gesamtheit der Hauptvektoren
beliebiger Stufen zu einem festen Eigenwert λ bilden einen linearen Raum,
den Hauptraum Hλ (von A) zum Eigenwert λ.
Die Dimension des Hauptraumes Hλ ist gleich der algebraischen Vielfachheit von λ:
dim Hλ = wλ .
Es ist somit
vλ ≤ wλ .
Gleichheit tritt offenbar genau dann ein, wenn der Hauptraum nur aus Eigenvektoren von λ besteht, also Hλ = Eλ ist.
Sind λ1 , . . . , λ` sämtliche verschiedenen Eigenwerte von A, so ist der N dimensionale Raum gerade die direkte Summe der Haupträume
Hλ1 ⊕ . . . ⊕ Hλ` .
Insbesondere sind also Hauptvektoren zu verschiedenen Eigenwerten linear
unabhängig.
Jeder Hauptraum Hλ selbst ist wie folgt strukturiert:
In Hλ existieren vλ linear unabhängige Eigenvektoren
ϕ1 , . . . , ϕ vλ
und vλ zu diesen Eigenvektoren gehörige Ketten von linear unabhängigen
(!) Hauptvektoren
ϕ1,1 (= ϕ1 ), ϕ1,2 , . . . , ϕ1,r1 ;
ϕ2,1 (= ϕ2 ), ϕ2,2 , . . . , ϕ2,r2 ;
·
·
·
ϕvλ,1 (= ϕvλ ), ϕvλ,2 , . . . , ϕvλ,rv ;
λ
mit
(A−λI)ϕk,1 = 0, (A−λI)ϕk,2 = ϕk,1 , . . . , (A−λI)ϕk,rk = ϕk,rk−1
und
vλ
X
k=1
rk = wλ .
(k = 1, . . . , vλ )
Matrizeneigenwertaufgaben
157
(Der erste Index der ϕk,i ist der Kettenindex, der zweite Index kennzeichnet
die Stufe des jeweiligen Hauptvektors).
Die aufgezählten Hauptvektoren ϕk,j bilden eine Basis des Hauptraumes
Hλ .
Jeder Hauptraum Hλ und jeder Eigenraum Eλ ist invariant unter A (d.h.
es ist AHλ ⊂ Hλ , AEλ ⊂ Eλ ).
Es gibt darüber hinaus weitere unter A invariante Unterräume, z.B. ist
jeder von einer Kette ϕk,1 , . . . , ϕk,rk aufgespannte Raum invariant unter A.
Sämtliche Ketten von Hauptvektoren zu sämtlichen verschiedenen Eigenwerten λi von A
ϕik,j
(i = 1, . . . , `; k = 1, . . . , vλi ; j = 1, . . . , rki )
bilden eine Basis des N -dimensionalen Raumes
N=
`
X
v
wλi =
i=1
λi
`
X
X
i=1
!!
rki
.
k=1
Es sei Φ die aus diesen Hauptvektoren ϕik,j als Spalten gebildete reguläre
(N, N )-Matrix.
Durch die Ähnlichkeitstransformation Φ−1 AΦ ergibt sich dann die Jordansche Normalform von A
J = Φ−1 AΦ .
(10.1)
Dabei hat J die Gestalt
J1
0
J2
J =
0
Jl
mit
J1i
0
Ji
2
Ji =
(i=1,..., l )
0
Jli
Matrizeneigenwertaufgaben
158
und
λi
1
λi
1
0
Jki =
1
0
("Jordan−Kästchen")
(k=1,..., vλ i )
λi
Die Jordansche Normalform einer Matrix ist bis auf die Anordnung der
Teilmatrizen J i in J und die Anordnung der Jordan-Kästchen Jki in J i eindeutig bestimmt.
Ist eine Matrix B der Matrix A ähnlich (d.h. existiert eine reguläre Transformationsmatrix T , so daß B = T −1 AT ), so ist die Jordansche Normalform
von A gleichzeitig Jordansche Normalform von B.
Ist für einen Eigenwert λi die Ordnung gleich der Vielfachheit, so sind die
zu λi gehörigen Jordankästchen Jki (k = 1, . . . , vλi ) einelementig (rki = 1).
Die Jordansche Normalform J von A ist genau dann eine Diagonalmatrix, wenn eine Basis des N -dimensionalen Raumes aus Eigenvektoren von A
existiert. Dies ist insbesondere immer dann der Fall, wenn A N verschiedene
Eigenwerte besitzt.
Ist A eine hermitesche Matrix, so existiert eine Orthonormalbasis ϕ1 , . . . , ϕN
von Eigenvektoren von A, d.h.
(ϕi , ϕj ) = δij
(i, j = 1, . . . , N ) .
Die aus diesen ϕi gebildete Transformationsmatrix Φ ist dann unitär. Die
Jordansche Normalform von A ist in diesem Falle eine reelle Diagonalmatrix.
10.2
Vektoriteration und Varianten
Wir betrachten das Problem Aϕ = λϕ. Dabei sei A diagonalisierbar und
habe die Eigenwerte λ1 , . . . , λN mit zugehörigen Eigenvektoren ϕ1 , . . . , ϕN .
λ1 sei “dominierend”, d.h. es gelte
|λ1 | > |λ2 | ≥ |λ3 | ≥ · · · ≥ |λN | ≥ 0.
10.2.1
Vektoriteration
Zu gegebenem x(0) 6= 0 bezeichnet man die Iteration
x(n+1) = Ax(n)
(10.2)
Matrizeneigenwertaufgaben
159
als Vektoriteration (oder Potenzmethode, engl. power method).
Satz 10.1 (Vektoriteration). An x(0) sei ϕ1 beteiligt, d.h. in der Entwicklung x(0) = c1 ϕ1 + · · · + cN ϕN sei c1 6= 0. Dann gilt:
(i)
x(n) = λ1 n (c1 ϕ1 + r(n) ) mit r(n) → 0 für n → ∞.
n
n
n wobei r(n) = c2 λλ12 ϕ2 + · · · + cN λλN1
ϕN = O λλ21 .
(n+1)
x(i)
(ii)
(n)
x(i)
n = λ1 + O λλ21 (n+1)
D.h.
x(i)
(n)
x(i)
für alle i = 1, . . . , N mit (ϕ1 )(i) 6= 0.
→ λ1 für n → ∞ mit dem Konvergenzfaktor λλ21 .
Die Vektoriteration liefert also einen zu ϕ1 proportionalen Vektor gemäß (i)
und den Eigenwert λ1 gemäß (ii).
Beweis: zu (i):
x(n) = An x(0) = An (c1 ϕ1 + . . . + cN ϕN )
= λn1 c1 ϕ1 + . . . + λnN cN ϕN = λn1 (c1 ϕ + r(n) ).
zu (ii):
(n+1)
x(i)
(n)
x(i)
P
n
PN λj n
λj
λj
N
c
ϕ
c
ϕ
−
1
λn+1
c
ϕ
+
+
j j
j j λ1
1 1
1
j=2 λ1
j=2 λ1
(i)
(i)
=
n
P
λ
j
λn1 c1 ϕ1 + N
cj ϕj
j=2 λ1
(i)
n λ2 = λ1 1 + O .
λ1
Beachte: Die Forderung c1 6= 0 ist numerisch unerheblich, denn falls c1 = 0
sein sollte, bewirken Rundungsfehler i.d.R., dass c1 6= 0 bei x(1) , x(2) , etc.
10.2.2
Skalierungen
Die dauernde Veränderung der Größenordnung von x(n) um den asymptotischen Faktor λ1 kann durch geeignete Skalierungen vermieden werden.
Durch y (n) := x(n)1 x(n) erhält man eine Skalierung der i-ten Kompo( )(i)
(n)
nente von x auf 1 (im Falle (ϕ1 )(i) 6= 0 ist für alle hinreichend großen n
Matrizeneigenwertaufgaben
auch x(n) (i) 6= 0). Wir bilden daher die Folge y (n) gemäß
y (n+1) =
=
mit µ(n+1) = Ay
1
Ax(n)
Ax(n) =
(i)
1
Ay (n)
(n)
(i)
Ay (n) =
(i)
und y (0) =
x(n)
1
µ(n+1)
160
1
(n)
Ax(n)
x
(n)
(i)
Ax
(i)
(i)
Ay (n)
x(0)
.
(x(0) )(i)
Hierfür lauten die Aussagen des Satzes 10.1
n λ2 1
(n)
y
=
ϕ1 + O (ϕ1 )(i)
λ1
n−1 !
λ2 µ(n) = λ1 + O .
λ1
In der Praxis am günstigsten ist die Division durch die betraglich größte
Komponente.
Allgemeine Skalierungsmöglichkeiten:
(n)
(n+1)
,`
i
Andere Skalierungen erhält man, wenn man in (10.3) µ(n+1) = hAx
hx(n) ,`(n) i
mit einem konstanten Vektor `(n+1) = ` oder einer Folge `(n) wählt. Der
Wahl in (10.3) entspricht ` = ei , denn
Ax(n) (i)
hAx(n) , ei i
=
Ay (n)
=
.
(i)
hx(n) , ei i
x(n) (i)
Ein weiterer gebräuchlicher Spezialfall ist `(n+1) = ` = x(0) :
A sei hermitesch und ϕ1 , . . . , ϕN sei eine Orthonormalbasis aus Eigenvektoren. Dann ergibt sich
µ(n+1) =
hAx(n) , x(0) i
a(n+1)
=
= q (n)
hx(n) , x(0) i
a(n)
mit den Schwarzschen Konstanten a(n) und den Schwarzschen Quotienten
q (n) . Da A hermitesch ist, gilt
a(n) = hAx(n−1) , x(0) i = hAk x(0) , Am x(0) i mit
k + m = n.
Man beachte hierbei, dass zur Bestimmung von q (2n) nur x(n) benötigt wird:
q (2n) =
hAx(n) , x(n) i
a(2n+1)
=
=: R(n)
a(2n)
hx(n) , x(n) i
Matrizeneigenwertaufgaben
161
mit dem Rayleighquotienten R(n) . Analog zu Satz 10.1 (ii) läßt sich zeigen
2n !
λ2 (n)
R = λ1 + O .
λ1
2
Man hat also jetzt einen Konvergenzfaktor von λλ12 .
Als dritten Spezialfall betrachten wir noch `(n+1) = x(n+1) :
A sei wieder hermitesch und ϕ1 , . . . , ϕN eine Orthonormalbasis aus Eigenvektoren. Dann erhält man
a(2n+2)
hAx(n) , Ax(n) i
=
= q (2n+2) q (2n+1)
hx(n) , x(n) i
a(2n)
2n
2
= λ1 + O λλ12 .
µ(n+1) =
und damit µ(n)
10.2.3
Shiftstrategien
Wir
wollen uns nun mit der Frage beschäftigen, wie der Konvergenzfaktor
λ2 λ1 verbessert werden kann. Hierzu ist folgende einfache Überlegung hilfreich:
Aϕ = λϕ
⇔ (A − αI)ϕ = (λ − α)ϕ
↑
↑
Eigenwerte von A
Eigenwerte von A − αI
λ1 , . . . , λ N
λ1 − α, . . . , λN − α
Konvergenzbeschleunigung erreicht man hiermit leicht, falls z.B. A hermitesch und positiv definit ist und falls gilt
λ1 > λ2 ≥ λ3 ≥ . . . ≥ λN > 0.
Dann bestimmt man α so, daß
λ2 − α
λ1 − α
< λ2
λ1
.
Das Verfahren
x(n+1) = (A − αI)x(n) konvergiert dann mit dem Konver
−α genzfaktor λλ12 −α
und damit schneller als x(n+1) = Ax(n) (Konvergenzfaktor
λ2 λ1 ).
Deflation, Treppeniteration
162
Konvergenzerzeugung ist z.B. im Fall
|λ1 | = λ1 = −λ2 > |λ3 | ≥ . . .
möglich, in dem keine Dominanz von λ1 vorliegt. Durch eine geeignete Wahl
von α (α ≈ λ2 ) wird λ1 − α dominierend.
10.2.4
Inverse Iteration
Für die Berechnung des betraglich kleinsten Eigenwertes setzen wir voraus,
dass |λ1 | ≥ |λ2 | ≥ . . . ≥ |λN −1 | > |λN | > 0. Dann gelten für die inverse
Iteration
Ax(n+1) = x(n)
(10.3)
alle obigen Aussagen und Überlegungen für λN statt λ1 , denn λN ist der
betragsgrößte Eigenwert von A−1 . Praktisch wird man A nicht invertieren,
sondern in jedem Schritt das Gleichungssystem (10.3) lösen (etwa mit fester
LR-Zerlegung und sich ändernden rechten Seiten x(n) ). Insbesondere kann
A−1 für dünnbesetzte Matrizen A vollbesetzt sein, so daß der Aufwand über
die Berechnung der Inversen viel zu hoch wäre.
Die Idee der Verschiebung ist auch bei der inversen Vektoriteration anek bekannt (z.B. berechnet).
wendbar (Wieland). Für λk sei eine Näherung λ
ek und iteriert gemäß
Dann wählt man α = λ
(A − αI)x(n+1) = x(n) .
ek ≈ λk ist
Ein Eigenwert von (A − αI)−1 ist dann λk1−α . Wegen α = λ
1 λk −α (sehr) groß und daher in der Regel stark dominierend. Man darf
also sehr günstige Konvergenz erwarten und kann so schnell eine verbesserte
Näherung für λk berechnen.
10.3
Deflation, Treppeniteration
In diesem Abschnitt betrachten wir erstmals den Fall, daß wir nicht nur
einen sondern mehrere Eigenwerte berechnen wollen.
10.3.1
Voraussetzung
A sei hermitesch. Ferner gelte
|λ1 | > |λ2 | > |λ3 | ≥ · · · ≥ |λN | ≥ 0 .
Wie erhält man λ2 ?
Deflation, Treppeniteration
10.3.2
163
Einfachste Idee
Berechne zunächst λ1 , ϕ1 und bilde dann
x
en+1 := Axn
xn+1 = x
en+1 − (e
xn+1 , ϕ1 )ϕ1 ,
(10.4)
das heißt xn+1 ist orthogonal zu ϕ1 , also ϕ1 nicht an xn+1 beteiligt.
Wie sieht jetzt die Konvergenz → ϕ2 bzw. λ2 aus? Wir können schreiben
xn+1 = Axn − (Axn , ϕ1 )ϕ1 = Axn − λ1 (xn , ϕ1 )ϕ1
= (A − λ1 ϕ1 ϕ1 T ) xn .
|
{z
}
=:W
Die Matrix W ist ebenfalls hermitesch. Offenbar gilt
W ϕ1 = 0 ,
W |[ϕ2 ,...,ϕN ] = A|[ϕ2 ,...,ϕn ] ,
das heißt W hat die Eigenwerte 0, λ2 , . . . , λN .
10.3.3
Satz
Satz 10.2 Es sei (x0 , ϕ2 ) 6= 0.
Dann liefert (10.4) den Eigenwert λ2 und den Eigenvektor ϕ2 :
λ n 3
n
xn = λ2 (x0 , ϕ2 )ϕ2 + rn , rn = O (für n → ∞) .
λ2
Beweis: Der Gedankengang läuft genau wie beim Beweis des Satzes zur
Vektoriteration.
10.3.4
Bemerkung
Beim obigen Vorgehen wird erst ϕ1 , λ1 berechnet, dann ϕ2 , λ2 . Besser ist
es, beide gleichzeitig zu berechnen. Dazu setzen wir in (10.4) statt ϕ1 selbst
die jeweils bekannte Näherung für ϕ1 ein. Mit Skalierung ergibt sich dann
folgendes Verfahren:
yn+1
=
wn+1 =
1
Ayn
µn+1
1
(Awn − (Awn , yn+1 )yn+1 )
σn+1
(→ ϕ1 , λ1 )
(10.5)
(→ ϕ2 , λ2 ) .
Deflation, Treppeniteration
10.3.5
164
Variante
Eine Variante dieses Verfahrens ist
yn+1
1
=
Ayn
µn+1
1
(Awn − ρn+1 yn+1 ) .
σn+1
wn+1 =
(10.6)
Die Faktoren µn+1 , σn+1 und ρn+1 werden folgendermaßen bestimmt:
(1)
µn+1 so, daß
yn+1 = 1 ,
ρn+1
so, daß
wn+1 = 0 ,
σn+1 so, daß
wn+1 = 1 .
(1)
(10.7)
(i)
Konvergenz (ohne Beweis): Unter geeigneten Voraussetzungen gilt
µn → λ1 , σn → λ2 .
10.3.6
Darstellung in Matrixschreibweise:
Man kann dieses Verfahren auch in Matrixschreibweise dastellen:
Ayn = µn+1 yn+1
⇔ AYn = Yn+1 Λn+1
Awn = σn+1 wn+1 + ρn+1 yn+1
mit

"
#
Yn = yn , wn
2,N
10.3.7


=


1 0
∗ 1 


..
. ∗ 
∗ ∗
und
Λn =
µn+1 ρn+1
0
σn+1
Treppeniteration
Die Fortsetzung dieser Idee wird auch als Treppeniteration bezeichnet. Unter
den Voraussetzungen A hermitesch und
|λ1 | > |λ2 | > . . . > |λN | > 0
lassen sich mit ihr alle Eigenwerte gleichzeitig wie folgt berechnen:
AYn = Yn+1 Λn+1
LR- und QR-Algorithmus
165
mit





Yn = 




1
..
0
.
..
∗
(1)
µn+1








 , Λn+1 = 






.
..

.

..
∗
.
..
0
.
..
.
(N )
1








µn+1
Bei geeigneter Wahl von Y0 gilt
(i)
µn+1 → λi
.
Praktisch bildet man die LR-Zerlegung von AYn :
L = Yn+1 ,
R = Λn+1 .
Folglich ist die Treppeniteration äquivalent mit dem LR-Algorithmus
(vgl. folgenden Abschnitt).
10.4
LR- und QR-Algorithmus
LR- und QR-Algorithmen sind die am meisten verwendeten Algorithmen zur
Berechnung sämtlicher Eigenwerte einer Matrix A. Jedoch werden sie in der
Regel nicht direkt auf beliebige Matrizen A angewendet, sondern die Matrix
wird zunächst vorbehandelt und in eine Form gebracht, die für Konvergenz
und Algorithmik vorteilhaft ist.
10.4.1
LR-Algorithmus:
Der LR-Algorithmus wird hier beschrieben, ohne genaue Voraussetzungen
anzugeben. Implizit wird angenommen, daß der Algorithmus (auch ohne
Pivotwahl) durchführbar ist.
Ist
A = A0 = L0 R0
die LR-Zerlegung der Matrix A, so bilden wir
A1 := R0 L0
durch einfache Matrixmultiplikation und führen für A1 wieder eine LRZerlegung
A1 = L1 R1
(enthält Skalierungsfaktoren) .

Download Report