Weitere Informationen zu Methoden zur Lösung linearer algebraischer Gleichungssysteme

Es ist natürlich sehr schwierig, alle Methoden im Detail zu beschreiben, aber für mich scheint dieses Thema interessant und äußerst wichtig zu sein, da jeder häufig vor der Aufgabe steht, eine Lösung zu finden. Im ersten Artikel Warum Gauß? Die Gauß-Methode wurde beschrieben (auch mit Modifikationen) und einige iterative Methoden. Angesichts der Kritik an Sinn3r habe ich mich jedoch entschlossen, auch andere Methoden zu beschreiben.

Fangen Sie von vorne an

Lassen Sie uns also noch einmal ein System linearer algebraischer Ordnungsgleichungen lösen $$$n$. Eine der auffälligsten numerischen Methoden ist eine Methode, die verwendet $$$Lu$-Zersetzung der Matrix.

Diese intuitive Methode ist wie folgt. Angenommen, wir haben ein System linearer algebraischer Gleichungen (in Vektorform geschrieben):

$$

$$Ax = b,$$

wo $$$A = (a_ {ij})$- eine schreckliche und verwirrende nicht entartete Matrix. Wir stellen es als Produkt von zwei anderen Matrizen dar: $$$L = (l_ {ij})$Ist eine untere Dreiecksmatrix und $$$U = (u_ {ij})$Ist die obere Dreiecksmatrix. Dann nimmt das System offensichtlich die Form an:

$$

$$LUx = b.$$

Wenn angegeben $$$Ux = y$, dann wird die Lösung zum ursprünglichen System aus der Lösung von zwei anderen Systemen gefunden:

$$

$$Ly = b,$$

$$

$$Ux = y.$$

Der Vorteil dieser Methode ist, dass die Lösungen zweier Hilfssysteme sehr einfach sind (aufgrund der Tatsache, dass die Matrizen $$$L$und $$$U$- dreieckig). Aber ist es einfach, diese Matrizen zu finden? Die Aufgabe, das System zu lösen, wird also auf die Aufgabe des Bauens reduziert $$$Lu$-Zersetzungen für die Matrix.

Beschreibung des anwendbaren Algorithmus $$$Lu$-Zersetzung wird hier ausreichend detailliert beschrieben. In der Zwischenzeit werden wir uns eine andere Methode ansehen.

Quadratwurzelmethode

Wir legen der Matrix zusätzliche Bedingungen auf $$$A$. Wir fordern, dass es symmetrisch ist, d.h. $$$a_ {ij} = a_ {ji}$oder $$$A ^ t = A$. Eine solche Matrix kann dargestellt werden als

$$

$$A = S ^ tDS,$$

wo $$$S$- obere Dreiecksmatrix, $$$D$Ist eine diagonale reelle Matrix, und ihre diagonalen Elemente sind im absoluten Wert gleich Eins. In ähnlicher Weise wird das ursprüngliche System auf zwei andere reduziert:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

die auch aufgrund der Eigenschaften der Matrizen elementar gelöst werden $$$S$und $$$D$.

Die Ableitung algorithmischer Formeln ist ziemlich umständlich und geht über den Umfang der Veröffentlichung hinaus. Auf Wunsch finden Sie diese hier .

Beispiel für Java-Code, der die Sweep-Methode implementiert:

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

Sweep-Methode

Mit dieser Methode können nur bestimmte Systeme mit nicht mehr als drei Unbekannten in jeder Zeile gelöst werden. Das heißt, mit dem System

$$

$$Ax = b$$

Matrix $$$A$ist 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}.$$

Beachten Sie nur, dass es eine Verbindung benachbarter Lösungen gibt:

$$

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

$$$\ alpha_k, \ beta_k$- einige unbekannte Zahlen. Wenn wir sie und eine einzelne Variable finden, können wir alle anderen finden.

Ableitung von Formeln

$$

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

hier vorhanden. Nun, am Ende

$$

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

Beachten Sie dies in den Suchformeln $$$\ alpha_i, \ beta_i$Es gibt eine Division nach Zahlen $$$C_i - A_i \ alpha_ {i-1},$Dies kann sich als Null herausstellen, die verfolgt werden muss. Tatsächlich gilt jedoch die folgende Aussage , deren Beweis hier vorliegt: Der Sweep-Algorithmus ist korrekt und stabil, wenn die Bedingungen erfüllt sind:

$$

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

$$

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

Betrachten Sie den Java-Programmcode, der das System löst.

$$

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

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