Konditionstal

Konditionstal är inom numerisk analys ett mått på hur väl ett visst problem lämpar sig för numeriska beräkningar. Ett problem, exempelvis ett linjärt ekvationssystem $Ax=b \,\!$, kan vara olika känsligt för störningar i högerledet så att det orsakar en förändring i lösningen $x \,\!$.

Är konditionstalet för en matris till ett problem litet kallas det att matrisen är välkonditionerad, och problemet är lätt att lösa med god noggrannhet. Är konditionstalet istället stort är matrisen illa-konditionerad. Då är problemet känsligare för fel och därmed svårare att lösa med bra noggrannhet. Ett olösligt problem, till exempel att invertera en singulär matris, har oändligt stort konditionstal.

Definition

Konditionstalet av en matris $A$ kan definieras som

$\kappa(A) = \Vert A^{-1} \Vert \cdot \Vert A \Vert$,

där $\Vert \cdot \Vert$ är någon matrisnorm.

Om man också vill understycka villken matrisnorm som används kan man t ex skriva

$\kappa(A) = \Vert A^{-1} \Vert_\infty \cdot \Vert A \Vert_\infty$

som då avser den oändliga matrisnormen, dvs maximala radsumman, av matrisen $A$.

Härledning

För att härleda konditionstalet, betraktar vi först ett linjärt ekvationssytem $Ax=b \,\!$ som här är ett exakt system med den exakta lösningen $x \,\!$. Om vi nu har en förändring $db \,\!$ i högerledet, så kommer vi också att få en förändring $dx \,\!$ i lösningen.

$A(x+dx)=b+db \,\!$, det vill säga $Ax+Adx=b+db \,\!$.

Eftersom $Ax=b \,\!$ så är

$Adx=db \,\!$

vilket är ekvivanent med

$dx=A^{-1}db \,\!$

Nästa steg är att uppskatta det relativa felet $\frac{\Vert dx \Vert}{\Vert x \Vert}$ för uttrycket. Om man först tar normen av uttrycket så fås

$\Vert dx \Vert=\Vert A^{-1}db \Vert \le \Vert A^{-1} \Vert \cdot \Vert db \Vert$

vilket är en uppskattning av det absoluta felet.

Om man på samma sätt också tar normen av $Ax=b \,\!$ fås

$\Vert b \Vert=\Vert Ax \Vert \le \Vert A \Vert \cdot \Vert x \Vert$

Av dessa uttryck följer att

$\Vert b \Vert \cdot \Vert dx \Vert \le \Vert A \Vert \cdot \Vert x \Vert \cdot \Vert A^{-1} \Vert \cdot \Vert db \Vert$

och om man slutligen dividerar bägge leden med $\Vert x \Vert$ och $\Vert b \Vert$ får man

$\frac{\Vert dx \Vert}{\Vert x \Vert} \le \Vert A \Vert \cdot \Vert A^{-1} \Vert \cdot \frac{\Vert db \Vert}{\Vert b \Vert}$

Här ser vi alltså att konditionstalet $\kappa(A)=\Vert A \Vert \cdot \Vert A^{-1} \Vert$ är den skalfaktor som styr hur relativa felet i indata $b \,\!$ påverkar det relativa felet i lösningen $x \,\!$. Med detta samband kan vi nu uppskatta en övre gräns för känsligheten hos ett linjärt ekvationssystem.

Vad är då det minsta värde som $\kappa(A)\,\!$ kan anta? För ett ekvationssystem där det relativa felet för $x \,\!$är $1= \frac{\Vert x \Vert}{\Vert x \Vert}$, så följer

$\frac{\Vert x \Vert}{\Vert x \Vert}=\Vert E \Vert=\Vert A \cdot A^{-1}\Vert \le\Vert A \Vert \cdot \Vert A^{-1} \Vert =\kappa(A)$, där $E \,\!$ är enhetsmatrisen.

Alltså är $\kappa(A)\ge 1$

Också matrisen kan innehålla störningar. Uttrycket för att uppskatta känsligheten hos lösningen ser då ut såhär:

$\frac{\Vert dx \Vert}{\Vert x \Vert} \le \frac{\kappa(A)}{1-r} \Bigg( \frac{ \Vert dA \Vert}{\Vert A \Vert} + \frac{\Vert db \Vert}{\Vert b \Vert} \Bigg)$ där $r=\Vert dA \Vert \cdot \Vert A^{-1} \Vert$ och $r<1 \,\!$

Tillämpning

Exempel

Vi vill bestämma en övre gräns för $\frac{\Vert dx \Vert_\infty}{\Vert x \Vert_\infty}$ till ett givet ekvationssystem $Ax=\bar b \,\!$, där

$A= \begin{pmatrix} 0.6 & 0.25 \\ 0.4 & 0.2 \end{pmatrix}$, $A^{-1}= \begin{pmatrix} 10 & -12.5 \\ -20 & 30 \end{pmatrix}$ och $\bar b= \begin{pmatrix} 1.000 \\ 0.400 \end{pmatrix}$.

Elementen i $\bar b \,\!$ är givna med tre korrekta decimaler. Det innebär att vi har ett fel i $\bar b \,\!$ som är $\le 0.5\cdot10^{-3}$, dvs $db=\begin{pmatrix} 0.5\cdot10^{-3} \\ 0.5\cdot10^{-3} \end{pmatrix}$

Vi ska alltså beräkna $\frac{\Vert dx \Vert_\infty}{\Vert x \Vert_\infty} \le \kappa(A)_\infty \cdot \frac{\Vert db \Vert_\infty}{\Vert b \Vert_\infty}$.

Konditionstalet för $A$ är

$\kappa(A) = \Vert A^{-1} \Vert_\infty \cdot \Vert A \Vert_\infty = 0.85 \cdot 50=42.5$.

Normen av $\bar b$ är

$\Vert \bar b \Vert_\infty=\max (1 ,0.4)=1$.

Normen av $db \,\!$ är

$\Vert db \Vert_\infty=0.5\cdot10^{-3}$.

Gränsen för den relativa felet i lösningen blir då

$\frac{\Vert dx \Vert_\infty}{\Vert x \Vert_\infty} \le 42.5 \cdot \frac{0.5\cdot 10^{-3}}{1} \le 0.022$

Referenser

Eldén, Lars; Linde Wittmeyer-Koch (2001). Numeriska beräkningar -analys och illustrationer med MATLAB. Lund: Studnetlitteratur AB. ISBN 978-91-44-02007-5