La ventaja de la descomposición LU en computación explícitamente el inverso

Question

Les voy a enseñar un curso de álgebra lineal en el otoño, y quiero motivar el tema de la matriz factorizations tales como la descomposición LU. Una pregunta natural que uno puede hacer es, ¿por qué importa esto cuando uno ya sabe cómo calcular $A^{-1}$ y se puede utilizar para solucionar $Ax=b$ sólo por la matriz-vector de la multiplicación? La respuesta estándar es que es que en la práctica uno debe (casi) nunca realmente invertir una matriz, debido a que incurren en menos de redondeo de error por backsubstituting una factorización como $LUx = b$ de realizar la multiplicación $x=A^{-1}b$.

Sin embargo, recientemente me encontré con la ponencia "¿qué tan precisa es inv(A)*b?" por Druinsky y Toledo (2012), donde argumentan que la sabiduría recibida es engañoso, y una solución de $x_{\text{inv}}=Vx$ obtenido utilizando un aproximado inverso $V\approx A^{-1}$ es normalmente cerca de la verdad $x$ como una solución de $x_{\text{LU}}$ obtenido por backsubstitution. Así que yo no estoy tan seguro acerca de la precisión numérica como una motivación para la descomposición LU como solía ser.

Hice algunos experimentos numéricos con el azar mal condicionado matrices en Matlab, basado en Druinsky y Toledo código en Segundos, de 6 de su papel. Parece que el avance de los errores de $\|x_{\text{inv}}-x\|$ $\|x_{\text{LU}}-x\|$ eran de hecho muy similar, pero el retroceso de error $\|Ax_{\text{inv}}-b\|$ podría ser mucho más grande que la de $\|Ax_{\text{LU}}-b\|$. También trabajé un pequeño ejemplo a mano: $$\begin{align} A &= \begin{bmatrix}1.00&2.01 \\ 1.01 & 2.03\end{bmatrix} \\ &= \underbrace{\begin{bmatrix}1.00 & 2.01 \\ 0 & -1.00\times10^{-4}\end{bmatrix}}_{L}\underbrace{\begin{bmatrix}1 & 0 \\ 1.01 & 1\end{bmatrix}}_{U} \\ y= {\underbrace{\begin{bmatrix}-2.03\times10^4 & 2.01\times10^4 \\ 1.01\times10^4 & -1.00\times10^4 \end{bmatrix}}_{A^{-1}}}^{-1}, \\ b &= \begin{bmatrix}1.01 \\ 1.02\end{bmatrix}. \end{align}$$ La solución exacta es $x=[-1, 1]^T$. Computación $A^{-1}b$ con tres dígitos decimales de precisión en los intermedios de los cálculos se obtiene el resultado de la $x_{\text{inv}} = [0, 0]^T$ debido a la catastrófica de la cancelación. La misma precisión en LU backsubstitution da $x_{\text{LU}} = [1.01, 0]^T$. Ambas soluciones se diferencian claramente de la verdadera solución a $x$ por un error en el orden de $10^0$, pero $Ax_{\text{LU}}$ corresponde a $b$ a la precisión numérica mientras que $Ax_{\text{inv}}$ está totalmente apagado.

Mis preguntas son:

1. Es el explícito $2\times2$ ejemplo de arriba, el representante de lo que sucede en la práctica, o es un sin sentido ejemplo calculada con muy poca precisión que sólo casualmente coincide con la de otros experimentos numéricos?

2. Son el número de observaciones que generalmente cierto? Para hacer de este exacto, vamos a $A=LU$ y definir $V = U^{-1}*L^{-1}$, $x_{\text{inv}} = V*b$, y $x_{\text{LU}}= U^{-1}*(L^{-1}*b)$ donde $*$ denota multiplicación numéricos de redondeo de error. Es generalmente el caso de que $\|Ax_{\text{inv}}-b\|>\|Ax_{\text{LU}}-b\|$?

3. ¿Cuáles son algunos ejemplos de aplicaciones prácticas donde forward error es más importante que atrás de error, y viceversa?

Answer 1

Deje $x_{inv}$ ser la solución de $A x = b$ obtenido por el LU método, y $x_{inv}$ ser la solución calculada como $x_{inv} = \text{inv}(A) * b$. Deje $\text{inv}(A)$ denotar la inversa de a $A$ calculado a partir de la descomposición LU $A \approx \hat{L}\hat{U}$ mediante la resolución de $Ax_j = e_j$, y deje $B * y$ denotar la multiplicación de la matriz se realiza en la aritmética de precisión finita. Tenga en cuenta que $\text{inv}(A)$ es diferente de$\hat{U}^{-1} * \hat{L}^{-1}$, pero es mucho más sencillo de analizar.

El forward error de $x_{LU}$ es $$\tag{1}\|x - x_{LU}\|_\infty \leq c_n u \||A^{-1}| |\hat{L}| |\hat{U}| |x_{LU}| \|_\infty \leq c_n u \||A^{-1}| |\hat{L}| |\hat{U}|\|_\infty \times \|x_{LU} \|_\infty$$

donde $c_n$ denota una constante del orden de $n$ $u$ es la precisión de la máquina. Similar forward error de los límites para la $x_{inv}$ es $$\tag{2} \|x - x_{inv}\|_{\infty} \leq c_n u \||A^{-1}| |\hat{L}| |\hat{U}| |\text{inv}(A)| |b|\|_{\infty} \leq c_n u \||A^{-1}| |\hat{L}| |\hat{U}|\|_\infty \times \|\text{inv}(A)| |b|\|_{\infty}$$

Comparando (1) y (2) y señalar, que para suficientemente bien acondicionado matriz $A$, $$\tag{3} \|x_{LU}\|_\infty\approx \|x\|_\infty = \|A^{-1}b\|_\infty \leq \||A^{-1}||b|\|_\infty\approx \||\text{inv}(A)| |b|\|_\infty$$ vamos a ver, que mientras $\|x\|_\infty\approx \|A^{-1}||b\|_\infty$, $x_{LU}$ $x_{inv}$ similares de errores hacia adelante. Aviso, que se cumple esta condición general $b$.

Por lo tanto, forward error de límites (1) y (2) siempre prefiero $x_{LU}$ $x_{inv}$ pero por lo general los errores hacia adelante para $x_{inv}$ no es mucho peor.

Error de enlazado (1) puede encontrarse en Higham la "Exactitud y Estabilidad de los Algoritmos Numéricos". Error de enlazado (2) pueden ser calculados a partir de errores hacia adelante obligado para $\text{inv}(A)$: $$|\text{inv}(A) - A^{-1}| \leq c_n u |A^{-1}| |\hat{L}| |\hat{U}| |\text{inv}(A)|$$ y a partir de la observación, el error que se introduce por la multiplicación de la matriz $\text{inv}(A) * b$ es siempre menor que el error asociado al cálculo de $\text{inv}(A)$.

Ahora supongamos, que $\bar{x}_{inv} = A^{-1} *b$, es decir, luego inverso $A^{-1}$ se calcula exactamente y la única fuente de error es la multiplicación de la matriz. A continuación, los residuos de $b - A\bar{x}_{inv}$ satisfacer $$\tag{4} |b - A \bar{x}_{inv}| \leq c_n u |A| |A^{-1}| |b|$$ para $x_{LU}$ hemos $$\tag{5}|b - A x_{LU}| \leq c_n u |\hat{L}| |\hat{U}| |x_{LU}|$$ Ya que normalmente es cierto, que $\||\hat{L}| |\hat{U}|\|_\infty \approx \|A\|_\infty$, por lo $\bar{x}_{inv}$ $x_{LU}$ puede tener comparable residual normas sólo cuando $\|x_{LU}\|_\infty \approx \||A^{-1}| |b|\|_\infty$. Por otro lado, de (3) tenemos (por lo suficientemente bien acondicionado $A$), $\|x_{LU}\|_\infty \leq \||A^{-1}| |b|\|_\infty$, por lo tanto, los residuos de $x_{LU}$ son normalmente más pequeños que los residuos de la $x_{inv}$, incluso para bien acondicionado matriz $A$. Si $A$ tiene grandes condición de número, $\text{inv}(A)$ es inexacta, tenemos otra fuente de error en (4), por lo tanto, podemos esperar mucho más grande residuos de la $x_{inv}$.

Por lo tanto:

1. Presentó $2\times 2$ ejemplo es genérico, es decir, suele ser $x_{inv}$ $x_{LU}$ similares de errores hacia adelante (incluso para mal acondicionado matriz $A$) menos que $|x|_\infty \ll \||A^{-1}| |b|\|_\infty$.

2. Residuos de la $x_{inv}$ es generalmente más grandes que las de $x_{LU}$ si $A$ está bien acondicionado y $|x|_\infty \approx \||A^{-1}| |b|\|_\infty$.

Yo no soy consciente de ninguna de las aplicaciones prácticas donde minimizar el retroceso de error es el objetivo final. Sin embargo, el retroceso de error y el avance de error están estrechamente relacionados, de acuerdo a la desigualdad $$\text{forward_error} \leq \text{condition_number} \times \text{backward_error}$$

Puesto que la condición no depende del algoritmo utilizado para resolver determinado problema, uno puede esperar, que la elección de un algoritmo más pequeños hacia atrás error conducirá a la disminución de errores hacia adelante así.

Answer 2

Esto es más un comentario que una respuesta a las preguntas, pero demasiado largo para el formato de comentario

Me contestó que de aquí a una pregunta sobre el uso de la inversa. En la respuesta que yo uso el mismo artículo ¿qué tan precisa es la inv(A)*b?.

Voy a empezar con la consideración de que el uso de la inversa no es siempre malo, véase también el comentario en la pregunta vinculados, pero. Desde el artículo de obtener las dos estimaciones del informe en la respuesta, y la mejor es la vuelta hacia atrás estable. Usted puede mejorar la stime para el caso inverso, pero bajo ciertas condiciones. Así, en un caso con una matriz general, y no otra información, incluso es mejor usar para resolver el sistema lineal, por ejemplo, con LU. En mi opinión la precisión numérica es todavía una buena razón.

A más de esto, hay otro aspecto a considerar en la preferencia de la LU respeto a la inversa. Por ejemplo, el rendimiento, aceptar el uso de la matriz-vector de la multiplicación, pero debo calcular la inversa. O la consideración de la escasa caso, donde no es posible utilizar un explícito inversa. (ver los comentarios y otra respuesta en la pregunta vinculada).