Konditionstal

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Exempel[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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