Descomposición LU

La descomposición LU ( descomposición LU , factorización LU ) es una representación de una matriz como producto de dos matrices , donde es una matriz triangular inferior y una matriz triangular superior. $A$ $A=LU$ $L$ $tu$

La descomposición LU se utiliza para resolver sistemas de ecuaciones lineales , invertir matrices y calcular el determinante . Una descomposición LU existe solo si la matriz es invertible y todos los principales menores principales (esquinas) de la matriz no son degenerados [1] . $A$ $A$

Este método es una de las variedades del método de Gauss .

Aplicaciones

Resolver sistemas de ecuaciones lineales

La descomposición LU resultante de la matriz (matriz de coeficientes del sistema) se puede utilizar para resolver una familia de sistemas de ecuaciones lineales con diferentes vectores en el lado derecho [2] : $A$ $b$

hacha=b

Si se conoce la descomposición LU de la matriz , , el sistema original se puede escribir como $A$ $A=LU$

LUx=b.

Este sistema se puede resolver en dos pasos. El primer paso es resolver el sistema.

Li=b.

Como es una matriz triangular inferior, este sistema se resuelve directamente por sustitución directa . $L$

En el segundo paso, el sistema se resuelve

x=y.

Como es una matriz triangular superior, este sistema se resuelve directamente por sustitución hacia atrás . $tu$

Inversión de matriz

La inversión de matrices es equivalente a resolver un sistema lineal $A$

AX=I

donde es una matriz desconocida, es la matriz identidad. La solución a este sistema es una matriz inversa . $X$ $yo$ $X$ $A^{{-1}}$

El sistema se puede resolver mediante el método de descomposición LU descrito anteriormente.

Cálculo del determinante de una matriz

Dada la descomposición LU de la matriz , $A$

A=LU

podemos calcular directamente su determinante ,

\det(A)=\det(LU)=\det(L)\det(U)=\left(\prod _{{i=1}}^{n}L_{{ii}}\right)\ izquierda(\prod_{{i=1}}^{n}U_{{ii}}\derecha)

donde es el tamaño de la matriz , y son los elementos diagonales de las matrices y . $norte$ $A$ $L_{{ii}}$ $U_{{ii}}$ $L$ $tu$

Derivación de la fórmula

Según el ámbito de aplicación, la descomposición LU solo se puede aplicar a una matriz no singular, por lo tanto, en lo que sigue, supondremos que la matriz no es singular. $A$

Dado que tanto en la primera fila de la matriz como en la primera columna de la matriz , todos los elementos, excepto posiblemente el primero, son iguales a cero, tenemos $L$ $tu$

a_{{11}}=l_{{11}}u_{{11}}

Si , entonces o . En el primer caso, la primera fila de la matriz consta enteramente de ceros , en el segundo, la primera columna de la matriz . Por lo tanto, o es degenerado, y por lo tanto es degenerado , lo que lleva a una contradicción. Entonces, si , entonces la matriz no singular no tiene descomposición LU. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $tu$ $L$ $tu$ $A$ $a_{{11}}=0$ $A$

Sea , entonces y . Como L y U se definen hasta multiplicar U por una constante y dividir L por la misma constante, podemos exigir que . Al mismo tiempo $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Divida la matriz A en celdas:

A={\begin{pmatrix}a_{{11}}&w^{T}\\v&A'\\\end{pmatrix}}

donde tienen dimensiones respectivamente , , . $v,w^{T},A'$ ${\ estilo de visualización (N-1) \ veces 1}$ ${\ estilo de visualización 1 \ veces (N-1)}$ ${\ estilo de visualización (N-1) \ veces (N-1)}$

Del mismo modo, dividimos en celdas de la matriz y : $L$ $tu$

L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix)),\ U={\begin{pmatrix}a_{11}&w_{u}^{T} \\0&U'\\\end{pmatriz}}.

La ecuación toma la forma $A=LU$

{\ estilo de visualización w^{T}=w_{u}^{T},}

v=a_{11}v_{l},

A'=v_{l}w_{u}^{T}+L'U'.

Resolviendo el sistema de ecuaciones para , , , , obtenemos: ${\ Displaystyle v_ {l}}$ ${\ estilo de visualización w_ {u}}$ ${\ estilo de visualización L'}$ ${\ estilo de visualización U'}$

{\ estilo de visualización w_ {u} = w,}

v_{l}=v/a_{11},

L'U'=A'-vw^{T}/a_{11}.

Finalmente tenemos:

L={\begin{pmatrix}1&0\\v/a_{11}&L'\\\end{pmatrix)),

U={\begin{pmatrix}a_{11}&w^{T}\\0&U'\\\end{pmatrix)),

L'U'=A'-vw^{T}/a_{11}.

Entonces, hemos reducido la descomposición LU de la matriz de tamaño a la descomposición LU de la matriz de tamaño . ${\ estilo de visualización N \ veces N}$ ${\ estilo de visualización (N-1) \ veces (N-1)}$

La expresión se llama complemento de Schur del elemento en la matriz A [1] . $A'-vw^{T}/a_{{11}}$ $un_{11}$

Algoritmo

Uno de los algoritmos para calcular la descomposición LU se muestra a continuación. [3]

Usaremos la siguiente notación para los elementos de la matriz: , , , ; y los elementos diagonales de la matriz : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\puntos n$ $L$ $l_{{ii}}=1$ $i=1\puntos n$

Puede encontrar las matrices y de la siguiente manera (los pasos deben realizarse estrictamente en orden, ya que los siguientes elementos se encuentran usando los anteriores): $L$ $tu$

Bucle i de 1 a n
1. Bucle j de 1 a n
  1. uij = 0, lij = 0
  2. l ii = 1
Bucle i de 1 a n
1. Bucle j de 1 a n
  1. Si i<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj))$
  2. Si i > j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

Como resultado, obtenemos matrices - y . $L$ $tu$

Véase también

Notas

↑ 1 2 E. E. Tyrtyshnikov. Análisis matricial y álgebra lineal. — 2004-2005.
↑ Levitina, 2006 .
↑ Verzhbitsky V. M. Fundamentos de los métodos numéricos. Libro de texto para escuelas secundarias. - Escuela Superior, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Literatura

Ortega J. Introducción a los métodos paralelos y vectoriales para la resolución de sistemas lineales. — M .: Mir, 1991. — 376 p. — ISBN 5-03-001941-3 .
Algoritmos de Levitin A. V. Introducción al desarrollo y análisis - M. : Williams , 2006. - 576 p. — ISBN 978-5-8459-0987-9

Vectores y matrices

Vectores

Conceptos básicos	Vector en geometría Base base ortogonal Coordenadas vectoriales colinealidad ortogonalidad Dependencia lineal Espacio de columna
Tipos de vectores	Vector unitario vector axial vector isotrópico Normal colinealidad vector cero Vector de radio Vector propio
Operaciones sobre vectores	producto escalar producto vectorial producto mixto Producto pseudoescalar Producto cruzado doble
Tipos de espacio	espacio vectorial espacio afín espacio euclidiano Espacio pseudo-euclidiano espacio normado espacio minkowski

matrices

Conceptos básicos	Multiplicación de matrices matriz transpuesta Matriz conjugada hermítica Matriz simétrica matriz inversa valor propio Polinomio característico de una matriz
Matrices especiales	Matriz de identidad Matriz cero Matriz diagonal matriz lambda
Descomposiciones de matrices	descomposición LU Descomposición de Cholesky descomposición QR descomposición LUP valor singular de descomposición Descomposición espectral de una matriz

Otro