Número de condición - Condition number

En el campo del 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 para un pequeño cambio en el argumento de entrada. Esto se usa 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. Con mucha frecuencia, uno está resolviendo el problema inverso: dado uno está resolviendo para x, y por lo tanto se debe usar el número de condición de la inversa (local). En la regresión lineal, el número de condición de la matriz de momentos se puede utilizar como diagnóstico de multicolinealidad . ${\ Displaystyle f (x) = y,}$

El número de condición es una aplicación de la derivada y se define formalmente como el valor del cambio relativo asintótico en el peor de los casos en la salida 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 en á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.

Se dice que un problema con un número bajo de condiciones está bien acondicionado , mientras que un problema con un número alto de condiciones está mal acondicionado . En términos no matemáticos, un problema mal condicionado es aquel en el que, para un pequeño cambio en las entradas (las variables independientes ), hay un gran cambio en la respuesta o variable dependiente . Esto significa que la solución / respuesta correcta a la ecuación se vuelve difícil de encontrar. El número de condición es una propiedad del problema. Junto con el problema hay cualquier número de algoritmos que se pueden usar 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 estable hacia atrás resuelva con precisión problemas bien condicionados. Los libros de texto de análisis numérico dan fórmulas para los números de condición de problemas e identifican algoritmos estables hacia atrás 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. Sin embargo, el número de condición no da el valor exacto de la máxima inexactitud que puede ocurrir en el algoritmo. Por lo general, 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 x , el error absoluto es y el error relativo es . ${\ Displaystyle f}$${\ Displaystyle {\ tilde {f}}}$${\ Displaystyle \ | \ delta f (x) \ |: = \ left \ | f (x) - {\ tilde {f}} (x) \ right \ |}$${\ Displaystyle \ left \ | f (x) - {\ tilde {f}} (x) \ right \ | / \ left \ | f (x) \ right \ |}$

En este contexto, el número de condición absoluto de un problema f es

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

y el número de condición relativa es

${\ 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 sobre 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 de punto flotante de la computadora utilizada para resolver el sistema correspondiente. En particular, uno debería pensar en el número de condición como (muy aproximadamente) la tasa 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 error pequeño en b puede causar un error grande 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 con mayor precisión 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 razón del error relativo en la solución al 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 (por no nulo b y e ) se ve entonces a ser el producto de las dos normas de operador como sigue:

${\ Displaystyle {\ begin {alineado} \ 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 {\ izquierda \ | A ^ {- 1} e \ derecha \ |} {\ | e \ |}} \ derecha \} \, \ max _ {x \ neq 0} \ izquierda \ {{\ frac {\ | Ax \ |} {\ | x \ |}} \ right \} \\ & = \ left \ | A ^ {- 1} \ right \ | \, \ | A \ |. \ end {alineado}}}$

La misma definición se usa para cualquier norma consistente , es decir, una 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 solo 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, no significa que el algoritmo convergerá rápidamente a esta solución, solo que no divergerá arbitrariamente debido a la inexactitud en 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.

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 ningún algoritmo puede ser 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 es la norma definida en el espacio de secuencia sumable al cuadrado ℓ ² (que coincide con la distancia habitual en un espacio euclidiano estándar y generalmente se denota 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áximo y mínimo 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 es la norma definida en el espacio de secuencia ℓ ^∞ de todas las secuencias acotadas (que coincide con el máximo de distancias medidas en proyecciones en los subespacios base y generalmente se denota por ), y es triangular inferior no singular (es decir, para todos ), entonces ${\ Displaystyle \ | \ cdot \ |}$${\ Displaystyle \ | \ cdot \ | _ {\ 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 con secuencias sumables al cuadrado, pero se puede evaluar más fácilmente (y este es a menudo el único número de condición que se puede calcular de manera práctica, cuando el problema a resolver implica un problema no lineal). álgebra , 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 mucho mayor que uno, la matriz está bien acondicionada, lo que significa que su inversa se puede calcular con buena precisión. Si el número de condición es muy grande, se dice que la matriz está mal acondicionada. Prácticamente, tal matriz es casi singular, y el cálculo de su inverso, o la solución de un sistema lineal de ecuaciones, es propenso a grandes errores numéricos. Una matriz que no es invertible tiene un número de condición igual a infinito.

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 con el punto; en algunos casos, se puede usar el número de condición máximo (o superior) sobre el dominio de la función o el 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 mayor 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 |.}$

De manera más elegante, esto puede entenderse como (el valor absoluto de) la relación de 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 los cambios infinitesimales en la entrada pueden cambiar la salida de cero a positivo o negativo, lo que produce una relación con cero en el denominador, por lo tanto, relativa infinita. cambio. ${\ 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 los rendimientos de la relación ${\ 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 en el cálculo de cifras significativas y pueden calcularse inmediatamente a partir de la derivada; ver aritmética de significación de funciones trascendentales . A continuación se dan algunos importantes:

Nombre	Símbolo	Número de condición
Suma resta	${\ Displaystyle x + a}$	${\ Displaystyle \ left | {\ frac {x} {x + a}} \ right |}$
Multiplicación escalar	${\ Displaystyle ax}$	${\ Displaystyle 1}$
División	${\ Displaystyle 1 / x}$	${\ Displaystyle 1}$
Polinomio	${\ Displaystyle x ^ {n}}$	${\ Displaystyle | n |}$
Funcion exponencial	${\ Displaystyle e ^ {x}}$	${\ Displaystyle | x |}$
Función de logaritmo natural	${\ Displaystyle \ ln (x)}$	${\ Displaystyle \ left | {\ frac {1} {\ ln (x)}} \ right |}$
Función seno	${\ Displaystyle \ sin (x)}$	${\ Displaystyle | x \ cot (x) |}$
Función coseno	${\ Displaystyle \ cos (x)}$	${\ Displaystyle | x \ tan (x) |}$
Función tangente	${\ Displaystyle \ tan (x)}$	${\ Displaystyle | x (\ tan (x) + \ cot (x)) |}$
Función de seno inverso	${\ Displaystyle \ arcsin (x)}$	${\ Displaystyle {\ frac {x} {{\ sqrt {1-x ^ {2}}} \ arcsin (x)}}}$
Función coseno inverso	${\ Displaystyle \ arccos (x)}$	${\ Displaystyle {\ frac {| x |} {{\ sqrt {1-x ^ {2}}} \ arccos (x)}}}$
Función de tangente inversa	${\ Displaystyle \ arctan (x)}$	${\ Displaystyle {\ frac {x} {(1 + x ^ {2}) \ arctan (x)}}}$

Varias variables

Los números de condición se pueden definir para cualquier función que mapee sus datos de algún dominio (por ejemplo, una -tupla de números reales ) en 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 ) se define entonces como la relación máxima entre el cambio fraccionario en y cualquier cambio fraccionario en , en el límite donde el cambio en se vuelve infinitesimalmente pequeño: ${\ 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 es una norma sobre el dominio / codominio de . ${\ Displaystyle \ | \ cdot \ |}$${\ Displaystyle f}$

Si es diferenciable, equivale a: ${\ Displaystyle f}$

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

donde denota la matriz jacobiana de derivadas parciales de a , 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
• Matriz de Hilbert
• Problema mal planteado
• Valor singular

Referencias

Otras lecturas

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

enlaces externos

• Número de condición de una matriz en el Instituto de métodos numéricos holísticos
• Función de biblioteca MATLAB para determinar el número de condición
• Número de condición - Enciclopedia de las matemáticas
• ¿Quién inventó el número de condición de matriz? por Nick Higham