Tilstandsnummer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. december 2019; checks kræver 5 redigeringer .

Inden for numerisk analyse måler betingelsesnummeret for en funktion i forhold til et argument, hvor meget værdien af en funktion kan ændre sig med en lille ændring i argumentet. Denne parameter afspejler, hvor følsom funktionen er over for ændringer eller fejl i input, og hvor meget fejlen i output er resultatet af en fejl i input. Meget ofte løses det omvendte problem - at vide , finde , for hvilket betingelsesnummeret for det (lokale) omvendte problem skal bruges. Ved lineær regression kan tilstandsnummeret bruges som diagnostik for multikollinearitet . [1] [2] $f(x)=y$ $x$

Betingelsesnummeret er en anvendelse af den afledede og er formelt defineret som værdien af den asymptotiske worst-case relative ændring i output for den relative ændring i input.

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

i det små

\Delta x

[ afklare ]

hvor er normen eller metrikken , henholdsvis i rummet af argumenter eller værdier. $\|\cdot \|$ [ afklare ]

Betingelsesnummeret anvendes ofte på lineære algebraspørgsmål, i hvilket tilfælde den afledede er ligetil, men fejlen kan være i mange forskellige retninger og beregnes således ud fra matrixens geometri. Mere generelt kan betingelsesnummeret defineres for ikke-lineære funktioner af flere variable.

Et problem med et lavt tilstandstal siges at være velkonditioneret, mens et problem med et højt tilstandstal siges at være sygt konditioneret. Betingelsesnummeret er en egenskab ved problemet. Sammen med problemet kan et hvilket som helst antal algoritmer bruges til at løse problemet, det vil sige at beregne løsningen. Nogle algoritmer har en egenskab kaldet baglæns stabilitet . Generelt kan en baglæns stabil algoritme forventes at løse velkonditionerede problemer på en stabil måde. Lærebøger om numerisk analyse giver formler for tilstandsnumre for problemer og definerer velkendte bagudstabile algoritmer.

Typisk, hvis betingelsesnummeret er , så kan du miste op til k cifre af præcision ud over, hvad der ville gå tabt for en numerisk værdi på grund af tab af præcision fra aritmetiske metoder. [3] Betingelsesnummeret giver dog ikke en nøjagtig værdi af den maksimale fejl, der kan opstå i algoritmen. Normalt begrænser dette simpelthen det til et skøn (hvis beregnede værdi afhænger af valget af norm til at måle fejlen). ${\displaystyle \mu (f)=10^{k))$

Betingelsesnummer for lineære ligninger

Lad en afgrænset inverterbar lineær operator være givet . $EN$

Overvej den lineære ligning

økse = b

hvor er en lineær operator , er en vektor , er den nødvendige vektor ( ligningsvariabel ). Antag at ligningen er løst med en fejl på inputdataene . Forholdet mellem argumentets og løsningens relative fejl er lig med $EN$ $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\|}}}=\venstre({\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\ |}}\right)\cdot \left({\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right).

Så karakteriserer betingelsestallet, hvor stor fejlen i løsningen vil være for vilkårlige ikke-nul b og 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}}

Den samme definition er givet for enhver operatørnorm (det vil sige, definitionen afhænger af valget af normen):

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

Hvis operatøren ikke er begrænset , anses operatørens betingelsesnummer normalt for at være . $A^{{-1}}$ $EN$ $\mu (A)=+\infty$

Der er mange udsagn og skøn af teorien om beregningsmatematik forbundet med betingelsesnummeret .

Hvis operatørens tilstandsnummer er lille, kaldes operatøren velkonditioneret . Hvis betingelsestallet er stort, kaldes operatøren dårligt konditioneret . Jo mindre , jo bedre, det vil sige, jo mindre vil løsningsfejlene være i forhold til fejlene i tilstanden. Givet det , så er det bedste betingelsesnummer 1. $EN$ $\mu (A)$ $\mu (A)\geqslant 1$

Eksempel

Givet et system af to lineære ligninger: $\left\{{\begin{matrix}u+10v=11\\100u+1001v=1101\end{matrix}}\right.$

Løsningen er et par tal $\left\{{1;1}\right\}.$

Vi "forstyrrer" højre side af den første ligning med 0,01 (i stedet for 11 skriver vi 11,01), og vi får et nyt, "forstyrret" system, hvis løsning er et talpar {11,01; 0,00}, hvilket adskiller sig meget fra løsningen af det uforstyrrede system. Her førte en ændring i værdien af en parameter med mindre end til en relativt kraftig forstyrrelse af løsningen. $0,\!1\%$

Nogle sætninger relateret til betingelsesnummeret

Et estimat af den relative fejl, når ligningen erstattes af en tæt

Overvej to lineære ligninger:

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

- "grundlæggende" ligning.

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

- "tæt" på ham.

Lade være en lineært afgrænset inverterbar operator, der virker fra hele rummet . $EN$ $U$

Lad også operatorerne være afgrænset, og . $A^{-1},\Delta A$ $||A^{-1}||\cdot ||\Delta A||<1$

Lad være en løsning af ligning (1), vær en løsning af ligning (2). $u^{*}$ $u^{*}+\Delta u$

Derefter

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

Noter

↑ Belsley, David A.; Kuh, Edwin; Welsch, Roy E. Tilstandsnummeret // Regressionsdiagnostik: Identifikation af indflydelsesrige data og kilder til kollinearitet . - New York: John Wiley & Sons , 1980. - S. 100-104 . — ISBN 0-471-05856-4 .
↑ Pesaran, M. Hashem Multikolinearitetsproblemet // Tidsserier ogpaneldataøkonomi . - New York: Oxford University Press , 2015. - S. 67-72 [s. 70]. - ISBN 978-0-19-875998-0 .
↑ Cheney; Kincaid. Numerisk matematik og databehandling (ubestemt) . - 2007. - ISBN 978-0-495-11475-8 .