Nombre de condició

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

En l'àmbit de l'anàlisi numèrica, el nombre de condició d'una funció respecte a un argument mesura com canvia el resultat de la funció per un canvi petit en l'argument d'entrada. Això s'utilitza per definir la sensibilitat d'una funció respecte errors en l'entrada, i quant error s'obté en el resultat arran d'un error en l'entrada. Molt freqüentment, hom es troba amb el problema de trobar una funció inversa – donada f(x) = y, volem resoldre per x, i per tant hom ha d'emprar el nombre de condició de la inversa (local).

El nombre de condició és una aplicació de la derivada, i formalment es defineix com el valor absolut del canvi relatiu del resultat en el cas pitjor asimptòtic, respecte a un canvi relatiu en l'entrada. La "funció" és la solució d'un problema i els "arguments" en són les dades. El nombre de condició sovint s'aplica en qüestions d'àlgebra lineal, on la derivada és senzilla de calcular, però l'error pot aparèixer en diferents direccions, i es calcula segons la geometria de la matriu. Més generalment, es poden definir els nombres de condició per funcions no lineals en diverses variables.

Un problema amb un nombre de condició baix s'anomena ben condicionat, mentre que un problema amb un nombre de condició alt s'anomena mal condicionat. El nombre de condició és una propietat del problema. Conjuntament amb el problema existeixen els algorismes per resoldre'l, és a dir, per trobar-ne la solució. Alguns algorismes tenen una propietat anomenada estabilitat numèrica. En general, hom espera que un algorisme amb estabilitat numèrica pugui resoldre amb precisió problemes ben condicionats. Alguns tractats d'anàlisi numèrica proporcionen fórmules pels nombres de condició dels problemes i identifiquen algorismes numèricament estables.

Com a regla general, si el nombre de condició és \kappa(A) = 10^k, aleshores hom pot perdre fins a k dígits significatius pel fet d'emprar un cert mètode numèric, degut a la pèrdua de precisió dels càlculs aritmètics.[1] Tot i això, el nombre de condició no proporciona el valor exacte de la màxima imprecisió que podem tenir en l'algorisme. Generalment, només estableix una fita amb una estimació de l'error (el valor calculat del qual depèn de l'elecció de la norma emprada per mesurar la imprecisió).

Matrius[modifica | modifica el codi]

Per exemple, el nombre de condició associat a l'equació lineal Ax = b proporciona una fita sobre la imprecisió de la solució x si en donem una aproximació. Notem que això és abans dels efectes dels errors d'arrodoniment; el nombre de condició és una propietat de la matriu, no de l'algorisme ni de la precisió en coma flotant de l'ordinador emprat per resoldre el sistema d'equacions. En particular, hom ha de pensar en el nombre de condició com (de forma grollera) la taxa de canvi de la solució x respecte a un canvi en b. Així, si el nombre de condició és gran, encara que hi hagi un error petit en b podem tenir un error gran en x. D'altra banda, si el nombre de condició és petit, llavors l'error de x no serà gaire més gran que l'error de b.

Hom defineix de forma més precisa el nombre de condició com el quocient màxim de l'error relatiu de x entre l'error relatiu en b.

Sigui e l'error en b. Assumint que A és una matriu quadrada, l'error de la solució A−1b és A−1e. El quocient de l'error relatiu de la solució entre l'error relatiu de b és

 \frac{ \left\Vert A^{-1} e \right\Vert / \left\Vert A^{-1} b \right\Vert }{ \left\Vert e \right\Vert / \left\Vert b \right\Vert } .

Això es pot transformar fàcilment en

 \left( \left\Vert A^{-1} e \right\Vert / \left\Vert e \right\Vert \right) \cdot \left( \left\Vert b \right\Vert / \left\Vert A^{-1} b \right\Vert \right) .

Hom pot veure fàcilment que el valor màxim (per b i e no-nuls) és el producte de les dues normes operacionals:

 \kappa(A) = \left\Vert A^{-1} \right\Vert \cdot \left\Vert A \right\Vert .

La mateixa definició s'usa per qualsevol norma consistent, és a dir, que satisfaci

 \kappa(A) \ge 1 .\,

Quan el nombre de condició és exactament 1, llavors l'algorisme pot trobar una aproximació de la solució amb una precisió arbitrària. Però això no vol dir que l'algorisme convergeixi ràpidament a aquesta solució; només que no divergirà arbitràriament per causa d'imprecisions en les dades, sempre que l'error introduït per l'algorisme no divergeixi per ell mateix per haver acumulat errors d'arrodoniment intermedis.

El nombre de condició també pot ser infinit; en aquest cas, l'algorisme no trobarà cap solució fiable al problema, ni tan sols una aproximació feble (independentment de l'ordre de magnitud) amb una precisió raonable i demostrable.

És clar que aquesta definició depèn de la norma escollida:

  • Si  \left\| \cdot \right\| és la norma (denotada usualment com  \left\| \cdot \right\|_2 ) definida en l'espai de les successions de quadrat sumable 2 (que coincideix amb la distància usual en un espai cartesià continu i isotròpic), llavors
     \kappa(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} ,
    on  \sigma_{\max}(A) i \sigma_{\min}(A) són els valors singulars màxim i mínim de A, respectivament.
    Per tant
    Aquest nombre apareix tan freqüentment en àlgebra lineal numèrica que rep el nom distingit de nombre de condició d'una matriu.
  • Si  \left\| \cdot \right\| és la norma (denotada usualment com  \left\| \cdot \right\|_\infty ) definida en l'espai de les successions fitades (que coincideix amb la distància no-lineal mesurada com el màxim de les distàncies mesurades en les projeccions en els subespais base, sense la condició que l'espai sigui isotròpic ni tan sols lineal, sinó només continu; aquesta norma es pot definir en qualsevol Espai de Banach), i A és triangular inferior no-singular (és a dir,  \forall i, a_{ii} \ne 0 \,) llavors
     \kappa(A) \geq \frac{\max_i(|a_{ii}|)}{\min_i(|a_{ii}|)} .
    El nombre de condició calcular amb aquesta norma normalment és més gran que el nombre de condició calculat segons la norma de les successions de quadrat sumable, però hom pot avaluar-lo de forma més senzilla (i usualment és l'únic nombre de condició calculable, quan el problema a resoldre implica una àlgebra no-lineal, per exemple quan s'aproximen funcions irracionals i transcendents mitjançant mètodes numèrics).

Si el nombre de condició és proper a 1, la matriu està ben condicionada, la qual cosa significa que hom pot calcular-ne la inversa amb una bona precisió. Si el nombre de condició és gran, llavors hom diu que la matriu és mal condicionada. A la pràctica, una matriu mal condicionada és gairebé com una matriu singular, i el càlcul de la seva inversa, o equivalentment la solució a un sistema d'equacions lineals, és propens a errors numèrics grans. Una matriu que no és invertible té un nombre de condició igual a infinit.

Cas no lineal[modifica | modifica el codi]

També es poden definir els nombres de condició per funcions no lineals, i es poden calcular mitjançant anàlisi matemàtica. El nombre de condició varia segons el punt; en alguns casos es pot usar el nombre de condició màxim (o el suprem) sobre el domini de la funció o del problema com a nombre de condició global, mentre que en altres casos el nombre de condició en un punt particular té un interès especial.

Una variable[modifica | modifica el codi]

Vegeu també: Funció transcendent

El nombre de condició d'una funció diferenciable f en una variable com a funció és \left|xf'/f\right|. Avaluat al punt x tenim:

\left|\frac{xf'(x)}{f(x)}\right|.

D'una forma més elegant, hom pot interpretar això com (el valor absolut de) el quocient entre la derivada logarítmica de f, que és (\log f)' = f'/f i la derivada logarítmica de x, que és (\log x)' = x'/x = 1/x, resultant en un quocient de xf'/f. Això és així perquè la derivada logarítmica és la taxa infinitesimal de canvi d'una funció: és la derivada f' escalada pel valor de f. Notem que si una funció s'anul·la en un punt, llavors el seu nombre de condició en aquest punt és infinit, ja que un canvi infinitesimal en la variable pot canviar el resultat de 0 a positiu o negatiu, donant així un quocient amb un zero al denominador, i per tant un canvi relatiu infinit.

Més concretament, donat un canvi petit \Delta x en x, el canvi relatiu en x és [(x + \Delta x) - x]/x = (\Delta x)/x, mentre que el canvi relatiu en f(x) és [f(x + \Delta x) - f(x)]/f(x). Prenent el quocient obtenim:

\frac{[f(x + \Delta x) - f(x)]/f(x)}{(\Delta x)/x}
= \frac{x}{f(x)}\frac{f(x + \Delta x) - f(x)}{(x + \Delta x) - x}.

L'últim terme és el coeficient diferencial (el pendent de la recta secant), i prenent el límit tenim la derivada.

Els nombres de condició d'algunes funcions elementals són particularment importants quan calculem dígits significatius, i es poden calcular immediatament a partir de la derivada. Aquí en donem uns exemples destacats:

  • Funció exponencial e^x: x
  • Funció logaritme natural \ln(x): \frac{1}{\ln(x)}
  • Funció sinus \sin(x): x\cot(x)
  • Funció cosinus \cos(x): x\tan(x)
  • Funció tangent \tan(x): x(\tan(x)+\cot(x))
  • Funció arcsinus \arcsin(x): \frac{x}{\sqrt{1-x^2}\arcsin(x)}
  • Funció arccosinus \arccos(x): \frac{x}{\sqrt{1-x^2}\arccos(x)}
  • Funció arctangent \arctan(x): \frac{x}{(1+x^2)\arctan(x)}

Més d'una variable[modifica | modifica el codi]

Hom pot definir nombres de condició per qualsevol funció ƒ que porti el seu argument des d'un domini (per exemple, una m-tupla de nombres reals x) dins un codomini [per exemple, una n-tupla de nombres reals ƒ(x)], on tant el domini com el codomini són espais de Banach. Aquests nombres de condició expressen com és de sensible la funció a petits canvis (o petits errors) en els seus arguments. Això és crucial a l'hora de determinar la sensibilitat i les potencials dificultats de precisió no nombrosos problemes computacionals, com per exemple resolució d'equacions polinomials o com el càlcul de valors propis.

El nombre de condició de ƒ en un punt x (específicament, el seu nombre de condició relatiu[2]) llavors es defineix com el quocient màxim entre el canvi fraccional en ƒ(x) entre qualsevol canvi fraccional en x; en el límit, quan el canvi δx en x esdevé infinitament petit:[2]

\lim_{ \varepsilon \to 0^+ }
        \sup_{ \Vert \delta x \Vert \leq \varepsilon } 
        \left[  \frac{ \left\Vert f(x + \delta x) - f(x)\right\Vert }{ \Vert f(x) \Vert }  
              / \frac{ \Vert \delta x \Vert }{ \Vert x \Vert }
        \right],

on \Vert \cdot \Vert és una norma en el domini/codomini de ƒ(x).

Si ƒ és diferenciable, això és equivalent a:[2]

\frac{\Vert J \Vert}{ \Vert f(x) \Vert / \Vert x \Vert},

on J denota el Jacobià de derivades parcials de ƒ i \Vert J \Vert és la norma induïda sobre la matriu.

Referències[modifica | modifica el codi]

  1. Numerical Mathematics and Computing, by Cheney and Kincaid.
  2. 2,0 2,1 2,2 L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM, 1997).

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]