Referencia: Chapra 9.2 p254 pdf278, Burden 6.1 p359. Rodriguez 4.3 p119
El método de Gauss realiza operaciones sobre la matriz aumentada y pivoteada por filas, añadiendo procedimientos con las siguientes fórmulas:
- eliminación hacia adelante:
- sustitución hacia atrás:
para i = n-1, n-2, …
Método de Gauss
El método de Gauss opera sobre la matriz aumentada y pivoteada por filas, añadiendo el proceso de «eliminación hacia adelante» mediante la operación entre filas. Se continúa entonces desde el resultado del tema de 3.2 pivoteo parcial por filas para matrices:
Referencia: Rodriguez cap4.0 Ejemplo 1 pdf.105
\begin{cases} 4x_1+2x_2+5x_3 = 60.70 \\ 2x_1+5x_2+8x_3 = 92.90 \\ 5x_1+4x_2+3x_3 = 56.30 \end{cases}matriz pivoteada por fila: [[ 5. 4. 3. 56.3] [ 2. 5. 8. 92.9] [ 4. 2. 5. 60.7]]
Desarrollo Analítico
Eliminación hacia adelante
Consiste en simplificar la matriz a una triangular superior, con ceros debajo de la diagonal, usando operaciones entre filas.
Como referencia, los índices de fila y columna, A[i,j], se usan de forma semejante a la nomenclatura de los textos de Algebra Lineal.
Progresivamete para cada fila, se toma como referencia o pivote el elemento de la diagonal (i=j). Se realizan operaciones con las filas inferiores para convertir los elementos por debajo de la diagonal en cero. Las operaciones incluyen el vector B debido a que se trabaja sobre la matriz aumentada AB.
matriz pivoteada por fila: [[ 5. 4. 3. 56.3] [ 2. 5. 8. 92.9] [ 4. 2. 5. 60.7]]
iteración fila 1, operacion fila 1 y 2
Para la fila 1, con posición i=0, se usa el elemento ai,i como pivote.
pivote = A[i,i] = AB[0,0] = 5
Para las filas de que estan después de la diagonal se referencian como k
k= i+1 = 0+1 = 1
Se obtiene el factor escalar de la operación entre filas de la formula
A_{k} = A_{k} -A_{i}\frac{a_{k,i}}{pivote}factor = AB[1,0]/pivote = 2/5
y se realiza la operación entre fila k y la fila i para actualizar la fila k,
[ 2. 5. 8. 92.9] -(2/5)*[ 5. 4. 3. 56.3] __________________________ = [ 0. 3.4 6.8 70.38]
con lo que la matriz aumentada AB se actualiza a:
AB = [[ 5. 4. 3. 56.3 ] [ 0. 3.4 6.8 70.38] [ 4. 2. 5. 60.7 ]]
iteración fila 1, operacion fila 1 y 3
se continúa con la siguiente fila, quedando la matriz aumentada con la columna debajo de la primera diagonal en cero:
k = i+1 = 2 factor = 4/5 [ 4. 2. 5. 60.7] - (4/5)*[ 5. 4. 3. 56.3] _____________________________ = [ 0. -1.2 2.6 15.66] AB = [[ 5. 4. 3. 56.3 ] [ 0. 3.4 6.8 70.38] [ 0. -1.2 2.6 15.66]]
Como ya se terminaron las operaciones con la primera posición de la diagonal, el siguiente paso es usar la segunda posición, i =2.
iteración fila 2
Para la fila 2, con posición i=1, se toma el elemento de la diagonal ai,i como pivote, la variable adelante indica la referencia de la tercera fila
i=1 pivote = A[i,i] = AB[1,1] = 3.4
Para las filas ubicadas adelante de la diagonal se referencian como k
adelante = i+1 = 1+1 = 2 k = adelante = 2
Para aplicar la fórmula por filas, se obtiene el factor .
factor = AB[2,1]/pivote = -1,2/3.4 = - 0,3529 [ 0. -1.2 2.6 15.66] -(-1,2/3.4)*[ 0. 3.4 6.8 70.38] ________________________________ = [ 0. 0. 5. 40.5 ] AB = [[ 5. 4. 3. 56.3 ] [ 0. 3.4 6.8 70.38] [ 0. 0. 5. 40.5 ]]
Con lo que se completa el objetivo de tener ceros debajo de la diagonal.
Observe que no es necesario realizar operaciones para la última fila, por lo que k debe llegar solamente hasta la fila penúltima.
El resultado de la eliminación hacia adelante a ser usado en el proximo paso es:
Elimina hacia adelante [[ 5. 4. 3. 56.3 ] [ 0. 3.4 6.8 70.38] [ 0. 0. 5. 40.5 ]]
Sustitución hacia atrás
La fórmula se interpreta para facilitar el algoritmo
x_i = \frac{b_i^{(i-1)}-\sum_{j=i+1}^{n}a_{ij}^{(i-1)} x_{j}}{a_{ii}^{(i-1)}}Para una fila i, el vector b[i] representa el valor de la constante en la fila i de la matriz aumentada, a[i] se refiere los valores de los coeficientes de la ecuación, de los que se usan los que se encuentran a la derecha de la diagonal.
Las operaciones se realizan de abajo hacia arriba desde la última fila. Para el ejercicio presentado se tiene que:
utlfila = n-1 = 3-1 = 2 ultcolumna = m-1 = 4-1 = 3
la matriz a procesar es:
Elimina hacia adelante [[ 5. 4. 3. 56.3 ] [ 0. 3.4 6.8 70.38] [ 0. 0. 5. 40.5 ]]
iteración 1, fila 3, i=2
Empieza desde la última fila de la matriz,
[ 0. 0. 5. 40.5 ]0 x_1 + 0 x_2 + 5 x_3 = 40.5
El valor de la constante es b = 40.5 y no existen elementos hacia la derecha de la diagonal. No se usa la ultima columna que es de las constantes:
5 x_3 = 40.5 x_3 = 40.5/5 = 8.1la respuesta se interpreta en el vector X como:
X= \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 8.1 \end{pmatrix}iteración 2, fila 2, i = 1
De la penúltima fila se obtiene la ecuación para encontrar x2
[ 0. 3.4 6.8 70.38]0x_1 + 3.4 x_2 +6.8 x_3 = 70.38
se observa que b = 70.38 y a la derecha de a diagonal se tiene un solo valor de [6.8].
3.4 x_2 = 70.38 -6.8 x_3usa el valor de x3 encontrado en la iteración anterior
3.4 x_2 = 70.38 -6.8 (8.1)Muestra la ecuación para la segunda fila.
x_2 = (70.38 -6.8 (8.1))/3.4 = 4.5la respuesta se interpreta en el vector X como:
X= \begin{pmatrix} 0 \\ 4.5 \\ 8.1 \end{pmatrix}iteración 3 fila 1, i=0
se sigue el mismo proceso para la siguiente incógnita X1 que se interpreta como
[ 5. 4. 3. 56.3 ]5x_1 + 4 x_2 + 3x_3 = 56.3 5x_1 = 56.3 - ( 4 x_2 + 3x_3) x_1 = \frac{56.3 - ( 4 x_2 + 3x_3)}{5}
realice las operaciones con los valores encontrados para X2 y X3
Se encuentra que la solución al sistema de ecuaciones es:
X= \begin{pmatrix} 2.8\\ 4.5 \\ 8.1 \end{pmatrix}por sustitución hacia atras el vector solución X es: [[2.8] [4.5] [8.1]]
Verificar respuesta
Para verificar que el resultado es correcto, se usa el producto punto entre la matriz a y el vector resultado X. La operación A.X = B debe dar el vector B.
verificar que A.X = B [[60.7] [92.9] [56.3]]
Algoritmo en Python
El algoritmo en su primera parte reutiliza lo desarrollado en Python para la matriz aumentada y pivoteo parcial por filas.
Recordar: Asegurar que los arreglos sean de tipo Real (float), para que no se considere el vector como entero y realice operaciones entre enteros, generando errores por truncamiento.
La parte nueva a desarrollar corresponde al procedimiento de «eliminación hacia adelante» y el procedimiento de «sustitución hacia atras».
# Método de Gauss # Solución a Sistemas de Ecuaciones # de la forma A.X=B import numpy as np # INGRESO A = np.array([[4,2,5], [2,5,8], [5,4,3]]) B = np.array([[60.70], [92.90], [56.30]]) # PROCEDIMIENTO casicero = 1e-15 # Considerar como 0 # Evitar truncamiento en operaciones A = np.array(A,dtype=float) # Matriz aumentada AB = np.concatenate((A,B),axis=1) AB0 = np.copy(AB) # Pivoteo parcial por filas tamano = np.shape(AB) n = tamano[0] m = tamano[1] # Para cada fila en AB for i in range(0,n-1,1): # columna desde diagonal i en adelante columna = abs(AB[i:,i]) dondemax = np.argmax(columna) # dondemax no está en diagonal if (dondemax !=0): # intercambia filas temporal = np.copy(AB[i,:]) AB[i,:] = AB[dondemax+i,:] AB[dondemax+i,:] = temporal AB1 = np.copy(AB) # eliminación hacia adelante for i in range(0,n-1,1): pivote = AB[i,i] adelante = i + 1 for k in range(adelante,n,1): factor = AB[k,i]/pivote AB[k,:] = AB[k,:] - AB[i,:]*factor # sustitución hacia atrás ultfila = n-1 ultcolumna = m-1 X = np.zeros(n,dtype=float) for i in range(ultfila,0-1,-1): suma = 0 for j in range(i+1,ultcolumna,1): suma = suma + AB[i,j]*X[j] b = AB[i,ultcolumna] X[i] = (b-suma)/AB[i,i] X = np.transpose([X]) # SALIDA print('Matriz aumentada:') print(AB0) print('Pivoteo parcial por filas') print(AB1) print('eliminación hacia adelante') print(AB) print('solución: ') print(X)
Tarea
Revisar cuando la matriz pivoteada por filas tienen un elemento cero o muy cercano a cero pues la matriz sería singular. El valor considerado como casi cero podría ser 1×10-15
A estas alturas, por la cantidad de líneas de instrucción es recomendable reutilizar bloques de algoritmos usando funciones def-return. Por ejemplo: pivoteo por filas, eliminación hacia adelante, sustitución hacia atrás