5-Met_iterativos_sist_lineales

Vista previa del material en texto

1
CALCULO AVANZADO - MODULO IV 
 
METODOS ITERATIVOS PARA LA RESOLUCION DE SISTEMAS DE 
ECUACIONES LINEALES – VERSION REDUCIDA 
 
METODO DE JACOBI 
Veremos el método para un sistema de tres ecuaciones y tres incógnitas, pero se realiza 
en forma similar para un sistema de n ecuaciones y n incógnitas. Sea el sistema 
 
a11x1+a12x2+a13x3=b1 
a21x1+a22x2+a23x3=b2 
a31x1+a32x2+a33x3=b3 
 
Para aplicar el método despejamos x1 de la primera ecuación, x2 de la segunda y x3 de la 
tercera, por lo que evidentemente obtenemos un sistema equivalente al dado, es decir, 
con la misma solución. 
 
x1= (b1-a12x2-a13x3)/a11 
x2=(b2 –a21x1-a23x3)/a22 (*) 
x3=(b3-a31x1-a32x2)/a33 
 
Comenzamos suponiendo una aproximación inicial al vector solución : 
 x1
0 
XO = x2
0 
 x3
0 
Con esos valores, reemplazando en (*), obtenemos una segunda aproximación, de la 
siguiente manera: 
 
x1
1= (b1-a12x2
0-a13x3
0)/a11 
X1 = x2
1=(b2 –a21x1
0-a23x3
0)/a22 
x3
1=(b3-a31x1
0-a32x2
0)/a33 
 
Luego donde están los valores de XO ponemos los de X1 y obtenemos una tercera 
aproximación y así sucesivamente. 
 
Ejemplo: Sea el sistema 
 
10x1+ 2x2 -1x3=4 
 3x1+ 6x2 + x3=8 
 2x1- x2 +4x3=6 
 
Lo escribimos como: 
x1= (4-2x2+x3)/10 
x2=(8 –3x1-x3)/6 
x3=(6-2x1+x2)/4 
 
 Suponemos como aproximación inicial 
 0 
XO = 0 
 0 
 2
y obtenemos 
x1
1= (4-2x2
0
+x3
0)/10 =4/10 
X1 = x2
1=(8 –3x1
0-x3
0)/6 =8/6 
x3
1=(6-2x1
0
+x2
0)/4 =6/4 
 
Ahora calculamos la siguiente aproximación: 
 
x1
2= (4-2x2
1
+x3
1)/10 = (4-2.8/6+6/4)/10 
X2 = x2
2=(8 –3x1
1-x3
1)/6 = (8-3.4/10-6/4)/6 
x3
2=(6-2x1
1
+x2
1)/4 = (6-2.4/10+8/6)/4 
 
Y así sucesivamente. 
 
CONDICION SUFICIENTE DE CONVERGENCIA 
 
Con estas iteraciones ¿nos acercaremos a la verdadera solución del sistema de 
ecuaciones? 
Definimos dos medidas que necesitaremos: 
 
Norma infinita de un vector: 
||X||∞ = ||(x1,x2,x3)||∞ = máximo { |x1|,|x2|,|x3|} 
Ejemplo: Si X= (-4, 3, 1) entonces ||X||∞ = 4 
 
Norma infinita de una matriz: 
 a11 a12 a13 
||A||∞ = a21 a22 a23 = 
 a31 a32 a33 
= máx {|a11|+| a12|+| a13|,|a21|+| a22|+| a23|,|a31|+| a32|+| a33|} 
Ejemplo: 
Sea 
 2 -3 5 
 A= 6 4 8 
 7 -10 -1 
||A||∞ = máx {2+3+5, 6+4+8, 7+10+1}= 18. 
 
Volviendo a la condición suficiente de convergencia: 
Sea 
 x1
E 
XE = x2
E la solución exacta del sistema, y 
 x3
E 
 
 x1
k 
Xk = x2
k los valores aproximados en la iteración nº k 
 x3
k 
 
Evidentemente, para que el método converja (se acerque a la solución) deberá ocurrir 
que para i=1,2,3 se verifique que: 
|xi
E-xi
k| tienda a cero a medida que k aumenta, pero esto es equivalente a pedir que la 
máxima de estas diferencias tienda a cero, es decir: 
 
 3
lím ||ek||∞ = 0 
k→∞ 
siendo x1
E – x1
k 
 ek = x2
E – x2
k (vector error en la iteración k) 
 x3
E – x3
k 
 
Veamos que tiene que ocurrir para asegurar esto: 
Sabemos que XE debe satisfacer el sistema, por lo tanto: 
 3 
x i
E= (bi-∑aijxj
E)/aii i = 1,2,3 y calculamos: 
 j=1 
 j≠ i 
 
 3 
x i
k+1= (bi-∑aijxj
k)/aii i = 1,2,3 
 j=1 
 j≠ i 
 
Restamos miembro a miembro y obtenemos: 
 3 3 
xi
E – xi
k+1 = (bi-∑aijxj
E - bi+∑aijxj
k)/aii i = 1,2,3 
 j=1 j=1 
 j≠ i j≠i 
 3 
xi
E – xi
k+1 = ∑aij [xj
k - xj
E] / aii para i =1,2,3 
 j=1 
 j≠i 
 3 3 
| xi
E – xi
k+1 | = | ∑aij [xj
k - xj
E] / aii | ≤ ∑|aij | |xj
k - xj
E| / |aii | para i =1,2,3 
 j=1 j=1 
 j≠i j≠i 
|xj
k - xj
E| es el error de la incógnita número “j” en la iteración número “k”, que sabemos 
(por la definición dada de norma infinita de un vector y de vector error), verifica: 
 
|xj
k - xj
E| ≤ ||ek||∞ 
Por lo tanto, si en la última sumatoria reemplazamos |xj
k - xj
E| por ||ek||∞ obtenemos: 
 3 3 
| xi
E – xi
k+1 | ≤ ∑|aij| |xj
k - xj
E| / |aii | ≤ ∑|aij | ||e
k||∞ / |aii | para i =1,2,3 
 j=1 j=1 
 j≠i j≠i 
 
O, lo que es lo mismo: 
 3 
| xi
E – xi
k+1 | ≤ ||ek||∞ . ∑ [|aij | / |aii |] para i =1,2,3 
 j=1 
 j≠i 
Evidentemente para cada uno de los valores de “i” la sumatoria que aparece en la última 
expresión da distintos resultados. 
 3 3 3 
Llamemos con φ = máx {∑ [|a1j| / |a11 |] , ∑ [|a2j| / |a22 |] , ∑ [|a3j| / |a33 |] } 
 j=1 j=1 j=1 
 j≠i j≠i j≠i 
Se cumplirá entonces que 
 3 
 4
| xi
E – xi
k+1 | ≤ ||ek||∞ . ∑ [|aij | / |aii |] ≤ ||e
k||∞ . φ para todo “i” 
 j=1 
 j≠i 
Como la desigualdad anterior se cumple para todo “i” también se cumplirá para la 
mayor de las diferencias | xi
E – xi
k+1 | que, por definición, es la norma del error en la 
iteración nº “k+1”. 
Tenemos entonces: 
||ek+1||∞ ≤ ||e
k||∞ . φ 
Razonando de manera similar tendríamos: 
||ek||∞ ≤ ||e
k-1||∞ . φ (notar que φ es el mismo pues no depende del número de iteración) 
 
de lo anterior: 
||ek+1||∞ ≤ ||e
k-1||∞ . φ
2 
y siguiendo con el mismo razonamiento llegaríamos a: 
||ek+1||∞ ≤ ||e
0||∞ . φ
k+1 donde ||e0||∞ es una constante (desconocida). 
Como ||ek+1||∞ ≤ ||e
0||∞ . φ
k+1 
Se cumple también que: 
 
lím ||ek+1||∞ ≤ lim ||e
0||∞ . φ
k+1 
k→∞ k→∞ 
Sabemos que φ es positivo. Si φ es menor que 1, seguro el límite del segundo miembro 
valdrá cero, y por ende también el primero (ya que no puede ser negativo), y por lo 
tanto el error tenderá a cero y el método converge. 
 
Conclusión: La condición suficiente para que el método converja es que φ sea 
menor que 1. 
¿Cómo ver esto fácilmente? 
Recordemos quién es φ. 
 3 3 3 
φ = máx {∑ [|a1j| / |a11 |] , ∑ [|a2j| / |a22 |] , ∑ [|a3j| / |a33 |] } 
 j=1 j=1 j=1 
 j≠i j≠i j≠i 
Si φ< 1 tenemos 
 3 3 3 
φ = máx {∑ [|a1j| / |a11 |] , ∑ [|a2j| / |a22 |] , ∑ [|a3j| / |a33 |] }<1 
 j=1 j=1 j=1 
 j≠i j≠i j≠i 
 
Si la máxima de estas sumas es menor que 1, quiere decir que todas lo son, por lo que 
se debe cumplir que cada una de las sumas debe ser menor que uno. Planteando las tres 
desigualdades, desarrollando las sumas y despejando, obtenemos: 
|a11| > |a12 | + |a13 | 
|a22| > |a21 | + |a23 | 
|a33| > |a31 | + |a32 | 
Es decir: Para asegurarconvergencia se pide que : en cada fila, el valor absoluto del 
elemento de la diagonal principal sea mayor que la suma de los valores absolutos de los 
elementos de esa fila. En ese caso decimos que el sistema tiene diagonal dominante. 
En el ejemplo dado al principio de este apunte vemos que: 
10 > 2+1 
6 > 3 +1 
4 > 2 +1 
 5
Por lo que el método convergerá con seguridad. Es por eso que se suele tomar como 
aproximación inicial de xi, xi
0 = bi / aii. 
 
Cota de error 
Se puede demostrar que: 
||ek||∞ = || x
E -xk || ≤ [ || M ||∞ / ( 1- || M ||∞)] . || x
k -xk-1 || 
 
siendo M = N-1.P donde N y P son las siguientes matrices: 
 a11 0 0 
N 0 a22 0 y P = A - N 
 0 0 a33 
Siendo A la matriz de coeficientes del sistema dado. 
 
EJEMPLO 
Retomemos nuestro ejemplo. Calculamos las primeras 6 iteraciones: 
 
 aprox.inicial iteración 1 iteración 2 iteración 3 iteración 4 iteración 5 iteración 6 
x1 0 0,4 0,28333333 0,38666667 0,37402778 0,37829167 0,37517245 
x2 0 1,33333333 0,88333333 0,91944444 0,87680556 0,89023148 0,88882292 
x3 0 1,5 1,63333333 1,57916667 1,53652778 1,5321875 1,53341204 
 
Calculamos las matrices: 
10 2 -1 10 0 0 0 2 -1 
A = 3 6 1 N= 0 6 0 P= 3 0 1 
 2 -1 4 0 0 4 2 -1 0 
 
 1/10 0 0 0 1/5 -1/10 
N-1= 0 1/6 0 M=N-1P= 1/2 0 1/6 
 0 0 1/4 1/2 -1/4 0 
 
Por lo que || M ||∞ = máx {0+1/5+1/10, 1/2+1/6, 1/2+1/4}= 0,75 
|| x6 –x5 || = || (-0,00311921, -0,00140856, 0,00122454 || = 0,00311921 
Por lo que la cota de error es: 
|| xE –x6 || ≤ (0,75 / 0,25) . 0,00311921= 0,00935764 
Esto significa que: 
| x1
E –x1
6 | ≤ 0,00935764 
| x2
E –x2
6 | ≤ 0,00935764 
| x3
E –x3
6 | ≤ 0,00935764 
 O lo que es lo mismo: 
| x1
E –0,37517245 | ≤ 0,00935764 
| x2
E –0,88882292 | ≤ 0,00935764 
| x3
E –1,53341204 | ≤ 0,00935764 
Entonces: 
 - 0,00935764 ≤ x1
E –0,37517245 ≤ 0,00935764 
 - 0,00935764 ≤ x2
E –0,88882292 ≤ 0,00935764 
 - 0,00935764 ≤ x3
E –1,53341204 ≤ 0,00935764 
De donde: 0,36581481 ≤ x1
E ≤ 0,38453009 
 0,87946528≤ x2
E ≤ 0,89818056 
 1,5240544 ≤ x3
E ≤ 1,54276968 
Y tenemos los intervalos en los cuales se hallan los valores exactos de las soluciones. Si 
necesitamos mayor precisión debemos realizar más iteraciones. 
 6
 
METODO DE GAUSS – SEIDEL 
 
Es similar al anterior, solo que en cada iteración se usan las últimas aproximaciones que 
se tienen de cada incógnita. Así, por ejemplo, la iteración 1 se calcula como: 
 
x1
1= (b1-a12x2
0-a13x3
0)/a11 
X1 = x2
1=(b2 –a21x1
1-a23x3
0)/a22 
x3
1=(b3-a31x1
1-a32x2
1)/a33 
 
La condición suficiente de convergencia es la misma, aunque cambia la definición de la 
matriz N, que ahora es una matriz triangular inferior: 
 
 a11 0 0 
N = a21 a22 0 
 a31 a32 a33 
 
 
Ejercicios Propuestos: 
 
1. Obtener las dos primeras iteraciones del método de Jacobi para los siguientes 
sistemas lineales, usando X(0)= 
 
a) 3x1 – x2 + x3 = 1, b) 10x1 – x2 = 9, 
3x1 +6 x2 + 2x3 = 0, - x1 + 10 x2 – 2x3 = 7, 
3x1 +3 x2 + 7x3 = 4. – x2 + 10x3 = 6 
 
Rta: a) (0.1428571, -0.3571429, 0.4285714)t b) (0.97, 0.91, 0.74)t 
 
 
2. Repetir el ejercicio 1 empleando el método de Gauss-Seidel. 
 
3. Aplicar el método de Gauss-Seidel para aproximar la solución del sistema 
2x + 3y = 1 ; 6x + 2y = 10. 
Partir de (0,0)t y verificar que el método converja. Realizar tres aproximaciones 
y determinar, si es posible, en que rango varía x e y, de lo contrario fundamentar 
la respuesta. 
 Rta: 1.967078189 < x < 2 ; -1.005486968 < y < -0.9725651578 
 
 
4. Las dimensiones de una caja verifican que, 
12x + y +2z = 10.6 ; 6y –x +z = 4.2 ; 7z – 2x + 2y = 4.9. 
Se desea colocar en ella 0.35 m3 de arena. Partiendo de (0,0,0) realizar 3 
iteraciones y determinar si esto es posible. 
 
 
 
 
Bibliografía: Burden, R. y Faires J.D “Análisis Numérico” (2002)