Universidad Central de Venezuela Cálculo Cientı́fico

Escuela de Computación Semestre II-2025

Resumen # 6

Métodos iterativos para SEL

2 de Diciembre de 2025
Prof. M. Monsalve
Cálculo Cientı́fico I Semestre II-2025

Idea general de Método Iterativo

Considere el SEL Ax = b con A no singular, cuya solución se denota por x∗ .

Dado x(0) ∈ Rn , la idea es usar un algoritmo iterativo para generar una sucesión
de vectores x(0) , x(2) , . . . x(0) , . . ., denotada por {x(k) }k≥0 tal que x(k) → x∗ cuando
k → ∞, donde x∗ = (x∗1 , x∗2 , . . . , x∗n )T es la solución del SEL.

Métodos Estacionarios
Se escriben de la forma
x(k+1) = Bx(k) + d (1)
donde B ∈ Rn×n y d ∈ Rn se denominaz Matriz y vector de iteración respectivamente.
Los más conocidos son:

ˆ Jacobi ˆ Gauss Seidel ˆ SOR

Formulación por componente

Sea x(0) ∈ Rn un vector dado. Los siguientes esquemas definen a los métodos estacionar-
ios de Jacobi, Gauss-Seidel y SOR. Estos esquemas generan una sucesión {x(k) }k>0
que, bajo ciertas condiciones, convergen a x∗ solución del sistema Ax = b.

Jacobi
La i-ésima ecuación del SEL viene dada por

ai1 x1 + ai2 x2 + · · · aii−1 xi−1 + aii xi + aii+1 xi+1 + · · · ain xn = bi

Si se asume aii 6= 0 y al despejar la variable i de dicha ecuación se obtiene que:

1
xi = [bi − ai1 x1 + ai2 x2 + · · · aii−1 xi−1 + aii+1 xi+1 + · · · ain xn ]
aii
 
n
1  X
= bi − aij xj 
aii
j=1, j6=i

Esta última expresión motiva al método de Jacobi, definido como:

 
n
(k+1) 1 bi −
X (k)
xi = aij xj  para 1 ≤ i ≤ n (2)
aii
j=1, j6=i

Gauss-Seidel

(k+1) (k+1)
Note que en el método de Jacobi, para calcular x2 es posible usar x1 (valor
(k)
más reciente de x2 ) en vez de x2 . Este cambio genera el método de Gauss-Seidel.

1 Elaborado por Prof. M. Monsalve

Cálculo Cientı́fico I Semestre II-2025

Teniendo en el comentario anterior, se genere una nuevo esquema conocido como el método
Gauss-Seidel:
 
i−i n
(k+1) 1  X (k+1)
X (k)
xi = bi − aij xj − aij xj  para 1 ≤ i ≤ n (3)
aii
j=1 j=i+1

SOR (Successive Over Relaxation)

(k) (k+1)
Note que ni Jacobi, ni Gauss-Seidel, emplean el valor de x1 para calcular x1 ;
(k)
y esto último puede resultar una buena idea, ya que que se supone que x1 es
una mejor aproximación a x∗1 (valor exacto de la primera componente). Este
(k+1)
mismo comentario es válido para x2 .

Por lo tanto, el método de SOR se define como:

(k+1) (k+1) (k)
xi = ωb
xi + (1 − ω)xi para 1 ≤ i ≤ n, (4)
(k+1)
donde x
bi se obtiene usando Gauss-Seidel.

Formulación Matricial
Todo método estacionario se puede escribir de la forma

x(k+1) = Bx(k) + d, (5)

con x(0) dado. En este contexto, B y d reciben el nombre de matriz y vector de iteración
respectivamente.

Para la definición matricial de los métodos estacionarios considerados, conviene parti-

cionar la matriz A según se indica en la Figura:

Figura 1: Particionamiento de la matriz de coeficientes del SEL

Jacobi
De la expresión del método de Jacobi (2) se tiene que la i-ésima componente del vector
x(k+1) se puede escribir como:

2 Elaborado por Prof. M. Monsalve

Cálculo Cientı́fico I Semestre II-2025

h i
(k+1) 1 (k) (k) (k) (k) (k) (k)
xi = aii bi − ai1 x1 + ai2 x2 + · · · aii−1 xi−1 + 0xi + aii+1 xi+1 + · · · ain xn
 (k) 
x1
 (k) 
 x 
 2 
 . 
 .. 
 
  (k) 

ai1 ai2 aii−1 aii+1 ain  xi−1 
 bi
= − ··· 0 ··· +
aii aii aii aii aii  x(k)  aii

 i 
 (k) 
 x 
 i+1 
 . 
 .. 
 
(k)
xn
Por lo tanto, las n componentes se pueden calcular mediante un producto matriz-vector
y una suma de vectores, es decir:
 (k+1)     (k)   
x1 0 −a12 /a11 · · · −a1i /a11 · · · −a1n /a11 x1 b1 /a11
 (k+1)    (k)  
 x2  −a21 /a22 0 · · · −a2i /a22 · · · −a2n /a22 
 x2   b2 /a22 
 .   .. .. .. 

..  ..  
 
 .   
.

 .   . .  .   . 
 (k+1)  =   (k) + 
xi   −ai1 /aii −ai2 /aii · · · 0 · · · −ain /aii  xi   bi /aii 
 

 ..  
  .. .. ..  ..  
 .. 
 .   . . .   .   . 
(k+1)
xn −an1 /ann −an2 /ann · · · −ani /ann · · · 0 (k) bn /ann
| {z } xn | {z }
BJ dJ

Con lo cual, la iteración matricial para el método de Jacobi es

x(k+1) = BJ x(k) + dJ ,
con x(0) dado.

Ahora bien, esta matriz BJ se puede escribir en función del particionamiento de A,

descrito en la Figura 1, como:
BJ = −D−1 (L + U ),
mientras que dJ se escribe como:
dJ = −D−1 b.

Gauss-Seidel
Siguiendo un ánalisis similar al realizado con Jacobi, se tiene que la matriz de iteración de
Gauss-Seidel es
BGS = −(L + D)−1 U,
mientras que el vector de iteración se define como:
dGS = (L + D)−1 b.
y similarmente, la iteración matricial para el método de Gauss-Seidel es
x(k+1) = BGS x(k) + dGS ,
con x(0) dado.

3 Elaborado por Prof. M. Monsalve

Cálculo Cientı́fico I Semestre II-2025

SOR
Siguiendo un ánalisis similar al realizado con Jacobi, se tiene que la matriz de iteración de
SOR es
BSOR = (ωL + D)−1 [(1 − ω)D − ωU ],
mientras que el vector de iteración se define como:

dSOR = ω(ωL + D)−1 b.

y similarmente, la iteración matricial para el método de Gauss-Seidel es

x(k+1) = BSOR x(k) + dSOR ,

con x(0) dado.

Criterios de parada:
En cada uno de los métodos iterativos para resolver un sistema lineal Ax = b, las siguientes
expresiones sirven como criterios de parada al proceso iterativo. La variable  es un
número positivo dado por el usuario y que debe ser escogido de acuerdo a la precisión
deseada.

kb − Ax(k+1) k2 kx(k+1) − x(k) k2

kb − Ax(k+1) k2 <  < <
kbk2 kx(k) k2

Convergencia (Resumen)
1. Los método estacionarios convergen si y solo si B es una matriz convergente.

2. B es convergente si y solo si limk→∞ B k = 0

3. B es convergente si y solo si ρ(B) < 1, donde ρ(B) = max1≤i≤n |λi |

4. Calcular ρ(B) es costoso pero por suerte ρ(B) se puede relacionar con la kBk (donde
k.k es cualquier norma subordinada).

5. Para cualquier norma subordinada se cumple que λ ≤ kBk donde λ es autovalor de

B. De aquı́ se desprende que:

6. ρ(B) ≤ kBk.

7. Finalmente de 3 y 6 se desprende que

Si kBk < 1, entonces B es una matriz convergente (el recı́proco no es cierto)

4 Elaborado por Prof. M. Monsalve