M´ etodos Num´ ericos (SC–854) Soluci´ on de sistemas de ecuaciones lineales c M. Valenzuela 2007  (21 de agosto de 2007)

1.

Matrices

Definici´ on. 1 Una matriz n × m es un arreglo rectangular de elementos con n filas (o renglones) y m columnas en el cual no s´ olo es importante el valor de los elementos sino tambi´en su posici´ on en el arreglo. Ejemplo:

⎡ ⎢ ⎢ A = (aij ) = ⎢ ⎣

a11 a21 .. .

a12 a22 .. .

··· ··· .. .

an1

an2

· · · anm

a1m a2m .. .

⎤ ⎥ ⎥ ⎥ ⎦

(1)

Las matrices se denotan con may´ usculas (con negritas) y sus elementos con min´ usculas.

2.

Vectores

Definici´ on. 2 Una matriz 1 × n, B=



b11

b12

· · · b1n



,

(2)

se le llama un vector rengl´ on de n dimensiones. Definici´ on. 3 Una matriz n × 1,

⎡ ⎢ ⎢ C=⎢ ⎣

c11 c12 .. .

⎤ ⎥ ⎥ ⎥, ⎦

(3)

c1n se le llama un vector columna de n dimensiones. Usualmente, los sub´ındices innecesarios se omiten, de manera que  y = y1 y2 · · · ym , denota un vector rengl´on de m dimensiones, y

⎡

⎢ ⎢ x=⎢ ⎣

x1 x2 .. .

(4)

⎤ ⎥ ⎥ ⎥, ⎦

(5)

xn denota un vector columna de n dimensiones. Los vectores se denotan con min´ usculas y negritas. La norma de un vector x se define de la siguiente manera:

n 1/p  p ||x||p = |xi | (6) i=1

N´otese que

 n  ||x||2 =  |xi |2 = |x|, i=1

(7)

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

10Ω

− +

20V

5Ω

R = 5Ω

10Ω

5Ω

5Ω

Figura 1: Circuito el´ecitrico que puede ser descrito mediante un sistema de ecuaciones simult´aneas. es decir, la magnitud del vector. N´ otese tambi´en que

n 1/p  p |xi | = max (|xi |) , ||x||∞ = lim p→∞

i

i=1

(8)

es decir, el m´ aximo de los valores absolutos de las componentes xi del vector.

3.

Por qu´ e se requieren m´ etodos para resolver sistemas de ecuaciones lineales

Muchos problemas pueden ser descritos mediante un sistemas de ecuaciones lineales. Por ejemplo, considere el circuito el´ectrico mostrado en la figura 1. Las ecuaciones de malla que describen a este circuito son las siguientes: 15ii −5i1

− 5i2 + 15i2 − 5i2

− +

= 20 = 0 = 0

5i3 20i3

(9)

A partir de las ecuaciones de malla se pueden obtener todas las corrientes, voltajes, y pontencial de los elementos del circuito. Por ejemplo, la corriente de la resistencia R es i1 − i2 .

4.

Representaci´ on de sistemas de ecuaciones Un sistema de ecuaciones lineales simulat´aneas de la forma a11 x1 + a12 x2 + · · · + a1n xn a21 x1 + a22 x2 + · · · + a2n xn

= = .. .

b1 b2

an1 x1 + an2 x2 + · · · + ann xn

=

bn

puede representarse mediante una matriz n × (n + 1). A partir de la matriz A y el vector b ⎡ a11 a12 · · · ⎢ a21 a22 · · · ⎢ A=⎢ . .. .. ⎣ .. . . an2 ⎡ b1 ⎢ b2 ⎢ b=⎢ . ⎣ ..

an1

a1n a2n .. .

⎤ ⎥ ⎥ ⎥ ⎦

(10)

· · · ann ⎤ ⎥ ⎥ ⎥ ⎦

(11)

bn c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 2

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

se forma la matriz aumentada ⎡ ⎢ ˜ =⎢ A ⎢ ⎣

a11 a21 .. .

a12 a22 .. .

··· ··· .. .

a1n a2n .. .

b1 b2 .. .

an1

an2

· · · ann

bn

⎤ ⎥ ⎥ ⎥ ⎦

(12)

Esta matriz aumentada representa la ecuaci´ on vectorial Ax = b.

5.

Ejemplo de circuitos el´ ectricos Definiendo R, i, y v:

⎡

⎤ 15 −5 0 R = ⎣ −5 15 −5 ⎦ 0 −5 20 ⎤ ⎡ ⎤ ⎡ 20 i1 i = ⎣ i2 ⎦ v = ⎣ 0 ⎦ i3 0

Podemos expresar el juego de ecuaciones como ⎤ ⎡ ⎡ ⎤ ⎤⎡ 20 15 −5 0 i1 Ri = v = ⎣ −5 15 −5 ⎦ ⎣ i2 ⎦ = ⎣ 0 ⎦ i3 0 0 −5 20 Que puede representarse mediante la matriz aumentada: ⎡ ⎤ 15 −5 0 20 ˜ = ⎣ −5 15 −5 0 ⎦ R 0 −5 20 0

6.

(13)

(14)

(15)

(16)

Operaciones elementales de rengl´ on

˜ representa un sistema de ecuaciones simult´aneas, es posible reComo la matriz aumentada A alizar las siguientes operaciones elementales de rengl´on manteniendo las igualdades de las ecuaciones representadas: Multiplicar un rengl´ on por una constante Multiplicar un rengl´ on por una constante y sumarlo a otro rengl´on Los m´etodos de soluciones de sistemas de ecuaciones aplican estas operaciones sobre la matriz aumentada en forma ordenada y repetida. En las siguientes secciones se explican los siguientes m´etodos: Eliminaci´ on gaussiana (Gauss) Gauss-Jordan Montante

c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 3

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

Function EGaussiana(A,b) 1 2 3 4 5

6 7 8 9 10

A ← [Ab] ; for i ← 1 to n do // Hacer ceros abajo de pivote for j ← i + 1 to n do A(i, :)A(j, i) A(j, :) ← A(j, :) − ; A(i, i) for i ← n downto 1 do // Hacer pivote 1 A(i, :) A(i, :) ← ; A(i, i) // Hacer ceros arriba de pivote for j ← i − 1 downto 1 do A(j, :) ← A(j, :) − A(i, :)A(j, i) ; x ← A(:, n + 1) ; return x

Figura 2: Pseudoc´ odigo que implementa el m´etodo de eliminaci´ on gaussiana para soluci´ on de sistemas de ecuaciones lineales.

7.

Eliminaci´ on Gaussiana

Eliminaci´ on gaussiana aplica operaciones de rengl´ on para resolver un sistema de ecuaciones simulat´ aneas; su pseudoc´ odigo se presenta en la figura 2, y en la figura 3 su implementaci´ on en MATLAB. on Para cada rengl´ on, se define el elemento ai,i de la matriz aumentada como el pivote. Eliminaci´ gaussiana opera en dos fases. Primero, para cada rengl´ on empezando por el primer rengl´ on, hace ceros en los elementos debajo del pivote (l´ıneas 3 y 4). Segundo, para cada rengl´ on empezando por el u ´ ltimo rengl´ on, hace el pivote igual a 1, y hace ceros arriba del pivote (l´ıneas 5 a 8). La soluci´ on al sistema de ecuaciones queda en la u ´ ltima columna de la matriz aumentada (l´ınea 9). A continuaci´ on se presenta la soluci´on del ejemplo del circuito el´ecitrico mediante eliminaci´on gaussiana. ⎡ ⎤ ⎡ ⎤ 15 −5 0 20 15 −5 0 20 ˜ = ⎣ −5 15 −5 0 ⎦ ∼ ⎣ 0 13.3333 −5 6.6667 ⎦ ∼ R (17) 0 −5 20 0 0 −5 20 0 ⎡ ⎤ ⎡ ⎤ 15 −5 0 20 15 −5 0 20 ⎣ 0 13.3333 −5 6.6667 ⎦ ∼ ⎣ 0 13.3333 −5 6.6667 ⎦ ∼ (18) 0 0 18.1250 2.5 0 0 1 0.1379 ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 15 −5 0 20 15 0 0 22.7586 1 0 0 1.5172 ⎣ 0 13.3333 0 7.3563 ⎦ ∼ ⎣ 0 1 0 0.5517 ⎦ ∼ ⎣ 0 1 0 0.5517 ⎦ (19) 0 0 1 0.1379 0 0 1 0.1379 0 0 1 0.1379 de donde se tiene que las corrientes de malla son: ⎡ ⎤ 1.5172 i = ⎣ 0.5517 ⎦ 0.1379

c M. Valenzuela, 2007 (21 de agosto de 2007) 

(20)

P´ agina 4

Soluci´ on de sistemas de ecuaciones lineales

function x = EGauss(A,b) % % % % % % %

Implementacion del metodo de eliminacion gaussiana para resolver sistemas de ecuaciones lineales.

M´etodos Num´ericos (SC–854)

for i=1:n % Hacer ceros en la columna i debajo de la fila i for j=i+1:n A(j ,:) = A(j,:) − A(i,:)∗A(j, i)/A(i, i ); end end

x = EGauss(A,b) Regresa x, la solucion del sistema Ax=b.

% 22 enero 2007 % Manuel Valenzuela % Crear la matriz aumentada A = [A b]; n = size(A,1);

for i=n:−1:1 % Hacer uno el elemento i,i A(i ,:) = A(i,:)/A(i, i ); % Hacer ceros en la columna i arriba de la fila i for j=i−1:−1:1 A(j ,:) = A(j,:) − A(i,:)∗A(j, i ); end end x = A(:,n+1);

Figura 3: Implementaci´ on en MATLAB del m´etodo de eliminaci´ on gaussiana para soluci´ on de sistemas de ecuaciones lineales.

8.

M´ etodo de Gauss-Jordan

En la figuras 4 y 5 se presenta en la implementaci´on del m´etodo Gauss-Jordan. El m´etodo de Gauss-Jordan es similar a eliminaci´ on gaussiana, pero primero hace el pivote igual a 1, y luego hace ceros en toda la columna del pivote. En el m´etodo de Gauss-Jordan primero se hace el pivote igual a 1 se hace el pivote igual a 1 (l´ınea 3), Despu´es se hacen cero los elementos arriba y abajo del pivote l´ıneas 4 a 6). La soluci´ on al sistema de ecuaciones queda en la u ´ltima columna de la matriz aumentada (l´ınea 7). A contiuaci´ on se muestra la soluci´on del ejemplo del circuito el´ectrico mediante Gauss-Jordan. ⎡ ⎤ ⎡ ⎤ 15 −5 0 20 1 −0.3333 0 1.3333 ˜ = ⎣ −5 15 −5 0 ⎦ ∼ ⎣ −5 ⎦∼ 15 −5 0 R (21) 0 −5 20 0 0 −5 20 0 ⎤ ⎡ ⎤ ⎡ 1 −0.3333 0 1.3333 1 −0.3333 0 1.3333 ⎣ 0 13.3333 −5 6.6667 ⎦ ∼ ⎣ 0 1 −0.3750 0.5000 ⎦ ∼ (22) 0 −5 20 0 0 −5 20 0 ⎡ ⎤ ⎡ ⎤ 1 0 −0.1250 1.5000 1 0 −0.1250 1.5000 ⎣ 0 1 −0.3750 0.5000 ⎦ ∼ ⎣ 0 1 −0.3750 0.5000 ⎦ ∼ (23) 0 0 18.1250 2.5000 0 0 1 0.1379 ⎡ ⎤ 1 0 0 1.5172 ⎣ 0 1 0 0.5517 ⎦ (24) 0 0 1 0.1379

9.

Pivote m´ aximo

Los algoritmos presentados pueden encontrar el problema de que el pivote sea cero, causando una divisi´ on entre cero. Para resolver este problema se pueden intercambiar renglones para colocar una elemento diferente de cero en la diagonal principal. En la figura 6 se presenta la implementaci´ on de Gauss-Jordan donde se escoge el elemento de m´aximo valor abosluto como pivote. c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 5

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

Function GaussJordan(A,b) 1 2

3 4 5 6 7 8

A ← [Ab] ; for i ← 1 to n do // Hacer pivote 1 A(i, :) A(i, :) ← ; A(i, i) for j ← 1 to n do if j = i then // Hacer ceros arriba y abajo del pivote A(j, :) ← A(j, :) − A(j, i)A(i, :) ; x ← A(:, n + 1) ; return x

Figura 4: Pseudoc´ odigo que implementa de m´etodo Gauss-Jordan para la soluci´ on de sistemas de ecuaciones lineales.

function x = GaussJ(A,b) % % % % % % %

Implementacion del metodo Gauss−Jordan para resolver sistemas de ecuaciones lineales. x = GaussJordan(A,b) Regresa x, la solucion del sistema Ax=b.

% 22 enero 2007 % Manuel Valenzuela % Se crea la matriz aumentada A = [A b]; n = size(A,1);

for i=1:n % Dividir renglon entre el pivote A(i ,:) = A(i,:)/A(i, i ); % Hacer ceros en la columna i for j=1:n if i˜=j A(j ,:) = A(j,:) − A(i,:)∗A(j, i ); end end end x = A(:,n+1);

Figura 5: Implementaci´ on en MATLAB del m´etodo Gauss-Jordan para soluci´ on de sistemas de ecuaciones lineales.

c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 6

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

Function GaussJordan(A,b) 1 2 3 4 5

6 7 8 9 10 11

A ← [Ab] ; for i ← 1 to n do m ← max(|A(i : n, i)|) ; k ← rengl´ on de m en A ; Intercambiar renglones i y k de A ; // Hacer pivote 1 A(i, :) A(i, :) ← ; A(i, i) for j ← 1 to n do // Hacer ceros arriba y abajo del pivote if j = i then A(j, :) ← A(j, :) − A(j, i)A(i, :) ; x ← A(:, n + 1) ; return x

Figura 6: Pseudoc´ odigo que implementa el m´etodo de Gauss-Jordan con pivote m´ aximo para soluci´ on de sistemas de ecuaciones lineales.

10.

Montante

El m´etodo de Montante, que se presenta en las figuras 7 y 8, resuelve un sistema de ecuaciones simult´aneas haciendo operaciones que mantienen el n´ umero de decimales que tiene los datos originales hasta el u ´ ltimo paso, donde se realiza la divisi´ on entre el determinante. Ejemplo del m´etodo Montante: ⎡ ⎤ ⎡ ⎤ 15 −5 0 20 15 −5 0 20 ˜ = ⎣ −5 15 −5 0 ⎦ ∼ ⎣ 0 200 −75 100 ⎦ ∼ A (25) 0 −5 20 0 0 −75 300 0 ⎡ ⎤ ⎡ ⎤ 200 0 −25 300 3625 0 0 5500 ⎣ 0 200 −75 100 ⎦ ∼ ⎣ 0 3625 0 2000 ⎦ ∼ (26) 0 0 3625 500 0 0 3625 500 ⎡ ⎤ 1 0 0 1.5172 ⎣ 0 1 0 0.5517 ⎦ (27) 0 0 1 0.1379

11.

Matriz inversa

Los m´etodos de eliminaci´on gaussiana, Gauss-Jordan, y Montante pueden ser utilizados para encontrar la inversa de una matriz. En este caso, la matriz aumentada ser´ a la matriz de original y la matriz identidad. ⎤ ⎡ ⎡ ⎤ 15 −5 0 1 0 0 15 −5 0 1 0 0 ⎣ −5 15 −5 0 1 0 ⎦ ∼ ⎣ 0 200 −75 5 15 0 ⎦ ∼ (28) 0 −5 20 0 0 1 0 −75 300 0 0 15 ⎡ ⎤ ⎡ ⎤ 200 0 −25 15 5 0 3625 0 0 275 100 25 ⎣ 0 200 −75 5 15 0 ⎦ ∼ ⎣ 0 3625 0 100 300 75 ⎦ (29) 0 0 3625 25 75 200 0 0 3625 25 75 200 c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 7

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

Function Montante(A,b) 1 2 3 4 5 6 7 8

9 10 11

A ← [Ab] ; pivAnt ← 1 ; for i ← 1 to n do piv ← A(k, k) ; for j ← 1 to n do // Hacer ceros arriba y abajo del pivote if j = i then A(j, :)piv − A(i, :)A(j, i) A(j, :) ← ; pivAnt pivAnt ← piv ; A(:, n + 1) ; piv det ← A(n, n) ; return x, det x←

Figura 7: Pseudoc´ odigo que implementa el m´etodo de Montante para la soluci´ on de sistemas de ecuaciones lineales.

function x = Mont(A,b) % % % % % % %

Implementacion del metodo Montante para resolver sistemas de ecuaciones lineales. x = Montante(A,b) Regresa x, la solucion del sistema Ax=b.

% 22 enero 2007 % Manuel Valenzuela % Se crea la matriz aumentada A = [A b]; n = size(A,1);

pivAnt = 1; % pivote inicial for i=1:n % pivote actual piv = A(i,i ); % Hacer ceros en la columna i for j=1:n if j˜=i A(j ,:) = (A(j,:)∗piv − A(i,:)∗A(j, i ))/pivAnt; end end % Guardar el pivote anterior pivAnt = piv; end % Dividir entre el ultimo pivote (determinante) A = A/piv; x = A(:,n+1);

Figura 8: Implementaci´ on en MATLAB del m´etodo de Montante para la soluci´ on de sistemas de ecuaciones lineales.

c M. Valenzuela, 2007 (21 de agosto de 2007) 

P´ agina 8

Soluci´ on de sistemas de ecuaciones lineales

⎡

1 ∼⎣ 0 0

0 0 1 0 0 1

M´etodos Num´ericos (SC–854)

⎤ 0.0759 0.0276 0.0069 0.0276 0.0828 0.0207 ⎦ 0.0069 0.0207 0.0552

La inversa son las u ´ ltimas n columnas de la matriz aumentada: ⎡ ⎤ 0.0759 0.0276 0.0069 A−1 = ⎣ 0.0276 0.0828 0.0207 ⎦ 0.0069 0.0207 0.0552

12.

(30)

(31)

M´ etodos Iterativos: Jacobi

Dado un sistema de ecuaciones de la forma: a11 x1 + a12 x2 + · · · + a1n xn

=

b1

(32)

a21 x1 + a22 x2 + · · · + a2n xn

= .. . =

b2

(33)

bn

(34) (35)

an1 x1 + an2 x2 + · · · + ann xn

si se despeja la variable xi de cada ecuaci´on se obtiene lo siguiente: x1

=

−

a12 a13 a1n b1 x2 − x3 − · · · − xn + a11 a11 a11 a11

(36)

x2

=

−

a21 a23 a2n b2 x1 − x3 − · · · − xn + a22 a22 a22 a22

(37)

.. . xn

=

(38) −

an1 an2 an,n−1 bn x1 − x2 − · · · − xn−1 + ann ann ann ann

(39)

El sistema anterior, puede usarse como una f´ormula recursiva, es decir, x1 (t + 1) =

−

a12 a13 a1n b1 x2 (t) − x3 (t) − · · · − xn (t) + a11 a11 a11 a11

(40)

x2 (t + 1) =

−

a21 a23 a2n b2 x1 (t) − x3 (t) − · · · − xn (t) + a22 a22 a22 a22

(41)

.. . xn (t + 1) =

(42) an1 an2 an,n−1 bn − x1 (t) − x2 (t) − · · · − xn−1 (t) + ann ann ann ann

on de los valores de xi (t). puede usarse para obtener los valores de xi (t + 1) en funci´ Si definimos la matriz T y el vector c de la siguiente manera, ⎤ ⎡ ⎤ ⎡ a13 a1n a12 b1 − ··· 0 − ⎥ ⎢ ⎢ a a11 a11 a11 ⎥ ⎢ ⎥ ⎢ 11 ⎥ ⎢ ⎥ ⎢ b ⎥ a a a 23 1n ⎥ ⎢ − 21 ⎢ 2 ⎥ 0 − ··· − ⎥ ⎢ ⎥ ⎢ a22 a22 ⎥ ⎢ a22 ⎢ a22 ⎥ ⎥ ⎢ ⎥ ⎢ a31 a32 a3n ⎥ c = ⎢ b3 ⎥ T=⎢ − 0 ··· − ⎥ ⎢ − ⎥ ⎢ ⎢ a33 ⎢ a33 ⎥ a33 a33 ⎥ ⎥ ⎢ ⎥ ⎢ .. .. .. ⎢ ⎥ ⎢ .. ⎥ ⎢ ⎥ ⎢ . ⎥ . . . ⎥ ⎢ ⎥ ⎢ ⎣ an1 ⎦ ⎣ bn ⎦ an2 an,n−1 − ··· − 0 − ann ann ann ann c M. Valenzuela, 2007 (21 de agosto de 2007) 

(43)

(44)

P´ agina 9

Soluci´ on de sistemas de ecuaciones lineales

M´etodos Num´ericos (SC–854)

Function Jacobi(A,b,x0 ) 1 2 3 4 5 6 7 8

Obtener matriz T ; Obtener vector c ; x ← x0 ; repeat xant ← x ; x ← Tx + c ; ||x − xant ||∞ until