En la disciplina matemática del álgebra lineal numérica , una división de matrices 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 matrices tridiagonales . Estas ecuaciones matriciales a menudo se pueden resolver de manera directa y eficiente cuando se escriben como una división de matrices. La técnica fue ideada por Richard S. Varga en 1960. [1]
Particiones regulares
Buscamos resolver la ecuación matricial
( 1 )
donde A es una matriz no singular n × n dada, yk es un vector columna dado con n componentes. Dividimos la matriz A en
( 2 )
donde B y C son n × n matrices. Si, para una matriz M arbitraria n × n , M tiene entradas no negativas, escribimos M ≥ 0 . Si M solo tiene entradas positivas, escribimos M > 0 . De manera similar, si la matriz M 1 - M 2 tiene entradas no negativas, escribimos M 1 ≥ M 2 .
Definición: A = B - C es una división regular de A si B −1 ≥ 0 y C ≥ 0 .
Suponemos que las ecuaciones matriciales de la forma
( 3 )
donde g es un vector de columna dado, se puede resolver directamente para el vector x . Si ( 2 ) representa una división regular de A , entonces el método iterativo
( 4 )
donde x (0) es un vector arbitrario, se puede realizar. De manera equivalente, escribimos ( 4 ) en la forma
( 5 )
La matriz D = B -1 C tiene entradas no negativos si ( 2 ) representa una división regular de A . [2]
Se puede demostrar que si A −1 > 0 , entonces <1, donde representa el radio espectral de D y, por tanto, D es una matriz convergente . Como consecuencia, el método iterativo ( 5 ) es necesariamente convergente . [3] [4]
Si, además, se elige la división ( 2 ) de modo que la matriz B sea una matriz diagonal (con las entradas diagonales todas distintas de cero, ya que B debe ser invertible ), entonces B se puede invertir en tiempo lineal (ver Complejidad de tiempo ).
Métodos iterativos de matriz
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 la matriz
( 6 )
donde D es la parte diagonal de A , y U y L son matrices n × n triangulares estrictamente superior e inferior respectivamente , entonces tenemos lo siguiente.
El método de Jacobi se puede representar en forma de matriz como una división
( 7 )
El método de Gauss-Seidel se puede representar en forma de matriz como una división
( 8 )
El método de sobre-relajación sucesiva se puede representar en forma de matriz como una división
( 9 )
Ejemplo
División regular
En la ecuación ( 1 ), sea
( 10 )
Apliquemos la división ( 7 ) que se usa 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 fuera de la diagonal de A , negado . (Por supuesto, esta no es la única forma útil de dividir una matriz en dos matrices). Tenemos
( 11 )
Dado que B −1 ≥ 0 y C ≥ 0 , la división ( 11 ) es una división regular. Dado que A −1 > 0 , el radio espectral<1. (Los valores propios aproximados de D son) Por tanto, la matriz D es convergente y el método ( 5 ) necesariamente converge para el problema ( 10 ). Tenga en cuenta 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]
El método ( 5 ) aplicado al problema ( 10 ) toma entonces la forma
( 12 )
La solución exacta de la ecuación ( 12 ) es
( 13 )
Las primeras iteraciones para la ecuación ( 12 ) se enumeran en la tabla a continuación, comenzando con x (0) = (0,0, 0,0, 0,0) T . En la tabla se puede ver que el método está convergiendo evidentemente hacia la solución ( 13 ), aunque con bastante lentitud.
0.0 | 0.0 | 0.0 |
0.83333 | -3.0000 | 2.0000 |
0.83333 | -1,7917 | 1.9000 |
1.1861 | -1,8417 | 2.1417 |
1.2903 | -1,6326 | 2.3433 |
1.4608 | -1.5058 | 2.4477 |
1.5553 | -1,4110 | 2.5753 |
1.6507 | -1,3235 | 2.6510 |
1.7177 | -1,2618 | 2.7257 |
1.7756 | -1.2077 | 2.7783 |
1.8199 | -1.1670 | 2.8238 |
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
( 14 )
Entonces tenemos
El método Gauss-Seidel ( 8 ) aplicado al problema ( 10 ) toma la forma
( 15 )
Las primeras iteraciones para la ecuación ( 15 ) se enumeran en la tabla a continuación, comenzando con x (0) = (0,0, 0,0, 0,0) T . En la tabla se puede ver que el método evidentemente está convergiendo hacia la solución ( 13 ), algo más rápido que el método de Jacobi descrito anteriormente.
0.0 | 0.0 | 0.0 |
0.8333 | -2,7917 | 1,9417 |
0.8736 | -1.8107 | 2.1620 |
1.3108 | -1,5913 | 2.4682 |
1.5370 | -1,3817 | 2.6459 |
1.6957 | -1.2531 | 2.7668 |
1.7990 | -1.1668 | 2.8461 |
1.8675 | -1.1101 | 2.8985 |
1.9126 | -1.0726 | 2.9330 |
1,9423 | -1.0479 | 2.9558 |
1,9619 | -1.0316 | 2.9708 |
Método sucesivo de relajación excesiva
Sea ω = 1.1. Usando la división ( 14 ) de la matriz A en el problema ( 10 ) para el método de sobre-relajación sucesiva, tenemos
El método sucesivo de sobre-relajación ( 9 ) aplicado al problema ( 10 ) toma la forma
( 16 )
Las primeras iteraciones para la ecuación ( 16 ) se enumeran en la tabla a continuación, comenzando con x (0) = (0,0, 0,0, 0,0) T . En la tabla se puede ver que el método está convergiendo evidentemente a la solución ( 13 ), algo más rápido que el método de Gauss-Seidel descrito anteriormente.
0.0 | 0.0 | 0.0 |
0.9167 | -3.0479 | 2.1345 |
0.8814 | -1,5788 | 2.2209 |
1,4711 | -1,5161 | 2.6153 |
1,6521 | -1,2557 | 2.7526 |
1,8050 | -1.1641 | 2.8599 |
1.8823 | -1.0930 | 2.9158 |
1,9314 | -1.0559 | 2.9508 |
1.9593 | -1.0327 | 2.9709 |
1.9761 | -1.0185 | 2.9829 |
1.9862 | -1.0113 | 2.9901 |
Ver también
- Lista de temas de división de operadores
- Descomposición de la matriz
- Matriz M
- Matriz de Stieltjes
Notas
- ↑ Varga (1960)
- ^ Varga (1960 , págs. 121-122)
- ^ Varga (1960 , págs. 122-123)
- ↑ Varga (1962 , p. 89)
- ↑ Burden & Faires (1993 , p. 408)
- ↑ Varga (1962 , p. 88)
- ↑ Burden & Faires (1993 , p. 411)
- ↑ Varga (1962 , p. 88)
- ↑ Burden & Faires (1993 , p. 416)
- ↑ Varga (1962 , p. 88)
- ^ Carga y ferias (1993 , p. 371)
Referencias
- Burden, Richard L .; Faires, J. Douglas (1993), Análisis numérico (5.a 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: Prensa de la Universidad de Wisconsin . págs. 121-142. LCCN 60-60003 .CS1 maint: ref duplica el valor predeterminado ( enlace )
- Varga, Richard S. (1962), Análisis iterativo de matrices , Nueva Jersey: Prentice-Hall , LCCN 62-21277.