¿Por qué gauss? (100 formas de resolver el sistema de ecuaciones)

¿Qué hará si se le pide que resuelva un sistema simple con tres incógnitas? Cada uno ha formado su propio enfoque y el más conveniente para él personalmente. Hay muchas formas de resolver un sistema de ecuaciones algebraicas lineales. Pero, ¿por qué se da preferencia específicamente al método Gauss?

Primero lo primero

Comencemos con uno simple. Sea un sistema de ecuaciones lineales de tercer orden:

$$$$ display $$ \ left \ {\ begin {alineado} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {21} x_1 + a_ {22} x_2 + a_ { 23} x_3 = b_2, \\ a_ {31} x_1 + a_ {32} x_2 + a_ {33} x_3 = b_3. \\ \ end {alineado} \ right. $$ display $$

El método de Gauss consiste en "destruir" secuencialmente los términos debajo de la diagonal principal. En el primer paso, la primera ecuación se multiplica por$$ $ en línea $ \ dfrac {a_ {21}} {a_ {11}} $ en línea $ y restado del segundo (y multiplicado de manera similar por$$ $ en línea $ \ dfrac {a_ {31}} {a_ {11}} $ en línea $ y restado del tercero). Es decir, después de esta conversión, obtenemos lo siguiente:

$$$$ display $$ \ left \ {\ begin {alineado} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {22} 'x_2 + a_ {23}' x_3 = b_2 ', \\ a_ {32}' x_2 + a_ {33} 'x_3 = b_3'. \\ \ end {alineado} \ right. $$ display $$

Ahora la segunda ecuación se multiplica por$$ $ en línea $ \ dfrac {a_ {32} '} {a_ {22}'} $ en línea $ y restado del tercero:

$$$$ display $$ \ left \ {\ begin {alineado} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {22} 'x_2 + a_ {23}' x_3 = b_2 ', \\ a_ {33}' 'x_3 = b_3' '. \\ \ end {alineado} \ right. $$ display $$

Tenemos un sistema bastante simple, desde el cual es fácil de encontrar$$ $ en línea $ x_3 $ en línea $ entonces$$ $ en línea $ x_2 $ en línea $ y$$ $ en línea $ x_1 $ en línea $ .

Un lector atento definitivamente se dará cuenta: ¿qué pasa si los elementos diagonales son iguales a cero? Qué hacer si, por ejemplo,$$ $ en línea $ a_ {11} = 0 $ en línea $ ? ¿El famoso método de Gauss termina ahí?

¡Nada de qué preocuparse! Vamos a encontrar$$ $ en línea $ \ max | a_ {1j} | $ en línea $ e intercambiar$$ $ en línea $ j $ en línea $ th y primera fila (sin pérdida de generalidad, supongamos que$$ $ en línea $ \ max | a_ {1j} | = a_ {13} $ en línea $ ) Tenga en cuenta que el caso cuando todo$$ $ en línea $ a_ {1j} = 0 $ en línea $ no puede serlo, ya que en este caso el determinante de la matriz de coeficientes desaparece y no es posible resolver el sistema. Entonces, después de reorganizar la 3a ecuación en la primera línea, realizamos los pasos descritos anteriormente.

La búsqueda del elemento de módulo máximo se puede tratar en cada iteración, es decir, en$$ $ en línea $ k $ en línea $ -th iteración a buscar$$ $ en línea $ \ max | a_ {kj} | $ en línea $ luego cambiar$$ $ en línea $ j $ en línea $ y$$ $ en línea $ k $ en línea $ th line. El algoritmo en el que se busca el elemento máximo en la columna se llama método Gauss con la elección del elemento principal en la columna.

Hay otra manera Puede en$$ $ en línea $ k $ en línea $ -th iteración a buscar$$ $ en línea $ \ max | a_ {ik} | $ en línea $ , luego no cambie las filas, sino las columnas. Pero es importante recordar los índices de las columnas cambiantes en alguna matriz$$ $ en línea $ \ alpha $ en línea $ (luego para restaurar el orden exacto de las variables).

Un ejemplo de un código simple que implementa este algoritmo:

import java.io.FileReader; import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.Locale; import java.util.Scanner; public class GuassianEliminationSearchMainElementsAtString { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; // input for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); } int[] alpha = new int[n + 1]; // array of indices for (int i = 1; i <= n; i++) { alpha[i] = i; } for (int m = 1; m <= n; m++) { double max = Math.abs(a[m][m]); int count = m; for (int i = m + 1; i <= n; i++) { if (Math.abs(a[m][i]) > max) { // search max elements at the string max = Math.abs(a[m][i]); count = i; } } int tmp = alpha[m]; // swap strings alpha[m] = alpha[count]; alpha[count] = tmp; for (int i = m; i <= n; i++) { double tmp2 = a[i][m]; a[i][m] = a[i][count]; a[i][count] = tmp2; } for (int i = m + 1; i <= n; i++) { // guassian right stroke b[i] = b[i] - a[i][m] * b[m] / a[m][m]; for (int j = m + 1; j < n; j++) { a[i][j] = a[i][j] - a[i][m] * a[m][j] / a[m][m]; } } } // for m double[] x = new double[n+1]; for (int i = n; i >= 1; i--) { // guassian back stroke double sum = 0; for (int j = i + 1; j <= n; j++) { sum += a[i][j] * x[alpha[j]]; } x[alpha[i] - 1] = (b[i] - sum) / a[i][i]; } // output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 0; i < n; i++) { pw.printf(Locale.US, "x%d = %.5f \n", i + 1, x[i]); } pw.flush(); pw.close(); } } 

¿Por qué gauss?

Hay otra forma de resolver SLAE. Uno de ellos es el método Cramer. Consiste en el cálculo preliminar de un cierto número de determinantes, con la ayuda de los cuales se calculan instantáneamente los valores de las variables. Bajo el sistema original, este método se verá así:

$$$$ display $$ \ Delta = \ begin {vmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \\ a_ {31} & a_ {32} y a_ {33} \\ \ end {vmatrix}, \ Delta_1 = \ begin {vmatrix} b_1 y a_ {12} y a_ {13} \\ b_2 y a_ {22} y a_ {23} \ \ b_3 & a_ {32} & a_ {33} \\ \ end {vmatrix}, $$ display $$

$$$$ display $$ \ Delta_2 = \ begin {vmatrix} a_ {11} & b_1 & a_ {13} \\ a_ {21} & b_2 & a_ {23} \\ a_ {31} & b_3 & a_ {33} \\ \ end {vmatrix}, \ Delta_3 = \ begin {vmatrix} a_ {11} & a_ {12} & b_1 \\ a_ {21} & a_ {22} & b_2 \\ a_ {31} y a_ {32 } & b_3 \\ \ end {vmatrix}, $$ display $$

$$$$ display $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ display $$

Pero recuerde: ¿qué es un calificador?

Por definición, el determinante de una matriz$$ $ en línea $ A = (a_ {ij}) $ en línea $ hay una cantidad

$$$$ display $$ \ sum \ limits_ {1 \ leq i_1 <\ dots <i_n \ leq n} (-1) ^ {N (i_1, \ dots, i_n)} a_ {1i_1} \ dots a_ {ni_n}, $$ display $$

donde$$ $ en línea $ N (i_1, \ dots, i_n) $ en línea $ - comodín$$ $ en línea $ i_1, \ puntos, i_n. $ en línea $

El determinante contiene$$ $ en línea $ n! $ en línea $ términos Para resolver el sistema, debes contar$$ $ en línea $ n + 1 $ en línea $ determinantes En suficientemente grande$$ $ en línea $ n $ en línea $ Es muy caro. Por ejemplo, cuando$$ $ en línea $ n = 12 $ en línea $ el número de operaciones se convierte$$ $ en línea $ 12! (12 + 1) = 6227020800, $ en línea $ mientras que el método de Gauss con asintóticas$$ $ en línea $ n ^ 3 $ en línea $ solo requerirá$$ $ en línea $ 12 ^ 3 = 1728 $ en línea $ operaciones

Métodos iterativos

Los llamados métodos iterativos también son adecuados como algoritmos para resolver SLAEs. Consisten en calcular secuencialmente las aproximaciones hasta que una de ellas esté lo más cerca posible de la respuesta exacta.

Primero, se selecciona un vector arbitrario$$ $ en línea $ x ^ 0 $ en línea $ Es una aproximación cero. Se construye un vector sobre él.$$ $ en línea $ x ^ 1 $ en línea $ - Esta es la primera aproximación. Y así sucesivamente. Los cálculos terminan cuando$$ $ en línea $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ en línea $ donde$$ $ en línea $ \ varepsilon $ en línea $ - algún valor establecido de antemano. La última desigualdad significa que nuestra "mejora" de la solución con cada iteración es casi insignificante.

Considere el popular método Jacobi, que es uno de los métodos iterativos más simples para resolver SLAEs.

Para comenzar, escribimos el sistema de la siguiente forma:

$$$$ display $$ \ sum \ limits_ {j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n}. $$ display $$

Por separado$$ $ en línea $ i $ en línea $ -th term y expresarlo a través de todo lo demás

$$$$ display $$ x_i = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}. $$ display $ $ $

Ahora simplemente cuelgue los "contadores" en las variables y obtenga el método de iteración de Jacobi:

$$$$ display $$ x_i ^ k = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}}, \ i = \ overline {1, n}, \ k = 0,1, \ puntos. $$ display $$

Tenga en cuenta que un requisito previo para usar este método es la ausencia de ceros a lo largo de la diagonal principal.

Implementación del método Jacobi en Java:
Como un$$ $ en línea $ \ varepsilon $ en línea $ Se toma una máquina precalculada llamada épsilon.

 import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class JacobiMethod { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; double[] x0 = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); x0[i] = b[i] / a[i][i]; } double EPS = EPSCalc(); double[] x = new double[n+1]; double norm = Double.MAX_VALUE; int counter = 0; do{ for(int i = 1; i <= n; i++) { double sum = 0; for(int j = 1; j <= n; j++) { if(j == i) continue; sum += a[i][j] * x0[j]; } x[i] = (b[i] - sum) / a[i][i]; } norm = normCalc(x0, x, n); for(int i = 1; i <= n; i++) { x0[i] = x[i]; } counter++; } while(norm > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x0[i]); } pw.flush(); pw.close(); } static double normCalc(double []x1, double[] x2, int n) { double sum = 0; for(int i = 1; i <= n; i++) { sum += Math.abs(x1[i] - x2[i]); } return sum; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } } 

Una modificación del método de Jacobi es el método de relajación. Su principal diferencia es que con la ayuda de un parámetro preseleccionado, el número de iteraciones se reduce significativamente. Describamos brevemente la idea principal del método.

Del sistema original, expresamos nuevamente$$ $ en línea $ x $ en línea $ , pero configuremos los contadores un poco diferente y agreguemos el parámetro$$ $ en línea $ \ omega $ en línea $ :

$$$$ display $$ x_i ^ k = \ dfrac {\ omega \ left (b_i - \ sum \ limits_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k + 1} - \ sum \ limits_ {j = i + 1} ^ n a_ {ij} x_j ^ k \ right)} {a_ {ii}} + (1- \ omega) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ puntos. $$ display $$

En$$ $ en línea $ \ omega = 1 $ en línea $ todo se convierte en un método de Jacobi.

Por lo tanto, buscaremos algunos "buenos"$$ $ en línea $ \ omega $ en línea $ . Establecer un número$$ $ en línea $ s $ en línea $ y tomaremos valores$$ $ en línea $ \ omega \ en (0,2) $ en línea $ , para cada uno de los cuales consideraremos las normas$$ $ en línea $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s} $ en línea $ . Para la más pequeña de estas normas, recuerde este valor$$ $ en línea $ \ omega $ en línea $ , y con ello resolveremos nuestro sistema.

Ilustración del método Java:
aqui$$ $ en línea $ s = 5 $ en línea $

 import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SuccessiveOverRelaxation { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); } double EPS = EPSCalc(); double w = bestRelaxationParameterCalc(a, b, n); double[] x = new double[n + 1]; int counter = 0; double maxChange = Double.MAX_VALUE; do { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm ; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } counter++; } while(maxChange > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(w + " is the best relaxation parameter"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } static double bestRelaxationParameterCalc(double[][]a, double[]b, int n) { double bestW = 1, bestMaxChange = Double.MAX_VALUE; for (double w = 0.05; w <= 2; w += 0.05) { double[] x = new double[n + 1]; double maxChange = 0; for (int s = 0; s < 5; s++) { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } } if (maxChange < bestMaxChange) { bestMaxChange = maxChange; bestW = w; } } return bestW; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } } 

En lugar de una conclusión

Hay muchos más algoritmos para resolver SLAE. Por ejemplo, el método de raíz cuadrada, en el que el sistema deseado se reemplaza por dos sistemas "simples", cuyas soluciones se calculan mediante fórmulas elementales; Método de barrido, que se utiliza para matrices tridiagonales tan específicas. Todos eligen qué método usar para su problema.