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óModifica

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

 

i numèricament estable per l'error relatiu si

 .

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

 

i numèricament inestable per l'error relatiu si

 .

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

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

 

Aplicant la desigualtat triangular, s'obté:

 

Hom acostuma a designar per   la condició del problema, i per   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èricaModifica

Anàlisi cap endavantModifica

Es diu que un algorisme és estable si existeix una constant   tal que

 

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

Anàlisi cap enrereModifica

El segon mètode d'anàlisi dels algorismes fou desenvolupat per James H. Wilkinson. Moltes vegades, hom coneix una fita superior   per l'error relatiu   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   per les dades d'entrada (possiblement arrodonides)   (on  ) és:

 

on   és el domini del problema.

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

per tot  

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]

AplicacionsModifica

AddicióModifica

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 diferencialsModifica

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  .

Equacions diferencials ordinàriesModifica

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   pels quals el mètode de resolució del test de Dahlquist

 

per increments   é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 parcialsModifica

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ènciesModifica

  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.  Arxivat 2014-01-24 a Wayback Machine.

BibliografiaModifica

  • 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].
  • 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.