Tema 5: Aplicaciones de la teoría del endomorfismo

Métodos iterativos para resolver sistemas de ecuaciones lineales.

Método de Jacobi: Dado un sistema de ecuaciones lineales AX = B podemos suponer que la matriz A es cuadrada regular. También podemos suponer que los elementos de la diagonal de A son todos 1. De esta forma consideramos la matriz C = In-A (que tiene todos los elementos de la diagonal iguales a cero).

El sistema inicial es AX = B. O sea, (I-C)X = B ! X = CX + B.

Construimos la sucesión de vectores:

X(0) = B X(i+1) = CX(i) + B Vi = 0,1,…

Si esta sucesión tiene límite, entonces ese límite es la solución del sistema.

Veremos más adelante en qué circunstancias podemos asegurar que este método de Jacobi converge.

Método de Gauss-Seidel: Mejora el proceso iterativo del método de Jacobi de la siguiente manera:

Hacemos como en el método de Jacobi X = CX + B. La sucesión de vectores la construimos de una manera difrente.

X(r+1) = -L-1UX(r) + L-1B

Donde L es una matriz triangular inferior (|L| = 1) y U es una matriz estrictamente superior (los elementos de la diagonal son 0). A = L + U.

El método de Gauss converge más rápidamente que el de Jacobi.

Usa el mismo número de operaciones que el de Jacobi, pero usa menos memoria. Es más fácil de escribir en el lenguaje de programación.

Veremos en qué condiciones podemos asegurar que converge.

El teorema de Gerschgorin. (todo en el cuerpo de los complejos !)

Para hallar los valores propoios de una matriz podemos hallar el polinomio característico y calcular sus raíces. Pero hallar las raíces de un polinomio de grado n es difícil. Existen métodos iterativos para aproximarnos a esas raíces. Para usar esos métodos iterativos es conveniente saber de antemano “por dónde están esas raíces”.

Lo que vamos a ver son algunos resultados que nos permiten localizar las zonas por dónde están los valores propios.

Idea: En una matriz diagonal, los valores propios son los valores de la diagonal.

Si la matriz es casi diagonal, los valores propios estarán cerca de los valores de la diagonal.

Matrices de diagonal dominante.

Una matriz cuadrada, A = [tij]  Mat(n,!), se dice que es de diagonal dominante si verifica que |tii| > j"i|tij| Vi=1,…,n.

En particular, t11"0, …, tnn"0.

Lema: Si A = [tij] es una matriz de diagonal dominante y realizamos en ella una operación elemental del tipo 2 (Si1(t)) que sirva para hacer cero el lugar (i,1), entonces la matriz que se obtiene sigue siendo de diagonal dominante.

Teorema: Cualquier matriz de diagonal dominante es regular.

Si t es “muy grande” entonces tI-A será de diagonal dominante (por tanto, regular) y así t no es valor propio de A.

El teorema de gerschgorin (continuación).

Teorema (Gerschgorin): Sea A  Mat(n,!), A = [tij]. Si t es valor propio de A, entonces existe un i tal que |t - tii| " j"i|tij|

Dada una matriz A  Mat(n,!), A = [tij], se llaman discos de Gerschgorin de la matriz A a los círculos del plano complejo con centro un elemento de la diagonal de A y radio la suma de los módulos de los demás elementos de su fila.

{z!; |z - tii| j"i|tij|}

Teorema de Gerschgorin: cada valor propio de A está en algún disco de Gerschgorin.

El teorema de gerschgorin mejorado.

Un conjunto de discos de Gerschgorin de la matriz A se dice que es un grupo disjunto de discos si la intersección de cualquier disco de ese conjunto con cualquier otro disco de Gerschgorin que no esté en el conjunto es vacío.

Teorema: Si G es un grupo disjunto de discos de la matriz A que consta de d discos (contando repeticiones) entonces hay d valores propios de la matriz A (contando repeticiones) que están contenidos en los discos de G.

Radio espectral.

En los métodos de Jacobi y Gauss-Seidel se tiene AX = B con A matriz cuadrada regular con los elementos de la diagonal todos iguales a 1.

C = I - A X(r+1) = CX(r)+B X(0) = B X(1) = CX(0)+B (Jacobi)

Si tomamos X(r) como solución del sistema, el error que estamos cometiendo es X(r)- X = e(r) (en donde X es la solución exacta). Le llamamos error en el término r-ésimo.

Vamos a observar que el error en el término r+1 es:

e(r+1) = X(r+1) - X = CX(r) + B - X = C(e(r)+X) + B - X = Ce(r) + Cx + B - X = Ce(r)

Supongamos que al tomar X(0) da la casualidad de que e(0) = X(0) - X resulta ser vector propio de valor propio t para la matriz C.

e(1) = Ce(0) = te(0)

e(2) = Ce(1) = Cte(0) = t2e(0)

………………………….

e(r) = tre(0)

Si |t| "1, entonces e(r)!0 cuando r!"

O sea, la sucesión {X(r)}"x=0!X

El método no es convergente.

Se llama radio espectral de una matriz cuadrada A al número real ρ(A) = máx{|t|; t es valor propio de A}.

Teorema: Sea AMat(n,!). Entonces Ar![0] (cuando r!") ! ρ(A) < 1.

Teorema: Sea AX = B un sistema de ecuaciones con A cuadrada regular y con todos los elementos de la diagonal iguales a 1. Si A es de diagonal dominante, entonces el método de Jacobi aplicado a ese sistema es convergente.

Teorema: Sea AX = B un sistema de ecuaciones con A cuadrada regular y con todos los elementos de la diagonal iguales a 1. Si A es de diagonal dominante, entonces el método de Gauss-Seidel es convergente.