Kurs:Numerik I/Störungsresultate für Matrizen

Aus testwiki
Zur Navigation springen Zur Suche springen

Störungsresultate für Matrizen

Wie das numerisches Problem auf Störungen in den Anfangsdaten reagiert, wird mit der Kondition gemessen. Hat ein Problem eine große Kondition, so hängt die Lösung des Problems empfindlich von den Anfangsdaten ab, d.h. bei leichten Veränderungen des Anfangszustand kann sich die Lösung des numerischen Verfahrens stark verändern. Dies hängt insbesondere mit Rundungsfehler zusammen, die als Störung der Anfangsdaten aufgefasst werden können.

Störung - absoluter Fehler

In der folgenden Formulierung wird die Störung als absoluter Fehler ΔA. In den Komponenten der Matrix steht der Wert für die Abweichung vom tatsächlichen Wert. Diese "Störungen" können in der Praxis durch externe Einflüsse entstehen, die dann die Messungenauigkeiten verschlechtern.

Beispiel

Stellen wir z.B. ein Bild als quadratische Pixelmatrix A, das von einem optischen Teleskop bei der Beobachtung von Sternen generiert wird. Die Lichtverschmutzung bei der Sternbeobachtung stört die Aufnahme von A um ΔA. Das resultierende Bild ist dann A+ΔA.

Aufgaben - Anwendungsbezug

  • Geben Sie weiter Anwendungsbespiele für störende Einflüsse, die Messungen verfälschen können (z.B. Verkehrsprognosen, Wettervorhersage, Klausurergebnisse, Börsenkurse,...)!
  • Betrachten Sie nun eine Übergangsmatrix A im Kontext von Markow-Ketten und erläutern Sie, wie relative Häufigkeiten mit dem Gesetz der großen Zahlen einen Näherungswert für eine theoretische Wahrscheinlichkeit darstellen. Welche Ähnlichkeiten und Unterschiede können Sie zwischen einem numerischen und statistischen Zugang erkennen?

Konditionszahl und invertierbar Matrizen

Für eine reguläre/invertierbare Matrix An×n mit einer Matrixnorm :n×n+ wird die Konditionszahl über

cond(A):=AA1

berechnet. Das folgende Lemma ist hilfreich, um für die Konditionszahl die Matrixnorm A1 mit A:=I+F nach oben abzuschätzen.


Lemma - Regularität und induzierte Matrixnorm

Sei :n×n0+ eine durch eine Norm auf n induzierte Matrixnorm und Fn×n eine Matrix mit F<1. Dann ist die Matrix I+F regulär, und es gilt

(I+F)111F.

Beweis - 1 - Regularität und induzierte Matrixnorm

Die umgekehrte Dreiecksungleichung liefert für xn

(I+F)x=x+Fx=x(Fx)umgek.ΔUnglxFx=FxxFx=(1F)x.

Also ist für x0v auch (I+F)x0v.

Beweis - 2 - Regularität und induzierte Matrixnorm

Wenn für alle x0v auch (I+F)=:Bx0v gilt, ist der Nullvektor 0v das einzige Element im Kern von B:=I+F. Damit die Invertierbarkeit von I+F impliziert.

Beweis - 2 - Regularität und induzierte Matrixnorm

Mit der Setzung y:=(I+F)x liefert die obige Ungleichung in Beweisschritt 1:

y(1F)(I+F)1y,yn

und damit

(I+F)1yy11F,yn,

was den Beweis des Lemmas durch Maximumsbildung in der Matrixnorm komplettiert.

q.e.d.

Störungen als Differenzmatrizen

Wenn man eine Matrix An×n gegeben hat und eine Störung als Veränderung ΔAn×n auffasst, ist es wesentlich die Konditionszahl cond(A+ΔA) der Matrix A+ΔA zu berechnen. Nach Definition der Konditionszahl cond(B):=BB1 muss man für B:=A+ΔA die induzierte Matrixnorm B1 abschätzen. Das folgende Korrolar liefert das als Resultat.

Korollar - Regularität und induzierte Matrixnorm

Sei :n×n+ die durch eine Vektornorm induzierte Matrixnorm und An×n sei eine reguläre Matrix. Für jede Matrix ΔAn×n mit ΔA<1A1 ist dann die Matrix A+ΔA regulär, und es gelten unter der Bedingung ΔA12A1 die Abschätzungen

(A+ΔA)1A11A1ΔA(A+ΔA)1A12A12ΔA

Beweis - 1 - Korollar

Mit der Submultiplikativität ABAB der induzierten Matrixnorm erhält man

A1ΔAA1ΔA<1

Dabei erhält man die Abschätzung nach oben gegen 1 unter der gegebenen Voraussetzung ΔA<1A1.

Beweis - 2 - Korollar

Nach Lemma über die Regularität ist somit die Matrix I+A1ΔA eine reguläre Matrix. Da nach Voraussetzung AGL(n,) ist auch das Produkt von regulären Matrizen A(I+A1ΔA)GL(n,) wieder regulär und man erhält:

A+ΔA=A(I+A1ΔA)GL(n,)

Beweis - 3 - Korollar

Mit (M1M2)1=M21M11 und der Darstellung aus dem vorherigen Schritt erhält man die folgende Darstellung:

(A+ΔA)1=(A(I+A1ΔA)1))1=(I+A1ΔA)1A1

Beweis - 4 - Korollar

Durch Anwendung des Lemmas über Regularität und induzierte Matrixnorm erhält man man nun die Abschätzung:

(A+ΔA)1A11A1ΔAA11A1ΔA.

Beweis - 5 - Korollar

Mit A1=(A+ΔA)1(A+ΔA)A1 erhält man die folgende Darstellung:

(A+ΔA)1A1=(A+ΔA)1(I(A+ΔA)A1)=(A+ΔA)1(IAA1=I+ΔAA1)=(A+ΔA)1ΔAA1

Beweis - 6 - Korollar

Zusammen mit der ersten Ungleichung des Korollars in Beweisschritt 3 folgt und der Verwendung der Submultiplikativität der Matrixnorm:

(A+ΔA)1A1(A+ΔA)1A1ΔAA11A1ΔA12A1ΔAA1112A1ΔA=2A12ΔA.

q.e.d.

Bemerkung zu Beweisschritt 6

In der zweiten Ungleichung liefert mit ΔA12A1 bzw. ΔAA112 im Nenner 1ΔAA1112>0 die Abschätzung nach oben.

Fehlerabschätzungen für gestörte Gleichungssysteme

Wir beweisen nun als nächstes ein Resultat, welches den Einfluss einer Störung der rechten Seite eines Gleichungssystems auf seine Lösung zeigt. Mit seien gleichzeitig eine Vektornorm auf n und die durch sie induzierte Matrixnorm auf n×n bezeichnet. Weiter sei AGL(n,)n×n eine reguläre Matrix.

Satz - Fehlerabschätzung gestörter Gleichungssysteme

Sei AGL(n,) und b,xn und Δb,Δxn seien Vektoren mit

(FG1) Ax=b,A(x+Δx)=b+Δb.

Dann gelten für den absoluten bzw. den relativen Fehler von x+Δx bezüglich x die Abschätzungen

(FG2) (x+Δx)x=ΔxA1Δb,
(FG3) (x+Δx)xx=Δxxcond(A)Δbb.

Beweis 1 - Fehlerabschätzung gestörter Gleichungssysteme

Aus (FG1) folgt unmittelbar über Multiplikation mit A1 die Aussage (FG2) mit Δb=0

AΔx=ΔbΔx=A1AΔx=A1ΔbΔx=A1Δb=A1ΔbΔbA1ΔbA1Δb

Beweis 2 - Fehlerabschätzung gestörter Gleichungssysteme

Δxx=(FG2)A1Δbxbb=Ax=bA1ΔbxAxbA1ΔbxAxb=A1AxxAΔbbcond(A)=A1AΔbb.

AΔx=Δb bzw. Δx=A1Δb líefert damit mit (FG2) die Behauptung (FG3). q.e.d.

Bemerkung

Wenn die Kondition einer Matrix A groß, also cond(A)1 ist, ist auch die obere Schranke für den relativen Fehler in der Lösung der fehlerbehafteten Version des linearen Gleichungssystems Ax=b 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 1a

Sei ε(0,1) sehr klein und A gegeben durch

A:=(100ε)A1=(1001/ε)

Beispiel 1b

Dann ist bei sehr kleinem ε die Matrixnorm von A21, von A121/ε und somit die Kondition

cond2(A):=A2A121ε

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

Ähnliches gilt auch im Falle gestörter Matrizen.

Satz - Fehlerabschätzung und Konditionszahl

Mit seien gleichzeitig eine Vektornorm auf n und die durch sie induzierte Matrixnorm auf n×n bezeichnet. Weiter sei An×n eine reguläre Matrix und ΔAn×n sei eine Matrix mit ΔA<1/A1. Dann gilt für beliebige Vektoren b,xn und Δb,Δxn mit

(FK1) Ax=b,(A+ΔA)(x+Δx)=b+Δb

die Abschätzung

(FK2) Δxxcond(A)1cond(A)ΔAA(ΔAA+Δbb).

Beweis 1 - Fehlerabschätzung und Konditionszahl

Aus (FK1) folgt mit AΔx=A(x~x)=Ax~Ax=b~b=Δb unmittelbar

(A+ΔA)Δx=AΔx+ΔAΔx=ΔbΔAx(A+ΔA)x=Ax+ΔAx

Insgesamt erhält man: (A+ΔA)(x+Δx)=b+Δb

Beweis 2 - Fehlerabschätzung und Konditionszahl

Korollar zur Regularität und Spektralnorm liefert nun die Invertierbarkeit der Matrix A+ΔA sowie die Abschätzung

ΔxA11A1ΔA(Δb+ΔAx)

Beweis 3 - Fehlerabschätzung und Konditionszahl

Mit der Abschätzung des absoluten Fehlers im Beweisschritt 2 erhält man bei Division durch x ein Abschätzung für den relativen Fehler mit x>0.

ΔxxA11A1ΔA(Δbx+ΔAxx=1).

Beweis 4 - Fehlerabschätzung und Konditionszahl

Da AGL(n,) regulär ist, gilt A>0. Durch Erweiterung des Ausdruck auf der rechten Seite der Ungleichung mit A erhält man:

ΔxxAA11A1ΔA(ΔbAx+ΔAA).

Beweis 5 - Fehlerabschätzung und Konditionszahl

Wegen bAx wird der Nenner nach unten und der Ausdruck aus Beweisschritt 4 weiter nach oben abgeschätzt und man erhält

ΔxxAA11A1ΔA(Δbb+ΔAA).

Beweis 6 - Fehlerabschätzung und Konditionszahl

Wegen ΔA=AΔAA sowohl im Zähler als auch im Nenner die Konditionszahl der Matrix A und damit die Behauptung:

ΔxxAA1=cond(A)1A1A=cond(A)ΔAA(Δbb+ΔAA).

q.e.d.


Bemerkung 1

Das Resultat liefert also eine Abschätzung des relativen Fehlers Δxx einer Lösung xn des Gleichungssystems Ax=b nach oben gegen eine Ausdruck, der

  • von der Konditionszahl der Matrix A und
  • von relativen Fehler der Matrix A und des relativen Fehlers des Vektors b

abhängt.

Bemerkung 2

Der Nenner in der Konstanten auf der rechten Seite in obigen Gleichung wird manchmal auch in der Form 1A1ΔA geschrieben.

Aufgabe - Tabellekalkulation

Berechnen Sie näherungsweise die induzierte Matrixnorm für eine beliebige 2×2-Matrix A2×2 bzgl. der euklischen Norm.

x=(x1x2)|:=x12+x22. Ferner sei Ax=b=(b1b2)
  • Berechnen Sie fehlende Spalteneinträge in E und F und bestimmen Sie dann in LibreOffice-Calc das Maximum aus Spalte G.
näherungsweise Berechnung - induzierte Matrixnorm
(A) k (B) Winkel (C)x1 (D)x2 (E)b1 (F)b2 (G)Ax
1 2π1n =cos(B2) =sin(C2) ... ... ...
2 2π2n =cos(B2) =sin(C2) ... ... ...
... ... ... ... ... ... ...
n 2πnn =cos(Bn+1) =sin(Cn+1) ... ... ...
  • Überprüfen Sie in der Tabellenkalkulation, ob die Determinante der Matrix von 0 verschieden ist.
  • Berechnen Sie mit der Tabellenkalkulation die inverse Matrix von A, unter der Bedingung, dass die Matrix A invertierbar ist.
  • Berechnen Sie dann die Konditionszahl cond(A) der Matrix A!
  • Wählen Sie ΔA und Δb und schätzen Sie den Fehler mit der Störungsresultaten ab!

Siehe auch

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.