Kurs:Numerik I/Störungsresultate für Matrizen
Störungsresultate für Matrizen Bearbeiten
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 Bearbeiten
In der folgenden Formulierung wird die Störung als absoluter Fehler . 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 Bearbeiten
Stellen wir z.B. ein Bild als quadratische Pixelmatrix , das von einem optischen Teleskop bei der Beobachtung von Sternen generiert wird. Die Lichtverschmutzung bei der Sternbeobachtung stört die Aufnahme von um . Das resultierende Bild ist dann .
Aufgaben - Anwendungsbezug Bearbeiten
- 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 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 Bearbeiten
Für eine reguläre/invertierbare Matrix mit einer Matrixnorm wird die Konditionszahl über
berechnet. Das folgende Lemma ist hilfreich, um für die Konditionszahl die Matrixnorm mit nach oben abzuschätzen.
Lemma - Regularität und induzierte Matrixnorm Bearbeiten
Sei eine durch eine Norm auf induzierte Matrixnorm und eine Matrix mit . Dann ist die Matrix regulär, und es gilt
Beweis - 1 - Regularität und induzierte Matrixnorm Bearbeiten
Die umgekehrte Dreiecksungleichung liefert für
Also ist für auch .
Beweis - 2 - Regularität und induzierte Matrixnorm Bearbeiten
Wenn für alle auch gilt, ist der Nullvektor das einzige Element im Kern von . Damit die Invertierbarkeit von impliziert.
Beweis - 2 - Regularität und induzierte Matrixnorm Bearbeiten
Mit der Setzung liefert die obige Ungleichung in Beweisschritt 1:
und damit
was den Beweis des Lemmas durch Maximumsbildung in der Matrixnorm komplettiert.
q.e.d.
Störungen als Differenzmatrizen Bearbeiten
Wenn man eine Matrix gegeben hat und eine Störung als Veränderung auffasst, ist es wesentlich die Konditionszahl der Matrix zu berechnen. Nach Definition der Konditionszahl muss man für die induzierte Matrixnorm abschätzen. Das folgende Korrolar liefert das als Resultat.
Korollar - Regularität und induzierte Matrixnorm 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 unter der Bedingung die Abschätzungen
Beweis - 1 - Korollar Bearbeiten
Mit der Submultiplikativität der induzierten Matrixnorm erhält man
Dabei erhält man die Abschätzung nach oben gegen 1 unter der gegebenen Voraussetzung .
Beweis - 2 - Korollar Bearbeiten
Nach Lemma über die Regularität ist somit die Matrix eine reguläre Matrix. Da nach Voraussetzung ist auch das Produkt von regulären Matrizen wieder regulär und man erhält:
Beweis - 3 - Korollar Bearbeiten
Mit und der Darstellung aus dem vorherigen Schritt erhält man die folgende Darstellung:
Beweis - 4 - Korollar Bearbeiten
Durch Anwendung des Lemmas über Regularität und induzierte Matrixnorm erhält man man nun die Abschätzung:
Beweis - 5 - Korollar Bearbeiten
Mit erhält man die folgende Darstellung:
Beweis - 6 - Korollar Bearbeiten
Zusammen mit der ersten Ungleichung des Korollars in Beweisschritt 3 folgt und der Verwendung der Submultiplikativität der Matrixnorm:
q.e.d.
Bemerkung zu Beweisschritt 6 Bearbeiten
In der zweiten Ungleichung liefert mit bzw. im Nenner die Abschätzung nach oben.
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. Mit seien gleichzeitig eine Vektornorm auf und die durch sie induzierte Matrixnorm auf bezeichnet. Weiter sei eine reguläre Matrix.
Satz - Fehlerabschätzung gestörter Gleichungssysteme Bearbeiten
Sei und und seien Vektoren mit
- (FG1)
Dann gelten für den absoluten bzw. den relativen Fehler von bezüglich die Abschätzungen
- (FG2)
- (FG3)
Beweis 1 - Fehlerabschätzung gestörter Gleichungssysteme Bearbeiten
Aus (FG1) folgt unmittelbar über Multiplikation mit die Aussage (FG2) mit
Beweis 2 - Fehlerabschätzung gestörter Gleichungssysteme Bearbeiten
bzw. líefert damit mit (FG2) die Behauptung (FG3). q.e.d.
Bemerkung Bearbeiten
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 1a Bearbeiten
Sei sehr klein und gegeben durch
Beispiel 1b Bearbeiten
Dann ist bei sehr kleinem die Matrixnorm von , von und somit die Kondition
sehr groß. Ein Gleichungssystem mit ist also ein schlecht konditioniertes Gleichungssystem.
Ähnliches gilt auch im Falle gestörter Matrizen.
Satz - Fehlerabschätzung und Konditionszahl 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
- (FK1)
die Abschätzung
- (FK2)
Beweis 1 - Fehlerabschätzung und Konditionszahl Bearbeiten
Aus (FK1) folgt mit unmittelbar
Insgesamt erhält man:
Beweis 2 - Fehlerabschätzung und Konditionszahl Bearbeiten
Korollar zur Regularität und Spektralnorm liefert nun die Invertierbarkeit der Matrix sowie die Abschätzung
Beweis 3 - Fehlerabschätzung und Konditionszahl Bearbeiten
Mit der Abschätzung des absoluten Fehlers im Beweisschritt 2 erhält man bei Division durch ein Abschätzung für den relativen Fehler mit .
Beweis 4 - Fehlerabschätzung und Konditionszahl Bearbeiten
Da regulär ist, gilt . Durch Erweiterung des Ausdruck auf der rechten Seite der Ungleichung mit erhält man:
Beweis 5 - Fehlerabschätzung und Konditionszahl Bearbeiten
Wegen wird der Nenner nach unten und der Ausdruck aus Beweisschritt 4 weiter nach oben abgeschätzt und man erhält
Beweis 6 - Fehlerabschätzung und Konditionszahl Bearbeiten
Wegen sowohl im Zähler als auch im Nenner die Konditionszahl der Matrix und damit die Behauptung:
q.e.d.
Bemerkung 1 Bearbeiten
Das Resultat liefert also eine Abschätzung des relativen Fehlers einer Lösung des Gleichungssystems nach oben gegen eine Ausdruck, der
- von der Konditionszahl der Matrix und
- von relativen Fehler der Matrix und des relativen Fehlers des Vektors
abhängt.
Bemerkung 2 Bearbeiten
Der Nenner in der Konstanten auf der rechten Seite in obigen Gleichung wird manchmal auch in der Form geschrieben.
Aufgabe - Tabellekalkulation Bearbeiten
Berechnen Sie näherungsweise die induzierte Matrixnorm für eine beliebige -Matrix bzgl. der euklischen Norm.
- . Ferner sei
- Berechnen Sie fehlende Spalteneinträge in E und F und bestimmen Sie dann in LibreOffice-Calc das Maximum aus Spalte G.
(A) k | (B) Winkel | (C) | (D) | (E) | (F) | (G) |
---|---|---|---|---|---|---|
1 | =cos(B2) | =sin(C2) | ... | ... | ... | |
2 | =cos(B2) | =sin(C2) | ... | ... | ... | |
... | ... | ... | ... | ... | ... | ... |
n | =cos(B ) | =sin(C ) | ... | ... | ... |
- Ü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 invertierbar ist.
- Berechnen Sie dann die Konditionszahl der Matrix !
- Wählen Sie und und schätzen Sie den Fehler mit der Störungsresultaten ab!
Siehe auch Bearbeiten
Seiteninformation Bearbeiten
Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.
Wiki2Reveal Bearbeiten
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.
- Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
- Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/St%C3%B6rungsresultate%20f%C3%BCr%20Matrizen
- siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.