NotasTema3_0 - Axel

Vista previa del material en texto

Tema 3: Solución numérica de sistemas de ecuaciones lineales
M. I. Luis Ángel Santamaŕıa Padilla
Facultad de Ingenieŕıa, UNAM
1 Métodos directos
Eliminación Gaussiana
Ejemplo 1
Pivoteo parcial con escalamiento de renglón
Ejemplo 2
Factorización LU (Doolittle)
Ejemplo 4
Factorización LU (Crout)
Ejemplo 5
2 Métodos iterativos
Norma de vectores y matrices
Método iterativo general
Método de Jacobi
Ejemplo 6
Método de Gauss-Seidel
Ejemplo 7
3 Problema de eigenvalores
Eigenvalores de una matriz
Ejemplo 8
Método de las potencias
Ejemplo 9
Objetivo tema 3
El estudiante aplicará algunos de los métodos para obtener soluciones aproximadas de sistemas de ecuaciones
lineales y determinará los valores y vectores caracteŕısticos de una matriz
Sistema de ecuaciones lineales
a11x1 + a12x2 + . . .+ a1nxn = b1
a21x1 + a22x2 + . . .+ a2nxn = b2
...
an1x1 + an2x2 + . . .+ annxn = bn
Donde los coeficientes aij son constantes conocidas.
Si todos los elementos bk son cero, el sistema de ecuaciones es homogéneo, en caso contrario es no homogéneo
Representación matricial de sistemas lineales
Todo sistema de ecuaciones algebraicas se puede representar de manera
matricial como
Ax = b
donde
A =

a11 a12 . . . a1n
a21 a22 . . . a2n
...
...
. . .
...
an1 an2 . . . ann

n×n
x =

x1
x2
...
xn

n×1
b =

b1
b2
...
bn

n×1
x es el vector solución
La matriz aumentada está dada por
[A|b] =

a11 a12 . . . a1n b1
a21 a22 . . . a2n b1
...
...
. . .
...
...
an1 an2 . . . ann b1

n×(n+1)
Solución numérica de sistemas
lineales
Los métodos se dividen en dos
categoŕıas
Directos
Eliminación Gaussiana
Descomposición LU
Método Doolittle
Método Crout
Indirectos
Método de Jacobi
Gauss-Seidel
Métodos directos Eliminación Gaussiana
Método de eliminación Gaussiana
Transforma un sistema lineal de ecuaciones en una forma triangular superior
La solución se encuentra por sustituciones hacia atrás
La matriz aumentada [A|b] representa al sistema Ax = b. Todas las modificaciones se aplican a la matriz
aumentada
Las transformación a una forma triangular superior se consigue mediante transformaciones elementales de
renglon (TER):
TER1 Multiplicar un renglón por constantes distintas a cero
TER2 Intercambiar dos renglones cualquiera
TER3 Multiplicar el i-ésimo renglón por una constante α 6= 0 y sumar el resultado al k-ésimo renglón, después
reemplazar el k-ésimo renglón por el resultado. El i-ésimo renglón es llamado pivote.
La naturaleza del sistema lineal se preserva bajo TER
Métodos directos Ejemplo 1
Ejemplo 1
Utilizando eliminación Gaussiana encontrar la solución
x1, x2, x3, x4 del sistema cuya matriz aumentada es
−1 2 3 1 3
2 −4 1 2 −1
−3 8 4 −1 6
1 4 7 −2 −4

Solución:
Se toma el primer renglón como pivote, se multiplica
por 2, -3 y 1 para sumarlo con los renglones 2, 3 y 4,
respectivamente
−1 2 3 1 3
0 0 7 4 5
0 2 −5 −4 −3
0 6 10 −1 −3

Intercambiando renglones 2 y 3
−1 2 3 1 3
0 2 −5 −4 −3
0 0 7 4 5
0 6 10 −1 −1

Se toma el renglón 2 como pivote, se multiplica por -2
y se suma con renglón 4
−1 2 3 1 3
0 2 −5 −4 −3
0 0 7 4 5
0 0 25 11 8

Métodos directos Ejemplo 1
Ejemplo 1
Se toma el renglón 3 como pivote, se multiplica por −25/7 y se suma con renglón 4
−1 2 3 1 3
0 2 −5 −4 −3
0 0 7 4 5
0 0 0 − 23
7
−−69
27

Se resuelve el sistema desde abajo
− 23
7
x4 = −
69
27
⇒ x4 = 3
7x3 + 4x4 = 5 ⇒ x3 = −1
2x2 − 5x3 − 4x4 = −3 ⇒ x2 = 2
− x1 + 2x2 + 3x3 + x4 = 3 ⇒ x1 = 1
Métodos directos Pivoteo parcial con escalamiento de renglón
Pivoteo parcial con escalamiento de renglón
Procedimiento
1 En cada renglón de A encontrar el mayor valor absoluto y llamarlo Mi
2 En cada renglón encontrar la razón del valor absoluto del coeficiente de x1 al valor absoluto de Mi
ri =
|ai1|
|Mi|
3 Elegir el mayor ri. Tomar como pivote al renglón que contiene este término. Eliminar x1 de los otros
renglones para obtener un nuevo sistema
4 En el nuevo sistema, considerar la submatriz (n− 1)× (n− 1) de la matriz de coeficientes y seguir la lógica
anterior para eliminar x2 y aśı sucesivamente.
Métodos directos Ejemplo 2
Ejemplo 2
Sea
[A|b] =
 −4 −3 5 06 7 −3 2
2 −1 1 6

Se toma la primer columna de la matriz aumentada y
se calcula
r1 =
| − 4|
|5| =
4
5
; r2 =
|6|
|7| =
6
7
; r3 =
|2|
|2| = 1
r3 es el valor más grande, por lo cual se elegirá como
pivote. Se intercambia renglón 1 con 3 2 −1 1 66 7 −3 2
−4 −3 5 0

Se multiplica primer rengón por −3 y 2, y se suman
resultados con segundo y tercer renglón,
respectivamente.
 2 −1 1 60 10 −6 −16
0 −5 7 12

r1 =
|10|
|10| = 1; r2 =
| − 5|
|7| =
5
7
r1 es el valor más grande, el segundo renglón se elige
como pivote. Se multiplica el segundo renglón por 1/2 y
se suma el resultado al tercer renglón. 2 −1 1 60 10 −6 −16
0 0 4 4

Se resuelve el sistema desde abajo
4x3 = 4 ⇒ x3 = 1
10x2 − 6x3 = −16 ⇒ x2 = −1
2x1 − x2 + x3 = 6 ⇒ x1 = 2
Métodos directos Factorización LU (Doolittle)
Métodos de factorización LU
Estos métodos se utilizan para reducir el número de
operaciones respecto a eliminación Gaussiana.
La factorización LU consiste en descomponer la
matriz A como
A = LU
Donde L es una matriz triangular inferior y U es una
matriz triangular superior
Factorización Doolittle
Se tiene A = LU, donde L es una matriz triangular
inferior con 1s en la diagonal principal y el negativo
de los multiplicadores (de eliminación Gaussiana)
debajo de la diagonal principal. U es la matriz
triangular superior de la matriz de coeficientes en el
paso final de la eliminación Gaussiana
Ejemplo 3
Obtener la factorización LU de la siguiente matriz
A =
1 3 62 −1 1
4 −2 3

Solución:
Se toma el primer renglón como pivote, se multiplica
por -2 y -4 y se suma con los renglones 2 y 3,
respectivamente.
Se toma el segundo renglón como pivote, se
multiplica por -2 y se suma con el renglón 3.
Con lo anterior se forman las matrices
L =
1 0 02 1 0
4 2 1
 ; U =
1 3 60 −7 −11
0 0 1

Métodos directos Factorización LU (Doolittle)
Cálculo directo de L y U (Doolittle)
Basado en la estructura de L y U en la factorización Doolittle, para el
caso de un sistema de 3 ecuaciones
L =
 1 0 0l21 1 0
l31 l32 1
 U =
u11 u12 u130 u22 u23
0 0 u33

Sabemos que A = LU, entoncesa11 a12 a13a21 a22 a23
a31 a32 a33
 =
 u11 u12 u13l21u11 l21u12 + u22 l21u13 + u23
l31u11 l31u12 + l32u22 l31u31 + l32u23 + u33

Se debe preservar la igualdad, por lo que el primer renglón de U se
puede calcular como
u11 = a11 u12 = a12 u13 = a13
Los elementos de primer columna de L se encuentran como
l21 =
a21
u11
l31 =
a31
u11
Los elementos del segundo renglón de
U se calculan con
u22 = a22 − l21u12
u23 = a23 − l21u13
El elemento de la segunda columna de
L es
l32 =
a32 − l31u12
u22
Finalmente el elemento del tercer
renglón de U
u33 = a33 − l31u13 − l32u23
Métodos directos Factorización LU (Doolittle)
Factorización Doolittle
De forma general se tiene
A = LU
L =

1 0 0 0 . . . 0
l21 1 0 0 . . . 0
l31 l32 1 0 . . . 0
l41 l42 l43 1 . . . 0
...
...
...
...
. . . 0
ln1 ln2 ln3 ln3 . . . 1

U =

u11 u12 u13 u14 . . . u1n
0 u22 u23 u24 . . . u2n
0 0 u33 u34 . . . u3n
0 0 0 u44 . . . u4n
...
...
...
...
. . .
...
0 0 0 . . . unn

Factorización Doolittle
donde:
u1j = a1j
li1 =
ai1
u11
uij = aij −
i−1∑
k=1
likukj
lij =
aij −
∑j−1
k=1 likukj
ujj
Método de Doolittle
Sea el sistema Ax = x con A = LU, entonces
[LU]x = b⇒ L[Ux] = b
Se resuelve en dos pasos
Ly = b
Ux = y
Cada uno de los sitemas es triangular, por lo tanto se
requiere sustitución hacia adelante y hacia atrás para
resolver.
Métodos directos Ejemplo 4
Ejemplo 4
Resuelva el sistema de ecuaciones Ax = b
mediante método de Doolittle, donde
A =
 3 1 1−3 −3 1
3 −3 6
 ; b =
 2−4
0

Solución:
Se buscanlas siguientes matrices
L =
 1 0 0l21 1 0
l31 l32 1

U =
u11 u12 u130 u22 u23
0 0 u33

Para u11, u12, u13
i = 1, j = 1
u1j = a1j
u11 = a11 = 3
i = 1, j = 2
u1j = a1j
u12 = a12 = 1
i = 1, j = 3
u1j = a1j
u13 = a13 = 1
Para l21, l31
i = 2, j = 1
li1 =
ai1
u11
l21 =
a21
u11
l21 =
−3
3
= −1
i = 3, j = 1
li1 =
ai1
u11
l31 =
a31
u11
l31 =
3
3
= 1
Métodos directos Ejemplo 4
Ejemplo 4
Para u22, u23
i = 2, j = 2
uii = aii −
i−1∑
k=1
likuki
u22 = a22 − l21u12
u22 = −3− (−1)(1) = −2
i = 2, j = 3
uij = aij −
i−1∑
k=1
likukj
u23 = a23 − l21u13
u23 = 1− (−1)(1) = 2
Para l32
i = 3, j = 2
lij =
aij −
∑j−1
k=1 likukj
ujj
l32 =
a32 − l31u12
u22
l32 =
−3− (1)(1)
−2 = 2
Para u33
i = 3, j = 3
uii = aii −
i−1∑
k=1
likuki
u33 = a33 − l31u13 − l32u23
u33 = 6− (1)(1)− (2)(2) = 1
Se obtiene la factorización.
L =
 1 0 0−1 1 0
1 2 1
 U =
3 1 10 −2 2
0 0 1

Se resuelve en dos pasos
Ly = b
Ux = y
Se resuelve primero y
y1 = 2
−y1 + y2 = −4
y1 + 2y2 + y3 = 0
y1 = 2; y2 = −2; y3 = 2
Métodos directos Ejemplo 4
Ejemplo 4
Se resuelve Ux = y
3x1 + x2 + x3 = 2
− 2x2 + 2x3 = −2
x3 = 2
x3 = 2; x2 = 3; x1 = −1
Por lo tanto el vector solución del sistema de ecuaciones
lineales está dado por
x =
−13
2

Métodos directos Factorización LU (Crout)
Descomposición de Crout
Es una descomposición alternativa para
A = LU.
Involucra una matriz U con 1s en la diagonal
principal.
La idea es similar al desarrollo de la
descomposición de Doolittle.
L =

l11 0 0 0 . . . 0
l21 l22 0 0 . . . 0
l31 l32 l33 0 . . . 0
l41 l42 l43 l44 . . . 0
...
...
...
...
. . . 0
ln1 ln2 ln3 ln3 . . . lnn

U =

1 u12 u13 u14 . . . u1n
0 1 u23 u24 . . . u2n
0 0 1 u34 . . . u3n
0 0 0 1 . . . u4n
...
...
...
...
. . .
...
0 0 0 . . . 1

Descomposición Crout
donde:
li1 = ai1
u1j =
a1j
l11
lij = aij −
j−1∑
k=1
likukj
uij =
aij −
∑i−1
k=1 likukj
lii
Método de Crout
Sea el sistema Ax = x con A = LU, entonces
[LU]x = b⇒ L[Ux] = b
Se resuelve en dos pasos
Ly = b
Ux = y
Cada uno de los sitemas es triangular, por lo tanto se
requere sustitución hacia adelante y hacia atrás para
resolver.
Métodos directos Ejemplo 5
Ejemplo 5
Resuelva el sistema de ecuaciones Ax = b
mediante método de Crout donde
A =
 3 1 1−3 −3 1
3 −3 6
 ; b =
 2−4
0

Solución:
Se buscan las siguientes matrices
L =
l11 0 0l21 l22 0
l31 l32 l33

U =
1 u12 u130 1 u23
0 0 1

Para l11, l21, l31
i = 1, j = 1
li1 = ai1
u11 = a11 = 3
i = 2, j = 1
li1 = ai1
u21 = a21 = −3
i = 3, j = 1
li1 = ai1
u31 = a31 = 3
Para u12, u13
i = 1, j = 2
u1j =
a1j
l11
l12 =
a12
l11
l12 =
1
3
i = 1, j = 3
u1j =
a1j
l11
l13 =
a13
l11
l13 =
1
3
Métodos directos Ejemplo 5
Ejemplo 5
Para l22, l32
i = 2, j = 2
lij = aij −
j−1∑
k=1
likukj
l22 = a22 − l21u12
l22 = −3− (−3)(1/3)
= −2
i = 3, j = 2
lij = aij −
j−1∑
k=1
likukj
l32 = a32 − l31u12
l32 = −3− (3)(1/3)
= −4
Para u23
i = 2, j = 3
uij =
aij −
∑i−1
k=1 likukj
lii
u23 =
a23 − l21u13
l22
u23 =
1− (−3)(1/3)
−2
Para l33
i = 3, j = 3
lij = aij −
j−1∑
k=1
likukj
l33 = a33 − l31u13 − l32u23
l33 = 6− (3)(1/3)− (−4)(−1)
= 1
Se obtiene la factorización.
L =
 3 0 0−3 −2 0
3 −4 1

U =
1 1/3 1/30 1 −1
0 0 1

Se resuelve en dos pasos
Ly = b
Ux = y
Se resuelve primero y
3y1 = 2
−3y1 − 2y2 = −4
3y1 − 4y2 + y3 = 0
y1 = 2/3; y2 = 1; y3 = 2
Métodos directos Ejemplo 5
Ejemplo 5
Se resuelve Ux = y
x1 + (1/3)x2 + (1/3)x3 = 2/3
x2 − x3 = 1
x3 = 2
x3 = 2; x2 = 3; x1 = −1
Por lo tanto el vector solución del sistema de ecuaciones
lineales está dado por
x =
−13
2

Métodos iterativos Norma de vectores y matrices
Métodos iterativos
Llamados métodos indirectos
Inician con un vector inicial y generan
aproximaciones sucesivas que convergen
al vector solución x
Número de operaciones dependerá de
los pasos a realizar para una
convergencia satisfactoria y de la
naturaleza del problema
Convergencia: La iteración finalizará
cuando dos vectores sucesivos entre śı
estén suficientemente cercanos entre śı.
Una medida de proximidad de dos vectores
es dada por la norma de un vector
Norma de un vector
Es una medida de qué tan pequeño o grande es un vector.
Propiedades:
||v|| ≥ 0 para todo v, y ||v|| = 0 śı y sólo śı v = 0
||αv|| = α||v||, α escalar
||v + w|| ≤ ||v||+ ||w||
Sea v =
[
v1 v2 . . . vn
]T
La norma L1, ||v||1
||v||1 = |v1|+ |v2|+ . . .+ |vn|
La norma L∞, ||v||∞
||v||∞ = máx {|v1|, |v2|, . . . , |vn|}
La norma L2, ||v||2
||v||2 =
[
v21 + v
2
2 + . . .+ v
2
n
]1/2
Métodos iterativos Norma de vectores y matrices
Norma de una matriz
Es una medida de qué tan pequeño o grande es una matriz. Sea An×n.
Propiedades:
‖A‖ ≥ 0 para todo A, y ‖A‖ = 0 śı y sólo śı
A = 0
‖αA‖ = α ‖A‖, α escalar
‖A + B‖ ≤ ‖A‖+ ‖B‖
‖AB‖ ≤ ‖A‖ ‖B‖
La norma 1 (Norma de suma de columna), ||A||1
||A||1 = máx
1≤j≤n
{
n∑
i=1
|aij |
}
La norma infinito (norma de suma de renglón),
||A||∞
||A||∞ = máx
1≤i≤n
{
n∑
j=1
|aij |
}
La norma 2 (norma euclideana, norma de
Frobenius), ||A||E
||A||E =
[
n∑
i=1
n∑
j=1
a2ij
]1/2
Métodos iterativos Método iterativo general
Método iterativo de solución
Se parte del sistema Ax = b, se define A = [Q−P], tal que Q sea no singular para que Q−1 exista.
Sustituyendo se tiene
Ax = b
[Q−P]x = b⇒ Qx = Px + b
El sistema no se puede resolver en esta forma, ya que el vector solución aparece en ambos lados de la igualdad.
Para resolverlo iterativamente, se elige un vector inicial x0 para resolver en términos de un nuevo vector x1
Qx1 = Px0 + b
De forma general se puede generar la secuencia
Qxk+1 = Pxk + b; k = 0, 1, 2, . . .
La ecuación anterior se resuelve en cada paso como
xk+1 = Q
−1Pxk + Q
−1b; k = 0, 1, 2, . . .
Métodos iterativos Método de Jacobi
Método iterativo de solución de Jacobi
Sean D,L y U las porciones diagonal, inferior y superior
triangular de la matriz A, respectivamente, esto es
D =

a11 0 . . . 0
0 a22 . . . 0
...
...
. . .
...
0 0 . . . ann

L =

0 0 . . . 0
a21 0 . . . 0
...
...
. . .
...
an1 an2
... 0

U =

0 a12 . . . a1n
0 0 . . . a2n
...
...
. . .
...
0 0
... 0

En el método de Jacobi, la matriz A se parte como
A = Q−P
= D + [L + U]
tal que Q = D, P = −[L + U].
La ecuación de iteración se transforma como
Qxk+1 = Pxk + b
Dxk+1 = −[L + U]xk + b
Métodos iterativos Método de Jacobi
Método iterativo de solución de Jacobi
Para que D−1 exista, la diagonal principal de D y A
debe ser distinta de cero. Si D−1 existe se tiene
xk+1 = D
−1 {−[L + U]xk + b}
Observaciones:
L + U es la matriz A pero sin la diagonal
principal
Los elementos de la diagonal principal de D−1
son 1
aii
para i = 1, 2, . . . , n
Si xk =
[
x1(k) x2(k) . . . xn(k)
]T
, podemos
reescribir cada elemento del vector x como
xi(k+1) =
1
aii
−
n∑
j = 1
j 6= i
aijxj(k) + bi

i = 1, 2, . . . , n
Convergencia del método iterativo de Jacobi
Una condición de convergencia del método de Jacobi
está dada por
‖MJ‖∞ < 1 donde MJ = −D
−1[L + U]
El método converge para matrices dominantes
diagonales
Una matriz A es dominante diagonal si
|aii| >
n∑
j = 1
j 6= i
|aij |, ó equivalentemente
n∑
j = 1
j 6= i
|aij |
|aii|
< 1
i = 1, 2, . . . , n
El método finaliza cuando ‖xk+1 − xk‖2 < ε
Métodos iterativos Ejemplo 6
Ejemplo 6
Sea el sistema de ecuaciones
10x1 − x2 + 2x3 = 6
−x1 + 11x2 − x3 + 3x4 = 25
2x1 − x2 + 10x3 − x4 = −11
3x2 − x3 + 8x4 = 15
Resuelva el sistema utilizando el método de Jacobi,
considerando x0 = [0 0 0 0]
T y ε = 0.001.
Solución:
A =

10 −1 2 0
−1 11 −1 3
2 −1 10 −1
0 3 −1 8
 ; b =

6
25
−11
15

Verificando que la matriz A sea dominante diagonal
|aii| >
n∑
j = 1
j 6= i
|aij |
Para i = 1
|a11| > |a12|+ |a13|+ |a14|
|10| > | − 1|+ |2|+ |0|
10 > 3 X
Para i = 2
|a22| > |a21|+ |a23|+ |a24|
|11| > | − 1|+ | − 1|+ |3|
11 > 5 XPara i = 3
|a33| > |a31|+ |a32|+ |a34|
|10| > |2|+ | − 1|+ | − 1|
10 > 4 X
Métodos iterativos Ejemplo 6
Ejemplo 6
Para i = 4
|a44| > |a41|+ |a42|+ |a43|
|8| > |0|+ |3|+ | − 1|
8 > 4 X
Śı es dominante diagonal.
xi(k+1) =
1
aii
−
n∑
j = 1
j 6= i
aijxj(k) + bi
 ,
i = 1, 2, . . . , n
Para la primera iteración del método k = 0
Para el elemento x1
x1(1) =
1
a11
[
−
(
a12x2(0) + a13x3(0) + a14x4(0)
)
+ b1
]
x1(1) =
1
10
[− ((−1)(0) + (2)(0) + (0)(0)) + 6]
x1(1) = 0.6
Para el elemento x2
x2(1) =
1
a22
[
−
(
a21x1(0) + a23x3(0) + a24x4(0)
)
+ b2
]
x2(1) =
1
11
[− ((−1)(0) + (−1)(0) + (3)(0)) + 25]
x2(1) = 2.2727
Métodos iterativos Ejemplo 6
Ejemplo 6
Para el elemento x3
x3(1) =
1
a33
[
−
(
a31x1(0) + a32x2(0) + a34x4(0)
)
+ b3
]
x3(1) =
1
10
[− ((2)(0) + (−1)(0) + (−1)(0)) + (−11)]
x3(1) = −1.1
Para el elemento x4
x4(1) =
1
a44
[
−
(
a41x1(0) + a42x2(0) + a43x3(0)
)
+ b4
]
x4(1) =
1
8
[− ((0)(0) + (3)(0) + (−1)(0)) + 15]
x4(1) = 1.875
De la primera iteración se obtiene
x1 =
[
0.6 2.2727 −1.1 1.875
]T
Para la segunda iteración del método k = 1
Para el elemento x1
x1(2) =
1
a11
[
−
(
a12x2(1) + a13x3(1) + a14x4(1)
)
+b1]
x1(2) = 1.0473
Para el elemento x2
x2(2) =
1
a22
[
−
(
a21x1(1) + a23x3(1) + a24x4(1)
)
+b2]
x2(2) = 1.7159
Para el elemento x3
x3(2) =
1
a33
[
−
(
a31x1(1) + a32x2(1) + a34x4(1)
)
+b3]
x3(2) = −0.8052
Métodos iterativos Ejemplo 6
Ejemplo 6
Para el elemento x4
x4(2) =
1
a44
[
−
(
a41x4(1) + a42x2(1) + a43x3(1)
)
+b4]
x1(2) = 0.8852
De la segunda iteración se obtiene
x2 =
[
1.0473 1.7159 −0.8052 0.8852
]T
k 0 1 2 . . . 11
x1 0 0.6000 1.0473 . . . 0.9999
x2 0 2.2727 1.7159 . . . 2.0001
x3 0 -1.1000 -0.8052 . . . -1.0001
x4 0 1.8750 0.8852 . . . 1.0001
Métodos iterativos Método de Gauss-Seidel
Método de Gauss-Seidel
Se parte de las ecuaciones obtenidas en el método de
Jacobi
xk+1 = D
−1 {−[L + U]xk + b} k = 0, 1, 2, . . .
xi(k+1) =
1
aii
−
n∑
j = 1
j 6= i
aijxj(k) + bi
 , i = 1, 2, . . . , n
Observaciones:
Toda componente de xk+1 es calculada totalmente
a partir de xk (iteración pasada)
Para acceder a xk+1 la k-ésima iteración debe ser
completada
El desempeño del método de Jacobi puede mejorar
si los componentes del vector más actualizados son
utilizados tan pronto como estén disponibles, para
calcular componentes subsecuentes del mismo
vector
Considere dos vectores sucesivos y la solución actual
xk =

x1(k)
...
xp(k)
xp+1(k)
...
xn(k)

xk+1 =

x1(k+1)
...
xp(k+1)
xp+1(k+1)
...
xn(k+1)

xa =

x1
...
xp
xp+1
...
xn

En general xp(k+1) es un mejor estimado de xp que
xp(k)
Utilizando xp(k+1) en lugar de xp(k) lleva a una
mejor aproximación del siguiente componente
xp+1(k) en el valor actual
Siguiendo esta lógica se define el método iterativo
Gauss-Seidel, se considera un refinamiento del
método de Jacobi
Métodos iterativos Método de Gauss-Seidel
Método de Gauss-Seidel
De acuerdo a la lógica anterior, la matriz A se
descompone como
A = Q−P
= [D + L] + U
tal que Q = D + L y P = −U. Donde [D + L] es una
matriz diagonal inferior. Con esto se llega
[D + L]xk+1 = −Uxk + b
xk+1 = −[D + L]−1Uxk + [D + L]−1b
Śı xk =
[
x1(k) x2(k) . . . xn(k)
]T
xi(k+1) =
1
aii
{
−
i−1∑
j=1
aijxj(k+1) −
n∑
j=i+1
aijxj(k) + bi
}
i = 1, 2, . . . , n
donde la primera suma se considera cero cuando i = 1
Criterio de convergencia
Condición de convergencia
‖MGS‖∞ < 1
MGS = −[D + L]−1U
Condición de fin de iteración
‖xk+1 − xk‖ < ε
Métodos iterativos Ejemplo 7
Ejemplo 7
Sea el sistema lineal Ax = b con
A =
 4 1 −1−2 5 0
2 1 6
 , b =
 1−7
13
 ; x =
x1x2
x3

Resuelva utilizando el método de Gauss-Seidel
considerando x0 =
[
0 1 1
]T
y ε = 0.001
xi(k+1) =
1
aii
{
−
i−1∑
j=1
aijxj(k+1) −
n∑
j=i+1
aijxj(k) + bi
}
i = 1, 2, . . . , n
Solución:
Para primera iteración k = 0
Para el elemento x1
x1(1) =
1
a11
{
−(a12x2(0) + a13x3(0)) + b1
}
x1(1) =
1
4
{−((1)(1) + (−1)(1)) + 1}
x1(1) = 0.25
Para el elemento x2
x2(1) =
1
a22
{
−(a21x1(1) + a23x3(0)) + b2
}
x2(1) =
1
5
{−((−2)(0.25) + (0)(1)) + (−7)}
x2(1) = −1.3
Para el elemento x3
x3(1) =
1
a33
{
−(a31x1(1) + a32x2(1)) + b3
}
x3(1) =
1
6
{−((2)(0.25) + (1)(−1.3)) + 13}
x3(1) = 2.3
De la primera iteración se obtiene
x1 =
[
0.25 −1.3 2.3
]
Métodos iterativos Ejemplo 7
Ejemplo 7
Para segunda iteración k = 1
Para el elemento x1
x1(2) =
1
a11
{
−(a12x2(1) + a13x3(1)) + b1
}
x1(2) =
1
4
{−((1)(−1.3) + (−1)(2.3)) + 1}
x1(2) = 1.15
Para el elemento x2
x2(2) =
1
a22
{
−(a21x1(2) + a23x3(1)) + b2
}
x2(2) =
1
5
{−((−2)(1.15) + (0)(2.3)) + (−7)}
x2(2) = −0.94
Para el elemento x3
x3(2) =
1
a33
{
−(a31x1(2) + a32x2(2)) + b3
}
x3(2) =
1
6
{−((2)(1.15) + (1)(−0.94)) + 13}
x3(2) = 1.94
De la segunda iteración se obtiene
x2 =
[
1.15 −0.94 1.94
]
k 0 1 2 . . . 7
x1 0 0.25 1.15 . . . 1
x2 1 -1.3 -0.94 . . . -1
x3 1 2.3 1.94 . . . 2
Problema de eigenvalores Eigenvalores de una matriz
Eigenvalores de una matriz
Av = λv, v 6= 0
Un número λ para el cual la ecuación anterior
posee solución distinta a la trivial es conocido
como eigenvalor (valor caracteŕıstico) de la
matriz A
La solución correspondiente v 6= 0 es el
eigenvector (vector caracteŕıstico) de la
matriz A para λ
(A− λI)v = 0
Los valores de λ que satisfacen la ecuación
anterior están dados por
|A− λI| = 0
De esta expresión se obtiene su polinomio
caracteŕıstico
λn + b1λ
n−1 + b2λ
n−2 + . . .+ bn−1λ+ bn = 0
p(λ) = 0
Del teorema de Caley-Hamilton: toda matriz cuadrada
satisface su ecuación caracteŕıstica p(A) = 0
p(A) = An + b1A
n−1 + b2A
n−2 + . . .+ bn−1A + bnI = 0
An = −
n∑
k=1
bkA
n−k
Multiplicando por un vector distinto a cero x0
Anx0 = −
n∑
k=1
bkA
n−kx0
Con lo anterior se obtiene un sistema de ecuaciones
algebraicas. Al resolverlo se obtienen los coeficientes de
la ecuación caracteŕıstica
Finalmente se encuentran las ráıces para la ecuación
caracteŕıstica y se determinan los eigenvalores
NOTA: Este método sirve para plantear el problema sin
resolver el determinante |A− λI| = 0
Problema de eigenvalores Ejemplo 8
Ejemplo 8
Encuentre el polinomio caractŕıstico de la siguiente
matriz
A =
 3 1 2−2 −1 0
−1 0 3

considere x0 =
[
1 0 0
]T
.
Solución:
El polinomio que se busca es
λ3 + b1λ
2 + b2λ+ b3 = 0
El problema que se debe resolver es
A3x0 = −b1A2x0 − b2Ax0 − b3Ix0 −1 3 46−6 −3 −20
−23 −5 9
10
0
 = −b1
 5 2 12−4 −1 −4
−6 −1 7
10
0

−b2
 3 1 2−2 −1 0
−1 0 3
10
0
− b3
1 0 00 1 0
0 0 1
10
0

 −1−6
−23
 = b1
−54
6
+ b2
−32
1
+ b3
−10
0

5 −3 −14 2 0
6 1 0
b1b2
b3
 =
 −1−6
−23

Resolviendo el sistema de ecuaciones lineales se
obtiene b1 = −5, b2 = 7, b3 = 5
λ3 + b1λ
2 + b2λ+ b3 = 0
λ3 + (−5)λ2 + (7)λ+ (5) = 0
Se resuelve el polinomio y se tiene que los
eigenvalores son
λ1 = −0.5098
λ2 = 2.7549 + 1.4897i
λ3 = 2.7549− 1.4897i
Problema de eigenvalores Método de las potencias
Método de las potencias
Es un método iterativo para estimar el eigenvalor
dominante de una matriz An×n. Suposiciones
An×n es una matriz real
An×n tiene n eigenvalores λ1, λ2, . . . , λn donde λ1
es el eigenvalor dominante
|λ1| ≥ |λ2| ≥ |λ3| ≥ . . . ≥ |λn|
y sus eigenvectores correspondientes
v1,v2, . . . ,vn son linealmente independientes
El eigenvalor dominante es real
Como v1,v2, . . . ,vn es un conjunto linealmente
independiente, existen constantes c1, c2, . . . , cn tal que
un vector arbitrario x0 puede ser expresado únicamente
como
x0 = c1v1 + c2v2 + . . .+ cnvn
El problema de eigenvalores es
Avi = λivi
A(Avi) = A(λivi)⇒ A2vi = λ2ivi
de forma general
Akvi = λ
k
i vi
Se define la secuencia de vectores
x1 = Ax0
x2 = Ax1 = A
2x0
...
xk = Axk−1 = A
kx0
Problema de eigenvalores Método de las potencias
Método de las potencias
El vector xk se puede definircomo
xk = A
kx0 = A
k [c1v1 + c2v2 + . . .+ cnvn]
= c1λ
k
1v1 + c2λ
k
2v2 + . . .+ cnλ
k
nvn
= λk1
[
c1v1 + c2
(
λ2
λ1
)k
v2 + . . .+ cn
(
λn
λ1
)k
vn
]
Como λ1 es el eigenvalor dominante, las relaciones
λ2
λ1
, λ3
λ1
, . . . , λn
λ1
son menores a 1, entonces para un valor
suficientemente grande k tenemos
xk ∼= c1λ1v1
Esta expresión se puede utilizar para obtener
xk+1 ∼= c1λk+1v1. Entonces
xk+1 ∼= λ1xk
La estimación de λ1 se obtiene premultiplicando por x
T
k
λ1 ∼=
xTk xk+1
xTk xk
El método de las potencias establece que la secuencia
de escalares
αk+1 =
xTk xk+1
xTk xk
, xk+1 = Axk
Converge al eigenvalor dominante λ1 para una k
suficientemente grande.
Se puede demostrar que la secuencia {αk} converge
a λ1 a una velocidad parecida en que (λ2/λ1)
k → 0
Entre mayor sea la magnitud de λ1 comparado con
λ2, la velocidad de convergencia es mayor
Como las componentes de xk crecen rápidamente,
es común normalizar xk, esto es dividir cada vector
xk por su norma 2, ‖xk‖2. Como consecuencia el
denominador se simplifica y se convierte en
xTk xk = 1, por lo tanto αk+1 = x
T
k xk+1
El método finaliza con |αk+1 − αk| < ε
Problema de eigenvalores Método de las potencias
Algoritmo del método de las potencias
Se comienza con una matriz A, un vector inicial x1 y
α1 = 0
1 Se normaliza x1 para obtener un vector unitario
⇒ x1 = x1‖x1‖2
Para k = 1, hasta el número máximo de iteraciones
2 Encontrar xk+1 = Axk
3 Calcular αk+1 = x
T
k xk+1
4 Normalizar xk+1 ⇒ xk+1 = xk+1‖xk+1‖2
5 Verificar si se cumple que |αk+1 − αk| < ε, en caso
contrario incrementar k a k+ 1 y regresar al paso 2.
Problema de eigenvalores Ejemplo 9
Ejemplo 9
Obtenga el eigen-valor dominante de la siguiente matriz
A =
−3 −4 −2−1 4 1
2 −6 −1

comenzando con α1 = 0, x1 =
[
1 1 1
]T
y una tolerancia
de ε = 10−4.
Solución:
Primera iteración k = 1
x1 =
x1
‖x1‖2
=
1√
3
11
1
 =
0.57740.5774
0.5774

x2 = Ax1 =
 3 −4 −2−1 4 1
2 −6 −1
0.57740.5774
0.5774
 =
−1.73212.3094
−2.8868

α2 = x
T
1 x2 = −1.3333
x2 =
x2
‖x2‖2
=
−0.42430.5657
−0.7071
 |α2 − α1| = 1.3333
Segunda iteración k = 2
x3 = Ax2 =
 3 −4 −2−1 4 1
2 −6 −1
−0.42430.5657
−0.7071

x3 =
−2.12131.9799
−3.5355

α3 = x
T
2 x3 = 4.52
x3 =
x3
‖x3‖2
=
−0.46380.4329
−0.7730

|α3 − α2| = 5.8533
k 1 2 3 . . . 20
x1 0.5774 -0.4243 -0.4638 . . . -0.4086
x2 0.5774 0.5657 0.4329 . . . 0.4082
x3 0.5774 -0.7071 -0.7730 . . . -0.8163
αk 0 -1.3333 4.5200 . . . 3.0014
	Métodos directos
	Eliminación Gaussiana
	Ejemplo 1
	Pivoteo parcial con escalamiento de renglón
	Ejemplo 2
	Factorización LU (Doolittle)
	Ejemplo 4
	Factorización LU (Crout)
	Ejemplo 5
	Métodos iterativos
	Norma de vectores y matrices
	Método iterativo general
	Método de Jacobi
	Ejemplo 6
	Método de Gauss-Seidel
	Ejemplo 7
	Problema de eigenvalores
	Eigenvalores de una matriz
	Ejemplo 8
	Método de las potencias
	Ejemplo 9