Story Transcript
Eliminaci´on Gaussiana con pivote parcial Luis R´andez Dpto. Matem´ atica Aplicada Facultad de Ciencias Universidad de Zaragoza
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
1/7
Ejemplo.Considerar el sistema lineal 1.00 × 10−4 x1 + 1.00x2 = 1.00 1.00x1 + 1.00x2 = 2.00 cuya soluci´on exacta es x1 = 1.00010001 . . ., x2 = 0.99989998 . . .. Se trata de resolver el sistema lineal anterior con aritm´etica de tres d´ıgitos significativos utilizando eliminaci´ on Gaussiana con/sin pivote parcial. 3
2
1
æ
1
-1
-1
Luis R´ andez (Dpto. Matem´ atica Aplicada)
2
3
Fig. 1.- Geometr´ıa inicial del problema Eliminaci´ on Gaussiana con pivote parcial
2/7
Sin pivote Sea la matriz ampliada A 1.00 × 10−4 1.00 1.00 , A= 1.00 1.00 2.00
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
3/7
Sin pivote y ahora construimos la matriz L1 1.00 0.00 L1 = −1.00 × 104 1.00
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
3/7
Sin pivote dando lugar al sistema triangular superior 1.00 1.00 × 10−4 1.00 , A= 0.00 1.00 − 1.00 × 104 2.00 − 1.00 × 104
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
3/7
Sin pivote y con la aritm´etica empleada 1.00 1.00 × 10−4 1.00 , A= 0.00 −1.00 × 104 −1.00 × 104
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
3/7
Sin pivote tiene por soluci´on x2 = 1.00 y x1 = A=
1.00 − 1.00 = 0.00 1.00 × 10−4
1.00 1.00 × 10−4 1.00 0.00 −1.00 × 104 −1.00 × 104
,
3
2
1æ
1
-1
2
3
-1
Fig. 2.- Geometria final del problema Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
3/7
Con pivote Considerar la matriz ampliada con las filas permutadas A 1.00 1.00 2.00 , A= 1.00 × 10−4 1.00 1.00
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
4/7
Con pivote y ahora construimos la matriz L1 1.00 0.00 L1 = −1.00 × 10−4 1.00
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
4/7
Con pivote dando lugar al sistema triangular superior 2.00 1.00 1.00 , A= 0.00 1.00 − 1.00 × 10−4 1.00 − 2.00 × 10−4
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
4/7
Con pivote y con la aritm´etica empleada 1.00 1.00 2.00 , A= 0.00 1.00 1.00
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
4/7
Con pivote 2.00 − 1.00 = 1.00 1.00 1.00 1.00 2.00 A= , 0.00 1.00 1.00
tiene por soluci´on x2 = 1.00 y x1 =
3
2
1
æ
1
-1
2
3
-1
Fig. 2.- Geometr´ıa final del problema Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
4/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
0 1 3 −4
Luis R´ andez (Dpto. Matem´ atica Aplicada)
2 1 2 5 0 1 3 5 1 −4 2 2 0 1 1 −2
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
0 1 3 −4
2 1 2 5 0 1 3 5 1 −4 2 2 0 1 1 −2
El pivote hay que escogerlo en la primera columna Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
0 1 3 −4
2 1 2 5 0 1 3 5 1 −4 2 2 0 1 1 −2
Es −4 por lo que se permutan las filas 1 y 4 Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
(1 ↔ 4) 5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 1 3 0
0 1 1 −2 0 1 3 5 1 −4 2 2 2 1 2 5
1 1/4 L1 = 3/4 0
0 1 0 0
0 0 1 0
0 0 0 1
Ya est´an permutadas y construimos L1 Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 0 5/4 13/4 9/2 1 −13/4 11/4 1/2 2 1 2 5
Quedando tras la primera etapa Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 0 5/4 13/4 9/2 1 −13/4 11/4 1/2 2 1 2 5
El siguiente pivote hay que escogerlo en la segunda columna Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 0 5/4 13/4 9/2 1 −13/4 11/4 1/2 2 1 2 5
Es 2 por lo que se permutan las filas 2 y 4 Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
(2 ↔ 4) 5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 1 −13/4 11/4 1/2 0 5/4 13/4 9/2
1 0 0 0 1 0 L2 = 0 −1/2 1 0 0 0
0 0 0 1
Ya est´an permutadas y construimos L2 Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 0 −15/4 7/4 −2 0 5/4 13/4 9/2
Quedando tras la segunda etapa Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 0 −15/4 7/4 −2 0 5/4 13/4 9/2
El siguiente pivote hay que escogerlo en la tercera columna Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 0 −15/4 7/4 −2 0 5/4 13/4 9/2
Es −15/4 por lo que no hay que permutar en esta ocasi´on Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 0 −15/4 7/4 −2 0 5/4 13/4 9/2
1 0 L3 = 0 0
0 0 1 0 0 1 0 1/3
0 0 0 1
Construimos L3 Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
Ejemplo.Sea el sistema lineal Ax = b, 0 2 1 2 1 0 1 3 3 1 −4 2 −4 0 1 1
5 x = 5 2 −2
Consideremos ahora la matriz ampliada:
−4 0 0 0
0 1 1 −2 2 1 2 5 0 −15/4 7/4 −2 0 0 23/6 23/6
Obteniendo el sistema lineal triangular superior equivalente
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
5/7
En ocasiones, la eliminaci´on Gaussiana con pivote parcial puede no resultar conveniente. Sea la siguiente matriz hueca, cuya estructura viene dada en la figura (1), donde los elementos de la diagonal son peque˜ nos en valor absoluto, por lo que ser´ıa necesario permutar filas. 0
10
20
30
40
50
60
70
80
90
100 0
10
20
30
40
50 60 nz = 494
70
80
90
100
Fig. 1.- Estructura hueca de la matriz Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
6/7
En la figura (2) se ve que la matriz U se llena completamente de elementos no nulos, por lo que ser´ıa necesario reservar bastante memoria para su almacenamiento. 0
10
20
30
40
50
60
70
80
90
100 0
10
20
30
40
50 60 nz = 5050
70
80
90
100
Fig. 2.- LLenado de la matriz U
Luis R´ andez (Dpto. Matem´ atica Aplicada)
Eliminaci´ on Gaussiana con pivote parcial
7/7