PDF de programación - Programación: Solución de sistemas de ecuaciones lineales con métodos iterativos de Jacobi y de Gauss–Seidel

Programación: Métodos iterativos

de Jacobi y de Gauss–Seidel

Objetivos. Programar los métodos de Jacobi y Gauss–Seidel para resolver sistemas de
ecuaciones lineales.

1. Idea de los métodos iterativos. Se considera un sistema de ecuaciones lineales
Ax = b. En ambos métodos se construye una sucesión de vectores x(0), x(1), x(2), . . . , que
bajo ciertas condiciones converge a la solución exacta del sistema.

2. Terminar el proceso si llegamos a un punto fijo. Terminar el proceso iterativo si
x − y2 < ε, donde ε es un número dado, x es el vector obtenido en la última iteración,
y es el vector obtenido en la iteración anterior y · 2 es la norma euclideana. Vamos a
denotar x − y2 por d.

3. Número máximo de iteraciones. En algunas situaciones los métodos iterativos no
convergen. Por eso desde el inicio elegimos el número máximo de iteraciones pmax, en
una variable p contamos el número de las iteraciones realizadas y salimos del ciclo si
p >= pmax.

4. Condición de terminación y condición de continuación. Vamos a terminar el
ciclo si la solución actual es muy cercana a la solución encontrada en el paso anterior o si
el número de iteraciones hechas es mayor o igual al número máximo de iteraciones:

Condición de terminación:

(d < eps)

∨

(p ≥ pmax).

La condición de continuación del ciclo obtenemos como la negación de la condición de
terminación:

Condición de continuación:



∧



.

?

?

Programación: métodos de Jacobi y de Gauss–Seidel, página 1 de 2

5. Estructura del algoritmo para métodos iterativos.

Entrada: A, b, eps, pmax.
Variables locales: ... .
n := longitud de b;
x := vector nulo de longitud n;
d := 2 * eps;
p := ...;
Mientras ...:

y := x;
... (construir x nuevo) ...
d := norma del vector (x - y);
p += 1;

Salida: x, p.

Fórmula del método de Jacobi. En cada paso las componentes del vector nuevo x se
calculan a través del vector anterior z mediante las siguientes fórmulas:

xi :=

1
Ai,i

bi −

Ai,j yj −

Ai,j yj

.

j=1

j=i+1

6. Problema SyslineqJacobi (2 %). Entradas: A, b, eps, pmax, donde A es una
matriz cuadrada de orden n, b es un vector de longitud n. Salida: vector x y número de
iteraciones realizadas p.



i−1

i−1

n



n



Fórmula del método de Gauss–Seidel.

xi :=

1
Ai,i

bi −

Ai,j xj −

Ai,j yj

.

j=1

j=i+1

7. Problema SyslineqGaussSeidel (1 %). Entradas: A, b, eps, pmax, donde A es
una matriz cuadrada de orden n, b es un vector de longitud n. Salida: vector x y número
de iteraciones realizadas p.

8. Comprobación. Aplique los métodos de Jacobi y de Gauss–Seidel al siguiente sistema:

 −5

1 −2
1
5

1 −4
3
1

 x =

 .

 8

−1
3

Compare el número iteraciones en estos dos métodos aplicados al mismo sistema y con el
mismo eps = 0.001.

Programación: métodos de Jacobi y de Gauss–Seidel, página 2 de 2