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.

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}$.

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\,\!}$

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}$

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