Einfach und praktisch! Die von drei Deutschen entwickelte lineare Iterationsmethode übertraf eine Ära

Am 26. Dezember dieses Jahres jährt sich die Erfindung des ersten linearen Iterationsverfahrens der Geschichte durch den deutschen Mathematiker Gauss zum 200. Mal. Im kürzlich veröffentlichten Artikel „Wie löst man iterativ ein lineares Gleichungssystem?“ gingen wir von den Grundkonzepten aus und erläuterten die vorbereitenden Kenntnisse und den spezifischen Prozess der iterativen Methode zum Lösen linearer Gleichungen. Dieses Mal werden wir die Grundideen und die Konvergenz der beiden berühmtesten, einfachsten und praktischsten stationären Iterationsverfahren erster Ordnung in der Geschichte untersuchen: das Jacobi-Iterationsverfahren und das Gauss-Seidel-Iterationsverfahren.

Geschrieben von Ding Jiu (Professor für Mathematik an der University of Southern Mississippi)

In meinem vorherigen Artikel über Fanpu: „Wie löst man iterativ ein System linearer Gleichungen?“ Um es mit dem auf allgemeine vollständige Distanzräume anwendbaren Kontraktionsabbildungssatz zu verknüpfen, wird nur eine einfache, konvergenzausreichende Methode zur Lösung linearer Gleichungen durch Iteration angegeben.

Viele Wege führen nach Rom

Glücklicherweise stehen uns andere Normen zur Verfügung. Als direkte Verallgemeinerung des üblichen Begriffs der Streckenlänge ist der n-dimensionale euklidische Raum

Eigenwerte und Spektralradius

Es gibt jedoch eine notwendige und hinreichende Voraussetzung für die Konvergenz, die es zu erforschen gilt. Diese Bedingung verwendet nicht mehr die Norm der Matrix, sondern das Spektrum der Matrix. Das Spektrum gibt eine intrinsische Eigenschaft einer Matrix an, die unabhängig von ihrer Norm ist. Das Spektrum einer quadratischen Matrix ist eine endliche Menge komplexer Zahlen, die aus allen ihren Eigenwerten besteht. Bei einer gegebenen quadratischen Matrix M der Ordnung n nennen wir die komplexe Zahl λ einen Eigenwert von M, wenn die komplexe Matrix M – λI nicht invertierbar ist, das heißt, es gibt einen komplexen, von Null verschiedenen Spaltenvektor x, sodass Mx = λx. Dieses x wird als Eigenvektor von M bezeichnet, der dem Eigenwert λ entspricht. Wir haben erwähnt, dass eine Matrix genau dann singulär ist, wenn ihre Determinante Null ist, also ist λ genau dann ein Eigenwert von M, wenn det(M – λI) = 0, wobei das Symbol det die Determinante bezeichnet. Wenn wir λ auf der linken Seite dieser Gleichung als Variable betrachten, ist das Erweiterungsergebnis von det(M – λI) gemäß der Definition der Determinante ein Polynom n-ter Ordnung um λ, sodass eine quadratische Matrix n-ter Ordnung M höchstens n verschiedene Eigenwerte hat. Den maximalen Absolutwert aller Eigenwerte von M nennen wir den Spektralradius von M, bezeichnet mit ρ(M).

Der Hauptzweck der Untersuchung der linearen Iteration besteht darin, das lineare Gleichungssystem Ax = b numerisch zu lösen, wobei die Koeffizientenmatrix A nicht singulär ist.

Umgekehrt gilt: Wenn ρ(M) < 1, dann existiert eine ausreichend kleine positive Zahl ε, sodass ρ(M) + ε < 1. Diese scheinbar einfache Tatsache ist eine grundlegende Eigenschaft reeller Zahlen. Andererseits gilt für jeden Eigenwert λ von M und jede Norm ||•|| Auf Rn sei x ein Eigenvektor, der λ entspricht. Aus der Ungleichung ||M|| ||x|| ≥ ||Mx|| = ||λx|| = |λ| ||x|| und x ≠ 0, können wir sehen, dass beide Seiten der gerade erhaltenen Ungleichung durch die positive Zahl ||x|| geteilt werden können, und wir erhalten die Ungleichung ||M|| ≥ |λ|, daher können wir sehen, dass der Spektralradius ρ(M) der Matrix M eine Untergrenze für den Wert ||M|| ist. der Matrixnorm, die durch alle Vektornormen in M ​​induziert wird. Tatsächlich ist diese Untergrenze das „Infimum“ der reellen Zahlenmenge, die allen Normwerten ||M|| entspricht. der festen Matrix M, d. h. die „maximale Untergrenze“ unter allen Untergrenzen dieser Menge. Das Konzept der „oberen und unteren Grenzen“ ist das grundlegendste und wichtigste Konzept in der Infinitesimalrechnung. Wenn man sie wirklich beherrscht, können die Grenzwerttheorie und die sich daraus ergebenden Konzepte wie Kontinuität, Ableitungen, Integrale, Reihen usw. sogar leicht erlernt werden.

Jacobi-Iterationsverfahren und Gauss-Seidel-Iterationsverfahren

Wir können uns nun auf die Jacobi- und Gauss-Seidel-Methoden zur Lösung des linearen Systems Ax = b konzentrieren, wobei A eine reversible Matrix der Ordnung n ist. Diese beiden klassischen iterativen Verfahren aus Deutschland basieren auf der speziellen Auswahl von N und P in der Matrixzerlegung A = N - P. Ihre iterativen Formate können wie folgt geschrieben werden:

Vergleichen wir die wesentlichen Unterschiede zwischen der Jacobi-Methode und der Gauss-Seidel-Methode im iterativen Punktkomponentenberechnungsprozess. Aus der Iterationsformel der n Komponenten in der Jacobi-Iterationsmethode ist ersichtlich, dass nach der Berechnung aller Komponenten des k-1. Iterationsvektors die Komponenten des k-ten Iterationsvektors einzeln berechnet werden. Mit anderen Worten werden alle in der k-1-ten Iteration erhaltenen Komponenten zur Berechnung aller Komponenten der k-ten Iteration verwendet. Bei der Gauss-Seidel-Iterationsmethode werden, wenn die i-te Komponente des k-ten Iterationsvektors berechnet werden muss, nicht nur die i+1- bis n-te Komponente des berechneten k-1-ten Iterationsvektors als Hilfe benötigt, sondern auch die 1- bis i-1-te Komponente des k-ten Iterationsvektors, der in der aktuellen Iteration erhalten wurde. Mit anderen Worten ist das Gauss-Seidel-Verfahren „erfolgshungriger“ als das Jacobi-Verfahren und befiehlt der Iterationspunktkomponente, die gerade im aktuellen Iterationsschritt erfasst wurde, dieselbe Indexkomponente zu ersetzen, die im vorherigen Iterationsschritt „erfasst“ wurde, und „in die Schlacht zu ziehen“. Dies zeigt, dass Gauß und Seidl besser darin waren, Truppen „einzusetzen“ als Jacobi und nicht bereit waren, Moral zu verschwenden.

Konvergenzbedingungen

Natürlich können weder die Jacobi-Iterationsmethode noch die Gauss-Seidel-Iterationsmethode Konvergenz ohne bestimmte zusätzliche Annahmen bezüglich der Matrix A garantieren. Wenn also die Voraussetzung erfüllt ist, dass „die Diagonalelemente von A nicht Null sein können“, was ist dann die ausreichende Bedingung, um ihre Konvergenz sicherzustellen?

Hier kann die Anforderung der strikten Diagonaldominanz zur Gewährleistung der Konvergenz der Jacobi-Iterationsmethode in eine irreduzible schwache Diagonaldominanz geändert werden, d. h. alle oben genannten strengen Ungleichungen werden durch allgemeine Ungleichungen "≥" ersetzt, und mindestens eine Ungleichung ist streng gültig, es wird jedoch die zusätzliche Bedingung der Matrix-Irreduzibilität hinzugefügt. Wenn die Zeilen und Spalten einer quadratischen Matrix auf die gleiche Weise neu angeordnet werden können (das Nicht-Neuanordnen wird auch als „Neuanordnung“ betrachtet, da die Identitätsmatrix auch eine Permutationsmatrix ist), wird das Ergebnis eine obere Dreiecksmatrix mit 2 × 2 Blöcken, d. h. die untere linke Ecke der Matrix hat mindestens eine 1 × 1-Nullmatrix, dann sagen wir, dass die Matrix reduzierbar ist, andernfalls heißt sie irreduzibel.

Wenn A eine streng diagonal dominante Matrix ist, ist die ∞-Norm der Gauss-Seidel-Iterationsmatrix nicht größer als die ∞-Norm der Jacobi-Iterationsmatrix. Je kleiner diese Norm ist, desto schneller ist normalerweise die Konvergenzgeschwindigkeit. Daher ist die erstere Methode hinsichtlich der Konvergenzgeschwindigkeit der letzteren Methode nicht unterlegen.

Als letzten mathematischen Höhepunkt dieses Artikels präsentieren wir einen weiteren einzigartigen Konvergenzsatz der Gauss-Seidel-Methode:

Wenn die Koeffizientenmatrix A des linearen Systems Ax = b symmetrisch positiv definit ist, dann konvergiert das Gauss-Seidel-Iterationsverfahren.

Ende

Die Fackel der linearen Iterationsmethode, die vor zweihundert Jahren von deutschen Mathematikern entzündet wurde, überquerte hundert Jahre später den Ozean und wurde auf den amerikanischen Kontinent gebracht, wo die Technologie boomte und Computer geboren wurden. Um die Iterationseffizienz zu optimieren, führten der amerikanische Mathematiker und Informatiker David M. Young Jr. (1923–2008, „Fanpu“ stellt ihn separat vor) und der amerikanische Physiker und Informatiker Stanley Phillips Frankel (1919–1978) 1950, ausgehend vom klassischen Gauss-Seidel-Verfahren, fast gleichzeitig einen Relaxationsfaktor ω für eine Art affine Kombination ein, was zur „Methode der sukzessiven Überrelaxation (SOR)“ führte. Ersterer schlug die SOR-Methode in seiner Doktorarbeit Iterative Methods for Solving Partial Difference Equations of Elliptic Type an der Harvard University vor; Letzterer veröffentlichte im Journal of the American Mathematical Society (zehn Jahre später in Mathematics of Computation umbenannt) eine Abhandlung mit dem Titel Convergence rates of iterative treatments of partial differential equations, in der er eine umfassende Analyse der von ihm entwickelten und „Extrapolated Liebmann method“ genannten SOR-Methode durchführte. Diese beiden bahnbrechenden Studien, in denen die SOR-Methode vorgeschlagen wurde, beziehen sich beide auf partielle Differentialgleichungen, die in Wissenschaft und Technik häufig vorkommen. Wenn elektronische Computer zum Lösen großer, dünner linearer Gleichungen verwendet werden, die durch Diskretisierung dieser kontinuierlichen Gleichungen erhalten werden, sind iterative Methoden die erste Wahl. Dies ist die Ära, in der die SOR-Methode entstand.

Wenn der Relaxationsfaktor ω den Wert 1 annimmt, reduziert sich die SOR-Methode auf die Gauss-Seidel-Methode. Wir werden nicht näher auf diese Methode eingehen und diesen Artikel hier beenden, da wir die Grundidee des Konvergenzkriteriums linearer iterativer Methoden bereits durch das Verständnis zweier klassischer iterativer Methoden kennen. Zusammenfassend lässt sich sagen, dass die Erfindungen dreier deutscher Mathematiker im 19. Jahrhundert die Quelle der modernen Forschungswelle zu iterativen Lösungen großer, dünner, strukturierter linearer Gleichungssysteme sind.

Geschrieben am Sonntag, 19. November 2023, Summer Hills, Hattiesburg, USA

Dieser Artikel wird vom Science Popularization China Starry Sky Project unterstützt

Produziert von: Chinesische Vereinigung für Wissenschaft und Technologie, Abteilung für Wissenschaftspopularisierung

Hersteller: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Besondere Tipps

1. Gehen Sie zur „Featured Column“ unten im Menü des öffentlichen WeChat-Kontos „Fanpu“, um eine Reihe populärwissenschaftlicher Artikel zu verschiedenen Themen zu lesen.

2. „Fanpu“ bietet die Funktion, Artikel nach Monat zu suchen. Folgen Sie dem offiziellen Account und antworten Sie mit der vierstelligen Jahreszahl + Monat, also etwa „1903“, um den Artikelindex für März 2019 zu erhalten, usw.

Copyright-Erklärung: Einzelpersonen können diesen Artikel gerne weiterleiten, es ist jedoch keinem Medium und keiner Organisation gestattet, ihn ohne Genehmigung nachzudrucken oder Auszüge daraus zu verwenden. Für eine Nachdruckgenehmigung wenden Sie sich bitte an den Backstage-Bereich des öffentlichen WeChat-Kontos „Fanpu“.