Eliminación de Gauss

En álgebra lineal , eliminación de Gauss es un algoritmo que se puede utilizar para determinar las soluciones de un sistema de ecuaciones lineales , para encontrar el rango de una matriz , y para calcular la inversa de una matriz cuadrada invertible. Eliminación de Gauss se llama así por el matemático y científico alemán Carl Friedrich Gauss .

Operaciones elementales de renglón se utilizan en todo el algoritmo. El algoritmo tiene dos partes, cada una de las cuales considera las filas de la matriz en orden. La primera parte reduce la matriz para forma escalonada, mientras que el segundo se reduce aún más la matriz de forma escalonada reducida. La primera parte por sí sola es suficiente para muchas aplicaciones.

Un algoritmo relacionado, pero menos eficiente, Gauss-Jordan eliminación, trae una matriz de forma escalonada reducida en una sola pasada.

Historia

El método de eliminación de Gauss aparece en el Capítulo Ocho, rectangulares matrices, de la importancia de China texto matemático Jiuzhang suanshu o Los nueve capítulos en el arte matemático. Su uso se ilustra en dieciocho problemas, con dos a cinco ecuaciones. La primera referencia al libro de este título se fecha a 179 CE, pero partes de él fueron escritos ya en aproximadamente 150 aC.

Sin embargo, el método fue inventado en Europa de forma independiente. Lleva el nombre de la matemático Carl Friedrich Gauss .

Algoritmo visión general

El proceso de eliminación gaussiana tiene dos partes. La primera parte (Forward Eliminación) reduce un sistema dado a cualquiera triangular o forma escalonada, o resulta en un ecuación degenerada sin solución, indicando que el sistema no tiene solución. Esto se logra mediante el uso de operaciones elementales por filas. Los segundos usos de paso sustitución hacia atrás para encontrar la solución del sistema anterior.

Dicho de forma equivalente para las matrices, la primera parte se reduce a una matriz fila forma escalonada utilizando operaciones elementales por filas, mientras que el segundo lo reduce a forma escalonada reducida, o remar forma canónica.

Otro punto de vista, lo que resulta ser muy útil para analizar el algoritmo, es que la eliminación de Gauss calcula un descomposición de la matriz. Las tres operaciones elementales por filas utilizados en la eliminación de Gauss (multiplicando las filas, el cambio de filas, y añadiendo múltiplos de filas a otras filas) ascienden a multiplicar la matriz original con matrices invertibles de la izquierda. La primera parte del algoritmo calcula una LU descomposición, mientras que la segunda parte, escribe la matriz original como el producto de una matriz invertible determinado de forma única y una matriz escalonada reducida determinado de forma única.

Ejemplo

Supongamos que el objetivo es encontrar y describir la solución (s), si alguno, de la siguiente sistema de ecuaciones lineales :

El algoritmo es el siguiente: eliminar de todas las ecuaciones siguientes Y luego eliminar de todas las ecuaciones siguientes . Esto pondrá el sistema en forma triangular. Luego, utilizando sustitución regresiva, cada desconocido puede resolverse para.

En nuestro ejemplo, eliminamos desde añadiendo a Y luego eliminamos desde añadiendo a . Formalmente:

El resultado es:

Ahora eliminamos desde añadiendo a :

El resultado es:

Este resultado es un sistema de ecuaciones lineales en forma triangular, y por lo que la primera parte del algoritmo es completa.

La segunda parte, de vuelta de sustitución, consiste en resolver las incógnitas en orden inverso. Así, podemos ver fácilmente que

Luego, puede ser sustituido en , Que luego puede ser resuelto fácilmente para obtener

Siguiente, y puede ser sustituido en , Que puede ser resuelto para obtener

Así, el sistema se resuelve.

Este algoritmo funciona para cualquier sistema de ecuaciones lineales. Es posible que el sistema no puede ser reducida a una forma triangular, y aún así tener al menos una solución válida: por ejemplo, si no se había producido en y después de nuestra primera etapa anterior, el algoritmo hubiera sido incapaz de reducir el sistema a la forma triangular. Sin embargo, todavía habría reducido el sistema para forma escalonada. En este caso, el sistema no tiene una solución única, ya que contiene al menos una variable libre. El conjunto solución puede entonces ser expresada paramétricamente (es decir, en términos de las variables libres, de modo que si se eligen valores para las variables libres, se generará una solución).

En la práctica, no suele tratar con los sistemas reales en términos de ecuaciones, sino que hace uso de la matriz aumentada (que también es adecuado para la manipulación de un ordenador). Esto, entonces, es el algoritmo de Gauss Eliminación aplica a la matriz aumentada del sistema anterior, comenzando con:

que, al final de la primera parte del algoritmo es similar a esto:

Es decir, que está en forma escalonada.

Al final del algoritmo, nos quedamos con

Es decir, que está en forma escalonada reducida, o forma canónica fila.

Otras aplicaciones

Encontrar la inversa de una matriz

Suponer es un Matrix y que necesita para calcular su inversa. La matriz de identidad es aumentada a la derecha de , Formando una matriz (el matriz de bloqueo ). A través de la aplicación de las operaciones elementales de renglón y el algoritmo de eliminación de Gauss, el bloque de la izquierda de se puede reducir a la matriz de identidad , Lo que deja en el bloque de la derecha de .

Si el algoritmo no es capaz de reducir a la forma triangular, entonces no es invertible.

En la práctica, invertir una matriz casi nunca es necesaria. La mayoría del tiempo, uno es realmente después de la solución de un sistema particular de ecuaciones lineales.

El algoritmo general para calcular los rangos y bases

El algoritmo de eliminación de Gauss se puede aplicar a cualquier matriz . Si conseguimos "atascado" en una columna dada, nos movemos a la siguiente columna. De esta manera, por ejemplo, algunos matrices pueden transformarse en una matriz que tiene una forma escalonada reducida como

(Los * 's son entradas arbitrarias). Esta matriz escalonada contiene una gran cantidad de información acerca de : La rango de es 5, ya que hay 5 filas distintos de cero en ; el espacio vectorial abarcado por las columnas de tiene una base que consiste en la primera, tercera, cuarta, séptima y novena columna de (las columnas de los de ), Y la * 's indican cómo las otras columnas de se puede escribir como combinaciones lineales de las columnas básicos.

Análisis

Eliminación de Gauss en una matriz n × n requiere aproximadamente 2 n ^3/3 operaciones. Por lo tanto, tiene una complejidad de .

Este algoritmo se puede utilizar en un ordenador para sistemas con miles de ecuaciones e incógnitas. Sin embargo, el costo se convierte en prohibitivo para sistemas con millones de ecuaciones. Estos sistemas grandes se resuelven generalmente usando métodos iterativos. Existen métodos específicos para los sistemas cuyos coeficientes siguen un patrón regular (ver sistema de ecuaciones lineales ).

La eliminación de Gauss se puede realizar sobre cualquier campo.

Eliminación de Gauss es numéricamente estable para diagonalmente dominante o matrices definidas positivas. Para matrices generales, la eliminación de Gauss es generalmente considerado como estable en la práctica si se utiliza pivoteo parcial tal como se describe a continuación, aunque hay ejemplos para lo cual es inestable.

Pseudocódigo

Como se explicó anteriormente, la eliminación de Gauss escribe una determinada matriz m × n Una forma única como producto de un m × matriz invertible m S y una matriz escalonada T. Aquí, S es el producto de las matrices correspondientes a las operaciones de fila realizadas.

El algoritmo formal para calcular desde de la siguiente manera. Nosotros escribimos para la entrada en la fila , La columna en la matriz . La transformación se lleva a cabo "en el lugar", lo que significa que la matriz original se pierde y sucesivamente reemplazado por .

i := 1 j := 1 while (i ≤ m and j ≤ n) do Find pivot in column j, starting in row i: maxi := i for k := i+1 to m do if abs(A[k,j]) > abs(A[maxi,j]) then maxi := k end if end for if A[maxi,j] ≠ 0 then swap rows i and maxi, but do not change the value of i Now A[i,j] will contain the old value of A[maxi,j]. divide each entry in row i by A[i,j] Now A[i,j] will have the value 1. for u := i+1 to m do subtract A[u,j] * row i from row u Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0. end for i := i + 1 end if j := j + 1 end while 

Este algoritmo difiere ligeramente de la que se discutió anteriormente, ya que antes de eliminar una variable, primero intercambia filas para mover la entrada con el mayor valor absoluto a la "posición de pivote". Tal procedimiento pivotante mejora la estabilidad numérica del algoritmo; algunas variantes que también se utilizan.

La columna que se está transformado actualmente se llama columna pivote. Proceder de izquierda a derecha, dejando que la columna pivote sea la primera columna, a continuación, la segunda columna, etc., y finalmente la última columna antes de la línea vertical. Para cada columna pivote, hacer los dos pasos siguientes antes de pasar a la siguiente columna pivote:

1. Busque el elemento de la diagonal en la columna pivote. Este elemento se llama el pivote. La fila que contiene el pivote se llama la fila pivote. Divide cada elemento de la fila pivote por el pivote para conseguir un nuevo renglón pivote con un 1 en la posición de pivote.
2. Obtener un 0 en cada posición por debajo de la posición de pivote restando un múltiplo adecuado de la fila de pivote de cada una de las filas por debajo de ella.

Al término de este procedimiento, la matriz aumentada estará en forma escalonada y puede ser resuelto por sustitución regresiva.