Estabilitat numèrica

De Viquipèdia
Dreceres ràpides: navegació, cerca

En el camp de l'anàlisi numèrica, hom diu que un algorisme és numèricament estable 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 mesura 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ó[modifica | modifica el codi]

Donat un algorisme f(x), on x són les dades d'entrada i ε l'error en les dades d'entrada, diem 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

x - (x + \varepsilon) \simeq f(x) - f(x + \varepsilon)

i numèricament estable per l'error relatiu si

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

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

x - (x + \varepsilon) \ll f(x) - f(x + \varepsilon)\

i numèricament inestable per l'error relatiu si

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

Relació entre l'estabilitat i el nombre de condició[modifica | modifica el codi]

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

\|f(x) - \tilde f(\tilde x)\|.

Aplicant la desigualtat triangular, tenim:

\|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 \|f(x) - f(\tilde x)\| la condició del problema, i per \|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[modifica | modifica el codi]

Anàlisi cap endavant[modifica | modifica el codi]

Diem que un algorisme és estable si existeix una constant \sigma \in \mathbb{R} tal que

\|f(\tilde x) - \tilde f(\tilde x) \| \leq \kappa\sigma \varepsilon

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

Anàlisi cap enrere[modifica | modifica el codi]

El segon mètode d'anàlisi dels algorismes fou desenvolupat per James H. Wilkinson. Moltes vegades, hom coneix una fita superior \varepsilon per l'error relatiu \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 enrera, que hom anomena error cap enrera. La definició formal de l'error cap enrera de l'algorisme \tilde f per les dades d'entrada (possiblement arrodonides) \tilde x (on \|\tilde x\|\neq 0) és:


\varepsilon_{\rm R}(\tilde x) := \inf\left\{\frac{\|\hat x-\tilde x\|}{\|\tilde x\|}\mid \hat x \in\operatorname{Dom} f\;\wedge\; f(\hat x)=\tilde f(\tilde x) \right\},

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

Un algorisme és estable cap enrera si l'error cap enrera relatiu per tot \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 C>1 tal que,

per tot 
\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 enrera relatiu.

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

Aplicacions[modifica | modifica el codi]

Addició[modifica | modifica el codi]

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[modifica | modifica el codi]

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  \sigma .

Equacions diferencials ordinàries[modifica | modifica el codi]

En aquest cas podem 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 \xi=\Delta t \cdot \lambda pels quals el mètode de resolució del test de Dahlquist

y'=\lambda y, \quad y(0)=1

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

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

Equacions en derivades parcials[modifica | modifica el codi]

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 propociona condicions necessàries.

Referències[modifica | modifica el codi]

  1. III, / Lloyd N. Trefethen, David Bau. Numerical linear algebra.. 3. print.. SIAM: Society for Industrial and Applied Mathematics, 1996, p. 104. ISBN 978-0898713619. 

Bibliografia[modifica | modifica el codi]

  • 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. 2nd ed. (en alemany). New 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].
  • 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. 1. Aufl. (en alemany). München [u.a.]: Oldenbourg, 2004. ISBN 3-486-27606-9.