Practica tema 2: Teoría

Dados los sistemas de ecuaciones lineales:

A =

\[\begin{bmatrix} 7x_1 & + & x_2 & - & x_3 & + & 2x_4 & = & 3 \\ x_1 & + & 8x_2 & & & - & 2x_4 & = & -5 \\ -x_1 & & & + & 4x_3 & - & x_4 & = & 4 \\ 2x_1 & - & 2x_2 & - & x_3 & + & 6x_4 & = & -3 \end{bmatrix}\]

B =

\[\begin{bmatrix} 7x_1 & + & 3x_2 & - & x_3 & + & 2x_4 & = & -1 \\ 3x_1 & + & 8x_2 & + & x_3 & - & x_4 & = & 0 \\ -x_1 & + & x_2 & + & 4x_3 & - & x_4 & = & -3 \\ 2x_1 & - & 4x_2 & - & x_3 & + & 6x_4 & = & 1 \end{bmatrix}\]

Ejercicio A

Obtener las soluciones analíticas de los sistemas.


A = [7 1 -1 2;
     1 8 0 -2;
     -1 0 4 -1
     2 -2 -1 6;];
     
ba = [3;-5;4;-3];

xA = A\ba

B = [7 3 -1 2;
     3 8 1 -4;
     -1 1 4 -1
     2 -4 -1 6;];
     
bb = [-1;0;-3;1];

xB = B\bb

## xA =
## 
##    1.0000
##   -1.0000
##    1.0000
##   -1.0000
## 
## xB =
## 
##   -1.0000
##    1.0000
##   -1.0000
##    1.0000

Ejercicio B

Usando los métodos de Jacobi y Gauss-Seidel resolver los sistemas dados con cuatro decimales de exactitud usando programas para estos fines.

Solución mediante el método de Jacobi

Primer sistema

A = [7 1 -1 2;
     1 8 0 -2;
     -1 0 4 -1
     2 -2 -1 6;];
     
b = [3;-5;4;-3];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 300;

% Método de Jacobi
for k = 1:k_max,
  x(:, k+1) = D\(L+U)*x(:,k) + D\b;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor

% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)

## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 27
## Error de aproximacion: 2.2294e-08

Segundo sistema

A = [7 3 -1 2;
     3 8 1 -4;
     -1 1 4 -1
     2 -4 -1 6;];
     
b = [-1;0;-3;1];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 300;

% Método de Jacobi
for k = 1:k_max,
  x(:, k+1) = D\(L+U)*x(:,k) + D\b;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor

% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)

## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 127
## Error de aproximacion: 1.6881e-08

Solución mediante el método de Gauss-Seidel

Primer sistema

A = [7 1 -1 2;
     1 8 0 -2;
     -1 0 4 -1
     2 -2 -1 6;];
     
b = [3;-5;4;-3];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 300;

% Gauss-Seidel Method
for k = 1:k_max,
  x(:, k+1) = (D+L)\U*x(:,k) + (D+L)\b;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor

% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)

## Solucion iterativa:    0.6827  -0.5909   0.7780  -0.2051
## Numero de iteraciones: 15
## Error de aproximacion: 1.7918e-08

Segundo sistema

A = [7 3 -1 2;
     3 8 1 -4;
     -1 1 4 -1
     2 -4 -1 6;];
     
b = [-1;0;-3;1];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 300;

% Gauss-Seidel Method
for k = 1:k_max,
  x(:, k+1) = (D+L)\U*x(:,k) + (D+L)\b;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor

% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)

## Solucion iterativa:   -0.292588   0.042046  -0.629822   0.146077
## Numero de iteraciones: 23
## Error de aproximacion: 2.9262e-08

Ejercicio C y D

Escriba un código para el método iterativo SOR.

Solución utilizando algoritmo SOR

Primer sistema

A = [7 1 -1 2;
     1 8 0 -2;
     -1 0 4 -1
     2 -2 -1 6;];
     
b = [3;-5;4;-3];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 500;

% SOR method
K=[];
for w = 1:0.1:2,
for k = 1:k_max,
  T = inv(D-w*L)*(w*U+(1-w)*D);
  c = w*inv(D-w*L)*b;
  x(:, k+1) = T*x(:,k) + c;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor
% Factor de relajación
fprintf('Factor de relajacion: ') 
disp(w)
% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)
fprintf('\n') 
K(end+1)=k;
endfor

## Factor de relajacion: 1
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 15
## Error de aproximacion: 2.7794e-08
## 
## Factor de relajacion: 1.1000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 10
## Error de aproximacion: 5.6819e-08
## 
## Factor de relajacion: 1.2000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 14
## Error de aproximacion: 1.6329e-08
## 
## Factor de relajacion: 1.3000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 17
## Error de aproximacion: 3.3459e-08
## 
## Factor de relajacion: 1.4000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 22
## Error de aproximacion: 2.9455e-08
## 
## Factor de relajacion: 1.5000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 29
## Error de aproximacion: 2.3657e-08
## 
## Factor de relajacion: 1.6000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 39
## Error de aproximacion: 2.0421e-08
## 
## Factor de relajacion: 1.7000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 55
## Error de aproximacion: 2.0059e-08
## 
## Factor de relajacion: 1.8000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 86
## Error de aproximacion: 2.2426e-08
## 
## Factor de relajacion: 1.9000
## Solucion iterativa:    1.0000  -1.0000   1.0000  -1.0000
## Numero de iteraciones: 183
## Error de aproximacion: 1.6358e-08
## 
## Factor de relajacion: 2
## Solucion iterativa:   -0.078768  -0.871861   0.337966   0.386312
## Numero de iteraciones: 500
## Error de aproximacion: 3.0998

Segundo sistema

A = [7 3 -1 2;
     3 8 1 -4;
     -1 1 4 -1
     2 -4 -1 6;];
     
b = [-1;0;-3;1];

% Factorizamos la matriz de coeficientes
D = diag(diag(A));
L = -tril(A,-1);
U = -triu(A,1);

% Creamos un vector x para nuestra primera aproximación
x = zeros(size(b));

% Valores para la tolerancia y máximo de iteraciones
tol = sqrt(eps);
k_max = 500;

% SOR method
K=[];
for w = 1:0.1:2,
for k = 1:k_max,
  T = inv(D-w*L)*(w*U+(1-w)*D);
  c = w*inv(D-w*L)*b;
  x(:, k+1) = T*x(:,k) + c;
  if norm(x(:, k+1) - x(:,k)) < tol, break;
  endif
  er = norm(x(:, k+1) - x(:,k));
endfor
% Factor de relajación
fprintf('Factor de relajacion: ') 
disp(w)
% Solución iterativa
fprintf('Solucion iterativa: ') 
disp(transpose(x(:,k)))
% Número de iteraciones
fprintf('Numero de iteraciones: ') 
disp(k)
% Error de aproximación
fprintf('Error de aproximacion: ') 
disp(er)
fprintf('\n') 
K(end+1)=k;
endfor

## Factor de relajacion: 1
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 68
## Error de aproximacion: 1.5127e-08
## 
## Factor de relajacion: 1.1000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 54
## Error de aproximacion: 2.0446e-08
## 
## Factor de relajacion: 1.2000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 43
## Error de aproximacion: 1.6626e-08
## 
## Factor de relajacion: 1.3000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 31
## Error de aproximacion: 2.4399e-08
## 
## Factor de relajacion: 1.4000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 22
## Error de aproximacion: 3.2733e-08
## 
## Factor de relajacion: 1.5000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 29
## Error de aproximacion: 2.1949e-08
## 
## Factor de relajacion: 1.6000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 38
## Error de aproximacion: 2.3513e-08
## 
## Factor de relajacion: 1.7000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 54
## Error de aproximacion: 2.3015e-08
## 
## Factor de relajacion: 1.8000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 86
## Error de aproximacion: 1.4929e-08
## 
## Factor de relajacion: 1.9000
## Solucion iterativa:   -1.0000   1.0000  -1.0000   1.0000
## Numero de iteraciones: 184
## Error de aproximacion: 1.5418e-08
## 
## Factor de relajacion: 2
## Solucion iterativa:   -1.4158   1.3524  -1.9505   1.7627
## Numero de iteraciones: 500
## Error de aproximacion: 1.7006

Ejercicio E

Trace la gráfica del número de iteraciones para la convergencia contra los valores de w. ¿Qué valor de w da como resultado la convergencia más rápida?

“1er Sistema” “2do Sistema”

Para el 1er sistema de ecuaciones la convergencia más rápida se alcanzó con w = 1.1, con 10 iteraciones. Mientras que el 2do sistema requirió w = 1.4 , para 22 iteraciones.

Ejercicio F

Compare con los resultados obtenidos mediante los tres métodos iterativos.

En la siguiente tabla podemos ver la cantidad de iteraciones requerida para convergencia en cada uno de los tres métodos utilizados.

El método de Jacobi se muestra como el más lento
La diferencia entre utilizar Gauss-Seidel con o sin factor de relajación es beneficiosa ya que no es díficil agregar el factor w
Concluimos con que el método de Gauss-Seidel con factor de relajación fue el método más eficiente

	1er Sistema	2do Sistema
Jacobi	27	127
Gauss-Seidel	15	23
SOR	10	22