Contenido Checked

Eliminaci贸n de Gauss

Temas relacionados: Matem谩ticas

Acerca de este escuelas selecci贸n Wikipedia

Esta selecci贸n Escuelas fue originalmente elegido por SOS para las escuelas en el mundo en desarrollo que no tienen acceso a Internet. Est谩 disponible como una descarga intranet. SOS Children ha cuidado de ni帽os en 脕frica durante cuarenta a帽os. 驴Puedes ayudar a su trabajo en 脕frica ?

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 :

2x + y - z = 8 \ quad (L_1)
3x - y + 2z = -11 \ quad (L_2)
-2x + Y + 2z = -3 \ quad (L_3)

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

En nuestro ejemplo, eliminamos x desde L_2 a帽adiendo \ Begin {matriz} \ frac {3} {2} \ end {matriz} L_1 a L_2 Y luego eliminamos x desde L_3 a帽adiendo L_1 a L_3 . Formalmente:

L_2 + \ frac {3} {2} L_1 \ rightarrow L_2
L_3 + L_1 \ rightarrow L_3

El resultado es:

2x + y - z = 8 \,
\ Frac {1} {2} y + \ frac {1} {2} z = 1 \,
2y + z = 5 \,

Ahora eliminamos y desde L_3 a帽adiendo -4L_2 a L_3 :

L_3 + -4L_2 \ rightarrow L_3

El resultado es:

2x + y - z = 8 \,
\ Frac {1} {2} y + \ frac {1} {2} z = 1 \,
-z = 1 \,

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

z = -1 \ quad (L_3)

Luego, z puede ser sustituido en L_2 , Que luego puede ser resuelto f谩cilmente para obtener

y = 3 \ quad (L_2)

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

x = 2 \ quad (L_1)

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 y no se hab铆a producido en L_2 y L_3 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:

\ Begin {bmatrix} 2 y 1 y -1 y 8 \\ -3 y -1 y 2 y -11 \\ -2 y 1 y 2 y -3 \ end {bmatrix}

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

\ Begin {bmatrix} 2 y 1 y -1 y 8 \\ 0 & \ frac {1} {2} & \ frac {1} {2} y 1 \\ 0 & 0 & -1 y 1 \ end {bmatrix }

Es decir, que est谩 en forma escalonada.

Al final del algoritmo, nos quedamos con

\ Begin {bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 y -1 \ end {bmatrix}

Es decir, que est谩 en forma escalonada reducida, o forma can贸nica fila.

Otras aplicaciones

Encontrar la inversa de una matriz

Suponer La es un n \ n veces Matrix y que necesita para calcular su inversa. La n \ n veces matriz de identidad es aumentada a la derecha de La , Formando una n \ 茅pocas 2n matriz (el matriz de bloqueo B = [A, I] ). 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 B se puede reducir a la matriz de identidad YO , Lo que deja A ^ {- 1} en el bloque de la derecha de B .

Si el algoritmo no es capaz de reducir La a la forma triangular, entonces La 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 m \ times n matriz La . Si conseguimos "atascado" en una columna dada, nos movemos a la siguiente columna. De esta manera, por ejemplo, algunos 6 \ 9 veces matrices pueden transformarse en una matriz que tiene una forma escalonada reducida como

\ Begin {bmatrix} 1 & * y 0 & 0 & * & * & * y 0 y 0 \\ 0 & 0 & 1 & 0 & * & * & * y 0 y 0 \\ 0 & 0 & 0 & 1 & * & * & * y 0 y 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & * y 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ end {bmatrix}

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

An谩lisis

Eliminaci贸n de Gauss en una matriz nn requiere aproximadamente 2 n 3/3 operaciones. Por lo tanto, tiene una complejidad de \ Mathcal {O} (n ^ 3) \, .

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 mn 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 T desde La de la siguiente manera. Nosotros escribimos A [i, j] para la entrada en la fila yo , La columna j en la matriz La . La transformaci贸n se lleva a cabo "en el lugar", lo que significa que la matriz original La se pierde y sucesivamente reemplazado por T .

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.

Recuperado de " http://en.wikipedia.org/w/index.php?title=Gaussian_elimination&oldid=199193881 "