Kurs:Numerik I/2 Normen und Fehlerabschätzungen

Aus Wikiversity
Zur Navigation springen Zur Suche springen

In diesem Kapitel werden die Begriffe einer Vektor- und Matrixnorm bereit gestellt und wird in Vorbereitung auf die numerische Lösung linearer Gleichungssysteme der Einfluss von Störungen der Matrix und des Vektors auf die Lösung des linearen Gleichungssystems untersucht. Im Hinblick auf weitere Anwendungen werden wir dabei zunächst Vektoren aus und Matrizen aus zulassen, wobei oder ist.

2.1 Normen[Bearbeiten]

Im Folgenden sei ein beliebiger Vektorraum über .

Definition 2.1[Bearbeiten]

Eine Abbildung heißt Norm, falls folgendes gilt:
(i)
(ii) (Positive Homogenität),
(iii) (Dreiecksungleichung).

Eine Norm wird auch Vektornorm und entsprechend eine Norm auch Matrixnorm genannt.

Lemma 2.2[Bearbeiten]

Für eine Norm gilt die umgekehrte Dreiecksungleichung

Beweis[Bearbeiten]

Es seien . Dann gilt

und somit

(2.1)

Das Vertauschen von und in (2.1) liefert

(2.2)

Die Ungleichungen (2.1) und (2.2) zusammen liefern die Behauptung.

q.e.d.

Einen Vektorraum , auf dem eine Norm definiert ist, bezeichnet man als einen normierten Vektorraum. Man kennzeichnet ihn auch durch .

Definition 2.3[Bearbeiten]

Es sei ein normierter Vektorraum. Eine Folge von Elementen konvergiert gegen , kurz
wenn gilt:

Unter Verwendung dieser Definition folgt sofort aus Lemma 2.2 das folgende Ergebnis.

Korollar 2.4[Bearbeiten]

Eine Norm ist stetig, d. h., es gilt

Beispiel 2.5[Bearbeiten]

Es sei . Beispiele für Vektornomen sind

(1) (Euklidische oder -Norm),
(2) (Summen- oder -Norm),
(3) (Maximum- oder -Norm).

Der Beweis dafür, dass die Maximum- und Summennormen tatsächlich die Normeigenschaften erfüllen, ist elementar und wird hier nicht vorgeführt. Für die Euklidische Norm folgt die Dreiecksungleichung mit der Cauchy-Schwarzschen Ungleichung. Und zwar schließt man mit

für , dass

für alle gilt, wobei den Realteil von bezeichnet. Allgemeiner ist, wie man zeigen kann, für jedes durch

(4) (-Norm)

eine Norm definiert, und es gilt

Man kann zeigen, dass je zwei paarweise verschiedene, auf einem endlich-dimensionalen Vektorraum definierte Normen und äquivalent sind, d. h., dass es Konstanten gibt, so dass gilt:

Wie man leicht verifiziert, hat man speziell für die im Beispiel 2.5 genannten Normen auf die folgenden Abschätzungen:

(2.3)

Die (scharfen) Abschätzungen in den ersten beiden Zeilen von (2.3) sind dabei leicht einzusehen. Die erste Abschätzung in der dritten Zeile folgt aus

die zweite mit der Cauchy-Schwarzschen Ungleichung aus

wobei der Vektor mit den Komponenten ist. Für große sind allerdings die jeweils zweiten Abschätzungen in (2.3) aufgrund der Größe der auftretenden Konstanten numerisch bedeutungslos.

Beispiel 2.6[Bearbeiten]

Die folgenden Normen sind Matrixnormen für Matrizen :

(1) (Frobenius-Norm),
(2) (Zeilensummennorm),
(3) (Spaltensummennorm).

Der Beweis dafür, dass die Zeilen- und Spaltensummennorm tatsächlich die Normeigenschaften erfüllen, ist elementar. Jede Matrix lässt sich als Vektor der Länge auffassen und die Frobenius-Norm fällt dann mit der Euklidischen Vektornorm zusammen. Somit genügt die Frobenius-Norm auch den Normeigenschaften.

Definition 2.7[Bearbeiten]

Eine Matrixnorm nennt man
(i) submultiplikativ, falls
(ii) mit einer gegebenen Vektornorm verträglich, falls

Definition 2.8[Bearbeiten]

Sei eine Vektornorm. Dann heißt die durch
definierte Norm die durch die Vektornorm induzierte Matrixnorm.

Man beachte, dass wegen der Kompaktheit der Menge und der Stetigkeit der Vektornorm das Maximum in der Definition von tatsächlich angenommen wird. Offenbar gilt .

Satz 2.9[Bearbeiten]

Die durch eine Vektornorm induzierte Matrixnorm besitzt die in Definition 2.1 angegebenen Normeigenschaften. Ferner ist sie submultiplikativ und bezüglich der zugrunde liegenden Vektornorm verträglich.

Beweis[Bearbeiten]

Es seien die Vektornorm und die induzierte Matrixnorm. Die Normeigenschaften der induzierten Matrixnorm sind leicht nachzuprüfen. Ihre Verträglichkeit mit der Vektornorm folgt aus

für . Weiter gilt für und mit

Im Fall und hat man sicher auch

Somit folgt auch die Submultiplikativität der induzierten Matrixnorm.

q.e.d.

2.2 Spezielle Matrixnormen[Bearbeiten]

Die wesentlichen Eigenschaften der durch Vektornormen induzierten Matrixnormen sind im Folgenden zusammengefasst.

Definition 2.10[Bearbeiten]

Für eine Matrix nennt man
das Spektrum und
den Spektralradius von .

Satz 2.11[Bearbeiten]

Sei . Für die durch eine Vektornorm induzierte Matrixnorm gilt
(2.4)

Beweis.[Bearbeiten]

Sei Eigenvektor zum Eigenwert einer Matrix , d. h.

Mit der zugehörigen Vektornorm gilt dann

Daraus folgt die Ungleichung (2.4).

q.e.d.

Der folgende Satz besagt, dass die durch die Vektornormen und induzierten Matrixnormen bzw. gerade die in Beispiel 2.6 eingeführte Zeilensummen- und Spaltensummennorm sind.

Satz 2.12[Bearbeiten]

Für und die durch die Vektornormen und induzierten Matrixnormen bzw. gilt
(Zeilensummennorm),
(Spaltensummennorm).

Beweis.[Bearbeiten]

Wir weisen zunächst die Behauptung für die Zeilensummennorm nach. Für gilt

und somit

woraus

folgt. Zum Beweis der umgekehrten Abschätzung sei beliebig, aber fest gewählt. Für mit

gilt dann . Somit hat man

(2.5)

Da beliebig gewählt war, folgt die behauptete Darstellung für .

Nun gilt weiter für

Zum Beweis der umgekehrten Aussage sei beliebig, aber fest gewählt. Mit dem Einheitsvektor erhält man dann

Damit folgt auch die behauptete Darstellung von .

q.e.d.

Im Folgenden beschränken wir uns auf den reellen Fall . Als unmittelbare Konsequenz aus Satz 2.12 erhält man

Korollar 2.13[Bearbeiten]

Für Matrizen gilt

Der nachstehende Satz liefert im Fall reeller Matrizen für die durch die Euklidische Vektornorm induzierte Matrixnorm eine spezielle Darstellung.

Satz 2.14[Bearbeiten]

Sei . Für die durch die Euklidische Vektornorm induzierte Matrixnorm gilt

Beweis.[Bearbeiten]

Es ist eine symmetrische und wegen

(2.6)

positiv semi-definite Matrix. Somit besitzt Eigenwerte und gibt es zu ein System von orthonormalen Eigenvektoren, d. h. es ist

und . Für gilt daher mit der Darstellung

Gleichheit wird in dieser Abschätzung für einen Eigenvektor zu einem maximalen Eigenwert von angenommen, denn

Damit ist alles bewiesen.

q.e.d.

Die Matrixnorm bezeichnet man auch als Spektralnorm. Dieser Name begründet sich durch den letzten Satz bzw. die in folgendem Satz angegebene Identität für reelle, symmetrische Matrizen.

Satz 2.15[Bearbeiten]

Sei eine symmetrische Matrix, d. h. . Dann gilt
(2.7)
Für jede andere durch eine Vektornorm induzierte Matrixnorm gilt
(2.8)

Beweis.[Bearbeiten]

Wegen gilt und daher aufgrund der Symmetrie von

Der zweite Teil der Behauptung folgt nun mit (2.4).

q.e.d.

Beispiel 2.16[Bearbeiten]

(1) Die symmetrische Matrix

besitzt die Eigenwerte , so dass folgt:

Weiter hat man . Damit zeigt dieses Beispiel, dass sich die in (2.3) stehenden Beziehungen nicht auf die entsprechenden induzierten Matrixnormen übertragen lassen.

(2) Für die nicht symmetrische Matrix , definiert durch

gilt offenbar und . Letzteres zeigt, dass auf die Voraussetzung „“ in Satz 2.15 nicht verzichtet werden kann.

Der folgende Satz liefert noch Abschätzungen für die Spektralnorm beliebiger quadratischer Matrizen.

Satz 2.17[Bearbeiten]

Für jede Matrix gilt
(2.9)
wobei die in Beispiel 2.6 (a) definierte Frobenius-Norm sei.

Beweis.[Bearbeiten]

Mit Satz 2.14 und Korollar 2.13 hat man

Die zweite Abschätzung in (2.9) erhält manmit der Cauchy-Schwarz-Ungleichung:

für alle .

q.e.d.

2.3 Die Konditionszahl einer Matrix[Bearbeiten]

Definition 2.18[Bearbeiten]

Sei eine reguläre Matrix und eine Matrixnorm. Die Zahl
heißt Kondition oder Konditionszahl der Matrix .

Man beachte, dass die Konditionszahl einer Matrix im Allgemeinen von der gewählten Matrixnorm abhängig ist. Es gilt:

Satz 2.19[Bearbeiten]

Sei eine reguläre Matrix und eine Vektornorm. Für die Kondition von gilt dann bezüglich der durch induzierten Matrixnorm
(2.10)

Beweis.[Bearbeiten]

Die Beziehung (2.10) ergibt sich aus

q.e.d.

Die Konditionszahl gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors bei Multiplikation mit ändern kann. Aus (2.10) ergibt sich zudem

2.4 Störungsresultate für Matrizen[Bearbeiten]

Lemma 2.20[Bearbeiten]

Sei eine durch eine Vektornorm induzierte Matrixnorm und eine Matrix mit . Dann ist die Matrix regulär, und es gilt

Beweis.[Bearbeiten]

Die umgekehrte Dreiecksungleichung liefert für

(2.11)

Also ist für auch , was die Invertierbarkeit von impliziert. Die Setzung in (2.11) liefert weiter

und damit

was den Beweis des Lemmas komplettiert.

q.e.d.

Korollar 2.21[Bearbeiten]

Sei die durch eine Vektornorm induzierte Matrixnorm und sei eine reguläre Matrix. Für jede Matrix mit ist dann die Matrix regulär, und es gelten die Abschätzungen
, falls .

Beweis.[Bearbeiten]

Es ist

und nach Lemma 2.20 somit die Matrix regulär. Mit der Darstellung erhält man ferner mit Lemma 2.20

Mit der Darstellung

und der ersten Ungleichung des Korollars folgt für

q.e.d.

2.5 Fehlerabschätzungen für gestörte Gleichungssysteme[Bearbeiten]

Wir beweisen nun als nächstes ein Resultat, welches den Einfluss einer Störung der rechten Seite eines Gleichungssystems auf seine Lösung zeigt.

Satz 2.22[Bearbeiten]

Mit seien gleichzeitig eine Vektornorm auf und die durch sie induzierte Matrixnorm auf bezeichnet. Weiter sei eine reguläre Matrix und und seien Vektoren mit
(2.12)
Dann gelten für den absoluten bzw. den relativen Fehler von bezüglich die Abschätzungen
(2.13)
(2.14)

Beweis.[Bearbeiten]

Aus (2.12) folgt unmittelbar bzw. und damit (2.13). Aus (2.13) wiederum ergibt sich

q.e.d.

Wenn die Kondition einer Matrix groß, also ist, ist auch die obere Schranke für den relativen Fehler in der Lösung der fehlerbehafteten Version des linearen Gleichungssystems groß. In einem solchen Fall spricht man von einem schlecht konditionierten Gleichungssystem. Wir geben ein Beispiel für eine Matrix mit großer Kondition.

Beispiel 2.23[Bearbeiten]

Sei sehr klein und gegeben durch

Dann ist und und somit die Kondition

sehr groß. Ein Gleichungssystem mit ist also ein schlecht konditioniertes Gleichungssystem.

Ähnliches gilt auch im Falle gestörter Matrizen.

Satz 2.24[Bearbeiten]

Mit seien gleichzeitig eine Vektornorm auf und die durch sie induzierte Matrixnorm auf bezeichnet. Weiter sei eine reguläre Matrix und sei eine Matrix mit . Dann gilt für beliebige Vektoren und mit
(2.15)
die Abschätzung
(2.16)

Beweis.[Bearbeiten]

Aus (2.15) folgt unmittelbar

Korollar 2.21 liefert nun die Regularität der Matrix sowie die Abschätzung

Division durch und Erweiterung der rechten Seite mit liefert

Wegen folgt die Behauptung.

q.e.d.

Der Nenner in der Konstanten auf der rechten Seite in (2.16) wird manchmal auch in der Form geschrieben.