Más información sobre métodos para resolver sistemas de ecuaciones algebraicas lineales

Por supuesto, es muy difícil contar en detalle sobre todos los métodos, pero este tema me parece interesante y extremadamente importante, ya que todos se enfrentan con el problema de encontrar una solución con bastante frecuencia. En el primer artículo ¿Por qué Gauss? Se describió el método de Gauss (incluso con modificaciones) y algunos métodos iterativos. Sin embargo, dada la crítica de Sinn3r , decidí describir también otros métodos.

Empezar de nuevo

Entonces, de nuevo necesitamos resolver un sistema de ecuaciones de orden algebraicas lineales $$$n$. Uno de los métodos numéricos más llamativos es un método que utiliza $$$Lu$-descomposición de la matriz.

Este método intuitivo es el siguiente. Supongamos que tenemos un sistema de ecuaciones algebraicas lineales (escritas en forma de vector):

$$

$$Ax = b,$$

donde $$$A = (a_ {ij})$- una matriz no degenerada terrible y confusa. Lo representamos como el producto de otras dos matrices: $$$L = (l_ {ij})$Es una matriz triangular inferior, y $$$U = (u_ {ij})$Es la matriz triangular superior. Entonces, obviamente, el sistema toma la forma:

$$

$$LUx = b.$$

Si designado $$$Ux = y$, entonces la solución para el sistema original se encuentra a partir de la solución de otros dos sistemas:

$$

$$Ly = b,$$

$$

$$Ux = y.$$

La ventaja de este método es que las soluciones de dos sistemas auxiliares son muy simples (debido al hecho de que las matrices $$$L$y $$$U$- triangular). ¿Pero es fácil encontrar estas matrices? Entonces, la tarea de resolver el sistema se reduce a la tarea de construir $$$Lu$-descomposiciones para la matriz.

Descripción del algoritmo que aplica $$$Lu$-descomposición se describe con suficiente detalle aquí . Mientras tanto, veremos otro método.

Método de raíz cuadrada

Imponemos condiciones adicionales en la matriz. $$$A$. Requerimos que sea simétrico, es decir $$$a_ {ij} = a_ {ji}$o $$$A ^ t = A$. Dicha matriz se puede representar como

$$

$$A = S ^ tDS,$$

donde $$$S$- matriz triangular superior, $$$D$Es una matriz real diagonal, y sus elementos diagonales son iguales a la unidad en valor absoluto. Del mismo modo, el sistema original se reduce a otros dos:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

que también se resuelven elementalmente debido a las propiedades de las matrices $$$S$y $$$D$.

La derivación de fórmulas algorítmicas es bastante engorrosa y permanece más allá del alcance de la publicación. Si lo desea, se pueden encontrar aquí .

Ejemplo de código Java que implementa el método de barrido:

import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SquareRootMethod { public static void main(String[] args) throws FileNotFoundException { Scanner scanner = new Scanner(new FileReader("input.txt")); scanner.useLocale(Locale.US); int n = scanner.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] = scanner.nextDouble(); } b[i] = scanner.nextDouble(); } double[] x = new double[n + 1]; double[] d = new double[n + 1]; double[][] s = new double[n + 1][n + 1]; // for i = 1 d[1] = Math.signum(a[1][1]); s[1][1] = Math.sqrt(Math.abs(a[1][1])); for (int j = 2; j <= n; j++) { s[1][j] = a[1][j] / (s[1][1] * d[1]); } // for i > 1 //searching S and D matrix for (int i = 2; i <= n; i++) { double sum = 0; for (int k = 1; k <= i - 1; k++) { sum += s[k][i] * s[k][i] * d[k]; } d[i] = Math.signum(a[i][i] - sum); s[i][i] = Math.sqrt(Math.abs(a[i][i] - sum)); double l = 1 / (s[i][i] * d[i]); for (int j = i + 1; j <= n; j++) { double SDSsum = 0; for (int k = 1; k <= i - 1; k++) { SDSsum += s[k][i] * d[k] * s[k][j]; } s[i][j] = l * (a[i][j] - SDSsum); } } //solve of the system (s^t * d)y = b double[] y = new double[n + 1]; y[1] = b[1] / (s[1][1] * d[1]); for (int i = 2; i <= n; i++) { double sum = 0; for (int j = 1; j <= i - 1; j++) { sum += s[j][i] * d[j] * y[j]; } y[i] = (b[i] - sum) / (s[i][i] * d[i]); } //solve of the system sx = y x[n] = y[n] / s[n][n]; for (int i = n - 1; i >= 1; i--) { double sum = 0; for (int k = i + 1; k <= n; k++) { sum += s[i][k] * x[k]; } x[i] = (y[i] - sum) / s[i][i]; } //output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } } 

Método de barrido

Con este método, solo se pueden resolver sistemas específicos con no más de tres incógnitas en cada fila. Es decir, con el sistema

$$

$$Ax = b$$

matriz $$$A$es tridiagonal:

$$

$$A = \ begin {pmatrix} C_1 & -B_1 & 0 & \ dots & 0 & 0 \\ -A_2 & C_2 & -B_2 & \ dots & 0 & 0 \\ \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots \\ 0 & 0 & \ dots & -A_ {n-1} & C_ {n-1} & -B_ {n-1} \\ 0 & 0 & \ dots & 0 & -A_n & C_n \\ \ end {pmatrix}. $$$

Solo tenga en cuenta que hay una conexión de soluciones vecinas:

$$

$$x_ {i-1} = \ alpha_ {i-1} x_i + \ beta_ {i-1},$$

$$$\ alpha_k, \ beta_k$- Algunos números desconocidos. Si los encontramos y una sola variable, podemos encontrar todos los demás.

Derivación de fórmulas.

$$

$$\ alpha_1 = \ dfrac {B_1} {C_1}, \ \ alpha_i = \ dfrac {B_i} {C_i - A_i \ alpha_ {i-1}}, \ i = \ overline {2, n},$$

$$

$$\ beta_1 = \ dfrac {b_1} {C_1}, \ \ beta_i = \ dfrac {b_i + A_i \ beta_ {i-1}} {C_i - A_i \ alpha_ {i-1}}, \ i = \ overline { 2, n}$$

presente aquí Bueno al final

$$

$$x_n = \ dfrac {b_n + A_n \ beta_ {n-1}} {C_n - A_n \ alpha_ {n-1}}, \ x_i = \ alpha_i x_ {i + 1} + \ beta_i, \ i = n- 1, n-2, \ puntos, 1$$

Tenga en cuenta que en las fórmulas de búsqueda $$$\ alpha_i, \ beta_i$hay una división por número $$$C_i - A_i \ alpha_ {i-1},$que puede llegar a ser cero y necesita ser rastreado. Pero, de hecho, se cumple la siguiente declaración , cuya prueba está aquí : el algoritmo de barrido es correcto y estable si se cumplen las condiciones:

$$

$$C_1, C_n \ neq 0, A_i, B_i \ neq 0 \ (i = \ overline {2, n}),$$

$$

$$| C_i | \ geq | A_i | + | B_i |.$$

Considere el código del programa Java que resuelve el sistema.

$$

$$\ left \ {\ begin {alineado} & x_1 = 0, \\ & x_ {i-1} + \ xi x_ {i + 1} = \ dfrac {i} {n}, \ (i = \ overline {2, n-1}), \\ & x_n = 1, \\ \ end {alineado} \ right.$$

a las $$$\ xi = 2, n = 21$.

 package SystemOfLinearAlgebraicEquations; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class TridiagonalMatrixAlgorithm { public static void main(String[] args) throws FileNotFoundException { final int n = 21; double[] A = new double[n + 1]; double[] B = new double[n + 1]; double[] C = new double[n + 1]; double[] F = new double[n + 1]; double xi = 2; C[1] = 1; F[1] = 0; for(int i = 2; i <= n-1; i++) { A[i] = 1; C[i] = xi; B[i] = 1; F[i] = - (double) i / n; } A[n] = 0; C[n] = 1; F[n] = 1; double[] alpha = new double[n + 1]; double[] beta = new double[n + 1]; // right stroke alpha[1] = B[1] / C[1]; beta[1] = F[1] / C[1]; for (int i = 2; i <= n - 1; i++) { double denominator = C[i] - A[i] * alpha[i-1]; alpha[i] = B[i] / denominator; beta[i] = (F[i] + A[i] * beta[i - 1]) / denominator; } double[] x = new double[n + 1]; // back stroke x[n] = (F[n] + A[n] * beta[n - 1]) / (C[n] - A[n] * alpha[n - 1]); for (int i = n - 1; i >= 1; i--) { x[i] = alpha[i] * x[i + 1] + beta[i]; } // output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i = i + 5) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } }