UNIDAD III Solución de Sistemas de Ecuaciones Lineales, No-Lineales y Valores Característicos

Sistemas de Ecuaciones Lineales Forma General

a11x1  a12 x2    a1n xn  b1 a21x1  a22 x2    a2 n xn  b2 





an1 x1  an 2 x2    ann xn  bn

a – Coeficientes (Constantes) b – Términos Independientes (Constantes) n – Número de Ecuaciones Los sistemas de dos y tres ecuaciones se pueden resolver manualmente en la mayoría de los casos, los sistemas de cuatro o más ecuaciones requieren el uso de métodos numéricos.

Notación Matricial  a11 a12  a1n  a a  a  2 n  Matriz de Coeficientes A   21 22        an1 an 2  ann  B T  b1 b2 bn  Vector de Términos Independientes X T  x1

x2  xn  Vector de Variables Incógnitas

 a11 a12 a13 b1    A  a21 a22 a23 b2  Matriz Aumentada de A con B  a31 a32 a33 b3  Los métodos de esta unidad están dedicados a la búsqueda de una solución X al sistema de ecuaciones A·X=B, de manera que X=A-1 ·B.

Regla de Cramer

• Para sistemas pequeños de dos ecuaciones se puede usar un método gráfico, o resolverse manualmente por sustitución de incógnitas, también se puede usar la Regla de Cramer. • La Regla de Cramer establece que cada incógnita de un sistema de ecuaciones lineales puede expresarse como una fracción de dos determinantes. • El denominador D es el determinante de la matriz de coeficientes. • El numerador se obtiene a partir de D al reemplazar la columna de coeficientes de la incógnita en cuestión por las constantes de los términos independientes. a11 a12 D  a21 a22 a31 a32

a13 a23 a33

x1 

b1

a12

a13

a11

b1

a13

a11

b2

a22

a23

a21 b2

a23

a21 a22 b2

b3

a32 D

a33

x2 

a31 b3 a33 D

x3 

a12

a31 a32 D

b1 b3

Ejemplo: Regla de Cramer Utilice la Regla de Cramer para resolver el siguiente sistema de ecuaciones 0.3x  0.52 x  x  0.01 1

2

3

0.5 x1  x2  1.9 x3  0.67 0.1x1  0.3x2  0.5 x3  0.44 0.3 0.52 D  0 .5 0 .1

1 0 .3

0.3  0.01 0.5

0.67

 0.01 0.52

1 1.9  0.0022 0 .5 1

0.67

1.9

 0.44 0.3 0.5 x1   14 .9  0.0022 0.3 0.52  0.01

0.5

1.9

0.1  0.44 0.5 x2   29 .5  0.0022

1

1

x3 

0.1

1

0.67

0.3  0.44  19 .8  0.0022

Para n>3 la Regla de Cramer resulta ineficiente, ya que el cálculo del determinante cada vez es más complicado.

Eliminación de Incógnitas • La eliminación de incógnitas mediante la combinación ecuaciones se ilustra con el siguiente ejemplo:

a11x1  a12 x2  b1 a21x1  a22 x2  b2 • La estrategia básica consiste en multiplicar las ecuaciones por constantes de tal forma que se elimine una de las incógnitas cuando se combinan dos de las ecuaciones. • El resultado es una sola ecuación en la que se puede despejar la incógnita restante. • Este valor se sustituye en cualquiera de las ecuaciones originales para calcular la otra variable.

Eliminación de Incógnitas • Iniciamos multiplicando la primera ecuación por a21 y la segunda por a11 a11a21x1  a12a21x2  b1a21 a21a11x1  a22a11x2  b2 a11 • Se restan estas dos ecuaciones para eliminar x1 a12a21x2  a22a11x2  b1a21  b2a11 • Se despeja x2 b1a21  b2 a11 x2  a12a21  a22a11 • Se sustituye x2 en la primera ecuación y se despeja x1 b2 a12  b1a22 x1  a12a21  a22a11

Eliminación de Incógnitas • Las expresiones para x1 y x2 obtenidas se relacionan directamente con la regla de Cramer, que establece b1

a12

b2 a22 b1a22  a12b2 x1   a11 a12 a11a22  a12a21 a21 a22

a11

b1

a21 b2 a11b2  b1a21 x2   a11 a12 a11a22  a12a21 a21 a22

Eliminación Gaussiana • Se utilizan dos pasos: 1. Eliminación de incógnitas hacia adelante 2. Sustitución hacia atrás • En forma de algoritmo para resolver grandes sistemas de ecuaciones. • El método esta ideado para resolver un sistema general de n ecuaciones. a11x1  a12 x2    a1n xn  b1

a21x1  a22 x2    a2 n xn  b2 





an1 x1  an 2 x2    ann xn  bn

1.- Eliminación de Incógnitas Hacia Adelante • La primera fase consiste en reducir el sistema de ecuaciones a un sistema triangular superior. • El paso inicial será reducir la primera incógnita desde la segunda hasta la n-ésima ecuación, para esto se multiplica la primera ecuación por a21/ a11 para obtener a21 a21 a21 a21x1 

a11

a12 x2   

a11

a1n xn 

a11

b1

• Ahora esta ecuación se resta a la segunda ecuación del sistema   a21  a21  a21  a22  a12  x2     a2 n  a1n  xn  b2  b1 a11 a11 a11    

1.- Eliminación de Incógnitas Hacia Adelante • Esta última ecuación se escribe como a22 ' x2   a2n ' xn  b2 '

• El apóstrofe significa que el coeficiente original fue modificado. • El procedimiento se repite con las ecuaciones restantes para construir el sistema a11x1  a12 x2  a13 x3    a1n xn  b1

a22 ' x2  a23 ' x3    a2 n ' xn  b2 ' a32 ' x2  a33 ' x3    a2 n ' xn  b3 ' 







an 2 ' x2  an 3 ' x3    ann ' xn  bn '

1.- Eliminación de Incógnitas Hacia Adelante • En todos los pasos anteriores, a la primera ecuación que no se modifica se le llama “ecuación pivote” y al coeficiente a11 se le llama “elemento pivote”. • El procedimiento se repite para eliminar la segunda incógnita de la tercera hasta la n-ésima ecuación, para realizar esto se multiplica la segunda ecuación por a32’/ a22’ y se resta de la tercera ecuación. • Se realiza la eliminación en forma similar a las ecuaciones restantes para obtener el siguiente sistema donde el superíndice bi-prima significa que el coeficiente original se ha modificado dos veces.

1.- Eliminación de Incógnitas Hacia Adelante a11x1  a12 x2  a13 x3    a1n xn  b1 a22 ' x2  a23 ' x3    a2 n ' xn  b2 ' a33 ' ' x3    a2 n ' ' xn  b3 ' ' 





an3 ' ' x3    ann ' ' xn  bn ' '

• El procedimiento continúa utilizando las ecuaciones pivote restantes. • La última manipulación en esta secuencia es el uso de la (n-1)-ésima ecuación para eliminar el término xn-1 de la n-ésima ecuación.

1.- Eliminación de Incógnitas Hacia Adelante

• Así el sistema se habrá transformado en un sistema triangular superior a11x1  a12 x2  a13 x3    a1n xn  b1 a22 ' x2  a23 ' x3    a2 n ' xn  b2 ' a33 ' ' x3    a2 n ' ' xn  b3 ' ' 

 ann

( n 1)

 xn  bn

( n 1)

• El determinante del sistema se puede calcular multiplicando los elementos de la diagonal principal del sistema triangular superior. ( n 1) D  a11  a22 'a33 ' '  ann  (1) p p es el número de veces en que los renglones se pivotean

Pseudocódigo para la Eliminación Hacia Adelante 1. for k=1 hasta n-1 2. for i=k+1 hasta n 3. factor=a(i,k)/a(k,k) 4. for j=1 hasta n 5. a(i,j)=a(i,j)-factor*a(k,j) 6. termina for j 7. b(i)=b(i)-factor*b(k) 8. termina for i 9. termina for k

• El ciclo externo (k) mueve el renglón pivote hacia debajo de la matriz. • El siguiente ciclo (i) mueve hacia abajo el renglón pivote a cada renglón subsecuente donde se lleva a cabo la eliminación. • El ciclo mas interno (j) avanza a través de las columnas para eliminar o transformar los elementos del renglón determinado.

2.- Sustitución Hacia Atrás • De la última ecuación de la matriz diagonal superior se calcula xn ( n 1) bn xn  ( n 1) ann

• Este resultado se puede sustituir hacia atrás en la (n-1)-ésima ecuación y despejar xn-1. • El procedimiento para evaluar las variables restantes se resume en la siguiente fórmula xi 

bi

( i 1)

n

  aij i i 1 ( i 1) ii

a

( i 1)

 xj

Pseudocódigo para la Sustitución Hacia Atrás 1. x(n)=b(n)/a(n,n) 2. for i=n-1 hasta 1 3. suma=0 4. for j=i+1 hasta n 5. suma=suma+a(i,j)*x(j) 6. termina for j 7. x(i)=(b(i)-suma)/a(i,i) 8. termina for i

Ejemplo: Eliminación Gaussiana • Resolver el siguiente sistema de ecuaciones utilizando el método de eliminación Gaussiana. • Efectuar los cálculos con seis cifras significativas. 3x1  0.1x2  0.2 x3  7.85 0.1x1  7 x2  0.3x3  19 .3 0.3x1  0.2 x2  10 x3  71 .4

Dificultades del los Métodos de Eliminación • División entre cero.- Cuando el primer elemento (x1) de la primera ecuación del sistema no esta presente (a11 =0), entonces en la normalización del primer renglón habrá una división entre cero. • Errores de redondeo.- Se produce por el uso limitado de cifras significativas. Para cuantificar los posibles errores se deben sustituir los valores calculados en las ecuaciones del sistema para verificar los resultados. • Sistemas mal condicionados.- Los sistemas mal condicionados son aquellos en donde pequeños cambios en los coeficientes generan grandes cambios en la solución.

Dificultades del los Métodos de Eliminación • Sistemas Singulares.- Cuando dos de las ecuaciones son idénticas, el sistema no tiene solución ya que n cambia a n-1 y tenemos mas incógnitas que ecuaciones. Estos casos no son tan obvios en sistemas muy grandes. • El determinante de un sistema singular es cero.

Sistemas Mal Condicionados • Un sistema mal condicionado es el siguiente

donde las pendientes son tan cercanas que no es posible determinar la solución.

Sistemas Mal Condicionados • Un sistema mal condicionado es aquel en el que el determinante es cercano a cero. • Es difícil determinar que tan cercano a cero debe ser el determinante para decidir si un sistema es mal condicionado. • Esto se complica porque el determinante puede cambiar al multiplicar una o más de las ecuaciones por factor de escalamiento, por lo tanto, el determinante es un factor relativo influenciado por la magnitud de los coeficientes.

Sistemas Singulares • En el primer caso como las líneas no se cruzan no existe solución. • En el segundo caso las líneas son iguales por lo que existe un número infinito de soluciones

Técnicas para Mejorar las Soluciones de los Métodos de Eliminación • Uso de más cifras significativas. • Pivoteo parcial.- Se determina el elemento más grande disponible en la columna por debajo del elemento pivote. Se intercambian los renglones para que el elemento más grande sea el pivote. • Escalamiento.- Se escalan las ecuaciones en forma tal que el elemento máximo en cualquier renglón igual a 1.

Pseudocódigo para Implementar el Pivoteo Parcial 1. p=k 2. mayor=|a(k,k)| 3. for i=k+1 hasta n 4. temp=|a(i,k)| 5. if temp>mayor 6. mayor=temp 7. p=i 8. termina if 9. termina for i

10.if p≠k 11. for j=k hasta n 12. temp=a(p,j) 13. a(p,j)=a(k,j) 14. a(k,j)=temp 15. termina for j 16. temp=b(p) 17. b(p)=b(k) 18. b(k)=temp 19.termina if

En este pseudocódigo los renglones se intercambian, esto es tardado, una implementación eficiente solo lleva un control por separado de cual es elemento pivote sin cambiar los renglones.

Algoritmo del Método de Eliminación Gaussiana 1. n=no. de renglones de a 2. for i=1 hasta n 3. s(i)=|a(i,1)| 4. for j=2 hasta n 5. if |a(i,j)|>s(i) 6. s(i)=|a(i,j)| 7. termina if 8. termina for j 9. termina for i 10.a,b,er= Eliminacion(a,b,s,n,tol) 11.if er==0 12. x=Sustitucion(a,b,n) 13.termina if

Los parámetros de entrada para el Método de Eliminación Gaussiana son: a – Matriz de Coeficientes b – Vector de Términos Independientes tol – Valor de tolerancia mínimo para los elementos pivote

Rutina de Eliminación Modificada 1. error=0 2. for k=1 hasta n-1 3. a,b,s=Pivoteo(a,b,s,n,k) 4. if |a(k,k)/s(k)|mayor 6. mayor=temp 7. p=i 8. termina if 9. termina for i

10.if p≠k 11. for j=k hasta n 12. temp=a(p,j) 13. a(p,j)=a(k,j) 14. a(k,j)=temp 15. termina for j 16. temp=b(p) 17. b(p)=b(k) 18. b(k)=temp 19. temp=s(p) 20. s(p)=s(k) 21. s(k)=temp 22.termina if

Esta rutina recibe como entradas: la matriz a, el vector b, el vector s, n y k; y regresa la matriz a y los vectores b y s modificados.

Rutina para la Sustitución Hacia Atrás 1. x(n)=b(n)/a(n,n) 2. for i=n-1 hasta 1 3. suma=0 4. for j=i+1 hasta n 5. suma=suma+a(i,j)*x(j) 6. termina for j 7. x(i)=(b(i)-suma)/a(i,i) 8. termina for i

Esta rutina recibe como entradas: la matriz a modificada en forma de matriz triangular superior, el vector b modificado y n (número de ecuaciones); y regresa el resultado final en el vector x (solución del sistema de ecuaciones)

Método de Gauss-Jordan • La principal diferencia con la Eliminación Gaussiana consiste en que cuando una incógnita se elimina en el método de Gauss-Jordan, ésta es eliminada de todas las ecuaciones, no solo de las subsecuentes. • Todos los renglones se normalizan al dividirlos entre su elemento pivote. • El paso de eliminación genera una matriz identidad en vez de una triangular superior. • En consecuencia, ya no es necesaria la sustitución hacia atrás. (n)  1 0 0 | b1  x1  a11 a12 a13 | b1   a a a | b   0 1 0 | b ( n )   2   21 22 23 2    a31 a32 a33 | b3  0 0 1 | b3( n )   

 b1 x2

(n)

 b2

(n)

x3  b3

(n)

Ejemplo: Método de Gauss-Jordan • Resolver el siguiente sistema de ecuaciones utilizando el método de Gauss-Jordan. • Efectuar los cálculos con seis cifras significativas. 3x1  0.1x2  0.2 x3  7.85 0.1x1  7 x2  0.3x3  19 .3 0.3x1  0.2 x2  10 x3  71 .4

Algoritmo del Método de Gauss-Jordan • Del algoritmo de eliminación gaussiana se elimina la rutina de sustitución hacia atrás y se modifica la rutina de eliminación para generar la matriz identidad. • Se sigue utilizando la rutina de pivoteo y las pruebas al elemento pivote para verificar que sea mayor al valor de tolerancia.

Rutina de Eliminación Modificada para el Método de Gauss-Jordan 1. for k=1 hasta n 2. if k