En savoir plus sur les méthodes de résolution de systèmes d'équations algébriques linéaires

Il est bien sûr très difficile de décrire en détail toutes les méthodes, mais ce sujet me semble intéressant et extrêmement important, car tout le monde est confronté au problème de trouver une solution assez souvent. Dans le premier article Pourquoi Gauss? la méthode de Gauss a été décrite (y compris avec des modifications) et quelques méthodes itératives. Cependant, étant donné la critique de Sinn3r , j'ai décidé de décrire également d'autres méthodes.

Recommencer

Alors, encore une fois, nous devons résoudre un système d'équations algébriques linéaires d'ordre $$$n$. L'une des méthodes numériques les plus frappantes est une méthode qui utilise $$$Lu$-décomposition de la matrice.

Cette méthode intuitive est la suivante. Supposons que nous ayons un système d'équations algébriques linéaires (écrites sous forme vectorielle):

$$

$$Ax = b,$$

où $$$A = (a_ {ij})$- une matrice non dégénérée terrible et déroutante. Nous le représentons comme le produit de deux autres matrices: $$$L = (l_ {ij})$Est une matrice triangulaire inférieure, et $$$U = (u_ {ij})$Est la matrice triangulaire supérieure. Alors évidemment le système prend la forme:

$$

$$LUx = b.$$

Si désigné $$$Ux = y$, la solution du système d'origine est trouvée à partir de la solution de deux autres systèmes:

$$

$$Ly = b,$$

$$

$$Ux = y.$$

L'avantage de cette méthode est que les solutions de deux systèmes auxiliaires sont très simples (du fait que les matrices $$$L$et $$$U$- triangulaire). Mais est-il facile de trouver ces matrices? Ainsi, la tâche de résoudre le système est réduite à la tâche de construire $$$Lu$-décompositions pour la matrice.

Description de l'algorithme d'application $$$Lu$-la décomposition est décrite de manière suffisamment détaillée ici . En attendant, nous examinerons une autre méthode.

Méthode de la racine carrée

Nous imposons des conditions supplémentaires à la matrice $$$A$. Nous exigeons qu'il soit symétrique, c'est-à-dire $$$a_ {ij} = a_ {ji}$ou $$$A ^ t = A$. Une telle matrice peut être représentée comme

$$

$$A = S ^ tDS,$$

où $$$S$- matrice triangulaire supérieure, $$$D$Est une matrice réelle diagonale, et ses éléments diagonaux sont égaux à l'unité en valeur absolue. De même, le système d'origine est réduit à deux autres:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

qui sont également résolus élémentairement en raison des propriétés des matrices $$$S$et $$$D$.

La dérivation des formules algorithmiques est assez lourde et reste au-delà du champ de publication. Si vous le souhaitez, vous pouvez les trouver ici .

Exemple de code Java qui implémente la méthode de balayage:

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éthode de balayage

En utilisant cette méthode, seuls les systèmes spécifiques avec pas plus de trois inconnues dans chaque ligne peuvent être résolus. Autrement dit, avec le système

$$

$$Ax = b$$

matrice $$$A$est 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}.$$

Notez simplement qu'il existe une connexion de solutions voisines:

$$

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

$$$\ alpha_k, \ beta_k$- quelques nombres inconnus. Si nous les trouvons et une seule variable, nous pouvons trouver toutes les autres.

Dérivation de formules

$$

$$\ 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}$$

présent ici . Eh bien, à la fin

$$

$$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, \ points, 1$$

Notez que dans les formules de recherche $$$\ alpha_i, \ beta_i$il y a une division par numéro $$$C_i - A_i \ alpha_ {i-1},$qui peut s'avérer être zéro qui doit être suivi. Mais en fait, l' énoncé suivant est vrai, la preuve en est ici : l'algorithme de balayage est correct et stable si les conditions sont remplies:

$$

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

$$

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

Considérez le code du programme Java qui résout le système.

$$

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

à $$$\ 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(); } }