Skript zur Vorlesung - KIT...Skript zur Vorlesung Numerische Methoden für die Fachrichtungen Elektrotechnik, Meteorologie, Geodäsie und Geoinformatik Prof. Dr. Wolfgang Reichel Institut

Skript zur Vorlesung

Numerische Methoden

für die Fachrichtungen Elektrotechnik,Meteorologie, Geodäsie und Geoinformatik

Prof. Dr. Wolfgang ReichelInstitut für Analysis, Fakultät für Mathematik, KIT

Unter Verwendung von Skripten von

Prof. Dr. Wilhelm Niethammer

Institut für angewandte und numerische Mathematik, Fakultät für Mathematik, KIT

Sommersemester 2011

Inhaltsverzeichnis

1 Direkte Verfahren 3

1.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Das Eliminationsverfahren von Gauß und die LR-Zerlegung . . . . . . . 5

1.3 Die Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.4 Die QR-Zerlegung (Ergänzung) . . . . . . . . . . . . . . . . . . . . . . 19

2 Eigenwertprobleme 28

2.1 Begriffe und Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2 Die von-Mises Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3 Die inverse Iteration von Wielandt . . . . . . . . . . . . . . . . . . . . 32

2.4 Das LR-Verfahren und das QR-Verfahren für Eigenwertprobleme (Er-gänzung) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5 Die Reduktionsmethode von Householder aufHessenberg- bzw. Tridiagonalform (Ergänzung) . . . . . . . . . . . . . 47

3 Lineare Optimierung 53

4 Fehleranalyse 59

4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2 Fehlerfortpflanzung bei linearen Gleichungssystemen . . . . . . . . . . . 61

1

Vorwort

Dieses Skript entstand anläßlich der Vorlesung Numerische Mathematik für die Fach-richtung Elektroingenieurwesen im Sommersemester 2009 und wurde zum Sommerse-mester 2010 in die jetzige Form gebracht. Als Vorlage dienten einerseits die Notizen vonProf. Dr. Michael Plum aus dem vorangegangenen Sommersemester und andererseitsdie in vielen Semestern erprobten und detailliert ausgearbeiteten Numerik-Skriptenvon Prof. Dr. Wilhelm Niethammer. Beiden Kollegen danke ich sehr für die Zurver-fügungstellung ihres Materials. Ebenso danke ich herzlich Frau Dipl.-Math. SusannePohlig, Frau Dipl.-Math. Dorothee Frey und Herrn Dipl.-Math.techn. Rainer Mandelfür die Arbeit, das Skript zu tippen, die Bilder zu erstellen und das Ergebnis Korrekturzu lesen.

Karlsruhe, im Sommersemester 2010

Wolfgang Reichel

Für die Vorlesung im Sommersemester 2011 wird das Skript der beiden vorangegange-nen Vorlesungen angepasst. Insbesondere fallen aus der numerischen linearen Algebra(Kapitel 1 und Kapitel 2) die QR-Zerlegung und das QR-Verfahren heraus. Anstattdessen beschränkte ich mich bei den Eigenwertverfahren in Kapitel 2 auf die soge-nannte Potenzmethode (bzw. Vektoriteration oder von-Mises-Iteration). Innerhalb desSkriptes finden sich die Verfahren zwar weiterhin — sie sind aber nicht Gegenstandder Vorlesung des aktuellen Semesters und sind als sogenannte Ergänzungen kenntlichgemacht.

Mit dieser Verkürzung wird in der Vorlesung Platz geschaffen für eine ausführlicher Be-handlung der finite-Differenzen- und der finite-Elementeverfahren zur Lösung partiellerDifferentialgleichungen.

Karlsruhe, im Sommersemester 2011

Wolfgang Reichel

2

Kapitel 1

Direkte Verfahren zur Auflösunglinearer Gleichungssysteme

1.1 Einleitung

In diesem Paragraphen befassen wir uns mit direkten Methoden zur Auflösung linea-rer Gleichungssysteme. Als direkt (im Gegensatz zu iterativ) bezeichnet man diejenigenVerfahren, welche es im Prinzip gestatten, die Lösung eines linearen Gleichungssystemsin endlich vielen Schritten zu berechnen. Auf lineare Gleichungssyteme stößt man inder Praxis an vielen Stellen. Wir befassen uns hier nur mit einigen besonders typischenSituationen.

Elektrische Netzwerke lassen sich mit Hilfe der Kirchhoffschen Regeln beschreiben.(Ähnliche Zusammenhänge findet man auch in der Statik, etwa bei der Behandlungvon Fachwerken.) Wir betrachten ein Netzwerk mit Spannungsquellen und Widerstän-den des folgenden, in Abbildung 4.1 dargestellten Typs.

Es gelten folgende Regeln, die das Netzwerk vollständig beschreiben:

• Knotenregel : An jedem Knotenpunkt ist die Summe der zufließenden Strömegleich der abfließenden Ströme, d.h. es gilt (unter Berücksichtigung der Strom-richtung): ∑

Ik = 0.

• Maschenregel : In jedem beliebig herausgegriffenen, in sich geschlossenen Strom-kreis („Masche“) ist die Summe der Spannungsabfälle in den einzelnen Zweigengleich der Summe der vorhandenen elektromotrischen Kräfte:∑

IkRk =∑

Uk.

Bei gegebenen Widerständen Rk und elektromotorischen Kräften Uk erhält man offen-sichtlich ein lineares Gleichungssystem für die Ströme Ik, wenn man alle Knoten undMaschen betrachtet. Möglicherweise ergeben sich dabei mehr Gleichungen als Unbe-kannte; die redundanten Gleichungen sind dann zu streichen.Wir diskutieren exemplarisch das in Abbildung 4.1 dargestellte Netzwerk. Die Kirch-hoffschen Regeln ergeben je vier Knoten- und Maschengleichungen für die unbekannten

3

KAPITEL 1. DIREKTE VERFAHREN 4

A

D

B

C

I

I

I

I

I

I

U

R

R

RR

R

R

6

3

4 5

1

21

2

3

54

6

Abbildung 1.1: Schaltbild eines elektrischen Netzwerkes

Ströme I1, ..., I6. Es wird sich zeigen, dass von diesen acht Gleichungen zwei redundantsind. Im einzelnen gilt:

Knoten A : I1 −I3 +I4 = 0Knoten B : −I2 +I3 −I5 = 0Knoten C : −I1 +I2 +I6 = 0Knoten D : −I4 +I5 −I6 = 0

Maschen ADC: R1I1 −R4I4 +R6I6 = UMaschen BCD: R2I2 −R5I5 −R6I6 = 0Maschen ABD: R3I3 +R4I4 +R5I5 = 0Maschen ABC: R1I1 +R2I2 +R3I3 U

Wir stellen das System in Matrix-Vektor-Schreibweise dar:

1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1

0 0 0 −1 1 −1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0R1 R2 R3 0 0 0

I1I2I3I4I5I6

=

0000U00U

Man erkennt, dass die Gleichungen z.T. voneinander linear abhängig sind, und zwardie vierte von den drei ersten und die letzte von der fünften, sechsten und siebten.


Diese linear abhängigen (redundanten) Gleichungen können wir streichen und erhaltenso das System:

1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0

I1I2I3I4I5I6

=

000U00

Wir notieren uns typische Eigenschaften dieses Gleichungssystems:

• Die Zeilen der Koeffizienten, welche von den Knotengleichungen herstammen,enthalten nur die Werte -1, 0, 1. Dies rührt von der topologischen Struktur desNetztes her; man erkennt, welche Knoten direkt miteinander verbunden sind. DieKnotengleichungen sind außerdem homogen.

• Die Maschengleichungen sind imhomogen, wobei die Inhomogenitäten von denelektromotorischen Kräften herstammen.

• Das System hat eine eindeutig bestimmte Lösung zu jeder rechten Seite. Mankann diesen Sachverhalt physikalisch „beweisen“: Wenn keine elektromotorischeKraft U anliegt, fließen keine Ströme Ik; also hat das homogene System nur dietriviale Lösung und jedes zugehörige System ist folglich auf genau eine Weiselösbar.

1.2 Das Eliminationsverfahren von Gauß und die LR-Zerlegung

In der linearen Algebra ist Ihnen das Prinzip des Gaußschen Eliminationsverfahrensmöglicherweise schon begegnet. Wir verwenden dieses Verfahren zur Lösung eines ge-gebenen linearen Gleichungssystems. Wir gehen aus von einem System

Ax = b;

dabei sei A eine gegebene reguläre Matrix mit m Zeilen und m Spalten, x der gesuchteLösungsvektor und b ein gegebener Vektor, also A ∈ Km×m, x ∈ Km, b ∈ Km, wobei Kden Körper der reellen oder der komplexen Zahlen bezeichne. A

x

=

b

.

Das Ziel des Eliminationsverfahrens von Gauß ist es, dieses Ausgangssystem so um-zuformen, dass die Komponenten des Lösungsvektors x sich leicht berechnen lassen.Man versucht zu diesem Zweck, aus dem gegebenen System ein äquivalentes System


aufzubauen, dessen Koeffizientenmatrix A Dreiecksgestalt hat:

Ax = b ⇔ Ax = b

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗... . . . . . . ...... . . . . . . ...... . . . . . . ∗0 . . . . . . . . . 0 ∗

︸︷︷︸

A

∗............∗

︸︷︷︸

x

=

∗............∗

︸︷︷︸

b

(* bezeichnet Elemente, die möglicherweise von Null verschieden sind.)

Diese Reduktion auf Dreiecksgestalt kann man dadurch erreichen, dass man Gleichun-gen vertauscht und Vielfache von Gleichungen zu anderen Gleichungen addiert.

Aufgabe 1.1.Man bringe das Gleichungssystem 0 5 2

4 2 −16 −5 10

x1

x2

x3

=

61

36

auf Dreiecksgestalt und ermittle dann die Lösung.

Die Vertauschung und die Linearkombination von Gleichungen können wir durch Mul-tiplikation mit speziellen Matrizen erreichen. Zu diesem Zweck führen wir folgendeBezeichnungen ein.

Definition 1.2 (Permutationsmatrix).Eine Matrix P , die in jeder Zeile und jeder Spalte genau eine Eins und sonst nur Nullenenthält heißt Permutationsmatrix.

Wir listen einige Permutationsmatrizen auf:

m=1: [1]

m=2:[

1 00 1

],

[0 11 0

]

m=3:

1 0 00 1 00 0 1

, 1 0 0

0 0 10 1 0

, 0 1 0

1 0 00 0 1

, 0 1 0

0 0 11 0 0

, 0 0 1

1 0 00 1 0

, 0 0 1

0 1 01 0 0


Da die Spalten einer Permutationsmatrix durch Permutation der Spalten der Einheits-matrix entstehen, existieren genau m! m-reihige Permutationsmatrizen.Man macht sich nun leicht klar, dass

• Multiplikation einer Matrix von links mit einer Permutationsmatrix eine Permu-tation der Zeilen bewirkt,

• Multiplikation einer Matrix von rechts mit einer Permutationsmatrix eine Per-mutation der Spalten bewirkt.

Definition 1.3 (elementare untere Dreiecksmatrix).Eine Matrix des Typs

Λi =

1 0. . .

1

λi+1,i. . .

... . . .0 λm,i 0 1

m×m

die sich von der Einheitsmatrix nur in der i-ten Spalte unterhalb der Diagonalen un-terscheidet, bezeichnen wir als elementare untere Dreiecksmatrix.

Elementare untere Dreiecksmatrizen lassen sich auf einfache Weise invertieren. Diessollen Sie in der folgenden Aufgabe zeigen.

Aufgabe 1.4 (Die Inverse einer elementaren unteren Dreiecksmatrix).Man zeige: Für

Λi =

1 0. . .

1

λi+1,i. . .

... . . .0 λm,i 0 1

m×m

gilt

Λ−1i =

1 0. . .

1

−λi+1,i. . .

... . . .0 −λm,i 0 1

m×m

.

Wir kehren nun zur Ausgangssituation zurück und betrachten das System

Ax = b,


das in Komponentenschreibweise die folgende Gestalt hat:a11 a12 . . . . . . a1m

a21 a22 . . . . . . a2m...

......

......

...am1 am2 . . . . . . amm

x1.........xm

=

b1.........bm

Dieses System formen wir in einem rekursiven Prozess um. Wir setzten dabei zunächst

A(1) := A, b(1) := b,

wobei A invertierbar sei. Dann existiert in der ersten Spalte von A(1) ein von Nullverschiedenes Element a(1)

k1 , 1 ≤ k ≤ m. Durch Vertauschung der ersten mit der k-tenZeile erreichen wir, dass in der Position (1, 1) ein von Null verschiedenes Element steht.Diesen Vertauschungsprozess leistet die Linksmultiplikation mit der Permutationsma-trix

P1 =

0 . . . . . . 0 1... 1 0 0... . . . ... O0 0 1

...1 0 . . . . . . 0 . . . . . . . . . . . .

... 1 0

O ... . . .... . . .... 0 1

← k.

↑k

(Ist k = 1, so hat man P1 = E =Einheitsmatrix zu wählen.) (O steht hier und imFolgenden für die Nullmatrix.)

Für

A(1) := P1A(1), b(1) := P1b

(1)

gilt alsoa

(1)11 6= 0.

Jetzt adieren wir zur zweiten Zeile das − a(1)21

a(1)11

-fache der ersten,..., allgemein zur k-ten

Zeile das − a(1)k1

a(1)11

-fache der ersten Zeile, k = 2, ...,m. Dann stehen in der ersten Spalte


unterhalb der Diagonalen nur Nullen:a

(1)11 a

(1)12 . . . . . . a

(1)1m

0 ∗ . . . . . . ∗...

......

......

...0 ∗ . . . . . . ∗

x1.........xm

=

b(1)1

∗......∗

.

Diese (m− 1)-malige Linearkombination lässt sich aber gerade als Linksmultiplikationmit der elementaren unteren Dreicksmatrix

L1 :=

1 0 . . . . . . 0−l21 1 0... . . .... . . .−lm1 0 1

interpretieren, wobei

lk1 :=a

(1)k1

a(1)11

, k = 2, ...,m

gesetzt wurde.Aus

A(1)x = b(1)

erhalten wir also

L1P1A(1)x = L1P1b

(1)

Wir setzen abkürzend

A(2) := L1P1A(1), b(2) := L1P1b

(1).

Dann hat A(2) die gewünschten Nullen in den Positionen (k, 1), k = 2, ...,m. Dabeiist das ursprüngliche Gleichungssystem Ax = b äquivalent zu modifizierten SystemA(2)x = b(2).

Auf A(2) wendent man nun einen entsprechenden Eliminationsprozess an, der die ersteSpalte festlässt und die zweite Spalte unterhalb der Diagonalen annulliert. RekursiveFortführung liefert in m − 1 Schritten ein äquivalentes Gleichungssystem in Dreiecks-


form:

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗0 0 ∗ . . . . . . ∗... . . . . . . ...... 0

. . . . . . ...0 . . . . . . . . . 0 ∗

︸︷︷︸

A(m)

x1

x2

x3......

xm

︸︷︷︸

x

=

∗∗∗......∗

︸︷︷︸b(m)

.

Hieraus kann die Lösung x, wie am Ende dieses Paragraphen beschrieben, durch „Rücks-ubstitution“ berechnet werden.

Bemerkung 1.5 (Spaltenpivotisierung).Man beachte, dass die Regularität von A nicht ausreicht, in jedem Schritt das Nicht-verschwinden des Diagonalelements zu sichern.

triviales Beispiel:[

0 11 0

]Man muss also eventuell Gleichungen vertauschen, um ein nichtverschwindendes Dia-gonalelement (Pivot-Element, von engl. pivot: Türangel, Drehpunkt) zu erhalten. Eserweist sich als besonders günstg, wenn man möglichst betragsgroße Pivot-Elementewählt, da dann bei der Division zur Bildung der lνµ möglichst betragsgroße Nennerentstehen. Es empfiehlt sich deshalb in jedem Schritt eine Spalten-Pivot-Suche durch-zuführen, die darin besteht, dass man in der Spalte, die gerade dem Eliminationsprozessunterworfen wird, ein betragsgrößtes Element unterhalb der Diagonalen (einschließlichdes Diagonalelements) als Pivot-Element wählt.

Wir fassen unser Vorgehen algorithmisch.

Algorithmus 1.6 (Gauß-Eliminationsverfahren mit Spaltenpivotisierung).Es sei

A(1) = (a(1)ik ) := A = (aik)i,k=1,...,m,

A invertierbar,b(1) = (b

(1)i ) := b = (bi)i=1,...m.

Für ν = 1, ..,m− 1 bilde man A(ν+1) = (a(ν+1)ik )i,k=1,....m auf folgende Weise aus A(ν):

Zunächst bestimmt man ein Pivot-Element a(ν)µν , µ ∈ {ν, ...,m}, in der ν-ten Spalte

gemäß|a(ν)µν | = max

ν≤i≤m|a(ν)iν |.

Durch Vertauschung der ν-ten mit der µ-ten Gleichung des Systems

A(ν)x = b(ν)

erhält man das System


A(ν)x = b(ν)

wobeia(ν)νν 6= 0

ist.Anschließend werden die Elemente der ν-ten Spalte unterhalb der Diagonalen mit Hilfeder folgenden Transformationsformel eliminiert:Für i = ν + 1, ν + 2, ...,m setze:

liν :=a

(ν)iν

a(ν)νν

,

a(ν+1)iν := 0,

a(ν+1)ik := a

(ν)ik − liν a

(ν)νk , k = ν + 1, ...,m,

b(ν+1)i := b

(ν)i − liν b(ν)ν ,

Sonst setze man

a(ν+1)ik := a

(ν)ik , b

(ν+1)i := b

(ν)i

Die Vertauschung leistet eine Linksmultiplikation mit der Permutationsmatrix

Pν =

1 0. . .

10 . . . . . . . . . 1... 1

...... . . . ...... 1

...1 . . . . . . . . . 0

1. . .

0 1

← ν

← µ

↑ν

↑µ

A(ν) := PνA(ν), b

(ν)i := Pb(ν).

Der Übergang von A(ν) nach A(ν+1) lässt sich durch Linksmultiplikation mit der ele-mentaren unteren Dreiecksmatrix

Lν :=

1 0. . .

1

−lν+1,ν. . .

... . . .0 −lm,ν 0 1


deuten, wobei

liν :=a

(ν)iν

a(ν)νν

, i = ν + 1, ...,m,

gesetzt wurde.Die Matrix

A(m) = Lm−1Pm−1Lm−2Pm−2 · · ·L1P1A

ist eine obere Dreiecksmatrix:

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗0

. . . ∗ . . . . . . ∗... . . . . . . ...... 0

. . . . . . ...0 . . . . . . . . . 0 ∗

︸︷︷︸

A(m)

x1

x2

x3......

xm

︸︷︷︸

x

=

∗∗∗......∗

︸︷︷︸b(m)

.

Resultat 1.7 (LR-Zerlegung).Das Gaußsche Eliminationsverfahren liefert die sogenannte „LR-Zerlegung“

PA = LR

wobie P eine Permutationsmatrix, L ein untere und R eine obere Dreiecksmatrix ist,die sich wie folgt ergeben:

A(m) = Lm−1Pm−1Lm−2Pm−1 · · ·L1P1A

= Lm−1(Pm−1Lm−2Pm−1)(Pm−1Pm−2Lm−3Pm−2Pm−1) · · ·· · · (Pm−1Pm−2 · · · P2L1P2 · · ·Pm−2Pm−1) · (Pm−1Pm−2 · · · P2P1)︸︷︷︸

=:P

A

= Lm−1Lm−2 · · · L1PA

mit elementaren Dreiecksmatrizen Lm−1, Lm−2, . . . , L1. D.h.

PA = L−11 · · · L−1

m−2L−1m−1︸︷︷︸

=:L

A(m)︸︷︷︸:=R

Aufgabe 1.8. Man löse das lineare Gleichungssystem2 3 −1 0−6 −5 0 2

2 −5 6 −64 6 2 −3

x1

x2

x3

x4

=

20−45−358

und bestimme explizit die Permutationsmatrix Pν sowie die elementaren unteren Drei-ecksmatrizen Lν,ν = 1, ...,m−1, die bei der Gauß-Elimination mit spaltenweiser Pivot-Suche auftreten.


Bemerkung 1.9 (diagonale Pivot-Wahl).Falls keine Vertauschungen von Gleichungen notwendig sind (diagonale Pivot-Wahl),hat man die Darstellung

A(m) = Lm−1 · · ·L1A

oder

A = L−11 · · ·L−1

m−1A(m).

In Aufgabe 1.4 hatten wir gezeigt, dass L−1ν , ν = 1, ..,m−1, ebenfalls eine elemtare un-

tere Dreiecksmatrix ist, die sich von Lν nur im Vorzeichen in der ν-ten Spalte unterhalbder Diagonalen unterscheidet. Man kann leicht zeigen, dass das Produkt von elemtarenunteren Dreiecksmatrizen eine untere Dreiecksmatrix ist, die in der Diagonalen nurEinsen enthält. Wir folgern dies aus

Aufgabe 1.10.Die untere Dreiecksmatrizen mit normierter Diagonale

∆ :=

1 0

∗ . . .... . . . . . .... . . . . . .∗ . . . . . . ∗ 1

m×m

bilden bezüglich der Multiplikation eine Gruppe.

Die Matrix

A = L−11 · · ·L−1

m−1A(m)

ist somit zerlegt in das Produkt einer unteren Dreiecksmatrix mit normierter Diagonale

L := L−11 · · ·L−1

m−1 = L−11 + L−1

2 + ...+ L−1m−1 − (m− 2)E

= −(L1 + L2 + ...+ Lm−1) +mE

und einer oberen Dreiecksmatrix

R := A(m), also:

∗ . . . . . . ∗...

......

...∗ . . . . . . ∗

︸︷︷︸

A

=

1 0

∗ . . .... . . . . . .∗ . . . ∗ 1

︸︷︷︸

L

∗ . . . . . . ∗

. . . .... . . ...

0 ∗

︸︷︷︸

R


Resultat 1.11 (LR-Zerlegung bei diagonaler Pivot-Wahl).Ist diagonale Pivot-Wahl möglich, so liefert das Gaußsche Eliminationsverfahren die„LR-Zerlegung“

A = LR

der Matrix A. Hierbei ergibt sich L aus den im Verlauf des Verfahrens verwendetenelementaren unteren Dreiecksmatrizen gemäß

L = mE − (L1 + L2 + ...+ Lm−1).

Wir haben gesehen, dass Algorithmus 1.6 ein reguläres Gleichungssystem

Ax = b

in ein äquivalentes Gleichungssystem

A(m)x = b(m)

mit oberer Dreiecksmatrix A(m) transformiert. Ein solches System löst man durchRücksubstitution:

Algorithmus 1.12 (Rücksubstitution).Es gelte

A(m)x = b(m)

mit regulärer oberer Dreiecksmatrix A(m) = (a(m)ik )m×m, b

(m) = (b(m)i ). Dann erhält man

die Komponenten xi, i = 1, ..,m, von x durch Rücksubstitution:Iteration: für i = m,m− 1, ..., 1 berechne

xi =1

a(m)ii

{b(m)i −

m∑k=i+1

a(m)ik xk

}.

Zusammenfassung:

In diesem Abschnitt wurde Ihnen das von der Schule her bekannte Eliminationsver-fahren in systematischer, für die Programmierung geeigneter Form vorgestellt. Hierbeiwurde die Notwendigkeit der Spaltenpivotisierung betont. Damit lässt sich ein Glei-chungssytem mit regulärer Matrix in ein äquivalentes System umformen, das durchRücksubstitution einfach gelöst werden kann.

Bemerkung 1.13 (gestaffeltes Gleichungssystem - Informationselement).Wenn man ein lineares Gleichungssystem auflösen will, wird man in der Regel direkt dasEliminationsverfahren aus Abschnitt 1.2 anwenden und nicht explizit die LR-Zerlegungaufstellen.


Sind dagegen mehrere Gleichungssysteme hintereinander mit derselben Koeffizienten-matrix A zu lösen, so empfiehlt es sich, die LR-Zerlegung von A zu ermitteln und dannjeweils das gestaffelte System

Ly = b,

Rx = y

zu lösen. Dabei bestimmt man y durch das sogenannte Vorwärtseinsetzen (erst y1 be-rechnen, dann y2 usw.) und danach x durch Rücksubstitution (erst xm berechnen, dannxm−1 usw.).Die LR-Zerlegung spielt ebenfalls eine wichtige Rolle bei der Berechnung von Eigen-werten nach dem LR-Verfahren. darauf werden wir später noch eingehen.

Vorteile bietet die LR-Zerlegung auch bei Matrizen speziellen Typs, inbesondere beiBandmatrizen.

Bezeichnung 1.14 (Band-Matrix der Bandbreite d - Tridiagonalmatrix).Eine Matrix des Typs

A =

∗ ∗ . . . ∗ 0

∗ . . . . . . . . .... . . . . . . . . . ∗∗ . . . . . . . . . ...

. . . . . . . . . ∗0 ∗ . . . ∗ ∗

,

wobei aik = 0 für |i−k| ≥ d gilt, bezeichnet man als Bandmatrix der Bandbreite d. Spe-zielle Bandmatrizen sind die Diagonalmatrizen mit d = 1 und die Tridiagonalmatrizenmit d = 2.

Bei der LR-Zerlegung ohne Pivotsuche bleibt die Bandstruktur erhalten. Dies zeigtman in:

Aufgabe 1.15.Für eine Bandmatrix A der Bandbreite d haben die zugehörigen Matrizen L und R dieBandbreite d.

Zusammenfassung:In diesem Abschnitt wurde festgestellt, dass bei diagonaler Pivot-Wahl die Bandbreiteeiner Matrix bei der LR-Zerlegung erhalten bleibt.

1.3 Die Cholesky-Zerlegung

Beim Gaußschen Eliminationsverfahren muss man i.A. Zeilen- (bzw. Spalten-) vertau-schungen vornehmen, um das Nichtverschwinden des Diagonalelementes zu sichern.Diagonale Pivot-Wahl ist nur bei speziellen Matrizen möglich. Wir zeigen dies in die-sem Abschnitt für positiv definite, Hermitesche Matrizen. Dazu erinnern wir uns anfolgende Definition aus der Lineare Algebra.


Definition 1.16 (Hermitesche und positiv definite Matrizen).Eine Matrix A = (aik)m×m heißt

• Hermitesch, falls AH = A

• positiv definit, falls xHAx > 0 für alle 0 6= x ∈ Cm

Dabei bezeichnet x 7→ xH bzw. A 7→ AH den Übergang zu konjugiert-transponiertenVektoren bzw. Matrizen.

Satz 1.17.Die Diagonalelemente einer positiv definiten Matrix sind sämtlich positiv.

Beweis:Es sei ei = (0, ..., 0, 1, 0, ..., 0)t, i = 1, ..,m, der i-te Einheitsvektor. Dann gilt wegenDefinition 1.16

0 < etiAei = aii.

�Eine weitere wichtige Eigeschaft betrifft die Eigenwerte. Dies ist Inhalt der folgendenAufgabe.

Aufgabe 1.18.Die Eigenwerte einer positiv definiten Matrix A sind positiv.

Bei einer positiv definiten Matrix A können wir versuchen, den Gauß-Algorithmussymmetrisch durchzuführen. Dies ergibt dann das so genannte Cholesky-Verfahren.Wir gehen aus von

A(1) := A

und beachten, dass a11 > 0 und A(1) Hermitesch ist. Wir eliminieren nun sowohl dieNichtdiagonalglieder in der ersten Zeile als auch in der ersten Spalte, indem wir

A(2) := L1A(1)LH1

mit

L1 :=

1 0 . . . . . . . . . 0

−a(1)21

a(1)11

1. . . ...

... 0. . . . . . ...

...... . . . . . . . . . 0

...... . . . 1 0

−a(1)m1

a(1)11

0 . . . . . . 0 1


bilden. A(2) hat dann die Form

A(2) =

a

(1)11 0 . . . . . . 00 . . . . . . . . ....

......

... B(2)

0...

, a(1)11 = a11.

Wegen(A(2))H = L1(A

(1))HLH1 = L1A(1)LH1 = A(2)

ist A(2) und damit auch B(2) Hermitesch. A(2) ist sogar positiv definit: Denn für jedenVektor 0 6= x ∈ Cm gilt wegen der Regularität von LH1

y := LH1 x 6= 0;

folglich ergibt sich

xHA(2)x = xHL1A(1)LH1 x

= (LH1 x)HA(1)(LH1 x)

= yHA(1)y > 0

wegen der positiven Definitheit von A(1). Mit A(2) ist aber offensichtlich auch B(2)

positiv definit. Wegen Satz 1.17 gilt dann

a(2)22 > 0,

und die symmetrische Dreieckzerlegung lässt sich in der beschriebenen Weise auf B(2)

statt A(1) anwenden. Nach m− 1 Schritten erhält man die Zerlegung

Lm−1 · · · L1ALH1 · · · LHm−1 =

a

(1)11 0

a(2)22

. . .. . .

0 a(m)mm

︸︷︷︸

=:diag(a(1)11 ,...,a

(m)mm)

.

Wir setztenD := diag(a

(1)11 , .., a

(m)mm)

und √D := diag(

√a

(1)11 , ...,

√a

(m)mm).

Man beachte, dass√D wegen a(i)

ii > 0, i = 1, ...,m, wohldefiniert ist.Dann gilt

D =√D√D


Insgesamt haben wir die Darstellung

A = L−11 ...L−1

m−1

√D√D(LHm−1)

−1...(LH1 )−1

gefunden. Wir setzen

L := L−11 ...L−1

m−1

√D,

LH =√D(L−1

m−1)−1...(LH1 )−1

Es resultiert dann die Cholesky-Zerlegung

A = LLH ;

dabei ist L eine untere Dreiecksmatrix. Man beachte, dass die Diagonalelemente von Ljetzt (im Gegensatz zur LR-Zerlegung beim Gaußschen Eliminationsverfahren) nichtmehr notwendig den Wert Eins haben.

Wir fassen zusammen:

Satz 1.19 (Cholesky-Zerlegung einer positiv definiten, Hermiteschen Matrix).Eine positiv definite, Hermitesche Matrix A lässt sich zerlegen in das Produkt einerunteren Dreiecksmatrix L mit ihrer konjugiert-transponierten:

A = LLH .

Wir verwenden zur expliziten Bestimmung der Elemente lik, i = 1, ...,m, k = 1, ..., i,eine geeignete Reihenfolge. Hier geht man am einfachsten zeilenweise vor.Aus

A = LLH

erhält man

aik =m∑µ=1

liµlkµ, i, k = 1, ...,m,

woraus wegen der Dreiecksgestalt von L die Darstellung

aik =

min(i,k)∑µ=1

liµlkµ, i, k = 1, ..,m,

folgt. Insgesamt ergibt sich so:

Algorithmus 1.20 (Cholesky-Verfahren).Für i = 1, ...,m:

1. Für k = 1, ..., i− 1 berechne

lik :=1

lkk

{aik −

k−1∑µ=1

liµlkµ

}.

2. Berechne

lii :=

√√√√aii −i−1∑µ=1

|liµ|2.


Der Rechenaufwand beim Cholesky-Verfahren ist wesentlich niedriger als beim Gauß-Algorithmus. Wir lösen in diesem Zusammenhang folgende Aufgabe.

Aufgabe 1.21.Man bestimme den Rechenaufwand, der bei der Cholesky-Zerlegung einer positiv defi-niten (m×m)-Matrix erforderlich ist

Zusammenfassung:In diesem Abschnitt haben Sie eine symmetrische Variante des Gaußschen Eliminati-onsverfahrens für positiv definite Matrizen kennengelernt. Dieses sogenannte Cholesky-Verfahren ist insbesondere auch numerisch weniger aufwendig.

1.4 Die QR-Zerlegung (Ergänzung)

Der Gauß-Algorithmus liefert mit Hilfe elementarer Dreiecksmatrizen die LR-Zerlegungeiner regulären Matrix; dabei wird ein gegebenes System Ax = b auf (obere) Dreiecks-gestalt gebracht. Wir werden bei der Fehleranalyse des Gauß-Algorithmus feststellen,dass die LR-Zerlegung u.U. ein ungünstiges Fehlerverhalten zeigen kann. In gewissenFällen kann es daher angebracht sein, die Reduktion auf Dreiecksgestalt mit Hilfe uni-tärer (oder orthogonaler) Matrizen durchzuführen. Zu diesem Zweck erinnern wir unsan das Orthogonalisierungsverfahren von E. Schmidt, das Ihnen in der Lineare Algebravorgestellt wurde.

Aufgabe 1.22 (Orthogonalisierung nach E. Schmidt).Es seien a1, .., am m linear unabhängige Vektoren aus Cm (oder aus Rm). Man kon-struiere dazu rekursiv eine Orthonormalbasis q1, ..., qm, d.h. für q1, ..., qm gelte

(qν , qµ) = δνµ, ν, µ = 1, ...,m undaν ∈ span(q1, ..., qν), ν = 1, ...,m,

wenn (., .) das kanonische Skalarprodukt in Cm (oder in Rm) bezeichnet.

Die in dieser Aufgabe hergeleiteten Formeln, welche die Vektoren aν mit den qν , ν =1, ...,m, verbinden, sind vom Typ

a1 = r11q1,

a2 = r12q1 + r22q2,...

am = r1mq1 + r2mq2 + ...+ rmmqm

(Beachten Sie, dass die sich hier ergebende Dreiecksform vom rekursiven Aufbau desSchmidtschen Orthogonalisierungsverfahren herrührt.) Wenn wir jetzt die Vektorena1, ..., am und q1, ..., qm jeweils als Spaltenvektoren einer Matrix A und einer Matrix Qauffassen, können wir die Orthogonalisierungsformeln in der Form

(a1, ..., am) = (q1, ..., qm)

r11 . . . r1m. . . ...

0 rmm


schreiben. Komponentenweise mit

aν =: (a1ν , a2ν , ..., amν)t, ν = 1, ...,m

qν =: (q1ν , q2ν , ..., qmν)t, ν = 1, ...,m

gilt dann

A := (aµν)µ=1,...,mν=1,...,m

=

q11 . . . q1m...

...qm1 . . . qmm

︸︷︷︸

:=Q

r11 . . . r1m. . . ...

0 rmm

︸︷︷︸

:=R

Resultat 1.23 (QR-Zerlegung von A).Das Orthogonalisierungsverfahren nach E. Schmidt liefert die Darstellung

A = QR („QR-Zerlegung“);

dabei ist Q eine unitäre Matrix, d.h.

QHQ = E, Q−1 = QH ,

und R eine obere Dreiecksmatrix.

Mit Hilfe der QR-Zerlegung ist die Auflösung eines linearen Gleichungssystems

Ax = b

auf die Auflösung eines „gestaffelten“ Systems

Rx = Q−1b = QHb

zurückgeführt, die sich rekursiv durch Rücksubstitution wie bei

Ly = b,

Rx = y

ergibt.

Bemerkung 1.24.In der Praxis stößt man beim Orthogonalisierungsverfahren nach E. Schmidt auf Schwie-rigkeiten, falls die Ausgangsvektoren ai „fast“ linear abhängig sind. Hier können schongeringe Rundungsfehler eine starke Störung der Orthogonalität der berechneten Vekto-ren q1, ..., qm verursachen.

Günstiger lässt sich die QR-Zerlegung mit Hilfe von geeigneter Spiegelung, den soge-nannten Householder-Transformationen, gewinnen.

Hierzu betrachten wir einen Vektor w ∈ Cm der euklidischen Länge 1, d.h. es geltewHw = 1. Ist E die Einheitsmatrix der Dimension m, so ist die (m×m)-Matrix

Hw := E − 2wwH

wegen(E − 2wwH)H = EH − 2(wwH)H = E − 2wwH

Hermitesch.


Definition 1.25 (elementare Hermitesche Matrix - Householder-Transformation).Eine Matrix des Typs

Hw := E − 2wwH , w ∈ Cm, wHw = 1, E = m×m-Einheitsmatrix

heißt elementare Hermitesche Matrix; die durch Hw vermittelte Abbildung des RaumesCm in sich bezeichnet man als Householder-Transformation.

Wir stellen einige wichtige Eigenschaften elementarer Hermitescher Matrizen zusam-men:

Satz 1.26.Es sei Hw eine elementare Hermitesche (m×m)-Matrix.Dann ist Hw

1. unitär: H−1w = HH

w ,

2. involutorisch: (Hw)2 = E, und

3. die Abbildung x 7→ Hwx entspricht einer Spiegelung von x an der zu w orthogo-nalen Hyperebene L.

Beweis:

1. Wegen

HHw Hw = HwHw = (E − 2wwH)(E − 2wwH) = E − 4wwH + 4wwHwwH

folgt unter Berücksichtigung von wHw = 1 die Beziehung HHw ·Hw = E; also gilt:

H−1w = HH

w .

2. ist wegen (1) und wegen HHw = Hw klar.

3. Einen Vektor x ∈ Cm projizieren wir auf die eindeutig bestimmte Hyperebene L,welche orthogonal zu w ist, vgl. Abbildung 1.2.

Dann lässt sich x in eindeutiger Weise in der Form

x = tw + v mit t ∈ C, v ∈ L

darstellen. Spiegelung an L entspricht dem Übergang von

x 7→ x := −tw + v.

WegenwHx = twHw + wHv = t

folgtx = −wHxw + v

und daraus mitv = x− tw = x− wHxw


L

x

v

x~

w

tw

−tw

Abbildung 1.2: Spiegelung von x an der zu w orthogonalen Hyperebene L

die Darstellung

x = −wHxw + x− wHxw= x− 2wHxw

= x− 2wwHx (beachte: wHx ∈ C !)= (E − 2wwH)x

= Hwx.

�

Mit Hilfe von Householder-Transformationen werden wir ebenfalls die QR-Zerlegungkonstruieren. Dazu benötigen wir den algorithmischen Zusammenhang, der die Spie-gelung eines gegebenen Vektors x in ein skalares Vielfaches eines weiteren gegebenenVektors y beschreibt; y wird ein kanonischer Einheitsvektor ek, 1 ≤ k ≤ m, sein.Wir machen uns zunächst anschaulich klar, dass es zwei Spiegelungen gibt, die dasgewünschte leisten, vgl. Abbildung 1.3.

Nach diesen anschaulichen Überlegungen stellen wir nun den entsprechenden algorith-mischen Zusammenhang auf.

Gegeben sei der Vektor x 6= 0. Wir suchen elementare Matrizen

Hw = E − 2wwH , wHw = 1,

welcheHwx = αek, k ∈ 1, ...,m fest, 0 6= α ∈ C,

liefern; dabei bezeichnetek = (0, ..., 0, 1, 0, ..., 0)t


L

x

x~

w

y

(w x)wH

x−(w x)wH

x

y

w

(w x)wH

L

x~

x−(w x)wH

Abbildung 1.3: Zwei mögliche Spiegelungen

den k-ten Einheitsvektor.

Zunächst beachten wir, dass eine Spiegelung die euklidische Länge eines Vektors inva-riant lässt; also gilt

|α| = ‖x‖e :=√xHx =

√√√√ m∑ν=1

|xν |2 6= 0,

wenn x die Komponenten x1, ..., xm hat. Wir verwenden die Darstellung

xk = |xk| · eiϕk ( ϕk := 0 für xk = 0)

von xk in Polarkoordinaten.Wegen x 6= 0 können wir nun w ∈ Cm mit wHw = 1 und α ∈ C derart bestimmen,dass

αek = Hwx

gilt. Denn ausαek = (E − 2wwH)x = x− 2wwHx


folgtx− αek = 2wwHx.

Hieraus erhält man durch Multiplikation mit xH von links

xHx− αxHek = 2xHwwHx

oderxHx− αxk = 2|wHx|2.

Diese Gleichung zeigt unter Beachtung der Tatsache, dass xHx reell ist, dass auch α ·xkreell sein muss. Ist xk 6= 0, so kann α wegen

xk = |xk| · eiϕk und α 6= 0

nur die Darstellungen

α1 = |α| · eiϕk oder α2 = −|α| · eiϕk

besitzen. Beide Vorzeichen sind möglich; dies steht im Einklang mit Abbildung 1.3,wo wir die beiden möglichen Spiegelungen dargestellt haben. Ist xk = 0, so kann dasArgument von α zunächst beliebig gewählt werden; im Einklang mit der Festlegungϕk = 0 beschränken wir uns auch hier auf die Fälle α1 = |α| oder α2 = −|α|. DenVektor w erhalten wir aus der Beziehung

x− α1,2ek = 2wwHx = 2(wHx)w,

d.h. w is ein Vielfaches von x−α1,2ek. Welches ist die bessere Wahl: α1 oder α2? Wegen

‖x− α1,2ek‖2e = |x1|2 + ...+ |xk−1|2 + |xk − α1,2|2 + |xk+1|2 + ...+ |xm|2

giltx− α2ek 6= 0 und ‖x− α2ek‖e > ‖x− α1ek‖e.

Man setzt deshalbw :=

x− α2ek‖x− α2ek‖e

,

um den Rundungsfehler der Komponente wk von w möglichst klein zu halten. DieseWahl von w leistet das Gewünschte, denn α2 = −‖x‖eeiϕk und daher

Hwx = x− 2w(wHx)

= x− 2‖x‖2e − α2xk

‖x‖2e − α2xk − α2xk + |α2|2(x− α2ek)

= x− 2‖x‖2e − α2xk

‖x‖2e − α2xk − α2xk + |α2|2(x− α2ek)

= α2ek.

Wir stellen die Transformationsformeln für eine Householder-Spiegelung nochmals über-sichtlich zusammen.


Algorithmus 1.27 (Spiegelung durch Householder-Transformation).Es sei x = (x1, ..., xm)t 6= 0 ein gegebener Vektor und k ∈ 1, ...,m.Ist xk 6= 0, so setze man

xk =: |xk|eiϕ.

Ist xk = 0, so setze manϕ := 0.

Man berechne

|α| := ‖x‖e =

√√√√ m∑ν=1

|xν |2,

α := −|α|eiϕ,β := ‖x− αek‖e := [|x1|2 + ...+ |xk−1|2 + (|xk|+ |α|)2 + |xk+1|2 + ...+ |xm|2]1/2,

w :=1

β(x− αek).

Dann giltwHw = 1,

und die durch die elementare Hermitesche Matrix

Hw := E − 2wwH

gegebene Householder-Transformation spiegelt den Vektor x auf den Vektor αek 6= 0,

Hw := x 7→ αek.

(Für reelles xk 6= 0 berücksichtige man, dass eiϕ = sign(xk) gilt; für x ∈ Rm verläuftdie Rechnung also im Reellen).

Diesen Algorithmus verwenden wir nun dazu, die QR-Zerlegung

A = QR

einer gegebenen regulären Matrix A zu erzeugen. Wir gehen rekursiv vor und spiegelnim ersten Schritt den ersten Spaltenvektor a1 von A = (a1, ..., am) auf ein skalaresVielfaches von e1. Dies erreichen wir durch geeignete Wahl von w1 ∈ Cm entsprechenddem Algorithmus 1.27. Dann hat

A(1) := Hw1A = (E − 2w1wH1 )A, wH1 w1 = 1,

die Gestalt

A(1) =

∗ a(1)12 ∗ . . . . . . ∗

0 a(1)22 ∗ . . . . . . ∗

0...

......

......

......

......

......

0 a(1)n2 ∗ . . . . . . ∗

.


Im zweiten Schritt wird w2 ∈ Cm so konstruiert, dass Hw2 in der zweiten Spalte unter-halb der Diagonalen Nullen erzeugt und die erste Spalte nicht verändert:

w2 =

(0w2

); w2 ∈ Cm−1

so, dass die Householder-Transformation Hw2 in Cm−1 liefert:

Hw2

a(1)22...a

(1)n2

= β

10...0

∈ Cm−1.

Dann

Hw2

10...0

=

10...0

, Hw2

a

(1)12......a

(1)k2

=

a

(1)12

β0...0

,

also

Hw2A(1) =

∗ ∗ ∗ · · · ∗0 ∗ ...

...... 0

......

......

......

0 0 ∗ . . . ∗

=: A(2)

Im dritten Schritt gehen wir wie folgt vor:

w3 =

00w3

, w3 ∈ Cm−2,

wobei w3 in Cm−2 so gewählt wird, dass Hw3 den Vektor

a(2)33...a

(2)n3

∈ Cm−2 auf

γ

10...0

∈ Cm−2 abbildet, etc.. In dieser Weise fortfahrend erhält man in m − 1

Schritten die Darstellung

A(m−1) = Hwm−1 ...Hw1A =: R =

∗ . . . . . . ∗

. . . .... . . ...

0 ∗

.Dabei hat R obere Dreicksform und nichtverschwindende Diagonalelemente.


Aufgabe 1.28. Man formuliere einen Algorithmus, der mit Hilfe von Householder-Transformationen die QR-Zerlegung einer reellen regulären Matrix liefert.

Man beachte, dass die QR-Zerlegung für jede reguläre (m×m)-Matrix existiert, wäh-rend die LR-Zerlegung selbst bei regulären Maritzen i.A. nur unter Verwendung vonZeilen- (oder Spalten-) permutationen (Pivot-Suche) möglich ist.Resultat 1.29 (QR-Zerlegung durch Householder-Transformation).Eine reguläre (m × m)-Matrix A lässt sich mit Hilfe von m − 1 Householder-Trans-formationen in der Form

A = QR mit QHQ = E, R= obere Dreiecksmatrix,

darstellen. Das Gleichungssystem Ax = b ist nun leicht auflösbar: QRx = b ⇔ Rx =QHb da Q unitär (Auflösen durch Rückwärtssubstitution).

Zusatz: Es sei bemerkt, dass man auch QR-Zerlegungen singulärer quadratischer Ma-trizen bestimmen kann, wenn Spaltenpermutationen zugelassen werden. In diesem Fallwird zu Beginn des k-ten Schrittes in der oben (für reguläre Matrizen) beschriebenenQR-Zerlegung die Matrix

A(k) =

∗ . . . . . . . . . ∗. . . ...

∗ . . . ∗

0 B(k)

von rechts mit einer (m×m)-Permutationsmatrix P (k) multipliziert,

P (k) =

1 0. . .

1

0 P(k)1

wobei die ((m − k + 1) × (m − k + 1))-Permutationsmatrix P

(k)1 so gewählt wird,

dass die Matrix B(k) · P (k)1 in der ersten Spalte eine nichtverschwindende Komponente

besitzt. Auf A(k)P (k) kann nun die im Algorithmus 1.27 beschriebene Householder-Transformation angewendet werden. Das Verfahren bricht nach genau r := Rang(A)Schritten ab (wenn A singulär ist) und liefert

A(r) = Hwr · · ·Hw1AP(1) · · ·P (r) =

∗ . . . . . . . . . . . . ∗. . . ...

∗ . . . . . . ∗

0 O

bzw.

AP (1) · · ·P (r) = Hw1 · · ·HwrA(r) =: QR.

Kapitel 2

Eigenwertprobleme

2.1 Begriffe und Definitionen

Gegeben sei eine Matrix A ∈ Km×m (K = R oder K = C).

Definition 2.1 (Eigenwert, Eigenvektor).Ein Wert λ ∈ C heißt Eigenwert von A, falls ein Vektor u ∈ Cm \ {0} existiert mit

Au = λu.

Jeder derartige Vektor u 6= 0 heißt ein zu λ gehöriger Eigenvektor.

Die Eigenwerte einer Matrix können berechnet werden als Nullstellen des charakteris-tischen Polynoms

pA(λ) := det(A− λE)

der Matrix A. Dieses Vorgehen ist numerisch instabil und daher nicht zu empfehlen. Zielder Untersuchungen dieses Kapitels ist es, numerisch praktikable Verfahren zu finden,mit denen man (unter geeigneten Voraussetzungen an die Matrix A) Näherungen andie Eigenwerte und Eigenvektoren von A berechnen kann.

Wir werden uns im Folgenden auf die Klasse der diagonalisierbaren Matrizen beschrän-ken. Dabei heißt eine m×m Matrix A diagonalisierbar, falls es m linear unabhängigeEigenvektoren u1, . . . , um der Matrix A gibt. Die Vektoren u1, . . . , um bilden eine Basisdes Cm aus Eigenvektoren. Der zu ui gehörige Eigenwert sei mit λi bezeichnet, i =1, . . . ,m. Setze nun

T :=

u1 u2 . . . um

.Die m × m-Matrix T ist regulär, da ihre Spalten u1, . . . , um linear unabhängig sind.Wir berechnen

AT =

Au1 Au2 . . . Aum

=

λ1u1 λ2u

2 . . . λmum

=

u1 u2 . . . um

λ1 0

. . .0 λm

= T

λ1 0. . .

0 λm

,28

KAPITEL 2. EIGENWERTPROBLEME 29

und erhalten somit für eine diagonalisierbare Matrix A die Darstellung

T−1AT =

λ1 0. . .

0 λm

= diag(λ1, . . . , λm)

bzw.A = T diag(λ1, . . . , λm)T−1.

Unter jeder der folgenden vier Bedingungen ist die Matrix A diagonalisierbar:

(1) A besitzt m verschiedene Eigenwerte.

(2) A ist normal, d.h. AAH = AHA. In diesem Fall kann man die Eigenvektoren sogarso wählen, daß u1 . . . , um eine Orthonormalbasis ist. Damit ist T eine unitäreMatrix, denn

THT =

u1H

u2H

...umH

u1 u2 . . . um

= E, d.h. T−1 = TH .

(3) A ist Hermitesch. Denn dann ist wegen AH = A die Matrix A insbesonderenormal. In diesem Fall sind die Eigenwerte λ1, . . . , λm alle reell.

(4) A ist unitär. Denn dann ist wegen AHA = E = AAH die Matrix A insbesonderenormal. In diesem Fall gilt für die Eigenwerte: |λ1| = . . . = |λm| = 1.

2.2 Die von-Mises Iteration

Ziel diese Abschnittes ist es, ein iteratives Verfahren zur Bestimmung eines Eigenwerteseiner diagonalisierbaren Matrix zu formulieren. Es sei also A ∈ Cm×m eine diagonali-sierbare m×m-Matrix. Wir ordnen die Eigenwerte gemäß der Größe ihres Betrages

|λ1| ≥ |λ2| ≥ . . . ≥ |λm|.

Im Folgenden betrachten wir den Spezialfall

|λ1| > |λ2| ≥ . . . ≥ |λm|

und beschreiben ein Verfahren zur Bestimmung des betragsgrößten Eigenwertes λ1. Seialso u1, . . . , um mit Aui = λiu

i, i = 1, . . . ,m die Basis aus Eigenvektoren von A. Einbeliebiger Vektor x0 ∈ Cm lässt sich in der Basis entwickeln:

x0 = ρ1u1 + ρ2u

2 + . . .+ ρmum mit ρ1, . . . , ρm ∈ C.

Wir nehmen an, dass ρ1 6= 0 gilt.

Definierexk := Axk−1 für k = 1, 2, . . . .


Dann gilt

xk = Axk−1 = A(Axk−2) = . . . = A · A · . . . · A︸︷︷︸=:Ak

x0

= Akx0.

Es folgt

xk = Akx0 = Ak(ρ1u1 + ρ2u

2 + . . .+ ρmum)

= Ak−1(ρ1Au1 + ρ2Au

2 + . . .+ ρmAum)

= Ak−1(ρ1λ1u1 + ρ2λ2u

2 + . . .+ ρmλmum)

= . . .

= ρ1λk1u

1 + ρ2λk2u

2 + . . .+ ρmλkmu

m.

Folglich gilt:

xk

λk1= ρ1u

1 + ρ2

(λ2

λ1

)k︸︷︷︸→0

u2 + . . .+ ρm

(λmλ1

)k︸︷︷︸→0

um

→ ρ1u1 für k →∞.

Problem: λ1 ist gesucht, d.h. im Allgemeinen nicht bekannt! Abhilfe wird durch diefolgende Modifikation der obigen Iteration geschaffen.

Algorithmus 2.2 (Von-Mises Iteration).Sei A eine diagonalisierbare m×m-Matrix; wähle Startvektor x0 ∈ Cm wie zuvor.Iteration: Für k = 1, 2, ... bilde die Vektoren

zk :=Axk−1

xk :=zk

zkik, wobei der Index ik so gewählt ist, dass gilt: |zkik | =

mmaxi=1|zki |

Resultat 2.3 (Konvergenz der von-Mises Iteration).Für die von-Mises Iteration gilt:

• zk+1ik→ λ1 für k →∞

• xk nähert sich einem Vielfachen des Eigenvektors u1. Genauer:

xk − u1

u1ik

→ 0 für k →∞.

Beweis: Wir skizzieren die Beweisschritte.


1. Es gilt folgende Darstellung für den k-ten iterierten Vektoren

xk =zk

zkik=

Axk−1

(Axk−1)ik=

Azk−1 · 1

zk−1ik−1

(Azk−1)ik · 1

zk−1ik−1

=A2xk−2

(A2xk−2)ik= . . .

=Akx0

(Akx0)ik

2. Nun betrachten wir zk+1ik

und erhalten

zk+1ik

= (Axk)ik =(Ak+1x0)ik(Akx0)ik

=(ρ1λ

k+11 u1 + ρ2λ

k+12 u2 + . . .+ ρmλ

k+1m um)ik

(ρ1λk1u1 + ρ2λk2u

2 + . . .+ ρmλkmum)ik

= λ1

(ρ1u

1 + ρ2

(λ2

λ1

)k+1

u2 + . . .+ ρm

(λmλ1

)k+1

um)ik(

ρ1u1 + ρ2

(λ2

λ1

)ku2 + . . .+ ρm

(λmλ1

)kum)ik

→ λ1 für k →∞,

da die Terme(λ2

λ1

)k, . . . ,

(λmλ1

)kfür k → ∞ gegen Null streben. Damit ist die erste

Aussage des Resultates bewiesen.

3. Die zweite Aussage folgt auf ähnliche Art und Weise:

xk − u1

u1ik

=Akx0

(Akx0)ik− u1

u1ik

=ρ1λ

k1u

1 + ρ2λk2u

2 + . . .+ ρmλkmu

m

(ρ1λk1u1 + ρ2λk2u

2 + . . .+ ρmλkmum)ik

− u1

u1ik

=ρ1u

1 + ρ2

(λ2

λ1

)ku2 + . . .+ ρm

(λmλ1

)kum(

ρ1u1 + ρ2

(λ2

λ1

)ku2 + . . .+ ρm

(λmλ1

)kum)ik

− u1

u1ik

→ 0 für k →∞,

da wiederum die Terme(λ2

λ1

)k, . . . ,

(λmλ1

)kfür k → ∞ gegen Null streben. Damit ist

die Konvergenz der von-Mises Iteration geklärt. �

Bemerkung: Die Bedingung ρ1 6= 0 bei der Wahl des Startvektors x0 bereitet keineProbleme, denn aufgrund von Rundungsfehlern ist dies spätestens ab dem zweitenIterationsschritt gewährleistet.


2.3 Die inverse Iteration von Wielandt

Die folgende Variante der von-Mises Iteration liefert Approximationen des betrags-kleinsten Eigenwertes einer diagonalisierbaren und invertierbaren Matrix A. Wiederumseien λ1, . . . λm die Eigenwerte von A mit zugehöriger Basis aus Eigenvektoren ui mit

Aui = λiui für i = 1, . . . ,m,

wobei gelten möge:|λ1| ≥ |λ2| ≥ . . . > |λm|.

Da A als invertierbar vorausgesetzt wurde, gilt

ui = λiA−1ui bzw. A−1ui =

1

λiui für i = 1, . . . ,m.

Das bedeutet, dass die Matrix A−1 die Eigenwerte 1λ1, . . . , 1

λmmit zugehörigen Eigen-

vektoren u1, . . . , um hat. Außerdem gilt1

|λm|>

1

|λm−1|≥ . . . ≥ 1

|λ1|.

Nun wenden wir die von-Mises Iteration auf die Matrix A−1 an, deren betragsgrößterEigenwert gerade 1/λm ist. Das entstehende Verfahren heißt inverse Iteration.

Algorithmus 2.4 (Inverse Iteration).Sei A eine diagonalisierbare, reguläre m×m-Matrix; wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bilde die Vektoren,

wk :=A−1yk−1

yk :=wk

wkik, wobei der Index ik so gewählt ist, dass gilt: |wkik | =

mmaxi=1|wki |

Resultat 2.5 (Konvergenz der inversen Iteration).Für die inverse Iteration gilt:

• wk+1ik→ 1

λmfür k →∞

• yk nähert sich einem Vielfachen des Eigenvektors um. Genauer:

yk − um

umik→ 0 für k →∞.

In der Praxis wird A−1 nicht berechnet. Anstelle dessen wird der Algorithmus derinversen Iteration wie folgt formuliert:

Algorithmus 2.6 (Inverse Iteration – Variante).Sei A eine diagonalisierbare, reguläre m×m-Matrix; wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem Awk = yk−1

yk :=wk


mmaxi=1|wki |


Für die Lösung des linearen Gleichungssystems kann man z.B. die LR-Zerlegung derMatrix A bestimmen, vgl. Kapitel 1.

Zusammenfassung:

Die m×m-Matrix A sei diagonalisierbar. Die von-Mises Iteration liefert Approximatio-nen an den betragsgrößten Eigenwert von A (und den zugehörigen Eigenvektor). Dieinverse Iteration liefert (sofern A invertierbar ist) Approximationen an den Kehrwertdes betragskleinsten Eigenwertes von A (und den zugehörigen Eigenvektor).

Praktischer Nutzen der inversen Iteration:

Angenommen, wir kennen bereits eine brauchbare Approximation λ an einen Eigenwertλj, d.h.

|λ− λj| < |λ− λl| für alle l 6= j.

Die bedeutet, dass λj − λ der betragskleinste Eigenwert der Matrix A − λE ist. Nunkönnen wir die inverse Iteration anwenden.

Wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem (A− λE)wk = yk−1

yk :=wk


mmaxi=1|wki |

Diese Iteration liefert das Ergebnis:

yk+1ik→ 1

λj − λfür k →∞

bzw.λ+

1

yk+1ik

→ λj für k →∞,

d.h. wir erhalten ein iteratives Verfahren, das verbesserte Approxmationen an λj liefert.

Bemerkung: Es liegt nahe, in jedem Iterationsschritt λ durch die gerade neu gewon-nene bessere Approximation an λj zu ersetzen. Dies führt zu folgendem Algorithmus:

Wähle Startvektor y0 ∈ Cm. Setze µ0 := λ =: µ1.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem (A− µk−1E)wk = yk−1

yk :=wk


mmaxi=1|wki |

µk := µk−1 +1

ykik−1

für k ≥ 2.


2.4 Das LR-Verfahren und das QR-Verfahren für Ei-genwertprobleme (Ergänzung)

Wir bereits zuvor erwähnt, setzen wir voraus, daß die Matrix A diagonalisierbar ist.Von Rutishauser wurde 1958 das LR-Verfahren vorgeschlagen. Wie der Name schonandeutet, wird dabei an wesentlicher Stelle die LR-Zerlegung aus Abschnitt 1.2 benützt.

Wir beginnen mit einer Motivation für das weitere Vorgehen: Für die Matrix A =: A1

existiere die LR-Zerlegung (ohne Zeilenvertauschungen)

A1 = L1R1,

wobei

L1 =

1 0

∗ . . .... . . . . . .... . . . . . .∗ . . . . . . ∗ 1

,

R1 =

∗ . . . . . . . . . ∗

. . . .... . . ...

. . . ...0 ∗

untere bzw. obere Dreiecksmatrizen sind. Nun wollen wir überlegen, wie die LR-Zerlegung der k-ten Potzenz Ak von A aussieht. Für die k-te Potenz Ak folgt zuerst

Ak = Ak1 = L1R1L1R1 · · · L1R1L1R1︸︷︷︸k−mal der Faktor L1R1

.

Wir setzenA2 := R1L1

und erhaltenAk1 = L1 A2 · · · A2︸︷︷︸

k − 1 Faktoren

R1 = L1Ak−12 R1.

Man erkennt, wie man durch Wiederholung dieses Prozesses eine Faktorisierung vonAk erhalten kann.

Resultat 2.7.Setze

A1 := A.

Wir nehmen an, daß die LR-Zerlegungen (ohne Zeilenvertauschungen)

Aν = LνRν , ν = 1, ..., k,

für A1 und für die Matrizen

Aν := Rν−1Lν−1, ν = 2, ..., k


existieren. Dann giltAk = L1L2 · · · LkRkRk−1 · · ·R1.

Setzt manLk := L1L2 · · · Lk und Rk := RkRk−1 · · ·R1,

so ist Lk eine untere Dreiecksmatrix mit normierter Diagonale und Rk eine obere Drei-ecksmatrix. Damit haben wir die LR-Zerlegung

Ak := LkRk

von Ak bestimmt.

Wir betrachten nun eine diagonalisierbare m×m-Matrix A, bei der λ1 der dominanteEigenwert ist, d.h.:

|λ1| > |λν |, ν = 2, ...,m.

Die zugehörige Basis aus Eigenvektoren sei {u1, ..., um}. Wir starten nun ein Iterati-onsverfahren mit

z0 := e1 = (1, 0, ..., 0)t

und setzenzk := Azk−1 = Akz0 = Ake1.

In der Basisdarstellung des Vektors e1

e1 = ρ1u1 + ρ2u2 + ...+ ρmum

gelte die Annahmeρ1 6= 0.

Dann folgt

zk = Ak(ρ1u1 + ρ2u2 + ...+ ρmum)

= ρ1λk1u1 + ρ2λ

k2u2 + ...+ ρmλ

kmum

= λk1

{ρ1u1 +

m∑µ=2

ρµ

[λµλ1

]kuµ

},

und darauszkλk1−→ ρ1u1 für k →∞.

Zum Vergleich berechnen wir erneut zk; diesmal jedoch unter Verwendung der zuvorerörterten LR-Zerlegung von Ak

Ak = LkRk.


Unter Ausnützung der Dreiecksgestalt von Lk und Rk sowie der besonderen Form deskanonischen Einheitsvektors e1 berechnet man

zk = Ake1 =

1 0

l(k)21

. . .... . . . . . .... . . . . . .l(k)m1 . . . . . . l

(k)mm−1 1

︸︷︷︸

Lk

r(k)11 . . . . . . . . . r

(k)1m

. . . .... . . ...

. . . ...0 r

(k)mm

︸︷︷︸

Rk

10......0

= r(k)11

(1, lk21, ..., l

km1

)t.

Wir erhalten also

zkλk1

=r(k)11

λk1

1

l(k)21...l(k)m1

︸︷︷︸

=:l(k)1

→ ρ1

η11

η21...ηm1

︸︷︷︸

:=u1 6=0

für k →∞

und insbesondere (bei Betrachtung der ersten Komponente):

r(k)11

λk1→ ρ1η11 für k →∞.

Setzt manRk =:

(r(k)ij

)m×m

,

so erhält man ausRk = RkRk−1

die Beziehungr(k)11 = r

(k)11 r

(k−1)11 .

Unter der Annahmeη11 6= 0

folgt dann aus der Konvergenz

r(k)11 λ

−k1 → ρ1η11 für k →∞,

dass das linke obere Element der oberen Dreiecksmatrizen Rk gegen den dominantenEigenwert konvergiert:

r(k)11 =

r(k)11

r(k−1)11

=r(k)11 λ

−k1 λ1

r(k−1)11 λ

−(k−1)1

→ ρ1η11λ1

ρ1η11

= λ1 für k →∞.

Weiter konvergiert die erste Spalte der unteren Dreiecksmatrizen Lk wegen

zkλk1

=r(k)11

λk1

(1, l

(k)21 , ..., l

(k)m1

)t→ ρ1 (η11, η21, ..., ηm1)

t , k →∞,


gegen einen zu λ1 gehörenden Eigenvektor:(1, l

(k)21 , ..., l

(k)m1

)t→ 1

η11

(η11, ..., ηm1)t =

u1

η11

, k →∞.

Diese Konvergenzaussagen, insbesondere die Aussage

r(k)11 → λ1 für k →∞,

erhielten wir unter einschränkenden Bedingungen an λ1 (dominanter Eigenwert) undu1 (η11 6= 0), sowie unter der Annahme, dass die LR-Zerlegung für jedes Ak existiert.

Damit wird die Vermutung nahegelegt, dass unter weiteren Bedingungen an A (vgl.Resultat 2.9) die Hauptdiagonalelemente von Rk gegen die Eigenwerte von A konver-gieren und alle Spalten von Lk - und damit die Matrix Lk selbst - konvergieren. Da dieLk normierte untere Dreiecksmatrizen sind, folgt wegen

Lk+1 = LkLk

aus der Konvergenz der Lk, dass die Lk gegen die Einheitsmatrix konvergieren unddamit in

Ak = LkRk

die Elemente unterhalb der Hauptdiagonalen für k →∞ im Grenzwert verschwinden.Wir formulieren daher:

Algorithmus 2.8 (LR-Verfahren).Sei A eine reguläre m×m-Matrix; setze A := A1.Iteration: Für k = 1, 2, ... bilde die LR-Zerlegung von Ak (falls diese existiert),

Ak = LkRk,

und berechneAk+1 := RkLk.

Man stoppe die Iteration, falls die Komponenten von Ak+1 unterhalb der Diagonalenkleiner sind als eine vorgegebene Fehlerschranke.

Es stellt sich natürlich die Frage, ob das LR-Verfahren konvergiert. Wir wenden unsdaher nun der Konvergenzbetrachtung des LR-Verfahrens zu und formulieren folgendesResultat. Der Beweis findet sich im Anschluss.

Resultat 2.9 (Konvergenz des LR-Verfahrens).Für die Matrix A =: A1 ∈ Km×m seien folgende Voraussetzungen erfüllt:

1. A sei diagonalisierbar,

A = T diag(λ1, ..., λm)T−1,

wobei für T und für T−1 die LR-Zerlegungen (ohne Zeilenvertauschungen) exis-tieren mögen.

2. Die Eigenwerte von A lassen sich betragsmäßig ordnen gemäß

|λ1| > |λ2| > ... > |λm| > 0.


3. Das LR-Verfahren (ohne Zeilenvertauschungen)

Ak =: LkRk, Ak+1 := RkLk, k = 1, 2, ...,

sei durchführbar, d.h. in jedem k-ten Schritt existiere die LR-Zerlegung der Ma-trix Ak. Dann gilt

limk→∞

Ak = limk→∞

Rk =

λ1 ∗ . . . . . . ∗

λ2. . . .... . . . . . ...

. . . ∗0 λm

und

limk→∞

Lk = E.

Beweis: Wir führen nun den Beweis der Konvergenz des LR-Verfahrens unter denobigen Annahmen. Aus der Darstellung

A = TDT−1

mitD = diag(λ1, ..., λm)

folgt für die Potenzen Ak, k = 1, 2, ...

Ak = (TDT−1)k = TDkT−1.

Wenn für T und T−1 die LR-Zerlegungen

T = LTRT ,

T−1 = LT−1RT−1

existieren, so folgtAk = LTRTD

kLT−1RT−1 .

Mit A ist auch D regulär. In diesem Fall gilt

Ak = LTRT (DkLT−1D−k)DkRT−1 , k = 1, 2, ....

In der folgenden Aufgabe zeigen wir, dass in gewissen Fällen die Folge{DkLT−1D−k

}k∈N

gegen die Einheitsmatrix strebt.

Aufgabe 2.10.Es gelte

|λ1| > |λ2| > ... > |λm| > 0.

Dann konvergiert die Folge{DkLT−1D−k

}k=1,2,...

, D := diag(λ1, ..., λm),

geometrisch gegen die Einheitsmatrix:

DkLT−1D−k = E + Fk, k = 1, 2, ...,

limk→∞

Fk = 0.


Dieses Resultat verwenden wir nun, um das Verhalten der Matrixpotenzen Ak, k =1, 2, ..., zu untersuchen. Es folgt

Ak = LTRT (DkLT−1D−k)DkRT−1

= LTRT (E + Fk)DkRT−1

= LT (E +RTFkR−1T )RTD

kRT−1 .

Wir beachten, dass mitlimk→∞

Fk = 0

auchlimk→∞

RTFkR−1T = 0

gilt. Für genügend große k existiert somit die LR-Zerlegung der Matrix

E +RTFkR−1T =: LkRk.

Dabei giltlimk→∞

Lk = E = limk→∞

Rk,

wie man unmittelbar auslimk→∞

RTFkR−1T = 0

folgert.

Für hinreichend großes k folgt also für die Matrixpotenzen Ak die Darstellung

Ak = LT LkRkRTDkRT−1 .

In dieser Faktorisierung ist LT Lk eine untere Dreiecksmatrix mit normierter Diagonaleund RkRTD

kRT−1 eine obere Dreiecksmatrix. Also folgt aufgrund der Eindeutigkeitder LR-Zerlegung durch Vergleich mit Resultat 2.7:

Lk = LT Lk, Rk = RkRTDkRT−1 ,

wobei - wie oben gezeigt -limk→∞

Lk = limk→∞

Rk = E,

gilt. WegenLk = L−1

k−1Lk = L−1k−1L

−1T LT Lk = L−1

k−1Lk

und

Rk = RkR−1k−1 = RkRTD

kRT−1R−1T−1D

−(k−1)R−1T R−1

k−1

= RkRTDR−1T R−1

k−1

folgt somit

limk→∞

Lk = E

limk→∞

Rk = RTDR−1T


und damitlimk→∞

Ak = limk→∞

LkRk = RTDR−1T .

Dabei hat die Matrix RTDR−1T obere Dreiecksform, und in der Diagonalen stehen die

Diagonalelemente von D:

RTDR−1T =

λ1 ∗ . . . . . . ∗

λ2. . . .... . . . . . ...

. . . ∗0 λm

.

Insgesamt ist damit gezeigt, dass das LR-Verfahren in gewissen Fällen (nämlich unterobigen Annahmen an die Matrix A) iterativ sämtliche Eigenwerte von A liefert. Diesbeendet die Konvergenzuntersuchung. �

Bemerkung 2.11.Ist die Matrix A positiv definit, so kann unter Verwendung der Cholesky-Zerlegung einesymmetrische Variante des LR-Verfahrens durchgeführt werden:

A =: A1,

Ak =: LkLHk , Ak+1 := LHk Lk, k = 1, 2, ....

Es ist zu bemerken, dass die Matrizen Ak alle postiv definit sind; folglich existiert injedem Iterationsschritt die Cholesky-Zerlegung.

Die wesentliche Schwäche des LR-Verfahrens liegt darin, dass die LR-Zerlegung nichtfür jede reguläre Matrix notwendig existiert bzw. ihre Berechnung numerisch instabilist. Wie wir in Abschnitt 1.4 gesehen haben, existiert aber bei regulärer Matrix stetseine QR-Zerlegung, die z.B. nach Algorithmus 1.27 berechnet werden kann. Analogzum LR-Verfahren erhalten wir so das von Francis vorgeschlagene QR-Verfahren:

Algorithmus 2.12 (QR-Verfahren).Sei A =: A1 eine reguläre m×m-Matrix.Iteration: Für k = 1, 2, ... zerlege Ak:

Ak =: QkRk,

wo Qk unitär und Rk obere Dreiecksmatrix ist, und berechne

Ak+1 := RkQk.

Breche die Iteration ab, wenn die Komponenten von Ak+1 unterhalb der Diagonalendem Betrag nach kleiner sind als eine gegebene Fehlerschranke.

Zur Untersuchung des QR-Verfahrens gehen wir ähnlich wie beim LR-Verfahren vor.

Aufgabe 2.13.Man zeige, dass mit den in Algorithmus 2.12 gegebenen Matrizen Qi, Ri eine QR-Zerlegung der Matrixpotenzen Ak aufgebaut werden kann: Man beweise

Ak = QkRk, k = 1, 2, ...,


wobei

Qk := Q1Q2 · · ·Qk,

Rk := RkRk−1 · · ·R1

gesetzt wurde.

Es sei A diagonalisierbar mit dominantem Eigenwert

λ1 =: |λ1|eiϕ.

Es gilt wiederum

Ake1λk1→ ρ1u1,

‖Ake1‖|λk1|

→ ‖ρ1u1‖ für k →∞.

Daraus folgt

e−ikϕAke1‖Ake1‖

−→ ρ1u1

‖ρ1u1‖,

e−i(k−1)ϕ Ake1‖Ak−1e1‖

−→ λ1ρ1u1

‖ρ1u1‖für k →∞,

falls der kanonische Einheitsvektor e1 in Bezug auf den zu λ1 gehörenden Eigenvektoru1 eine nichtverschwindende Komponente ρ1 hat. Mit

Rk = (r(k)ij )m×m,

Qk =

q(k)1 q

(k)2 . . . q

(k)m

, k = 1, 2, ...

folgtAke1 = r

(1)11 · r

(2)11 · · · r

(k)11 q

(k)1 , ‖Ake1‖ = |r(1)

11 · · · r(k)11 |,

und falls wir

r(1)11 · · · r

(k)11 := |r(1)

11 · · · r(k)11 | · eiψk k = 1, 2, ...,

q(k)1 =: (q

(k)11 , ..., q

(k)m1)

t k = 1, 2, ...,

u1 =: (η1, ...ηm)t

setzen, ergibt sich für ν = 1, ...,m:

ei(ψk−kϕ)q(k)ν1

k→∞−→ ρ1ην‖ρ1u1‖

,

ei(ψk−1−(k−1)ϕ)r(k)11 q

(k)ν1

k→∞−→ λ1ρ1ην‖ρ1u1‖

.

Für ην 6= 0 erhalten wir schließlich unter Verwendung der Phasenfaktoren eiφk mit

φk := ϕ+ ψk−1 − ψk


die Konvergenzaussageeiφkr

(k)11 −→ λ1 für k →∞.

Die links oben stehenden Komponenten der Matrizen Rk konvergieren demnach nurbis auf einen Phasenfaktor gegen λ1. (Wählt man hierbei in jedem Schritt die QR-Zerlegung so, dass die Matrizen Rk reelle positive Diagonalelemente haben, so giltψk = 0, k = 1, 2, ..., und r(k)

11 → |λ1| für k →∞). Dieses für das QR-Verfahren typischeKonvergenzverhalten zeigt sich auch im folgenden Konvergenzsatz:

Satz 2.14 (Konvergenz des QR-Verfahrens).Für die Matrix A =: A1 ∈ Km×m seien folgende Voraussetzungen erfüllt:

1. A sei diagonalisierbarA = T diag(λ1, ..., λm)T−1,

wobei für T−1 die LR-Zerlegung vorausgesetzt wird:

T−1 = LT−1RT−1 .

2. Die Eigenwerteλj =: |λj|eiϕj , j = 1, ...,m,

lassen sich betragsmäßig ordnen gemäß

|λ1| > |λ2| > ... > |λm| > 0.

Wählt man in jedem Schritt des QR-Verfahrens

Ak =: QkRk, Ak+1 := RkQk, k = 1, 2, ...,

die obere Dreiecksmatrix Rk derart, dass in der Diagonalen reelle positive Ele-mente stehen, so gilt für k →∞

Qk −→ diag(eiϕ1 , eiϕ2 , ..., eiϕm),

(r(k)11 , r

(k)22 , ..., r

(k)mm) −→ (|λ1|, |λ2|, ..., |λm|),

und damita

(k)ij −→

{0 für i > j,λi für i = j.

(Hierbei haben wir Ak = (a(k)ij )m×m, Rk = (r

(k)ij )m×m gesetzt.)

Beweis: Wir führen den Beweis der Konvergenz des QR-Verfahrens unter obigenAnnahmen. In Aufgabe 2.13 haben wir gezeigt, dass die Matrixpotenzen Ak die QR-Zerlegungen

Ak = QkRk mitQk = Q1Q2 · · ·Qk undRk = RkRk−1 · · ·R1, k = 1, 2, ...,

besitzen, und diese Zerlegungen sind eindeutig bestimmt, falls für Rk positive Diagonal-elemente vorgeschrieben werden. Im folgenden leiten wir eine alternative Darstellungder Matrizen Qk und Rk ab.


Wir setzen

D = diag(λ1, λ2, ..., λm),

∆ = diag(eiϕ1 , eiϕ2 , ..., eiϕm).

WegenA = TDT−1

gilt auchAk = TDkT−1,

und unter Verwendung der QR-Zerlegung von T

T = QTRT

(RT besitze positive Diagonalelemente!) und der LR-Zerlegung von T−1,

T−1 = LT−1RT−1 ,

ergibt sichAk = QTRTD

kLT−1RT−1 .

FürL∗k := DkLT−1D−k

gilt wegen Aufgabe 2.10L∗k → E für k →∞,

da LT−1 eine untere Dreiecksmatrix mit normierter Diagonale ist und da die Eigenwertevon A nach Voraussetzung betragsmäßig getrennt liegen. Bildet man die QR-Zerlegungvon RTL

∗k gemäß

RTL∗k = Q∗kR

∗k,

wobei R∗k in der Diagonale wiederum positive Elemente besitze, so erhalten wir schließ-lich

Ak = QTRTL∗kD

kRT−1 = QTQ∗kR∗kD

kRT−1 .

Hiermit haben wir eine weitere Zerlegung der Matrix Ak in das Produkt einer unitärenMatrix QTQ

∗k und einer oberen Dreiecksmatrix R∗kDkRT−1 gefunden. Das Argument in

der komplexen Polardarstellung der Diagonalelemente von R∗kDkRT−1 ist allein durchDk und die Diagonalelemente ρ1, ρ2, ..., ρm von RT−1 bestimmt, da R∗k nur positiveDiagonalelemente besitzt. Wir setzen

ρj =: |ρj|eiψj , j = 1, ...,m,

und∆ = diag(eiψ1 , eiψ2 , ..., eiψm).

Dann hat∆−1∆−kR∗kD

kRT−1

in der Diagonalen nur positive Elemente. Da die Ri nach Voraussetzung nur positi-ve Diagonalelemente besitzen, hat auch Rk nur positive Elemente in der Diagonalen.Aufgrund der Eindeutigkeitsaussage für die QR-Zerlegung folgt

QTQ∗k∆

k∆ = Qk = Q1Q2 · · ·Qk


und∆−1∆−kR∗kD

kRT−1 = Rk = RkRk−1 · · ·R1.

Unter Verwendung dieser Identitäten werden wir die Konvergenzaussagen ableiten kön-nen. Zunächst gilt

Qk = Q−1k−1Qk

= (QTQ∗k−1∆

k−1∆)−1QTQ∗k∆

k∆

= ∆−1∆−(k−1)(Q∗k−1)−1Q∗k∆

k∆.

AusRTL

∗k = Q∗kR

∗k

undL∗k → E für k →∞

folgt wegen der Eindeutigkeit der QR-Zerlegung (da sowohl RT als auch R∗k in derDiagonale positive Elemente besitzen)

Q∗k → E, R∗k → RT für k →∞.

Wegen Q∗k → E können wir auf

∆−(k−1)(Q∗k−1)−1Q∗k∆

k → ∆ für k →∞

und weiter aufQk → ∆−1∆∆ = ∆ für k →∞

schließen.Die Konvergenzaussage für die oberen Dreiecksmatrizen Rk erhält man aus der Dar-stellung

Rk = RkR−1k−1

= ∆−1∆−kR∗kDkRT−1R−1

T−1D−(k−1)(R∗k−1)

−1∆k−1∆

= ∆−1∆−kR∗kD(R∗k−1)−1∆k−1∆

Wegen

R∗kD(R∗k−1)−1 → RTDR

−1T =

λ1 ∗ . . . ∗

. . . . . . .... . . ∗

0 λm

, k →∞,

konvergiert die Diagonale von ∆−kR∗kD(R∗k−1)−1∆k−1 gegen die Beträge der Eigenwer-

te, woraus wegen der Diagonalgestalt der Matrix ∆ die im Satz behauptete Konver-genzaussage für die Matrizen Rk folgt.Die Konvergenzaussage für die Matrizen Ak erhält man schließlich direkt aus der Dar-stellung

Ak = QkRk, k = 1, 2, ...,

unter Verwendung der schon bewiesenen Konvergenzaussagen für die Matrizen Qk undRk. Dies beendet den Beweis der Konvergenz des QR-Verfahrens. �

Wir schließen diesen Abschnitt mit einigen Bemerkungen.


(1) Die für die Konvergenzaussagen 2.9 und 2.14 wesentliche Forderung an die Ma-trix A ist die Eigenschaft, dass A diagonalisierbar ist. Die anderen Forderungen,insbesondere die Forderung

|λ1| > |λ2| > ... > |λm|,

können abgeschwächt werden, ohne dass die Konvergenzaussage wesentlich ein-geschränkt wird. (Wir verweisen auf Wilkinson: The Algebraic Eigenvalue Pro-blem, Oxford, Clarendon Press, 1965). Es ist allerdings darauf hinzuweisen, dassdas LR-Verfahren selbst bei theoretisch gesicherter Konvergenz zusammenbre-chen kann, da die Berechnung der LR-Zerlegung in einem Iterationsschritt aufnumerische Instabilität führen kann.

(2) Vom Standpunkt der Praxis aus kann man sich bei Hermiteschen Matrizen Aimmer auf den Spezialfall reeller Matrizen beschränken. Denn, falls A nicht reellist, so kann man komplexe Arithmetik dadurch vermeiden, dass man A zerlegtin Real- und Imaginärteil,

A = A1 + iA2

und anstelle von A die Matrix

A =

[A1 −A2

A2 A1

]betrachtet. Es ist einfach einzusehen, dass ein Eigenwert λ von A ein zweifacherEigenwert von A ist. (Verifizieren Sie diese Aussage!)

(3) Der unverhältnismäßig hohe numerische Aufwand von O(m3) Rechenoperationenin jedem Schritt der beiden Verfahren kann dadurch vermindert werden, dassman die vorliegende Matrix zuerst mit der in folgenden Abschnitt 2.5 beschrie-benen Methoden auf einfachere Gestalt (Tridiagonalform bzw. Hessenberg-Form)bringt. Wesentlich ist, dass diese spezielle Form bei LR- bzw. QR-Verfahren in-variant bleibt, so dass der Aufwand pro Iterationsschritt auf O(m) bzw. O(m2)Punktoperationen reduziert wird.

(4) Auch bei Anwendung des LR- bzw. QR-Verfahrens auf eine Matrix A(=: A1) mitspezieller Bandgestalt haben die in den Verfahren berechneten Matrizen Ak, k =1, 2, ..., dieselbe Bandgestalt, so dass auch hier der Aufwand pro Iterationsschrittvermindert wird. Dies zeigt die folgende Aufgabe:

Aufgabe 2.15.Man zeige

1. Ist A1 =: (aij)m×m eine Bandmatrix mit Bandbreite d, d.h. gilt

aij = 0 für |i− j| ≥ d,

so sind beim LR-Verfahren die Ak, k = 1, 2, ..., ebenfalls Bandmatrizender Bandbreite d. Insbesondere bleibt etwa Tridiagonalgestalt (Fall d = 2)erhalten (Tridiagonalgestalt siehe Abschnitt 2.5).

2. Ist A1 eine reguläre Hermitesche Bandmatrix mit Bandbreite d, so sind esbeim QR-Verfahren die Ak, k = 1, 2, ..., ebenfalls.


3. Ist A1 =: (aij)m×m eine reguläre Matrix mit unterem Band der Breite d,d.h., gilt

aij = 0 für i− j ≥ d,

so sind es beim LR-Verfahren die Ak, k = 1, 2, ..., ebenfalls. Insbesonderebleibt die obere Hessenberg-Form (Fall d = 2) erhalten ( obere Hessenberg-Form siehe Abschnitt 2.5).

4. Ist A1 eine reguläre Matrix mit unterem Band der Breite d, so sind es beimQR-Verfahren die Ak, k = 1, 2, ..., ebenfalls.

Im Folgenden behandeln wir abschließend shift-Methoden in Verbindung mit LR- undQR-Verfahren.

In den Konvergenzsätzen 2.9 und 2.14 hatten wir gesehen, dass in den Matrizen Akdie Elemente unterhalb der Diagonalen gegen Null und die Diagonalelemente gegendie Eigenwerte der Ausgangsmatrix streben. Man darf also erwarten, dass das Elementa

(k)mm eine von Schritt zu Schritt bessere Näherung für den Eigenwert λm wird. Shift-

Methoden für LR- und QR-Verfahren werden gemäss folgendem Schema gebildet:

Seien σk, k = 1, 2, ..., Näherungen für λm. Man bilde für k = 1, 2, ... (mit A =: A1)

Ak − σkE =: LkRk, Ak+1 := RkLk + σkE (LR-Verfahren mit shift)

bzw.

Ak − σkE =: QkRk, Ak+1 := RkQk + σkE (QR-Verfahren mit shift).

Folgende Strategien haben sich in der Praxis bewährt (wir setzen Ak = (a(k)ij )m×m):

Strategie a: σk = a(k)mm.

Strategie b: σk wird gewählt als derjenige Eigenwert der 2× 2-Matrix[a

(k)m−1,m−1 a

(k)m−1,m

a(k)m,m−1 a

(k)m,m

]

der am nächsten bei a(k)mm liegt.

Man kann zeigen, dass die Strategie b, falls sie auf eine (nicht-zerlegbare) HermitescheTridiagonalmatrix angewendet wird, mindestens quadratische Konvergenz für

a(k)m,m−1 −→ 0,

a(k)m,m −→ λm für k →∞

liefert; in vielen Fällen kann sogar kubische Konvergenz gesichert werden.

Zusammenfassung:

In diesem Abschnitt wurden Ihnen zwei vom Typ ähnliche Iterationsverfahren zur si-multanen Berechnung aller Eigenwerte einer Matrix beschrieben. Für beide Verfahrensind unter relativ allgemeinen Voraussetzungen globale Konvergenzaussagen bekannt.In der Praxis werden diese Verfahren üblicherweise nur unter Verwendung von shift-Techniken benützt, um lokal eine höhere Konvergenzordnung zu erhalten.


2.5 Die Reduktionsmethode von Householder aufHessenberg- bzw. Tridiagonalform (Ergänzung)

Im vorangehenden Abschnitt hatten wir Methoden kennengelernt, die es gestatten, un-ter gewissen einschränkenen Bedingungen die Eigenwerte einer Matrix A in geschickterWeise zu berechnen. Wir wenden uns nun dem Problem zu, wie man für eine gegebe-ne Matrix A die sogenannte Hessenberg-Form bzw. für eine Hermitesche Matrix dieHermitesche Tridiagonalgestalt erreichen kann. Damit lässt sich der Aufwand der LR-bzw., QR-Verfahrens erheblich reduzieren.

Eine Matrix A hat obere Hessenberg-Form, falls sie von folgender Bauart ist:

A =

∗ . . . . . . . . . ∗∗ . . . ...

. . . . . . .... . . . . . ∗

0 ∗ ∗

.

Eine Matrix A hat Tridiagonalgestalt, falls sie von folgender Bauart ist:

A =

∗ ∗ 0

∗ . . . . . .. . . . . . . . .

. . . . . . ∗0 ∗ ∗

.

Bei dem oben formulierten Problem handelt es sich also um Folgendes. Gegeben seieine Matrix A ∈ Km×m (K = R oder K = C). Da Ähnlichkeitstransformationen

A 7−→ T−1AT, T regulär,

und insbesondere unitäre Transformationen

A 7−→ UHAU, U unitär, d.h. UH = U−1,

die Eigenwerte von A invariant lassen, kann man versuchen, möglichst einfache Trans-formationsmatrizen zu finden, dieA auf Hermitesche Tridiagonalform oder auf Hessenberg-Form bringen. Es wird sich zeigen, dass man mit einer endlichen Kette solcher Trans-formationen dieses Problem lösen kann:

Sei

A(0) := A,

A(1) := UH1 A

(0)U1,...

A(k) := UHk A

(k−1)Uk;

dann hat bei geeigneter Wahl von U1, ..., Uk die EndmatrixA(k) die gewünschte Hessenberg-oder Hermitesche Tridiagonalform. Die Länge k der Kette hängt von der Zeilenzahl vonA und der Bauart der verwendeten Transformationsmatrizen Uν , ν = 1, ..., k, ab.


Aufgabe 2.16.Es sei

A =

2 3 13 4 51 5 6

.1. Man konstruiere eine Householder-Matrix

Hw := E − 2wwH , wHw = 1,

welche den Vektor (3, 1)t in die Richtung des ersten Einheitsvektors im R2 spie-gelt:

Hw :

[31

]7−→ α

[10

].

2. Man bilde

U :=

1 0 000 Hw

und zeige, dass

A(1) := UHAU

Hermitesche Tridiagonalform hat.

Bei dieser Aufgabe haben wir schon das Prinzip der Reduktionsmethode von House-holder kennengelernt. Wir betrachten nun eine beliebige m-reihige Matrix A, die wirauf obere Hessenberg-Form transformieren wollen. Es soll gezeigt werden, dass dies mitm − 2 unitären Transformationen, die aus Householder-Spiegelungen aufgebaut sind,zu erreichen ist.

Wir gehen davon aus, dass durch i − 1 Schritte (i ≥ 2) von „links oben her“ schonein Stück obere Hessenberg-Form erzeugt ist, d.h. die Ausgangsmatrix A = A(0) seiunitär ähnlich einer Matrix A(i−1) des Typs:

A(i−1) = UHi−1 · · · UH

1 A(0)U1 · · · Ui−1 =

...

Bi... Dm−i...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−i

......

;

Bi : i× i-Matrix in oberer Hessenbergform;

Cm−i : (m− i)× (m− i)-Matrix;

bi ∈ Km−i (K = R oder K = C);Dm−i : i× (m− i)-Matrix.


Nach Abschnitt 1.4, wo wir die QR-Zerlegung behandelt haben, existiert eine House-holdertransformation

Hi := E − 2wiwHi , wHi wi = 1,

auf dem Raum Cm−i, die den Vektor bi in ein skalares Vielfaches des kanonischenEinheitsvektors e1 ∈ Cm−i spiegelt:

Hi : bi 7−→ αiei ∈ Cm−i.

Wie man bei gegebenem Vektor bi den entsprechenden Vektor wi numerisch am güns-tigsten bestimmt, haben wir bei der Behandlung der QR-Zerlegung gezeigt. Hier gehtes darum, die Transformationsmatrix Ui zu definieren. Wir setzen (entsprechend derEinteilung der Matrix A(i−1)):

Ui :=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

.

Da Hi Hermitesch und unitär ist,

Hi = HHi = H−1

i ,

gilt dasselbe auch für UiUi = UH

i = U−1i .

Wir betrachten jetzt die unitäre Ähnlichkeitstransformation

A(i−1) 7−→ UHi A

(i−1)Ui = UiA(i−1)Ui =: A(i).


Aufgrund der Blockstruktur der Matrizen A(i−1) und Ui ergibt sich

A(i) =

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

·

...

Bi... Dm−i...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−i

......

·

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

·

...

Bi... Dm−iHi...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−iHi

......

=

...

Bi... Dm−iHi...

. . . . . . . . . . . . . . . . . .... αi

...

O ... 0... HiCm−iHi

......

...... 0

...

=:

...

Bi+1... Dm−i−1...

. . . . . . . . . . . . . . . . . ....

...

O ... bi+1... Cm−i−1

......

,

wobei die (i+ 1)× (i+ 1)-Matrix Bi+1 obere Hessenberg-Form besitzt.

Wir erkennen somit, dass jedem-reihige Matrix A durchm−2 Ähnlichkeitstransforma-tionen mittels unitärer Transformationsmatrizen auf obere Hessenberg-Form gebracht


werden kann:

A 7−→ Um−2Um−1 · · · U1︸︷︷︸=UH

AU1U2 · · · Um−2︸︷︷︸=:U

= A(m−2) =: A,

UHU = E, A =

∗ . . . . . . . . . ∗∗ . . . ...

. . . . . . .... . . . . . ∗

0 ∗ ∗

.

Ist A Hermitesch, so liefert der Transformationsprozess wegen

AH = (UHAU)H = UHAHU = UHAU = A

sogar in A eine Hermitesche Tridiagonalmatrix.

Resultat 2.17 (Reduktion auf obere Hessenberg-Form).Eine beliebige m-reihige Matrix A lässt sich mit Hilfe von m−2 Householder-Transfor-mationen auf eine obere Hessenberg-Form bringen. Ist A Hermitesch, so liefert dieserTransformationsprozess sogar eine Hermitesche Tridiagonalmatrix.

Algorithmus 2.18 (Reduktionsverfahren nach Householder).Start: Es sei

A(0) := (a(0)νµ )ν,µ=1,...,m := A = (aνµ)ν,µ=1,...,m.

Iteration: Für i = 1, ...,m− 2 bilde man

A(i) = (a(i)νµ)ν,µ=1,...,m gemäß

A(i) := UiA(i−1)Ui,

wobei

Ui :=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

Die (m− 1)-reihige Matrix Hi ist eine Householder-Spiegelung, die wir mit dem Algo-rithmus 1.27 durch die Forderung erhalten, dass Hi die i-te Spalte von A(i−1) unterhalbder Diagonalen auf ein skalares Vielfaches des ersten Einheitsvektors von Cm−i spiegelt.

Bemerkung 2.19.Es ist naheliegend zu fragen, ob mit einer endlichen Kette solcher Ähnlichkeitstrans-formationen

A(0) := A −→ A(1) := T−11 A(0)T1 −→ A(2) := T−1

2 A(1)T2 ...


die volle Jordansche Normalform, d.h. insbesondere bei Hermiteschen Matrizen dieDiagonalform erreichbar ist. Wir machen uns klar, dass dies, wenn die Lösung des Ei-genwertproblems noch nicht bekannt ist, wovon wir ja ausgehen wollen, nicht möglichist. Der Grund ist der folgende: Selbst wenn wir von einer Matrix A mit ganzzahligenElementen aνµ, ν, µ = 1, ...,m ausgehen, können die Eigenwerte als Nullstellen einesPolynom m-ten Grades irrational sein und auch nicht durch einen endlichen arith-metischen Ausdruck, der nur die Grundrechenarten und die Quadratwurzelrechnungverwendet, berechnet werden. (In der Sprache der Algebra ausgedrückt: Die Wurzelneines Polynoms m-ten Grades, m > 2, liegen sogar bei ganzzahligen Koeffizienten i. A.nicht in einem Erweiterungskörper von Q, der durch Adjunktion von Quadratwurzelnentsteht.)Es ist also prinzipiell nicht möglich, mit Reduktionsmethoden des betrachtetenTyps die Jordan-Normalform zu erreichen. Deswegen war es auch sinnvoll, dass wiruns mit der Hessenberg- bzw. der Hermiteschen Tridiagonalform begnügten.

Zusammenfassung:

In diesem Abschnitt wurde Ihnen eine Methode vorgestellt, wie beliebige Matrizenauf obere Hessenberg-Form und insbesondere Hermitesche Matrizen auf HermitescheTridiagonalform transformiert werden können. Damit erhalten die Verfahren, die Sieim vorangehenden Abschnitt kennengelernt haben, erst ihre wahre Bedeutung, da Sienunmehr Algorithmen für die Berechnung der Eigenwerte beliebiger Matrizen in derHand haben.

Kapitel 3

Lineare Optimierung

Definition 3.1 (lineares Optimierungsproblem).Gesucht ist ein Extremum - das kann ein Maximum oder ein Minimum sein - derZielfunktion

z(x) =n∑k=1

ckxk, (c1, . . . , cn ∈ R sind gegeben)

wobei die m Nebenbedingungen∑n

k=1 aikxk ∼ bi, (i = 1, ...,m) erfüllt sein müssen.Dabei steht ∼ für eines der Zeichen =, ≤ oder ≥.

Definition 3.2 (Standardmodell).Ein Standardmodell ist ein lineares Optimierungsproblem, bei dem das Maximum derZielfunktion

z(x) =n∑k=1

ckxk

gesucht wird, wobei die m Nebenbedingungen∑n

k=1 aikxk ≤ bi, (i = 1, ...,m) sowiexk ≥ 0, (k = 1, ..., n) erfüllt sein müssen.

Satz 3.3.Jedes lineare Optimierungsproblem lässt sich in ein Standardmodell überführen, indemman die folgenden Umforungen durchführt:

1. Eine Nebenbedingung in Gleichungsform wird durch 2 Ungleichungen mit ≤ und≥ ersetzt.

2. Eine ≥-Ungleichung wird mit (−1) multipliziert, damit sich das Ungleichheitszei-chen umdreht.

3. Ein Minimierungsproblem wird zu einem Maximierungsproblem, indem man dieZielfunktion mit (−1) multipliziert.

4. Variablen xk, die sowohl negativ also auch positiv sein können, werden als Diffe-renz zweier neuer nicht-negativer Variablen geschrieben. Soll etwas xk ≥ 0 gelten,so schreibt man xk = yk − yk mit yk, yk ≥ 0.

Definition 3.4 (Normalform).Ein Standardmodell liegt in Normalform vor, falls bi ≥ 0 gitl für i = 1, ...,m.

53

KAPITEL 3. LINEARE OPTIMIERUNG 54

Definition 3.5 (Zulässiger Bereich).Die Teilmenge des Rn, in dem alle Nebenbedingungen eines linearen Optimierungspro-blems erfüllt sind, heißt zulässiger Bereich.

In der Regel ist der zulässige Bereich ein n-dimensionales Vieleck (Polyeder).

Satz 3.6 (Hauptsatz der linearen Optimierung).Falls das lineare Optimierungsproblem eine optimale Lösung besitzt, dann gibt es ins-besondere eine optimale Lösung in einem Eckpunkt des zulässigen Bereiches.

Folgerung 3.7.Das bedeutet, dass es genügt nur die zulässigen Ecken als Kandidaten für die optimaleLösung des Optimierungsproblems zu betrachten.

Definition 3.8 (Schlupfvariable).Durch die Einführung der Schlupfvariablen y1, . . . , ym werden die Ungleichungen

n∑k=1

aikxk ≤ bi (i = 1, . . . ,m)

zu Gleichungenn∑k=1

aikxk + yi = bi mit Nebenbedingung yi ≥ 0 (i = 1, . . . ,m).

Die Variablen x1, . . . , xn heißen Struktur- oder Problemvariablen; die Variablen y1, . . . , ymheißen Schlupfvariablen.

Durch das Einführen von Schlupfvariablen können die Nebenbedingungen eines Linea-ren Optimierungsproblems

∑nk=1 aikxk ≤ bi (i = 1, ...,m) als lineares Gleichungssystem

geschrieben werden:

a11x1 + a21x2 + . . . + a1nxn + y1 = b1a21x1 + a22x2 + . . . + a2nxn + y2 = b2...

......

......

...am1x1 + am2x2 + . . . + amnxn + ym = bm

.

In Matrixschreibweise erhält man

a11 a21 . . . a1n 1 0 . . . 0a21 a22 . . . a2n 0 1 . . . 0...

......

...... . . . ...

am1 am2 . . . amn 0 0 . . . 1

x1...xny1...ym

=

b1b2...bm

(3.1)

oder kürzerAx+ y = b, bzw. (A|E)

(xy

)= b.

Dieses besitzt n + m Variablen und m Gleichungen. Daher ist Rg(A|E) = m, da dieletzten m Spalten linear unabhängig sind, und der Lösungsraum ist n dimensional.


Der zulässige Bereich eines Standardmodells in Normalform (vgl. Definition 3.2 undDefinition 3.4) besteht aus den Lösungen des Gleichungssystems für die die Bedingun-gen xk ≥ 0, k = 1, ..., n und yi ≥ 0, i = 1, ...,m erfüllt sind.

Eine Basislösung erhält man, indem man jeweils n der Variablen x1, ..., xn, y1, ..., ym auf

Null setzt und das Gleichungssystem (A|E)

(xy

)= b löst, sofern die entsprechenden

m Spalten von (A|E) linear unabhängig sind.

Definition 3.9 (Basislösung, Basisvariable).Eine Basislösung erhält man, indem man jeweils n der Variablen x1, ..., xn, y1, ..., ym auf

Null setzt und das Gleichungssystem (A|E)

(xy

)= b löst, wobei die entsprechenden

m Spalten von (A|E) linear unabhängig sein müssen. Diejenigen Variablen, die dabeinicht Null gesetzt wurden, heißen Basisvariablen, weil sie in die jeweilige Basislösungeingehen. Die Variablen, die Null gesetzt wurden, heißen Nicht-Basisvariablen.

Algorithmus 3.10.Naiv-rechnerische Herangehensweise an die Lösung eines Standardmodells.

1. Stelle das Gleichungssytem (A|E)

(xy

)= b auf.

2. Setze jeweils n Variablen gleich Null und löse das Gleichungssystem, sofern dieentsprechenden verbleibenden m Spalten linear unabhängig sind. Jede dieser Lö-sungen ist eine Basislösung.

3. Überprüfe die Basislösungen auf Zulässigkeit. Das ist der Fall, wenn xk ≥ 0,k = 1, ..., n und yi ≥ 0, i = 1, ...,m.

4. Setze die zulässigen Basislösungen in die Zielfunktion ein.

5. Bestimme die Basislösung, an der die Zielfunktion maximal wird.

Algorithmus 3.10 bedeutet einen sehr hohen Rechenaufwand, wenn die Anzahl n der

Strukturvariablen oder die Anzahl der Nebenbedingungen groß wird, weil(n+mn

)Basislösungen berechnet und auf Zulässigkeit überprüft werden müssen. Der Simplex-Algorithmus umgeht dieses Problem, indem er von vornherein nur zulässige Basislösun-gen berechnet und hierbei zielstrebig vorgeht, indem er den folgenden Satz beachtet:

Satz 3.11.Ist eine zulässige Basislösung eines linearen Optimierungsproblems nicht optimal, sogibt es eine benachbarte Basislösung, in der die Zielfunktion einen besseren Wert an-nimmt.

Der Übergang zu einer benachbarten Basislösung geschieht im Simplex-Algorithmusdadurch, dass jeweils eine Basisvariable gegen eine Nicht-Basisvariable ausgetauschtwird. Dieser Austausch von Variablen geschieht durch Operationen, die schon aus demGauß-Verfahren bekannt sind.


Definition 3.12.Das Ausgangstableau für den Simplex-Algorithmus erhält man aus Gleichung (3.1),indem man als letzte Zeile die Zielfunktionszeile anfügt, wobei die Koeffizienten ckjeweils mit (−1) multipliziert werden. Da die Zielfunktion nicht von den Schlupfvaria-blen y1, ..., ym abhängt, steht in den entsprechenden Spalten jeweils eine 0. In der erstenSpalte wird vermerkt, welche die aktuellen Basisvariablen sind.

aktuelle x1 x2 . . . xn y1 y2 . . . ym rechte SeiteBasisvar.

y1 a11 a12 . . . a1n 1 0 . . . 0 b1y2 a21 a22 . . . a2n 0 1 . . . 0 b2...

......

......

... . . . ......

ym am1 am2 . . . amn 0 0 . . . 1 bm−c1︸︷︷︸=:z1

−c2︸︷︷︸=:z2

. . . −cn︸︷︷︸=:zn

0︸︷︷︸=:zn+1

0︸︷︷︸=:zn+2

. . . 0︸︷︷︸=:zn+m

0

Im Ausgangstableau sind die Basisvariablen durch die Schlupfvariablen y1, ..., ym ge-geben, daher sind alle Strukturvariablen Null und dies entspricht der Basislösung imKoordinatenursprung. Für diese Basislösung gilt y1 = b1, ..., ym = bm, d.h. diese Basis-lösung ist zulässig, falls b1, ..., bm ≥ 0.

Algorithmus 3.13 (Der Simplex-Algorithmus).Voraussetzung:xk ≥ 0 und bi ≥ 0 für alle k = 1, . . . , n und i = 1, . . . ,m, d.h. das Optimierungsproblemliegt als Standardmodell in Normalform vor.

1. Stelle das Ausgangstableau gemäß Def. 3.12 auf.

2. Auswahl der Pivotspalte l: Wähle als Pivotspalte diejenige Spalte, die in der Ziel-funktionszeile den betragsmäßig größten negativen Wert zl < 0 aufweist.

3. Auswahl der Pivotzeile p:

(i) Berechne für jede Zeile j den Wert bjajl

, sofern ajl > 0.

(ii) Falls ajl ≤ 0 für alle j = 1, . . . ,m, so existiert keine optimale Lösung, daxl beliebig groß gewählt werden kann und hierdurch die Zielfunktion beliebiggroß wird.

(iii) Falls ajl > 0 für mindestens eine Zeile j, so wähle unter diesen Zeilendiejenige aus (→ Zeile p), für die der Quotient bj

ajlminimal wird.

4. Austausch der Variablen:

(i) Tausche diejenige Basisvariable, in deren Spalte der p-te Einheitsvektor ep ∈Rm+1 steht, gegen die Nichtbasisvariable in der l-ten Spalte aus.

(ii) Addiere zu jeder Zeile j 6= p das − ajlapl

-fache der p-ten Zeile.

(iii) Addiere zur Zielfunktionszeile das − zlapl︸︷︷︸>0

−fache der p-ten Zeile.

(iv) Dividiere die p-te Zeile durch apl.


Bemerkungen:

• Für die neue ”rechte Seite” bneu gilt die Formel bneuj = baltj −ajlapl· baltp . So-

mit wird durch 3.(iii) gewährleistet, dass bneuj ≥ 0 gilt, denn die Wahl desminimalen Quotienten impliziert:

baltj −ajlapl· baltp = ajl︸︷︷︸

>0

·( baltjajl−baltpapl︸︷︷︸

≥0

)≥ 0

• Durch die Aktionen 4.(ii)-4.(iv) wird in der l-ten Spalte mittels Zeilenum-formung der Einheitsvektor ep ∈ Rm+1 erzeugt. Man zeigt induktiv, dass derWert rechts unten im Tableau stets der Wert der Zielfunktion an der ak-tuellen Basislösung ist. Durch 4.(iii) wird die Zielfunktion in jedem Schrittvergrößert (es sei denn, das Optimalitätskriterium greift).

5. Überprüfung des Abbruchkriteriums:Falls alle Werte der letzten Zeile nichtnegativ sind, lies den optimalen Wert derZielfunktion rechts unten im Tableau ab. Eine optimale (Basis-)Lösung erhältman, indem man die aktuellen Nicht-Basisvariablen auf 0 und die aktuellen Ba-sisvariablen auf die aktuellen b1, . . . , bm setzt (in der durch die aktuellen Basiss-palten vorgegebenen Reihenfolge).Der Algorithmus ist beendet.Falls es in der letzten Zeile negative Werte gibt, so ist das Optimum noch nicht er-reicht. Ersetze darum das alte Tableau durch das neue und durchlaufe den obigenAlgorithmus ab 2.

Wenn das Standardmodell nicht in Normalform vorliegt, ist die Basislösung 0 nichtzulässig. In diesem Fall muss vor dem Simplex-Algorithmus eine Vorphase durchgeführtwerden, in dem eine zulässige Basislösung gesucht wird.

Beispiel 3.14.Eine Fabrik kann zwei Typen A und B eines Produkts unter folgenden Bedingungenherstellen:

Produkt Typ A Typ B maximal möglichStück pro Tag x1 x2 100 StückArbeitszeit pro Stück 4 1 160 StundenKosten pro Stück 20 10 1100 EURGewinn pro Stück 120 40

Wie müssen x1 und x2 gewählt werden, damit der Gewinn maximal wird? Dabei mussoffenbar der lineare Ausdruck

z(x1, x2) := 120x1 + 40x2

zu einem Maximum gemacht werden unter den linearen Nebenbedingungen

x1 + x2 ≤ 1004x1 + x2 ≤ 160 , x1 ≥ 0, x2 ≥ 0.

20x1 + 10x2 ≤ 1100


Lösung des Beispiels:

y1 1 1 1 0 0 100y2 4 1 0 1 0 160y3 20 10 0 0 1 1100−120 −40 0 0 0 0

120 > 40 ⇒ erste Spalte wird Pivotspalte

b1a11

= 100,b2a21

= 40,b3a31

= 55 : 40 minimal

⇒ a21 = 4 Pivotelement

y1 0 3/4 1 −1/4 0 60x1 1 1/4 0 1/4 0 40y3 0 5 0 −5 1 300

0 −10 0 30 0 4800

zweite Spalte wird Pivotspalte (einziger negativer Eintrag unter den aktuellen cj)

b1a12

= 80,b2a22

= 160,b3a32

= 60 : 60 minimal

⇒ a32 = 5 Pivotelement

y1 0 0 1 1/2 −3/20 15x1 1 0 0 1/2 −1/20 25x2 0 1 0 −1 1/5 60

0 0 0 20 2 5400

alle aktuellen cj ≥ 0 ⇒ Optimalität erreicht

Optimum: x1 = 25, x2 = 60Gewinn: 5400 Euro

Kapitel 4

Fehleranalyse

4.1 Einleitung

In diesem Paragraphen beschäftigen wir uns mit Fehleruntersuchungen. An verschiede-nen Stellen dieses Kurses hatten wir schon auf diesen Teil verwiesen und eine detaillierteAnalyse der möglichen Fehlerquellen und deren Auswirkungen auf numerische Resul-tate angekündigt. Um Motivation für unser weiteres Vorgehen zu erhalten, betrachtenwir zunächst ein bereits früher untersuchtes Beispiel.

In Kapitel 1 hatten wir das folgende elektrische Netzwerk untersucht.

A

D

B

C

I

I

I

I

I

I

U

R

R

RR

R

R

6

3

4 5

1

21

2

3

54

6

Abbildung 4.1: Schaltbild eines elektrischen Netzwerkes

Die in diesem Netzwerk fließenden Ströme Iν , ν = 1, ..., 6, lassen sich aus dem linearen

59

KAPITEL 4. FEHLERANALYSE 60

Gleichungssystem1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0

I1I2I3I4I5I6

=

000U00

berechnen.Vom Standpunkt der Anwendungen her gesehen stellt sich folgendes Problem: Wennman eine elektromotorische Kraft U misst und dann die Ströme Iν , ν = 1, ..., 6, ausdiesem System berechnet, ist dann garantiert, dass I1, ..., I6 tatsächlich in der berech-neten Stromstärke in dem Netzwerk fließen? Muss man nicht vielmehr damit rechnen,dass die berechneten Stromstärken nur näherungsweise mit den tatsächlich fließendenübereinstimmen? Diese Fragen sind in der Tat wohlbegründet, wie wir uns klar machenwollen.

• Fehler in den physikalischen Gesetzen:Mögliche Abweichungen können daher stammen, dass das verwendete physikali-sche Gesetz den Sachverhalt nicht genau wiedergibt. Denkbar ist, dass das Ohm-sche Gesetz U = R · I für die verwendeten Widerstände R1, ..., R6 nicht exakterfüllt ist. (Infolge einer geringen Temperaturabhängigkeit besitzen die Wider-stände z.B. keine genau lineare Charakteristik.) Einflüsse dieser Art auf die ge-suchten Ströme haben mit der numerischen Lösung des Problems offensichtlichnichts zu tun. Hier hat der Anwender zu entscheiden, ob das physikalische Modell,das er benützt, den wahren Sachverhalt genau genug beschreibt.

• Messungenauigkeit:Weitere Fehlerquellen resultieren aus Messungenauigkeiten. Die WiderständeR1, ..., R6 und die elektromotorische Kraft U lassen sich nur mit einer begrenz-ten Messgenauigkeit bestimmen. Eine Abschätzung (oder gar eine Reduzierung)dieser Messtoleranzen liegt ebenfalls nicht im Arbeitsbereich des Numerikers. Inder Numerik kann man aber damit zusammenhängende Fragen klären, wieweitgegebene Toleranzen bei U oder den Widerständen Rν , ν = 1, ..., 6, die StrömeIν beeinflussen können. Zu untersuchen ist also die Abhängigkeit der Resultatevon Eingangsdaten (Fehlerfortpflanzung).

• Rundungsfehler:Ein eigentlich numerisches Problem stellt sich bei der Auflösung dieses linearenGleichungssystems, wenn man mit Dezimalzahlen einer festen Stellenlänge arbei-tet. Dann ist stets damit zu rechnen, dass Zwischenresultate gerundet werdenmüssen. Es gilt dann den Einfluss von Rundungsfehlern abzuschätzen und, fallsdiese sich unangenehm akkumulierern sollten, eventuell eine günstigere Lösungs-methode einzusetzen.

• Schließlich sollte man bei starken Abweichungen der berechneten von den gemes-senen Stromstärken immer auch an die Möglichkeit von Rechenfehlern denken.


In folgenden Abschnitt 4.2 untersuchen wir speziell die Fehlerfortpflanzung bei linearenGleichungssystemen. Neben Fehlern der Komponenten der rechten Seite lassen wir auchStörungen der Matrix zu. Ist N(·) eine geeignete Matrixnorm (vgl. Abschnitt 4.2), sozeigt sich, dass beide Fehlertypen um den Faktor

condN(A) = N(A)N(A−1)

verstärkt in das Resultat eingehen können. Dieser Faktor heisst Konditionszahl vonA zur Matrixnorm N . In diesem Zusammenhang interessieren uns diejenigen Metho-den zur Lösung linearer Gleichungssysteme, welche die Konditionszahl verkleinern oderwenigstens nicht vergrößern. Dabei erweist sich das QR-Verfahren bzgl. der Spektral-kondition als numerisch günstig.

4.2 Fehlerfortpflanzung bei linearen Gleichungssyste-men

Im Folgenden befassen wir uns speziell mit der Fehlerfortpflanzung bei linearen Glei-chungssystemen. Gegeben sei also ein lineares Gleichungssystem

Ax = b,

wobeiA ∈ Km×m (K = R oder K = C), A regulär, b ∈ Km.

Auf Rm (Cm) sei ‖ · ‖ eine Norm gegeben und N(·) sei eine mit ‖ · ‖ verträglicheMatrixnorm, d.h.

‖Cy‖ ≤ N(C)‖y‖ ∀C ∈ Km×m und ∀y ∈ Km.

Meist notiert man N(C) =: ‖C‖.

Nun sei b + 4b eine Störung der rechte Seite des linearen Gleichungssystems undx+4x die Lösung von A(x+4x) = b+4b. Also gilt

A(4x) = 4b bzw. 4x = A−1(4b).

Daraus ergibt sich die folgende Abschätzung für den absoluten Fehler

‖4x‖ ≤ N(A−1) · ‖4b‖,

da N und ‖ · ‖ ein verträgliches Paar von Vektor- und Matrixnorm bilden.

Um den relativen Fehler abschätzen zu können, beachten wir

‖b‖ = ‖Ax‖ ≤ N(A) · ‖x‖,

also, falls b 6= 0 und damit auch x 6= 0 gilt,

1

‖x‖≤ N(A)

‖b‖.


Insgesamt folgt‖4x‖‖x‖

≤ N(A)N(A−1)‖4b‖‖b‖

.

Als Verstärkungsfaktor beim relativen Fehler tritt also gerade die Größe

condN(A) := N(A)N(A)−1

auf.

Bezeichnung 4.1 (Konditionszahl einer Matrix).Für eine reguläre Matrix A und eine Matrixnorm N bzeichnet man

condN(A) := N(A)N(A−1)

als die zur Matrixnorm N gehörende Konditionszahl von A.

Das oben gewonnene Resultat über die Fortpflanzung von Datenfehlern halten wir fest.

Resultat 4.2 (Fehlerfortpflanzung bei Störung von b). Bezeichnet 4b den Vektor derabsoluten Datenfehler und 4x den Vektor der absoluten Fehler des Resultatvektors, sogelten für ein lineares Gleichungssystem

Ax = b, A ∈ Km×m regulär, b ∈ Km, b 6= 0,

die Abschätzungen

‖4x‖ ≤ N(A−1)‖4b‖,‖4x‖‖x‖

≤ condN(A) · ‖4b‖‖b‖

.

Bemerkung 4.3.Die Konditionszahl condN(A) einer regulären Matrix A spielt eine wichtige Rolle beider Fehlerfortpflanzung in der numerischen linearen Algebra. Ein gewisser Nachteil istallerdings, dass sie nur bei Kenntnis der inversen Matrix zugänglich ist.

Man kann leicht eine untere Schranke für condN(A) angeben, falls N submultiplikativist, d.h. falls gilt N(AB) ≤ N(A)N(B). In diesem Fall stellt man fest

N(E) = N(AA−1) ≤ N(A)N(A−1) = condN(A).

Aus 0 < N(E) ≤ N(E)N(E) folgt N(E) ≥ 1; also kann man die Abschätzung vergrö-bern zu

1 ≤ condN(A).

Die Konditionszahl condN(A) einer regulären Matrix A hängt nach Definition von dergewählten Matrixnorm N ab. Man kann nun die Frage stellen, ob sich bei gegebenerNorm N die Konditionszahl durch den Übergang von A zu einer geeigneten Matrix TAverkleinern lässt. Dazu löse man zunächst folgende Aufgabe.


Aufgabe 4.4.Durch die Wahl der Matrixnorm

‖C‖2 := supy 6=0

‖Cy‖2‖y‖2

=√λmax(CHC), C ∈ Km×m

ensteht als zugehörige Kondition die sogenannte Spektralkondition

cond2(A) := ‖A‖2 · ‖A−1‖2.

Für die so definierte Spektralkondition folgt: ist A eine reguläre Matrix und U eineunitäre Matrix so gilt

cond2(A) = cond2(UA) = cond2(AU).

Die Spektralkondition bleibt also beim Übergang von A zu UA oder AU invariant,wenn U unitär ist. Dies ist für numerische Zwecke günstig. So haben z.B. beim QR-Verfahren die Matrizen Ak = QkRk und Rk dieselbe Spektralkondition und, da dieMatrizen Ak unitär ähnlich sind, haben die Matrizen Ak und Rk für alle k diesselbeKonditionszahl wie die Ausgangsmatrix A.

Wir kommen zurück zur Frage, ob man die Konditionszahl einer Matrix A durch Über-gang zur Matrix TA verkleinern kann. Dazu definieren wir die Matrixnorm

‖C‖∞ := maxy 6=0

‖Cy‖∞‖y‖∞

= maxi

m∑k=1

|cik|

und die zugehörige Kondition

cond∞(A) := ‖A‖∞ · ‖A−1‖∞.

Man beachte, dass die Matrixnorm ‖ · ‖∞ zur Zeilensummennorm gehört. Motivationfür unser weiteres Vorgehen liefert die folgende

Aufgabe 4.5.

1. Für

A :=

1 1 11 10 1001 100 10000

berechne man cond∞(A).

2. Man bestimme eine Diagonalmatrix D := diag(d11, d22, d33) so, dass die Betrags-summen aller Zeilen von DA den Wert Eins haben, und berechne cond∞(DA).

Das Resultat dieser Aufgabe zeigt, dass man die auf der Zeilensummennorm beruhendeKonditionszahl cond∞(·) eventuell dadurch erheblich verkleinern kann, dass man dieZeilen von A mit geeigneten Faktoren multipliziert. Dies entspricht einer Änderung desMaßstabs, in dem die Zeilenelemente gemessen werden. Man spricht deshalb auch voneiner Skalierung. Teil 2 der obigen Aufgabe 4.5 lässt also folgendes vermuten.


Satz 4.6 (Günstige Skalierung von Matrizen).Gilt für eine reguläre Matrix A ∈ Km×m die Beziehungen

m∑k=1

|aik| = 1, i = 1, ...,m,

so folgt für jede reguläre Diagonalmatrix D die Ungleichung

cond∞(DA) ≥ cond∞(A).

Daraus folgt für eine beliebige invertierbare Matrix A ∈ Rm×m und eine invertierbareDiagonalmatrix D ∈ Rm×m:

cond∞(DA) ≥ cond∞(D∗A)

mit

D∗ =

d∗1 0

d∗2. . .

0 d∗m

, d∗i =1∑m

j=1 |aij|.

Dies folgt, weil A := D∗A gerade die im ersten Teil des Satzes verlangte Eigenschaftbesitzt.

Beweis:Wir setzen

A−1 =: (αik)i,k=1,...,m, D := diag(d11, ..., dmm).

Dann folgt

‖A−1D−1‖∞ = maxi=1,...,m

m∑k=1

|αik| ·1

|dkk|

≥

(max

i=1,...,m

m∑k=1

|αik|

)· mink=1,...,m

1

|dkk|

= ‖A−1‖∞ · mink=1,...,m

1

|dkk|

sowie

‖DA‖∞ = maxi=1,..,m

|dii|m∑k=1

|aik| = maxi=1,...,m

|dii|.

Man erhält so

cond∞(DA) = ‖DA‖∞ · ‖A−1D−1‖∞

≥ ‖A−1‖∞ · mink=1,...,m

1

|dkk|· maxi=1,...,m

|dii|,

woraus wegen

mink=1,...,m

1

|dkk|· maxi=1,...,m

|dii| ≥ 1 = ‖A‖∞


die Behauptungcond∞(DA) ≥ cond∞(A)

folgt. �

Damit haben wir gezeigt, dass sich bei einer regulären Matrix A, deren sämtliche Zei-lenvektoren in der l1-Norm die Länge Eins besitzen, die Kondition cond∞(A) durchSkalierung nicht mehr verbessern lässt. Es empfiehlt sich also anstelle des Gleichungs-systems

Ax = b das System D∗Ax = D∗b

zu lösen, wobei die Diagonalmatrix D∗ so wie im obigen Satz 4.6 gewählt ist.

Neben Fehlern in den Daten b können auch „Störungen“ bei den Matrixelementen auf-treten. Wir wollen jetzt den Fall betrachten, dass ein System

(A+4A)x = b

gegeben ist. Dabei bezeichnet 4A die Fehlermatrix. Gesucht ist eine Abschätzung fürden absoluten Fehler

4x := x− x,wenn x die Lösung des „ungestörten“ Systems Ax = b bezeichnet.

Wegenx = (A+4A)−1b (falls A+4A regulär),

liegt es nahe, zunächst die „Störempfindlichkeit“ der Inversen zu bestimmen. Dazu dientfolgende Aufgabe.

Aufgabe 4.7.Es sei E die m ×m-Einheitsmatrix und S ∈ Km×m mit N(S) < 1 für eine submulti-plikative Matrixnorm N . Man zeige:

1. Die Matrix E + S ist regulär.

2. Es gilt: N((E + S)−1) ≤ N(E)

1−N(S).

Aus diesem Resultat erhalten wir für eine reguläre Matrix A im Fall

N(A−14A) < 1,

dass die Matrix E + A−14A und damit auch

A+4A = A(E + A−14A)

regulär ist und dass die Abschätzung

N((A+4A)−1) = N((E + A−14A)−1A−1) ≤ N(E)

1−N(A−14A)N(A−1)

gilt. Falls auchN(A−1)N(4A) < 1


gilt, folgt hieraus

N((A+4A)−1) ≤ N(E)

1−N(A−1)N(4A)·N(A−1).

Auf diesem Weg erhalten wir schließlich

N((A+4A)−1)

N(A−1)≤ N(E)

1−N(A−1)N(4A)

=N(E)

1− condN(A) · N(4A)

N(A)

.

Resultat 4.8 (Störempfindlichkeit der Matrixinversion).Für die reguläre Matrix A und eine zugehörige „Störmatrix“ 4A gelte

N(A−1)N(4A) < 1.

Dann existiert (A+4A)−1 und es folgt

N((A+4A)−1)

N(A−1)≤ N(E)


N(A)

.

Jetzt können wir uns dem oben gestellten Problem zuwenden, eine Abschätzung fürden Fehler 4x zu konstruieren, wenn die reguläre Matrix A entsprechend

(A+4A)(x+4x) = b

mit Fehlern 4A behaftet ist. Wegen Ax = b folgt

(A+4A)4x = −4A · x.

FallsN(A−1)N(4A) < 1

gilt, existiert (A+4A)−1. Dann erhalten wir

4x = −(A+4A)−14A · x

und hieraus‖4x‖ ≤ N((A+4A)−1)N(4A)‖x‖, x 6= 0.

Mit Resultat 4.8 folgt für den relativen Fehler

‖4x‖‖x‖

≤ N(E) · condN(A)


N(A)

· N(4A)

N(A).


Resultat 4.9 (Abschätzung des relativen Fehlers von x).Gilt

N(A−1)N(4A) < 1,

so lässt sich der relative Fehler der Lösung des gestörten linearen Gleichungssystems

(A+4A)(x+4x) = b, A regulär, b 6= 0,

abschätzen in der Form

‖4x‖‖x‖

≤ N(E) · condN(A)


N(A)

· N(4A)

N(A).

Den allgemeinen Fall, dass sowohl die Matrix A als auch die rechte Seite eines linearenGleichungssystems mit Fehlern behaftet sind, behandeln wir in der folgenden Aufgabe.

Aufgabe 4.10.Die Matrix A sei regulär und es gelte:

N(A−1)N(4A) < 1.

Dann lässt sich der relative Fehler der Lösung des linearen Gleichungssystems

(A+4A)(x+4x) = b+4b

abschätzen in der Form

‖4x‖‖x‖

≤ N(E)condN(A)


N(A)

(‖4b‖‖b‖

+N(4A)

N(A)

), x 6= 0 6= b.

Zusammenfassung:

In diesem Abschnitt haben Sie Abschätzungen für relative und absolute Fehler kennen-gelernt. Die Abschätzung des relativen Fehlers von x in Abhängigkeit von der rechtenSeite des Gleichungssystems Ax = b führte auf die Konditionszahlen von Matrizen. Andiesen Konditionszahlen erkannte man, dass Multiplikationen mit unitären Matrizenund bestimmte Skalierungen numerisch günstig sind.

Documents

Skript zur Vorlesung - KIT...Skript zur Vorlesung Numerische Methoden für die Fachrichtungen Elektrotechnik, Meteorologie, Geodäsie und Geoinformatik Prof. Dr. Wolfgang Reichel Institut