Estabilitat numèrica

En el camp de l'anàlisi numèrica, hom diu que un algorisme és numèricament estable, o que té estabilitat numèrica, quan petites alteracions en les dades no provoquen gaire alteracions del resultat. En particular, això vol dir que els errors d'arrodoniment no repercuteixen en gran manera sobre el càlcul. Hom acostuma a diferenciar entre els conceptes de nombre de condició, estabilitat i consistència, que estan fortament relacionats entre si. L'estabilitat és una propietat dels algorismes, i la condició és una propietat dels problemes.

Definició

Donat un algorisme f(x), on x són les dades d'entrada i ε l'error en les dades d'entrada, es diu que l'algorisme és numèricament estable (és a dir, l'algorisme depèn de forma contínua dels paràmetres) per l'error absolut si

${\displaystyle x-(x+\varepsilon )\simeq f(x)-f(x+\varepsilon )}$

i numèricament estable per l'error relatiu si

${\displaystyle {\frac {x-(x+\varepsilon )}{x}}\simeq {\frac {f(x)-f(x+\varepsilon )}{f(x)}}}$.

Es diu que un algorisme és numèricament inestable per l'error absolut si

${\displaystyle x-(x+\varepsilon )\ll f(x)-f(x+\varepsilon )\ }$

i numèricament inestable per l'error relatiu si

${\displaystyle {\frac {x-(x+\varepsilon )}{x}}\ll {\frac {f(x)-f(x+\varepsilon )}{f(x)}}}$.

Relació entre l'estabilitat i el nombre de condició

Sigui ${\displaystyle f(x)}$ un problema matemàtic, depenent de l'entrada ${\displaystyle x}$, i siguin ${\displaystyle {\tilde {f}}}$ l'algorisme numèric i ${\displaystyle {\tilde {x}}}$ les dades alterades. La intenció és trobar una fita per la magnitud de l'error:

${\displaystyle \|f(x)-{\tilde {f}}({\tilde {x}})\|.}$

Aplicant la desigualtat triangular, s'obté:

${\displaystyle \|f(x)-{\tilde {f}}({\tilde {x}})\|=\|f(x)-f({\tilde {x}})+f({\tilde {x}})-{\tilde {f}}({\tilde {x}})\|\leq \|f(x)-f({\tilde {x}})\|+\|f({\tilde {x}})-{\tilde {f}}({\tilde {x}})\|.}$

Hom acostuma a designar per ${\displaystyle \|f(x)-f({\tilde {x}})\|}$ la condició del problema, i per ${\displaystyle \|f({\tilde {x}})-{\tilde {f}}({\tilde {x}})\|}$ la seva estabilitat.

L'estabilitat també descriu la robustesa d'un algorisme numèric en relació a petites variacions en les dades d'entrada; en particular, si els errors d'arrodoniment es propaguen o no, i si comporten variacions significatives en els resultats. La quantificació d'aquesta idea pot variar en funció del problema i de la norma emprada.

Mètodes d'anàlisi de l'estabilitat numèrica

Anàlisi cap endavant

Es diu que un algorisme és estable si existeix una constant ${\displaystyle \sigma \in \mathbb {R} }$ tal que

${\displaystyle \|f({\tilde {x}})-{\tilde {f}}({\tilde {x}})\|\leq \kappa \sigma \varepsilon }$

on ${\displaystyle \kappa }$ és el nombre de condició relatiu del problema, i ${\displaystyle \varepsilon }$ és l'èpsilon de la màquina. El valor ${\displaystyle \sigma }$ quantifica l'estabilitat en el sentit de l'anàlisi cap endavant.

Anàlisi cap enrere

El segon mètode d'anàlisi dels algorismes fou desenvolupat per James H. Wilkinson. Moltes vegades, hom coneix una fita superior ${\displaystyle \varepsilon }$ per l'error relatiu ${\displaystyle {\frac {\|{\tilde {x}}-x\|}{\|x\|}}}$ en les dades d'entrada (depenent del problema, això pot representar un error de mesura o també un error d'arrodoniment). Per estimar millor els errors produïts per l'algorisme, hom pot calcular un error equivalent en les dades del problema, mitjançant l'anàlisi cap enrere, que hom anomena error cap enrere. La definició formal de l'error cap enrere de l'algorisme ${\displaystyle {\tilde {f}}}$ per les dades d'entrada (possiblement arrodonides) ${\displaystyle {\tilde {x}}}$ (on ${\displaystyle \|{\tilde {x}}\|\neq 0}$) és:

${\displaystyle \varepsilon _{\rm {R}}({\tilde {x}}):=\inf \left\{{\frac {\|{\hat {x}}-{\tilde {x}}\|}{\|{\tilde {x}}\|}}{\Bigg |}{\hat {x}}\in \operatorname {Dom} f\;\wedge \;f({\hat {x}})={\tilde {f}}({\tilde {x}})\right\},}$

on ${\displaystyle \operatorname {Dom} }$ és el domini del problema.

Un algorisme és estable cap enrere si l'error cap enrere relatiu per tot ${\displaystyle {\tilde {x}}\in \operatorname {Dom} {\tilde {f}}}$ és menor que l'error relatiu inevitable d'entrada. Per a algunes aplicacions, hom relaxa aquesta condició i n'hi ha prou amb una constant ${\displaystyle C>1}$ tal que,

per tot ${\displaystyle {\tilde {x}}\in \operatorname {Dom} {\tilde {f}}:\;\varepsilon _{\rm {R}}({\tilde {x}})\leq C\varepsilon .}$

De vegades només és interessant poder trobar una fita per l'error cap enrere relatiu.

Hom pot demostrar que l'estabilitat cap enrere implica l'estabilitat cap endavant.^[1]

Aplicacions

Addició

Com que es pot veure que la condició relativa de l'addició de dos nombres en cas de cancel·lació (el resultat és pròxim a 0) pot ser arbitràriament dolenta, se segueix a partir de la definició d'anàlisi cap endavant que l'addició, pensada com un algorisme numèric, és estable.

Equacions diferencials

En el cas de solucions numèriques a equacions diferencials amb condicions inicials o condicions de contorn, hom pot buscar una fita de la solució en termes de la grandària de l'entrada. En el sentit de l'anàlisi cap endavant, hom pot trobar la constant ${\displaystyle \sigma }$.

Equacions diferencials ordinàries

En el cas d'equacions diferencials ordinàries es pot aplicar el teorema d'equivalència de Lax, que estableix l'equivalència entre la convergència i l'estabilitat.

El domini d'estabilitat es defineix com el conjunt de nombres complexos ${\displaystyle \xi =\Delta t\cdot \lambda }$ pels quals el mètode de resolució del test de Dahlquist

${\displaystyle y'=\lambda y,\quad y(0)=1}$

per increments ${\displaystyle \Delta t}$ és una successió monòtona d'aproximacions a la solució.

El millor cas es dona quan el domini d'estabilitat és semiplà complex esquerre; hom diu doncs que el procediment és A-estable.

Equacions en derivades parcials

El mètode estàndard per analitzar l'estabilitat de mètodes numèrics per equacions en derivades parcials és l'anàlisi d'estabilitat de Von Neumann, el qual proporciona condicions necessàries i suficients per problemes lineals. Per problemes no lineals, en canvi, només proporciona condicions necessàries.

Referències

Bibliografia

• Wilkinson, J. H. «Error Analysis of Direct Methods of Matrix Inversion» (en anglès). Journal of the ACM, 8, 3, NaN undefined NaN, pàg. 281–330. DOI: 10.1145/321075.321076 [Consulta: 4 agost 2013].
• Hohmann, Peter Deuflhard, Andreas. Numerical analysis in modern scientific computing : an introduction (en alemany). 2nd ed.. Nova York: Springer, 2003. ISBN 9780387954103. 
• Krause, Prof.Dr.Rolf «Praktische Mathematik» (en alemany). Universität Bonn. Rheinischen Friedrich-Wilhelms-Universität Bonn [Consulta: 4 agost 2013].^{[Enllaç no actiu]}
• Hermann, von Martin. Numerische Mathematik (en alemany). München [u.a.]: Oldenbourg, 2001. ISBN 3-486-25558-4. 
• Hermann, von Martin. Numerik gewöhnlicher Differentialgleichungen : Anfangs- und Randwertprobleme (en alemany). 1. Aufl.. München [u.a.]: Oldenbourg, 2004. ISBN 3-486-27606-9.