División de matriz

Representación de una matriz como suma

En la disciplina matemática del álgebra lineal numérica , una descomposición matricial es una expresión que representa una matriz dada como una suma o diferencia de matrices. Muchos métodos iterativos (por ejemplo, para sistemas de ecuaciones diferenciales ) dependen de la solución directa de ecuaciones matriciales que involucran matrices más generales que las matrices tridiagonales . Estas ecuaciones matriciales a menudo se pueden resolver de manera directa y eficiente cuando se escriben como una descomposición matricial. La técnica fue ideada por Richard S. Varga en 1960. ^[1]

Divisiones regulares

Buscamos resolver la ecuación matricial

donde A es una matriz no singular n × n dada, y k es un vector columna dado con n componentes. Dividimos la matriz A en

donde B y C son matrices n × n . Si, para una matriz arbitraria n × n M , M tiene entradas no negativas, escribimos M ≥ 0 . Si M solo tiene entradas positivas, escribimos M > 0 . De manera similar, si la matriz M ₁ − M ₂ tiene entradas no negativas, escribimos M ₁ ≥ M ₂ .

Definición: A = B − C es una división regular de A si B ⁻¹ ≥ 0 y C ≥ 0 .

Suponemos que las ecuaciones matriciales de la forma

donde g es un vector columna dado, se puede resolver directamente para el vector x . Si ( 2 ) representa una división regular de A , entonces el método iterativo

donde x ⁽⁰⁾ es un vector arbitrario, se puede realizar. De manera equivalente, escribimos ( 4 ) en la forma

La matriz D = B ⁻¹ C tiene entradas no negativas si ( 2 ) representa una división regular de A . ^[2]

Se puede demostrar que si A ⁻¹ > 0 , entonces < 1, donde representa el radio espectral de D , y por lo tanto D es una matriz convergente . En consecuencia, el método iterativo ( 5 ) es necesariamente convergente . ^{[3] [4]} ${\displaystyle \rho (\mathbf {D} )}$ ${\displaystyle \rho (\mathbf {D} )}$

Si, además, se elige la división ( 2 ) de modo que la matriz B sea una matriz diagonal (con todas las entradas diagonales distintas de cero, ya que B debe ser invertible ), entonces B se puede invertir en tiempo lineal (ver Complejidad temporal ).

Métodos iterativos matriciales

Muchos métodos iterativos pueden describirse como una división de matrices. Si las entradas diagonales de la matriz A son todas distintas de cero, y expresamos la matriz A como la suma de matrices

donde D es la parte diagonal de A , y U y L son respectivamente matrices n × n triangulares estrictamente superior e inferior , entonces tenemos lo siguiente.

El método de Jacobi se puede representar en forma matricial como una descomposición

El método de Gauss-Seidel se puede representar en forma matricial como una división

El método de sobre-relajación sucesiva se puede representar en forma matricial como una división

Ejemplo

División regular

En la ecuación ( 1 ), sea

Apliquemos la división ( 7 ) que se utiliza en el método de Jacobi: dividimos A de tal manera que B consiste en todos los elementos diagonales de A y C consiste en todos los elementos no diagonales de A , negados. (Por supuesto, esta no es la única forma útil de dividir una matriz en dos matrices). Tenemos

${\displaystyle {\begin{aligned}&\mathbf {A^{-1}} ={\frac {1}{47}}{\begin{pmatrix}18&13&16\\11&21&15\\13&12&22\end{pmatrix}},\quad \mathbf {B^{-1}} ={\begin{pmatrix}{\frac {1}{6}}&0&0\\[4pt]0&{\frac {1}{4}}&0\\[4pt]0&0&{\frac {1}{5}}\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}\mathbf {D} =\mathbf {B^{-1}C} ={\begin{pmatrix}0&{\frac {1}{3}}&{\frac {1}{2}}\\[4pt]{\frac {1}{4}}&0&{\frac {1}{2}}\\[4pt]{\frac {3}{5}}&{\frac {1}{5}}&0\end{pmatrix}},\quad \mathbf {B^{-1}k} ={\begin{pmatrix}{\frac {5}{6}}\\[4pt]-3\\[4pt]2\end{pmatrix}}.\end{aligned}}}$

Como B ⁻¹ ≥ 0 y C ≥ 0 , la división ( 11 ) es una división regular. Como A ⁻¹ > 0 , el radio espectral < 1. (Los valores propios aproximados de D son ) Por lo tanto, la matriz D es convergente y el método ( 5 ) converge necesariamente para el problema ( 10 ). Nótese que los elementos diagonales de A son todos mayores que cero, los elementos fuera de la diagonal de A son todos menores que cero y A es estrictamente diagonalmente dominante . ^[11] ${\displaystyle \rho (\mathbf {D} )}$ ${\displaystyle \lambda _{i}\approx -0.4599820,-0.3397859,0.7997679.}$

El método ( 5 ) aplicado al problema ( 10 ) toma entonces la forma

La solución exacta de la ecuación ( 12 ) es

Las primeras iteraciones de la ecuación ( 12 ) se enumeran en la tabla siguiente, comenzando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T. En la tabla se puede ver que el método evidentemente está convergiendo a la solución ( 13 ), aunque bastante lentamente.

Método Jacobi

Como se indicó anteriormente, el método de Jacobi ( 7 ) es el mismo que la división regular específica ( 11 ) demostrada anteriormente.

Método de Gauss-Seidel

Dado que las entradas diagonales de la matriz A en el problema ( 10 ) son todas distintas de cero, podemos expresar la matriz A como la división ( 6 ), donde

Entonces tenemos

${\displaystyle {\begin{aligned}&\mathbf {(D-L)^{-1}} ={\frac {1}{120}}{\begin{pmatrix}20&0&0\\5&30&0\\13&6&24\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {(D-L)^{-1}U} ={\frac {1}{120}}{\begin{pmatrix}0&40&60\\0&10&75\\0&26&51\end{pmatrix}},\quad \mathbf {(D-L)^{-1}k} ={\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}}.\end{aligned}}}$

El método de Gauss-Seidel ( 8 ) aplicado al problema ( 10 ) toma la forma

Las primeras iteraciones de la ecuación ( 15 ) se enumeran en la tabla siguiente, comenzando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T. En la tabla se puede ver que el método evidentemente converge a la solución ( 13 ), algo más rápido que el método de Jacobi descrito anteriormente.

Método de sobre-relajación sucesiva

Sea ω = 1,1. Utilizando la división ( 14 ) de la matriz A en el problema ( 10 ) para el método de sobre-relajación sucesiva, tenemos

${\displaystyle {\begin{aligned}&\mathbf {(D-\omega L)^{-1}} ={\frac {1}{12}}{\begin{pmatrix}2&0&0\\0.55&3&0\\1.441&0.66&2.4\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {(D-\omega L)^{-1}[(1-\omega )D+\omega U]} ={\frac {1}{12}}{\begin{pmatrix}-1.2&4.4&6.6\\-0.33&0.01&8.415\\-0.8646&2.9062&5.0073\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {\omega (D-\omega L)^{-1}k} ={\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135\end{pmatrix}}.\end{aligned}}}$

El método de sobre-relajación sucesiva ( 9 ) aplicado al problema ( 10 ) toma la forma

Las primeras iteraciones de la ecuación ( 16 ) se enumeran en la tabla siguiente, comenzando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T. En la tabla se puede ver que el método evidentemente converge a la solución ( 13 ), ligeramente más rápido que el método de Gauss-Seidel descrito anteriormente.

Véase también

• Lista de temas sobre división de operadores
• Descomposición matricial
• Matriz M
• Matriz de Stieltjes

Notas

1. Varga (1960)
2. Varga (1960, págs. 121-122)
3. Varga (1960, págs. 122-123)
4. Varga (1962, pág. 89)
5. Carga y ferias (1993, pág.408)
6. Varga (1962, pág. 88)
7. Carga y ferias (1993, pág.411)
8. Varga (1962, pág. 88)
9. Carga y ferias (1993, pág.416)
10. Varga (1962, pág. 88)
11. Carga y ferias (1993, p.371)

Referencias

• Burden, Richard L.; Faires, J. Douglas (1993), Análisis numérico (5.ª ed.), Boston: Prindle, Weber y Schmidt, ISBN 0-534-93219-3.
• Varga, Richard S. (1960). "Factorización y métodos iterativos normalizados". En Langer, Rudolph E. (ed.). Problemas de contorno en ecuaciones diferenciales . Madison: University of Wisconsin Press . págs. 121–142. LCCN  60-60003.
• Varga, Richard S. (1962), Análisis iterativo de matrices , Nueva Jersey: Prentice-Hall , LCCN  62-21277.