Número de condición

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Medición de la sensibilidad de una función al cambio de entrada o error

En el análisis numérico, el estado de una función mide cuánto el valor de salida de la función puede cambiar para un pequeño cambio en el argumento de entrada. Esto se utiliza para medir cuán sensible es una función a los cambios o errores en la entrada, y cuánto error en la salida resulta de un error en la entrada. Muy a menudo, uno está resolviendo el problema inverso: dado $f(x) = y,$ uno está resolviendo para x, y por lo tanto el número de condición del inverso (local) debe ser utilizado. En regresión lineal, el número de condición de la matriz de momento se puede utilizar como un diagnóstico para la multicollinearidad.

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 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 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 una serie 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 los problemas e identifican algoritmos estables hacia atrás conocidos.

Como regla de pulgar, si el número de condición $kappa(A) = 10^k$ Entonces puedes perder hasta $k$ dígitos de precisión sobre lo que se perdería al 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 se limita con una estimación (cuyo valor calculado depende de la elección de la norma para medir la inexactitud).

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

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

En este contexto, el absoluto condición número 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 relativo 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 de cuán imprecisa 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 del algoritmo o precisión de punto flotante de la computadora utilizada para resolver el sistema correspondiente. En particular, se debe pensar en el número de condición como (muy aproximadamente) la tasa a la que cambiará la solución x 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 de manera más precisa como la proporción máxima del error relativo en x al error relativo en b.

Sea e el error en b. Asumiendo 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}eright|}{left|A^{-1}bright|}}/{frac {|e|}{|b|}}={frac {left|A^{-1}eright|}{|e|}}{frac {|b|}{left|A^{-1}bright|}}.}

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

{displaystyle {begin{aligned}max _{e,bneq 0}left{{frac {left|A^{-1}eright|}{|e|}}{frac {|b|}{left|A^{-1}bright|}}right}&=max _{eneq 0}left{{frac {left|A^{-1}eright|}{|e|}}right},max _{bneq 0}left{{frac {|b|}{left|A^{-1}bright|}}right}\&=max _{eneq 0}left{{frac {left|A^{-1}eright|}{|e|}}right},max _{xneq 0}left{{frac {|Ax|}{|x|}}right}\&=left|A^{-1}right|,|A|.end{aligned}}}

La misma definición se usa para cualquier norma consistente, es decir, una que satisface

{displaystyle kappa (A)=left|A^{-1}right|,left|Aright|geq left|A^{-1}Aright|=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, lo que significa que 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 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 por la acumulación de 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 no Se puede esperar que el algoritmo encuentre 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 $|cdot |$ es la norma matriz inducida por el (vector) Norma euclidiana (a veces conocida como la L² norma y generalmente denotado $|cdot |_{2}$ ), entonces

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

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

Si $A$ es normal, entonces ${displaystyle kappa (A)={frac {left|lambda _{text{max}}(A)right|}{left|lambda _{text{min}}(A)right|}},}$ Donde ${displaystyle lambda _{text{max}}(A)}$ y ${displaystyle lambda _{text{min}}(A)}$ son máximos y mínimos (por moduli) eigenvalues de $A$ respectivamente.
Si $A$ es unitario, entonces ${displaystyle kappa (A)=1.}$

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

Si $|cdot |$ es norma de matriz inducida por $L^{infty }$ (vector) norm y $A$ es triangular inferior no-singular (es decir, ${displaystyle a_{ii}neq 0}$ para todos $i$ ), entonces

{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 calculable en la práctica, cuando el problema a resolver implica un álgebra no lineal, 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, se dice que la matriz está mal condicionada. En la práctica, dicha matriz es casi singular y el cálculo de su inversa, 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 según el punto; en algunos casos, se puede usar el número de condición máximo (o supremo) 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 diferente $f$ en una variable como función ${displaystyle left|xf'/fright|}$ . Evaluado en un punto $x$ , esto es

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

Más elegantemente, esto se puede entender como (el valor absoluto de) la relación del derivado logarítmico de $f$ , que es $(log f)' = f'/f$ , y el derivado logarítmico $x$ , que es ${displaystyle (log x)'=x'/x=1/x}$ , rendimiento de una relación ${displaystyle xf'/f}$ . Esto se debe a que el derivado logarítmico es la tasa infinitesimal de cambio relativo en una función: es el derivativo $f'$ escalada por el valor $f$ . 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 infinitesimal en la entrada pueden cambiar la salida de cero a positivo o negativo, dando una relación con cero en el denominador, por lo tanto el cambio relativo infinito.

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

{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 línea secante), y al tomar 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 significado aritmético de funciones trascendentales. Algunos importantes se dan a continuación:

Nombre	Signatura	Estado
Adición / resta	${displaystyle x+a}$	${displaystyle left\|{frac {x}{x+a}}right\|}$
Multiplicación de escalar	${displaystyle ax}$	$1$
División	${displaystyle 1/x}$	$1$
Polynomial	$x^{n}$	${displaystyle \|n\|}$
Función exponencial	$e^{x}$	$\|x\|$
Función de logaritmo natural	$ln(x)$	${displaystyle left\|{frac {1}{ln(x)}}right\|}$
Función sine	$sin(x)$	$\|xcot(x)\|$
Función cosina	$cos(x)$	$\|xtan(x)\|$
Función tangente	$tan(x)$	$\|x(tan(x)+cot(x))\|$
Función inversa del pecado	$arcsin(x)$	$frac{x}{sqrt{1-x^2}arcsin(x)}$
Función cosina inversa	$arccos(x)$	${displaystyle {frac {\|x\|}{{sqrt {1-x^{2}}}arccos(x)}}}$
Función curvo inversa	$arctan(x)$	$frac{x}{(1+x^2)arctan(x)}$

Varias variables

Los números de condición se pueden definir para cualquier función $f$ mapear sus datos de algún dominio (por ejemplo, un $m$ - tropiezo de números reales $x$ ) en un codomain (por ejemplo, un $n$ - tropiezo de números reales $f(x)$ ), donde tanto el dominio como el codomain 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 las dificultades de sensibilidad y posible precisión de numerosos problemas computacionales, por ejemplo, hallazgos de raíz polinomio o valores de cálculo.

El número de condición $f$ en un momento $x$ (específicamente, su Estado relativo) se define entonces como la relación máxima del cambio fraccional en $f(x)$ a cualquier cambio fraccional en $x$ , en el límite donde el cambio $delta x$ dentro $x$ se hace infinitamente pequeño:

{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 $|cdot |$ es una norma en el dominio/codominio de $f$ .

Si $f$ es diferente, esto es equivalente a:

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

Donde $J(x)$ denota la matriz Jacobiana de derivados parciales de $f$ a $x$ , y ${displaystyle |J(x)|}$ es la norma inducida en la matriz.

Contenido relacionado

Más resultados...