[WS] Lineare Gleichungssysteme 1

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 1
Gliederung

  1. Normen

    1a. Beispiele für Vektornormen
    1b. Operatornorm
    1c. Spaltensummennorm
    1d. Spektralnorm
    1e. Zeilensummennorm
    1f. Verträglichkeit
    1g. Submultiplikativität
    1h. Frobenius- Norm
    1i. Äquivalenz von Normen

  2. Kondition und Fehlerabschätzung

    2a. Kondition einer Matrix
    2b. Kondition bei Normalengleichungen
    2c. Störungslemma
    2d. Störungssatz
    2e. Beispiel Störungssatz
    2f. Kondition und genaue Stellen


tigerbine Auf diesen Beitrag antworten »
1. Norm
Sei X ein reeller Vektorraum. Eine Abbildung: mit den Eigenschaften:





heißt Norm auf X.
tigerbine Auf diesen Beitrag antworten »
1a. Beispiele für Vektornormen
Lp-Normen




Betragssummennorm




Euklidische Norm




Maximumnorm

tigerbine Auf diesen Beitrag antworten »
1b. Operatornormen
Gegeben seinen 2 Vektornormen auf . Für einen linearen Operator ist die zugehörige Operatornorm definiert als:




Dabei gelten die Äquivalenzen (Beweis):




Aus Kompaktkeitsgründen gilt auch:




Eine weitere wichtige Eigenschaft (Verträglichkeit), die direkt aus der Definition (beachte das Supremum!) folgt, ist:



Damit folgt noch eine Eigenschaft, die Submultiplikativität (bedenke Bx ist ein Vektor!). Da es sich hier nun um 2 lineare Abbildung handelt, führen wir noch einen dritten VR Z ein. AB: X-> Y -> Z





Beweis 1 (Äquivalenzen):

Folgt, wenn man sich verdeutlicht, dass dadurch das Längenverhältnis von x, Ax in den Normen in X, Y dargestellt wird. Ferner ist die Abbildung stetig auf einem Kompaktum.


Beweis 2 (Normeigenschaften):










Im folgenden gilt X=Y und man betrachtet den Vektorraum der nxn-Matrizen. Die durch die Vektornorm X durch obige Definition erzeugten Vektornormen nennt man induzierte Matrixnormen. Für diese gilt insbesondere die Eigenschaft :

tigerbine Auf diesen Beitrag antworten »
1c. Spaltensummennorm
Spaltensummennorm




Beweis 1:

Sei . Dann gilt:

  1. Sei beliebig. Dann ist:






  2. Sei und der j-te Einheitsvektor. Dann gilt:



Somit gilt
tigerbine Auf diesen Beitrag antworten »
1d. Spektralnorm
Spektralnorm




Beweis :

Es die Matrix symmetrisch. Daher gibt es ONB von Eigenvektoren , d.h. .


Für jedes x ist . Daraus folgt, dass alle Eigenwerte nicht negativ sind, denn es gilt:


Für den Spektralradius gilt:


Somit folgt:






Wenn u der Eigenvektor zum größten Eigenwert ist, folgt mit:



Und somit die Gleichheit.
 
 
tigerbine Auf diesen Beitrag antworten »
1e. Zeilensummennorm
Zeilensummennorm





Beweis 3:

Sei . Dann gilt:

  1. Sei beliebig. Dann ist:






  2. Sei und der j-te Einheitsvektor. Dann gilt:





tigerbine Auf diesen Beitrag antworten »
1f. Verträglichkeit
Eine Matrixnorm und zwei Vektornorm X,Y heißen verträglich, wenn gilt:

tigerbine Auf diesen Beitrag antworten »
1g. Submultiplikativität
Eine Matrixnorm heißt submultiplikativ, wenn gilt

tigerbine Auf diesen Beitrag antworten »
1h. Frobenius- Norm
Als klassisches Beispiel für eine nicht induzierte Matrix Norm wird die Fobenius Norm angeführt:




Diese ist für n>1 keine Induzierte MAtrixnorm, denn es gilt:



Hingegen gilt für jede Induzierte Matrixnorm:



die Frobeniusnorm ist submultiplikativ und mit der euklidischen Norm verträglich.
tigerbine Auf diesen Beitrag antworten »
1i. Äquivalenz von Normen
In endlich-dimensionalen Vektorräumen sind je 2 Normen äquivalent, es gibt also 2 Konstanten c und C mit:






D.h. die Konvergenz einer Folge hängt nicht von der gewählten Norm ab.
tigerbine Auf diesen Beitrag antworten »
2. Kondition und Fehlerabschätzung
Wenn man nun ein LGS Ax = b mittels Computer lösen möchte, so entstehen schon unabhängig von der Wahl des Lösungsalgorithmus allein durch die Übergabe der Daten i.A. Fehler (Endlichkeit der Maschinenzahlen). D.h. durch die Implementierung wird das System:



lösen. Dabei stellt sich natürlich die Frage, wir stark sich die Fehler in A, b auf die zu berechnende Größe x übertragen. Im folgenden sei A eine reguläre Matrix.
tigerbine Auf diesen Beitrag antworten »
2a. Kondition einer Matrix
Betrachtet werden hier die beiden LGS




Welchen Einfluss hat nun die Störung von b auf die Lösung x?



Dabei folgt die letzte Abschätzung aus der Verträglichkeit von Vektor und Matrixnorm.


Weiter gilt die folgende Abschätzung:




Somit folgt für den relativen Fehler von x die Abschätzung





Damit kann man den Term als Verstärkungsfaktor des relativen Fehlers von b ansehen. Man nennt ihn die Kondition von A:





Welche minimale Kondition (Verstärkung) ist möglich?





Welche Matrizen sind gut konditioniert?

Orthogonale Matrizen Q sind gut konditioniert, gilt doch für ihre Spektralkondition( Spektralradius):










Weiter notieren wir hierbei noch die Längentreue einer Orthogonalen Abbildung:





Beispiel für schlecht konditionierte Matrizen

Hilbert-Matrix

Hier wächst die Kondition exponentiell mit n.
tigerbine Auf diesen Beitrag antworten »
2b. Kondition bei Normalengleichungen
Sei A eine reguläre Matrix. Betrachtet man die Spektralnorm, dann ist:





Beweis:

Es besitzen und dieselben Eigenwerte, gilt doch (: Spektrum)




Daraus folgt und somit . Des weiteren gilt:




Somit ergibt sich dann:

tigerbine Auf diesen Beitrag antworten »
2c. Störungslemma
Störungslemma

Die Matrix B habe die Norm . Dann ist die Matrix regulär und es gilt:





Beweis:

Zunächst soll die Regularität gezeigt werden. Es gilt dabei für alle :




Wegen der Voraussetzung folgt:




Und es gilt für alle




Daraus folgt direkt die Injektivität von (I+B) und wegen der endl. Dimension direkt auch die Bijektivität.


Somit gilt:



Durch Umstellen erhält man die Behauptung:

tigerbine Auf diesen Beitrag antworten »
2d. Störungssatz
Durch die Eingabe der Daten des LGS wird ja nicht nur der Vektor b gestört, sondern auch die Matrix A (regulär) . Sei also:





Gilt für A dann , so ist die Matrix ebenfalls regulär und es gilt:






Im Falle gilt dann:




Somit kann man auch hier die Kondition von A als Verstäkungsfaktor der relativen Fehler von b und A verstehen.





Beweis:

Nach Voraussetzung gilt , damit folgt auch .


Mit dem Störungslemma ist die folgende Matrix regulär:




Es gilt:



Da invertierbar ist, folgt:





Daraus folgt:



Durch Umstellen folgt nun die Behauptung:

tigerbine Auf diesen Beitrag antworten »
2e. Beispiel Störungssatz
Es soll nun ein Beispiel konstruiert werden, so dass im Strörungsatz Gleichheit gilt.

Sei A nun eine symmetrische positiv definite Matrix. Dann ist A auch regulär. Weiter seien:

  • der kleinste EW und der zugehörige normierte EV

  • der kleinste EW und der zugehörige normierte EV


Betrachtet werden soll das gestörte System:




Es gilt dann:




Diese haben die Lösungen:






Es folgt dann, mit dem Wissen über die Spektralnorm einer symmtetrischen Matrix

tigerbine Auf diesen Beitrag antworten »
2f. Kondition und genaue Stellen
Sei die Kondition von A, . Für die relativen Fehler von A und b gelte:




Dann ist der Term:




Damit gilt für den relativen Fehler im Ergebnis:




d.h. man verliert s-Stellen gegenüber der gegebenen Genauigkeit von A und b.
tigerbine Auf diesen Beitrag antworten »
Ausblick
Mit dem Thema "Lösen von Linearen Gleichungssystemen" beschäftigt sich der nächste Workshop.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »