TEMA 3 [Modo de compatibilidad] - joseluisquintero.com Numerico/Clases/TEMA 3.pdf · Suponga que la...
Transcript of TEMA 3 [Modo de compatibilidad] - joseluisquintero.com Numerico/Clases/TEMA 3.pdf · Suponga que la...
SISTEMAS
DE
ECUACIONES
16 de Mayo de 2013
Cálculo Numérico José Luis Quintero 1
ECUACIONESDepartamento de Matemática Aplicada
Facultad de Ingeniería
Universidad Central de Venezuela
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 2
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Suponga que la matriz A de tiene unaestructura diagonal. Esto significa que todoslos componentes distintos de cero de A seencuentran sobre la diagonal principal y elsistema es de la forma:
Sistemas fáciles de resolver
n n×
a 0 0 0 x b …
Cálculo Numérico José Luis Quintero 3
11 1 1
22 2 2
33 3 3
nn n n
a 0 0 0 x b
0 a 0 0 x b
.0 0 a 0 x b
0 0 0 a x b
=
…
…
…
⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
…
En este caso el sistema se reduce a necuaciones simples y la solución es:
Sistemas fáciles de resolver
1 11
2 22
3 33
b a
b a
x .b a
=
Cálculo Numérico José Luis Quintero 4
Si para algún índice i, y también,entonces puede ser cualquier número real.Si y no hay solución alguna.
3 33
n nn
x .b a
b a
=
⋮
iia 0=
ib 0=
ix
iia 0=
ib 0,≠
Suponga que la matriz A de tiene unaestructura triangular inferior. Esto significa quetodos los elementos de A distintos de cero sesitúan sobre la diagonal principal o debajo deella y el sistema es de la forma:
Sistemas fáciles de resolver
n n×
a 0 0 0 x b …
Cálculo Numérico José Luis Quintero 5
11 1 1
21 22 2 2
31 32 33 3 3
n1 n2 n3 nn n n
a 0 0 0 x b
a a 0 0 x b
.a a a 0 x b
a a a a x b
=
…
…
…
⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
…
Para resolver el sistema, suponga paratodo i; en tal caso se obtiene a partir de laprimera ecuación. Sustituyendo el valorconocido de en la segunda ecuación,resuélvala para
Procediendo de la misma forma, se obtienen
Sistemas fáciles de resolver
1x
iia 0≠
1x
2x .
Cálculo Numérico José Luis Quintero 6
Procediendo de la misma forma, se obtienenlos valores en este orden. En estecaso el pseudocódigo para encontrar lasolución se llama sustitución progresiva:
1 2 nx ,x ,...,x ,
Sistemas fáciles de resolver
ij i
1 1 11
1
inicio
leer (n,(a ),(b ))
x b a
escribir(x )
desde i 2 hasta n hacer
←
=
Cálculo Numérico José Luis Quintero 7
i 1
i i ij j ii
j 1
i
desde i 2 hasta n hacer
x b a x a
escribir(x )
fin_ desde
fin
−
=
=
← −
∑
Suponga que la matriz A de tiene unaestructura triangular superior. Esto significaque todos los elementos de A distintos decero se sitúan sobre la diagonal principal oencima de ella y el sistema es de la forma:
Sistemas fáciles de resolver
n n×
a a a a x b …
Cálculo Numérico José Luis Quintero 8
11 12 13 1n 1 1
22 23 2n 2 2
33 3n 3 3
nn n n
a a a a x b
0 a a a x b
.0 0 a a x b
0 0 0 a x b
=
…
…
…
⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
…
Para resolver el sistema, suponga paratodo i; en tal caso se obtiene a partir de laúltima ecuación. Sustituyendo el valorconocido de en la penúltima ecuación,resuélvala para
Procediendo de la misma forma, se obtienen
Sistemas fáciles de resolver
nx
iia 0≠
nx
n 1x .−
Cálculo Numérico José Luis Quintero 9
Procediendo de la misma forma, se obtienenlos valores en este orden. En estecaso el pseudocódigo para encontrar lasolución se llama sustitución regresiva:
n n 1 1x ,x ,...,x ,−
Sistemas fáciles de resolver
ij i
n n nn
n
inicio
leer (n,(a ),(b ))
x b a
escribir(x )
desde i n 1 hasta 1 hacer
←
= −
Cálculo Numérico José Luis Quintero 10
n
i i ij j ii
j i 1
i
desde i n 1 hasta 1 hacer
x b a x a
escribir(x )
fin_ desde
fin
= +
= −
← −
∑
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 11
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Suponga que A se puede factorizar como elproducto de una matriz triangular inferior Lcon una matriz triangular superior U: .
En este caso, para resolver el sistema deecuaciones se puede proceder por
Factorizaciones LU
A LU=
Ax b=
Cálculo Numérico José Luis Quintero 12
ecuaciones se puede proceder poretapas como sigue:
Resolver para zResolver para x.
Ax b=
Lz b=Ux z=
El análisis previo muestra lo simple que esresolver estos dos sistemas triangulares.
Se verá como se puede llevar a cabo lafactorización con el supuesto de queen el cálculo no aparecen divisores iguales a
Factorizaciones LU
A LU=
Cálculo Numérico José Luis Quintero 13
en el cálculo no aparecen divisores iguales acero.
No toda matriz tiene una factorización de estaíndole, por lo que se debe investigar estadificultad. Se comenzará con una matriz A dey se buscarán matrices
tales que . Cuando esto es posible, se
Factorizaciones LU
A LU=
=
=
nn
n333
n22322
n1131211
nn3n2n1n
333231
2221
11
u000
uu00
uuu0
uuuu
U
llll
0lll
00ll
000l
L
⋯
⋮⋱⋮⋮⋮
⋯
⋯
⋯
⋯
⋮⋱⋮⋮⋮
⋯
⋯
⋯
Cálculo Numérico José Luis Quintero 14
tales que . Cuando esto es posible, sedice que A tiene una factorización LU. Esposible que L y U no se puedan determinar enforma única.
De hecho, para cada i, se puede asignar unvalor distinto de cero a o a (más no aambos).
A LU=
iil
iiu
Por ejemplo, una elección simple consiste enfijar para y de este modo Lqueda convertida en una matriz triangularinferior unitaria (Factorización de Doolittle).Otra elección obvia es hacer de U una matriztriangular superior unitaria ( para cada
Factorizaciones LU
iil 1= i 1,2,...,n,=
iiu 1=
Cálculo Numérico José Luis Quintero 15
triangular superior unitaria ( para cadai) (Factorización de Crout). Estos casosespeciales tienen una particular importancia.
Cuando de modo que parael algoritmo se llama factorización
de Cholesky.
iiu 1=
tU L=ii iil u=
1 i n,≤ ≤
Factorización LU
ij ii
11 11 11
1j 1j 11
j1 j1 11
kk kk ks s
inicio
leer (n,(a ),(l ))
u a l
desde j 2 hasta n hacer
u a l
l a u
fin _ desde
desde k 2 hasta n hacer
u a l u
←=
←
←
=
← −
k-1
k kk
s 1
k-1
l
desde j k 1 hasta n hacer
u a l u l
=
= + ← −
∑
∑
Cálculo Numérico José Luis Quintero 16
kj kj ks sj kk
s 1
u a l u l
fin _ desde
desde i k 1 hasta n hacer
=
← −
= +
∑
k-1
ik ik is sk kk
s 1
l a l u u
fin _ desde
fin_ desde
desde j 1 hasta n hacer
desde i j hasta n hacer
=
← −
==
∑
ij jiescribir(l ,u )
fin _ desde
fin_ desde
fin
Factorización de Doolittle
Ejemplo numérico 1
1 2 3
1 2 3
1 2 3
2x 4x 6x 18
4x 5x 6x 24
3x x 2x 4
+ + = + + = + − =
Cálculo Numérico José Luis Quintero 17
Factorización de Doolittle
3 52 3
2 4 6 1 0 0 2 4 6
A 4 5 6 2 1 0 0 3 6 LU
3 1 2 1 0 0 1
= = − − = − −
Sistemas a resolver
Ejemplo numérico 1
1 1
2 2
3 52 3 3 3
1 0 0 z 18 z 18
2 1 0 z 24 z 12
1 z 4 z 3
= ⇒ = − −
Cálculo Numérico José Luis Quintero 18
2 3 3 3
1 1
2 2
3 3
2 4 6 x 18 x 4
0 3 6 x 12 x 2
0 0 1 x 3 x 3
− − = − ⇒ = − − −
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 19
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Como ya se mencionó, hay una factorizaciónde matrices que resulta muy útil en algunassituaciones. A esta factorización se le hadado el nombre del matemático André LouisCholesky, quien demostró el siguienteresultado:
Factorización de Cholesky
Cálculo Numérico José Luis Quintero 20
resultado:
TEOREMA 1. Si A es una matriz real, simétrica ydefinida positiva, entonces tiene unafactorización única en donde L es una matriztriangular inferior con diagonal positiva.
El algoritmo para la factorización de Choleskyes un caso especial del algoritmo generalpara la factorización LU. Si A es real, simétricay definida positiva, entonces, por el teorema
Factorización de Cholesky
Cálculo Numérico José Luis Quintero 21
y definida positiva, entonces, por el teorema1, tiene una factorización única de la formadada por en donde L es triangularinferior y tiene una diagonal principal positiva
tA LL ,=
Factorización de Cholesky
( )
ij
1 2
11 11
j1 j1 11
1 2k-1
2kk kk ks
s 1
inicio
leer (n,(a ))
l a
desde j 2 hasta n hacer
l a l
fin_ desde
desde k 2 hasta n hacer
l a l
=
←
=←
=
← −
∑ desde i k 1 hasta n hacer= +
Cálculo Numérico José Luis Quintero 22
k-1
ik ik is ks kk
s 1
desde i k 1 hasta n hacer
l a l l l
fin_ desde
fin_ desde
desde i 1 hasta n hacer
desde j 1 hasta
=
= + ← −
==
∑
ij
n hacer
escribir(l )
fin_ desde
fin_ desde
fin
Factorización de Cholesky
Ejemplo numérico 2
1 2 3
1 2 3
1 2 3
x x x 2
x 5x x 12
x x 3x 12
− + =− + + = + + =
Cálculo Numérico José Luis Quintero 23
Factorización de Cholesky
t
1 1 1 1 0 0 1 1 1
A 1 5 1 1 2 0 0 2 1 LL
1 1 3 1 1 1 0 0 1
− − = − = − =
Sistemas a resolver
Ejemplo numérico 2
1 1
2 2
3 3
1 0 0 z 2 z 2
1 2 0 z 12 z 7
1 1 1 z 12 z 3
− = ⇒ =
Cálculo Numérico José Luis Quintero 24
3 3
1 1
2 2
3 3
1 1 1 x 2 x 1
0 2 1 x 7 x 2
0 0 1 x 3 x 3
− = ⇒ =
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 25
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Entre otros, la factorización LU y sus variantesson conocidos como métodos directos pararesolver el problema matricial Seejecutan a través de un número finito depasos y generan una solución x que sería
Métodos iterativos
Ax b.=
Cálculo Numérico José Luis Quintero 26
pasos y generan una solución x que seríaexacta si no fuera por los errores deredondeo.
En contraste, un método indirecto da lugar auna sucesión de vectores que idealmenteconverge a la solución. El cálculo se detienecuando se cuenta con una soluciónaproximada con cierto grado de precisión
Métodos iterativos
Cálculo Numérico José Luis Quintero 27
aproximada con cierto grado de precisiónespecificado de antemano o después decierto número de iteraciones.
Los métodos indirectos son casi siempreiterativos por naturaleza: para obtener lasucesión mencionada se utilizarepetidamente un proceso sencillo. Otraventaja de los métodos iterativos es que
Métodos iterativos
Cálculo Numérico José Luis Quintero 28
ventaja de los métodos iterativos es queusualmente son estables y de hechoamortiguan errores (debidos al redondeo o aerrores pequeños) conforme el proceso selleva a cabo.
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 29
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Sea
donde es el vector residual definidomediante
Método de Richardson
(k) (k 1) (k 1) (k 1)x (I A)x b x r ,− − −= − + = +
(k 1)r −
(k 1) (k 1)r b Ax .− −= −
Cálculo Numérico José Luis Quintero 30
La iteración de Richardson dará lugar a unasolución de (en el límite) sipara alguna norma matricial subordinada.
El siguiente pseudocódigo ejecuta la iteraciónde Richardson:
Ax b= I A 1− <
Método de Richardson
ij i i
n
i i ij j
j 1
inicio
leer (n,(a ),(b ),(x ),M,cot anorma)
cuadrado 0
desde k 1 hasta M hacer
desde i 1 hasta n hacer
r b a x
=
←=
=
← −∑
2icuadrado cuadrado r← +
Cálculo Numérico José Luis Quintero 31
i
1 2
i i
fin_ desde
norma (cuadrado)
escribir(k,norma)
desde i 1 hasta n hacer
x x r
←
=← +
i
i iescribir(x ,r)
fin_ desde
si norma cot anorma entonces stop
fin_ desde
fin
<
Ejemplo numérico 3
1 1 112 3 181
1 1 113 2 182
1 1 112 3 183
1 x
1 x
1 x
=
(0) t
(1) t
x (0.000000, 0.000000, 0.000000)
x (0.611111, 0.611111, 0.611111)
==
Cálculo Numérico José Luis Quintero 32
(10) t
(40)
x (0.279498, 0.279498, 0.279498)
x (0.333107, 0.3
=
=
⋮
⋮
t
(80) t
33107, 0.333107)
x (0.333333, 0.333333, 0.333333)=⋮
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 33
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
TEOREMA 2. Si A es diagonalmentedominante, entonces la sucesión que resultade la iteración de Jacobi converge a lasolución de para cualquier vectorinicial.
Método de Jacobi
Ax b=
Cálculo Numérico José Luis Quintero 34
inicial.
A continuación se presenta el pseudocódigopara el método de Jacobi:
Método de Jacobi
)u-x(cuadradocuadrado
axabu
hacer n hasta 1i desde
hacer M hasta 1k desde
0cuadrado
)anormacot,M),(x),(b),(a(n, leer
inicio
2ii
ii
n
ij1j
jijii
iiij
+←
−←
==←
∑≠=
Cálculo Numérico José Luis Quintero 35
fin
fin_desde
stop entonces cotanormanorma si
fin_desde
)r,escribir(x
u x
hacer n hasta 1i desde
norma),escribir(k
(cuadrado)norma
fin_desde
)u-x(cuadradocuadrado
ii
ii
21
ii
<
←=
←
+←
Ejemplo numérico 4
1
2
x7 6 3
x8 9 4
− = − −
(k) (k 1)6 37 71 2
(k) (k 1)8 49 92 1
x x
x x
−
−
= += −
Cálculo Numérico José Luis Quintero 36
9 92 1
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 37
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Método de Gauss Seidel
1
2
x7 6 3
x8 9 4
− = − −
(k) (k 1)6 37 71 2
(k) (k)8 49 92 1
x x
x x
−= += −
Cálculo Numérico José Luis Quintero 38
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 39
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Método de Newton
Cálculo Numérico José Luis Quintero 40
Método de Newton
Cálculo Numérico José Luis Quintero 41
Método de Newton
Cálculo Numérico José Luis Quintero 42
Método de Newton
Cálculo Numérico José Luis Quintero 43
Método de Newton
Cálculo Numérico José Luis Quintero 44
Método de Newton
Cálculo Numérico José Luis Quintero 45
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 46
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Métodos Cuasi-Newton
Cálculo Numérico José Luis Quintero 47
Métodos Cuasi-Newton
Cálculo Numérico José Luis Quintero 48
1. Sistemas fáciles de resolver
2. Factorizaciones LU
3. Factorización de Cholesky
4. Métodos iterativos
5. Método de Richardson
Puntos a tratar
Cálculo Numérico José Luis Quintero 49
6. Método de Jacobi
7. Método de Gauss Seidel
8. Método de Newton
9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 50
Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 51
Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 52
Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 53
Pensamiento de hoy
“Solo tengo una luz por la que seguían mis pasos, y esta luz es la de laexperiencia. No conozco otra manerade juzgar el futuro que rodea el
Cálculo Numérico José Luis Quintero 54
de juzgar el futuro que rodea elpasado”.
Patric Henry