View
231
Download
0
Category
Preview:
Citation preview
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 1
1.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 2 3
1 2 3
18 6 10
2 16 2
8 2 8
x x xx x xx x x
+ − = − + + = − + − =
, se pide
a. Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b. Estudiar si A es definida positiva. c. Estudiar si la matriz A de los coeficientes es estrictamente diagonal
dominante, en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante.
d. ¿Es B definida positiva? e. Halla el número de condición de las matrices A y B y comenta el resultado. f. Hallar la descomposición LU de la matriz A y de la matriz B y explicar las
diferencias entre ambas descomposiciones. g. Hallar la solución de los sistemas S y S’, a partir de las matrices de
descomposición LU y usando la instrucción del apartado a) y di si coinciden o no.
h. Da una explicación de los resultados del apartado g. i. Si queremos obtener, por el método de Jacobi, una solución aproximada del
sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿porqué?
j. Teniendo en cuenta la respuesta en i) Halla una solución aproximada para una tolerancia de 0.01, y di cuántas iteraciones son necesarias.
2.- La tabla que aparece a continuación representa la discretización del problema del calor en una placa. En el modelo discreto se supone que, en una situación de equilibrio térmico, la temperatura en cada nodo Ti es la media de las temperaturas en los nodos vecinos. Se trata de determinar las temperaturas en dichos nodos conocidas las temperaturas en el borde.
100 40 60 100 50 50
50 50
T1
T3
T5
T7
T2
T4
T6
T8
0 25 50 0
Para ello, se pide:
a) Escribir el sistema lineal (∗) correspondiente a los datos de la tabla. b) Estudiar si la matriz es, o no, estrictamente diagonal dominante. c) Resolver el sistema utilizando el algoritmo de Crout (método directo). d) Usa el método de Jacobi para obtener una solución aproximada con una
tolerancia de 0.01. Indica el número de iteraciones que has necesitado.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 2
e) Calcula una aproximación con el método de Gauss-Seidel (con igual tolerancia). Indica el número de iteraciones que has necesitado y compáralo con el de Jacobi.
f) Calcula una aproximación con el método de sobrerrelajación con w=1.2 e igual tolerancia. Indica el número de iteraciones que has necesitado en este caso.
g) Prueba, con algún otro valor para w que tú elijas, si fuera posible rebajar el número de iteraciones necesarias para obtener una aproximación con la tolerancia 0.01.
3.- Una empresa comercializa sus productos en n tiendas diferentes. Cada año el 5% de los productos de la tienda i se trasladan a la tienda i+1, y el 7% a la tienda i-1. Se pide: a) Escribir el sistema de ecuaciones lineales que proporciona el número de productos
que hay en cada tienda el año (k) en función de los que había el año anterior (k-1). b) Un año determinado el número de productos que había en cada tienda está dado por
la deca-upla (100, 105, 120, 138, 232, 190, 125, 100, 200, 180) ¿Cuál será la deca-upla correspondiente al año anterior? ¿y al cabo de los tres años?
c) Un nuevo gerente llega a la empresa y se encuentra con el siguiente número de productos en cada una de las 10 tiendas (120, 123, 145, 132, 211, 129, 200, 232, 100, 190) ¿Cómo puede averiguar la distribución de productos que había en las tiendas el año anterior? ¿Y dos años antes?
4.- Sea el sistema:
Se pide: a) Introducir la matriz A de los coeficiente como una matriz B sparse b) Dar A como una matriz llena a partir de la matriz B c) Volver a definir A como una matriz dispersa S a partir de la matriz llena d) Introducir A como una matriz tridiagonal E cuyas diagonales son escalares e) Dar la solución A\b del sistema f) Dar la descomposición LU de A g) Hallar la solución del sistema utilizando la descomposición LU h) Dar la solución con la función crout i) Dar una solución aproximada aplicando el método de Jacobi, tomando como x0 el vector nulo, como cota de error tol=0.01 y como el máximo de iteraciones maxiter=50. j) Dar una solución aproximada aplicando el método de Gauss‐Seidel k) Dar una solución aproximada aplicando el método de sobrerrelajación con ω=1.2
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 3
l) Dar el número de condición de A
5.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 2 3
1 2 3
3 2 6 2
4 9
5 3 1
x x xx x x
x x x
+ − = − + − = − + =
, se pide:
a) Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b) Estudiar si A es definida positiva. c) Estudiar si la matriz A de los coeficientes es estrictamente diagonal dominante, en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante. d) ¿Es B definida positiva? e) Halla el número de condición de las matrices A y B y comenta el resultado. f) Hallar la descomposición LU de la matriz A y de la matriz B y explicar las diferencias entre ambas descomposiciones. g) Hallar la solución de los sistemas S y S’, a partir de las matrices de descomposición LU y usando la instrucción del apartado a) y di si coinciden o no. h) Da una explicación de los resultados del apartado g. i) Si queremos obtener, por el método de Jacobi, una solución aproximada del sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿porqué? j) Teniendo en cuenta la respuesta en i) Halla una solución aproximada para una tolerancia de 0.01, y dí cuántas iteraciones son necesarias.
6.- Dado el sistema S1 ≡ 1 2 3
1 2 3
1 2 3
2 6 38
3 7 34
8 2 20
x x xx x xx x x
− − = −− − + = −− + − = −
, se pide:
a) Estudiar si la matriz de coeficientes de S1 es estrictamente diagonal dominante por filas y justificar si sería conveniente o no realizar una pivotación parcial.
b) Escribir un sistema S2 equivalente a S1 cuya matriz de coeficientes sea estrictamente diagonal dominante por filas (usar la operación elemental intercambio de filas).
c) Hallar la solución del sistema S2 por el método de Gauss con MATLAB (x=A\b) ¿Se obtendría la misma solución para S1? Razona la respuesta.
d) Hallar la descomposición LU con la función de MATLAB [L,U]=lu(A) tanto para el sistema S1 como para S2 y comentar los resultados. Calcular la solución del sistema S2 utilizando la descomposición LU obtenida en el apartado anterior.
7.- Dado el sistema de 1 2 3
1 2 3
1 2 3
5 21,5
10 2 27
3 6 2 61,5
x x xx x xx x x
+ + = − + − =− − + = −
, se pide:
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 4
a. Comprobar que A es una matriz bien condicionada y resolver el sistema con el comando \
b. Hallar la descomposición LU de la matriz A con las funciones [L,U] y [L,U,P] de MatLab. Comentar la diferencia observada en los resultados.
c. Razonar si A es estrictamente diagonal dominante o no, en caso negativo decir si se puede obtener uno equivalente Bx=c, cuya matriz sí sea estrictamente diagonal dominante. Resolverlo con el comando \ de Matlab.
d. Hallar la descomposición [L,U] y [L,U,P] de la matriz B y justificar el resultado. e. ¿A cuál de los dos sistemas anteriores se puede aplicar los métodos de Jacobi y
Gauss-Seidel con la seguridad de que habrá convergencia? f. Completa la tabla que aparece a continuación para el sistema que resulta del
apartado b) siendo x la solución obtenida en dicho apartado y k el nº mínimo de iteraciones para la convergencia.
k
(mínimo iterac.)
( 1)kx −
( )kx ( ) ( 1)k kx x −
∞− ( )kx x
∞−
Jacobi
(tol=0.01)
Gauss-Seidel
(tol=0.01)
Jacobi
(tol=0.001)
Gauss-Seidel
(tol=0.001)
8.- Un ingeniero que trabaja en la construcción requiere 4800, 5800 y 5700 m3 de arena, grava fina y grava gruesa, respectivamente. Hay 3 canteras de las que se puede extraer dichos materiales y su distribución es:
Arena % Grava fina % Grava gruesa % Cantera 1 55 30 15 Cantera 2 25 45 30 Cantera 3 25 20 55
El sistema lineal correspondiente a los datos de la tabla es:
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 5
A x= b 1 2 3
1 2 3
1 2 3
0,55 0,25 0,25 4800
0,3 0,45 0,2 5800
0,15 0,3 0,55 5700
+ + =⇔ + + = + + =
x x xx x xx x x
, siendo x1 = material total extraído de la
primera cantera, x2 = material total extraído de la segunda cantera y x3 = material total extraído de la tercera cantera
a) Estudiar si la matriz A es estrictamente diagonal dominante y hallar la solución con el comando \ de MatLab.
b) Calcula una aproximación con el método de Gauss-Seidel con tolerancia 0.01. Indica el número de iteraciones que has necesitado (copia en la respuesta la iteración que converge y la anterior). Expresa en una tabla la cantidad extraída de cada cantera:
Gauss Arena Grava fina Grava gruesa Total
Cantera 1
Cantera 2
Cantera 3
c) Calcula una aproximación con el método de sobrerrelajación con w=1.2 e igual
tolerancia (copia en la respuesta la iteración que converge y la anterior). Rellena una tabla similar a la del apartado b).
d) Prueba, con valores de w = 0.8, w =1.1, w = 1.4 si es posible rebajar el número de iteraciones necesarias para obtener una aproximación con tolerancia 0.01. Compara estos resultados con los obtenidos en b) y c) y preséntalo en una tabla similar a la siguiente, siendo “x” la solución con el comando \.
k mínimo de convergencia
( )kx =[ ]( )
1 2 3, ,kx x x ( )
∞−kx x
Gauss-Seidel Sob. w=1,2 Sob. w= 0.8
Sob. w=1.1
Sob. w=1.4
9.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 3
1 2
6 2 4.6
4 14.5
2 5 8.7
− + = + =− + =
x x xx x
x x, se pide
a. Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b. Estudiar si A es definida positiva. c. Estudiar si la matriz A de los coeficientes es estrictamente diagonal dominante,
en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante.
d. ¿Es B definida positiva? e. Hallar el número de condición de las matrices A y B y comentar el resultado.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 6
f. Hallar la descomposición LU de la matriz A y de la matriz B y explicar las diferencias entre ambas descomposiciones.
g. Hallar la solución de los sistemas S y S’, a partir de las matrices de descomposición LU y usando la instrucción del apartado a). ¿Coinciden?
h. Dar una explicación de los resultados del apartado g. i. Si queremos obtener, por el método de Jacobi, una solución aproximada del
sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿por qué?
j. Teniendo en cuenta la respuesta en i), hallar una solución aproximada para una tolerancia de 0.001, y decir cuántas iteraciones son necesarias.
k. Mismas cuestiones i. y j. utilizando Gauss-Seidel. l. Mismas cuestiones i. y j. utilizando Sobrerrelajación para dos valores diferentes
de w.
10.- Dado el sistema de ecuaciones lineales S ≡
2 -1 0 x 5
AX = B -1 2 -1 y = 0
0 -1 2 z 0
⇔
a. ¿Es A una matriz definida positiva?, ¿es A estrictamente diagonal dominante? b. Razonar si puede utilizarse la descomposición LU sin pivoteo para resolver el
sistema S. Si fuera así, resolverlo por ese método. c. Razonar si puede utilizarse el método de Cholesky para resolver el sistema S. Si
fuera así, resolverlo por ese método. d. Razonar si puede utilizarse el algoritmo de Crout para encontrar la solución del
sistema. Si fuera así, resolverlo por ese método. e. Hallar una solución aproximada utilizando el método de Sobrerrelajación con
w=1.2, para una tolerancia de 0.01, y justificar cuántas iteraciones son necesarias.
11.- Dado el sistema de ecuaciones lineales S≡1 2
1 2 3
2 3
0,8 0,4 41
0,4 0,8 0,4 25
0,4 0,8 10,5
x xx x xx x
− =− + − =− + =
, se pide:
a) Estudiar si la matriz A de los coeficientes es definida positiva y si está bien condicionada. b) Dar la solución con el comando \ de Matlab. c) Dar la solución con el algoritmo de Crout. d) Completar la tabla que aparece al dorso de la hoja (basta escribir el resultado para 3 iteraciones: una de ellas la mínima que cumple la condición, una anterior y otra posterior) para una tolerancia tol=0,01 y siendo x la solución del sistema obtenida en el apartado b).
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 7
1.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 2 3
1 2 3
18 6 10
2 16 2
8 2 8
x x xx x xx x x
+ − = − + + = − + − =
, se pide:
a. Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b. Estudiar si A es definida positiva. c. Estudiar si la matriz A de los coeficientes es estrictamente diagonal
dominante, en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante.
d. ¿Es B definida positiva? e. Halla el número de condición de las matrices A y B y comenta el resultado. f. Hallar la descomposición LU de la matriz A y de la matriz B y explicar las
diferencias entre ambas descomposiciones. g. Hallar la solución de los sistemas S y S’, a partir de las matrices de
descomposición LU y usando la instrucción del apartado a) y di si coinciden o no.
h. Da una explicación de los resultados del apartado g. i. Si queremos obtener, por el método de Jacobi, una solución aproximada del
sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿porqué?
j. Teniendo en cuenta la respuesta en i) Halla una solución aproximada para una tolerancia de 0.01, y dí cuántas iteraciones son necesarias.
Solución: a) >> A=[1,18,-6;2,1,16;8,1,-2],b=[-10;-2;8],x=A\b A = 1 18 -6 2 1 16 8 1 -2 b = -10 -2 8 x =A/b 1.0326 -0.6834 -0.2114
b) a11>0, >> det([1,18;2,1]) = -35, luego no es definida positiva
c) >> B=[8,1,-2;1,18,-6;2,1,16], c=[8;-10;-2],x=B\c B = 8 1 -2 1 18 -6 2 1 16
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 8
c = 8 -10 -2 x = 1.0326 -0.6834 -0.2114
d) 8>0 >> det([8,1;1,18]) = 143 >> det(B)=394, luego b si es definida positiva.
e) cond(A) =2.5217 cond(B)= =2.5217 El número de condición indica que son matrices bien condicionadas (número cerca de 1) y coinciden por ser matrices bien condicionadas a las que solo hemos intercambiado filas
f) >> [L,U]=lu(A) L = 0.1250 1.0000 0 0.2500 0.0420 1.0000 1.0000 0 0 U = 8.0000 1.0000 -2.0000 0 17.8750 -5.7500 0 0 16.7413 >> [L,U]=lu(A);x=U\(L\b) x = 1.0326 -0.6834 -0.2114 >> [L,U]=lu(B) L = 1.0000 0 0 0.1250 1.0000 0 0.2500 0.0420 1.0000 U = 8.0000 1.0000 -2.0000 0 17.8750 -5.7500 0 0 16.7413 >> [L,U]=lu(B);x=U\(L\c) x = 1.0326 -0.6834 -0.2114
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 9
g) Observamos que los resultados coinciden (calculados en los apartados a) y f)). h) Coinciden porque la instrucción \ (x=U\(L\c)) pivota las ecuaciones por lo que las matrices
LU usadas en el caso de la matriz A son pivotadas por el programa. i) >> x0=[0;0;0];tol=0.01;maxiter=4;jacobi(B,c,x0,tol,maxiter)
maxiter = 4 incr = 1.0100 No converge con las iteraciones dadas >> x0=[0;0;0];tol=0.01;maxiter=5,jacobi(B,c,x0,tol,maxiter) tol = 0.0100 maxiter = 5 incr = 1.0100 ans = 1.0321 -0.6840 -0.2107 Por lo que son necesarias 5 iteraciones.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 10
2.- La tabla que aparece a continuación representa la discretización del problema del calor en una placa. En el modelo discreto se supone que, en una situación de equilibrio térmico, la temperatura en cada nodo Ti es la media de las temperaturas en los nodos vecinos. Se trata de determinar las temperaturas en dichos nodos conocidas las temperaturas en el borde.
100 40 60 100 50 50
50 50
T1
T3
T5
T7
T2
T4
T6
T8
0 25 50 0
Para ello, se pide:
a) Escribir el sistema lineal (∗) correspondiente a los datos de la tabla. b) Estudiar si la matriz es, o no, estrictamente diagonal dominante. c) Resolver el sistema utilizando el algoritmo de Crout (método directo). d) Usa el método de Jacobi para obtener una solución aproximada con una
tolerancia de 0.01. Indica el número de iteraciones que has necesitado. e) Calcula una aproximación con el método de Gauss-Seidel (con igual tolerancia).
Indica el número de iteraciones que has necesitado y compáralo con el de Jacobi. f) Calcula una aproximación con el método de sobrerrelajación con w=1.2 e igual
tolerancia. Indica el número de iteraciones que has necesitado en este caso. g) Prueba, con algún otro valor para w que tú elijas, si fuera posible rebajar el
número de iteraciones necesarias para obtener una aproximación con la tolerancia 0.01.
(∗) Por ejemplo, T1=1/4(50+100+ T3+ T2), solo se considera nodo vecino al que se accede por la línea horizontal o vertical de la cuadrícula Solución:
a) T1=1/4 (T2+T3 + 50 + 100) ⇒ 4T1 -T2 - T3 = 150 4T1 -T2 - T3 = 150
T2=1/4 (T1+T4 + 50 + 0) ⇒ 4T2 -T1 – T4 = 50 -T1 +4T2– T4 = 50
T3=1/4 (T1+T4 + T5 + 40) ⇒ 4T3-T1 – T4 –T5 = 40 -T1 + 4T3– T4 –T5 = 40
T4=1/4 (T2+T3 + T6 + 25) ⇒ 4T4-T2 – T3 –T6 = 25 ⇒ -T2 – T3 +4T4–T6 = 25
T5=1/4 (T3 + T6 + T7+ 60) ⇒ 4T5-T3 – T6 –T7 = 60 -T3 + 4T5– T6 –T7 = 60
T6=1/4 (T4 + T5 + T8+ 50) ⇒ 4T6-T4 –T5 – T8 = 50 -T4 –T5 + 4T6– T8 = 50
T7=1/4 (T5 + T8+ 50+ 100) ⇒ 4T7 –T5 – T8 = 150 -T5 + 4T7– T8 = 150
T8=1/4 (T6 + T7+ 50 + 0) ⇒ 4T8 –T6– T7 = 50 -T6– T7 + 4T8 = 50
b) La matriz M es estrictamente diagonal dominante pues los elementos de la diagonal son 4, y la suma de los elementos restantes de cada fila es, en valor absoluto, menor que 3, es
decir, mii > Σ|aij| siendo j=1,…,8 con i≠j c) No se puede aplicar el algoritmo de Crout porque la matriz no es tridiagonal por lo que
utilizaremos un método directo
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 11
M = 4 -1 -1 0 0 0 0 0 -1 4 0 -1 0 0 0 0 -1 0 4 -1 -1 0 0 0 0 -1 -1 4 0 -1 0 0 0 0 -1 0 4 -1 -1 0 0 0 0 -1 -1 4 0 -1 0 0 0 0 -1 0 4 -1 0 0 0 0 0 -1 -1 4 n = 150 50 40 25 60 50 150 50 >> x=M\n x = 58.6256 36.8289 47.6737 38.6900 53.3790 45.2574 60.5849 38.9606 d) Se necesitan 20 iteraciones >> x0=[0;0;0;0;0;0;0;0];tol=0.01;maxiter=19;jacobi(M,n,x0,tol,maxiter) incr =1.0100 No converge con las iteraciones dadas >> x0=[0;0;0;0;0;0;0;0];tol=0.01;maxiter=20;jacobi(M,n,x0,tol,maxiter) incr =1.0100 ans = 58.6148 36.8181 47.6561 38.6724 53.3614 45.2399 60.5741 38.9497
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 12
e) >> x0=[0;0;0;0;0;0;0;0];tol=0.01;maxiter=12;gausseidel(M,n,x0,tol,maxiter) incr =1.0100 No converge con las iteraciones dadas >> x0=[0;0;0;0;0;0;0;0];tol=0.01;maxiter=13;gausseidel(M,n,x0,tol,maxiter) incr = 1.0100 ans = 58.6216 36.8263 47.6694 38.6872 53.3762 45.2556 60.5838 38.9598 Se necesitan, por tanto 13 iteraciones para la convergencia f) >> omega=1.2, tol=0.01, maxiter=7,sobrerrelajacion(M,n,x0,omega,tol,maxiter) omega =1.2000 tol = 0.0100 maxiter = 7 incr = 1.0100 No converge con las iteraciones dadas >> omega=1.2, tol=0.01, maxiter=8,sobrerrelajacion(M,n,x0,omega,tol,maxiter) omega =1.2000 tol = 0.0100 maxiter = 8 incr = 1.0100 ans = 58.6250 36.8293 47.6717 38.6895 53.3770 45.2565 60.5838 38.9604 g) omega=1.1; tol=0.01; maxiter=8;sobrerrelajacion(M,n,x0,omega,tol,maxiter) incr = 1.0100 No converge con las iteraciones dadas omega=0.9; tol=0.01; maxiter=8;sobrerrelajacion(M,n,x0,omega,tol,maxiter) incr = 1.0100 No converge con las iteraciones dadas Análogamente no converge con 8 iteraciones, es decir, no se mejora el procedimiento con valores de omega =0.1,….1.1, 1.4, 1.5,….2,
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 13
3.- Una empresa comercializa sus productos en n tiendas diferentes. Cada año el 5% de los productos de la tienda i se trasladan a la tienda i+1, y el 7% a la tienda i-1. Se pide: a) Escribir el sistema de ecuaciones lineales que proporciona el número de productos que hay en cada tienda el año (k) en función de los que había el año anterior (k-1). b) Un año determinado el número de productos que había en cada tienda está dado por la deca-upla (100, 105, 120, 138, 232, 190, 125, 100, 200, 180) ¿Cuál será la deca-upla correspondiente al año anterior? ¿y al cabo de los tres años? c) Un nuevo gerente llega a la empresa y se encuentra con el siguiente número de productos en cada una de las 10 tiendas (120, 123, 145, 132, 211, 129, 200, 232, 100, 190) ¿Cómo puede averiguar la distribución de productos que había en las tiendas el año anterior? ¿Y dos años antes?
Solución: a) En general, el número de productos que hay en cada tienda el año (k) es:
Para i=2,…,9 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 1 1 1 1
1 1 1 10,05 0,07 0,05 0,07 0,05 0,88 0,07k k k k k k k k ki i i i i i i i ix x x x x x x x x− − − − − − − −
− + − += + + − − = + +
para i=1 ( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 11 1 2 1 1 20,07 0,05 0,95 0,07k k k k k kx x x x x x− − − − −= + − = +
para i=10 ( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 110 10 9 10 9 100,05 0,07 0,05 0,93k k k k k kx x x x x x− − − − −= + − = +
En forma matricial: ( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
1
2
3
4
5
6
7
8
9
10
0,95 0,07 0 0 0 0 0 0 0 0
0,05 0,88 0,07 0 0 0 0 0 0 0
0 0,05 0,88 0,07 0 0 0 0 0 0
0 0 0,05 0,88 0,07 0 0 0 0 0
0 0 0 0,05 0,88 0,07 0 0 0 0
0 0 0 0 0,05 0,88 0,07 0 0 0
0 0 0 0 0 0,05 0,88 0,07 0 0
0 0
k
k
k
k
k
k
k
k
k
k
x
x
x
x
x
x
x
x
x
x
=
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
11
12
13
14
15
16
17
18
19
110
0 0 0 0 0,05 0,88 0,07 0
0 0 0 0 0 0 0 0,05 0,88 0,07
0 0 0 0 0 0 0 0 0,05 0,93
k
k
k
k
k
k
k
k
k
k
x
x
x
x
x
x
x
x
x
x
−
−
−
−
−
−
−
−
−
−
Designando por A a la matriz , abreviadamente podríamos escribir X(k)=A X(k-1)
b) La respuesta a este apartado es la solución del sistema que se obtiene despejando Xk-1
X(k-1)=A-1 X(k)
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 14
0,95 0,07 0 0 0 0 0 0 0 0
0,05 0,88 0,07 0 0 0 0 0 0 0
0 0,05 0,88 0,07 0 0 0 0 0 0
0 0 0,05 0,88 0,07 0 0 0 0 0
0 0 0 0,05 0,88 0,07 0 0 0 0
0 0 0 0 0,05 0,88 0,07 0 0 0
0 0 0 0 0 0,05 0,88 0,07 0 0
0 0 0 0 0 0 0,05 0,88 0,07 0
0 0 0 0 0 0 0 0,05 0,88 0,07
0 0 0 0 0 0 0 0 0,05 0,93
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
111
12
13
14
15
16
17
18
19
110
100
105
120
138
232
190
125
100
200
180
k
k
k
k
k
k
k
k
k
k
x
x
x
x
x
x
x
x
x
x
−−
−
−
−
−
−
−
−
−
−
=
Al tratarse de nº de productos hemos de redondear los resultados a entero positivo.
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
11
12
13
14
15
16
17
18
19
110
98
104
121
123
345
186
124
90
208
182
k
k
k
k
k
k
k
k
k
k
x
x
x
x
x
x
x
x
x
x
−
−
−
−
−
−
−
−
−
−
=
Al cabo de tres años (suponemos que los datos dados en el enunciado corresponden al año k y queremos obtener la decaupla correspondiente al año k+3) el número de productos viene dado por la ecuación: X(k+3)=A X(k+2)= A AX(k+1)=AAAX(k) = A3 X(k)
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
31
32
33
34
35
36
37
38
39
310
107
108
124
167
276
193
131
121
184
172
k
k
k
k
k
k
k
k
k
k
x
x
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
+
+
+
=
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 15
c) Al igual que se ha procedido en el apartado anterior y partiendo de la ecuación obtenida en el apartado a) X(k)=A X(k-1) se obtienen las respuestas:
La distribución del apartado anterior, despejando X(k-1)=A-1 X(k) :
La distribución de dos años antes, X(k)=A X(k-1)= A AX(k-2) ⇒ X(k-2)=(A-1)2 X(k)
En general, la distribución n años antes vendrá dada por X(k-n)=(A-1)n X(k) y n
años después por X(k+n)=An X(k)
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 16
4.- Sea el sistema:
Se pide: a) Introducir la matriz A de los coeficiente como una matriz B sparse b) Dar A como una matriz llena a partir de la matriz B c) Volver a definir A como una matriz dispersa S a partir de la matriz llena d) Introducir A como una matriz tridiagonal E cuyas diagonales son escalares e) Dar la solución A\b del sistema f) Dar la descomposición LU de A g) Hallar la solución del sistema utilizando la descomposición LU h) Dar la solución con la función crout i) Dar una solución aproximada aplicando el método de Jacobi, tomando como x0 el vector nulo, como cota de error tol=0.01 y como el máximo de iteraciones maxiter=50. j) Dar una solución aproximada aplicando el método de Gauss‐Seidel k) Dar una solución aproximada aplicando el método de sobrerrelajación con ω=1.2 l) Dar el número de condición de A
Solución: a) B=sparse([1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6],[1,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6],[4,1,1,4,1,1,4,1,1,4,1,1,4,1,1,4]) B= (1,1) 4 (2,1) 1 (1,2) 1 (2,2) 4 (3,2) 1 (2,3) 1 (3,3) 4 (4,3) 1 (3,4) 1 (4,4) 4 (5,4) 1 (4,5) 1 (5,5) 4 (6,5) 1 (5,6) 1 (6,6) 4 b) >> A=full(B) A= 410000 141000 014100 001410 000141 000014 c) >> S=sparse (A)
S= (1,1) 4 (2,1) 1 (1,2) 1 (2,2) 4 (3,2) 1 (2,3) 1 (3,3) 4 (4,3) 1 (3,4) 1 (4,4) 4 (5,4) 1 (4,5) 1 (5,5) 4 (6,5) 1 (5,6) 1 (6,6) 4
d) >> n=6, dp=ones(1,n), ds=ones(1,n‐1), E=diag(4*dp)+diag(ds,1)+diag(ds,‐1) n= 6 dp = 111111 ds = 11111 E= 410000 141000 014100 001410 000141 000014
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 17
e) >> b=[‐96;174;30;‐396;12;90], x=A\b b=‐96 174 30 ‐396 12 90 x= ‐35.6125 46.4500 23.8124 ‐111.6998 26.9866 15.7533 f) Obsérvese que A es una matriz estrictamente diagonal dominante por lo que no haría falta
el pivoteo >> [L,U]=lu(A) L=
U=
g) La solución con la descomposición LU es >> x=U\(L\b)
x= ‐35.6125 46.4500 23.8124
‐111.6998 26.9866 15.7533
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 18
h) Para hallar la solución del sistema con el algoritmo de crout de MATLAB hemos de definir la función crout (a,b,c,z) en MATLAB con un fichero del tipo.m
File/NewBlank M‐File (las órdenes se pueden copiar del documento Ficheros_MATLAB (punto m) que se encuentra en el curso del Moodle del Centro >> a=[4,4,4,4,4,4],b=[1,1,1,1,1],c=[1,1,1,1,1],z=[‐96;174;30;‐396;12;90], crout(a,b,c,z) a= 444444 b= 11111 c= 11111 z=
‐96 174 30
‐396 12 90
x= 0 0 0 0 26.9866 15.7533 x= 0 0 0 ‐111.6998 26.9866 15.7533 x= 0 0 23.8124 ‐111.6998 26.9866 15.7533 x= 0 46.4500 23.8124 111.6998 26.9866 15.7533 x= ‐35.6125 46.4500 23.8124 ‐111.6998 26.9866 15.7533 ans = ‐35.6125 46.4500 23.8124 ‐111.6998 26.9866 15.7533
i) Para hallar la solución del sistema con el método (iterativo) de Jacobi hemos de definir una función que designaremos por jacobi (A,b,x0,tol,maxiter) en MATLAB con un fichero del tipo.m (tal y como se ha mostrado en el apartado anterior) A es la matriz de coeficientes del sistema, b es la columna de términos independientes, x0 es el valor inicial, tol es la cota de error y maxiter es el máximo número de iteraciones >>A,b=[‐96;174;30;‐396;12;90],x0=[0;0;0;0;0;0],tol=0.01,maxiter=50,jacobi(A,b,x0,tol,maxiter) A=
b=-96 174 30‐396 12 90
x0 = 0 0 0 0 0 0 tol = 0.0100 maxiter = 50 incr = 1.0100 ans =‐35.6130 46.4520 23.8113 ‐111.6972 26.9857 15.7545
j) Para hallar la solución del sistema con el método (iterativo) de Gauss‐Seidel hemos de definir una función que podemos designar por gausSeidel (A,b,x0,tol,maxiter) en
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 19
MATLAB con un fichero del tipo.m (tal y como se ha mostrado en el apartado anterior) A es la matriz de coeficientes del sistema, b es la columna de términos independientes, x0 es el valor inicial, tol es la cota de error y maxiter es el máximo número de iteraciones
>>A,b=[‐96;174;30;‐396;12;90],x0=[0;0;0;0;0;0],tol=0.01,maxiter=50,gausSeidel(A,b,x0,tol,maxiter)
A= 410000 141000 014100 001410 000141 000014 b= ‐96 174 30 ‐396 12 90 x0 = 0 0 0 0 0 0 tol = 0.0100 maxiter = 50 incr = 1.0100 ans = ‐35.6130 46.4504 23.8122 ‐111.6997 26.9866 15.7534
k) Para hallar la solución del sistema con el método (iterativo) de Gauss‐Seidel hemos de definir una función que podemos designar por sobrerrelajacion (A,b,x0,omega,tol,maxiter) en MATLAB con un fichero del tipo.m (tal y como se ha mostrado en el apartado anterior) A es la matriz de coeficientes del sistema, b es la columna de términos independientes, x0 es el valor inicial, tol es la cota de error y maxiter es el máximo número de iteraciones >> A,b=[‐96;174;30;‐396;12;90], x0=[0;0;0;0;0;0], omega=1.2, tol=0.01, maxiter=50, sobrerrelajacion(A,b,x0,omega, tol,maxiter) b= ‐96 174 30 ‐396 12 90
x0 = 0 0 0 0 0 0 omega = 1.2000 tol = 0.0100 maxiter = 50 incr = 1.0100 ans = ‐35.6124 46.4497 23.8126 ‐111.6998 26.9866 15.7533
l) El número de condición de A es: >> cond(A)
ans = 2.6396 Es decir, la matriz está bien condicionada.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 20
5.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 2 3
1 2 3
3 2 6 2
4 9
5 3 1
x x xx x x
x x x
+ − = − + − = − + =
, se pide:
a) Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b) Estudiar si A es definida positiva. c) Estudiar si la matriz A de los coeficientes es estrictamente diagonal dominante, en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante. d) ¿Es B definida positiva? e) Halla el número de condición de las matrices A y B y comenta el resultado. f) Hallar la descomposición LU de la matriz A y de la matriz B y explicar las diferencias entre ambas descomposiciones. g) Hallar la solución de los sistemas S y S’, a partir de las matrices de descomposición LU y usando la instrucción del apartado a) y di si coinciden o no. h) Da una explicación de los resultados del apartado g. i) Si queremos obtener, por el método de Jacobi, una solución aproximada del sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿porqué? j) Teniendo en cuenta la respuesta en i) Halla una solución aproximada para una tolerancia de 0.01, y dí cuántas iteraciones son necesarias.
Solución: a) >> A=[3,2,-6;4,1,-1;1,-5,3],b=[-2;9;1], x=A\b A = 3 2 -6 4 1 -1 1 -5 3 b = -2 9 1 x = 2.3830 1.4894 2.0213
b) A será definida positiva si los menores principales son todos positivos, en este caso det([3,2;4,1]) = -5 <0, luego A no es definida positiva.
c) iia >1
n
ijjj i
a=≠
∑ para i=1….n, para que A sea estrictamente diagonal dominante por filas, en este
caso A no lo es pues ya en la primera fila 3<2+|-6|=8
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 21
Reordenando las filas (f1→f3, f2→f1) se obtiene el sistema S’1 2 3
1 2 3
1 2 3
4 9
5 3 1
3 2 6 2
x x xx x xx x x
+ − = − + = + − = −
cuya matriz B=[4,1,-1;1,-5,3;3,2,-6] cumple la condición de estrictamente diagonal dominante
4>1+1; 5>1+3; 6>3+2 y es equivalente al anterior (tiene la misma solución)
>> B=[4,1,-1;1,-5,3;3,2,-6] ;c=[9;1;-2];x=B\c x = 2.3830 1.4894 2.02138
d) La matriz B tampoco es definida positiva pues aunque a11= 4>0, 4 1
21 01 5
= − <−
e) cond(A) =3.7494 = cond(B) El número de condición indica que son matrices bien condicionadas (número cerca de 1) y coinciden por ser al ser A una matriz bien condicionada el intercambio por filas no produce cambio significativo del número de condición.
f) >> [L,U]=lu(A) L = 0.7500 -0.2381 1.0000 1.0000 0 0 0.2500 1.0000 0 U = 4.0000 1.0000 -1.0000 0 -5.2500 3.2500 0 0 -4.4762 La descomposición LU de una matriz es una descomposición en productos de sendas matrices triangulares, una inferior y otra superior, se observa que en el caso de A la descomposición es errónea por no ser L triangular inferior, ello es debido a que A no es estrictamente diagonal dominante
>> [L,U]=lu(B) L = 1.0000 0 0 0.2500 1.0000 0 0.7500 -0.2381 1.0000 U = 4.0000 1.0000 -1.0000 0 -5.2500 3.2500 0 0 -4.4762
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 22
En el caso de la matriz B la descomposición es correcta porque B si es estrictamente diagonal dominante.
g) Utilizando x=U\(L\b) en las 2 descomposiciones anteriores se obtiene la misma solución que para x=A\b, es decir, x= 2.3830 1.4894 2.0213
h) Coinciden porque la instrucción \ (x=U\(L\b)) pivota las ecuaciones por lo que las matrices LU usadas en el caso de la matriz A son pivotadas por el programa
i) Hemos de usar las matrices asociadas al sistema S’ pues hemos de aplicar el teorema que dice que “Si A es una matriz es estrictamente diagonalmente dominante, entonces para cualquier estimación inicial x(0), las iteraciones de Jacobi y de Gauss-Seidel convergen a la solución del
sistema inicial S ≡ Ax=b”.
j) >> B=[4,1,-1;1,-5,3;3,2,-6] ;c=[9;1;-2];
x0=[0;0;0]; tol=0.01; maxiter=9; jacobi(B,c,x0,tol,maxiter)
incr =1.0100
No converge con las iteraciones dadas
ans =
2.3803
1.4838
2.0246
>> B=[4,1,-1;1,-5,3;3,2,-6] ;c=[9;1;-2];
x0=[0;0;0];
tol=0.01;
maxiter=10;
jacobi(B,c,x0,tol,maxiter)
incr =1.0100
1.0100
ans =
2.3852
1.4908
2.0181
Por lo que son necesarias 10 iteraciones.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 23
6.- Dado el sistema S1 ≡ 1 2 3
1 2 3
1 2 3
2 6 38
3 7 34
8 2 20
x x xx x xx x x
− − = −− − + = −− + − = −
, se pide:
a) Estudiar si la matriz de coeficientes de S1 es estrictamente diagonal dominante por filas y justificar si para aplicar el método de Gauss sería conveniente o no realizar una pivotación parcial. b) Escribir un sistema S2 equivalente a S1 cuya matriz de coeficientes sea estrictamente diagonal dominante por filas (usar la operación elemental intercambio de filas). c) Hallar la solución del sistema S2 por el método de Gauss con MATLAB (x=A\b) ¿Se obtendría la misma solución para S1? Razona la respuesta. d) Hallar la descomposición LU con la función de MATLAB [L,U]=lu(A) tanto para el sistema S1 como para S2 y comentar los resultados. e) Calcular la solución del sistema S2 utilizando la descomposición LU obtenida en el apartado anterior.
Solución
a) La matriz de coeficientes A1 del sistema S1 no es diagonal dominante por filas, por tanto, para aplicar el método de Gauss sería conveniente realizar una pivotación. Matlab, de hecho, utilizaría Gauss con pivotación para resolverlo si aplicamos la instrucción \ : A1=[2,-6,-1;-3,-1,7;-8,1,-2],b=[-38;-34;-20],x=A1\b A1 = 2 -6 -1 -3 -1 7 -8 1 -2 b = -38 -34 -20 x = 4 8 -2
b) El sistema S2 equivalente cuya matriz de coeficientes sea diagonal dominante sería:
�−8 1 −22 −6 −1−3 −1 7
� ∗ �𝑥𝑥1𝑥𝑥2𝑥𝑥3� = �
−20−38−34
�
c) Sí, se obtendrá la misma respuesta tal como se ha indicado en el apartado a): A2=[-8,1,-2;2,-6,-1;-3,-1,7;],b=[-20;-38;-34],x=A2\b
A2 = -8 1 -2 2 -6 -1 -3 -1 7 b = -20 -38 -34 x =
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 24
4 8 -2
d) Para A1 A1=[2,-6,-1;-3,-1,7;-8,1,-2],[L,U]=lu(A1) A1 = 2 -6 -1 -3 -1 7 -8 1 -2 L1 = -0.2500 1.0000 0 0.3750 0.2391 1.0000 1.0000 0 0 U1 = -8.0000 1.0000 -2.0000 0 -5.7500 -1.5000 0 0 8.1087 Observamos que L no es triangular inferior Para A2 la descomposición LU es A2=[-8,1,-2;2,-6,-1;-3,-1,7;],[L,U]=lu(A2) A2 = -8 1 -2 2 -6 -1 -3 -1 7 L2 = 1.0000 0 0 -0.2500 1.0000 0 0.3750 0.2391 1.0000 U2 = -8.0000 1.0000 -2.0000 0 -5.7500 -1.5000 0 0 8.1087 Al no ser A1 estrictamente diagonal dominante los resultados para las matrices L son distintos (L1≠L2), es más, L1 no es triangular inferior. Y es que, llamando P a la matriz unitaria de cambio de filas se verifica P A1 = A2 = L2 U2, y, por tanto, A1 = (P-1 L2 ) U2 = L1 U1. La matriz L2 sí es triangular inferior, no así la matriz L1 = P-1 L2. Para hacer directamente la descomposición LU de A1 hay que realizar previamente la pivotación: A=[2,-6,-1;-3,-1,7;-8,1,-2],[L,U, P]=lu(A) A = 2 -6 -1 -3 -1 7 -8 1 -2 L = 1.0000 0 0 -0.2500 1.0000 0 0.3750 0.2391 1.0000 U = -8.0000 1.0000 -2.0000
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 25
0 -5.7500 -1.5000 0 0 8.1087 P = 0 0 1 1 0 0 0 1 0 Con la permutación de filas las matrices L y U coinciden (precisamente la reordenación de filas de S1 es la permutación P)
e) A=[-8,1,-2;2,-6,-1;-3,-1,7;];b=[-20;-38;-34];[L,U]=lu(A);x=U\(L\b) x = 4 8 -2
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 26
7.- Dado el sistema de 1 2 3
1 2 3
1 2 3
5 21,5
10 2 27
3 6 2 61,5
x x xx x xx x x
+ + = − + − =− − + = −
, se pide:
a) Comprobar que A es una matriz bien condicionada y resolver el sistema con el comando \ b) Hallar la descomposición LU de la matriz A con las funciones [L,U] y [L,U,P] de MatLab. Comenta la diferencia observada en los resultados, lee el tema 1 (de sistemas) y razona a partir de la teoría la razón de dicha diferencia. c) Razonar si A es estrictamente diagonal dominante o no, en caso negativo decir si se puede obtener uno equivalente Bx=c, cuya matriz sí sea estrictamente diagonal dominante d) Hallar la descomposición [L,U] y [L,U,P] de la matriz B y justifica el resultado e) ¿A cuál de los dos sistemas anteriores se puede aplicar los métodos de Jacobi y Gauss-Seidel con la seguridad de que habrá convergencia? Razona la respuesta citando, en su caso, el teorema que lo asegura. f) Completa la tabla que aparece a continuación para el sistema que resulta del apartado b) siendo x la solución obtenida en el apartado a) y k el nº mínimo de iteraciones para la convergencia.
k (mínimo iterac.)
( 1)kx −
( )kx ( ) ( 1)k kx x −
∞− ( )kx x
∞−
Jacobi (tol=0.01)
Gauss-Seidel (tol=0.01)
Jacobi (tol=0.001)
Gauss-Seidel (tol=0.001)
Solución a) cond(A) ans = 2.4580 Al ser pequeño el número de condición, A es una matriz bien condicionada. b = [-21.5;27;-61.5]; A\b ans = 0.5000 8.0000 -6.0000 b) [L,U]=lu(A) L = 0.1000 -0.1481 1.0000 1.0000 0 0 -0.3000 1.0000 0 U = 10.0000 2.0000 -1.0000 0 -5.4000 1.7000
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 27
0 0 5.3519 [L,U,P]=lu(A) L = 1.0000 0 0 -0.3000 1.0000 0 0.1000 -0.1481 1.0000 U = 10.0000 2.0000 -1.0000 0 -5.4000 1.7000 0 0 5.3519 P = 0 1 0 0 0 1 1 0 0 Como A no es estrictamente diagonal dominante, no estaba garantizada su descomposición LU sin pivotación. Y efectivamente hay que efectuar pivotación a través de la matriz P para obtener la descomposición PA=LU. c) A no es estrictamente diagonal dominante, como ya se ha señalado en el apartado anterior. Realizamos un intercambio de filas para transformarla en una matriz que sí lo sea. >> B=[10 2 -1;-3 -6 2;1 1 5]; c=[27; -61.5;-21.5]; >> B\c ans = 0.5000 8.0000 -6.0000 d) >> [L,U]=lu(B) L = 1.0000 0 0 -0.3000 1.0000 0 0.1000 -0.1481 1.0000 U = 10.0000 2.0000 -1.0000 0 -5.4000 1.7000 0 0 5.3519 >> [L,U,P]=lu(B) L = 1.0000 0 0 -0.3000 1.0000 0 0.1000 -0.1481 1.0000 U = 10.0000 2.0000 -1.0000 0 -5.4000 1.7000 0 0 5.3519 P = 1 0 0 0 1 0 0 0 1
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 28
Como B es estrictamente diagonal dominante, admite descomposición LU sin pivotación y por eso se obtienen las mismas L y U al ser P la matriz unidad: A = LU equivalente a PA= LU. e) Al ser B estrictamente diagonal dominante, está garantizada la convergencia del sistema Bx=c en los métodos de Jacobi y Gauss-Seidel. f) Jacobi con tolerancia 0.01: >> x0=[0;0;0]; tol=0.01; maxiter=10; >> jacobi(B,c,x0,tol,maxiter) incr = 1.0100 ans = 0.5010 8.0009 -5.9996 >> jacobi(B,c,x0,tol,7) incr = 1.0100 No converge con las iteraciones dadas ans = 0.5010 7.9969 -5.9958 >> jacobi(B,c,x0,tol,8) incr = 1.0100 ans = 0.5010 8.0009 -5.9996 >> jacobi(B,c,x0,tol,8)-jacobi(B,c,x0,tol,7) incr = 1.0100 incr = 1.0100 No converge con las iteraciones dadas ans = -0.0000 0.0039 -0.0038 >> jacobi(B,c,x0,tol,8)-[0.5;8;-6] incr = 1.0100 ans = 0.0010 0.0009 0.0004 Jacobi con tolerancia 0.001: >> jacobi(B,c,x0,0.001,10) incr = 1.0010 ans = 0.5000 7.9999 -5.9999 >> jacobi(B,c,x0,0.001,9) incr = 1.0010 No converge con las iteraciones dadas
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 29
ans = 0.4999 7.9996 -6.0004 >> jacobi(B,c,x0,0.001,10)-jacobi(B,c,x0,0.001,9) incr = 1.0010 incr = 1.0010 No converge con las iteraciones dadas ans = 1.0e-03 * 0.1711 0.3201 0.4810 >> jacobi(B,c,x0,0.001,10)-[0.5;8;-6] incr = 1.0010 ans = 1.0e-03 * 0.0381 -0.0596 0.1026 Gausseidel con tolerancia 0.01: >> gausseidel(B,c,x0,tol,6) incr = 1.0100 ans = 0.5003 8.0001 -6.0001 >> gausseidel(B,c,x0,tol,5) incr = 1.0100 No converge con las iteraciones dadas ans = 0.4973 7.9991 -5.9993 >> gausseidel(B,c,x0,tol,6)-gausseidel(B,c,x0,tol,5) incr = 1.0100 incr = 1.0100 No converge con las iteraciones dadas ans = 0.0029 0.0010 -0.0008 >> gausseidel(B,c,x0,0.01,6)-[0.5;8;-6] incr = 1.0100 ans = 1.0e-03 * 0.2534 0.1121 -0.0731 Gausseidel con tolerancia 0.001: >> gausseidel(B,c,x0,0.001,6)
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 30
incr = 1.0010 No converge con las iteraciones dadas ans = 0.5003 8.0001 -6.0001 >> gausseidel(B,c,x0,0.001,7) incr = 1.0010 ans = 0.5000 8.0000 -6.0000 >> gausseidel(B,c,x0,0.001,7)-gausseidel(B,c,x0,0.001,6) incr = 1.0010 incr = 1.0010 No converge con las iteraciones dadas ans = 1.0e-03 * -0.2832 -0.1216 0.0810 >> gausseidel(B,c,x0,0.001,7)-[0.5;8;-6] incr = 1.0010 ans = 1.0e-04 * -0.2974 -0.0950 0.0785 Todos estos resultados se recogen en la tabla siguiente:
k (mínimo iterac.)
( 1)kx −
( )kx ( ) ( 1)k kx x −
∞− ( )kx x
∞−
Jacobi (tol=0.01) 8
0.5010 7.9969 -5.9958
0.5010 8.0009 -5.9996
0.0039 0.001
Gauss-Seidel (tol=0.01) 6
0.4973 7.9991 -5.9993
0.5003 8.0001 -6.0001
0.0029 0.0002534
Jacobi (tol=0.001) 10
0.4999 7.9996 -6.0004
0.5000 7.9999 -5.9999
0.000481 0.0001026
Gauss-Seidel (tol=0.001) 7
0.5003 8.0001 -6.0001
0.5000 8.0000 -6.0000
0.0002832 0.0002974
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 31
8.- Un ingeniero que trabaja en la construcción requiere 4800, 5800 y 5700 m3 de arena, grava fina y grava gruesa, respectivamente. Hay 3 canteras de las que se puede extraer dichos materiales y su distribución es:
Arena % Grava fina % Grava gruesa %
Cantera 1 55 30 15
Cantera 2 25 45 30
Cantera 3 25 20 55
El sistema lineal correspondiente a los datos de la tabla es:
A x= b 1 2 3
1 2 3
1 2 3
0,55 0,25 0,25 4800
0,3 0,45 0,2 5800
0,15 0,3 0,55 5700
+ + =⇔ + + = + + =
x x xx x xx x x
, siendo x1 = material total extraído de la
primera cantera, x2 = material total extraído de la segunda cantera y x3 = material total extraído de la tercera cantera a) Estudiar si la matriz A es estrictamente diagonal dominante y hallar la solución con el comando \ de MatLab. b) Calcula una aproximación con el método de Gauss-Seidel con tolerancia 0.01. Indica el número de iteraciones que has necesitado (copia en la respuesta la iteración que converge y la anterior). Expresa en una tabla la cantidad extraída de cada cantera:
Gauss Arena Grava fina Grava gruesa Total
Cantera 1
Cantera 2
Cantera 3
c) Calcula una aproximación con el método de sobrerrelajación con w=1.2 e igual tolerancia (copia en la respuesta la iteración que converge y la anterior). Rellena una tabla similar a la del apartado b). d) Prueba, con valores de w = 0.8, w =1.1, w = 1.4 si es posible rebajar el número de iteraciones necesarias para obtener una aproximación con tolerancia 0.01. Compara estos resultados con los obtenidos en b) y c) y preséntalo en una tabla similar a la siguiente, siendo “x” la solución con el comando \.
k mínimo de convergencia
( )kx =[ ]( )
1 2 3, ,kx x x ( )
∞−kx x
Gauss-Seidel Sob. w=1,2 Sob. w= 0.8
Sob. w=1.1
Sob. w=1.4
Solución a. La matriz A no es estrictamente diagonal dominante porque en la segunda fila
a22 < a21 + a23 (0.45<0.3+0.2), sin embargo está muy próxima a ser diagonal dominante.
A=[0.51,0.24,0.25;0.25,0.55,0.2;0.15,0.3,0.55],b=[4800;5800;5700],x=A\b A =
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 32
0.5500 0.2500 0.2500 0.3000 0.4500 0.2000 0.1500 0.3000 0.5500 b = 4800 5800 5700 La solución es x=A\b = [2416.667, 9193.333, 4690.0]
b. Tomando como x0 = [0;0;0] gausseidel(A,b,x0,0.01,13) incr = 1.010000000000000 No converge con las iteraciones dadas ans = x1 = 2416.675 x2 = 9193.323 x3 = 4690.002 >> gausseidel(A,b,x0,0.01,14) incr = 1.0100 ans = x1 = 2416.670
x2 = 9193.330 x3 = 4690.001 luego se necesitan 14 iteraciones para la aproximación deseada y las cantidades extraídas de las canteras son:
Gauss Arena Grava fina Grava gruesa Total
Cantera 1 1329,17 725,00 362,50 2416.67
Cantera 2 2298,33 4137,00 2758,00 9193.330
Cantera 3 1172,50 938,00 2579,50 4690.001
c. Utilización w = 1,2
>> sobrerrelajacion(A,b,x0,1.2,0.01,11) incr =1.0100 No converge con las iteraciones dadas ans = 2416.66 9193.33 4690.00 sobrerrelajacion(A,b,x0,1.2,0.01,12) incr =1.0100 ans = x1 = 2416.667 x2 = 9193.332 x3 = 4690.000 luego se necesitan 12 iteraciones para la aproximación deseada y las cantidades extraídas de las canteras son:
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 33
w=1,2 Arena Grava fina Grava gruesa Total
Cantera 1 1329,17 725,00 362,50 2416.667 Cantera 2 2298,33 4137,00 2758,00 9193.332 Cantera 3 1172,50 938,00 2579,50 4690.000
d. La solución con el comando \ es x= [2416.667, 9193.333, 4690.0]
k mínimo de
convergencia x(k) ||x(k) – x||∞
Gauss-Seidel 14 [2416.667,9193.333,4690.07] 0.07
Sobrerrelajación. w=1.2
12 [2416.667,9193.332,4690.001] 0.001
Sobrerrelajación w=0.8
22 [2416.672,9193.335,4690.005] 0.005
Sobrerrelajación w=1.1
11 [2416.667,9193.332,4690.000] 0.001
Sobrerrelajación w=1.4
19 [2416.664,9193.335,4689.998] 0.003
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 34
9.- Dado el sistema de ecuaciones lineales S≡1 2 3
1 3
1 2
6 2 4.6
4 14.5
2 5 8.7
− + = + =− + =
x x xx x
x x, se pide
a. Resolver con MATLAB con la instrucción x=A\b (método de Gauss). b. Estudiar si A es definida positiva. c. Estudiar si la matriz A de los coeficientes es estrictamente diagonal dominante,
en caso negativo definir un sistema S’ cuya matriz B de coeficientes sea estrictamente diagonal dominante.
d. ¿Es B definida positiva? e. Hallar el número de condición de las matrices A y B y comentar el resultado. f. Hallar la descomposición LU de la matriz A y de la matriz B y explicar las
diferencias entre ambas descomposiciones. g. Hallar la solución de los sistemas S y S’, a partir de las matrices de
descomposición LU y usando la instrucción del apartado a). ¿Coinciden? h. Dar una explicación de los resultados del apartado g. i. Si queremos obtener, por el método de Jacobi, una solución aproximada del
sistema formado por las 3 ecuaciones dadas ¿debemos usar las matrices asociadas a S o las asociadas a S’? ¿por qué?
j. Teniendo en cuenta la respuesta en i), hallar una solución aproximada para una tolerancia de 0.001, y decir cuántas iteraciones son necesarias.
k. Mismas cuestiones i. y j. utilizando Gauss-Seidel. l. Mismas cuestiones i. y j. utilizando Sobrerrelajación para dos valores
diferentes de w.
Solución:
a. >> A=[6 -2 1;1 0 4;-2 5 0] A = 6 -2 1 1 0 4 -2 5 0 >> b=[4.6;14.5;8.7] b = 4.6000 14.5000 8.7000 >> x=A\b x = 0.9000 2.1000 3.4000 b. >> det(A) ans = -99 No es definida positiva. Ni siquiera es simétrica y además det(A) < 0.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 35
c. Claramente la matriz A no es estrictamente diagonal dominante. Por ejemplo en su segunda fila, el elemento de la diagonal principal 0 no es mayor que la suma de los otros dos (1 + 4 = 5).
Intercambiando el orden de las dos últimas filas, queda ya una matriz estrictamente diagonal dominante: >> B=[6 -2 1;-2 5 0;1 0 4] B = 6 -2 1 -2 5 0 1 0 4 Hacemos lo mismo con la matriz de términos independientes: >> c=[4.6;8.7;14.5] c = 4.6000 8.7000 14.5000 El nuevo sistema S’ es equivalente a S y tiene, por tanto, las mismas soluciones: >> y=B\c y = 0.9000 2.1000 3.4000
d. B es simétrica y sus tres menores principales son positivos: 6, 6 2
262 5
−=
− y det(B) =
99. Luego B es definida positiva. e. >> cond(A) ans = 2.5774 >> cond(B) ans = 2.5774 El número de condición indica que son matrices bien condicionadas (número cerca de 1) y coinciden ambos números por ser matrices bien condicionadas que solo se diferencian en el orden de sus filas. f. Descomposición LU de la matriz A: >> [L,U]=lu(A) L = 1.0000 0 0 0.1667 0.0769 1.0000 -0.3333 1.0000 0 U = 6.0000 -2.0000 1.0000 0 4.3333 0.3333 0 0 3.8077 Descomposición LU de la matriz B: >> [L,U]=lu(B) L = 1.0000 0 0 -0.3333 1.0000 0
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 36
0.1667 0.0769 1.0000 U = 6.0000 -2.0000 1.0000 0 4.3333 0.3333 0 0 3.8077 Como B es estrictamente diagonal dominante, admite descomposición LU sin pivotación y por eso L es triangular inferior. No ocurre así con A. g. Solución de ambos sistemas: >> [L,U]=lu(A);x=U\(L\b) x = 0.9000 2.1000 3.4000 >> [L,U]=lu(B);y=U\(L\c) y = 0.9000 2.1000 3.4000 Coinciden. Y es que eran sistemas equivalentes. h. Coinciden porque la instrucción \ ( x=U\(L\c)) pivota las ecuaciones por lo que las
matrices LU usadas en el caso de la matriz A son pivotadas por el programa. i. Como B es estrictamente diagonal dominante, tenemos asegurada la convergencia de
Jacobi en la resolución del sistema S’.
j. >> x0=[0;0;0];tol=0.001; >> jacobi(B,c,x0,tol,9) incr = 1.0010 No converge con las iteraciones dadas ans = 0.8992 2.0997 3.4002 >> jacobi(B,c,x0,tol,10) incr = 1.0010 ans = 0.8999 2.0997 3.4002 Luego, son necesarias 10 iteraciones. k. Como B es estrictamente diagonal dominante, tenemos asegurada la convergencia de
Gausseidel en la resolución del sistema S’. >> gausseidel(B,c,x0,tol,5) incr = 1.0010
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 37
No converge con las iteraciones dadas ans = 0.8993 2.0997 3.4002 >> gausseidel(B,c,x0,tol,6) incr = 1.0010 ans = 0.8999 2.0999 3.4000 Se necesitan, por tanto, 6 iteraciones frente a las 10 con Jacobi.
l. >> sobrerrelajacion(B,c,x0,1.2,0.01,5) incr = 1.0100 No converge con las iteraciones dadas ans = 0.8995 2.0975 3.3940 >> sobrerrelajacion(B,c,x0,1.2,0.01,6) incr = 1.0100 ans = 0.9003 2.1006 3.4011 Siguen siendo necesarias 6 iteraciones como en Gausseidel. >> sobrerrelajacion(B,c,x0,0.1,tol,5) incr = 1.0010 No converge con las iteraciones dadas ans = 0.2635 0.6234 1.2310 >> sobrerrelajacion(B,c,x0,0.1,tol,6) incr = 1.0010 No converge con las iteraciones dadas ans = 0.3141 0.7476 1.4626 No se consigue disminuir el número de iteraciones necesarias para la convergencia.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 38
10.- Dado el sistema de ecuaciones lineales S ≡
2 -1 0 x 5
AX = B -1 2 -1 y = 0
0 -1 2 z 0
⇔
a) ¿Es A una matriz definida positiva?, ¿es A estrictamente diagonal dominante?
b) Razonar si puede utilizarse la descomposición LU sin pivoteo para resolver el sistema S. Si fuera así, resolverlo por ese método.
c) Razonar si puede utilizarse el método de Cholesky para resolver el sistema S. Si fuera así, resolverlo por ese método.
d) Razonar si puede utilizarse el algoritmo de Crout para encontrar la solución del sistema. Si fuera así, resolverlo por ese método.
e) Hallar una solución aproximada utilizando el método de Sobrerrelajación con w=1.2, para una tolerancia de 0.01, y justificar cuántas iteraciones son necesarias.
Solución: a) >> A=[2 -1 0;-1 2 -1;0 -1 2];
>> b=[5;0;0]; >> A\b ans = 3.7500 2.5000 1.2500 A es definida positiva por ser simétrica y tener todos sus menores principales positivos. En
efecto: 2 > 0, 2 1
3 01 2
−= >
−, A = 4 > 0.
A no es estrictamente diagonal dominante pues en la segunda fila 22a = 2 no es
estrictamente mayor que 21 23a + a = 2 .
b) Por ser A definida positiva, sí puede utilizarse la descomposición LU sin pivoteo para
resolver el sistema S. >> [L,U]=lu(A)
L = 1.0000 0 0 -0.5000 1.0000 0 0 -0.6667 1.0000 U = 2.0000 -1.0000 0 0 1.5000 -1.0000 0 0 1.3333 >> z=L\b z = 5.0000 2.5000
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 39
1.6667 >> X=U\z ans = 3.7500 2.5000 1.2500 c) Por el mismo motivo, puede aplicarse la descomposición de Cholesky.
>> L=chol(A,'lower') L = 1.4142 0 0 -0.7071 1.2247 0 0 -0.8165 1.1547 >> z=L\b z = 3.5355 2.0412 1.4434 >>X= L'\z ans = 3.7500 2.5000 1.2500 d) Como A es una matriz tridiagonal, puede aplicarse el algoritmo de Crout.
>> a=[2 2 2];b=[-1 -1];c=[-1 -1];z=[5;0;0]; >> crout(a,b,c,z) ans = 3.7500 2.5000 1.2500 e) >> b=[5;0;0];
>> sobrerrelajacion(A,b,[0;0;0],1.2,0.01,5) incr = 1.0100 No converge con las iteraciones dadas ans = 3.7471 2.5012 1.2505 >> sobrerrelajacion(A,b,[0;0;0],1.2,0.01,6) incr = 1.0100 ans = 3.7513 2.5009 1.2504 Luego, son necesarias 6 iteraciones para la convergencia pedida.
Sistemas de Ecuaciones Lineales
U. D. de Matemáticas de la ETSITGC Asignatura: Métodos Matemáticos 40
11.- Dado el sistema de ecuaciones lineales S≡1 2
1 2 3
2 3
0,8 0,4 41
0,4 0,8 0,4 25
0,4 0,8 10,5
x xx x xx x
− =− + − =− + =
, se pide:
a) Estudiar si la matriz A de los coeficientes es definida positiva y si está bien condicionada. b) Dar la solución con el comando \ de Matlab. c) Dar la solución con el algoritmo de Crout. d) Completar la tabla que aparece al dorso de la hoja (basta escribir el resultado para 3 iteraciones: una de ellas la mínima que cumple la condición, una anterior y otra posterior) para una tolerancia tol=0,01 y siendo x la solución del sistema obtenida en el apartado b). Solución: a) A=[0.8,-0.4,0;-0.4,0.8,-0.4;0,-0.4,0.8]; b=[41;25;10.5]; cond(A) ans = 5.8284, luego A está bien condicionada. >> A(1,1), A2=A(1:2,1:2), det(A2), det(A) ans = 0.8000 A2 = 0.8000 -0.4000 -0.4000 0.8000 ans = 0.4800 ans = 0.2560, luego A es una matriz definida positiva por ser positivos los menores principales. b) x = A\B= [114.6875, 126.8750, 76.5625] c) a=[0.8,0.8,0.8];b=[-0.4,-0.4];c=[-0.4,-0.4];z=[41;25;10.5],crout(a,b,c,z) ans = [114.6875 126.8750 76.5625], que es igual que la obtenida con la descomposición “\”. d) Considerando la solución del sistema obtenida con “\”:
x∞
= máx {114.6875, 126.8750, 76.5625}= 126.8750.
Jacobi Iteración k = 8 (no cumple) Iteración k = 17 (Sí, mínimo) Iteración k= 20 (sí cumple)
Aprox. ( )kx [106.7578,114.9219,68.6328] [114.3140,126.3794,76.1890 [114.5636,126.6882,76.4386]
( )kx x
x∞
∞
−
114.9219 126.8750 0.0942
126.8750
−=
126.3794 126.8750
126.87500.0039
−=
126.6882 126.8750
126.87500.0015
−=
Gauss-Seidel Iteración k = 8 (no cumple) Iteración k = 9 (Sí, mínimo) Iteración k =17 (sí cumple)
Aprox. ( )kx [113.5938,125.7813,76.0156] [114.1406,126.3281,76.2891] [114.6790,126.8665,76.5582]
( )kx x
x∞
∞
−
125.7853 126.8750 0.0086
126.8750
−=
126.3281 126.8750
126.87500.0043
−=
126.8665 126.8750
126.87500.000069
−=
Sobrerrelajación (w=1.2)
Iteración k = 4 (no cumple) Iteración k = 5 (Sí, mínimo) Iteración k =9 (sí cumple)
Aprox. ( )kx [111.8268,125.2246,76.3314] [114.2694,126.8155,76.5730] [114.6884,126.8755,76.5626]
( )kx x
x∞
∞
−
125.2246 126.8750 0.0130
126.8750
−=
126.8155 126.8750
126.87500.00046
−=
126.8775 126.8750
126.87500.000004
−=
Sistemas de ecuaciones lineales
Se llama sistema de m ecuaciones lineales con n incógnitas a un conjunto de ecuaciones lineales de la forma:
mnmn22m11m
2nn2222121
1nn1212111
bxa...xaxa
...
b xa...xaxa
b xa...xaxa
S
donde los coeficientes a ij , i=1,...,m, j=1,...,n, y los términos independientes
bi , i=1,...,m, son escalares de un cuerpo K y x x xn1 2, , . . . , son las incógnitas.
Matriz definida positiva
Una matriz simétrica A=At es definida positiva si y sólo si XtAX>0 para cualquier n-upla X no nula.
Matriz estrictamente diagonal dominante Una matriz )K(MA n es estrictamente diagonal dominante por filas
si: n
ii ijj 1j i
a a
para i=1,…,n
Número de condición
Se define el número de condición de una matriz A como el número:
Cond(A)=||A|| . ||A-1||, siendo ||A|| una norma de la matriz A
El número de condición es una medida de la sensibilidad de la solución de un sistema de ecuaciones lineales a los errores presentes en los datos. Da una indicación de la precisión de los resultados de una matriz inversa o una solución de un sistema de ecuaciones lineales.
Matriz dispersa Es la matriz que tiene pocos elementos no nulos frente a los nulos, por ejemplo, la matriz identidad sería una matriz dispersa.
Método de factorización o descomposición LU
Este método de resolución de un sistema S Ax=b es consecuencia inmediata de la
reducción de la matriz A a una matriz escalonada U por el método de eliminación de Gauss.
El procedimiento, consiste en transformar, mediante operaciones elementales, la matriz A en
un producto A= LU donde L es una matriz triangular inferior (mxm) y U es una matriz
escalonada (mxn). De esta forma, el sistema anterior se escribe:
LUx=b
Haciendo Ux=z, queda el sistema Lz=b que por sustitución hacia adelante es de resolución
inmediata y una vez obtenida z, se obtendría x en Ux=z con un procedimiento análogo de
resolución hacia atrás.
Si no es necesario el pivoteo (intercambio de filas) la matriz U es la resultante de la
eliminación de Gauss y la matriz L=E‐1 donde E es la matriz que resulta de aplicar las
operaciones elementales que hemos hecho para transformar A en U a la matriz identidad
de orden m, es decir:
Si Ek∙Ek‐1∙∙∙∙E1∙A=U, donde Ei son las matrices elementales2 de la reducción de Gauss y
designamos E= Ek∙Ek‐1∙∙∙∙E1 E∙A=U A= E‐1∙U, luego:
A=LU, donde L= E‐1 y U es la matriz escalonada de la reducción de Gauss.
Si es necesario el intercambio de filas (pivoteo) y conociéramos dichos cambios antes de
aplicar Gauss, podríamos expresar el efecto de los mismos mediante una matriz P unitaria
(los elementos no nulos son 1) que es la resultante de aplicar dichos cambios a la matriz
identidad correspondiente (mxm en este caso), entonces PAx=Pb= y se procedería a la
descomposición LU de PA como en el caso anterior, es decir:
PA=LU LUx= y haciendo Ux=z, se resolvería ,
en primer lugar Lz = y, a continuación , Ux=z
MATLAB proporciona la descomposición LU, con pivoteo, de una matriz A mediante la instrucción
[L,U,P]=lu(A)
Observación: La factorización LU presenta la ventaja de que con las mismas L y U permite la
resolución de sistemas de ecuaciones lineales que solo difieren en los términos independientes.
2 Matriz elemental es la que resulta de aplicar una operación elemental a una matriz identidad
Método de eliminación de Gauss
Este es el método más conocido, consiste en transformar un sistema S de ecuación matricial
Ax=b y mediante operaciones elementales, en un sistema S’ de forma escalonada o triangular
y ecuación Ux=c, cuya resolución es inmediata.
Diremos que un sistema S’ está en forma escalonada o es escalonado si es de la forma:
m
p
pnpnjpj
nnjj
nnjj
c
cxuxu
cxuxuxu
cxuxuxuxu
S
c0
0
'
1
222222
111212111
con (p<n)
En forma matricial S’
m
p
n
j
pnpj
nj
nj
nj
c
c
c
c
c
x
x
x
x
x
uu
uuu
uuuu
uuuuu
3
2
1
3
2
1
3333
222322
11131211
00000
00000
000
00
0
La matriz de coeficientes A se transforma en una matriz U escalonada.
Si A es una matriz cuadrada invertible (el sistema es compatible determinado), se transforma
en una matriz U triangular. Es decir, un sistema S’ está en forma triangular o es triangular si
es de la forma:
nnnn
nn
nn
cxu
cxuxu
cxuxuxu
S
' 22222
11212111
Método de Jacobi
Dado un sistema S Ax=b, el método de Jacobi consiste en iterar el sistema de punto fijo
Dx = (D – A)x + b, es decir,
D x(k) = (D – A) x(k‐1) + b
donde D es la matriz diagonal cuyos elementos son los de la diagonal de A.
Observemos que equivale a despejar las incógnitas de los elementos de la diagonal en S.
1 12 2 13 3 1
12 2 1 1
2 21 1 23 3 221 1
111
2 2
1 1
11 1
22 2 22
2 21 1 2 1 1
2
2
n n
nn
n n
n nn n
n n nn n n n
n
nn
nn
n
b a x a x a x
a x a x bb a x a x a xa x a x b
S
a x a x bb a x a
x a
x a
a x
a x x a
a xx
xa
El método de Jacobi se aplica siguiendo la siguiente secuencia de pasos:
Primer paso: se sustituye en el segundo miembro las incógnitas por la estimación inicial,
0 0 0 01 1 2 2 3 3, , , , n nx x x x x x x x
Los valores obtenidos en el primer miembro constituyen la primera aproximación x(1)
x(1)= 1 1 1 11 2 3, , , , nx x x x
Segundo paso: se sustituye en el segundo miembro las incógnitas por la aproximación
obtenida en el paso anterior,
1 1 1 11 1 2 2 3 3, , , , n nx x x x x x x x
Los valores obtenidos en el primer miembro constituyen la segunda aproximación x(2)
x(2)= 2 2 2 21 2 3, , , , nx x x x y así sucesivamente.
En general:
1 1 11 12 2 13 3 1
1 1 12 21 1 23 3 2
1 1
111
22
2
2
11 1 2 1 1
k
k
kn
k k kn n
k k kn n
k k kn n n n n
n
n
n
x a
x a
b a x a x a x
b a x a x a x
b a x a x a xx a
¿Cuándo paramos?: Criterio de convergencia (criterio de parada)
Se utiliza como criterio una cota de la diferencia en norma entre dos aproximaciones (iterados)
consecutivas.
( ) ( 1) (tolerancia)k kx x Tol
O incluso mejor
( ) ( 1)
( )
k k
k
x xTol
x
Como norma habitual se usa la norma del supremo x
, es decir
( ) ( 1) ( ) ( 1)
1
k k k ki i
i nx x máx x x
Algoritmo de Crout
Sea Ax=z, donde A es cuadrada y tridiagonal. Por comodidad usaremos la notación
na
ac
bac
ba
000
00
0
00
A 32
221
11
Podemos factorizar A como producto de dos matrices triangulares L y U, donde L es bidiagonal
inferior y U bidiagonal superior de la siguiente forma:
1000
0100
010
001
·
000
00
00
000
000
00
0
00
2
1
32
21
1
32
221
11
u
u
l
lc
lc
l
a
ac
bac
ba
nn
Esta factorización es la LU que se obtiene con el método de eliminación de Gauss, escalando
cada fila de la matriz triangular superior para que el pivote sea 1.
Las expresiones que nos dan los elementos de las matrices L y U son:
l1 = a1
1,,1 para nil
bu
i
ii
li = ai – ui-1 ci-1 para i = 2,···, n
De esta forma, el sistema tridiagonal Ax=z se transforma en dos sistemas bidiagonales
Ax=z LUx=z L(Ux)=z
Haciendo Ux=y, resolvemos primero de manera sencilla e inmediata, por sustitución hacia
adelante o directa, el sistema bidiagonal Ly=z
Seguidamente, por sustitución hacia atrás o regresiva, se resuelve, Ux=y.
Método de Gauss‐Seidel
Dado S Ax=b, el método de Gauss‐Siedel consiste en iterar el sistema de punto fijo
(L+D)x = (L+D – A)x + b,
Obsérvese que A‐(L+D) es la matriz triangular superior cuyos elementos no nulos son los que
están por encima de la diagonal superior, es decir,
A‐(L+D)=U=
12 1
2
0
0 0
0 0 0
n
n
a a
a
Luego la ecuación anterior queda de la forma (L+D)x = ‐Ux + b, y las sucesivas iteraciones se
obtienen mediante
(L+D)x(k) = – U x(k‐1) + b
1 11
1111 1
2121 1 22 2 2
22
1 1 2 21 1 2 2 1
2 2 13 3 1
12 2
1
1 1
2 1 23 3 22 2
n n
n n
n nn n
nn n nn nn n nn n
nnn
n
x aa x
a xa x a x x a
a x a x a xa x a
b a x a x a x
a x a x bb a x a xa x
x a xx
b
a
S
bb
La secuencia de pasos es semejante a la seguida en el método de Jacobi con la diferencia de que
el valores obtenidos para xi(k) seutiliza para aproximar xi+1
(k)
Primer paso: se sustituye en la primera ecuación del segundo miembro las incógnitas en
negro por la estimación inicial 0 0 02 2 3 3, , , n nx x x x x x para obtener 1
1 x ,
A continuación, se sustituye en la segunda ecuación 1 0 01 31 3, , , n nx x x xx x para
obtener 12 x
Seguidamente sustituiríamos en la tercera ecuación 1 1 0 01 2 4 41 2, , , , n nxx x x x x x x
para obtener 13x y así sucesivamente hasta obtener x(1)= 1 1 1 1
1 2 3, , , , nx x x x
Segundo paso: se procede ecuación por ecuación del sistema igual que en el primer paso
para obtener
x(2)= 2 2 2 21 2 3, , , , nx x x x y así sucesivamente.
En general:
( )1
11
( )21 1( )
2
( 1) ( 1) ( 1)1 12 2 1
22
( ) ( ) ( )1 1 2 2 1 1( )
3 3 1
( 1) ( 1)2 23 3 2
k
kk
k k
k k kn n
k kn n
kn n nn nk
nn
n
n
b a x a x a x
b a x a x
x a
a xx a
a x a x a xx a
b
Se utiliza el mismo criterio de convergencia (o de parada) que en el método de Jacobi.
Método de Sobrerrelajación
Si para un sistema determinado, S Ax=b, el método de Gauss‐Seidel converge, entonces ha de
verificarse, en general, que cada aproximación de cada incógnita ( )kix estará más cerca de la
solución que ( 1)kix para cada i = 1∙∙∙n.
El método de sobrerrelajación se basa en la idea de que el proceso de convergencia puede
acelerarse ponderando la diferencia entre los valores ( )kix y ( 1)k
ix para cada i = 1∙∙∙n , es decir,
( )kix = ( 1)k
ix + ∙di para cada i = 1∙∙∙n,
donde ( ) ( 1)ˆ k ki i id x x (denotamos por ( )k
ix la aproximación obtenida por el método de
sobrerrelajación y por ( )ˆ kix la que obtendríamos aplicando Gauss‐Seidel)
Sustituyendo y operando:
( )kix = ( 1)k
ix + ∙di = ( 1)kix + ∙ ( ) ( 1)ˆ k k
i ix x = ( 1) ( )ˆ1 ω ωk ki ix x para cada i = 1∙∙∙n
El proceso consiste, en consecuencia, hallar cada iteración de Gauss‐Seidel y ponderarla con el elegido. La secuencia de pasos es la siguiente:
Primer paso: partiendo de la estimación inicial x(0) obtenemos la primera iteración de
Gauss‐Seidel como se ha expicado en la página 4 anterior y la designamos
(1) 1 1 1 11 2 3ˆ ˆ ˆ ˆ ˆ, , , , nx x x x x
A continuación, hallamos la primera iteración de sobrerrelajación según la fórmula de dicho
método
(1) (0) (1)1 1 1
(1) (0) (1)2 2 2
(1) (0) (1)2
ˆ1 ω ω
ˆ1 ω ω
ˆ1 ω ω n n
x x x
x x x
x x x
Segundo paso: con esta aproximación obtenida x(1)= 1 1 1 11 2 3, , , , nx x x x se calcula la
segunda iteración con Gauss‐Seidel y la denotamos (2) 2 2 2 21 2 3ˆ ˆ ˆ ˆ ˆ, , , , nx x x x x y aplicamos
la fórmula de sobrerrelajación para obtener la segunda iteración x(2)= 2 2 2 21 2 3, , , , nx x x x
(2) (1) (2)1 1 1
(2) (1) (2)2 2 2
(2) (1) (2)2
ˆ1 ω ω
ˆ1 ω ω
ˆ1 ω ω n n
x x x
x x x
x x x
y así sucesivamente.
Es decir, en general:
( ) ( 1) ( )1 1 1
( ) ( 1) ( )2 2 2
( ) ( 1) ( )2
ˆ1 ω ω
ˆ1 ω ω ( )
ˆ1 ω ω
k k k
k k k
k k kn n
x x x
x x x
x x x
Y desarrollándola completamente:
( 1) ( 1) ( 1)1 12 2 13 3 1( ) ( 1)
1 1
( 1) ( 1)2 23 3 2( ) ( 1)
2 2
( ) ( 1
11
( )21 1
22
( ) ( )1 1 2 2)
1 ω ω
1 ω ω
1 ω
ˆ
ˆ ˆ ω
k k kn nk k
k kk
k k
n nk k
nk kn
n nn
b a x a x a xx x
b a x a xx
a
ax
b
xa
a x a xx x
( )1 1ˆ k
nn n
nn
a xa
La ecuación matricial del método se obtiene a partir de la ecuación de sobrerrelajación ()
kx = ( 1) ( )ˆ1 ω ωk kx x
La solución ( )ˆ kx de Gauss‐Siedel se obtiene al despejar ( )kx en la ecuación
(L+D)x(k) = – U x (k‐1) + b (ver página 4 apartado 3.4)
Operando:
Lx(k) + Dx(k) = – U x (k‐1) + b Dx(k) = ‐ Lx(k) – U x (k‐1) + b x(k) = D‐1 (‐ Lx(k) – U x (k‐1) + b)
kx = k k 1( 1) 11 ω ω·D ( L – U b) kx x x
D kx = k k 1( 1) 1D 1 ω ω·DD ( L – U b) kx x x
D
ωkx =
k k 1( 1)1 ωD L – U b
ωkx x x
( 1)D 1 ωD U b
ω ωk kL x x
Matrices tridiagonales
En diversas aplicaciones nos encontramos con sistemas Ax=z donde A es cuadrada y sus
elementos son todos nulos excepto los de la diagonal principal y algunas de las paralelas a dicha
diagonal. Estas matrices se denominan matrices banda.
Un caso particular de matrices banda son las matrices tridiagonales.
Se llama matriz tridiagonal a las matrices de la forma siguiente:
nnnn
nnnn
aa
aa
aa
aaa
aa
,1,
,11,1
3332
232221
1211
000
000
000
00
000
A
Para este tipo de matrices hay algoritmos de factorización que simplifican el número de
operaciones a realizar, aprovechando la gran cantidad de ceros que aparecen siguiendo
patrones regulares. Estos métodos son preferibles frente a los que no tienen en cuenta la
tridiagonalidad de la matriz.
U.D. de Matemáticas de la E.T.S.I. en Topografía, Geodesia y Cartografía 44
Descomposición de Cholesky
La descomposición de Cholesky es única: dada una matriz simétrica definida positiva A, hay una única matriz triangular inferior L con entradas diagonales estrictamente positivas tales que A = LLt.
El recíproco también es cierto: si A se puede escribir como LLt para alguna matriz invertible L, triangular inferior o no, entonces A es simétrica definida positiva.
Se obtiene de esta forma una nueva caracterización de las matrices simétricas definidas positivas: Una matriz simétrica es definida positiva si y solo si admite una única factorización de Cholesky.
11 12 1n
12 22 2n
1n 2n nn
a a a
a a aA
a a a
11 11 12 1n
12 22 22 2n
1n 2n nn nn
l 0 0 l l l
l l 0 0 l l
l l l 0 0 l
Al efectuar el producto e igualar se plantea un sistema.
11 12 1n
12 22 2n
1n 2n nn
a a a
a a a
a a a
211 21 11 n1 11
2 221 11 21 22 n1 21 n2 22
2 2 2n1 11 n1 21 n2 22 n1 n2 nn
l l l l l
l l l l l l l l
l l l l l l l l ... l
k 12
kk kk krr 1
k 1
ik ir krr 1
ikkk
k 1,...,n
l a l
a l ll ,i k 1,...,n
l
Sistemas de la forma Ax = b con A simétrica y definida positiva aparecen a menudo en la práctica. Por ejemplo, las ecuaciones normales en problemas de mínimos cuadrados lineales son problemas de esta forma.
La descomposición de Cholesky se utiliza para resolver este tipo de sistemas de ecuaciones lineales en la misma forma que se usa la descomposición LU genérica. Y es más eficiente y más estable numéricamente que cualquier otra descomposición LU.
U.D. de Matemáticas de la E.T.S.I. en Topografía, Geodesia y Cartografía 170
Tolerancia
Valor máximo del error.
Recommended