Numărul condiției

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 decembrie 2019; verificările necesită 5 modificări .

În domeniul analizei numerice , numărul de condiție al unei funcții în raport cu un argument măsoară cât de mult se poate schimba valoarea unei funcții cu o mică modificare a argumentului. Acest parametru reflectă cât de sensibilă este funcția la modificări sau erori în intrare și cât de mult eroarea din ieșire este rezultatul unei erori în intrare. Foarte des, problema inversă este rezolvată — știind , găsiți , pentru care ar trebui folosit numărul de condiție al problemei inverse (locale). În regresia liniară , numărul condiției poate fi folosit ca diagnostic pentru multicoliniaritate . [1] [2] $f(x)=y$ $X$

Numărul condiției este o aplicație a derivatei și este definit formal ca valoarea modificării relative asimptotice în cel mai rău caz a ieșirii pentru modificarea relativă a intrării.

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

la mic

\Delta x

[ clarifica ]

unde este norma sau , respectiv, metrica în spațiul argumentelor sau valorilor. $\|\cdot \|$ [ clarifica ]

Numărul condiției este adesea aplicat întrebărilor de algebră liniară, caz în care derivata este directă, dar eroarea poate fi în multe direcții diferite și este astfel calculată din geometria matricei. Mai general, numărul condiției poate fi definit pentru funcții neliniare ale mai multor variabile.

Se spune că o problemă cu un număr de condiție scăzut este bine condiționată, în timp ce o problemă cu un număr de stare mare se spune că este prost condiționată. Numărul condiției este o proprietate a problemei. Odată cu problema, se poate folosi orice număr de algoritmi pentru a rezolva problema, adică pentru a calcula soluția. Unii algoritmi au o proprietate numită stabilitate înapoi . În general, se poate aștepta ca un algoritm stabil înapoi să rezolve probleme bine condiționate într-o manieră stabilă. Manualele de analiză numerică oferă formule pentru condiționarea numărului de probleme și definesc algoritmi stabili înapoi bine-cunoscuți.

De obicei, dacă numărul condiției este , atunci puteți pierde până la k cifre de precizie în plus față de ceea ce s-ar pierde pentru o valoare numerică din cauza pierderii preciziei din metodele aritmetice. [3] Cu toate acestea, numărul condiției nu oferă o valoare exactă a erorii maxime care poate apărea în algoritm. De obicei, aceasta o limitează pur și simplu la o estimare (a cărei valoare calculată depinde de alegerea normei de măsurare a erorii). $\mu (f)=10^{k)$

Numărul condiției pentru ecuații liniare

Să fie dat un operator liniar inversabil mărginit . $A$

Luați în considerare ecuația liniară

ax = b

unde este un operator liniar , este un vector , este vectorul necesar ( variabila ecuației ). Să presupunem că ecuația este rezolvată cu o eroare la datele de intrare . Raportul dintre erorile relative ale argumentului și soluției este egal cu $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).

Apoi, numărul condiției caracterizează cât de mare va fi eroarea soluției pentru b și e arbitrar diferit de zero. $\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}}

Aceeași definiție este dată pentru orice normă de operator (adică definiția depinde de alegerea normei):

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

Dacă operatorul nu este limitat , atunci numărul de condiție al operatorului este de obicei considerat a fi . $A^{{-1}}$ $A$ $\mu (A)=+\infty$

Există multe afirmații și estimări ale teoriei matematicii computaționale asociate cu numărul condiției .

Dacă numărul de condiție al operatorului este mic, atunci operatorul este numit bine condiționat . Dacă numărul condiției este mare, atunci operatorul este numit prost condiționat . Astfel, cu cât mai mici , cu atât „mai bine”, adică cu atât erorile de soluție vor fi mai mici în raport cu erorile din condiție. Având în vedere că , atunci cel mai bun număr de condiție este 1. $A$ $\mu (A)$ $\mu (A)\geqslant 1$

Exemplu

Dat un sistem de două ecuații liniare: $\left\{{\begin{matrice}u+10v=11\\100u+1001v=1101\end{matrice}}\right.$

Soluția este o pereche de numere $\stanga\{{1;1}\dreapta\}.$

„Perturbăm” partea dreaptă a primei ecuații cu 0,01 (în loc de 11 scriem 11,01) și obținem un sistem nou, „perturbat”, a cărui soluție este o pereche de numere {11,01; 0,00}, care diferă foarte mult de soluția sistemului neperturbat. Aici, o modificare a valorii unui parametru cu mai puțin decât a condus la o perturbare relativ puternică a soluției. $0,\!1\%$

Câteva teoreme legate de numărul condiției

O estimare a erorii relative atunci când ecuația este înlocuită cu una apropiată

Luați în considerare două ecuații liniare:

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

- ecuația „de bază”.

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

- „aproape” de el.

Fie un operator inversabil liniar mărginit care acționează din spațiul complet . $A$ $U$

Fie și operatorii să fie mărginiți și . $A^{-1},\Delta A$ $||A^{-1}||\cdot ||\Delta A||<1$

Fie o soluție a ecuației (1), fie o soluție a ecuației (2). $u^{*}$ $u^{*}+\Delta u$

Apoi

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

Note

↑ Belsley, David A.; Kuh, Edwin; Welsch, Roy E. The Condition Number // Diagnosticarea regresiei: identificarea datelor influente și a surselor de coliniaritate . - New York: John Wiley & Sons , 1980. - P. 100-104 . — ISBN 0-471-05856-4 .
↑ Pesaran, M. Hashem Problema multicolinearității // Serii temporale și econometrie a datelor de panou . - New York: Oxford University Press , 2015. - P. 67-72 [p. 70]. - ISBN 978-0-19-875998-0 .
↑ Cheney; Kincaid. Matematică numerică și calcul (nedefinit) . - 2007. - ISBN 978-0-495-11475-8 .