Kondition eines linearen Gleichungssystems

Beschreibung

Hier wird beschrieben wie stark das Ergebnis eines Linearen Gleichungssystems von dem Gleichungssystem abhängt. D.h. welche Änderung eine kleine Änderung der Gleichungsparameter hervorruft.

Fehleranalysen

Fehler bei Variation von $b$

Sei $A\in \mathcal{M}(n,\text{K})$ invertierbar. Betrachte $Ax=b\text{ mit einer A¨nderung}A(x+\Delta x)=b+\Delta b$

Dann gilt für den absoluten Fehler: $\Vert \Delta \Vert \le \Vert A^{-1}\Vert \Vert \Delta b\Vert$ und für den relativen Fehler $\frac{\Vert \Delta x\Vert }{\Vert x\Vert }\le \kappa (A)\frac{\Vert \Delta b\Vert }{\Vert b\Vert }$.

Fehler bei Variation von $Id$

Wir variieren $Id$ durch $\Delta A,\Vert \Delta A\Vert <1$ und erhalten für die Umkehrfunktion (die ein lineares Gleichungssyste lösen soll): $\Vert (Id+\Delta A{)}^{-1}y\Vert \le \frac{1}{1-\Vert \Delta A\Vert }\Vert y\Vert$

Fehler bei Variation von $A$

Wir variieren $A$ durch $\Delta A,\Vert \Delta A\Vert <\Vert A^{-1}{\Vert }^{-1}$ und erhalten für die Umkehrfunktion (die ein lineares Gleichungssyste lösen soll): $\Vert (A+\Delta A{)}^{-1}y\Vert \le \frac{1}{\Vert A^{-1}{\Vert }^{-1}-\Vert \Delta A\Vert }\Vert y\Vert$

Fehler bei Variation von $A$ und $b$

Formalitäten wie zuvor. Durch Variation erhalten wir: $\frac{\Delta x}{\Vert x\Vert }=\frac{\kappa (A)}{1-\Vert A^{-1}\Vert \Vert \Delta A\Vert }\text{klam}\frac{\Vert \Delta A\Vert }{\Vert A\Vert }+\frac{\Vert \Delta b\Vert }{\Vert b\Vert }$

$\kappa (A)$ ist die Konditionszahl von $A$.

Q: Relativer Fehler bei Variation von $A$ und $b$ eines Gleichungssystems. A: (\frac{\Delta x}{|x|} = \frac{\kappa(A)}{1-|A^{-1}||\Delta A|}\klam{\frac{|\Delta A|}{|A|} + \frac{|\Delta b|}{|b|}})

Eigenschaften

Verstärkung durch Eigenwerte

Haben die Eigenwerte einer Matrix sehr unterschiedliche Größenordnungen, so ist die Kondition sehr groß. Das erkennt man aus oberer Gleichung mit folgender Substitution für die Konditionszahl bei hermitischem $A$: $\frac{\Vert \Delta x\Vert }{\Vert x\Vert }\le \frac{\max |\sigma (A)|}{\min |\sigma (A)|}\frac{\Vert \Delta b\Vert }{\Vert b\Vert }$

Die Störung ist besonders anfällig für $b=v_{max}$ in Richtung von $v_{min}$. Wobei das die Eigenvektoren des größten und kleinsten Eigenwertes sind. Denn wenn wir $b$ in Richtung $v_{min}$ bewegen, so multipiziert sich die von $x$ zurückgelegte Strecke v um ${\lambda }_{min}^{-1}$. Dadurch, dass $b=v_{max}$ ist, ist $x$ besonders klein und erfährt eine größere relative Änderung durch die Verschiebung. Für $\Vert v_{min}\Vert =\Vert v_{max}\Vert =1$ ist der Fehler genau $\frac{\max |\sigma (A)|}{\min |\sigma (A)|}$

\newcommand{\R}{\mathbb R}