Método de Gauss

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de febrero de 2022; las comprobaciones requieren 6 ediciones .

El método de Gauss es un método clásico para resolver un sistema de ecuaciones algebraicas lineales (SLAE). Nombrado en honor al matemático alemán Carl Friedrich Gauss . Este es un método de eliminación sucesiva de variables , cuando, con la ayuda de transformaciones elementales, se reduce el sistema de ecuaciones a un sistema equivalente de tipo triangular, a partir del cual se encuentran secuencialmente todas las variables del sistema, comenzando por la última. (por número) [1] .

Historia

Aunque este método ahora se conoce comúnmente como el método de Gauss, se conocía antes de C. F. Gauss. La primera descripción conocida de este método se encuentra en el tratado chino Matemáticas en nueve libros.

Descripción del método

Deje que el sistema original se vea así:

\left\{{\begin{array}{lcr}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_ {m1}x_{1}+\ldots +a_{mn}x_{n}&=&b_{m}\\\end{matriz}}\right.

Se puede escribir en forma matricial :

hacha = b,

dónde

A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\ldots &&\\a_{m1}&\ldots &a_{mn}\end{array }}\right),\quad x=\left({\begin{array}{c}x_{1}\\\vdots \\x_{n}\end{array}}\right),\quad b= \left({\begin{matriz}{c}b_{1}\\\vdots \\b_{m}\end{matriz}}\right).\quad (1)

La matriz se llama matriz principal del sistema, la columna de miembros libres. $A$ $b$

Entonces, de acuerdo con la propiedad de las transformaciones elementales sobre filas, la matriz principal de este sistema se puede reducir a una forma escalonada (las mismas transformaciones se deben aplicar a la columna de miembros libres):

\left\{{\begin{matriz}{rcl}\alpha _{1j_{1}}x_{j_{1}}+\alpha _{1j_{2}}x_{j_{2}}+ \ldots +\alpha _{1j_{r}}x_{j_{r}}+\ldots +\alpha _{1j_{n}}x_{j_{n}}&=&\beta _{1}\\ \alpha _{2j_{2}}x_{j_{2}}+\ldots +\alpha _{2j_{r}}x_{j_{r}}+\ldots +\alpha _{2j_{n}}x_ {j_{n}}&=&\beta _{2}\\&\ldots &\\\alpha _{rj_{r}}x_{j_{r}}+\ldots +\alpha _{rj_{n }}x_{j_{n}}&=&\beta _{r}\\0&=&\beta _{r+1}\\&\ldots &\\0&=&\beta _{m}\end {matriz}}\derecho.,

dónde $\alpha _{1j_{1}},\ldots,\alpha _{rj_{r}}\neq 0.$

En este caso, supondremos que el menor básico ( menor de orden máximo distinto de cero ) de la matriz principal está en la esquina superior izquierda, es decir, incluye solo los coeficientes de las variables [2] . $x_{j_{1}},\ldots,x_{j_{r}}$

Las variables se denominan entonces variables principales . Todos los demás se llaman libres . $x_{j_{1}},\ldots,x_{j_{r}}$

Si al menos un número , donde , entonces el sistema en consideración es inconsistente , es decir, no tiene una solución única. ${\ estilo de visualización \ beta _ {i} \ neq 0}$ $yo > r$

Deja para cualquier . ${\ estilo de visualización \ beta _ {i} = 0}$ $yo > r$

Transferimos las variables libres más allá de los signos de igual y dividimos cada una de las ecuaciones del sistema por su coeficiente en la más a la izquierda ( , donde es el número de la fila): $X$ $\alpha _{ij_{i}},\,i=1,\ldots,r$ $i$

\left\{\begin{matriz}{rcc} x_{j_1}+\widehat{\alpha}_{1j_2}x_{j_2}+\ldots+\widehat{\alpha}_{1j_r}x_{j_r}&= & \widehat{\beta}_1-\widehat{\alpha}_{1j_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{1j_n}x_{j_n } \\ x_{j_2}+\ldots+\widehat{\alpha}_{2j_r}x_{j_r}&=& \widehat{\beta}_2-\widehat{\alpha}_{2j_{r+1)) x_{j_{r+1}}-\ldots- \widehat{\alpha}_{2j_n}x_{j_n} \\ &\ldots& \\ x_{j_r}&=& \widehat{\beta}_r-\ widehat{\alpha}_{rj_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{rj_n}x_{j_n} \\ \end{matriz}\right ., \qquad \widehat{\beta}_i=\frac{\beta_i}{\alpha_{ij_i)),\quad \widehat{\alpha}_{ij_k}=\frac{\alpha_{ij_k)){\ alfa_{ij_i}}\quad (2)

dónde $i=1,\ldots,r,\quad k=i+1,\ldots,n.$

Si a las variables libres del sistema (2) se les dan todos los valores posibles y se resuelve el nuevo sistema con respecto a las principales incógnitas de abajo hacia arriba (es decir, de la ecuación inferior a la superior), entonces obtendremos todas las soluciones de esta SLAE . Como este sistema se obtuvo por transformaciones elementales sobre el sistema original (1), entonces por el teorema de equivalencia bajo transformaciones elementales, los sistemas (1) y (2) son equivalentes, es decir, los conjuntos de sus soluciones coinciden.

Consecuencias:
1: Si en un sistema conjunto todas las variables son principales, entonces dicho sistema es definitivo.

2: Si el número de variables en el sistema excede el número de ecuaciones, entonces dicho sistema es indeterminado o inconsistente.

Criterio de consistencia

La condición anterior para todos se puede formular como condición necesaria y suficiente para la compatibilidad: ${\ estilo de visualización \ beta _ {i} = 0}$ $yo > r$

Recuérdese que el rango de un sistema conjunto es el rango de su matriz principal (o extendida, ya que son iguales).

Teorema de Kronecker-Capelli .
Un sistema es consistente si y solo si el rango de su matriz principal es igual al rango de su matriz extendida.

Consecuencias:

El número de variables principales es igual al rango del sistema y no depende de su solución.
Si el rango de un sistema compatible es igual al número de variables de este sistema, entonces está definido.

Algoritmo

El diagrama de bloques se muestra en la figura. Esta figura está adaptada para escribir un programa en C/C++, donde a es una matriz aumentada, cuya última columna es una columna de miembros libres. El número de líneas es n.

Descripción

El algoritmo para la resolución de SLAE por el método de Gauss se divide en dos etapas.

En la primera etapa, se lleva a cabo el llamado movimiento directo, cuando, mediante transformaciones elementales sobre filas, se lleva el sistema a una forma escalonada o triangular , o se establece que el sistema es inconsistente. Para ello, entre los elementos de la primera columna de la matriz, se elige uno distinto de cero, la fila que lo contiene se desplaza a la posición superior, haciendo de esta fila la primera. Además, los elementos distintos de cero de la primera columna de todas las filas subyacentes se ponen a cero restando la primera fila de cada fila, multiplicando por la proporción del primer elemento de estas filas al primer elemento de la primera fila. Una vez realizadas las transformaciones indicadas, se tachan mentalmente la primera fila y la primera columna y se continúa hasta que quede una matriz de tamaño cero. Si en algunas de las iteraciones entre los elementos de la primera columna no se encontró uno distinto de cero, vaya a la siguiente columna y realice una operación similar.
En la segunda etapa, se lleva a cabo el llamado movimiento inverso, cuya esencia es expresar todas las variables básicas resultantes en términos de no básicas y construir un sistema fundamental de soluciones , o, si todas las variables son básicas, luego exprese numéricamente la única solución al sistema de ecuaciones lineales. Este procedimiento comienza con la última ecuación, a partir de la cual se expresa la variable básica correspondiente (y allí sólo hay una) y se sustituye en las ecuaciones anteriores, y así sucesivamente, subiendo los "pasos". Cada línea corresponde exactamente a una variable básica, por lo que en cada paso, a excepción del último (superior), la situación repite exactamente el caso de la última línea.

El método de Gauss requiere operaciones aritméticas. $O(n^{3})$

Este método se basa en:

Teorema (sobre la reducción de matrices a una forma escalonada).
Cualquier matriz por transformaciones elementales solo sobre filas se puede reducir a una forma escalonada.

El caso más simple

En el caso más simple, el algoritmo se ve así:

\left\{\begin{matriz}{lcc} a_{11} \cdot x_1 + a_{12} \cdot x_2 + \ldots + a_{1n} \cdot x_n & = b_1 & (1) \\ a_{21 } \cdot x_1 + a_{22} \cdot x_2 + \ldots + a_{2n} \cdot x_n & = b_2 & (2) \\ \ldots & & \\ a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + \ldots + a_{mn} \cdot x_n & = b_m & (m) \end{matriz}\right.

Movimiento directo:

\begin{array}{ccc} (2)\to (2)-(1) \cdot ( \frac {a_{21}}{a_{11}}) &:& a_{22}^{\prime} \cdot x_2 + a_{23}^{\prime} \cdot x_3 + \ldots + a_{2n}^{\prime} \cdot x_n = b_2^{\prime} \\ (3)\to (3)- (1) \cdot ( \frac {a_{31}}{a_{11))) &:& a_{32}^{\prime} \cdot x_2 + a_{33}^{\prime} \cdot x_3 + \ldots + a_{3n}^{\prime} \cdot x_n = b_3^{\prime} \\ \ldots & & \\ (m)\to (m)-(1) \cdot ( \frac {a_{ m1)){a_{11))) &:& a_{m2}^{\prime} \cdot x_2 + a_{m3}^{\prime} \cdot x_3 + \ldots + a_{mn}^{\prime } \cdot x_n = b_n^{\prime} \\ (3)\to (3)-(2) \cdot ( \frac {a_{32}^{\prime)){a_{22}^{\prime ))) &:& a_{33}^{\prime\prime} \cdot x_3 + \ldots + a_{3n}^{\prime\prime} \cdot x_n = b_3^{\prime\prime} \\ \ ldots & & \\ (m)\to (m)-(m-1) \cdot ( \frac {a_{m,n-1}^{(m-2)}}{a_{m-1,n -1}^{(m-2)}}) &:& a_{mm}^{(m-1)} \cdot x_m + \ldots + a_{mn}^{(m-1)} \cdot x_n = b_m^{(m-1)} \end{matriz}

Movimiento inverso. A partir de la última ecuación distinta de cero, expresamos la variable básica en términos de las no básicas y la sustituimos en las ecuaciones anteriores. Repitiendo este procedimiento para todas las variables básicas, obtenemos la solución fundamental.

Ejemplo

Veamos cómo se puede resolver el siguiente sistema por el método de Gauss:

\left\{\begin{matriz}{ccc}2x + y - z &=& 8 \\ -3x - y + 2z &=& -11 \\ -2x + y + 2z &=& -3 \end{ matriz}\derecho.

Establezca los coeficientes en cero en la segunda y tercera fila. Para hacer esto, agrégueles la primera línea, multiplicada por y , respectivamente: $X$ ${\ estilo de visualización \ estilo de texto {\ frac {3} {2}}}$ $una$

\left\{\begin{matriz}{rcc} 2x + y - z &=& 8 \\ \frac{1}{2}y + \frac{1}{2}z &=& 1 \\ 2y + z &=& 5 \end{matriz}\right.

Ahora restablecemos el coeficiente en la tercera fila, restándole la segunda fila multiplicada por : $y$ $cuatro$

\left\{\begin{matriz}{rcc} 2x + y - z &=& 8 \\ \frac{1}{2} y + \frac{1}{2} z &=& 1 \\ -z &=& 1 \\ \end{matriz}\right.

Como resultado, reducimos el sistema original a una forma triangular , completando así la primera etapa del algoritmo.

En la segunda etapa, resolvemos las ecuaciones obtenidas en orden inverso. Tenemos:

{\ estilo de visualización z = -1}

del tercero;

{\ estilo de visualización y = 3}

del segundo, sustituyendo el resultante

z

x=2

del primero, sustituyendo el obtenido y .

z

y

Por lo tanto, el sistema original está resuelto.

Si el número de ecuaciones en el sistema conjunto resultó ser menor que el número de incógnitas, la respuesta se escribirá en forma de un sistema fundamental de soluciones .

Implementación del algoritmo en el lenguaje de programación C#

espacio de nombres Gauss_Method { clase de matemáticas { /// <resumen> /// Método de Gauss (solución SLAE) /// </resumen> /// <param name="Matrix">Matriz inicial</param> /// <devoluciones></devoluciones> público estático doble [] Gauss ( doble [,] Matriz ) { int n = Matriz . ObtenerLongitud ( 0 ); //Dimensión de la matriz inicial (fila) doble [,] Matrix_Clone = nuevo doble [ n , n + 1 ]; //matriz duplicadora para ( int i = 0 ; i < n ; i ++) para ( int j = 0 ; j < n + 1 ; j ++) Matrix_Clone [ i , j ] = Matriz [ i , j ]; // Movimiento hacia adelante (Poniendo a cero la esquina inferior izquierda) for ( int k = 0 ; k < n ; k ++) //número de línea k { for ( int i = 0 ; i < n + 1 ; i ++) //número de columna i Matrix_Clone [ k , i ] = Matrix_Clone [ k , i ] / Matrix [ k , k ]; //Dividiendo la cadena k por el primer miembro !=0 para convertirlo en uno for ( int i = k + 1 ; i < n ; i ++) //i-número de la siguiente línea después de k { doble K = Matrix_Clone [ i , k ] / Matrix_Clone [ k , k ]; //Coeficiente for ( int j = 0 ; j < n + 1 ; j ++) // número de columna j de la siguiente línea después de k Matrix_Clone [ i , j ] = Matrix_Clone [ i , j ] - Matrix_Clone [ k , j ] * K ; // Poner a cero los elementos de la matriz debajo del primer miembro convertido a uno } for ( int i = 0 ; i < n ; i ++) //Actualizar, realizar cambios en la matriz inicial para ( int j = 0 ; j < n + 1 ; j ++) Matriz [ i , j ] = Matrix_Clone [ i , j ]; } // Movimiento inverso (Poniendo a cero la esquina superior derecha) for ( int k = n - 1 ; k > - 1 ; k --) //k-número de línea { for ( int i = n ; i > - 1 ; i --) //número de columna i Matrix_Clone [ k , i ] = Matrix_Clone [ k , i ] / Matrix [ k , k ]; for ( int i = k - 1 ; i > - 1 ; i --) //i-número de la siguiente línea después de k { doble K = Matrix_Clone [ i , k ] / Matrix_Clone [ k , k ]; for ( int j = n ; j > - 1 ; j --) //número de columna j de la siguiente línea después de k Matrix_Clone [ i , j ] = Matrix_Clone [ i , j ] - Matrix_Clone [ k , j ] * K ; } } // Separar las respuestas de la matriz general doble [] Respuesta = nuevo doble [ n ]; para ( int i = 0 ; i < n ; i ++) Respuesta [ i ] = Matrix_Clone [ i , n ]; devolver respuesta ; } } }

Aplicaciones y modificaciones

Además de la solución analítica de SLAE , el método Gaussiano también se aplica a:

encontrar una matriz inversa a la dada (a la matriz de la derecha se le asigna una matriz unitaria del mismo tamaño que la original: , después de lo cual se reduce a la forma de una matriz identidad por el método de Gauss-Jordan ; como como resultado, la inversa de la matriz original aparece a la derecha en lugar de la matriz identidad original: ); ${\ estilo de visualización [A|E]}$ $A$ ${\ estilo de visualización [E|A^{-1}]}$
determinar el rango de una matriz (según el corolario del teorema de Kronecker-Capelli, el rango de una matriz es igual al número de sus principales variables);
solución numérica de SLAE en aplicaciones técnicas (para reducir el error de cálculo, se utiliza el Método de Gauss con la selección del elemento principal, cuya esencia es elegir en cada paso como la variable principal aquella en la que entre las filas y columnas restante después de la eliminación, existe el coeficiente de módulo máximo).

Ventajas del método

Para matrices de tamaño limitado, consume menos tiempo en comparación con otros métodos.
Le permite determinar sin ambigüedades si el sistema es compatible o no, y si es compatible, encontrar su solución.
Le permite encontrar el número máximo de ecuaciones linealmente independientes: el rango de la matriz del sistema [3] .

Estabilidad del método de Gauss

El método de Gauss para matrices de coeficientes mal acondicionados es computacionalmente inestable . Por ejemplo, para matrices de Hilbert, el método conduce a errores muy grandes incluso para dimensiones pequeñas de estas matrices. Puede reducir el error de cálculo utilizando el método de Gauss con la selección del elemento principal, que es condicionalmente estable [4] . El uso generalizado del método gaussiano se debe al hecho de que las matrices mal condicionadas son relativamente raras en la práctica.

No-optimalidad del método gaussiano

En 1969, Strassen demostró que las matrices grandes se pueden multiplicar en el tiempo [5] . Esto implica que la inversión de matriz y la solución SLAE pueden implementarse mediante algoritmos que son asintóticamente más rápidos que el método de Gauss. Por lo tanto, para grandes SLAE, el método gaussiano no es óptimo en términos de velocidad. $O(n^{\log _{2}{7)))=O(n^{2{,}81})$

Véase también

Notas

↑ N. Sh. Kremer , 2.3. "Método de Gauss", página 44
↑ Tal disposición del menor se puede lograr reorganizando las columnas de la matriz principal y renumerando las variables correspondientemente.
↑ N. Sh. Kremer , 2.4. "Sistema de m ecuaciones lineales con n variables", pág. 49
↑ ESTABILIDAD Y PRECISIÓN DE LOS MÉTODOS DIRECTOS (enlace inaccesible)
↑ Strassen V. La eliminación gaussiana no es óptima // Numer . Matemáticas / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, edición. 4.- Pág. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411

Literatura

I. M. Vinogradov. Método de Gauss // Enciclopedia Matemática. — M.: Enciclopedia soviética . - 1977-1985. (Ruso)
Ilyin V. A., Poznyak E. G. Álgebra lineal: un libro de texto para escuelas secundarias . - 6ª ed., borrada. - M. : FIZMATLIT, 2004. - 280 p.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Métodos computacionales para ingenieros. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Métodos numéricos. - 8ª edición. |lugar=M. |editor=Laboratorio de Conocimientos Básicos |año=2000 |paginas= |isbn=}}
Volkov E. A. Métodos numéricos. — M. : Fizmatlit, 2003.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Matemáticas superiores para economistas / Ed. N. Sh. Kremer. - 3ra ed. - M. : UNITI-DANA, 2007. - 479 p. — ISBN 5-238-00991-7 .

Enlaces

Prensa, WH; Teukolsky, SA; Vetterling, WT & Flannery, BP (2007), Sección 2.2 , Recetas numéricas: El arte de la informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8

diccionarios y enciclopedias	Gran danés
En catálogos bibliográficos	TIERRA : 4156110-7

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento