Numerik linearer Gleichungssysteme: Direkte und iterative Verfahren [1 ed.] 9783540206545, 354020654X [PDF]

Zitiervorschau

Springer-Lehrbuch

christian Kanzow

Numeriklinearer Gleichungssysteme: Direkte und iterative Verfahren Mit 39 Abbildungen

Springer

Christian Kanzow Universitat Wiirzburg Institut fiir Angewandte Mathematik und Statistik Am Hubland 97074 Wurzburg, Deutschland e-mail: [email protected]

Bibliografische Information Der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet iiber http://dnb.ddb.de abrufbar.

Mathematics Subject Classification (2000): 65F05,65F10,65F25,65N22, 15A60

ISBN 3-540-20654-X Springer Beriin Heidelberg New York Dieses Werk ist urheberrechtlich geschiitzt. Die dadurch begriindeten Rechte, insbesondere die der Ubersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfaltigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfaltigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulassig. Sie ist grundsatzlich vergiitungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Springer ist ein Unternehmen von Springer Science^Business Media springer.de © Springer-Verlag Berlin Heidelberg 2005 Printed in GermanyDie Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dafi solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten waren und daher von jedermann benutzt werden diirften. Satz: Reproduktionsfertige Vorlage vom Autor Herstellung: LE-TEX Jelonek, Schmidt & Vockler GbR, Leipzig Einbandgestaltung: design & production GmbH, Heidelberg Gedruckt auf saurefreiem Papier SPIN: 10974599 44/3142YL - 5 4 3 2 1 0

Fiir Karin, Rainer, Florian und Christoph

Vorwort

Die Losung eines linearen Gleichungssystems ist das in den Anwendungen der Mathematik vielleicht am haufigsten auftretende (Teil-) Problem. Die numerische Losung eines solchen Gleichungssystems ist daher von immenser Bedeutung. Das vorliegende Buch befasst sich gerade mit dieser Problemstellung. Es ist entstanden aus entsprechenden Vorlesungen, die der Autor an der Julius-Maximilians-Universitat Wiirzburg gehalten hat. Zum Verstandnis dieses Buches gentigen elementare Kenntnisse aus der linearen Algebra, wobei die wichtigsten Dinge im Kapitel 1 auch wiederholt werden. Aus diesem Grunde sollte das vorliegende Buch alien Studierenden zuganglich sein, sofern diese zumindest einen einsemestrigen Kurs zur linearen Algebra gehort haben und ansonsten ein gewisses Interesse an den numerischen Methoden der Mathematik mitbringen. Zum Aufbau des Buches: Es enthalt insgesamt acht Kapitel, die jeweils in mehrere Abschnitte gegliedert sind und am Ende stets eine Reihe von Aufgaben enthalten, deren Behandlung dem Leser dringend empfohlen wird. Das schon angesprochene Kapitel 1 enthalt neben einigen Grundlagen auch eine einfache Diskussion liber verschiedene Randwertprobleme bei partiellen Different ialgleichungen, die spater zur Erzeugung von Testbeispielen dienen. Das zweite Kapitel beschaftigt sich mit den direkten Verfahren zur Losung von linearen Gleichungssystemen. Im Mittelpunkt des Interesses steht hier insbesondere die LR-Zerlegung von Gaufi mitsamt seinen Varianten. Im Gegensatz zu vielen anderen Buchern wird in diesem Kapitel auch die ParlettReid-Aasen-Zerlegung zur Losung von linearen Gleichungssystemen mit einer nur symmetrischen Koeffizientenmatrix besprochen. Das dritte Kapitel behandelt eine Reihe von Orthogonalisierungsverfahren. Diese dienen etwas allgemeiner zur Losung von linearen Ausgleichsproblemen, konnen im Spezialfall aber auch zur Losung von linearen Gleichungssystemen herangezogen werden. Bei der Konstruktion einiger Krylov-Raum-Methoden treten spater allerdings auch explizit lineare Ausgleichsprobleme auf, so dass die im Kapitel 3 besprochenen Verfahren von Gram-Schmidt, Householder

viii

Vorwort

und Givens auch dort eingesetzt werden. Ferner enthalt das Kapitel 3 eine Behandlung der schnellen Givens-Rotationen. In den verbleibenden Kapiteln beschaftigen wir uns ausschliefilich mit iterativen Verfahren zur Losung von linearen Gleichungssystemen. Das Kapitel 4 behandelt dabei die mehr klassischen Split ting-Met hoden, deren Bedeutung in den letzten Jahren allerdings zurtickgegangen ist. Das Kapitel 5 ist dann voUstandig dem CG-Verfahren gewidmet. Im Kapitel 6 kommen wir zur Behandlung des GMRES-Verfahrens mitsamt einigen Varianten. Hierzu gehort auch das MINRES-Verfahren zur Losung von linearen Gleichungssystemen mit einer symmetrischen KoefRzientenmatrix. Im Kapitel 7 werden dann eine Reihe von weiteren Methoden vorgestellt, die sich in der Praxis bewahrt haben und heute zu den Standardverfahren zur Losung groBer linearer Gleichungssysteme gehoren. Das abschliefiende Kapitel 8 behandelt die Mehrgitterverfahren, die insbesondere bei der numerischen Losung von partiellen Differentialgleichungen eingesetzt werden. Ansonsten wird dem Dozenten ein Blick auf das Inhaltsverzeichnis weitaus mehr sagen als die Ausfiihrungen in diesem Vorwort. Insofern sind ein paar Worte liber die nicht behandelten Themen hier vielleicht sogar wichtiger. Zunachst betrachten wir keine Verallgemeinerungen der direkten Methoden auf grofidimensionale Probleme. Hierzu waren insbesondere auch spezielle Speichertechniken erforderlich, wie sie beispielsweise in dem Buch [53] von Saad behandelt werden. Die hier beschriebenen direkten Verfahren sind in der angegebenen Form daher nur auf Probleme von kleiner oder mittlerer Dimension anwendbar. Zur Losung grofidimensionaler Probleme dienen hingegen die iterativen Verfahren, bei denen die Matrix oft gar nicht abgespeichert werden muss. Stattdessen wird in vielen Fallen nur ein Matrix-Vektor-Produkt benotigt, das sich haufig sehr einfach berechnen lasst. Abgesehen von den Mehrgitterverfahren werden keine weiteren speziellen Methoden zur Losung von diskretisierten Differentialgleichungen behandelt. Der interessierte Leser sei hier beispielsweise auf Hackbusch [31] verwiesen. Daftir besprechen wir explizit direkte und iterative Verfahren zur Losung von symmetrischen (nicht notwendig positiv definiten) Gleichungssystemen, die in vielen verwandten Biichern keine Beriicksichtigung finden. Die Behandlung von symmetrischen Matrizen liegt letztlich wohl darin begrtindet, dass der Autor selbst im Bereich der Optimierung forscht, wo sehr haufig symmetrische (aber indefinite) Matrizen auftreten, vergleiche [24, 25]. Ansonsten bleibt mir zum Schluss nur die angenehme Pflicht, mich bei all denen zu bedanken, die mich bei der Entstehung dieses Buches tatkraftig untersttitzt haben. Namentlich seien hier insbesondere meine Sekretarin, Frau Wrschka, sowie meine Mitarbeiter, Herr Dr. Christian Nagel, Herr Dipl.-Math. Michael Flegel, Herr Dipl.-Math. Andreas Klug, Herr Dipl.-Math. Matthias Hummer sowie Frau Dipl.-Math. Stefania Petra genannt. Frau Wrschka hat in endlosen Stunden mein handschriftliches Manuskript mit einer erstaunlichen Sicherheit in ihren Computer getippt. Alle Mitarbeiter haben Telle des Manuskriptes gelesen und Verbesserungsvorschlage gemacht. Herr Nagel

Vorwort

ix

hat auBerdem in alien Fragen zum Umgang mit E*TJiX stets Auskunft geben konnen, wahrend Herr Flegel bereits in der Entstehungsphase des Skriptes (im Rahmen einer Vorlesung) wichtige Hinweise geliefert hat und obendrein bei der Konstruktion einiger Bilder von groBer Hilfe war. Nicht zuletzt gilt mein Dank natiirlich dem Springer-Verlag, insbesondere Herrn Peters und Frau McCrory.

Wurzburg, Februar 2004

Christian Kanzow

Inhaltsverzeichnis

1

Grundlagen 1.1 Lineare Gleichungssysteme L2 Einige Klassen von Matrizen 1.3 Normalformen von Matrizen 1.4 Vektor- und Matrixnormen 1.5 Kondition und Fehlerabschatzung 1.6 Das Kronecker-Produkt 1.7 Die Poisson-Gleichung 1.8 Die Helmholtz-Gleichung 1.9 Die Konvektions-Diffusions-Gleichung Aufgaben

1 1 7 10 17 21 25 27 35 38 42

2

Direkte Verfahren 2.1 Lineare Gleichungssysteme einfacher Struktur 2.2 LR-Zerlegung ohne Pivotisierung 2.3 LR-Zerlegung mit Pivotisierung 2.4 LR-Zerlegung flir Bandmatrizen 2.5 Cholesky-Zerlegung fur positiv definite Systeme 2.6 Parlett-Reid-Aasen fiir symmetrische Systeme Aufgaben

47 47 51 61 69 77 82 90

3

Orthogonalisierungsverfahren 3.1 Lineare Ausgleichsprobleme 3.2 QR-Zerlegungen 3.3 Gram-Schmidt-Orthogonalisierung 3.4 Householder-Spiegelungen 3.5 Givens-Rotationen 3.6 Schnelle Givens-Rotationen Aufgaben

95 95 100 104 109 115 121 129

xii

Inhaltsverzeichnis

4

Splitting-Methoden 4.1 Allgemeine Splitting-Verfahren 4.2 Gesamtschrittverfahren 4.3 Einzelschrittverfahren 4.4 SOR-Verfahren 4.5 Symmetrisches SOR-Verfahren 4.6 Tschebyscheff-Polynome 4.7 Polynomiale Konvergenzbeschleunigung 4.8 Vergleich der Verfahren Aufgaben

133 133 139 145 150 163 168 172 178 182

5

CG-Verfahren 5.1 Herleitung des CG-Verfahrens 5.2 Charakterisierungen des CG-Verfahrens 5.3 Konvergenzanalyse des CG-Verfahrens 5.4 Das prakonditionierte CG-Verfahren 5.5 Sphtting-basierte Prakonditionierer 5.6 Unvollstandige Cholesky-Zerlegung 5.7 CGNE und CGNR flir regulare Systeme Aufgaben

187 187 195 199 203 206 208 211 217

6

G M R E S und verwandte Verfahren 6.1 Krylov-Raume 6.2 GMRES flir regulare Systeme 6.3 GMRES(m) flir regulare Systeme 6.4 MINRES flir symmetrische Systeme 6.5 Prakonditionierte Verfahren 6.6 Unvollstandige LR-Zerlegung Aufgaben

221 222 226 235 239 250 255 257

7

Weitere K r y l o v - R a u m - M e t h o d e n 7.1 QMR-Verfahren 7.2 BiCG-Verfahren 7.3 CGS-Verfahren 7.4 BiCGSTAB-Verfahren 7.5 TFQMR-Verfahren Aufgaben

261 261 269 278 282 288 301

8

Mehrgitterverfahren 8.1 Nochmals die Poisson-Gleichung 8.2 Das Richardson-Verfahren 8.3 Gitter-Hierarchie 8.4 Das Zweigitterverfahren 8.5 Mehrgitterverfahren 8.6 VoUstandiges Mehrgitterverfahren

305 305 309 314 320 326 329

Inhaltsverzeichnis Aufgaben

xiii 335

Literatur

339

Index

343

Grundlagen

Dieses Kapitel beschaftigt sich mit einigen Grundlagen aus der linearen Algebra, die dem Leser aus den entsprechenden Vorlesungen im Grundstudium groBtenteils bereits bekannt sein diirften und hier nur der VoUstandigkeit halber wiedergegeben werden. Dem Leser wird daher empfohlen, dieses erste Kapitel zunachst nur zu iiberfliegen und erst bei Bedarf einen genaueren Blick auf den Inhalt zu werfen. Im Einzelnen behandeln wir im Abschnitt 1.1 die Losbarkeit von linearen Gleichungssystemen und diskutieren die Struktur der Losungsmenge, wahrend wir im Abschnitt 1.2 einige wichtige Klassen von Matrizen einftihren, die bei unseren spateren Untersuchungen eine besondere Bedeutung spielen. Danach wiederholen wir im Abschnitt 1.3 einige Normalformen von Matrizen, erinnern an die Definition und wesentlichen Eigenschaften von Vektor- und Matrixnormen im Abschnitt 1.4 und benutzen die hier gewonnenen Ergebnisse, um im Abschnitt 1.5 die Kondition einer Matrix zu definieren, die bei der Fehlerbetrachtung von linearen Gleichungssystemen eine grofie RoUe spielt. Die verbleibenden vier Abschnitte dienen im Wesentlichen nur dazu, um einige Testbeispiele ftir die noch zu beschreibenden Verfahren zu konstruieren. Als technisches Hilfsmittel fiihren wir dazu im Abschnitt 1.6 zunachst das so genannte Kronecker-Produkt ein, welches dann zur einheitlichen Herleitung von geeignet diskretisierten Formen der Poisson-, Helmholtz- und Konvektions-DifFusions-Gleichung dient. Diese drei partiellen Differentialgleichungen werden in den Abschnitten 1.7, 1.8 und 1.9 etwas naher untersucht.

1.1 Lineare Gleichungssysteme Im Mittelpunkt dieses Buches steht das Problem, zu einer gegebenen Matrix AeW""^ und einem gegebenen Vektor 6 G M"" ein x G W^ mit Ax = b

(i.i;

2

1 Grundlagen

zu finden. A wird hierbei als Koeffizientenmatrix, b als rechte Seite und jedes X mit Ax = b als Losung des linearen Gleichungssystems (1.1) bezeichnet. Wir wiederholen in diesem Abschnitt im Wesentlichen einige bekarmte Kriterien zur Losbarkeit eines linearen Gleichungssystems. Prinzipiell konnen die folgenden Falle eintreten: - das lineare Gleictiungssystem (1.1) besitzt keine Losung; Beispiel:

-G:> das lineare Gleichungssystem (1.1) besitzt genau eine Losung; Beispiel:

^

1 ox -00 l l)' y

1^

-

VI

das lineare Gleichungssystem (1.1) besitzt unendlich viele Losungen; Beispiel:

(o o)' ^=G, Fiir eine genaue Untersuchung erinnern wir zunachst an einige elementare BegrifFe aus der linearen Algebra. Definition 1.1. Sei A G M'^^^ eine gegebene (nicht notwendig quadratische) Matrix. Dann heifien (a) Kem{A) := {x ^W\Ax = 0} der Kern von A; (b) Bild{A) := {y eW^\3x eW : Ax = y} das Bild von A; (c) Rang{A) := dim.{Bild{A)) der Rang von A. Der Kern einer Matrix A £ M"^^^ ist offenbar ein Unterraum des M^, wahrend das Bild von A einen Unterraum des W^ darstellt. Weiterhin ist der Rang von A gleich der maximalen Zahl an linear unabhangigen Spaltenvektoren von A, da diese offenbar den Raum Bild (A) aufspannen. Bekanntlich ist dies gleich der maximalen Zahl an linear unabhangigen Zeilenvektoren von A. Mit Hilfe dieser Begriffe sind wir in der Lage, das folgende Losbarkeitskriterium fur das lineare Gleichungssystem (1.1) zu formulieren. Satz 1.2. Seien A E E^^^ und 6 E M^ gegeben. Dann sind die folgenden Aussagen dquivalent: (a) Das lineare Gleichungssystem Ax = b besitzt (mindestens) eine Losung. (b) Es istbG Bild(A). (c) Es gilt Rang{A) = Rang{A^b), wobei (A^b) diejenige Matrix aus dem ]^nx(n+i) i)Qzeichnet, die aus A durch Hinzunahme von b als weitere Spalte entsteht.

1.1 Lineare Gleichungssysteme

3

Beweis. Die Aquivalenz von (a) und (b) folgt sofort aus der Definition von Bild(^). 1st nun (b) erflillt, so folgt Bild(^) = Bild{A,b) und damit auch Rang(^) = Rang(A, 6) gemafi Definition 1.1. Sei umgekehrt Rang(A) = Rang (A, 6). Dann ist 6 als Linearkombination der Spalten von A darstellbar. Dies impliziert aber b G Bild(A). D Die nachstehend formulierte Dimensionsformel dtirfte ebenfalls aus den Grundvorlesungen zur linearen Algebra bekannt sein. Satz 1.3. (Dimensionsformel) Sei A £ M"^^^ gegeben. Dann gelten die folgenden Aussagen: (a) Es ist n = diim{Kern{A)) + dim{Bild{A)). (b) Es ist m = dim{Kem{A'^)) + Rang{A). Beweis. (a) Setze k := dim(Kern(yl)). Sei 6i,...,6fe ferner eine Basis von Kern(^). Diese kann durch Hinzunahme von n — k weiteren Vektoren C i , . . . , Cn-k zu einer Basis des W^ erweitert werden. Wir behaupten, dass die Vektoren Aci,... ,Acn-k eine Basis von Bild(^) bilden, was dann die Behauptung (a) impliziert. Zunachst spannen die Elemente Aci,... ,Acn-k den Raum Bild(A) auf, denn fiir beliebiges x e W^ existieren ai, jSj £ E mit X = Yli=i o^i^i + ^"jZi Pj(^3^ woraus sich n—k

Ax =

n—k

A[Y,p^c^)^Y.f^3{Acj)

ergibt, was wiederum span{Aci,..., Acn-k} = Bild(A) impliziert. Ferner sind die Vektoren Aci^... ,Acn-k linear unabhangig, denn aus n—k

y ^ 'yj(Acj) = 0

mit 7^- G M

folgt zunachst n—k

^I]7jC,=0 und daher X^TjCj GKern(A). Folglich existieren Si^... ,Sk G R mit n—k

k

4

1 Grundlagen

Dies liefert k

n—k

i=l

j=l

Aber die Vektoren 6 1 , . . . , 6^, C i , . . . , Cn-k sind per Konstruktion linear unabhangig. Daher verschwinden alle KoefRzienten, insbesondere gilt also 71 = 0,...,7n-fc = 0 . (b) Wegen Rang(^) = Rang(A^) folgt aus Teil (a) unmittelbar m = dim(Kern(^^)) + dim(Bild{A^)) - dim(Kern{A^)) + Rang(A^) = dim(Kern(yl^)) + Rang(^), womit auch die Aussage (b) bewiesen ist.

D

In unserem nachsten Resultat untersuchen wir die Struktur der Losungsmenge eines linearen Gleichungssystems. Satz 1.4. Seien A G W^^^ und 6 G M" gegeben sowie x* G W^ eine beliebige Losung des linearen Gleichungssystems Ax = b. Dann ist die gesamte Losungsmenge von Ax = b gegeben durch x* + Kern{A). Beweis. Sei zunachst re G x* + Kern(A). Dann existiert ein y G Kern(A) mit x = X* -j-y. Hieraus folgt Ax = Ax* -I-Ay = Ax* = 6, d.h., a: ist ebenfalls eine Losung des linearen Gleichungssystems Ax = b. Sei umgekehrt a: G M^ eine Ldsung von Ax = b. Dann ist A{x — x*) = b — b = 0, also x — x* e Kern(^) und daher x £ x* + Kern(^). • Aufgrund der beiden vorhergehenden Satze 1.3 und 1.4 hat die Losungsmenge eines linearen Gleichungssystems Ax = b die Dimension dim(Kern(^)) =n-

dim(Bild(A)) = n ~ Rang(^).

Von besonderem Interesse ist hierbei der Fall Kern (A) = {0}, denn dann besitzt das lineare Gleichungssystem Ax = b genau eine Losung. Dies motiviert die folgende Definition. Definition 1.5. Eine quadratische Matrix A G R^^'^ heifit regular, wenn Kern{A) = {0} gilt Aufgrund der Herleitung ist eine Matrix A G M"^" also genau dann regular, wenn eine der folgenden aquivalenten Bedingungen erfiillt ist: - Kern(^) = {0} - BM{A) = W

1.1 Lineare Gleichungssysteme

5

- Rang(^) = n - das homogene lineare Gleichungssystem Ax = 0 hat nur die triviale Losung rr — 0 - das inhomogene lineare Gleichungssystem Ax = b hat ftir jede rechte Seite b eW^ genau eine Losung. Aus der hnearen Algebra ist aufierdem bekannt, dass eine Matrix A genau dann regular ist, wenn - det{A) ^ 0 ist, wobei det(^) nattirhch die Determinate von A bezeichnet. Regulare Matrizen A GR'^^^ besitzen eine inverse Matrix A~'^, die durch die Bedingung A-^A = 1

^=>

AA-^ = I

charakterisiert ist. Das Produkt zweier regularer Matrizen A^B G M"^^ ist offenbar wieder regular, und es gilt die Beziehung (AB)-^

=B-^A-\

denn es ist {B-^A-^){AB)

= B-\A-^A)B

= B'^B

- /,

so dass es sich bei B~^A~^ tatsachhch um die Inverse von AB handeln muss. Mit ^ G M""^"^ ist auch die transponierte Matrix A^ regular, und es gilt [A^y^

= {A-^Y

=: A-^

wegen [A'^YA^ = {^^~^T = r = 1. Fur einen beliebigen Unterraum F C R" fuhren wir schliefilich noch den so genannten Orthogonalraum V-^ := {zi; G M^ I w^v - 0 Vv G V} von V ein, vergleiche Abbildung 1.1. Offenbar ist V-^ selbst ein Unterraum, und es gilt ( V ^ ) ^ = V,

(1.2)

d.h., der Orthogonalraum des Orthogonalraums ist wieder der urspriingliche Vektorraum, vergleiche Aufgabe 1.2. Diese Aussage wird im Beweis des folgenden Resultates benotigt. Satz 1.6. Fiir A G M"^^"^ gelten die folgenden Aussagen: (a) Kern{A) = Bild{A^Y und Bild{A^) = (h) Kern{A) = Kern{A''A). (c) BildiA-^) = Bild{A^A).

Kem{AY.

6

1 Grundlagen

Abbildung 1.1. Veranschaulichung des Orthogonalraumes Beweis. (a) Wir beweisen zunachst die Inklusion Kern(^) C Bild(^ T\± V G Kern(A) ==> Av = 0 =^ve

Bild(yl^)^.

Die umgekehrte Inklusion Bild(A^)-^ C Kern(A) ergibt sich wie folgt: i; G Bild(A^)-^ = x:—Av

=^ =^

v'^A^x^Q \fxeW^ x'^Av^O VXGM"^ {AvY{Av) = 0 Av = 0 V e KeTn{A).

Zusammen folgt hieraus Kern(A) = Bild(74^)-'-. Dann sind aber auch die zugehdrigen Orthogonalraume gleich: Kern(^)-^ - (Bild(A^)-^)-^ = Bild(A'^), wobei die zweite Gleichheit aus (1.2) folgt. (b) Wir verifizieren zunachst die Inklusion Kern(A) C Kern(A^^): V e Kern(A) ==^ Av = 0 => A^Av = 0 ==^ v G Kern(A^^). Umgekehrt folgt die Inklusion Kern(A'^^) C Kern(A) aus V G Kein{A^A)

=^ A^Av = 0

1.2 Einige Klassen von Matrizen - ^ v^A^Av

=0

=^ Av = 0 =^ V e Kern(^). Insgesamt ergibt sich gerade die Behauptung (b). (c) Mit den Aussagen (a) und (b) folgt Bild(yl^) =^ Kern(yl)-^ ^^ Kexn{A^A)^ womit auch Teil (c) bewiesen ist.

^^ Bild(^^^),

n

1.2 Einige Klassen von M a t r i z e n Im Laufe der nachsten Abschnitte und Kapitel spielen eine ganze Reihe von speziellen Matrizen eine groBe Rolle. Die wichtigsten Vertreter sollen deshalb an dieser Stelle definiert werden. Sei dazu A € E"^"^ eine gegebene Matrix mit den Eintragen aij fiir i,j = 1 , . . . , n. Wir bezeichnen A als - Diagonalmatrix, falls aij = 0 fiir alle i ^ j gilt, d.h., wenn A von der Gestalt

[*

o\

Vo / ist. Fiir eine Diagonalmatrix mit den Diagonalelementen an, a22, • • •,cLnn schreiben wir auch diag(aii,a22, • • •, cinn)- Tridiagonalmatrix, falls aij = 0 fiir alle i,j G { 1 , . . . ,n} mit |i — i | > 1 gilt, d.h., wenn A von der Gestalt /* *

o\

A =

ist. untere Dreiecksmatrix, falls aij = 0 fiir alle i < j gilt, d.h., wenn A von der Gestalt A =

1 Grundlagen ist. obere Dreiecksmatrix, falls aij = 0 ftir alle i > j gilt, d.h., wenn A von der Gestalt * • • •* A =

Vo / ist. normierte untere (obere) Dreiecksmatrix, falls A eine untere (obere) Dreiecksmatrix ist, deren Diagonaleintrage alle gleich Eins sind. untere Hessenberg-Matrix , falls aij = 0 ftir alle j > i + l gilt, d.h., wenn A von der Gestalt * * *

ist. obere Hessenberg-Matrix A von der Gestalt

, falls aij = 0 ftir alle i > j + 1 gilt, d.h., wenn

/ Vo ist. untere Bidiagonalmatrix, falls aij = 0 ftir alle i^j e { l , . . . , n } mit j 7^ i und j ^ i — I gilt, d.h., wenn A von der Gestalt /

* *

o\

A

\o

* *y

ist. o6ere Bidiagonalmatrix, falls a^j == 0 ftir alle i,j G { 1 , . . . ,n} mit j y^ i und J ^ i + 1 gilt, d.h., wenn A von der Gestalt /* *

0\

VO

* */

^ =

ist.

1.2 Einige Klassen von Matrizen - Bandmatrix, falls aij ^ 0 nur flir solche Indizes i^j £ { 1 , . . . , n } auftritt, ftir die i — p < j (C

A

^

>jC >jC

* * * * * * *

die untere Bandbreite p= 1 und die obere Bandbreite q ~ 2. - Permutationsmatrix , wenn sich die Zeilen von A durch eine Permutation aus den Zeilen der Einheitsmatrix 7 € R"^'^ ergeben. Aus der Definition einer Permutationsmatrix folgt sofort, dass P genau dann eine solche Matrix ist, wenn in jeder Zeile und Spalte von P genau eine Eins steht (und sonst lauter Nullen). Dies wiederum ist Equivalent dazu, dass die Spalten von P durch Vertauschung der Spalten von / entstehen. Die zeilenweise Sicht in unserer Definition ist ftir die Zwecke dieses Buches jedoch angemessener, da wir spater (bei der Behandlung der LR-Zerlegung) vor allem Zeilenvertauschungen vornehmen werden. Ferner nennen wir eine Matrix A = (aij) E M^^'^ -

symmetrisch, falls A = A^ gilt, also a^j — aji fur alle i,j G { 1 , . . . ,n} ist. positiv semidefinit, falls x'^Ax > 0 fur alle x G M'^ gilt. positiv definit, falls x'^Ax > 0 fur alle x G M'^ mit x ^0 gilt. symmetrisch positiv semidefinit, falls A sowohl symmetrisch als auch positiv semidefinit ist. - symmetrisch positiv definite falls A sowohl symmetrisch als auch positiv definit ist. - orthogonal^ falls A^A — I gilt, falls also die Spalten a^,a^,..., a'^ von A orthonormal sind, also / i\T A ^ f 1, falls i = j , {a') a':= Sij := ^^' 0, falls i y^ j ist. - nichtnegativ, falls aij > 0 fur alle i,j G { l , . . . , n } gilt. Hierfiir schreiben wir auch A> 0. - positiv, falls aij > 0 fiir alle i,j G { l , . . . , n } gilt, wofiir wir kurz A > 0 schreiben. Eine Matrix A G M^^^ ist offenbar genau dann orthogonal, wenn A'^ orthogonal ist. Ferner ist auch jede Permutationsmatrix orthogonal. Um dies einzusehen, bezeichnen wir mit

10

1 Grundlagen e, : - ( 0 , . . . , 0 , 1 , 0 , . . . , 0 ) ^ € E ^

den i-ten Einheitsvektor im W^ (die Eins steht an der z-ten Stelle). 1st P e W^^^ dann eine Permutationsmatrix, so existiert gemaB Definition eine bijektive Abbildung TT : { 1 , . . . , n} —^ { 1 , . . . , n} mit

(

I

'

V I

I

Hieraus folgt sofort

PP'^^

(

:

1 ( eJrn • • • e J . ^ ] =

-.

1=7.

Also ist P^ und damit auch P orthogonal. Ferner ist das Produkt zweier orthogonaler Matrizen A,B ^ M^^^ wieder orthogonal, wie sich unmittelbar aus

{AB^AB

= B'^ A'A B = B^B - / =7

ergibt. Hingegen ist das Produkt zweier symmetrischer Matrizen A^B E W^^'^ im Allgemeinen nicht symmetrisch! Beispielsweise erhalt man fiir 1 2X 3 i)

und S : = i ; I

die beiden Produkte

-=G:) - --G») man vergleiche hierzu auch die Aufgabe 1.7. Abschliefiend weisen wir noch ausdrucklich darauf hin, dass in diesem Buch eine positiv definite oder semidefinite Matrix nicht notwendig symmetrisch sein muss. Soil die Symmetrie explizit gefordert werden (was meistens der Fall sein wird), so wird dies auch gesondert vorausgesetzt, indem wir ausdrucklich von einer symmetrisch positiv definiten bzw. semidefiniten Matrix sprechen, vergleiche die obigen Definitionen. Diese kleine Unterscheidung ist insofern wichtig, als dass viele der bekannten Charakterisierungen von positiv definiten oder semidefiniten Matrizen nur unter der zusatzlichen Voraussetzung der Symmetric gelten.

1.3 Normalformen von Matrizen Dieser Abschnitt enthalt einige so genannte Normalformen von Matrizen, die insbesondere fiir die theoretischen Untersuchungen in den spateren Kapiteln

1.3 Normalformen von Matrizen

11

von einiger Bedeutung sind. Da wir hier lediglich an reellen Matrizen interessiert sind, geben wir diese Normalformen auch nur ftir reelle Matrizen an, wenngleich die komplexe Formulierung manchmal etwas eleganter ist. Vor der Bereitstellung unseres erst en Result ates erinnern wir daran, dass eine (eventuell komplexe) Zahl A ^ C als Eigenweii einer Matrix A G W^'^^ bezeichnet wird, wenn ein f 7^ 0 mit

Av = \v existiert. Jedes solche v heifit dann Eigenvektor von A zum Eigenwert A. Offenbar ist mit v auch jedes Vielfache av,a ^ 0, ein Eigenvektor von A zum Eigenwert A. Gemafi Definition ist A genau dann ein Eigenwert von A, wenn das homogene lineare Gleichungssystem {A — \I)v = 0 eine nichttriviale Ldsung t; 7^ 0 besitzt. Dies wiederum ist aquivalent dazu, dass die Matrix A — XI singular ist, also det(74 — A/) = 0 gilt. Folglich ist A genau dann ein Eigenwert von A, wenn A eine Nullstelle des so genannten charakteristischert Polynoms PA{t) :=det{A-tI) von A ist. Hieraus folgt beispielsweise, dass die Diagonaleintrage einer (oberen oder unteren) Dreiecksmatrix T notwendig die Eigenwerte dieser Matrix sind, denn die Determinante einer Dreiecksmatrix ist bekanntlich gleich dem Produkt ihrer Diagonaleintrage. Ferner haben ahnliche Matrizen dieselben Eigenwerte, da sich die Nullstellen des charakteristischen Polynoms bei einer Ahnlichkeitstransformation offenbar nicht andern (zur Erinnerung: zwei Matrizen A,B e M^^^ heiBen dhnlich, wenn eine regulare Matrix X e R^^^ existiert mit B = XAX~^). Ist A daher ahnlich zu einer Dreiecksmatrix, so sind die Diagonalelemente dieser Dreiecksmatrix auch die Eigenwerte von A. Diese Bemerkungen erklaren insbesondere den zweiten Teil das nachstehenden Satzes, wobei die Ahnlichkeitstransformation hier sogar durch eine orthogonale Matrix gegeben ist. Satz 1.7. (Schursche Normalform) Sei A G M^^^ eine gegebene Matrix mit lauter reellen Eigenwerten. Dann existiert eine orthogonale Matrix Q £ R^^^ derart, dass Q'^AQ =: T eine obere Dreiecksmatrix ist Die Diagonalelemente von T sind hierbei die Eigenwerte von A. Beweis. Aufgnmd der vorangehenden Diskussion haben wir lediglich die Existenz einer orthogonalen Matrix Q zu zeigen, mit der Q'^AQ zu einer oberen Dreiecksmatrix wird. Der Beweis hierfur geschieht durch Induktion nach n. Ftir n = 1 ist die Aussage klar, indem man einfach Q := I setzt. Sei daher n > 2 und die Aussage ftir alle Matrizen mit reellen Eigenwerten der Dimension n — 1 richtig. Sei nun A G W^^^ eine beliebige Matrix mit lauter reellen Eigenwerten. Wir wahlen einen dieser Eigenwerte und nennen ihn Ai. Der zugehdrige Eigenvektor heifie xi. Da A und Ai beide reell sind, kann xi hierbei ebenfalls

12

1 Grundlagen

reell gewahlt werden. Aufierdem konnen wir durch Normierung ohne Einschrankung davon ausgehen, dass x^Xi = 1 gilt. Dann existieren Vektoren 0:2,..., Xn derart, dass xi, X2, • . . , x^ eine Orthonormalbasis des M^ ist, also xfxj = Sij gilt. Seien nun A2,-..,An G M die iibrigen Eigenwerte von A. Definiere dann eine Matrix V e W^^^'^~^^ durch V:=

X2 •

SO dass [xi V] G M"^^ eine orthogonale Matrix ist mit A[xi V] = [Aixi AV]. Wegen rr^^xi = 1 und V^xi — 0 erhalten wir

[x, VfAlxi

Ai xlAV 0 V^AV

V]

so dass die Eigenwerte von V^AV gegeben sind durch A2,..., A^, denn die Matrix [xi VYA[xi V] ist ahnlich zu A und besitzt daher dieselben Eigenwerte. Nach Induktionsvoraussetzung gibt es dann eine orthogonale Matrix U e M(^-i)x("-i) derart, dass W^V^AVU =: R eine obere Dreiecksmatrix ist mit den Eigenwerten A2,..., A„ auf der Diagonalen. Definiere nun Q := [xi V]

1 0 OU

Dann folgt Q'^AQ =

1 0 Ai 0

Ai x^AV 0 V^AV

1 0 OU

xJAVU U^V^AVU

Ai x^AVU 0 R

wobei T eine obere Dreiecksmatrix mit den Eigenwerten A i , . . . , A^^ von A auf der Diagonalen ist. • Wir woUen den Satz 1.7 jetzt auf symmetrische Matrizen anwenden. Zu diesem Zweck bemerken wir zunachst, dass alle Eigenwerte einer synunetrischen Matrix stets reell sind, was den Satz 1.7 liberhaupt erst anwendbar macht. Sei namlich X £ C ein unter Umstanden komplexer Eigenwert von A mit zugehorigem (eventuell komplexen) Eigenvektor a; G C^, von dem wir ohne Beschrankung der Allgemeinheit annehmen, dass x"x = I gilt, wobei wir

1.3 Normalformen von Matrizen jb

.— X

.—

13

I'Cl 5 • • • 5 '^n)

gesetzt haben. Aus der Gleichung Ax = Ax folgt dann A = \x"x

= x"{Xx) = x"Ax = x"A"x

= {Ax)" x = {Xx)" x = Xx"x = X.

Folglich ist A = A und A somit reell. Eine symmetrische Matrix besitzt also lauter reelle Eigenwerte. Als Konsequenz des Satzes 1.7 erhalten wir nun das nachstehende Result at. Satz 1.8. (Spektralzerlegung oder Spektralsatz) Sei A eW^ eine symmetrische Matrix. Dann existiert eine orthogonale Matrix Q e W^^^ derart, dass Q^AQ =: D eine Diagonalmatrix ist. Die Eigenwerte von A sind hierhei gerade die Diagonalelemente von D. Beweis. Da A als symmetrische Matrix nur reelle Eigenwerte besitzt, existiert aufgrund des Satzes 1.7 eine orthogonale Matrix Q G M'^^'^, so dass Q'^AQ =: T eine obere Dreiecksmatrix ist, deren Diagonaleintrage gerade die Eigenwerte von A sind. Wir behaupten, dass T in diesem FaU sogar eine Diagonalmatrix ist. Aus der vorausgesetzten Symmetrie von A folgt namlich T^ = [Q^AQY

= Q^A^Q

= Q-^AQ = T.

Die Gleichheit T = T'^ ist fur eine obere Dreiecksmatrix T aber nur moglich, wenn T Diagonalgestalt hat. D Sei A € W^^^ eine symmetrische Matrix und Q'^AQ = D die Spektralzerlegung aus dem Satz 1.8. Schreiben wir D — diag(Ai,..., A^) und bezeichnen wir den 2-ten Spaltenvektor der orthogonalen Matrix Q mit g% so folgt aus Q^AQ = D 4=^ AQ = QD M mit den Eigenschaften (i) (ii) (in) (iv)

\\x\\ > 0 fiir alle x e X; \\x\\ = 0

furalle.^O.

ftir alle x e M^.

\\AX\\Y

eW^^

beliebig gegeben. Dann folgt

\AB]\YZ

=

sup

\\ABX\\Y

x^O

< sup

\\X\\Z

\\A\\YX

xj^o =

\A\\YX

'

\\BX\\X

^

m\z sup

\\BX\\X

x^o m\z = \\A\\YX

\\B\\XZ.

wobei die hierin auftretende Ungleichung aus dem schon bewiesenen Teil (a) folgt. a Die Eigenschaft (a) aus dem Lemma 1.18 wird als Vertrdglichkeit von Vektorund (induzierter) Matrixnorm bezeichnet, wahrend die Eigenschaft (b) die so genannte Submultiplikativitdt von (induzierten) Matrixnormen ist. An dieser Stelle sei vermerkt, dass nicht jede Matrixnorm durch eine Vektornorm induziert wird. Beispielsweise ist die Frobenius-Norm

PIIF:=(E4)'^'

furAeK"X"

1.5 Kondition und Fehlerabschatzung

21

(fiir n > 1) keine induzierte Matrixnorm, denn es gilt ||7||F

= yfn

flir die Einheitsmatrix / G

W''',

wahrend man flir jede induzierte Matrixnorm ofFenbar ||/|| = sup \\Ix\\ - sup \\x\\ = 1 ||x||=l 11x11 = 1 erhalt. Abschliefiend erwahnen wir noch ein einfaches Ergebnis zur Abschatzung von Eigenwerten. Zuvor werden allerdings noch zwei niitzliche Begriffe eingefiihrt. Definition 1.19. Sei A € W^^'^ eine gegebene Matrix. Dann heifit (i) (T{A) := {A G C I A Eigenwert von A} das Spektrum von A; (a) p{A) := max {|A| | A G cr(A)} der Spektralradius von A. Das Spektrum ist also die Menge aller Eigenwerte einer Matrix, wahrend der Spektralradius durch den betragsgroBten Eigenwert gegeben ist. Der Spektralradius spielt beispielsweise in dem folgenden Satz eine Rolle. Satz 1.20. (Satz von Hirsch) Fiir jede Matrix M G M^^^ und jede induzierte Matrixnorm || • || gilt die Ungleichung p{M) < \\M\\. Beweis. Sei A ein beliebiger (eventuell komplexer) Eigenwert der Matrix M mit zugehorigem (eventuell komplexen) Eigenvektor x ^ 0. Aus Mx = Xx und Lemma 1.18 (a) folgt dann |A| ||a;|| = ||Aa:|| = \\Mx\\ < \\M\\ \\x\\ und daher |A| < ||M||. Da dies fiir jeden Eigenwert A von M gilt, folgt die Behauptung. n Der Spektralradius wird im Rahmen dieses Buches vor allem bei der Konvergenzuntersuchung von Splitting-Verfahren von groBer Bedeutung werden, siehe das Kapitel 4.

1.5 Kondition und Fehlerabschatzung Wir betrachten in diesem Abschnitt ein lineares Gleichungssystem Ax — b mit einer regularen Matrix A G E"^'^ und gegebenem 6 G M^. Parallel hierzu untersuchen wir ein zweites lineares Gleichungssystem der Form Ax = b mit einer gestorten rechten Seite 6 G M^, die als Naherung an die eigentlich interessierende rechte Seite 6 G M'^ aufgefasst werden soil, wahrend wir zur

22

1 Grundlagen

Vereinfachung der Problematik in beiden Gleichungssystemen dieselbe Koeffizientenmatrix A nehmen. Wir wollen untersuchen, wie sich die Unterschiede von b und b auf die Losungen der zugehorigen linearen Gleichungssysteme auswirken. Dies ist insofern wichtig, als dass die berechnete Losung eines linearen Gleichungssystems aufgrund des benutzten Verfahrens oder auch der nur endlichen Rechengenauigkeit des Computers im Allgemeinen nicht mit der exakten Losung iibereinstimmt. Hingegen kann die berechnete Losung als die exakte Losung eines gestorten linearen Gleichungssystems aufgefasst werden. Satz 1.21. Seien A G W'^'^ eine reguldre Matrix sowie 6,6 G M*^ zwei gegebene Vektoren mit b^ 0. Bezeichnen wir die Losungen von Ax = b bzw. Ax = b mit X bzw. X, so gilt die Ungleichung

^^ M eine ebenfalls gegebene Funktion darstellt. Dabei sei angemerkt, dass bei der klassischen Helmholtz-Gleichung / = 0 gilt und man deshalb auch gerne von der Eigenwert-Gleichung spricht, denn in diesem Fall ist jede nichttriviale Losung des Problems eine zum Eigenwert A zugehorige Eigenfunktion des Laplace-Operators. Wir interessieren uns im Folgenden vor allem fiir die Falle n = 1 und n = 2 der HelmholtzGleichung. Sei zunachst n — 1 und J? = (0,1). Das Dirichlet-Problem ftir die Helmholtz-Gleichung lautet dann -u"{x)

- \u[x) = f{x) n(0) = 0,

ftir alle x G (0,1), u{l) = 0.

Zur Diskretisierung der Helmholtz-Gleichung sei wieder eine Zahl AT G N gegeben, die ihrerseits eine Schrittweite AT + l bestimmt, mit deren Hilfe wir die insgesamt N + 2 aquidistant verteilten Punkte Xi := ih ftir i = 0 , 1 , . . . , A/" + 1 definieren. Setzen wir zur Abktirzung noch

36

1 Grundlagen Ui:=u{xi),

fi := f(xi)

fiir i = 0 , 1 , . . . , iV + 1

und approximieren die zweite Ableitung u"{x) im Punkte x = xi wie vorher durch den zentralen Differenzen-Quotienten

SO lasst sich die Helmholtz-Gleichung in den diskreten Punkten xi naherungsweise wiedergeben durch das System -Ui-i

+ (2 - \)ui - UiJ^i ^ h?fi

yi^l,...,N.

Bezeichnen wir mit Vi diejenigen Naherungen an die Ui, welche den Gleichungen -Vi^i + (2 - X)vi - Vi+i = h^fi yi=l,...,N exakt geniigen und berticksichtigen noch VQ := UQ = u{0) = 0

sowie

Vjv+i '-= UN+I = u{l) = 0

aufgrund der vorgegebenen Randbedingungen, so erhalten wir ein lineares Gleichungssystem der Form HMV = h^f mit den Vektoren v:={v^,...,VNVeR'^, /:=(/i,...,/Af)"€R^

und der von dem Parameter A abhangigen Tridiagonalmatrix /2-A HN

:= HN{A)

:=

-1

-1

0

\

2 - A ••. •.

V 0

>NxN

(1.15)

•. - 1 -12-A/

Offenbar ist die Matrix Hjsr stets symmetrisch, im Gegensatz zu der entsprechenden Matrix Tj\j aus (1.8) jedoch im Allgemeinen nicht mehr positiv definit. Die Matrix HN kann in der Tat eine ganze Reihe von negativen Eigenwerten besitzen. Dies hangt natiirlich von der Wahl von A ab und wird in dem folgenden Result at prazisiert. Satz 1.30. Die Matrix HN = HN{X) aus (1.15) besitzt die Eigenwerte

Afc:=(2-A)-2cos(^)=2(l-cos-^)-A, mit zugehorigem Eigenvektor x^ G M^, dessen Komponenten durch

^?-sin(^^-^), wobei k ebenfalls die Menge { 1 , . . . , N}

i = l,...,iV, durchlduft.

k=l,...,N, gegeben sind

1.8 Die Helmholtz-Gleidmng

37

Beweis. Wegen HM{^) = TN — XIN haben die beiden Matrizen if AT (A) und Tjsf dieselben Eigenvektoren, wahrend die Eigenwerte um —A verschoben werden. Die Behauptung folgt daher unmittelbar aus dem Satz 1.27. D Als Nachstes betrachten wir den Fall n — 2 mit Q = (0,1) x (0,1). Das Dirichlet-Problem flir die zweidimensionale Helmholtz-Gleichung ist dann gegeben durch d XL d u -^(ar,y)--Q-2^^^y)~'^^(^'y)

= /(^'y)

^^^^^^^ ( ^ ' y ) ^ ^ '

u{x,y) — 0 flir alle {x,y) G dO. Wir diskretisieren die Menge i? wieder durch Einfiihren von Punkten Xi := ih^ yi := ih

flir alle i = 0 , 1 , . . . , iV + 1

mit der Schrittweite h := l/(Ar+l) flir ein N eN. Benutzen wir die Abktirzungen Uij :=u{xi,yj),

fij := f{xi,yj)

fiir alle i, j = 0 , 1 , . . . ,iV + 1

und verwenden die bereits aus dem vorigen Abschnitt bekannte Naherung d'^u{xi,yj) dx^

_ d'^u{xi,yj) dy'^

_ 4uij - Uj-ij - Uj+ij - Ujj-i - Ujj+i h^

flir den (negativen) Laplace-Operator, so lasst sich die zweidimensionale Helmholtz-Gleichung approximativ schreiben als (4 - X)Uij - Ui-ij - Ui+ij - Uij-i - Uij+i ^ h^fij

Vi, j = 1 , . . . , N.

Ersetzen wir die nicht bekannten Uij durch Naherungen Vij, welche die Gleichungen (4 - X)vij - Vi-ij - Vi+ij - Vij^i - Vij+i = h^fij

Vi,i = 1 , . . . , AT (1.16)

exakt erfuUen, und setzt man noch Vo,j = VN+IJ = Vi,0 = Vi,N+l =0

V2,i = 0, 1, . . . , AT + 1

aufgrund der vorgegebenen Randwerte, so beschreibt (1.16) ein lineares Gleichungssystem mit n := iV^ Gleichungen in den ebenfalls n = N^ Unbekannten Vij {i,j = l,...,N). Setzen wir T/:=(^,,-)e]R^> m > 0 mit m\\x\\a

fiir alle

< \\x\\b
-» A^^^ ist stetig auf dem Raum der synmietrischen und positiv semidefiniten Matrizen. Aufgabe 1.9. Seien A,Ae W^^^ zwei regulare 6,6 G M^ gegebene rechte Seiten mit b ^ b {A eine Losung des Hnearen Gleichungssystems Ax gestorten Systems Ax = b. Zeigen Sie, dass dann

iwi

-

Matrizen mit A ~ -Ti SOW16 ^^ O^b y^ 0). Seien ferner x = b und x eine Losung des die Abschatzung

V ii^ii

gilt, wobei hier eine behebige Vektornorm mit der induzierten Matrixnorm genommen werden kann. Interpretation: Der relative Fehler in der Losung x ergibt sich im Wesentlichen aus der Summe der relativen Fehler der Daten A und 6, unter Umstanden allerdings verstarkt durch den Vorfaktor ||74|| ||^~-^||, der fur A ^ A weitgehend mit der Konditionszahl AC2(A) von A libereinstiromt. Aufgabe 1.10. (Singularwertzerlegung) Sei A G E"^^^ mit m> n und Rang(A) = r gegeben. Dann existieren orthogonale Matrizen t/ G M'^^"^ und V G M^^^ sowie eine Matrix T G M"'^^ der Gestalt

'ro 0 0

mit

E = diag((Ji,..., ar)

und

ai> ... > ar > 0,

so dass A = UEV^ gilt. Die ai heiBen dabei die Singularwerte von A, (Bemerkung: Ftir m < n erhalt man eine Singularwertzerlegung von A durch Betrachtung der Matrix A^.) Hinweis: Wende den Spektralsatz 1.8 auf A^A an.

44

1 Grundlagen

Aufgabe 1.11. Beweisen Sie die folgenden Aussagen als Konsequenz der Singularwertzerlegung aus der Aufgabe 1.10: (a) Fiir A G IR"'^''' ist P | | 2 = (Tmax{A), wobei (7max{A) den grdfiten Singularwert von A bezeichnet. (b) Fiir regulares B € W'''' ist K2{B) = ^ ^ ^ , wobei (7m^^{B) und amin{B) natiirlich den groBten und kleinsten Singularwert von B bezeichnen. Aus diesem Grunde definiert man als Kondition einer rechteckigen Matrix A G R"^^" auch K2{A) := ^ ^ H 4 | . (c)Fur A G R'^'''' mit Rang(^) = m ist P x | | 2 > crniin(^)lk||2 ftir alle xeW. Bemerkung: Diese Aufgabe wird beim Beweis der Aufgabe 7.5 gebraucht. Aufgabe 1.12. Seien G,K e M""^^ zwei gegebene Matrizen mit (eventuell komplexen) Eigenwerten A i , . . . , An und yL^i,..., /x^- Seien ferner x i , . . . , x^ und t/i,...,yn zugehorige Eigenvektoren. Dann ist A^/i^ ein Eigenwert von G ^ K mit zugehorigem Eigenvektor vec{yjx") fiir alle i, j = 1 , . . . ,n. Aufgabe 1.13. (Satz von Gerschgorin mit Anwendung auf T/VXAT) Sei A GW^^'^ beliebig gegeben. Dann liegt jeder (eventuell komplexe) Eigenwert von A in einem der so genannten Gerschgorin-Kreise Ki := {/i G C I l/i - aul < ^

\aij\}.

Man verifiziere mittels dieses Resultates noch einmal, dass die Matrix aus (1.13) symmetrisch positiv definit ist.

T/VXAT

Aufgabe 1.14. (Approximationsgtite finiter DifFerenzen) Im Folgenden sei stets x G E ein gegebener Punkt, h > 0 und u eine in einer Umgebung f2 von x definierte (hinreichend glatte) Funktion. Zeigen Sie: (a) u'{x) = ^(^+^^-^(^) + 0{h) ftir u G C^iH). (b) u'{x) - ^(^)-;^(^-^) + 0{h) ftir u G C^{n). (c) u'{x) - k > i.

•

Nach diesen Vorbereitungen sind wir nun in der Lage, die Existenz einer LRZerlegung und damit die Wohldefiniertheit des Algorithmus 2.11 zu beweisen. Satz 2.14. Sei A € R'^^"^ erne reguldre Matrix. Dann besitzt A genau dann eine LR-Zerlegung, wenn det{A[k]) ^ 0 fiir alle k = 1 , . . . , n gilt Beweis. Wir setzen zunachst voraus, dass A eine LR-Zerlegung besitzt. Dann existiert also eine normierte untere Dreiecksmatrix L eW^^^ und eine obere Dreiecksmatrix R G R'''^'' mit A = LR. Aus det(^) = det(L)det(i?) und der Regularitat von A folgt det(L) ^ 0 und det(i?) ^ 0. Da L und R Dreiecksmatrizen sind, liefert dies unmittelbar det(I/[A;]) ^ 0 und det(i?[A;]) ^ 0 fiir alle k = 1 , . . . , n. Mit Lemma 2.13 folgt somit det(A[A;]) - det{{LR)[k]) - det{L[k]R[k]) = det{L[k])det{R[k]) ^ 0 fiir alle /c == 1 , . . . ,n. Umgekehrt gelte nun det(A[A;]) ^ 0 fiir k = 1 , . . . ,n. Um nachzuweisen, dass A eine LR-Zerlegung besitzt, verifizieren wir, dass der Algorithmus 2.11 durchfiihrbar ist, dass also die Pivotelemente a\l^ fiir alle i = 1 , . . . ,n — 1 von Null verschieden sind. Der Beweis erfolgt durch Induktion nach i: Fiir i = 1 ist a[i = det(^[l]) ^ 0 nach Voraussetzung. Sei nun ayy ^ 0 fiir ein i > 1 mit i < n — 1 vorausgesetzt. Dann existiert insbesondere die Matrix A^'+^^ = Li - " LiA. Durch sukzessive Anwendung des Lemmas 2.13 ergibt sich hieraus A(^+i)[i + 1] =: Li[i + 1].. • Li[i + l]A[i + 1]. Aus dem Determinanten-Multiplikationssatz folgt daher det(A(^+i)[2 + 1]) = det(Li[i + 1]) • . . . • det(Li[i 4- l])det(^[i + 1]). Da A(^+i)[i+l] offenbar eine obere Dreiecksmatrix darstellt mit a\^^^l_^-^ als letztem Diagonalelement, folgt hieraus wegen det(A^*+^)[i + 1]) ^ 0 sofort

58

2 Direkte Verfahren

Wir woUen als Nachstes zeigen, dass die LR-Zerlegung unter den Voraussetzungen des Satzes 2.14 auch eindeutig bestimmt ist. Dazu benotigen wir noch zwei Hilfsaussagen. Wir zeigen zunachst, dass das Produkt von unteren (bzw. oberen) Dreiecksmatrizen wieder eine untere (bzw. obere) Dreiecksmatrix ist. Lemma 2.15. Es gelten die beiden folgenden Aussagen: (a) Sind L^^\L^^^ G W^^^ zwei untere (normierte) Dreiecksmatrizen, so ist auch L^^^L^^^ eine untere (normierte) Dreiecksmatrix, (b) Sind R^^\R^^^ G E ^ ^ ^ zwei obere (normierte) Dreiecksmatrizen, so ist auch i?(i)i?(2) eine obere (normierte) Dreiecksmatrix. Beweis. Wir beweisen lediglich die Aussage (a), da sich (b) voUig analog verifizieren lasst (bzw. sich einfach durch Transposition auf die Aussage (a) zuriickfiihren lasst). Seien also L^^^L^^^ G M"^^^ zwei untere Dreiecksmatrizen. Setze L := L^^^L^'^K Dann folgt fiir alle j > i wegen l\^ = 0 fiir m = j , . . . ,n und /^j = 0 fiir m = 1 , . . . , j - 1:

m=l

m=l

rn=j

d.h., L ist in der Tat eine untere Dreiecksmatrix. Sind L^^^ und L*^^^ sogar normierte untere Dreiecksmatrizen, so folgt voUig analog / _ V ^ /(l)/(2) _ V ^ ,(1) ,(2) , /(l)/(2) , V ^ ^1'^ — Z-^ ^im^mi ~ Z_^ ^im ''mi '^Hi Hi •" / _ ^ m=l m=l JYI m=i+l

,(1) 7(2) _ ;(1).(2) _ . ''im ''mi ~ ''ii ''ii ~ ^ j ^

fur alle Diagonalelemente la von L = L^^^L^^\ Somit ist L in diesem Fall sogar eine normierte untere Dreiecksmatrix. D Das nachste Resultat besagt, dass die Inverse einer unteren (bzw. oberen) Dreiecksmatrix ebenfalls eine untere (bzw. obere) Dreiecksmatrix ist. Lemima 2.16. Es gelten die beiden folgenden Aussagen: (a) Ist L G W^^'^ eine reguldre untere Dreiecksmatrix, untere Dreiecksmatrix. Ist L 'uberdies normiert, so (b) Ist R G W^^'^ eine reguldre obere Dreiecksmatrix, obere Dreiecksmatrix. Ist R 'Uberdies normiert, so

so ist auch L~^ eine ist auch L~^ normiert. so ist auch R"^ eine ist auch R~^ normiert.

2.2 LR-Zerlegung ohne Pivotisierung

59

Beweis. (a) Da L nach Voraussetzung regular ist, existiert die Inverse X := L~^. Per Definition gilt dann LX — / , was sich spaltenweise als Lxi = Ci Vi = 1 , . . . , n

(2.4)

formulieren lasst, wenn man mit Xi die i-te Spalte von X und mit ei den 2-ten Einheitsvektor im W^ bezeichnet. Betrachten wir ein festes i G { 1 , . . . , n} und partitionieren L, Xi und e^ in der Form

mit L^l e M(^-i)x(^-i),4^ G M(^-^+i)x(^-i),Lg e ]R(n-i+i)x(n-i+i) gQ^ig x ^ G M*-\a:^*^ G M^-^+i und dem Einheitsvektor ei G IR^-*+\ so lasst sich (2.4) in der Gestalt 0 -^21 -^22 ,

schreiben. Hieraus folgt insbesondere L^^x^^^ = 0, woraus sich wegen der Regularitat von L und der sich hieraus ergebenden Regularitat von L^\ unmittelbar rr^ = 0 ergibt. Also besitzt die i-te Spalte von X = L~^ in den ersten i — 1 Eintragen lauter Nullen. Da dies ftir alle i = 1 , . . . , n gilt, ist mit L auch die inverse Matrix X = L~^ eine untere Dreiecksmatrix. Ist L auBerdem normiert, so ergibt sich aus der obigen Zerlegung wegen x^l^ = 0 auch L22X2 = ^1- Da L22 eine normierte untere Dreiecksmatrix ist, folgt aus der ersten Gleichung dieses Systems unmittelbar, dass das z-te Element des Spaltenvektors Xi eine Eins sein muss. Da dies wiederum fur alle i = 1 , . . . , n gilt, handelt es sich bei der Inversen X = L~^ notwendig um eine normierte untere Dreiecksmatrix. (b) Die Aussage iiber obere Dreiecksmatrizen folgt unmittelbar aus der schon bewiesenen Aussage (a), indem man zu der transponierten Matrix iibergeht. • Als Konsequenz erhalten wir den folgenden Eindeutigkeitssatz fiir die LRZerlegung. Satz 2.17. Sei A G M'^xn ^g^^;^y ^if det{A[k]) ^ 0 fur k = 1,... ,n. Dann existiert genau eine LR-Zerlegung von A. Beweis. Die Existenz einer LR-Zerlegung folgt aus dem Satz 2.14. Zum Nachweis der Eindeutigkeit seien A = LiRi und A = L2R2 zwei LR-Zerlegungen von A mit normierten unteren Dreiecksmatrizen .^1,^2 ^ W^^'^ und oberen Dreiecksmatrizen Ri,R2 eR^^^. Dann folgt

60

2 Direkte Verfahren R2R1

L2

Li.

(2.5)

Wegen Lemma 2.15 und Lemma 2.16 ist i?2-R]"^ wieder eine rechte obere Dreiecksmatrix. Ebenfalls wegen Lemma 2.15 und Lemma 2.16 ist L^^I/i aber eine untere Dreiecksmatrix, die obendrein auch noch normiert ist. Aus (2.5) ergibt sich daher R2R1. - 1 = I und L2- 1 Li = / , also Li = L2 und Ri — R2 Somit ist D die LR-Zerlegung von A eindeutig bestimmt. Der Beweis des Satzes 2.17 zeigt iibrigens, dass eine LR-Zerlegung, sofern sie iiberhaupt existiert, notwendig eindeutig ist. Die Voraussetzung det(yl[A;]) ^ 0 fur alle /c = 1 , . . . , n wird hierzu gar nicht benotigt, sondern nur zum Nachweis der Existenz einer LR-Zerlegung. Bei der praktischen Durchfiihrung der LR-Zerlegung aus dem Algorithmus 2.11 speichert man die Elemente der Faktoren L und R nicht gesondert ab, sondern iiberschreibt die Eintrage von A mit diesen Elementen. Dabei werden die Elemente von L (mit Ausnahme der Diagonaleintrage, die aber alle gleich Eins sind) auf dem frei werdenden Platz unterhalb der Diagonalen von A gespeichert, wahrend im oberen Dreieck von A nach und nach die Matrix R entsteht. Ftir n = 4 sieht das Belegungsschema von A zu Beginn und am Ende des Algorithmus also wie folgt aus: / a n ai2 aiz a ^ X

/ r n ri2 ^ 3 r i 4 ^

^ 2 1 ^ 2 2 ^ 2 3 0-24 ^ 3 1 i mit a^-^^ 7^ 0 wahlt man diesen im AUgemeinen so, dass |aW| = max | a « | •^

i \a^\ - r r ^ l A I > \a^\ - \5i\ > |A+i|, \di-i\

was zu zeigen war.

D

Die Voraussetzungen des Lemmas 2.28 sehen auf den ersten Blick etwas technisch aus, lassen sich aber relativ leicht merken. Dazu sei zunachst erwahnt, dass man die Bedingung Si ^ 0 fur alle i = 2 , . . . ,n ohne Beschrankung der Allgemeinheit fordern kann, da ein lineares Gleichungssystem mit der Tridiagonalmatrix T anderenfalls offenbar in zwei oder mehr kleinere Gleichungssysteme zerlegbar ware. Die anderen Voraussetzungen des Lemmas 2.28 besagen lediglich, dass in jeder Zeile der Betrag des Diagonalelementes nicht kleiner ist als die Summe der Betrage der Eintrage aufierhalb der Diagonalen, wobei wir fur die erste Zeile eine strikte Ungleichung fordern. Diese Eigenschaften der Matrix T sind eng verwandt mit den spater einzufuhrenden Begriffen einer (strikt, irreduzibel) diagonaldominanten Matrix, vergleiche Definition 4.10 und Aufgabe 2.3. Wir kommen jetzt zur Betrachtung allgemeiner Bandmatrizen. Sei dazu j^ ^-^nxn gjj^g Matrix mit der unteren Bandbreite p und der oberen Bandbreite g. Zunachst nehmen wir auch hier an, dass die Matrix A eine LR-Zerlegung ohne Pivotisierung besitzt. Diese ist aufgrund des Satzes 2.17 dann notwendig eindeutig bestimmt. Das folgende Resultat besagt, dass sich die Bandstruktur von A dann voUstandig auf die Matrizen L und R iibertragt. Satz 2.29. Sei A G E^^'^ eine reguldre Bandmatrix mit unterer Bandbreite p und oberer Bandbreite q, die eine LR-Zerlegung A = LR besitze. Dann haben auch die normierte untere Dreiecksmatrix L die Bandbreite p und die obere Dreiecksmatrix R die Bandbreite q. Beweis. Der Beweis erfolgt durch vollstandige Induktion nach n. Fiir den Induktionsanfang n — min{p, g} + 1 ist offenbar nichts zu zeigen, denn die normale LR-Zerlegung von A leistet offenbar das Gewtinschte. Sei nun A € W^^'^ eine Matrix mit der unteren Bandbreite p und der oberen Bandbreite q. Wir partitionieren A in der Form V

B)

mit ae^,v,w e W'^ sowie B G E^'^-^^^^^"^) (beachte hierbei, dass a^O gilt nach Satz 2.14 sowie der vorausgesetzten Existenz einer LR-Zerlegung von A). Dann sind die letzten n—l—p Komponenten von v sowie die letzten n—l—q Eintrage von w alle Null, und B ist ebenfalls eine Bandmatrix mit unterer

2.4 LR-Zerlegung fiir Bandmatrizen

73

Bandbreite p und oberer Bandbreite q. Also ist die Matrix B — vw^/a eine ebensolche Bandmatrix im M ( ' ^ - I ) ^ ( ' ^ ~ I ) , die nach Induktionsvoraussetzung eine Zerlegung der Gestalt

B-vw'^/a

= LiRi

besitzt mit einer normierten unteren Dreiecksmatrix Li € ] R ( ^ ~ I ) ^ ( ^ ~ I ) , welche die untere Bandbreite p besitzt, und einer oberen Dreiecksmatrix Ri G ]R(^-I)>