sistemas de ecuaciones lineales web viewservir de fuente de búsqueda a otros estudiantes que...

universidad eafit

Sistemas de Ecuaciones Lineales

Segunda Entrega

Melissa Arcila, Stefanía Giraldo, Manuela Piedrahita, Cristina Rodríguez

24 de septiembre de 2013

Presentado a: Gustavo Restrepo

CONTENIDO

P.1. Introducción2. Objetivos3. Conceptos de Algebra Lineal4. Métodos

4.1 Eliminación Gaussiana Simple4.1.1 Ejemplo4.1.2 Código

4.2 Eliminación Gaussiana con Pivoteo Parcial4.2.1 Ejemplo4.2.2 Código

4.3 Factorización LU4.3.1 Doolitle

4.3.1.1 Ejemplo4.3.1.2 Código

4.3.2 Croult4.3.2.1 Ejemplo4.3.2.2 Código

4.3.3 Cholesky4.3.3.1 Ejemplo4.3.3.2 Código

4.4 Método Iterativos4.4.1 Jacobi

4.4.1.1 Ejemplo4.4.1.2 Código

4.4.2 Gauss-Seidel4.4.2.1 Ejemplo4.4.2.2 Código

4.4.3 Método de SOR4.4.3.1 Ejemplo4.4.3.2 Código

4.5 Código Extra5. Ejemplos con Códigos en Octave6. Conclusiones7. Referencias

1. INTRODUCCIÓN

Los procesos numéricos es una rama de las matemáticas que utiliza algoritmos a través de números para la simulación de procesos de la vida diaria. Dichos procesos van desde el cálculo de los valores de una función, hasta la programación de una herramienta de simulación como CREO Parametric o SolidWorks.

La producción de este trabajo está enfocada a explicar los diversos métodos de solución de sistemas de ecuaciones lineales. Entre los métodos se encuentran el método de eliminación gaussiana simple y con pivoteo parcial, factorización LU que incluye los métodos de Doolitle, Croult y Cholesky, los métodos iterativos de Jacobi y Gauss-Seidel, y por último el método de SOR.

Adicionalmente, se explicaran algunos conceptos de algebra lineal que sirven como base para resolver estos métodos y para sacar conclusiones respecto a ellos.

2. OBJETIVOS

Fortalecer lo aprendido en clase por medio de la producción de este trabajo y de los códigos en el lenguaje de Octave.

Proveer diversos métodos que faciliten la solución de sistemas de ecuaciones lineales. Servir de fuente de búsqueda a otros estudiantes que requieran la información

suministrada.

3. CONCEPTOS DE ALGEBRA LINEAL

Con el fin de resolver de manera más fácil y rápida los sistemas de ecuaciones lineales y de hacer uso de los métodos que van a ser explicados a lo largo de este trabajo, es necesario recordar varios conceptos vistos en algebra lineal.Ellos son:

Matriz Diagonal : es una matriz donde todos los elementos situados por encima y por debajo de su diagonal principal son ceros.

Ilustración 1 - Matriz Diagonal

Matriz Identidad : es una matriz donde todos los elementos situados en la diagonal principal son unos (1), y donde además todos los elementos situados arriba y debajo de dicha diagonal son ceros.

Ilustración 2 - Matriz Identidad

Matriz Triangular Superior : es una matriz donde los elementos situados por debajo de la diagonal principal son ceros.

Ilustración 3 - Matriz triangular superior

Matriz Triangular Inferior : es una matriz donde todos los elementos situados por encima de la diagonal principal son ceros.

Ilustración 4 - Matriz triangular inferior

Matriz Simétrica : es una matriz cuadrada (donde i = j) que verifica que A = At.

Ilustración 5 - Matriz simétrica/transpuesta

Matriz Estrictamente y Diagonalmente Dominante (edd) : es una matriz en la cual los valores absolutos de los elementos de la diagonal principal, son estrictamente mayores que las sumas de los valores absolutos de los elementos restantes de las mismas filas.

(−4 2 12 −8 41 −1 6)Ilustración 6 - Matriz edd

Valores propios de una matriz : dado un vector c diferente de cero, se dice que c es un vector propio de A si existe un λ que pertenece a los reales tal que Ac= λc. λ se conoce como valor propio de A. Para hallar los vectores propios, se debe encontrar el polinomio característico

P ( λ )=|A− λI|=det (A−λI )Las raíces de P son los valores propios de la matriz A.

Matriz definida estrictamente positiva : una matriz es definida de esta manera si y solo si

a. La matriz A es simétricab. Todos los valores propios de A son reales positivos.

4. MÉTODOS

4.1 ELIMINACIÓN GAUSSIANA SIMPLE

En forma general el método de eliminación Gaussiana simple propone la eliminación progresiva de variables en el sistema de ecuaciones, hasta tener sólo una ecuación con una incógnita (matriz triangular superior), esto se logra a través de operaciones básicas llamadas operaciones de renglón. Al llegar a este punto se procede a encontrar la solución del sistema utilizando sustitución regresiva, es decir hasta obtener los valores de todas las variables.

Para qué un sistema se pueda resolver utilizando eliminación Gaussiana Simple se debe tener en cuenta:

o La matriz debe ser nxn, es decir, el número de incógnitas debe ser igual al número de ecuaciones.

o Los coeficientes de la diagonal, aii, deben ser diferentes de cero, pues si algún pivote se vuelve cero en el proceso de resolución, la eliminación hacia adelante no procederá.

Operaciones básicas de renglón:a) Multiplicar o dividir un renglón por un número distinto de cero.b) Sumar el múltiplo de otro renglón a otro renglón.c) Intercambiar dos renglones

Estas operaciones lo que permiten es obtener ecuaciones equivalentes al sistema quesean válidas y que faciliten el proceso de solución.

4.1.1 EJEMPLO

Resolver el siguiente sistema de ecuaciones

x +2 y +3 z4 x +5 y +6 z3 x + y +2 z

¿9¿24¿ 4

(1 2 34 5 63 1 2

⋮9244 ) (1 2 3

0 −3 −60 −5 −11

⋮9

−12−23) (

1 2 30 −3 −60 0 3

⋮9

−12−3 )

Al realizar sustitución regresiva obtenemos:

F3f3 – 3f1

F2f2 – 4f1 F3f3 – (-5/-3)f2

z = -1y = ((-12+6(-1))/-3) = 6x = 9 – 2(6) -3(-1) = 0

4.1.2 CÓDIGO

function [ret] = Eliminacion_Gaussiana_Simple(A,b)

disp('Metodo de Eliminacion Gaussiana Simple');

%A=input('Ingrese la matriz A en []: ');%b=input('Ingrese el vector b en []: ');Ab=[A b]; %Matriz aumentada n=length(b); %Tamaño de la matriz A

for c=1:n-1 %Numero de etapas a realizarfprintf(' \nEtapa %g \n',c)for f=c+1:n %Inicia desde fila 2 para convertir la matriz en triang superior

if Ab(c,c)~=0 %La eliminacion gaussiana se puede realizar mientras los elementos de la diagonal sean diferentes de cero

mult=Ab(f,c)/Ab(c,c);

elsedisp('No se puede continuar debido a Division por cero')

end

for j=1:n+1 %intercambia todas las columnas de la fila de la matriz aumentada

Ab(f,j)=Ab(f,j)-mult*Ab(c,j);endAb %matriz triangular superiorend

end

fprintf('\nMatriz triangular superior:\n\n')disp(Ab) %Se muestra la matriz triangular superior obtenida

%Sustitucion regresivafor i=n:-1:1

suma=0;for j=i+1:n

suma=suma+Ab(i,j)*x(j,1);end

x(i,1)=(Ab(i,n+1)-suma)/Ab(i,i);enddisp('El vector solucion x es: ')disp(x)

4.2 ELIMINACIÓN GAUSSIANA CON PIVOTEO PARCIAL

Este método es una modificación a la Eliminación Gaussiana Simple que permite, utilizando intercambió de filas, evitar que los elementos de la diagonal sean cero y se pueda encontrar solución al sistema.El método busca encontrar el coeficiente más grande de la columna y con el intercambio de filas convertirlo en el elemento pivote, y luego se procede con el método de eliminación Gaussiana Simple para obtener los valores de todas las variables.

4.2.1 EJEMPLO

Resolver el siguiente sistema de ecuaciones

−2 x + y +5 z4 x −8 y +z4 x − y +z

¿15¿−21¿7

(−2 1 54 −8 14 −1 1

⋮15

−217 ) ( 4 −1 1

4 −8 1−2 1 5

⋮7

−2115 )

Ya tenemos que la matriz es estrictamente diagonalmente dominante, y se procede de igual forma que en el método de Eliminación Gaussiana Simple

( 4 −1 14 −8 1

−2 1 5⋮7

−2115 ) ( 1 −0.25 0.25

4 −8 1−2 1 5

⋮1.75−2115 ) (1 −0.25 0.25

0 −7 00 0.5 5.5

⋮1.75−2818.5)

F1f1 <–> f3

F2f2 – 4f1

F3f3 + 2f1

(1 −0.25 0.250 1 00 0.5 5.5

⋮1.75418.5) (1 −0.25 0.25

0 1 00 0 5.5

⋮1.75416.5)

Al realizar sustitución regresiva obtenemos:z = 16.5/5.5 = 3y = 4x = 1.75 – (-0.25)(4) – 0.25(3) = 2

4.2.2 CÓDIGO

function [ret] = Pivoteo_Parcial1(A,b)

disp('Metodo de Eliminacion Gaussiana con Pivoteo Parcial');%A=input('Ingrese la matriz A en []: ');%b=input('Ingrese el vector b en []: ');Ab = 0;Ab = [A b]; %Matriz aumentada[m,n]=size(Ab);

for c=1:m-1p=c; %se hace la fila c como la fila donde esta el mas grande de la columnabig=abs(Ab(c,c)); %se hace el elemento de la diagonal como el mas grande

de la columnafprintf(' \nEtapa %g \n',c)for f=c+1:m % se compara el elemento de la diag con los otros de la

columna aux=abs(Ab(f,c)); %se almacena en una variable auxiliar el

valor absoluto de las demas filasif aux>big %si auxiliar es mayor que el elemento de

la diagonal entonces este es el mas grandebig=aux;p=f; %se almacena la fila del auxil

endend

if p~=c % se mira si el mayor esta en la diagonalfor h=c:m+1

aux=Ab(c,h); % se mueve toda la fila a la fila de la diagonal

F2f2 * -1/7 F3f3 - 0.5f2

Ab(c,h)=Ab(p,h);Ab(p,h)=aux;

endend

for f=c+1:m % se va a llevar la matriz a triang superiorif Ab(c,c)~=0

mult=Ab(f,c)/Ab(c,c);else

disp('No se puede continuar debido a Division por cero')endfor j=c:m+1

Ab(f,j)=Ab(f,j)-mult*Ab(c,j);endAb

endend

fprintf('\nMatriz triangular superior:\n\n')disp(Ab)

%Sustitucion regresiva

for j=m:-1:1 % Un for j desde el tamaño de la matriz (m) con incremento de -1 hasta 1 (PARA UNA SUSTITUCION REGRESIVA). sum=0; % Contador de suma for i=j+1:1:m sum=sum+Ab(j,i)*X(i,1); end if Ab(j,j)~=0; % Controla si existe una division por cero X(j,1)=(Ab(j,m+1)-sum)/Ab(j,j); % Calcula los valores de las (x) por medio de una sustitucion regresiva (SOLUCION DEL SISTEMA) else disp('Division por cero') endend

disp('El vector solucion x es: ')disp(X)

4.3 FACTORIZACIÓN LU

Es una forma de factorización de una matriz como el producto de una matriz triangular inferior y una superior. Esta descomposición se usa en el análisis numérico para resolver sistemas de ecuaciones (más eficientemente) o encontrar las matrices inversas.

Su principal objetivo es solucionar el sistema Ax = b, donde se debe supones que existen matrices L y U donde la primera es triangular inferior y la segunda triangular superior tales que:

A = Lnxn Unxn

Dicho sistema se debe resolver de la siguiente manera:Ax = b

LUx = b donde z = UxLz = b

El último sistema se puede resolver al utilizar sustitución progresiva para encontrar el valor de z. Luego se debe resolver el sistema Ux = z utilizando sustitución regresiva para hallar x. Lo anterior convierte el problema de resolver Ax = b en dos problemas más sencillos.

Para aplicar el método de factorización LU se deben utilizar estrategias para encontrar las matrices L y U. Dichas estrategias se conocen como los métodos de Doolittle, Crout y Cholesky.

4.3.1 DOOLITTLElii=1donde i=1 ,2 ,3

4.3.1.1 EJEMPLO

Se tiene el siguiente sistema Ax=b:

(1 5 75 2 07 0 −3)(

x1x2x3)=(1374 )

Hallar los valores de L y U factorizando por Doolittle.

L=(l11 0 0l21 l22 0l31 l32 l33)U=(u11 u12 u13

0 u22 u230 0 u33)

(1 5 75 2 07 0 −3)=( 1 0 0

l21 1 0l31 l32 1)(

u11 u12 u130 u22 u230 0 u33)

1 = U11 x 1 U11 = 15 = U12 x 1 U12 = 57 = U13 x 1 U13 = 75 = 1 x L21 L21 = 5

2 = (5 x 5) + U22 U22 = -230 = (5 x 7) + U23 U23 = -35

7 = L31 L31 = 70 = (7 x 5) + (L32 x -23) L32 = 35/23

-3 = (7 x 7) + (35/23 x -35) + U33 U33 = 29/23

L=(1 0 05 1 07 35/23 1)U=(1 5 7

0 −23 −350 0 29/23)

Ahora se debe encontrar Lz = b:

(1 0 05 1 07 35/23 1)(

z1z2z3)=(1374 )

Se debe hacer sustitución progresiva para resolver el sistema:Z1 = 13

Z2 = 7 - (5 x 13) z2 = -58Z3 = 4 – (13 x 7) - (35/23 x -58) Z3 = 29/23

A continuación se debe resolver el sistema Ux = z haciendo sustitución regresiva:

(1 5 70 −23 −350 0 29/23)(

x1x2x3)=( 13

−5829 /23)

X3 = 1X2 = (-58 + 35)/-23 x2 = 1

X1 = 13 – 7 – 5 x1 = 1

El vector solución al problema es:X = (1 1 1)´

4.3.1.2 CÓDIGO

function [L,U] = Doolittle(A,b);

n=size(A);%Tamaño de AL=eye(n);%Matriz de 1U=eye(n);%Matriz de 1cond(A)%verificar si esta bien condicionada la matriz

% halla la fila 1 de Ufor j = 1:n U(1,j) = A(1,j);end% halla columna 1 de Lfor i = 1:n L(i,1) = A(i,1)/U(1,1);endfor k=2:n % Se hallan las demas filas desde la 2

for j=k:n Acumulador2 = 0; %Se inicializa el acumulador en cero para

el despeje de Ufor p=1:k-1

Acumulador2 = Acumulador2 + L(k,p)*U(p,j); % Acumulador es como el multiplicador

end U(k,j) = (A(k,j) - Acumulador2);

end for i= k:n

Acumulador = 0; %Se inicializa el acumulador en cero para el despeje de L

for p=1:k-1 Acumulador = Acumulador + L(i,p)*U(p,k);

end L(i,k) = (A(i,k) - Acumulador)/U(k,k);

end end

disp('U=') disp (U) disp('L=') disp (L) disp('L*U=')disp(L*U)

% se inicia la sustitucion progresiva para hallar Zfor i=1:n Acumulador3 = 0; for p = 1:i-1 Acumulador3=Acumulador3+L(i,p)*Z(p,1); end Z(i,1)=(b(i,1)-Acumulador3)/L(i,i);end

disp('Z=');disp(Z)

% se inicia la sustitucion regresiva para hallar Xfor i=n:-1:1 Acumulador4=0; for p=i+1:n Acumulador4=Acumulador4+U(i,p)*X(p,1); end X(i,1)=(Z(i,1)-Acumulador4)/U(i,i);end

disp('El vector solución al problema es :')disp(X)

endfunction

4.3.2 CROUTU ii=1donde i=1 ,2 ,3

4.3.2.1 EJEMPLO

Se tiene el mismo sistema Ax=b que en el ejemplo anterior:

(1 5 75 2 07 0 −3)(

x1x2x3)=(1374 )

Hallar los valores de L y U factorizando por Croult.

L=(l11 0 0l21 l22 0l31 l32 l33)U=(u11 u12 u13

0 u22 u230 0 u33)

(1 5 75 2 07 0 −3)=( l11 0 0

l21 l22 0l31 l32 l33)(

1 u12 u130 1 u230 0 1 )

1 = L11

5 = U12

7 = U13

5 = L21

2 = (5 x 5) + L22 L22 = -230 = (5 x 7) + (-23 x U23) U23 = 35/23

7 = L31

0 = (5 x 7) + (L32 x 1) L32 = -35-3 = (7 x 7) + (-35 x 35/29) + L33 L33 = 29/23

L=(1 0 05 −23 07 −35 29 /23)U=(1 5 7

0 1 35/230 0 1 )

Ahora se debe encontrar Lz = b:

(1 0 05 −23 07 −35 29/23)(

z1z2z3)=(1374 )


Z2 = (7 – (13 x 5))/-23 z2 = 58/23Z3 = (4 – (13 x 7) – (-35 x 58/23))/(29/23) z3 = 1


(1 5 70 1 35/230 0 1 )(x1x2x3)=( 13

58 /231 )

X3 = 1X2 = 58/23 – 35/23 x2 = 1

X1 = 13 – 5 – 7 x1 = 1


4.3.2.2 CÓDIGO

function [L,U] = Crout(A,b);

n=size(A);%Tamaño de AL=eye(n);%Matriz de 1U=eye(n);%Matriz de 1cond(A);%verificar si esta bien condicionada la matriz

% halla la fila 1 de Lfor i = 1:n L(i,1) = A(i,1);

end% halla columna 1 de Ufor j = 1:n U(1,j) = A(1,j)/L(1,1);endfor k=2:n

for i=k:n Acumulador2 = 0; %Se inicializa el acumulador en cero para

el despeje de Lfor p=1:k-1

Acumulador2 = Acumulador2 + L(i,p)*U(p,k); % Acumulador es como el multiplicador

end L(i,k) = (A(i,k) - Acumulador2);

end for j= k:n

Acumulador = 0; %Se inicializa el acumulador en cero para el despeje de U

for p=1:k-1 Acumulador = Acumulador + L(k,p)*U(p,j);

end U(k,j) = (A(k,j) - Acumulador)/L(k,k);

end end

disp('U=') disp (U) disp('L=') disp (L) disp('L*U=')disp(L*U)

%se inicia la sustitucion progresiva para hallar Zfor i=1:n Acumulador3 = 0; for p = 1:i-1 Acumulador3=Acumulador3+L(i,p)*Z(p,1);

end Z(i,1)=(b(i,1)-Acumulador3)/L(i,i);end

disp('Z=');disp(Z)

% se inicia la sustitucion regresiva para hallar Xfor i=n:-1:1 Acumulador4=0; for p=i+1:n Acumulador4=Acumulador4+U(i,p)*X(p,1); end X(i,1)=(Z(i,1)-Acumulador4)/U(i,i);end

disp('El vector solución al problema es :')disp(X)

endfunction

4.3.3 CHOLESKYlii=U iidonde i=1,2 ,3

Adicionalmente, para el método de Cholesky existe un teorema que es el siguiente:

Si A es definida positiva existe L tal que:A=LLt Factorización Cholesky

L y Lt Son entradas reales

4.3.3.1 EJEMPLO

A continuación se resolverá el mismo ejercicio que en los métodos de Doolittle y Croult. Dado el siguiente sistema Ax=b:

(1 5 75 2 07 0 −3)(

x1x2x3)=(1374 )

Hallar los valores de L y U factorizando por el método de Cholesky.

L=(l11 0 0l21 l22 0l31 l32 l33)U=(u11 u12 u13

0 u22 u230 0 u33)

(1 5 75 2 07 0 −3)=( l11 0 0

l21 l22 0l31 l32 l33)(

l11 u12 u130 l22 u230 0 l33 )

1 = L112 L11 = 1

5 = U12

7 = U13

5 = L21

2 = (5 x 5) + L222 L22 = (-23)1/2

0 = (5 x 7) + ((-8)1/2 x U23) U23 = -35/(-23)1/2

7 = L31

0 = (5 x 7) + (L32 x (-23)1/2) L32 = -35/(-23)1/2

-3 = (7 x 7) + (-1225/23) + L332 (667)1/2/23

L=(1 0 05 2√−23 0

7 −352√−23

2√66723 )U=(

1 5 7

0 2√−23 −352√−23

0 02√66723

)Ahora se debe encontrar Lz = b:

(1 0 05 2√−23 0

7 −352√−23

2√66723 )( z1z2z3)=(1374 )


Z2 = (7 – (13 x 5))/(-23)1/2 z2 = -58/(-23)1/2

Z3 = (4 – (13 x 7) – (-35/(-23)1/2 x -58/(-23)1/2)/((667)1/2/23) z3 = (667)1/2/23


(1 5 7

0 2√−23 −352√−23

0 02√66723

)( x1x2x3)=( 13−58/ 2√−232√667/23 )

X3 = 1X2 = (-58/(-23)1/2 – (-35/(-23)1/2))/(-23)1/2 x2 = 1

X1 = 13 – 5 – 7 x1 = 1


4.3.3.2 CÓDIGO

function [ret] = cholesky(A,b) %A=input("ingrese matriz A: "); %se ingresa la matriz con corchetes%b=input("ingrese vector b: "); %se ingresa el vector b en transpuestan=size(A);%Tamaño de AL=eye(n);%Matriz de 1U=eye(n);%Matriz de 1cond(A);%verificar si esta bien condicionada la matriz

for k=1:n Acumulador = 0; %Este es el acumulador de las diagonales

for p=1:k-1 Acumulador = Acumulador + L(k,p)*U(p,k);

end L(k,k)= sqrt(A(k,k)- Acumulador); % Este es el despeje de las

diagonales en el que usan raiz cuadradaU(k,k) = L(k,k); %Llenando las diagonales tanto de U como de L

for i=k+1:n Acumulador2 = 0;

for p=1:k-1 Acumulador2= Acumulador2 +

L(i,p)*U(p,k); %Despeje que se hace en ecuaciones para Lend

L(i,k) = (A(i,k)- Acumulador2)/L(k,k); %llenando Lend for j= k+1:n

Acumulador3 = 0; for p = 1:k-1

Acumulador3 = Acumulador3 + L(k,p)*U(p,j); %Despeje que se hace en ecuaciones para U

end U(k,j)= (A(k,j)- Acumulador3)/L(k,k); %llenando U

end end

disp ('L='); disp(L); disp('U=') ;disp (U); disp('L*U=')disp(L*U)

% se inicia la sustitucion progresiva para hallar Zfor i=1:n Acumulador4 = 0; for p = 1:i-1 Acumulador4=Acumulador4+L(i,p)*Z(p,1); end Z(i,1)=(b(i,1)-Acumulador4)/L(i,i);end

disp('Z=');disp(Z);

% se inicia la sustitucion regresiva para hallar Xfor i=n:-1:1

Acumulador5=0; for p=i+1:n Acumulador5=Acumulador5+U(i,p)*X(p,1); end X(i,1)=(Z(i,1)-Acumulador5)/U(i,i);end

disp('El vector solución al problema es = ')disp(X)

endfunction

4.4 MÉTODOS ITERATIVOS

Estos métodos iterativos empiezan con una aproximación inicial x (0)=[ x1(0), x2(0), … xn(0)]t y mediante alguna técnica se genera una sucesión {x(k)}k=0 donde lo ideal será que

limk→∞

‖x(k)−x‖=0❑↔limk→∞

x(k)=x

Con x la solucion del sistema Ax=b.

Cabe resaltar que para la solución matricial de los métodos iterativos de Jacobi y Gauss – Seidel se deben cumplir tres teoremas.

Teorema 1Cuando el radio espectral de una matriz T de Jacobi o Gauss – Seidel es menor que uno, el método iterativo genera una sucesión de vectores que converge sin importar la aproximación inicial.

Teorema 2Si para alguna norma matricial, la norma de T es menor que uno, entonces los métodos de Jacobi y Gauss – Seidel convergen sin importar la aproximación inicial. Si no se cumple el teorema, no implica que estos no converjan.

Teorema 3Dado el sistema Ax=b, si se tiene que A es e.d.d., entonces tanto el método de Jacobi como el de Gauss – Seidel convergen.

4.4.1 JACOBI

El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi. Su método consiste en usar fórmulas como iteración de punto fijo.La sucesión se construye descomponiendo la matriz del sistema A en la forma siguiente:

A = D – L – UDonde D es una matriz diagonal, L una matriz triangular inferior y U una matriz triangular superior.Su forma general con A∈Rnxn , x∈ Rn ,b∈ Rn es la siguiente:

x i(k +1)=

bi− ∑i=1 , j ≠i

n

aij x j(k )

a iicon i=1 ,2 ,3…,n

Su forma matricial parte del sistema Ax=b donde A, D – L, y D son invertibles:

(D – L – U)x = bDx – (L + U)x = bDx = (L + U)x + b

X = D-1(L + U)x + D-1 bX(k+1) = D-1 (L + U) x(k) + D-1 b

Donde Tj = D-1 (L + U) y Cj = D-1

Si en algún momento x(k+1) = x(k) , entonces x(k) es la solución al sistema.

4.4.1.1 EJEMPLO

Con el vector inicial x = (0 0 0)’, resolver el siguiente sistema de ecuaciones:

6x1 + 2x2 + x3 = 22-x1 + 8x2 + 2x3 = 30X1 – x2 + 6x3 = 23

Se despejan las variables x de cada una de las ecuaciones:X1 = (22 – 2x2 – x3)/6X2 = (30 + x1 – 2x3)/8X3 = (23 – x1 + x2)/6

Para el vector inicial x, los valores de x1, x2, x3 son 3.66, 3.75, 3.83 respectivamente.Se reemplazan estos nuevos valores de x en las ecuaciones obtenidas e iteramos:

Iteración X1 X2 X3

0 0 0 01 3.67 3.75 3.832 1.78 3.25 3.853 1.94 3.01 4.084 1.98 2.97 4.015 2.01 3.00 4.006 2.00 3.00 4.00

Se puede observar que a partir de la sexta iteración se presenta convergencia.

4.4.1.2 CÓDIGO

function [ret] = Jacobi(A,b,x,tol,iter);

n=size(A);%Tamaño de Acond(A)%verificar si esta bien condicionada la matriz

D=diag(diag(A)); %el programa encuentra la diagonal de AL=D-tril(A); %el programa encuentra la matriz trinagular inferirorU=D-triu(A); %el programa encuentra la matriz triangular superior

Tj=D^-1*(L+U); %encuentra la matriz Tj usando D L y Urho=max(abs(eig(Tj))); %encuentra el valor del radio espectral con la matriz Tj

if rho>1 %si el re>1 el metodo no converge disp('radio espectral mayor que 1'); disp('el metodo no converge');end

C=D^-1*b; %encunetre el valor de la constante Cji=0;error=tol+1;

while error>tol && i<iter %mientras error>tol y i<iter ejecute la formula iterativa xi=Tj*x+C; %formula iterativa i=i+1; %incrmente el valor del contador error=norm(xi-x); x=xi; %se tiene un nuevo valor de x para continuar hastra que encuentre solucion p(i)=error; %se crea un nuevo vector p, para cargar los valores del errorend

itermax = [1:i]; %se crea el vector iteraciones para poder graficar el errorplot(itermax,p,'-m') %grafica de los errrordisp('aproximacion xi') %muestre la aproximacion xidisp(xi)disp('iteraciones realizadas') %muestre las iteraciones que realizo hasta que convergiodisp(i)disp('error') %muestre el error obtenido por las operacionesdisp(error)disp('Radio Espectral')disp(rho) %muestre el radio espectraldisp('Matriz Tj')disp(Tj) %muestra la matriz Tj

endfunction

4.4.2 GAUSS-SEIDEL

El método de Gauss – Seidel es muy semejante al método de Jacobi. Mientras que en el segundo se utiliza el valor de las incognitas para determinar una

nueva aproximación, en el primero se utilizan los valores de las incógnitas recién calculadas en la misma iteración y no en la siguiente.Su forma general es la siguiente:

x i(k +1)=b i−¿¿

En su forma matricial, la sucesión se construye descomponiendo la matriz del sistema A en la forma siguiente:

A = D – L – UDonde D es una matriz diagonal, L una matriz triangular inferior y U una matriz triangular superior.Partiendo de Ax=b se tiene:

(D – L – U)x = b(D – L)x – Ux = b(D – L)x = Ux + b

X = (D – L)-1 Ux + (D – L)-1 bDonde Tg = (D – L)-1 U y Cg = (D – L)-1 b

4.4.2.1 EJEMPLO

Del ejemplo anterior, con el vector inicial x = (0 0 0)’, resolver el siguiente sistema de ecuaciones:

6x1 + 2x2 + x3 = 22-x1 + 8x2 + 2x3 = 30X1 – x2 + 6x3 = 23

Se despejan las variables x de cada una de las ecuaciones:X1 = (22 – 2x2 – x3)/6X2 = (30 + x1 – 2x3)/8X3 = (23 – x1 + x2)/6

Al implementar el vector inicial, se halla el valor de la primera incógnita:X1 = (22 – 2x2 – x3)/6

X1 = (22 – 2(0) – (0))/6X1 = 3.66

Se halla la segunda incógnita empleando el valor hallado para x1.X2 = (30 + x1 – 2x3)/8

X2 = (30 + (3.66) – 2(0))/8X2 = 4.21

De igual forma, se halla la tercera incógnita empleando los valores de x1 y x2.

X3 = (23 – x1 + x2)/6X3 = (23 – (3.66) + (4.21))/6

X3 = 3.925A continuación se debe iterar hasta que los valores de las incógnitas sean homogéneos:

Iteración X1 X2 X3

0 0 0 01 3.67 4.21 3.922 1.61 2.97 4.063 2.00 2.98 4.004 2.01 3.00 4.005 2.00 3.00 4.006 2.00 3.00 4.00

Se puede observar que este método converge más rápido que el método de Jacobi explicado anteriormente.

4.4.2.2 CÓDIGO

function [ret] = GaussSeidel(A,b,x,tol,iter);

n=size(A);%Tamaño de Acond(A);%verificar si esta bien condicionada la matriz


Tg=(D-L)^-1*U; %encuentra la matriz Tg usando D L y Urho=max(abs(eig(Tg))); %encuentra el valor del radio espectral con la matriz Tg

if rho>1 %si el re>1 el metodo no converge disp('radio espectral mayor que 1'); disp('el metodo no converge');

end

C=(D-L)^-1*b; %encuentre el valor de la constante Cgi=0;error=tol+1;

while error>tol && i<iter %mientras error>tol y i<iter ejecute la formula iterativa xi=Tg*x+C; %formula iterativa i=i+1; %incrmente el valor del contador error=norm(xi-x); x=xi; %se tiene un nuevo valor de x para continuar hastra que encuentre solucion p(i)=error; %se crea un nuevo vector p, para cargar los valores del errorend

itermax = [1:i]; %se crea el vector iteraciones para poder graficar el error. plot(itermax,p,'-m') %grafica de los errror.disp('aproximacion xi') %muestre la aproximacion xidisp(xi)disp('iteraciones realizadas') %muestre las iteraciones que realizo hasta que convergiodisp(i)disp('error') %muestre el error obtenido por las operacionesdisp(error)disp('Radio Espectral')disp(rho) %muestre el radio espectraldisp('Matriz Tg')disp(Tg) %muestra la matriz Tgendfunction

4.4.3 GAUSS – SEIDEL CON RELAJACIÓN (MÉTODO DE SOR)

Luego de calcular un nuevo valor de x por el método iterativo de Gauss – Seidel, ese valor se modifica por un promedio ponderado de los resultados de

las iteraciones hechas con Gauss – Seidel. Lo anterior se conoce como la técnica de SOR. Su forma general está dada de la siguiente manera:

x i(k)=w [ 1a ii

(bi−∑j=1

i−1

x j(k )− ∑

j=i+1

n

x j(k−1))]+ (1−w ) x i

(k−1 )

Para hallar los valores de x en el sistema de ecuaciones, se debe emplear la función fundamental:

Xi(k) = (1 – w) xi

(k) + w xi(k-1)

Se debe reemplazar w por un valor del intervalo abierto (0, 2), para obtener un Nuevo sistema de ecuaciones. Luego se deben reemplazar los valores iniciales con el fin de empezar a iterar y hallar un error menos a la tolerancia deseada.

Nota 1Si w = 1, el método es el mismo Gauss – Seidel. Si w pertence (0, 1), se tendrá un método de subrelajación que será útil cuando Gauss – Seidel no converja.

Nota 2Si w pertenece (0, 2) se tendrá un método de sobrerelajación que será útil para acelerar la convergencia de Gauss – Seidel.

Su forma matricial está dada de la siguiente manera:x (k )=¿

con A=D−L−U

TeoremaSi A es definida positiva estrictamente, entonces los método de SOR generan una sucesión {x(k)}k=0

∞ que converge para cualquier elección de w entre 0 y 2; y para todo x(0).Hay que tener en cuenta que w = 0 no se toma debido a que no se obtendrían mejoras a la aproximación inicial; tampoco se toma w≥2 ya que la sucesión diverge.

4.4.3.1 EJEMPLO

Se debe resolver el sistema planteado en los dos métodos anteriores, con el mismo vector inicial y w = 1.25, empleando el método de SOR.El sistema de ecuaciones queda de la siguiente manera:

X1 = (22*w – 2x2*w – x3*w + 6x1*(1-w))/6X2 = (30*w + x1*w – 2x3*w + 8x2(1-w))/8X3 = (23*w – x1*w + x2*w + 6x3*(1-w))/6

Al reemplazar el valor de w dado en el sistema de ecuaciones, queda lo siguiente:

X1 = (22*(1.25) – 2x2*(1.25) – x3*(1.25) + 6x1*(1 – 1.25))/6X2 = (30*(1.25) + x1*(1.25) – 2x3*(1.25) + 8x2(1 – 1.25))/8X3 = (23*(1.25) – x1*(1.25) + x2*(1.25) + 6x3*(1 – 1.25))/6

Al resolver, el sistema queda:X1 = (27.5 – 2.5x2 – 1.25x3 + 1.5x1)/6X2 = (37.5 + 1.25x1 – 2.5x3 + 2x2)/8

X3 = (28.75 – 1.25x1 + 1.25x2 + 1.5x3)/6Al emplear el valor inicial en la primera ecuación, se tiene que x 1= 4.58. Realizando el mismo procedimiento para x2 y x3 queda lo siguiente:

X2 = (37.5 + 1.25(4.58) – 2.5(0) + 2(0))/8X2= 5.40

X3 = (28.75 – 1.25(4.58) + 1.25(5.40) + 1.5(0))/6X3= 4.962

Iterando hasta conseguir la tolerancia deseada se tiene:

Iteración X1 X2 X3

0 0 0 01 4.58 5.40 4.962 0.15 1.81 3.903 2.98 3.48 3.924 1.57 2.84 4.075 2.16 3.04 3.966 1.95 3.00 4.027 2.01 3.00 3.998 2.00 3.00 4.00

Luego de resolver el mismo ejercicio con los tres métodos iterativos, se puede concluir que, para este caso, el método de convergencia más rápida es Gauss – Seidel.

4.4.3.2 CÓDIGO

function [ret] = SOR(A,b,x,w,tol,iter);

n=size(A);%Tamaño de Acond(A)%verificar si esta bien condicionada la matriz


T=(D-w*L)^-1*((1-w)*D+w*U); %encuentra la matriz T usando D L y Urho=max(abs(eig(T))); %encuentra el valor del radio espectral con la matriz T

if rho>1 %si el re>1 el metodo no converge disp('radio espectral mayor que 1'); disp('el metodo no converge');end

C=w*(D-w*L)^-1*b; %encunetre el valor de la constante Ci=0;error=tol+1;

while error>tol && i<iter %mientras error>tol y i<iter ejecute la formula iterativa xi=T*x+C; %formula iterativa i=i+1; %incrmente el valor del contador error=norm(xi-x); x=xi; %se tiene un nuevo valor de x para continuar hastra que encuentre solucion p(i)=error; %se crea un nuevo vector p, para cargar los valores del errorend

itermax = [1:i]; %se crea el vector iteraciones para poder graficar el error. plot(itermax,p,'-m') %grafica de los errror.

disp('aproximacion xi') %muestre la aproximacion xidisp(xi)disp('iteraciones realizadas') %muestre las iteraciones que realizo hasta que convergiodisp(i)disp('error') %muestre el error obtenido por las operacionesdisp(error)disp('Radio Espectral')disp(rho) %muestre el radio espectraldisp('Matriz T')disp(T) %muestra la matriz T

endfunction4.5 CÓDIGOS EXTRA

A continuación se muestra el código de eliminación gaussiana con pivoteo total con el fin de brindar al lector mayores oportunidades para resolver sistemas de ecuaciones lineales.

function [ret] = Eliminacion_Gaussiana_P_T(A,b)

disp('ELIMINACION GAUSSIANA CON PIVOTEO TOTAL: ');%Muestra una respuesta con mayor

ecxatitud y muestra la matriz aumentada[n,m]=size(A); % Tamaño de la matriz AAb=[A b]; % Matriz aumentada [Ab].

fprintf('La Matriz aumentada es:\n ');disp(Ab) % Muestra la matriz aumentadaif n==m % si la matriz es cuadrada for i=1:n marca(i)=i; %Almacena posiciones de las variables x en cada cambio

end for k=1:(n-1) fprintf('\n ETAPA %g= ',k) mayor=0; %Hace el mayor de la fila igual a cero filam=k; %La fila k contiene el numero mayor columnam=k; %Hace la columna k como la que tiene el numero mayor de toda la matriz for p=k:n for r=k:n if mayor<abs(Ab(p,r)) %Se busca el numero mayor por toda la matriz mayor=abs(Ab(p,r)); %Hace como el mayor el numero encontrado filam=p; %cambio de fila del numero mayor columnam=r; %cambio de columna del numero mayor end end end if mayor ==0 fprintf(' El sistema tiene infinitas soluciones ') break %se interrumpe el programa con la instruccion break, ya que %si mayor=0, mas adelante se obtiene una division por cero.

else if filam ~= k %si el mayor no esta en la fila k for j=1:(n+1) aux=Ab(k,j); %Se utiliza una variable auxiliar para intercambio de fila Ab(k,j)=Ab(filam,j); Ab(filam,j)=aux; end

end if columnam ~= k %si el mayor no esta en la columna k for i=1:n aux=Ab(i,k); %Se utiliza una variable auxiliar para intercambio de columna Ab(i,k)=Ab(i,columnam); Ab(i,columnam)=aux; end aux = marca(k); %Se utiliza una variable auxiliar para intercambio de variables marca(k)= marca(columnam); marca(columnam)=aux; end end fprintf('Matriz correspondiente a la etapa:\n'); disp(Ab) fprintf('\nMultiplicadores:\n'); for i=(k+1):n mult(i,k)=Ab(i,k)/Ab(k,k); %Multiplicadores de cada etapa fprintf('mult(%g,%g)=',i,k) disp(mult(i,k)); for j=k:(n+1) Ab(i,j)= Ab(i,j) - mult(i,k)*Ab(k,j); %Formula para convertir fila end end fprintf('\nLa matriz correspondiente a esta etapa es:\n ') disp(Ab) end fprintf('\nVector final de marcas:\n ') marca(columnam)=aux %Sustitucion regresiva

for i=n:-1:1 suma=0; for p=(i+1):n suma = suma + Ab(i,p)*X(p);

end X(i)=(Ab(i,n+1)-suma)/Ab(i,i); end %la siguiente parte del programa ordena las varibles, tomando en %cuenta la marca final y los retoma con su coeficiente a la marca %inicial for i=1:n for j=1:n if marca(j)==i k=j; end end aux=X(k); %para poder intercambiar las variables, se utiliza una variable auxiliar. X(k)=X(i); X(i)=aux; aux=marca(k); %para poder intercambiar las variables, se utiliza una variable auxiliar. marca(k)=marca(i); marca(i)=aux; endelse %En caso de que la matriz no sea cuadrada fprintf('No se puede realizar debido a que la matriz no es cuadrada ');endfprintf(' SOLUCION: ');fprintf('\nLa matriz final es:\n ');Abfprintf('\nLa solucion del sistema es:\n ');

%Muestra los resultadosfor i=1:n Xi=X(1,i); fprintf('\n X%g= ',i) disp(Xi);end

5. EJEMPLOS CON CÓDIGOS EN OCTAVE

Ejemplo Eliminacion Gaussiana

A=[1 5 75 2 07 0 −3 ] b=[1374 ]

Eliminación Gaussiana Simple:

Eliminación Gaussiana Simple con Pivoteo Parcial:

Eliminación Gaussiana simple con Pivoteo Total

En este sistema de ecuaciones se puede observar que al resolverlo por cualquiera de los métodos de eliminación gaussiana ya sea con pivoteo o sin pivoteo, surgen dos etapas

en el desarrollo de los métodos y las soluciones obtenidas es igual en cualquiera de los tres.

Ejemplo Factorización LU de matrices

A=[ 6 2 1−1 8 21 −1 6] b=[223023]

Doolittle:

Crout

Cholesky

En este caso se evidencia como los métodos para factorizar matrices son útiles para resolver sistemas de ecuaciones por medio de las matrices L y U, y se obtiene una solución independientemente del método de factorización escogido (Doolittle, Crout o Cholesky).

Ejemplo Métodos iterativos

A=[ 6 2 1−1 8 21 −1 6] b=[223023] x(0)=[000] tolerancia=5∗10−5

iteraciones=100

Jacobi

Gauss Seidel

Gauss Seidel con Relajación:

W= 1.2

El método de Gauss-Seidel como se ha explicado anteriormente converge más rápido a la solución que el método de Jacobi. En este caso se ha podido comprobar ya que Gauss-

Seidel ha convergido a la solución del sistema en 8 iteraciones y con un error de 7.5869*10-6, mientras que Jacobi lo ha hecho en 11 iteraciones y con una precisión menor (1.9210*10-5). Por otra parte al utilizar el método de Gauss- Seidel con relajación al contrario de lo esperado ha retrasado la convergencia del método de Gauss (13 iteraciones) y además ha disminuido la precisión del método (4.6182*10-5).

A=[1 5 75 2 07 0 −3 ] b=[1374 ] x(0)=[000] t olerancia=5∗10−5

iteraciones=1000

Jacobi:

Gauss Seidel

Gauss Seidel con Relajación:

En este ejemplo por el contrario se observa cuán útil puede ser el método de Gauss-Seidel con relajación, pues si bien al utilizar Jacobi y Gauss Seidel, éstos no convergían a la solución debido a que el radio espectral dela matriz T es mayor que 1, con el método

de relajación se obtiene una solución a las 18 iteraciones y un error de 3.1657*10 -5, y el radio espectral de T<1 lo que hace que se encuentre la solución.

6. CONCLUSIONES

Al realizar diversos análisis en el presente trabajo, podemos concluir que en el caso de la Eliminación Gaussiana con pivoteo parcial y total más que agilizar el procedimiento realizado en la eliminación Gaussiana Simple se disminuyen los errores errores de redondeo y la propagación de errores, ya que se evitan divisiones por cero.

Los métodos iterativos no siempre convergen a la solución por lo que en muchos casos resulta muy útil utilizar los métodos directos tales como eliminación gaussiana y factorización. Sin embargo el método de SOR, es muy recomendable ya que puede encontrar una solución en aquellos casos donde Gauss-Seidel no la encuentra, en algunos casos. Por otra parte la teoría afirma que cuando se escoge un valor de w>2 se puede acelerar la convergencia de Gauss-Seidel, lo cual luego de probar diversos sistemas de ecuaciones no resulto cierto en la totalidad de los casos.

La importancia que tiene la resolución de sistemas de ecuaciones lineales es sumamente amplia ya que tiene infinitos campos de aplicación, y es de esta manera como las herramientas de área de procesos numéricos se convierten en grandes ayudas que permiten simplificar y resolver sistemas y problemas que serían casi imposibles de resolver.

Es importante resaltar que no todos los métodos son ideales para resolver los sistemas, puesto que en algunos casos las soluciones obtenidas pueden contener grandes errores, como por ejemplo en el método de eliminación Gaussiana Simple.

7. REFERENCIAS

Eliminación Gaussiana. (s.f.). Recuperado el 22 de 10 de 2013

Sierra, C. A. (27 de Julio de 2010). Slideshare. Recuperado el 22 de 10 de 2013, de http://www.slideshare.net/cyndyArgote/metodos-iterativos-4854218

Steven C. Chapra, R. P. (1988). Métodos Numéricos para ingenieros. Mexico: McGraw Hill.

Vitutor, N. (2010). Vitutor. Recuperado el 22 de 10 de 2013

sistemas de ecuaciones lineales web viewservir de fuente de búsqueda a otros estudiantes que...

Documents