26.4: Eliminación gaussiana y factorización de LU

En este capítulo, se introdujo un procedimiento sistemático para resolver un sistema lineal mediante eliminación gaussiana y sustitución posterior. Interpretamos la eliminación gaussiana como un proceso de triangulación de la matriz del sistema de interés; el proceso se basó, en el\(k^{\text {th }}\) paso, en agregar versiones apropiadamente escaladas de la\(k^{\text {th }}\) ecuación a todas las ecuaciones debajo de ella para eliminar el coeficiente inicial. En particular, también modificamos el lado derecho de la ecuación en el procedimiento de triangulación de tal manera que estamos agregando la misma cantidad a ambos lados de la ecuación y por lo tanto no afectando la solución. El producto final de nuestro proceso de triangulación es una matriz triangular superior\(U\) y un lado derecho modificado\(\hat{f}\). Si se nos da un nuevo lado derecho, tendríamos que repetir el mismo procedimiento nuevamente (en\(\mathcal{O}\left(n^{3}\right)\) costo) para deducir el nuevo lado derecho modificado apropiado.

Resulta que una ligera modificación de nuestro procedimiento de eliminación gaussiana de hecho permitiría la solución al problema con un lado derecho diferente en\(\mathcal{O}\left(n^{2}\right)\) las operaciones. Para lograrlo, en lugar de modificar el lado derecho en el proceso de triangulación superior, registramos las operaciones utilizadas en el proceso de triangulación superior con las que generamos el lado derecho. Resulta que esta operación de grabación de hecho se puede hacer usando una matriz triangular inferior\(L\), de tal manera que el lado derecho modificado\(\hat{f}\) es la solución a\[L \hat{f}=f,\] donde\(f\) está el lado derecho original. Similar a la sustitución posterior para un sistema triangular superior, la sustitución hacia adelante permite la solución al sistema triangular inferior en\(\mathcal{O}\left(n^{2}\right)\) las operaciones. Esta matriz triangular inferior\(L\) que registra todas las operaciones utilizadas en la transformación de la matriz\(A\)\(U\) en hecho es una matriz que satisface\[A=L U .\] En otras palabras, las matrices\(L\) y\(U\) surgen de una factorización de la matriz\(A\) en matrices triangulares inferior y superior.

Este procedimiento se llama\(L U\) factorización. (El hecho de que\(L\) y\(U\) deba permitir tal factorización es sencillo de ver por el hecho de que\(U u=\hat{f}\) y\(L \hat{f}=f\); la multiplicación de ambos lados de\(U u=\hat{f}\) por\(L\) rendimientos \(L U u=L \hat{f}=f\), y debido a que la relación debe sostenerse para cualquier pareja solución-lado derecho\(\{u, f\}\) a\(A u=f\), debe ser eso\(L U=A\).) El proceso de factorización es, de hecho, idéntico a nuestra eliminación gaussiana y requiere\(2 n^{3} / 3\) operaciones. Tenga en cuenta que sí computamos todas las piezas de la matriz\(L\) en nuestro procedimiento de eliminación; simplemente no formamos la matriz por simplicidad.

En general la descomposición de LU existirá si la matriz no\(A\) es singular. Sin embargo, hay un giro: es posible que necesitemos permutar las filas de\(A\) - un proceso conocido como pivotamiento (parcial) - para evitar un pivote cero que terminaría prematuramente el proceso. (De hecho, las permutaciones de filas también pueden ser ventajosas para evitar pequeños pivotes que pueden conducir a la amplificación de errores de redondeo). Si incluso -digamos en infinita precisión- con permutaciones de fila llegamos a un pivote exactamente cero entonces esto es de hecho demuestra que\(A\) es singular. \({ }_{-}\)

Existen algunas matrices para las que no se requiere pivotar. Un ejemplo tan importante en ingeniería mecánica son las matrices SPD. Para una matriz SPD (que ciertamente no es singular - todos los valores propios son positivos) nunca llegaremos a un pivote cero ni necesitaremos permutar filas para asegurar la estabilidad. Tenga en cuenta, sin embargo, que es posible que aún deseemos permutar filas para mejorar la eficiencia de la descomposición de LU para sistemas dispersos, que es el tema de la siguiente sección.