01 de julio de 2016 sistemas de ecuaciones calculo numerico... · método de richardson 6. método...
TRANSCRIPT
Cálculo Numérico José Luis Quintero 1
01 de Julio de 2016
Postgrado de Investigación de OperacionesFacultad de Ingeniería
Universidad Central de Venezuela
SISTEMAS DE
ECUACIONES
Cálculo Numérico José Luis Quintero 2
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 3
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×
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
=
K
K
K
M M M O M M M
K
Cálculo Numérico José Luis Quintero 4
En este caso el sistema se reduce a necuaciones simples y la solución es:
Si para algún índice i, y también,entonces puede ser cualquier número real.Si y no hay solución alguna.
Sistemas fáciles de resolver
1 11
2 22
3 33
n nn
b a
b a
x .b a
b a
=
M
iia 0=
ib 0=
ix
iia 0=
ib 0,≠
Cálculo Numérico José Luis Quintero 5
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×
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
=
K
K
K
M M M O M M M
K
Cálculo Numérico José Luis Quintero 6
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 obtienenlos valores en este orden. En estecaso el pseudocódigo para encontrar lasolución se llama sustitución progresiva:
Sistemas fáciles de resolver
1x
iia 0≠
1x
2x .
1 2 nx ,x ,...,x ,
Cálculo Numérico José Luis Quintero 7
Sistemas fáciles de resolver
ij i
1 1 11
1
i 1
i i ij j ii
j 1
i
inicio
leer (n,(a ),(b ))
x b a
escribir(x )
desde i 2 hasta n hacer
x b a x a
escribir(x )
fin_ desde
fin
−
=
←
=
← −
∑
Cálculo Numérico José Luis Quintero 8
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×
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
=
K
K
K
M M M O M M M
K
Cálculo Numérico José Luis Quintero 9
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 obtienenlos valores en este orden. En estecaso el pseudocódigo para encontrar lasolución se llama sustitución regresiva:
Sistemas fáciles de resolver
nx
iia 0≠
nx
n 1x .−
n n 1 1x ,x ,...,x ,−
Cálculo Numérico José Luis Quintero 10
Sistemas fáciles de resolver
ij i
n n nn
n
n
i i ij j ii
j i 1
i
inicio
leer (n,(a ),(b ))
x b a
escribir(x )
desde i n 1 hasta 1 hacer
x b a x a
escribir(x )
fin_ desde
fin
= +
←
= −
← −
∑
Cálculo Numérico José Luis Quintero 11
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 12
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 poretapas como sigue:
Resolver para zResolver para x.
Factorizaciones LU
A LU=
Ax b=
Lz b=Ux z=
Cálculo Numérico José Luis Quintero 13
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 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
Factorizaciones LU
A LU=
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).
Factorizaciones LU
A LU=
=
=
nn
n333
n22322
n1131211
nn3n2n1n
333231
2221
11
u000
uu00
uuu0
uuuu
U
llll
0lll
00ll
000l
L
L
MOMMM
L
L
L
L
MOMMM
L
L
L
iil
iiu
Cálculo Numérico José Luis Quintero 15
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 cadai) (Factorización de Crout). Estos casosespeciales tienen una particular importancia.
Cuando de modo que parael algoritmo se llama factorización
de Cholesky.
Factorizaciones LU
iil 1= i 1,2,...,n,=
iiu 1=
tU L=ii iil u=
1 i n,≤ ≤
Cálculo Numérico José Luis Quintero 16
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
kj kj ks sj kk
s 1
l
desde j k 1 hasta n hacer
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
Cálculo Numérico José Luis Quintero 17
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
+ + = + + = + − =
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
= = − − = − −
Cálculo Numérico José Luis Quintero 18
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
= ⇒ = − −
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
− − = − ⇒ = − − −
Cálculo Numérico José Luis Quintero 19
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 20
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:
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.
Factorización de Cholesky
Cálculo Numérico José Luis Quintero 21
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 teorema1, tiene una factorización única de la formadada por en donde L es triangularinferior y tiene una diagonal principal positiva
Factorización de Cholesky
tA LL ,=
Cálculo Numérico José Luis Quintero 22
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
=
←
=←
=
← −
∑
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
Cálculo Numérico José Luis Quintero 23
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
− + =− + + = + + =
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
− − = − = − =
Cálculo Numérico José Luis Quintero 24
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
− = ⇒ =
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
− = ⇒ =
Cálculo Numérico José Luis Quintero 25
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 26
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íaexacta si no fuera por los errores deredondeo.
Métodos iterativos
Ax b.=
Cálculo Numérico José Luis Quintero 27
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ónespecificado de antemano o después decierto número de iteraciones.
Métodos iterativos
Cálculo Numérico José Luis Quintero 28
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 queusualmente son estables y de hechoamortiguan errores (debidos al redondeo o aerrores pequeños) conforme el proceso selleva a cabo.
Métodos iterativos
Cálculo Numérico José Luis Quintero 29
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 30
Sea
donde es el vector residual definidomediante
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:
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 .− −= −
Ax b= I A 1− <
Cálculo Numérico José Luis Quintero 31
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
=
←=
=
← −∑
2i
1 2
i i
cuadrado cuadrado r
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
<
Cálculo Numérico José Luis Quintero 32
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
(10) t
(40)
x (0.000000, 0.000000, 0.000000)
x (0.611111, 0.611111, 0.611111)
x (0.279498, 0.279498, 0.279498)
x (0.333107, 0.3
==
=
=
M
M
t
(80) t
33107, 0.333107)
x (0.333333, 0.333333, 0.333333)=M
Cálculo Numérico José Luis Quintero 33
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 34
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.
A continuación se presenta el pseudocódigopara el método de Jacobi:
Método de Jacobi
Ax b=
Cálculo Numérico José Luis Quintero 35
Método de Jacobi
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
axabu
hacer n hasta 1i desde
hacer M hasta 1k desde
0cuadrado
)anormacot,M),(x),(b),(a(n, leer
inicio
ii
ii
21
2ii
ii
n
ij1j
jijii
iiij
<
←=
←
+←
−←
==←
∑≠=
Cálculo Numérico José Luis Quintero 36
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 37
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 38
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 39
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
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
Método de Newton
Cálculo Numérico José Luis Quintero 46
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 47
Métodos Cuasi-Newton
Cálculo Numérico José Luis Quintero 48
Métodos Cuasi-Newton
Cálculo Numérico José Luis Quintero 49
Puntos a tratar
1. Sistemas fáciles de resolver2. Factorizaciones LU3. Factorización de Cholesky4. Métodos iterativos5. Método de Richardson6. Método de Jacobi7. Método de Gauss Seidel8. Método de Newton9. Métodos Cuasi-Newton
10. 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
Método de Jacobi No Lineal
Cálculo Numérico José Luis Quintero 54
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 elpasado”.
Patric Henry