Que ferez-vous si on vous demande de résoudre un système simple à trois inconnues? Chacun a formé sa propre approche et la plus pratique pour lui personnellement. Il existe de nombreuses façons de résoudre un système d'équations algébriques linéaires. Mais pourquoi la préférence est-elle donnée spécifiquement à la méthode de Gauss?
Tout d'abord
Commençons par un simple. Soit un système d'équations linéaires du troisième ordre:
$$ afficher $$ \ gauche \ {\ commencer {aligné} 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 {aligné} \ à droite. $$ display $$
La méthode de Gauss consiste à «détruire» séquentiellement les termes sous la diagonale principale. Dans la première étape, la première équation est multipliée par
$ inline $ \ dfrac {a_ {21}} {a_ {11}} $ inline $ et soustrait de la seconde (et de même multiplié par
$ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ et soustrait du troisième). Autrement dit, après cette conversion, nous obtenons ce qui suit:
$$ afficher $$ \ gauche \ {\ commencer {aligné} 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 {aligné} \ à droite. $$ display $$
Maintenant, la deuxième équation est multipliée par
$ inline $ \ dfrac {a_ {32} '} {a_ {22}'} $ inline $ et soustrait du troisième:
$$ afficher $$ \ gauche \ {\ commencer {aligné} 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 {aligné} \ à droite. $$ display $$
Nous avons un système assez simple, à partir duquel il est facile de trouver
$ en ligne $ x_3 $ en ligne $ alors
$ en ligne $ x_2 $ en ligne $ et
$ en ligne $ x_1 $ en ligne $ .
Un lecteur attentif remarquera certainement: et si les éléments diagonaux sont égaux à zéro? Que faire si, par exemple,
$ inline $ a_ {11} = 0 $ inline $ ? La fameuse méthode Gauss s'arrête-t-elle là?
Rien à craindre! Trouvons
$ inline $ \ max | a_ {1j} | $ inline $ et échanger
$ en ligne $ j $ en ligne $ e et première rangée (sans perte de généralité, supposons que
$ en ligne $ \ max | a_ {1j} | = a_ {13} $ en ligne $ ) Notez que le cas où tout
$ inline $ a_ {1j} = 0 $ inline $ cela ne peut pas l'être, car dans ce cas le déterminant de la matrice de coefficients disparaît et il n'est pas possible de résoudre le système. Ainsi, après avoir réorganisé la 3e équation sur la première ligne, nous effectuons les étapes décrites précédemment.
La recherche de l'élément modulo maximum peut être effectuée à chaque itération, c'est-à-dire à
$ en ligne $ k $ en ligne $ -th itération à rechercher
$ inline $ \ max | a_ {kj} | $ inline $ puis changez
$ en ligne $ j $ en ligne $ et
$ en ligne $ k $ en ligne $ e ligne. L'algorithme dans lequel l'élément maximum dans la colonne est recherché est appelé la méthode de Gauss avec le choix de l'élément principal dans la colonne.
Il y a une autre façon. Peut sur
$ en ligne $ k $ en ligne $ -th itération à rechercher
$ inline $ \ max | a_ {ik} | $ inline $ , puis modifiez non pas les lignes, mais les colonnes. Mais il est important de se rappeler les indices des colonnes changeantes dans un tableau
$ inline $ \ alpha $ inline $ (puis pour rétablir l'ordre exact des variables).
Un exemple de code simple qui implémente cet algorithme:
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];
Pourquoi Gauss?
Il existe une autre façon de résoudre SLAE. L'un d'eux est la méthode Cramer. Il consiste dans le calcul préalable d'un certain nombre de déterminants, à l'aide desquels les valeurs des variables sont instantanément calculées. Sous le système d'origine, cette méthode ressemblera à ceci:
$$ afficher $$ \ Delta = \ begin {vmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \\ a_ {31} & a_ {32} & a_ {33} \\ \ end {vmatrix}, \ Delta_1 = \ begin {vmatrix} b_1 & a_ {12} & a_ {13} \\ b_2 & a_ {22} & a_ {23} \ \ b_3 & a_ {32} & a_ {33} \\ \ end {vmatrix}, $$ display $$
$$ afficher $$ \ 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} & a_ {32 } & b_3 \\ \ end {vmatrix}, $$ display $$
$$ afficher $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ afficher $$
Mais rappelez-vous - qu'est-ce qu'un qualificatif?
Par définition, le déterminant d'une matrice
$ inline $ A = (a_ {ij}) $ inline $ il y a un montant
$$ afficher $$ \ 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}, $$ afficher $$
où
$ inline $ N (i_1, \ dots, i_n) $ inline $ - caractère générique
$ inline $ i_1, \ dots, i_n. $ inline $
Le déterminant contient
$ inline $ n! $ inline $ termes. Pour résoudre le système, vous devez compter
$ en ligne $ n + 1 $ en ligne $ déterminants. À suffisamment grand
$ en ligne $ n $ en ligne $ c'est très cher. Par exemple, lorsque
$ en ligne $ n = 12 $ en ligne $ le nombre d'opérations devient
$ en ligne 12 $! (12 + 1) = 6227020800, $ en ligne $ tandis que la méthode de Gauss avec asymptotique
$ en ligne $ n ^ 3 $ en ligne $ ne nécessitera que
$ en ligne $ 12 ^ 3 = 1728 $ en ligne $ opérations.
Méthodes itératives
Les méthodes dites itératives conviennent également comme algorithmes pour résoudre les SLAE. Ils consistent à calculer séquentiellement les approximations jusqu'à ce que l'une d'elles soit aussi proche que possible de la réponse exacte.
Tout d'abord, un vecteur arbitraire est sélectionné
$ en ligne $ x ^ 0 $ en ligne $ Est une approximation nulle. Le vecteur est construit dessus.
$ en ligne $ x ^ 1 $ en ligne $ - c'est la première approximation. Et ainsi de suite. Les calculs se terminent lorsque
$ inline $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ inline $ où
$ inline $ \ varepsilon $ inline $ - une valeur définie à l'avance. La dernière inégalité signifie que notre «amélioration» de la solution à chaque itération est presque insignifiante.
Considérez la méthode Jacobi populaire, qui est l'une des méthodes itératives les plus simples pour résoudre les SLAE.
Pour commencer, nous écrivons le système sous la forme suivante:
$$ affiche $$ \ sum \ limits_ {j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n}. $$ afficher $$
Séparé
$ en ligne $ i $ en ligne $ -ème terme et l'exprimer à travers tout le reste:
$$ affiche $$ x_i = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}. $$ display $ $
Maintenant, accrochez les «compteurs» sur les variables et obtenez la méthode d'itération Jacobi:
$$ afficher $$ 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, \ dots. $$ afficher $$
Notez qu'une condition préalable à l'utilisation de cette méthode est l'absence de zéros le long de la diagonale principale.
Implémentation de la méthode Jacobi en Java:
En tant que $ inline $ \ varepsilon $ inline $ une soi-disant machine epsilon pré-calculée est prise. 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; } }
Une modification de la méthode Jacobi est la méthode de relaxation. Sa principale différence est qu'à l'aide d'un paramètre présélectionné, le nombre d'itérations est considérablement réduit. Décrivons brièvement l'idée principale de la méthode.
A partir du système d'origine, nous exprimons à nouveau
$ en ligne $ x $ en ligne $ , mais configurons les compteurs un peu différemment et ajoutons le paramètre
$ inline $ \ omega $ inline $ :
$$ afficher $$ 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 \ droite)} {a_ {ii}} + (1- \ oméga) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ points. $$ afficher $$
À
$ inline $ \ omega = 1 $ inline $ tout se transforme en méthode Jacobi.
Donc, nous chercherons des «bons»
$ inline $ \ omega $ inline $ . Définir un certain nombre
$ inline $ s $ inline $ et nous prendrons des valeurs
$ inline $ \ omega \ in (0,2) $ inline $ , pour chacune desquelles nous considérerons les normes
$ inline $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s} $ inline $ . Pour la plus petite de ces normes, rappelez-vous cette valeur
$ inline $ \ omega $ inline $ , et avec lui, nous allons résoudre notre système.
Illustration de la méthode Java:
ici $ en ligne $ s = 5 $ en ligne $ 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; } }
Au lieu d'une conclusion
Il existe de nombreux autres algorithmes pour résoudre SLAE. Par exemple, la méthode de la racine carrée, dans laquelle le système souhaité est remplacé par deux systèmes "simples", dont les solutions sont calculées par des formules élémentaires; méthode de balayage, qui est utilisée pour des matrices tridiagonales si spécifiques. Chacun choisit la méthode à utiliser pour son problème.