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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle A}$ kan definieras som

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

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

Om man också vill understyka vilken matrisnorm som används kan man t.ex. skriva

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

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

Härledning

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

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

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

${\displaystyle Adx=db\,\!}$

vilket är ekvivalent med

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

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

${\displaystyle \Vert dx\Vert =\Vert A^{-1}db\Vert \leq \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 ${\displaystyle Ax=b\,\!}$ fås

${\displaystyle \Vert b\Vert =\Vert Ax\Vert \leq \Vert A\Vert \cdot \Vert x\Vert }$

Av dessa uttryck följer att

${\displaystyle \Vert b\Vert \cdot \Vert dx\Vert \leq \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 ${\displaystyle \Vert x\Vert }$ och ${\displaystyle \Vert b\Vert }$ får man

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

Här ser vi alltså att konditionstalet ${\displaystyle \kappa (A)=\Vert A\Vert \cdot \Vert A^{-1}\Vert }$ är den skalfaktor som styr hur relativa felet i indata ${\displaystyle b\,\!}$ påverkar det relativa felet i lösningen ${\displaystyle 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 ${\displaystyle \kappa (A)\,\!}$ kan anta? För ett ekvationssystem där det relativa felet för ${\displaystyle x\,\!}$är ${\displaystyle 1={\frac {\Vert x\Vert }{\Vert x\Vert }}}$, så följer

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

Alltså är ${\displaystyle \kappa (A)\geq 1}$

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

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

Tillämpning

Exempel

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

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

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

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

Konditionstalet för ${\displaystyle A}$ är

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

Normen av ${\displaystyle {\bar {b}}}$ är

${\displaystyle \Vert {\bar {b}}\Vert _{\infty }=\max(1,0.4)=1}$.

Normen av ${\displaystyle db\,\!}$ är

${\displaystyle \Vert db\Vert _{\infty }=0.5\cdot 10^{-3}}$.

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

${\displaystyle {\frac {\Vert dx\Vert _{\infty }}{\Vert x\Vert _{\infty }}}\leq 42.5\cdot {\frac {0.5\cdot 10^{-3}}{1}}\leq 0.022}$

Referenser

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