Was werden Sie tun, wenn Sie aufgefordert werden, ein einfaches System mit drei Unbekannten zu lösen? Jeder hat seinen eigenen und bequemsten Ansatz für ihn persönlich entwickelt. Es gibt viele Möglichkeiten, ein System linearer algebraischer Gleichungen zu lösen. Aber warum wird die Gauß-Methode speziell bevorzugt?
Das Wichtigste zuerst
Beginnen wir mit einem einfachen. Es sei ein lineares Gleichungssystem dritter Ordnung gegeben:
$$ display $$ \ left \ {\ begin {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} \ right. $$ display $$
Die Gauß-Methode besteht darin, die Terme unterhalb der Hauptdiagonale nacheinander zu "zerstören". Im ersten Schritt wird die erste Gleichung mit multipliziert
$ inline $ \ dfrac {a_ {21}} {a_ {11}} $ inline $ und von der Sekunde subtrahiert (und auf ähnliche Weise multipliziert mit
$ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ und vom dritten abgezogen). Das heißt, nach dieser Konvertierung erhalten wir Folgendes:
$$ display $$ \ left \ {\ begin {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} \ right. $$ display $$
Nun wird die zweite Gleichung mit multipliziert
$ inline $ \ dfrac {a_ {32} '} {a_ {22}'} $ inline $ und vom dritten abgezogen:
$$ display $$ \ left \ {\ begin {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} \ right. $$ display $$
Ich habe ein ziemlich einfaches System, das Sie leicht finden können
$ inline $ x_3 $ inline $ dann
$ inline $ x_2 $ inline $ und
$ inline $ x_1 $ inline $ .
Ein aufmerksamer Leser wird auf jeden Fall bemerken: Was ist, wenn die diagonalen Elemente gleich Null sind? Was tun, wenn zum Beispiel
$ inline $ a_ {11} = 0 $ inline $ ? Endet die berühmte Gauß-Methode dort?
Nichts Schlimmes! Lass uns finden
$ inline $ \ max | a_ {1j} | $ inline $ und tauschen
$ inline $ j $ inline $ th und erste Reihe (ohne Verlust der Allgemeinheit, nehmen wir an, dass
$ inline $ \ max | a_ {1j} | = a_ {13} $ inline $ ) Beachten Sie, dass der Fall, wenn alles
$ inline $ a_ {1j} = 0 $ inline $ es kann nicht sein, da in diesem Fall die Determinante der Koeffizientenmatrix verschwindet und es nicht möglich ist, das System zu lösen. Nachdem wir die 3. Gleichung in der ersten Zeile neu angeordnet haben, führen wir die zuvor beschriebenen Schritte aus.
Die Suche nach dem maximalen Modulo-Element kann bei jeder Iteration durchgeführt werden, d. H. Bei
$ inline $ k $ inline $ -th Iteration zu suchen
$ inline $ \ max | a_ {kj} | $ inline $ dann ändern
$ inline $ j $ inline $ und
$ inline $ k $ inline $ th Zeile. Der Algorithmus, in dem das maximale Element in der Spalte gesucht wird, wird als Gauß-Methode mit der Auswahl des Hauptelements in der Spalte bezeichnet.
Es gibt noch einen anderen Weg. Kann weiter
$ inline $ k $ inline $ -th Iteration zu suchen
$ inline $ \ max | a_ {ik} | $ inline $ Ändern Sie dann nicht die Zeilen, sondern die Spalten. Es ist jedoch wichtig, sich die Indizes der sich ändernden Spalten in einem Array zu merken
$ inline $ \ alpha $ inline $ (dann, um die genaue Reihenfolge der Variablen wiederherzustellen).
Ein Beispiel für einen einfachen Code, der diesen Algorithmus implementiert:
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];
Warum Gauß?
Es gibt einen anderen Weg, um SLAE zu lösen. Eine davon ist die Cramer-Methode. Es besteht in der vorläufigen Berechnung einer bestimmten Anzahl von Determinanten, mit deren Hilfe die Werte der Variablen sofort berechnet werden. Unter dem ursprünglichen System sieht diese Methode folgendermaßen aus:
$$ display $$ \ 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 $$
$$ 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} & a_ {32 } & b_3 \\ \ end {vmatrix}, $$ display $$
$$ display $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ display $$
Aber denken Sie daran - was ist ein Qualifier?
Per Definition die Determinante einer Matrix
$ inline $ A = (a_ {ij}) $ inline $ Es gibt einen Betrag
$$ Anzeige $$ \ Summe \ Grenzen_ {1 \ leq i_1 <\ Punkte <i_n \ leq n} (-1) ^ {N (i_1, \ Punkte, i_n)} a_ {1i_1} \ Punkte a_ {ni_n}, $$ Anzeige $$
wo
$ inline $ N (i_1, \ dots, i_n) $ inline $ - Platzhalter
$ inline $ i_1, \ dots, i_n. $ inline $
Die Determinante enthält
$ inline $ n! $ inline $ Begriffe. Um das System zu lösen, müssen Sie zählen
$ inline $ n + 1 $ inline $ Determinanten. Ausreichend groß
$ inline $ n $ inline $ es ist sehr teuer. Zum Beispiel wenn
$ inline $ n = 12 $ inline $ Die Anzahl der Operationen wird
$ inline $ 12! (12 + 1) = 6227020800, $ inline $ während die Gauß-Methode mit Asymptotik
$ inline $ n ^ 3 $ inline $ wird nur erfordern
$ inline $ 12 ^ 3 = 1728 $ inline $ Operationen.
Iterative Methoden
Sogenannte iterative Methoden eignen sich auch als Algorithmen zur Lösung von SLAEs. Sie bestehen darin, die Näherungen nacheinander zu berechnen, bis eine von ihnen der genauen Antwort so nahe wie möglich kommt.
Zunächst wird ein beliebiger Vektor ausgewählt
$ inline $ x ^ 0 $ inline $ Ist eine Nullnäherung. Darauf wird ein Vektor aufgebaut.
$ inline $ x ^ 1 $ inline $ - Dies ist die erste Annäherung. Usw. Die Berechnungen enden wann
$ inline $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ inline $ wo
$ inline $ \ varepsilon $ inline $ - einen eingestellten Wert im Voraus. Die letzte Ungleichung bedeutet, dass unsere „Verbesserung“ der Lösung mit jeder Iteration nahezu unbedeutend ist.
Betrachten Sie die beliebte Jacobi-Methode, eine der einfachsten iterativen Methoden zum Lösen von SLAEs.
Zunächst schreiben wir das System in der folgenden Form:
$$ Anzeige $$ \ Summe \ Grenzen_ {j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n}. $$ Anzeige $$
Trennen
$ inline $ i $ inline $ -th Begriff und drücken Sie es durch alles andere aus:
$$ display $$ x_i = \ dfrac {b_i - \ sum \ limit_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}. $$ display $ $
Hängen Sie nun einfach die "Zähler" an die Variablen und erhalten Sie die Jacobi-Iterationsmethode:
$$ display $$ x_i ^ k = \ dfrac {b_i - \ sum \ limit_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}}, \ i = \ overline {1, n}, \ k = 0,1, \ Punkte. $$ Anzeige $$
Beachten Sie, dass eine Voraussetzung für die Verwendung dieser Methode das Fehlen von Nullen entlang der Hauptdiagonale ist.
Implementierung der Jacobi-Methode in Java:
Als $ inline $ \ varepsilon $ inline $ es wird ein vorberechnetes sogenanntes maschinen-epsilon genommen. 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; } }
Eine Modifikation der Jacobi-Methode ist die Relaxationsmethode. Der Hauptunterschied besteht darin, dass mit Hilfe eines vorgewählten Parameters die Anzahl der Iterationen erheblich reduziert wird. Lassen Sie uns kurz die Hauptidee der Methode beschreiben.
Aus dem ursprünglichen System drücken wir noch einmal aus
$ inline $ x $ inline $ , aber lassen Sie uns die Zähler etwas anders einrichten und den Parameter hinzufügen
$ inline $ \ omega $ inline $ ::
$$ display $$ x_i ^ k = \ dfrac {\ omega \ left (b_i - \ sum \ limit_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k + 1} - \ sum \ limit_ {j = i + 1} ^ n a_ {ij} x_j ^ k \ right)} {a_ {ii}} + (1- \ omega) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ dots. $$ display $$
Bei
$ inline $ \ omega = 1 $ inline $ alles wird zu einer Jacobi-Methode.
Also werden wir nach etwas „Gutem“ suchen
$ inline $ \ omega $ inline $ . Stellen Sie eine Nummer ein
$ inline $ s $ inline $ und wir werden Werte nehmen
$ inline $ \ omega \ in (0,2) $ inline $ , für die wir jeweils die Normen berücksichtigen werden
$ inline $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s} $ inline $ . Denken Sie bei der kleinsten dieser Normen an diesen Wert
$ inline $ \ omega $ inline $ und damit lösen wir unser System.
Abbildung der Java-Methode:
hier $ inline $ s = 5 $ inline $ 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; } }
Anstelle einer Schlussfolgerung
Es gibt viel mehr Algorithmen zum Lösen von SLAE. Zum Beispiel die Quadratwurzelmethode, bei der das gewünschte System durch zwei "einfache" Systeme ersetzt wird, deren Lösungen durch Elementarformeln berechnet werden; Sweep-Methode, die für so spezifische tridiagonale Matrizen verwendet wird. Jeder wählt die Methode für sein Problem.