Themen: Grundlagen Gleitpunktzahlen und Maschinengenauigkeitdobro/num1/f1.pdf · i ∈ {0,1,...,9}, (= t gültige Stellen) Grundlagen Gleitpunktarithmetik

Grundlagen

GleitpunktarithmetikundRundungsfehlerEin Beispiel

Vektor- undMatrizennormenStabilität linearerGleichungssysteme

Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination

Die Cholesky-Zerlegung

Das Householder-Verfahren

WelchesVerfahren istvorzuziehen?

1 Grundlagen

Themen:

◮ Gleitpunktzahlen und Maschinengenauigkeit

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1 Grundlagen

Themen:


◮ Vektor- und Matrizennormen

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1 Grundlagen

Themen:


◮ Vektor- und Matrizennormen

◮ Stabilität linearer Gleichungssysteme

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1.1 Gleitpunktarithmetik und Rundungsfehler

Eine Gleitpunktzahl, auch Gleitkommazahl genannt, imDezimalsystem ist von der Form

x = 0.d1d2 . . . dt×10k , di ∈ {0, 1, . . . , 9}, (= t gültige Stellen)

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







mitd1 6= 0 für x 6= 0 und − m ≤ k ≤ m.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







mitd1 6= 0 für x 6= 0 und − m ≤ k ≤ m.

Es gibt also nur endlich viele Gleitpunktzahlen!

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







mitd1 6= 0 für x 6= 0 und − m ≤ k ≤ m.

Es gibt also nur endlich viele Gleitpunktzahlen!

Setze m = ∞ voraus.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Maschinengenauigkeit

Es seiM = Menge der Gleitpunktzahlen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Die Maschinengenauigkeit eps ist die kleinste positive Zahl inM mit

1.+ eps > 1. == true.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







1.+ eps > 1. == true.

In die Maschinengenauigkeit geht ein:

◮ Zahl t der gültigen Stellen

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







1.+ eps > 1. == true.



◮ Art der Rundung (normales Auf- und Abrunden bzw.Abschneiden)

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







1.+ eps > 1. == true.




Beides hängt von der Programmiersprache und/oder demRechner ab.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







1.+ eps > 1. == true.




Beides hängt von der Programmiersprache und/oder demRechner ab.

Vorsicht: Das Rechenwerk arbeitet i.a. genauer.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Feststellung von eps

program

eps=1

1 eps=0.99*eps

if(masch(1.+eps)==1) goto 1

write eps

end

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





program

eps=1

1 eps=0.99*eps


write eps

end

Das aufgerufene Funktionsunterprogramm ist

function masch(q)

masch=0

if(q>1.) masch=1

end

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





program

eps=1

1 eps=0.99*eps


write eps

end

Das aufgerufene Funktionsunterprogramm ist

function masch(q)

masch=0

if(q>1.) masch=1

end

Durch den Aufruf von masch muss 1.+q das Rechenwerkverlassen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Resultate für den fortran90 ifort-Compiler

Bytelänge eps

4 0.6 · 10−7

8 1.0 · 10−16

16 1.0 · 10−34

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Bytelänge eps

4 0.6 · 10−7

8 1.0 · 10−16

16 1.0 · 10−34

Diese Werte stimmen genau mit der üblichen Belegung derSpeicherplätze überein, wonach ein Byte für den Exponentenund die übrigen Bytes für die Mantisse verwendet wird.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Bytelänge eps

4 0.6 · 10−7

8 1.0 · 10−16

16 1.0 · 10−34

Diese Werte stimmen genau mit der üblichen Belegung derSpeicherplätze überein, wonach ein Byte für den Exponentenund die übrigen Bytes für die Mantisse verwendet wird.

Für die Numerik sollte man 8 Bytes verwenden, wasmanchmal als double precision bezeichnet wird.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Rundungsfehler

Es gibt eine Abbildung rd : R→ M mit

rd (x) = x(1 + ε) mit |ε| ≤ eps.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Rundungsfehler

Es gibt eine Abbildung rd : R→ M mit

rd (x) = x(1 + ε) mit |ε| ≤ eps.

Nach dem oben Gesagten sind Rundungsfehler relativeFehler, was in diesem Modell berücksichtigt wird.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Gleitpunktoperationen

Die Gleitpunktoperationen ◦∗ : M × M → M sind danndefiniert durch

x ±∗ y = rd (x ± y), x ·∗ y = rd (x · y), x/∗y = rd (x

y).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Gleitpunktoperationen

Die Gleitpunktoperationen ◦∗ : M × M → M sind danndefiniert durch

x ±∗ y = rd (x ± y), x ·∗ y = rd (x · y), x/∗y = rd (x

y).

Im Einklang mit dem oben Angeführten wird alsoangenommen, dass in M exakt gerechnet und anschließendgerundet wird.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Eigenschaften der Gleitpunktoperationen

Die Gleitpunktoperationen sind weder assoziativ nochdistributiv.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Beispiel Wir betrachten die Addition +∗ bei t = 1 undnormaler Auf- und Abrundung:

(0.8 +∗ 0.6) +∗ 0.3 = 0.1 × 101

0.8 +∗ (0.6 +∗ 0.3) = 0.2 × 101

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Beispiel Wir betrachten die Addition +∗ bei t = 1 undnormaler Auf- und Abrundung:

(0.8 +∗ 0.6) +∗ 0.3 = 0.1 × 101

0.8 +∗ (0.6 +∗ 0.3) = 0.2 × 101

Rechenzeiten: Was ist schneller für eine Gleitpunktzahl a

0.5 ∗ a, a ∗ 0.5, a/2, a/2. ?

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Numerische Stabilität

Die Funktion f : Rn → R sei stetig differenzierbar. DieAuswertung von f heißt numerisch stabil, wenn es eineKonstante K gibt mit

∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣≤ K

|∆x ||x |

für alle ∆x ∈ Rn mit ∆x genügend klein.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣≤ K

|∆x ||x |


|x | =√

x21+ . . .+ x2

n ist hier die euklidische Norm des

Vektors x (siehe später).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣≤ K

|∆x ||x |


|x | =√

x21+ . . .+ x2

n ist hier die euklidische Norm des

Vektors x (siehe später).

In der Regel hängt die Konstante K auch von x selber ab.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Anschaulich bedeutet die numerische Stabilität, dass dieRundungsfehler bei der Auswertung von f nur kontrolliertverstärkt werden: Die Konditionszahl K sollte möglichst kleinsein.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Anschaulich bedeutet die numerische Stabilität, dass dieRundungsfehler bei der Auswertung von f nur kontrolliertverstärkt werden: Die Konditionszahl K sollte möglichst kleinsein.

Da Rundungsfehler relative Fehler sind, müssen auch in derDefiniton der numerischen Stabilität relative Fehler stehen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel

Für die Addition f (x1, x2) = x1 + x2 erhalten wir

∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤ ?

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel


∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤ ?

Es gilt

|∆x1 +∆x2| ≤√

2(∆x2

1 +∆x2

2 )1/2 =

√2|∆x |

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel


∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤ ?

Es gilt

|∆x1 +∆x2| ≤√

2(∆x2

1 +∆x2

2 )1/2 =

√2|∆x |

und(x2

1 + x2

2 )1/2 ≤ |x1|+ |x2|,

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel

Falls x1, x2 > 0

∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤

√2|∆x ||x | .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel

Falls x1, x2 > 0

∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤

√2|∆x ||x | .

Die Addition zweier positiver Zahlen ist also numerisch stabilund die Subtraktion zweier ungefähr gleich großer Zahlen istinstabil.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel

Falls x1, x2 > 0

∣

∣

∣

f (x)− f (x +∆x)

f (x)

∣

∣

∣=

∣

∣

∣

∆x1 +∆x2

x1 + x2

∣

∣

∣≤

√2|∆x ||x | .

Die Addition zweier positiver Zahlen ist also numerisch stabilund die Subtraktion zweier ungefähr gleich großer Zahlen istinstabil.

Auf die gleiche Weise leitet man her, dass Multiplikation undDivision numerisch stabile Operationen sind.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die Differenz als Bösewicht

Die Subtraktion zweier ungefähr gleich großer Zahlen istinstabil.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Vorkommen:

◮ Auswertung eines Polynoms in der Nähe einer Nullstelle

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Vorkommen:

◮ Auswertung eines Polynoms in der Nähe einer Nullstelle

◮ Bestimmung des Skalarprodukts zweier fast orthogonalerVektoren

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Fazit

◮ Akkumulation von Rundungsfehlern bei der Additionnichtnegativer Zahlen verläuft linear in der Anzahl derSummanden

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Fazit


◮ Sie kann durch die Verwendung einer höherenGenauigkeit ausgeglichen werden

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Fazit


◮ Sie kann durch die Verwendung einer höherenGenauigkeit ausgeglichen werden

Dagegen: Numerische Instabilität aufgrund Auslöschung kannnur durch modifizierte Algorithmen behoben werden.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1.2 Ein Beispiel

Für die reellen Zahlen p, q > 0 mit p >> q > 0 soll derAusdruck

y = −p +√

p2 + q

in Gleitkommaarithmetik näherungsweise bestimmt werden.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1.2 Ein Beispiel

Für die reellen Zahlen p, q > 0 mit p >> q > 0 soll derAusdruck

y = −p +√

p2 + q

in Gleitkommaarithmetik näherungsweise bestimmt werden.

y ist die kleinere der beiden Nullstellen von

y2 + 2py − q = 0.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 1

Das Standardverfahren zur Bestimmung von y ist sicherlichdie direkte Auswertung der obigen Formel

t = p2 + q

u =√

t

y = −p + u

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 1

Das Standardverfahren zur Bestimmung von y ist sicherlichdie direkte Auswertung der obigen Formel

t = p2 + q

u =√

t

y = −p + u

Unter der Voraussetzung p >> q > 0 ist p ∼ u, derAlgorithmus daher instabil.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 2

t = p2 + q

u =√

t

v = p + u

y = q/v

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 2

t = p2 + q

u =√

t

v = p + u

y = q/v

Liefert das gleiche wegen

y =q

p +√

p2 + q

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 2

t = p2 + q

u =√

t

v = p + u

y = q/v

Liefert das gleiche wegen

y =q

p +√

p2 + q=

q

p +√

p2 + q· p −

√

p2 + q

p −√

p2 + q

=q(p −

√

p2 + q)

p2 − (p2 + q)= −p +

√

p2 + q

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Algorithmus 2 ist numerisch stabil

In v = p + u haben wir nun zwei positive Zahlen addiert.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Die Auswertung der Wurzel ist ebenfalls numerisch stabil.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Die Auswertung der Wurzel ist ebenfalls numerisch stabil.

In der Tat erhalten wir bei zwölfstelliger Rechnung für

p = 1000, q = 0.018 000 000 081

die Ergebnisse

Alg. 1 : 0.900 030 . . .× 10−5

Alg. 2 : 0.899 999 999 999 999 × 10−5,

der exakte Wert ist 0.9 × 10−5.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1.3 Vektor- und Matrizennormen

Sei X ein nicht notwendig endlich dimensionaler linearerVektorraum über K = R oder K = C.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Eine Abbildung ‖ · ‖ : X → R heißt Norm, wenn sie denfolgenden Bedingungen genügt:

(i) ‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







(i) ‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0

(ii) ‖αx‖ = |α| ‖x‖ für alle α ∈ K und x ∈ X .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







(i) ‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0

(ii) ‖αx‖ = |α| ‖x‖ für alle α ∈ K und x ∈ X .

(iii) ‖x + y‖ ≤ ‖x‖+ ‖y‖.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Diskussion der Norm

Anschaulich können wir uns vorstellen, dass die Norm von xdie Länge des Vektors x angibt oder, falls wir x als Punktansehen, die Entfernung dieses Punktes zum Nullpunkt. Indieser Interpretation sind alle Axiome sinnvoll:

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Diskussion der Norm


‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0

Abstände sind positiv, sofern es sich nicht um den Nullvektorhandelt.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Diskussion der Norm


‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0


‖αx‖ = |α| ‖x‖ für alle α ∈ K und x ∈ X .

Die Länge eines Vielfachen ist das Vielfache der Länge.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Diskussion der Norm


‖x‖ ≥ 0 und ‖x‖ = 0 ⇔ x = 0


‖αx‖ = |α| ‖x‖ für alle α ∈ K und x ∈ X .

Die Länge eines Vielfachen ist das Vielfache der Länge.

‖x + y‖ ≤ ‖x‖+ ‖y‖.Die Strecke ist die kürzeste Verbindung zweier Punkte.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Skalarprodukt und euklidische Norm

Für x , y ∈ Cn ist das Skalarprodukt definiert durch

(x , y) =n

∑

j=1

xjy j .

Die euklidische Norm ist für Vektoren x ∈ Cn (oder x ∈ Rn)definiert durch

|x | =(

n∑

j=1

|xj |2)1/2

= (x , x)1/2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Euklidische Norm

|x | =(

n∑

j=1

|xj |2)1/2

= (x , x)1/2.

Aufgrund des Satzes von Pythagoras handelt es sich hierbeiin der Tat um die Entfernung des Punktes x zum Nullpunkt.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Euklidische Norm

|x | =(

n∑

j=1

|xj |2)1/2

= (x , x)1/2.

Aufgrund des Satzes von Pythagoras handelt es sich hierbeiin der Tat um die Entfernung des Punktes x zum Nullpunkt.

Die Normaxiome (i) und (ii) sind klar, für dieDreiecksungleichung benötigen wir ein Hilfsmittel:

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die Cauchy-Ungleichung

Lemma Für x , y ∈ Cn gilt

|(x , y)| ≤ |x | |y |.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die Cauchy-Ungleichung

Lemma Für x , y ∈ Cn gilt

|(x , y)| ≤ |x | |y |.

Beweis Für a, b ≥ 0 gilt die Youngsche Ungleichung

ab ≤ 1

2a2 +

1

2b2,

die man aus der binomischen Formel beweist.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis der Cauchy-Ungleichung

Mit der Youngschen Ungleichung erhalten wir

|(x , y)| =∣

∣

∣

n∑

j=1

xjy j

∣

∣

∣≤

n∑

j=1

(1

2|xj |2 +

1

2|yj |2

)

≤ 1

2|x |2 + 1

2|y |2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






|(x , y)| =∣

∣

∣

n∑

j=1

xjy j

∣

∣

∣≤

n∑

j=1

(1

2|xj |2 +

1

2|yj |2

)

≤ 1

2|x |2 + 1

2|y |2.

Für |x | = |y | = 1 ist die Ungleichung damit bewiesen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






|(x , y)| =∣

∣

∣

n∑

j=1

xjy j

∣

∣

∣≤

n∑

j=1

(1

2|xj |2 +

1

2|yj |2

)

≤ 1

2|x |2 + 1

2|y |2.


Für x , y 6= 0 schreibe wieder

x = αx , y = βy mit |x | = |y | = 1

und erhalte die Cauchy-Ungleichung.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






|(x , y)| =∣

∣

∣

n∑

j=1

xjy j

∣

∣

∣≤

n∑

j=1

(1

2|xj |2 +

1

2|yj |2

)

≤ 1

2|x |2 + 1

2|y |2.


Für x , y 6= 0 schreibe wieder

x = αx , y = βy mit |x | = |y | = 1

und erhalte die Cauchy-Ungleichung.

Beachte das Homogenitätsargument!

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Nun zum Beweis der Dreicksungleichung für die EuklidischeNorm:

|x + y |2 = (x + y , x + y) = |x |2 + 2(x , y) + |y |2

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Nun zum Beweis der Dreicksungleichung für die EuklidischeNorm:

|x + y |2 = (x + y , x + y) = |x |2 + 2(x , y) + |y |2

≤ |x |2 + 2|x | |y |+ |y |2 = (|x |+ |y |)2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Frobenius-Norm

Für die euklidische Matrixnorm, auch Frobenius-Normgenannt, schreiben wir entsprechend

|A| =(

m∑

j=1

n∑

k=1

|ajk |2)1/2

, A ∈ Cm×n oder A ∈ Rm×n.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Transponierte und adjungierte Matrix

Für Matrizen A ∈ Cm×n, A = (ajk)j=1,...,m, k=1,...,n setze

AT = (akj)k=1,...,n, j=1,...,m = transponierte Matrix

AH = (akj)k=1,...,n, j=1,...,m = adjungierte Matrix

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Transponierte und adjungierte Matrix

Für Matrizen A ∈ Cm×n, A = (ajk)j=1,...,m, k=1,...,n setze

AT = (akj)k=1,...,n, j=1,...,m = transponierte Matrix

AH = (akj)k=1,...,n, j=1,...,m = adjungierte Matrix

Beispiel

A =

(

1 1 + 2i1 + 3i 2

)

,

AT =

(

1 1 + 3i1 + 2i 2

)

, AH =

(

1 1 − 3i1 − 2i 2

)

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Notation

Ist A ∈ Cn×n regulär, so gilt

(AH)−1 = (A−1)H .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Notation


(AH)−1 = (A−1)H .

Aus AA−1 = I folgt, dass

(A−1)HAH = IH = I .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Notation


(AH)−1 = (A−1)H .

Aus AA−1 = I folgt, dass

(A−1)HAH = IH = I .

Damit ist die Inverse von AH gerade die Matrix (A−1)H .Diese Beziehung rechtfertigt die Schreibweise

A−H = (A−1)H sowie A−T = (A−1)T .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Alternative Definition

Mit dem euklidischen Skalarprodukt (·, ·) gilt

(Ax , y) = (x ,AT y) ∀x , y ∈ Cn, A reell

(Ax , y) = (x ,AHy) ∀x , y ∈ Cn.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Alternative Definition

Mit dem euklidischen Skalarprodukt (·, ·) gilt

(Ax , y) = (x ,AT y) ∀x , y ∈ Cn, A reell

(Ax , y) = (x ,AHy) ∀x , y ∈ Cn.

Rechenregeln:

(AB)H = BHAH , insbesondere (AHA)H = AHA.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Skalarprodukt

Vektoren werden auch als Spaltenmatrizen aufgefasst, daher:

yHxZeile mal Spalte

=n

∑

j=1

y jxj = (x , y).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Symmetrische und hermitesche Matrizen

A ∈ Rn×n heißt symmetrisch, wenn A = AT .

A ∈ Cn×n heißt hermitesch, wenn A = AH .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Symmetrische und hermitesche Matrizen

A ∈ Rn×n heißt symmetrisch, wenn A = AT .

A ∈ Cn×n heißt hermitesch, wenn A = AH .

Bei hermiteschen Matrizen ist die zugehörige quadratischeForm reellwertig

q(x) := (Ax , x) = (x ,AHx) = (x ,Ax) = (Ax , x) ⇒ q(x) ∈ R.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Äquivalenz der Normen im Endlichdimensionalen

Satz Auf endlich dimensionalen Räumen sind alle Normenäquivalent, d.h. zu zwei Normen ‖ · ‖1 und ‖ · ‖2 auf einemendlich dimensionalen Raum V gibt es Konstanten m,M > 0mit

m‖x‖2 ≤ ‖x‖1 ≤ M‖x‖2 für alle x ∈ V .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






m‖x‖2 ≤ ‖x‖1 ≤ M‖x‖2 für alle x ∈ V .

Anwendung In der numerischen Mathematik werden eineVielzahl von Matrixnormen verwendet, die demnach alleäquivalent sind.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






m‖x‖2 ≤ ‖x‖1 ≤ M‖x‖2 für alle x ∈ V .

Anwendung In der numerischen Mathematik werden eineVielzahl von Matrixnormen verwendet, die demnach alleäquivalent sind.

Aber die Konstanten c1, c2 hängen in der Regel von derRaumdimension ab.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Inverse Dreiecksungleichung

Lemma Für jede Norm gilt die inverse Dreiecksungleichung

‖x − y‖ ≥∣

∣ ‖x‖ − ‖y‖∣

∣ für alle x , y ∈ V .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






‖x − y‖ ≥∣

∣ ‖x‖ − ‖y‖∣


Beweis Mit der normalen Dreiecksungleichung folgt

‖x‖ = ‖(x − y) + y‖ ≤ ‖x − y‖+ ‖y‖,

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






‖x − y‖ ≥∣

∣ ‖x‖ − ‖y‖∣


Beweis Mit der normalen Dreiecksungleichung folgt

‖x‖ = ‖(x − y) + y‖ ≤ ‖x − y‖+ ‖y‖,

also‖x − y‖ ≥ ‖x‖ − ‖y‖.

Vertauschen wir hier die Rollen von x und y , so ist dasLemma bewiesen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis des letzten Satzes

Es genügt, den Fall V = Cn (oder V = Rn) zu betrachten.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Jede Norm ‖ · ‖ : Cn → R, x 7→ ‖x‖ ist stetig, denn wennxk → x , so folgt aus dem letzten Lemma

∣

∣ ‖xk‖ − ‖x‖∣

∣ ≤ ‖xk − x‖ → 0.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Jede Norm ‖ · ‖ : Cn → R, x 7→ ‖x‖ ist stetig, denn wennxk → x , so folgt aus dem letzten Lemma

∣

∣ ‖xk‖ − ‖x‖∣

∣ ≤ ‖xk − x‖ → 0.

Die Einheitssphäre

S = {x ∈ Cn : |x | = 1}

ist kompakt.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Da die Normen ‖ · ‖j stetig sind, nehmen sie ihr Minimumund Maximum auf S an, also

mj ≤ ‖x‖j ≤ Mj für alle x mit |x | = 1.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Da die Normen ‖ · ‖j stetig sind, nehmen sie ihr Minimumund Maximum auf S an, also

mj ≤ ‖x‖j ≤ Mj für alle x mit |x | = 1.

Wegen 0 /∈ S , sind die mj > 0. Mit x = αx , |x | = 1, folgthieraus

mj |x | ≤ ‖x‖j ≤ Mj |x | ∀x ∈ Cn.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Nutzen der Homogenität

Die Ungleichungen

mj |x | ≤ ‖x‖j ≤ Mj |x | ∀x ∈ Cn.

sind homogen in x , d.h. sind sie für ein x erfüllt, so auch füralle αx mit α ∈ C.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Nutzen der Homogenität

Die Ungleichungen

mj |x | ≤ ‖x‖j ≤ Mj |x | ∀x ∈ Cn.

sind homogen in x , d.h. sind sie für ein x erfüllt, so auch füralle αx mit α ∈ C.

Es genügt also, die Ungleichung für alle x mit |x | = 1 zubeweisen (=Homogenitätsargument).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die p-Normen

Die p-Normen auf Cn (oder Rn) sind definiert durch

‖x‖p =(

n∑

j=1

|xj |p)1/p

, 1 ≤ p < ∞,

‖x‖∞ = max1≤j≤n

|xj |.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die p-Normen

Die p-Normen auf Cn (oder Rn) sind definiert durch

‖x‖p =(

n∑

j=1

|xj |p)1/p

, 1 ≤ p < ∞,

‖x‖∞ = max1≤j≤n

|xj |.

Für die Numerik wichtig sind die Normen

‖x‖1 =∑

j

|xj |, ‖x‖2 = |x |, ‖x‖∞ = max(|x1|, . . . , |xn|).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Die induzierte Matrixnorm

Sei ‖ · ‖1 eine Norm auf dem Cn und ‖ · ‖2 eine Norm aufdem Cm.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Der Ausdruck

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

, A ∈ Cm×n,

ist eine Norm auf dem Matrizenraum Cm×n.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Der Ausdruck

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

, A ∈ Cm×n,


‖A‖1→2 heißt (von ‖ · ‖1‖ und ‖ · ‖2) induzierte Matrixnorm.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






Der Ausdruck

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

, A ∈ Cm×n,


‖A‖1→2 heißt (von ‖ · ‖1‖ und ‖ · ‖2) induzierte Matrixnorm.

Die induzierte Matrixnorm auf dem Rm×n ist analog definiert.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Zwei wichtige Tatsachen

Offenbar gilt

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

= sup‖x‖1=1

‖Ax‖2.

Homogenitätsargument!

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Offenbar gilt

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

= sup‖x‖1=1

‖Ax‖2.


Die Menge {x : ‖x‖1 = 1} ist kompakt, so dass die stetigeFunktion x 7→ ‖Ax‖2 das Maximum annimmt.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Offenbar gilt

‖A‖1→2 = supx∈Cn\{0}

‖Ax‖2

‖x‖1

= sup‖x‖1=1

‖Ax‖2.


Die Menge {x : ‖x‖1 = 1} ist kompakt, so dass die stetigeFunktion x 7→ ‖Ax‖2 das Maximum annimmt.

Wir können daher auch gleich

‖A‖1→2 = maxx∈Cn\{0}

‖Ax‖2

‖x‖1

schreiben.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis der Normeigenschaft

Aufgrund der letzten Darstellung existiert ‖A‖1→2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






‖A‖1→2 = 0 gilt genau dann, wenn Ax = 0 für alle x , alsoA = 0.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination






‖A‖1→2 = 0 gilt genau dann, wenn Ax = 0 für alle x , alsoA = 0.

Die positive Homogenität folgt aus der positivenHomogenität von ‖ · ‖2

‖αA‖1→2 = sup‖x‖1=1

‖αAx‖2 = |α| sup‖x‖1=1

‖Ax‖2 = |α| ‖A‖1→2,

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis der Dreiecksungleichung

Die Dreiecksungleichung folgt analog aus derDreiecksungleichung für ‖‖2

‖A + B‖1→2 = sup‖x‖1=1

‖Ax + Bx‖2

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis der Dreiecksungleichung

Die Dreiecksungleichung folgt analog aus derDreiecksungleichung für ‖‖2

‖A + B‖1→2 = sup‖x‖1=1

‖Ax + Bx‖2

≤ sup‖x‖1=1

‖Ax‖2 + sup‖x‖1=1

‖Bx‖2

= ‖A‖1→2 + ‖B‖1→2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Verträglichkeit

Sei ‖ · ‖M eine Matrixnorm auf Cn×n und ‖ · ‖V eineVektornorm auf Cn.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Verträglichkeit

Sei ‖ · ‖M eine Matrixnorm auf Cn×n und ‖ · ‖V eineVektornorm auf Cn.

‖ · ‖M heißt verträglich mit ‖ · ‖V , wenn

‖Ax‖V ≤ ‖A‖M‖x‖V ∀A ∈ Cn×n ∀x ∈ Cn.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1

Euklidische Normen sind verträglich,

|Ax | ≤ |A| |x |

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1


|Ax | ≤ |A| |x |

was man mit Hilfe der Cauchy-Ungleichung beweist,

|Ax |2 =∑

j

∣

∣

∣

∑

k

ajkxk

∣

∣

∣

2

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1


|Ax | ≤ |A| |x |

was man mit Hilfe der Cauchy-Ungleichung beweist,

|Ax |2 =∑

j

∣

∣

∣

∑

k

ajkxk

∣

∣

∣

2

≤∑

j

(

∑

k

|ajk |2 ×∑

k

|xk |2)

=∑

j ,k

|ajk |2∑

k

|xk |2 = |Ax |2|x |2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 2

Die von einer Vektornorm ‖ · ‖V induzierte Matrixnorm‖ · ‖V→V ist mit dieser Vektornorm verträglich

‖Ax‖V ≤ ‖A‖V→V ‖x‖V .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 2

Die von einer Vektornorm ‖ · ‖V induzierte Matrixnorm‖ · ‖V→V ist mit dieser Vektornorm verträglich

‖Ax‖V ≤ ‖A‖V→V ‖x‖V .

Dies folgt aus der Definition der induzierten Norm: ‖A‖V→V

ist nämlich die kleinste Konstante c, so dass

‖Ax‖V ≤ c‖x‖V

für alle x richtig ist.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Submultiplikativität

Sei ‖ · ‖M eine Matrixnorm auf Cn×n.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Submultiplikativität

Sei ‖ · ‖M eine Matrixnorm auf Cn×n.

‖ · ‖M heißt submultiplikativ, wenn

‖AB‖M ≤ ‖A‖M‖B‖M ∀A,B ∈ Cn×n.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1

Euklidische Normen sind submultiplikativ

|AB| ≤ |A| |B |

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1


|AB| ≤ |A| |B |

wegen

|AB|2 =∑

j ,l

∣

∣

∣

∑

k

ajkbkl

∣

∣

∣

2

≤∑

j ,l

(

∑

k

|ajk |2 ×∑

k

|bkl |2))

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 1


|AB| ≤ |A| |B |

wegen

|AB|2 =∑

j ,l

∣

∣

∣

∑

k

ajkbkl

∣

∣

∣

2

≤∑

j ,l

(

∑

k

|ajk |2 ×∑

k

|bkl |2))

= |A|2|B |2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 2

Die von einer Vektornorm ‖ · ‖V induzierte Matrixnorm‖ · ‖V→V ist auch submultiplikativ wegen der Verträglichkeit

‖AB‖V→V = sup‖x‖V=1

‖ABx‖V ≤ sup‖x‖V=1

‖A‖V→V ‖Bx‖V

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beispiel 2

Die von einer Vektornorm ‖ · ‖V induzierte Matrixnorm‖ · ‖V→V ist auch submultiplikativ wegen der Verträglichkeit

‖AB‖V→V = sup‖x‖V=1

‖ABx‖V ≤ sup‖x‖V=1

‖A‖V→V ‖Bx‖V

≤ sup‖x‖V=1

‖A‖V→V ‖B‖V→V ‖x‖V

= ‖A‖V→V ‖B‖V→V

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Notation

Sei A ∈ Cm×n. Wenn nichts anderes gesagt wird, ist

‖A‖ = supx 6=0

|Ax ||x | .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Notation

Sei A ∈ Cm×n. Wenn nichts anderes gesagt wird, ist

‖A‖ = supx 6=0

|Ax ||x | .

d.h. ‖ · ‖ ohne irgendwelche Indizes ist immer die von deneuklidischen Normen induzierte Matrixnorm.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Charakterisierung von ‖ · ‖

Lemma Für A ∈ Cn×n gilt

‖A‖ = ρ(AAH)1/2 = ρ(AHA)1/2,

wobei ρ(B) den betragsmäßig größten Eigenwert von Bbezeichnet.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Charakterisierung von ‖ · ‖

Lemma Für A ∈ Cn×n gilt

‖A‖ = ρ(AAH)1/2 = ρ(AHA)1/2,

wobei ρ(B) den betragsmäßig größten Eigenwert von Bbezeichnet.

Ist A ∈ Cn×n hermitesch, so gilt

‖A‖ = ρ(A).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Es gilt

‖A‖2 = supx 6=0

(Ax ,Ax)

(x , x)= sup

x 6=0

(AHAx , x)

(x , x).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Es gilt

‖A‖2 = supx 6=0

(Ax ,Ax)

(x , x)= sup

x 6=0

(AHAx , x)

(x , x).

Wegen (AHA)H = AHA ist AHA hermitesch und wegen

(AHAx , x) = (Ax ,Ax) = |Ax |2 ≥ 0

ist AHA positiv semidefinit.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Es gilt

‖A‖2 = supx 6=0

(Ax ,Ax)

(x , x)= sup

x 6=0

(AHAx , x)

(x , x).

Wegen (AHA)H = AHA ist AHA hermitesch und wegen

(AHAx , x) = (Ax ,Ax) = |Ax |2 ≥ 0

ist AHA positiv semidefinit.

Sie besitzt daher einen vollständigen Satz von Eigenvektorenv1, . . . , vn mit

AHAvj = λjvj und λj nichtnegativ.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

In

‖A‖2 = supx 6=0

(AHAx , x)

(x , x).

setzen wir x =∑

j cjvj ein und erhalten wegen derOrthogonalität der vj

‖A‖2 = supc 6=0

(AHA∑

j cjvj ,∑

j cjvj)

(∑

j cjvj ,∑

j cjvj)= sup

c 6=0

∑

j λj |cj |2∑

j |cj |2.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

In

‖A‖2 = supx 6=0

(AHAx , x)

(x , x).

setzen wir x =∑

j cjvj ein und erhalten wegen derOrthogonalität der vj

‖A‖2 = supc 6=0

(AHA∑

j cjvj ,∑

j cjvj)

(∑

j cjvj ,∑

j cjvj)= sup

c 6=0

∑

j λj |cj |2∑

j |cj |2.

Dieses Optimierungsproblem wird natürlich durch cn = 1,cj = 0 für 1 ≤ j ≤ n − 1 gelöst, wenn λn der größteEigenwert von AHA ist.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Ist A hermitesch, so erhalten wir die Eigenwerte undEigenvektoren von AHA = A2 aus den Eigenwerten undEigenvektoren von A:

Av = λv ⇒ AHAv = A2v = λ2v .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Weitere Beispiele von Matrizennormen

Auf dem Cm×n sind

(i) ‖A‖Z = maxj

∑nk=1

|ajk | (=Zeilensummennorm),

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Auf dem Cm×n sind

(i) ‖A‖Z = maxj

∑nk=1


(ii) ‖A‖S = maxk

∑mj=1

|ajk | (=Spaltensummennorm),

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Auf dem Cm×n sind

(i) ‖A‖Z = maxj

∑nk=1



∑mj=1


(iii) ‖A‖∞ = maxj ,k |ajk |.ebenfalls Matrizennormen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination





Auf dem Cm×n sind

(i) ‖A‖Z = maxj

∑nk=1



∑mj=1


(iii) ‖A‖∞ = maxj ,k |ajk |.ebenfalls Matrizennormen.

(i) und (ii) sind submultiplikativ.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




‖A‖∞

ist nicht submultiplikativ wegen

(

1 11 1

)(

1 11 1

)

=

(

2 22 2

)

.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




1.4 Stabilität linearer Gleichungssysteme

Sei A ∈ Cn×n (oder A ∈ Rn×n). Wir wollen das lineareGleichungssystem

Ax = b für b ∈ Cn

lösen.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







lösen.

Satz Sei A regulär. Dann gilt für die Lösung x +∆x desgestörten Problems

A(x +∆x) = b +∆b

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination







lösen.

Satz Sei A regulär. Dann gilt für die Lösung x +∆x desgestörten Problems

A(x +∆x) = b +∆b

die Abschätzung

|∆x ||x | ≤ ‖A‖ ‖A−1‖|∆b|

|b| .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Konditionszahl

Die Zahlcond (A) = ‖A‖ ‖A−1‖

gibt die Verstärkung des relativen Fehlers bei ungenauerAuswertung der rechten Seite an und heißt deshalbKonditionszahl der Matrix A.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Aus A∆x = ∆b folgt

∆x = A−1∆b ⇒ |∆x | ≤ ‖A−1‖ |∆b|.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Beweis

Aus A∆x = ∆b folgt

∆x = A−1∆b ⇒ |∆x | ≤ ‖A−1‖ |∆b|.

Aus Ax = b erhalten wir entsprechend die Abschätzung|b| ≤ ‖A‖ |x | und damit die Behauptung.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Anwendung

Bei iterativen Verfahren zur Lösung von Ax = b erhalten wirNäherungen x , aber kennen den Fehler |x − x | nicht. Wannsollen wir abbrechen?

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Anwendung


Bestimme das Residuums r = b − Ax = A(x − x).

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Anwendung



x ist dann die exakte Lösung von Ax = b − r und für denrelativen Fehler gilt dann

|x − x ||x | ≤ cond (A)

|r ||b| .

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Anwendung



x ist dann die exakte Lösung von Ax = b − r und für denrelativen Fehler gilt dann

|x − x ||x | ≤ cond (A)

|r ||b| .

Mit x sind r und b bekannt, die Kondition von A mussallerdings geschätzt werden.

Grundlagen



Direkte Lösung

linearer Glei-

chungssysteme

Gauß Elimination




Documents

Themen: Grundlagen Gleitpunktzahlen und Maschinengenauigkeitdobro/num1/f1.pdf · i ∈ {0,1,...,9}, (= t gültige Stellen) Grundlagen Gleitpunktarithmetik