Número de condición

Sensibilidad de la función al cambio de argumento.

En el análisis numérico , el número de condición de una función mide cuánto puede cambiar el valor de salida de la función con un pequeño cambio en el argumento de entrada. Esto se utiliza para medir qué tan sensible es una función a cambios o errores en la entrada, y cuánto error en la salida resulta de un error en la entrada. Muy frecuentemente, uno está resolviendo el problema inverso: dado que está resolviendo x, y por lo tanto se debe usar el número de condición de la inversa (local). ^{[1] [2]} ${\displaystyle f(x)=y,}$

El número de condición se deriva de la teoría de la propagación de la incertidumbre y se define formalmente como el valor del cambio relativo asintótico en el peor de los casos en la producción para un cambio relativo en la entrada. La "función" es la solución de un problema y los "argumentos" son los datos del problema. El número de condición se aplica con frecuencia a preguntas de álgebra lineal , en cuyo caso la derivada es sencilla pero el error podría estar en muchas direcciones diferentes y, por lo tanto, se calcula a partir de la geometría de la matriz. De manera más general, los números de condición se pueden definir para funciones no lineales en varias variables.

Un problema con un número de condición bajo se dice que está bien condicionado , mientras que un problema con un número de condición alto se dice que está mal condicionado . En términos no matemáticos, un problema mal condicionado es aquel en el que, por un pequeño cambio en las entradas (las variables independientes ), hay un gran cambio en la respuesta o variable dependiente . Esto significa que resulta difícil encontrar la solución/respuesta correcta a la ecuación. El número de condición es una propiedad del problema. Junto con el problema hay cualquier número de algoritmos que puedan usarse para resolver el problema, es decir, para calcular la solución. Algunos algoritmos tienen una propiedad llamada estabilidad hacia atrás ; en general, se puede esperar que un algoritmo retroestable resuelva con precisión problemas bien condicionados. Los libros de texto de análisis numérico brindan fórmulas para los números de condición de los problemas e identifican algoritmos retroestables conocidos.

Como regla general, si la condición es número , entonces puede perder hasta dígitos de precisión además de lo que se perdería con el método numérico debido a la pérdida de precisión de los métodos aritméticos. ^[3] Sin embargo, el número de condición no proporciona el valor exacto de la máxima inexactitud que puede ocurrir en el algoritmo. Generalmente simplemente lo limita con una estimación (cuyo valor calculado depende de la elección de la norma para medir la inexactitud). ${\displaystyle \kappa (A)=10^{k}}$ ${\displaystyle k}$

Definición general en el contexto del análisis de errores.

Dado un problema y un algoritmo con una entrada y una salida, el error es el error absoluto y el error relativo es ${\displaystyle f}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle x}$ ${\displaystyle {\tilde {f}}(x),}$ ${\displaystyle \delta f(x):=f(x)-{\tilde {f}}(x),}$ ${\displaystyle \|\delta f(x)\|=\left\|f(x)-{\tilde {f}}(x)\right\|}$ ${\displaystyle \|\delta f(x)\|/\|f(x)\|=\left\|f(x)-{\tilde {f}}(x)\right\|/\|f(x)\|.}$

En este contexto, el número de condición absoluto de un problema es ^{[ se necesita aclaración ]} ${\displaystyle f}$

${\displaystyle \lim _{\varepsilon \rightarrow 0^{+}}\,\sup _{\|\delta x\|\,\leq \,\varepsilon }{\frac {\|\delta f(x)\|}{\|\delta x\|}}}$

y el número de condición relativo es ^{[ se necesita aclaración ]}

${\displaystyle \lim _{\varepsilon \rightarrow 0^{+}}\,\sup _{\|\delta x\|\,\leq \,\varepsilon }{\frac {\|\delta f(x)\|/\|f(x)\|}{\|\delta x\|/\|x\|}}.}$

matrices

Por ejemplo, el número de condición asociado con la ecuación lineal Ax  =  b da un límite de cuán inexacta será la solución x después de la aproximación. Tenga en cuenta que esto es antes de que se tengan en cuenta los efectos del error de redondeo ; El condicionamiento es una propiedad de la matriz , no el algoritmo o la precisión del punto flotante de la computadora utilizada para resolver el sistema correspondiente. En particular, uno debería pensar que el número de condición es (muy aproximadamente) la velocidad a la que la solución x cambiará con respecto a un cambio en b . Por lo tanto, si el número de condición es grande, incluso un pequeño error en b puede causar un gran error en x . Por otro lado, si el número de condición es pequeño, entonces el error en x no será mucho mayor que el error en b .

El número de condición se define más precisamente como la relación máxima entre el error relativo en x y el error relativo en b .

Sea e el error en b . Suponiendo que A es una matriz no singular , el error en la solución A ⁻¹ b es A ⁻¹ e . La relación entre el error relativo en la solución y el error relativo en b es

${\displaystyle {\frac {\left\|A^{-1}e\right\|}{\left\|A^{-1}b\right\|}}/{\frac {\|e\|}{\|b\|}}={\frac {\left\|A^{-1}e\right\|}{\|e\|}}{\frac {\|b\|}{\left\|A^{-1}b\right\|}}.}$

El valor máximo (para b y e distintos de cero ) se considera entonces como el producto de las dos normas del operador de la siguiente manera:

${\displaystyle {\begin{aligned}\max _{e,b\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}{\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right\}&=\max _{e\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}\right\}\,\max _{b\neq 0}\left\{{\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right\}\\&=\max _{e\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}\right\}\,\max _{x\neq 0}\left\{{\frac {\|Ax\|}{\|x\|}}\right\}\\&=\left\|A^{-1}\right\|\,\|A\|.\end{aligned}}}$

La misma definición se utiliza para cualquier norma consistente , es decir, aquella que satisface

${\displaystyle \kappa (A)=\left\|A^{-1}\right\|\,\left\|A\right\|\geq \left\|A^{-1}A\right\|=1.}$

Cuando el número de condición es exactamente uno (lo que sólo puede suceder si A es un múltiplo escalar de una isometría lineal ), entonces un algoritmo de solución puede encontrar (en principio, es decir, si el algoritmo no introduce errores propios) una aproximación de la solución. cuya precisión no es peor que la de los datos.

Sin embargo, esto no significa que el algoritmo convergerá rápidamente a esta solución, sólo que no divergirá arbitrariamente debido a la inexactitud de los datos de origen (error hacia atrás), siempre que el error hacia adelante introducido por el algoritmo no diverja también porque de acumular errores de redondeo intermedios. ^{[ se necesita aclaración ]}

El número de condición también puede ser infinito, pero esto implica que el problema está mal planteado (no posee una solución única y bien definida para cada elección de datos; es decir, la matriz no es invertible ) y no se puede crear ningún algoritmo. Se espera encontrar una solución confiable.

La definición del número de condición depende de la elección de la norma , como se puede ilustrar con dos ejemplos.

Si la norma matricial es inducida por la norma euclidiana (vectorial) (a veces conocida como norma L ² y típicamente denotada como ), entonces ${\displaystyle \|\cdot \|}$ ${\displaystyle \|\cdot \|_{2}}$

${\displaystyle \kappa (A)={\frac {\sigma _{\text{max}}(A)}{\sigma _{\text{min}}(A)}},}$

donde y son valores singulares máximos y mínimos de respectivamente. Por eso: ${\displaystyle \sigma _{\text{max}}(A)}$ ${\displaystyle \sigma _{\text{min}}(A)}$ ${\displaystyle A}$

• Si es normal entonces ${\displaystyle A}$
  $${\displaystyle \kappa (A)={\frac {\left|\lambda _{\text{max}}(A)\right|}{\left|\lambda _{\text{min}}(A)\right|}},}$$
  donde y son valores propios máximos y mínimos (por módulos) de respectivamente. ${\displaystyle \lambda _{\text{max}}(A)}$ ${\displaystyle \lambda _{\text{min}}(A)}$ ${\displaystyle A}$
• Si es unitario , entonces ${\displaystyle A}$ ${\displaystyle \kappa (A)=1.}$

El número de condición con respecto a L ² surge con tanta frecuencia en el álgebra lineal numérica que se le da un nombre: el número de condición de una matriz .

Si la norma matricial es inducida por la norma (vectorial) y es triangular inferior no singular (es decir, para todos ), entonces ${\displaystyle \|\cdot \|}$ ${\displaystyle L^{\infty }}$ ${\displaystyle A}$ ${\displaystyle a_{ii}\neq 0}$ ${\displaystyle i}$

${\displaystyle \kappa (A)\geq {\frac {\max _{i}{\big (}|a_{ii}|{\big )}}{\min _{i}{\big (}|a_{ii}|{\big )}}}}$

recordando que los valores propios de cualquier matriz triangular son simplemente las entradas diagonales.

El número de condición calculado con esta norma es generalmente mayor que el número de condición calculado en relación con la norma euclidiana , pero se puede evaluar más fácilmente (y este es a menudo el único número de condición prácticamente computable, cuando el problema a resolver implica una ecuación no lineal). álgebra ^{[ se necesita aclaración ]} , por ejemplo al aproximar funciones o números irracionales y trascendentales con métodos numéricos).

Si el número de condición no es significativamente mayor que uno, la matriz está bien condicionada , lo que significa que su inversa se puede calcular con buena precisión. Si el número de condición es muy grande, entonces se dice que la matriz está mal condicionada . En la práctica, una matriz de este tipo es casi singular y el cálculo de su inversa, o solución de un sistema lineal de ecuaciones, es propenso a grandes errores numéricos.

A menudo se dice que una matriz que no es invertible tiene un número de condición igual a infinito. Alternativamente, se puede definir como , donde está el pseudoinverso de Moore-Penrose . Para matrices cuadradas, esto desafortunadamente hace que el número de condición sea discontinuo, pero es una definición útil para matrices rectangulares, que nunca son invertibles pero aún se usan para definir sistemas de ecuaciones. ${\displaystyle \kappa (A)=\|A\|\|A^{\dagger }\|}$ ${\displaystyle A^{\dagger }}$

No lineal

Los números de condición también se pueden definir para funciones no lineales y se pueden calcular mediante cálculo . El número de condición varía según el punto; en algunos casos se puede utilizar el número de condición máximo (o supremo ) sobre el dominio de la función o dominio de la pregunta como un número de condición general, mientras que en otros casos el número de condición en un punto particular es de más interés.

una variable

El número de condición de una función diferenciable en una variable como función es . Evaluado en un punto , esto es ${\displaystyle f}$ ${\displaystyle \left|xf'/f\right|}$ ${\displaystyle x}$

${\displaystyle \left|{\frac {xf'(x)}{f(x)}}\right|=\left|{\frac {(\log f)'}{(\log x)'}}\right|.}$

Tenga en cuenta que este es el valor absoluto de la elasticidad de una función en economía.

De manera más elegante, esto puede entenderse como (el valor absoluto de) la relación entre la derivada logarítmica de , que es , y la derivada logarítmica de , que es , dando una relación de . Esto se debe a que la derivada logarítmica es la tasa infinitesimal de cambio relativo en una función: es la derivada escalada por el valor de . Tenga en cuenta que si una función tiene un cero en un punto, su número de condición en el punto es infinito, ya que cambios infinitesimales en la entrada pueden cambiar la salida de cero a positiva o negativa, produciendo una relación con cero en el denominador, por lo tanto infinita relativa. cambiar. ${\displaystyle f}$ ${\displaystyle (\log f)'=f'/f}$ ${\displaystyle x}$ ${\displaystyle (\log x)'=x'/x=1/x}$ ${\displaystyle xf'/f}$ ${\displaystyle f'}$ ${\displaystyle f}$

Más directamente, dado un pequeño cambio en , el cambio relativo en es , mientras que el cambio relativo en es . Tomando la relación se obtiene ${\displaystyle \Delta x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle [(x+\Delta x)-x]/x=(\Delta x)/x}$ ${\displaystyle f(x)}$ ${\displaystyle [f(x+\Delta x)-f(x)]/f(x)}$

${\displaystyle {\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}}={\frac {x}{f(x)}}{\frac {f(x+\Delta x)-f(x)}{\Delta x}}.}$

El último término es el cociente de diferencias (la pendiente de la recta secante ), y tomando el límite se obtiene la derivada.

Los números de condición de funciones elementales comunes son particularmente importantes al calcular cifras significativas y pueden calcularse inmediatamente a partir de la derivada. A continuación se detallan algunos importantes:

Varias variables

Los números de condición se pueden definir para cualquier función que mapee sus datos desde algún dominio (por ejemplo, una tupla de números reales ) a algún codominio (por ejemplo, una tupla de números reales ), donde tanto el dominio como el codominio son espacios de Banach . Expresan cuán sensible es esa función a pequeños cambios (o pequeños errores) en sus argumentos. Esto es crucial para evaluar la sensibilidad y las posibles dificultades de precisión de numerosos problemas computacionales, por ejemplo, la búsqueda de raíces polinomiales o el cálculo de valores propios . ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle f(x)}$

El número de condición de en un punto (específicamente, su número de condición relativo ^[4] ) se define entonces como la relación máxima entre el cambio fraccionario de in y cualquier cambio fraccionario de in , en el límite donde el cambio de in se vuelve infinitamente pequeño: ^{[4 ]} ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle \delta x}$ ${\displaystyle x}$

${\displaystyle \lim _{\varepsilon \to 0^{+}}\sup _{\|\delta x\|\leq \varepsilon }\left[\left.{\frac {\left\|f(x+\delta x)-f(x)\right\|}{\|f(x)\|}}\right/{\frac {\|\delta x\|}{\|x\|}}\right],}$

donde hay una norma sobre el dominio/codominio de . ${\displaystyle \|\cdot \|}$ ${\displaystyle f}$

Si es diferenciable, esto equivale a: ^[4] ${\displaystyle f}$

${\displaystyle {\frac {\|J(x)\|}{\|f(x)\|/\|x\|}},}$

donde denota la matriz jacobiana de derivadas parciales de at y es la norma inducida en la matriz. ${\displaystyle J(x)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle \|J(x)\|}$

Ver también

• Métodos numéricos para mínimos cuadrados lineales.
• Estabilidad numérica
• matriz de hilabert
• problema mal planteado
• Valor singular
• matriz de wilson

Referencias

1. Belsley, David A.; Kuh, Edwin ; Welsch, Roy E. (1980). "El número de condición". Diagnóstico de regresión: identificación de datos influyentes y fuentes de colinealidad . Nueva York: John Wiley & Sons. págs. 100-104. ISBN 0-471-05856-4.
2. Pesarán, M. Hashem (2015). "El problema de la multicolinealidad". Econometría de series temporales y datos de panel . Nueva York: Oxford University Press. págs. 67–72 [pág. 70]. ISBN 978-0-19-875998-0.
3. Cheney; Kincaid (2008). Matemáticas Numéricas y Computación. pag. 321.ISBN​ 978-0-495-11475-8.
4. Trefethen, LN; Bau, D. (1997). Álgebra lineal numérica. SIAM. ISBN 978-0-89871-361-9.

Otras lecturas

• Demmel, James (1990). "Matrices defectuosas más cercanas y geometría del mal condicionamiento". En Cox, MG; Hammarling, S. (eds.). Computación numérica confiable . Oxford: Prensa de Clarendon. págs. 35–55. ISBN 0-19-853564-3.

enlaces externos

• Número de condición de una matriz en el Holistic Numerical Methods Institute
• Función de biblioteca MATLAB para determinar el número de condición
• Número de condición - Enciclopedia de Matemáticas
• ¿Quién inventó el número de condición de Matrix? por Nick Higham