5.4: Descomposición de LU
- Page ID
- 125126
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Se puede usar una variante del algoritmo de eliminación gaussiana para calcular la descomposición de LU de una matriz. Este procedimiento fue inventado por Alan Turing, el matemático británico considerado el “padre de la informática”. La descomposición de LU de una matriz cuadrada\(\mathbf{A}\) consiste en una matriz triangular inferior\(\mathbf{L}\) y una matriz triangular superior\(\mathbf{U}\), de tal manera que
\[\mathbf{A} = \mathbf{L}\, \mathbf{U}.\]
En ciertas circunstancias especiales, las descomposiciones de LU proporcionan un método muy eficiente para resolver ecuaciones lineales. Supongamos que tenemos que resolver\(\mathbf{A} \vec{x} = \vec{b}\) muchas veces un conjunto de ecuaciones lineales, usando las mismas\(\mathbf{A}\) pero un número indefinido de\(\vec{b}\)'s que podrían no conocerse de antemano. Por ejemplo, los\(\vec{b}\)'s podrían representar una serie interminable de resultados de medición,\(\mathbf{A}\) representando alguna configuración experimental fija. Nos gustaría calcular de manera eficiente\(\vec{x}\) para cada uno\(\vec{b}\) que llegue. Si esto se hace con la eliminación gaussiana, cada cálculo llevaría\(O(N^{3})\) tiempo.
Sin embargo, si podemos realizar una descomposición de LU antes de tiempo, entonces los cálculos se pueden realizar mucho más rápidamente. Las ecuaciones lineales son
\[\mathbf{L}\, \mathbf{U} \vec{x} = \vec{b}.\]
Esto se puede dividir en dos ecuaciones separadas:
\[\mathbf{L}\, \vec{y} = \vec{b}, \quad \mathrm{and}\;\;\; \mathbf{U} \vec{x} = \vec{y}.\]
Debido a que\(\mathbf{L}\) es triangular inferior, podemos resolver la primera ecuación por sustitución directa (similar a la sustitución hacia atrás, excepto que va de la primera fila a la última) para encontrar\(\vec{y}\). Entonces podemos resolver la segunda ecuación por retrosustitución, para encontrar\(\vec{x}\). Todo el proceso lleva\(O(N^{2})\) tiempo, lo que es una tremenda mejora sobre la realización de una eliminación gaussiana mayorista.
Sin embargo, encontrar la descomposición de LU lleva\(O(N^{3})\) tiempo (no entraremos en detalles aquí, pero básicamente es una variante de la fase de reducción de filas del algoritmo de eliminación gaussiana). Por lo tanto, si estamos interesados en resolver las ecuaciones lineales solo una vez, o un puñado de veces, el método de descomposición de LU no mejora el rendimiento. Es útil en situaciones donde la descomposición de LU se realiza con anticipación. Se puede pensar en la descomposición de LU como una forma de reorganizar el algoritmo de eliminación gaussiana, de modo que no necesitamos saberlo\(\vec{b}\) durante la primera\(O(N^{3})\) fase, costosa.
En Python, puedes realizar la descomposición de LU usando la función scipy.linalg.lu. Las etapas de sustitución directa y sustitución posterior se pueden realizar usando scipy.linalg.solve_triangular.