Villkorsnummer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 december 2019; kontroller kräver 5 redigeringar .

Inom området numerisk analys mäter villkorsnumret för en funktion med avseende på ett argument hur mycket värdet på en funktion kan ändras med en liten förändring i argumentet. Denna parameter speglar hur känslig funktionen är för ändringar eller fel i ingången, och hur mycket felet i utmatningen är resultatet av ett fel i ingången. Mycket ofta löses det omvända problemet — att veta , hitta , för vilket villkorsnumret för det (lokala) omvända problemet ska användas. Vid linjär regression kan tillståndsnumret användas som diagnostik för multikollinearitet . [1] [2] $f(x)=y$ $x$

Villkorsnumret är en tillämpning av derivatan och definieras formellt som värdet av den asymptotiska värsta tänkbara relativa förändringen i utdata för den relativa förändringen i indata.

y=f(x)

y+\Delta y=f(x+\Delta x)

\mu (f):=\max _{x}{\frac {\varepsilon _{y}}{\varepsilon _{x}}}=\max _{x}{\frac {\|\ Delta y\|/\|y\|}{\|\Delta x\|/\|x\|}}

vid liten

\Delta x

[ förtydliga ]

var är normen respektive måtten i utrymmet för argument eller värden. $\|\cdot \|$ [ förtydliga ]

Villkorsnumret appliceras ofta på linjära algebrafrågor, i vilket fall derivatan är rakt fram, men felet kan vara i många olika riktningar och beräknas alltså utifrån matrisens geometri. Mer generellt kan villkorsnumret definieras för icke-linjära funktioner av flera variabler.

Ett problem med ett lågt tillståndstal sägs vara välkonditionerat, medan ett problem med ett högt tillståndstal sägs vara illa konditionerat. Villkorsnumret är en egenskap hos problemet. Tillsammans med problemet kan valfritt antal algoritmer användas för att lösa problemet, det vill säga för att beräkna lösningen. Vissa algoritmer har en egenskap som kallas bakåtstabilitet . I allmänhet kan en bakåtstabil algoritm förväntas lösa välkonditionerade problem på ett stabilt sätt. Läroböcker om numerisk analys ger formler för villkorsnummer för problem och definierar välkända bakåtstabila algoritmer.

Vanligtvis, om villkorsnumret är , kan du förlora upp till k siffror med precision utöver vad som skulle gå förlorat för ett numeriskt värde på grund av förlust av precision från aritmetiska metoder. [3] Villkorsnumret ger dock inget exakt värde på det maximala fel som kan uppstå i algoritmen. Vanligtvis begränsar detta helt enkelt det till en uppskattning (vars beräknade värde beror på valet av norm för att mäta felet). ${\displaystyle \mu (f)=10^{k))$

Villkorsnummer för linjära ekvationer

Låt en avgränsad inverterbar linjär operator ges . $A$

Betrakta den linjära ekvationen

yxa = b

där är en linjär operator , är en vektor , är den vektor som krävs ( ekvationsvariabel ). Antag att ekvationen löses med ett fel på indata . Förhållandet mellan de relativa felen i argumentet och lösningen är lika med $A$ $b$ $x$ $b\pm \Delta b$ $b$ $A^{-1}b$

{\frac {\frac {\left\|A^{-1}\Delta b\right\|}{\left\|A^{-1}b\right\|}}{\frac { \|\Delta b\|}{\|b\|}}}=\left({\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\ |}}\right)\cdot \left({\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right).

Då kännetecknar villkorstalet hur stort felet i lösningen blir för godtyckliga icke-noll b och e. $\mu (A)$

{\begin{aligned}\mu (A)=\max _{\Delta b,b\neq 0}\left\{\left({\frac {\left\|A^{-1}\ Delta b\right\|}{\|\Delta b\|}}\right)\cdot \left({\frac {\|b\|}{\left\|A^{-1}b\right\ |}}\right)\right\}&=\max _{\Delta b\neq 0}\left\({\frac {\left\|A^{-1}\Delta b\right\|}{ \|\Delta b\|}}\right\}\cdot \max _{b\neq 0}\left\{{\frac {\|b\|}{\left\|A^{-1}b \right\|}}\right\}\\&=\max _{\Delta b\neq 0}\left\({\frac {\left\|A^{-1}\Delta b\right\| }{\|\Delta b\|}}\right\}\cdot \max _{x\neq 0}\left\({\frac {\|Ax\|}{\|x\|}}\right \}\\&=\left\|A^{-1}\right\|\cdot \|A\|\end{aligned}}

Samma definition ges för alla operatörsnormer (det vill säga definitionen beror på valet av norm):

\mu (A)=||A||\cdot ||A^{{-1}}||

Om operatören inte är begränsad anses operatörens villkorsnummer vanligtvis vara . $A^{{-1}}$ $A$ $\mu (A)=+\infty$

Det finns många påståenden och uppskattningar av teorin om beräkningsmatematik förknippade med villkorsnumret .

Om operatörens villkorsnummer är litet kallas operatören välkonditionerad . Om tillståndsnumret är stort kallas operatören för dålig kondition . Således, ju mindre , desto "bättre", det vill säga desto mindre blir lösningsfelen i förhållande till felen i tillståndet. Med tanke på det är det bästa villkorstalet 1. $A$ $\mu (A)$ $\mu (A)\geqslant 1$

Exempel

Givet ett system av två linjära ekvationer: $\left\{{\begin{matrix}u+10v=11\\100u+1001v=1101\end{matrix}}\right.$

Lösningen är ett par siffror $\left\{{1;1}\right\}.$

Vi "stör" den högra sidan av den första ekvationen med 0,01 (istället för 11 skriver vi 11,01) och vi får ett nytt, "stört" system, vars lösning är ett par tal {11,01; 0,00}, vilket skiljer sig mycket från lösningen av det ostörda systemet. Här ledde en förändring av värdet på en parameter med mindre än till en relativt kraftig störning av lösningen. $0,\!1\%$

Några satser relaterade till villkorsnumret

En uppskattning av det relativa felet när ekvationen ersätts med en nära etta

Betrakta två linjära ekvationer:

Au=f\qquad \qquad \qquad \qquad \ (1)

- "grundläggande" ekvation.

(A+\Delta A)u=f+\Delta f\qquad (2)

- "nära" honom.

Låta vara en linjärt avgränsad inverterbar operator som verkar från hela rymden . $A$ $U$

Låt operatorerna också begränsas, och . $A^{-1},\Delta A$ $||A^{-1}||\cdot ||\Delta A||<1$

Låt vara en lösning av ekvation (1), var en lösning av ekvation (2). $u^{*}$ $u^{*}+\Delta u$

Sedan

{\frac {||\Delta u||}{||u^{*}||}}\leqslant {\frac {\mu (A)}{1-\mu (A){\frac {|| \Delta A||}{||A||}}}}\left({\frac {||\Delta A||}{||A||}}+{\frac {||\Delta f| |}{||f||}}\höger)

Anteckningar

↑ Belsley, David A.; Kuh, Edwin; Welsch, Roy E. Tillståndsnumret // Regression Diagnostics: Identifying Influential Data and Sources of Collinearity . - New York: John Wiley & Sons , 1980. - S. 100-104 . — ISBN 0-471-05856-4 .
↑ Pesaran, M. Hashem Multikollinearitetsproblemet //Tidsserier och paneldataekonomi . - New York: Oxford University Press , 2015. - S. 67-72 [s. 70]. - ISBN 978-0-19-875998-0 .
↑ Cheney; Kincaid. Numerisk matematik och beräkning (obestämd) . - 2007. - ISBN 978-0-495-11475-8 .