Einfache Iterationsmethode zur Lösung linearer Gleichungssysteme (Slough). Numerische Lösung linearer algebraischer Gleichungssysteme

Der Vorteil iterativer Methoden liegt in ihrer Anwendbarkeit auf schlecht konditionierte Systeme und Systeme höherer Ordnung, ihrer Selbstkorrektur und der einfachen Implementierung auf einem PC. Um mit Berechnungen zu beginnen, müssen bei iterativen Methoden zunächst eine Annäherung an die gewünschte Lösung angegeben werden.

Es ist zu beachten, dass die Bedingungen und die Konvergenzrate des iterativen Prozesses maßgeblich von den Eigenschaften der Matrix abhängen A System und auf die Wahl der ersten Näherungen.

Um die Iterationsmethode anzuwenden, muss das ursprüngliche System (2.1) oder (2.2) auf die Form reduziert werden

Danach wird der iterative Prozess nach wiederkehrenden Formeln durchgeführt

, k = 0, 1, 2, ... . (2.26A)

Matrix G und Vektor werden als Ergebnis der Transformation des Systems (2.1) erhalten.

Für Konvergenz (2.26 A) ist notwendig und ausreichend, sodass |l ich(G)| < 1, где lich(G) - Alle Eigenwerte Matrizen G. Konvergenz tritt auch auf, wenn || G|| < 1, так как |lich(G)| < " ||G||, wobei „irgendein“ ist.

Symbol || ... || bedeutet die Norm der Matrix. Bei der Bestimmung seines Wertes beschränken sie sich meist auf die Prüfung von zwei Bedingungen:

||G|| = oder || G|| = , (2.27)

Wo . Konvergenz ist auch dann gewährleistet, wenn die ursprüngliche Matrix vorliegt A hat diagonale Dominanz, d.h.

. (2.28)

Wenn (2.27) oder (2.28) erfüllt ist, konvergiert die Iterationsmethode für jede anfängliche Näherung. Am häufigsten wird der Vektor entweder Null oder Eins angenommen, oder der Vektor selbst wird aus (2.26) entnommen.

Es gibt viele Ansätze, das ursprüngliche System (2.2) mit der Matrix zu transformieren A um die Form (2.26) sicherzustellen oder die Konvergenzbedingungen (2.27) und (2.28) zu erfüllen.

(2.26) kann beispielsweise wie folgt erhalten werden.

Lassen A = IN+ MIT, det IN#0; Dann ( B+ MIT)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1, daher= − B –1 C+ B –1 .

Putten - B –1 C = G, B–1 = , erhalten wir (2.26).

Aus den Konvergenzbedingungen (2.27) und (2.28) geht hervor, dass die Darstellung A = IN+ MIT kann nicht willkürlich sein.

Wenn Matrix A die Bedingungen (2.28) erfüllt, dann als Matrix IN Sie können das untere Dreieck auswählen:

, ein ii ¹ 0.

; Þ ; Þ ; Þ

Durch die Wahl des Parameters a können wir sicherstellen, dass || G|| = ||E+ a A|| < 1.

Wenn (2.28) vorherrscht, kann die Transformation zu (2.26) durch Lösen jedes einzelnen erfolgen ich Gleichung des Systems (2.1) bzgl x i nach den folgenden wiederkehrenden Formeln:

(2.28A)

Wenn in der Matrix A es gibt keine diagonale Dominanz; sie muss durch einige lineare Transformationen erreicht werden, die ihre Äquivalenz nicht verletzen.

Betrachten Sie als Beispiel das System

(2.29)

Wie Sie sehen können, gibt es in den Gleichungen (1) und (2) keine diagonale Dominanz, in (3) jedoch schon, also lassen wir es unverändert.

Lassen Sie uns in Gleichung (1) eine diagonale Dominanz erreichen. Multiplizieren wir (1) mit a, (2) mit b, addieren beide Gleichungen und wählen in der resultierenden Gleichung a und b so, dass eine diagonale Dominanz vorliegt:

(2a + 3b) X 1 + (–1,8a + 2b) X 2 +(0,4a – 1,1b) X 3 = a.

Wenn wir a = b = 5 nehmen, erhalten wir 25 X 1 + X 2 – 3,5X 3 = 5.

Um Gleichung (2) mit einer Dominanz von (1) umzuwandeln, multiplizieren Sie mit g, (2) multiplizieren Sie mit d und subtrahieren Sie (1) von (2). Wir bekommen

(3d – 2g) X 1 + (2d + 1,8g) X 2 +(–1,1d – 0,4g) X 3 = −g.

Wenn wir d = 2, g = 3 setzen, erhalten wir 0 X 1 + 9,4 X 2 – 3,4 X 3 = −3. Als Ergebnis erhalten wir das System

(2.30)

Mit dieser Technik können Lösungen für eine breite Klasse von Matrizen gefunden werden.

oder

Als erste Näherung wird der Vektor = (0,2; –0,32; 0) angenommen T, werden wir dieses System mithilfe der Technologie lösen (2.26 A):

k = 0, 1, 2, ... .

Der Berechnungsprozess stoppt, wenn zwei benachbarte Näherungen des Lösungsvektors in ihrer Genauigkeit übereinstimmen, d.h.

.

Technologie der iterativen Lösung des Formulars (2.26 A) benannt einfache Iterationsmethode .

Grad absoluter Fehler für die einfache Iterationsmethode:

Wo ist das Symbol ||? ... || bedeutet normal.

Beispiel 2.1. Lösen Sie das System mithilfe einer einfachen Iterationsmethode mit einer Genauigkeit von e = 0,001 lineare Gleichungen:

Die Anzahl der Schritte, die eine Antwort mit einer Genauigkeit von e = 0,001 liefern, kann aus der Beziehung bestimmt werden

0,001 £.

Schätzen wir die Konvergenz mit der Formel (2.27). Hier || G|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Als erste Näherung nehmen wir den Vektor der freien Terme, also = (2,15; –0,83; 1,16; 0,44) T. Ersetzen wir die Vektorwerte in (2.26 A):

Wir setzen die Berechnungen fort und tragen die Ergebnisse in die Tabelle ein:

k	X 1	X 2	X 3	X 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Die Konvergenz in Tausendstel erfolgt bereits im 10. Schritt.

Antwort: X 1 » 3,571; X 2 "-0,957; X 3 » 1,489; X 4 "-0,836.

Diese Lösung kann auch mit den Formeln (2.28) erhalten werden A).

Beispiel 2.2. Zur Veranschaulichung des Algorithmus anhand von Formeln (2.28 A) Betrachten Sie die Lösung des Systems (nur zwei Iterationen):

; . (2.31)

Transformieren wir das System gemäß (2.28) in die Form (2.26). A):

Þ (2.32)

Nehmen wir die anfängliche Näherung = (0; 0; 0) T. Dann für k= 0 ist es offensichtlich, dass der Wert = (0,5; 0,8; 1,5) T. Setzen wir diese Werte in (2.32) ein, d. h. wann k= 1 erhalten wir = (1,075; 1,3; 1,175) T.

Fehler e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Blockdiagramm des Algorithmus zur Lösung des SLAE mithilfe der Methode einfache Iterationen nach Arbeitsformeln (2.28 A) ist in Abb. dargestellt. 2.4.

Eine Besonderheit des Blockdiagramms ist das Vorhandensein folgender Blöcke:

– Block 13 – sein Zweck wird weiter unten erläutert;

– Block 21 – Anzeige der Ergebnisse auf dem Bildschirm;

– Block 22 – Prüfung (Indikator) der Konvergenz.

Analysieren wir das vorgeschlagene Schema am Beispiel des Systems (2.31) ( N= 3, w = 1, e = 0,001):

= ; .

Block 1. Geben Sie die Ausgangsdaten ein A, ,Wir, N: N= 3, w = 1, e = 0,001.

Zyklus I. Legen Sie die Anfangswerte der Vektoren fest X 0ich Und x i (ich = 1, 2, 3).

Block 5. Setzen Sie den Iterationszähler zurück.

Block 6. Setzen Sie den aktuellen Fehlerzähler auf Null zurück.

IN Zyklus II werden die Zeilennummern der Matrix geändert A und Vektor.

Zyklus II:ich = 1: S = B 1 = 2 (Block 8).

Gehen Sie zu verschachtelter Schleife III, Block 9 – Matrixspaltennummernzähler A: J = 1.

Block 10: J = ich Daher kehren wir zu Block 9 zurück und erhöhen J pro Einheit: J = 2.

Im Block 10 J ¹ ich(2 ¹ 1) – wir gehen zu Block 11.

Block 11: S= 2 – (–1) × X 0 2 = 2 – (–1) × 0 = 2, gehe zu Block 9, in dem J um eins erhöhen: J = 3.

In Block 10 die Bedingung J ¹ ich ist erfüllt, also fahren wir mit Block 11 fort.

Block 11: S= 2 – (–1) × X 0 3 = 2 – (–1) × 0 = 2, danach fahren wir mit Block 9 fort, in dem J um eins erhöhen ( J= 4). Bedeutung J mehr N (N= 3) – wir beenden den Zyklus und fahren mit Block 12 fort.

Block 12: S = S / A 11 = 2 / 4 = 0,5.

Block 13: w = 1; S = S + 0 = 0,5.

Block 14: D = | x i – S | = | 1 – 0,5 | = 0,5.

Block 15: x i = 0,5 (ich = 1).

Block 16. Zustand prüfen D > de: 0,5 > 0, daher gehen wir zu Block 17, in dem wir zuweisen de= 0,5 und kehren Sie über den Link „ zurück A» zum nächsten Schritt von Zyklus II – zu Block 7, in dem ich um eins erhöhen.

Zyklus II: ich = 2: S = B 2 = 4 (Block 8).

J = 1.

Durch Block 10 J ¹ ich(1 ¹ 2) – wir gehen zu Block 11.

Block 11: S= 4 – 1 × 0 = 4, gehe zu Block 9, in dem J um eins erhöhen: J = 2.

In Block 10 ist die Bedingung nicht erfüllt, also fahren wir mit Block 9 fort, in dem J um eins erhöhen: J= 3. Analog gehen wir zu Block 11 über.

Block 11: S= 4 – (–2) × 0 = 4, danach beenden wir Zyklus III und fahren mit Block 12 fort.

Block 12: S = S/ A 22 = 4 / 5 = 0,8.

Block 13: w = 1; S = S + 0 = 0,8.

Block 14: D = | 1 – 0,8 | = 0,2.

Block 15: x i = 0,8 (ich = 2).

Block 16. Zustand prüfen D > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «A» zum nächsten Schritt von Zyklus II – zu Block 7.

Zyklus II: ich = 3: S = B 3 = 6 (Block 8).

Gehen Sie zu verschachtelter Schleife III, Block 9: J = 1.

Block 11: S= 6 – 1 × 0 = 6, gehe zu Block 9: J = 2.

Mit Block 10 gehen wir zu Block 11.

Block 11: S= 6 – 1 × 0 = 6. Wir beenden Zyklus III und fahren mit Block 12 fort.

Block 12: S = S/ A 33 = 6 / 4 = 1,5.

Block 13: S = 1,5.

Block 14: D = | 1 – 1,5 | = 0,5.

Block 15: x i = 1,5 (ich = 3).

Gemäß Block 16 (einschließlich Verweise „ A" Und " MIT") verlassen wir Zyklus II und gehen weiter zu Block 18.

Block 18. Erhöhung der Anzahl der Iterationen Es = Es + 1 = 0 + 1 = 1.

In den Blöcken 19 und 20 von Zyklus IV ersetzen wir die Anfangswerte X 0ich erhaltene Werte x i (ich = 1, 2, 3).

Block 21. Wir drucken Zwischenwerte der aktuellen Iteration, in diesem Fall: = (0,5; 0,8; 1,5) T, Es = 1; de = 0,5.

Wir gehen von Zyklus II zu Block 7 und führen die betrachteten Berechnungen mit neuen Anfangswerten durch X 0ich (ich = 1, 2, 3).

Danach bekommen wir X 1 = 1,075; X 2 = 1,3; X 3 = 1,175.

Hier konvergiert also Seidels Methode.

Nach Formeln (2.33)

k	X 1	X 2	X 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Antwort: X 1 = 0,248; X 2 = 1,115; X 3 = –0,224.

Kommentar. Wenn die einfache Iterations- und die Seidel-Methode für dasselbe System konvergieren, ist die Seidel-Methode vorzuziehen. In der Praxis können die Konvergenzbereiche dieser Methoden jedoch unterschiedlich sein, d. h. die einfache Iterationsmethode konvergiert, die Seidel-Methode divergiert jedoch und umgekehrt. Für beide Methoden, wenn || G|| in der Nähe Einheit Die Konvergenzgeschwindigkeit ist sehr gering.

Um die Konvergenz zu beschleunigen, wird eine künstliche Technik eingesetzt – die sogenannte Entspannungsmethode . Sein Wesen besteht darin, dass der nächste Wert durch die Iterationsmethode erhalten wird x i (k) wird anhand der Formel neu berechnet

wobei w normalerweise im Bereich von 0 bis 2 geändert wird (0< w £ 2) с каким-либо шагом (H= 0,1 oder 0,2). Der Parameter w wird so gewählt, dass die Konvergenz des Verfahrens in einer minimalen Anzahl von Iterationen erreicht wird.

Entspannung– eine allmähliche Schwächung eines beliebigen Zustands des Körpers nach dem Aufhören der Faktoren, die diesen Zustand verursacht haben (physikalische Technik).

Beispiel 2.4. Betrachten wir das Ergebnis der fünften Iteration unter Verwendung der Entspannungsformel. Nehmen wir w = 1,5:

Wie Sie sehen, wurde das Ergebnis fast der siebten Iteration erhalten.

In diesem Abschnitt betrachten wir einen stationären iterativen Prozess, wenn die Matrix und die Iterationsparameter verwendet werden hängen nicht vom Index ab , und beweisen Sie den folgenden Satz über ausreichende Bedingungen für seine Konvergenz.

Satz von Samarsky

Lassen - selbstadjungierte positiv definite Matrix:

,
,

- positiv definite Matrix, - positive Zahl:

,
.

Dann gilt für jede beliebige Nullnäherung iterativer Prozess, der durch die wiederkehrende Formel bestimmt wird , konvergiert zur Lösung des ursprünglichen Systems.

Bevor wir zum Beweis des Theorems übergehen, wollen wir seine Hauptanforderung – die positive Bestimmtheit der Matrix – genauer besprechen
. Diese Anforderung kann wie folgt umgeschrieben werden:

,
,
.

das heißt, es geht insbesondere davon aus, dass die Matrix ist positiv definitiv. Darüber hinaus bestimmt die Ungleichung das Intervall, in dem sich der Parameter ändern kann :

.

Nach diesen Bemerkungen gehen wir zum Beweis des Satzes über. Lassen Sie uns aus der Beziehung ausdrücken durch :

und setzen Sie es in die wiederkehrende Formel für die Iterationssequenz ein. Als Ergebnis erhalten wir:

.

Der Unterschied zwischen der iterativen Formel und besteht darin, dass sie homogen ist.

Matrix - positiv definitiv. Daher ist es nicht entartet und hat eine Umkehrung
. Mit ihrer Hilfe Wiederholungsbeziehung kann relativ gelöst werden
:

, Also
.

Multiplizieren Sie beide Seiten der Gleichheit auf der linken Seite mit der Matrix erhalten wir eine weitere Wiederholungsrelation

.

Betrachten Sie die Folge positiver Funktionale:

.

Erstellen wir einen ähnlichen Ausdruck für
und transformiere es mit wiederkehrenden Formeln und:

Aus der Selbstadjungiertheit der Matrix und die Formel folgt

Als Ergebnis hat die Formel die Form:

Somit die Reihenfolge der Funktionale an Bedingungen geknüpft
bildet eine monoton nicht zunehmende Folge, die nach unten durch Null begrenzt ist

.

,

Wo
ist eine streng positive Konstante. Als Ergebnis, entsprechend und wir werden haben

Aus dieser Ungleichung und der Konvergenz der Funktionalfolge Daraus folgt
bei
. Wiederum
, Also

Der Satz ist bewiesen.

1. Einfache Iterationsmethode.

Dieser Name wurde der Methode gegeben, bei der als Matrix Die Identitätsmatrix wird ausgewählt:
und der Iterationsparameter Es wird davon ausgegangen, dass es unabhängig von der Iterationszahl ist . Mit anderen Worten, die einfache Iterationsmethode ist eine explizite stationäre Methode bei der nächsten Iteration
berechnet nach der wiederkehrenden Formel

Wir gehen davon aus, dass die Matrix erfüllt die Bedingungen des Satzes von Samarsky,
, dann die Formel, die die Grenze des Konvergenzintervalls in Bezug auf den iterativen Parameter bestimmt , nimmt die Form an

.

Lassen
- Orthonormalbasis der Eigenvektoren des Operators, der der Matrix entspricht . Aufgrund der positiven Bestimmtheit sind alle seine Eigenwerte positiv. Wir betrachten sie in absteigender Reihenfolge nummeriert:

Erweitern wir den Vektor
basierend auf Eigenvektoren

Daraus folgt aus der Formel, dass die einfache Iterationsmethode für jeden konvergiert zum Intervall gehörend

.

Wir werden unsere weitere Untersuchung der einfachen Iterationsmethode auf einer spezifischen Analyse der wiederkehrenden Formel stützen. Lassen Sie uns die Matrix des Übergangsoperators vorstellen

,

und schreiben Sie die Formel im Formular um

.

In diesem Fall der Fehler
wird eine ähnliche Wiederholungsrelation erfüllen, nur homogen

.

Lassen Sie uns zwei Lemmata beweisen, die es uns ermöglichen, die Bedingungen für die Konvergenz der einfachen Iterationsmethode genauer zu untersuchen.

Lemma 1

Lassen Sie den Operator, den die Matrix generiert , hat einen Eigenvektor mit Eigenwert , dann der Übergangsoperator, der von der Matrix erzeugt wird , hat auch einen Eigenvektor , aber mit Eigenwert

.

Der Beweis ist elementar. Sie erfolgt durch direkte Verifizierung

Für eine selbstadjungierte Matrix Matrix ist auch selbstadjungiert. Folglich wird seine Norm durch den größten absoluten Eigenwert bestimmt
:

.

Lemma 2

Damit die einfache Iterationsmethode für jede beliebige Anfangsnäherung zu einer Lösung des Systems konvergiert, ist es notwendig und ausreichend, dass alle Eigenwerte des Übergangsoperators vorliegen waren im absoluten Wert kleiner als eins:

,

Angemessenheit. Die Bedingung bedeutet, dass die Norm der Matrix ist , entsprechend, wird kleiner als eins sein:
. Als Ergebnis bekommen wir

Bei
.

Notwendigkeit. Nehmen wir das unter den Eigenwerten an es gab mindestens einen , was die Bedingungen des Lemmas nicht erfüllt, d.h.

.

Wählen wir den Nullterm der Iterationssequenz in der Form
, Wo Lösung des Systems, dann fällt der Nullterm der Fehlerfolge mit dem Eigenvektor zusammen Übergangsoperator :
. Infolgedessen nimmt die wiederkehrende Formel für die folgenden Terme der Fehlersequenz die Form an:

,
.

d.h.
. Die Notwendigkeit, die Ungleichung für alle Eigenwerte zu erfüllen denn die Konvergenz der einfachen Iterationsmethode ist bewiesen.

Lemma 2 definiert das Programm zur weiteren Untersuchung der Konvergenz der einfachen Iterationsmethode: Es ist notwendig, den Bereich der Parametervariation festzulegen für die alle Eigenwerte die Ungleichung erfüllen. Es ist einfach zu machen. In Abb. 1 zeigt Diagramme abnehmender linearer Funktionen
. Sie kommen alle vom selben Punkt
,
und sinken aufgrund negativer Koeffizienten bei , und die am schnellsten abnehmende Funktion ist
. Wann ist es wichtig?
, die Bedingung dafür ist nicht mehr erfüllt:

, bei
.

Wert gefunden ist die Grenze des Konvergenzintervalls der einfachen Iterationsmethode

.

Wir kennen diese Ungleichung bereits. Sie wurde früher aus dem Satz von Samarsky als hinreichende Bedingung für die Konvergenz abgeleitet. Eine zusätzliche Analyse auf Basis von Lemma 2 ermöglicht es uns, das Ergebnis zu verdeutlichen. Jetzt haben wir die Zugehörigkeit des iterativen Parameters festgestellt Das Intervall ist eine notwendige und hinreichende Bedingung für die Konvergenz der einfachen Iterationsmethode.

Fahren wir mit der Untersuchung der Konvergenzrate der Methode fort. Eine Schätzung des Fehlers zeigt, dass er gemäß dem Gesetz der geometrischen Progression mit dem Nenner abnimmt

.

Schauen wir uns Abb. an. 2, die uns bei der Analyse dieser Formel helfen wird. Es ähnelt Abb. 1, zeigt jedoch Diagramme von Nichtfunktionen
und ihre Module. Bei klein alle Eigenwerte
sind positiv, und das Größte davon ist es
, die mit dem Wachstum abnimmt mit der niedrigsten Geschwindigkeit. Allerdings nach dem Passieren des Punktes
Eigenwert
, Vorzeichenwechsel, wird negativ. Infolgedessen nimmt sein Modul nun zu nimmt nicht ab, sondern nimmt mit zu
nähert sich dem Grenzwert – der Einheit.

Lassen Sie uns das Segment finden
Punkt , in der die abnehmende Funktion
im Vergleich zu einer steigenden Funktion
. Es wird durch die Gleichung bestimmt

was gibt

.

Als Ergebnis erhalten wir:

Ihr kleinster Wert ist die Norm der Matrix erreicht
:

.

Die Formel zeigt dies für eine schlecht konditionierte Matrix, selbst bei optimaler Wahl des Iterationsparameters
Matrixnorm liegt nahe bei Eins, daher ist die Konvergenz der einfachen Iterationsmethode in diesem Fall langsam.

Abschließend stellen wir fest, dass die Formel die Grenze des Konvergenzintervalls definiert und die Formel für den optimalen Wert des Iterationsparameters sind in erster Linie von theoretischem Interesse. Normalerweise werden beim Lösen von SLAEs die größten und kleinsten charakteristischen Zahlen der Matrix verwendet unbekannt, also berechnen Sie die Werte Und im Vorhinein unmöglich. Als Ergebnis der Iterationsparameter Oftmals muss man es direkt im Berechnungsprozess durch Ausprobieren auswählen.

Aufgabe 2.

Betrachten Sie ein System aus zwei Gleichungen mit zwei Unbekannten

und konstruieren Sie mithilfe der einfachen Iterationsmethode eine Näherungslösung dafür.

Schreiben wir sofort die Lösung für das System auf

,
,

sodass Sie es dann mit den Mitgliedern der Iterationssequenz vergleichen können.

Fahren wir mit der Lösung des Systems mithilfe der einfachen Iterationsmethode fort. Die Systemmatrix hat die Form

.

Es ist selbstadjungiert und positiv definit, da

Erstellen wir eine charakteristische Gleichung für die Matrix und finde seine Wurzeln:

,

,

Mit ihrer Hilfe können Sie die Grenze des Konvergenzintervalls bestimmen Und optimaler Wert Iterationsparameter :

,
.

Um eine Iterationssequenz zu konstruieren, wählen wir einen Wert des Iterationsparameters im Konvergenzintervall, zum Beispiel
. In diesem Fall hat die wiederkehrende Formel für die Mitglieder der Iterationssequenz die Form:

, Wo

Nehmen wir die einfachste anfängliche Näherung
und notieren Sie die ersten paar Terme der Iterationssequenz , Berechnen des Residuums für jeden von ihnen
. Als Ergebnis erhalten wir:

,
,
,

,
,
,

,
,
,

,
,
.

Die Norm der Residuen nimmt zwar langsam ab, was auf die Konvergenz des Prozesses hinweist. Das Gleiche lässt sich aus dem Vergleich der Terme der Iterationssequenz erkennen mit der Lösung des Systems. Die langsame Konvergenz ist auf eine schlechte Matrixkonditionierung zurückzuführen :

.

Die einfache Iterationsmethode basiert auf dem Ersetzen der ursprünglichen Gleichung durch eine äquivalente Gleichung:

Die anfängliche Annäherung an die Wurzel sei bekannt x = x 0. Ersetzen Sie es rechte Seite Gleichung (2.7) ergibt eine neue Näherung , dann erhalten wir auf ähnliche Weise usw.:

. (2.8)

Nicht unter allen Bedingungen konvergiert der iterative Prozess zur Wurzel der Gleichung X. Schauen wir uns diesen Prozess genauer an. Abbildung 2.6 zeigt eine grafische Interpretation eines einseitig konvergenten und divergenten Prozesses. Abbildung 2.7 zeigt bidirektionale konvergente und divergente Prozesse. Ein divergenter Prozess ist durch einen schnellen Anstieg der Werte des Arguments und der Funktion und die abnormale Beendigung des entsprechenden Programms gekennzeichnet.

Bei einem bidirektionalen Prozess ist ein zyklisches Durchlaufen möglich, also eine endlose Wiederholung derselben Funktions- und Argumentwerte. Durch Schleifen wird ein divergenter Prozess von einem konvergenten Prozess getrennt.

Aus den Diagrammen geht hervor, dass die Konvergenz zur Wurzel sowohl bei einseitigen als auch bei zweiseitigen Prozessen durch die Steigung der Kurve in der Nähe der Wurzel bestimmt wird. Je kleiner die Steigung, desto besser ist die Konvergenz. Bekanntlich ist der Tangens der Steigung einer Kurve gleich der Ableitung der Kurve an einem bestimmten Punkt.

Je kleiner die Zahl in der Nähe der Wurzel ist, desto schneller konvergiert der Prozess.

Damit der Iterationsprozess konvergent ist, muss in der Umgebung der Wurzel die folgende Ungleichung erfüllt sein:

Der Übergang von Gleichung (2.1) zu Gleichung (2.7) kann durchgeführt werden auf verschiedene Weise abhängig von der Art der Funktion f(x). Bei einem solchen Übergang ist es notwendig, die Funktion so zu konstruieren, dass die Konvergenzbedingung (2.9) erfüllt ist.

Betrachten wir einen der allgemeinen Algorithmen für den Übergang von Gleichung (2.1) zu Gleichung (2.7).

Lassen Sie uns die linke und rechte Seite der Gleichung (2.1) mit einer beliebigen Konstante multiplizieren B und füge das Unbekannte zu beiden Teilen hinzu X. In diesem Fall ändern sich die Wurzeln der ursprünglichen Gleichung nicht:

Lassen Sie uns die Notation einführen und gehen wir von Beziehung (2.10) zu Gleichung (2.8).

Beliebige Wahl der Konstante B stellt die Erfüllung der Konvergenzbedingung (2.9) sicher. Das Kriterium für die Beendigung des iterativen Prozesses ist die Bedingung (2.2). Abbildung 2.8 zeigt eine grafische Interpretation der Methode der einfachen Iterationen unter Verwendung der beschriebenen Darstellungsmethode (die Maßstäbe entlang der X- und Y-Achse sind unterschiedlich).

Wird eine Funktion in der Form gewählt, so ist die Ableitung dieser Funktion. Die höchste Konvergenzgeschwindigkeit liegt dann bei und die Iterationsformel (2.11) wird zur Newtonschen Formel. Somit weist Newtons Methode den höchsten Konvergenzgrad aller iterativen Prozesse auf.

Die Softwareimplementierung der einfachen Iterationsmethode erfolgt in Form einer Unterprogrammprozedur Iteras(PROGRAMM 2.1).

Das gesamte Verfahren besteht praktisch aus einem Zyklus „Wiederholen ... Bis“, wobei die Formel (2.11) unter Berücksichtigung der Bedingung zum Stoppen des iterativen Prozesses (Formel (2.2)) implementiert wird.

Die Prozedur verfügt über einen integrierten Schleifenschutz, indem die Anzahl der Schleifen mithilfe der Niter-Variablen gezählt wird. Im praktischen Unterricht müssen Sie durch die Ausführung des Programms sicherstellen, wie sich die Wahl des Koeffizienten auswirkt B und erste Annäherung im Prozess der Suche nach der Wurzel. Beim Ändern des Koeffizienten B die Art des iterativen Prozesses für die untersuchte Funktion ändert sich. Es wird zunächst zweiseitig und dann zu Schleifen (Abb. 2.9). Achsenskalen X Und Y sind unterschiedlich. Ein noch größerer Wert des Moduls b führt zu einem divergenten Prozess.

Vergleich von Methoden zur Näherungslösung von Gleichungen

Der Vergleich der oben beschriebenen Methoden zur numerischen Lösung von Gleichungen wurde mit einem Programm durchgeführt, mit dem Sie den Prozess der Wurzelfindung grafisch auf dem PC-Bildschirm beobachten können. Die in diesem Programm enthaltenen Verfahren und die Implementierung der verglichenen Methoden sind unten aufgeführt (PROGRAMM 2.1).

Reis. 2.3-2.5, 2.8, 2.9 sind Kopien des PC-Bildschirms am Ende des Iterationsprozesses.

In allen Fällen wurde die untersuchte Funktion übernommen quadratische Gleichung x 2 -x-6 = 0, mit analytische Lösung x 1 = -2 und x 2 = 3. Der Fehler und die anfänglichen Näherungen wurden für alle Methoden als gleich angenommen. Root-Suchergebnisse x= 3, dargestellt in den Figuren, sind wie folgt. Die Dichotomiemethode konvergiert am langsamsten – 22 Iterationen, am schnellsten ist die einfache Iterationsmethode mit b = –0,2 – 5 Iterationen. Hier besteht kein Widerspruch zur Aussage, dass Newtons Methode die schnellste ist.

Ableitung der an diesem Punkt untersuchten Funktion X= 3 ist gleich -0,2, d. h. die Berechnung wurde in diesem Fall praktisch nach der Newton-Methode mit dem Wert der Ableitung am Punkt der Wurzel der Gleichung durchgeführt. Beim Ändern des Koeffizienten B die Konvergenzrate sinkt und der allmähliche Konvergenzprozess verläuft zunächst in Zyklen und wird dann divergent.

Die einfache Iterationsmethode, auch sukzessive Approximationsmethode genannt, ist ein mathematischer Algorithmus zum Ermitteln des Werts einer unbekannten Größe durch schrittweise Verfeinerung. Der Kern dieser Methode besteht darin, dass, wie der Name schon sagt, durch schrittweises Ausdrücken nachfolgender Methoden ausgehend von der anfänglichen Annäherung immer verfeinerte Ergebnisse erzielt werden. Diese Methode wird verwendet, um den Wert einer Variablen in zu ermitteln gegebene Funktion sowie beim Lösen linearer und nichtlinearer Gleichungssysteme.

Betrachten wir, wie diese Methode bei der Lösung von SLAEs implementiert wird. Die einfache Iterationsmethode hat den folgenden Algorithmus:

1. Überprüfung der Erfüllung der Konvergenzbedingung in der Originalmatrix. Konvergenzsatz: Wenn die ursprüngliche Matrix des Systems eine Diagonaldominanz aufweist (d. h. in jeder Zeile müssen die Elemente der Hauptdiagonalen im Absolutwert größer sein als die Summe der Elemente der Nebendiagonalen im Absolutwert), dann ist die einfache Die Iterationsmethode ist konvergent.

2. Die Matrix des ursprünglichen Systems weist nicht immer eine diagonale Dominanz auf. In solchen Fällen kann das System umgestellt werden. Gleichungen, die die Konvergenzbedingung erfüllen, bleiben unangetastet, und mit denen, die dies nicht tun, werden lineare Kombinationen vorgenommen, d. h. Multiplizieren, subtrahieren und addieren Sie Gleichungen miteinander, bis Sie das gewünschte Ergebnis erhalten.

Wenn im resultierenden System unbequeme Koeffizienten auf der Hauptdiagonale vorhanden sind, werden auf beiden Seiten einer solchen Gleichung Terme der Form mit i * x i hinzugefügt, deren Vorzeichen mit den Vorzeichen der Diagonalelemente übereinstimmen müssen.

3. Transformation des resultierenden Systems in Normalform:

x - =β - +α*x -

Dies kann auf viele Arten erfolgen, zum Beispiel so: Drücken Sie aus der ersten Gleichung x 1 durch andere Unbekannte aus, aus der zweiten - x 2, aus der dritten - x 3 usw. In diesem Fall verwenden wir die Formeln:

α ij = -(a ij / a ii)

i = b i /a ii
Sie sollten erneut sicherstellen, dass das resultierende System normal aussehend entspricht der Konvergenzbedingung:

∑ (j=1) |α ij |≤ 1, während i= 1,2,...n

4. Wir beginnen, die Methode der sukzessiven Approximationen selbst anzuwenden.

x (0) ist die anfängliche Näherung, wir werden x (1) dadurch ausdrücken, dann werden wir x (2) durch x (1) ausdrücken. Allgemeine Formel und in Matrixform sieht es so aus:

x (n) = β - +α*x (n-1)

Wir rechnen so lange, bis wir die erforderliche Genauigkeit erreicht haben:

max |x i (k)-x i (k+1) ≤ ε

Lassen Sie uns also die einfache Iterationsmethode in die Praxis umsetzen. Beispiel:
SLAE lösen:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 mit einer Genauigkeit von ε=10 -3

Mal sehen, ob diagonale Elemente im Modul überwiegen.

Wir sehen, dass nur die dritte Gleichung die Konvergenzbedingung erfüllt. Wir transformieren die erste und die zweite und fügen die zweite zur ersten Gleichung hinzu:

7,6x1+0,6x2+2,4x3=3

Vom dritten subtrahieren wir das erste:

2,7x1+4,2x2+1,2x3=2

Wir haben das ursprüngliche System in ein äquivalentes System umgewandelt:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Bringen wir nun das System in seine normale Form:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

Wir überprüfen die Konvergenz des iterativen Prozesses:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, d.h. die Bedingung ist erfüllt.

0,3947
Ursprüngliche Schätzung x(0) = 0,4762
0,8511

Wenn wir diese Werte in die Normalformgleichung einsetzen, erhalten wir die folgenden Werte:

0,08835
x(1) = 0,486793
0,446639

Wenn wir neue Werte einsetzen, erhalten wir:

0,215243
x(2) = 0,405396
0,558336

Wir setzen die Berechnungen fort, bis wir uns Werten nähern, die die gegebene Bedingung erfüllen.

x (7) = 0,441091

Lassen Sie uns die Richtigkeit der erhaltenen Ergebnisse überprüfen:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Die durch Einsetzen der gefundenen Werte in die ursprünglichen Gleichungen erhaltenen Ergebnisse erfüllen die Bedingungen der Gleichung vollständig.

Wie wir sehen können, liefert die einfache Iterationsmethode ziemlich genaue Ergebnisse, aber um diese Gleichung zu lösen, mussten wir viel Zeit aufwenden und umständliche Berechnungen durchführen.

Vorlesung Iterative Methoden zur Lösung eines Systems algebraischer linearer Gleichungen.

Bedingung für die Konvergenz des Jacobi-Verfahrens

Einfache Iterationsmethode

Wir betrachten ein lineares System algebraische Gleichungen

Um iterative Methoden anwenden zu können, muss das System auf eine äquivalente Form reduziert werden

Dann wird eine anfängliche Näherung für die Lösung des Gleichungssystems ausgewählt und eine Folge von Näherungsverfahren für die Wurzel gefunden.

Damit der iterative Prozess konvergiert, reicht es aus, dass die Bedingung erfüllt ist
(Matrixnorm). Das Kriterium zum Beenden von Iterationen hängt von der verwendeten Iterationsmethode ab.

Jacobi-Methode .

Der einfachste Weg, das System in eine für die Iteration geeignete Form zu bringen, ist wie folgt:

Aus der ersten Gleichung des Systems drücken wir das Unbekannte aus X 1, aus der zweiten Gleichung des Systems, das wir ausdrücken X 2 usw.

Als Ergebnis erhalten wir ein Gleichungssystem mit Matrix B, in dem sich null Elemente auf der Hauptdiagonale befinden und die restlichen Elemente nach den Formeln berechnet werden:

Die Komponenten des Vektors d werden nach den Formeln berechnet:

Die Berechnungsformel für die einfache Iterationsmethode lautet:

oder in Koordinatenschreibweise sieht es so aus:

Das Kriterium zum Beenden von Iterationen in der Jacobi-Methode hat die Form:

Wenn
, dann können wir ein einfacheres Kriterium zum Beenden von Iterationen anwenden

Beispiel 1. Lösen eines Systems linearer Gleichungen mit der Jacobi-Methode.

Gegeben sei das Gleichungssystem:

Es ist erforderlich, eine genaue Lösung für das System zu finden

Reduzieren wir das System auf eine für die Iteration geeignete Form:

Wählen wir zum Beispiel eine erste Näherung:

- Vektor der rechten Seite.

Dann sieht die erste Iteration so aus:

Die folgenden Näherungen zur Lösung werden auf ähnliche Weise erhalten.

Finden wir die Norm der Matrix B.

Wir werden die Norm verwenden

Da die Summe der Module der Elemente in jeder Zeile 0,2 beträgt, dann
, also ist das Kriterium für das Beenden von Iterationen in diesem Problem

Berechnen wir die Normen der Vektordifferenzen:

Weil
Die angegebene Genauigkeit wurde bei der vierten Iteration erreicht.

Antwort: X 1 = 1.102, X 2 = 0.991, X 3 = 1.0 1 1

Seidel-Methode .

Die Methode kann als Modifikation der Jacobi-Methode betrachtet werden. Die Hauptidee ist, dass bei der Berechnung des nächsten (n+1)-te Annäherung an das Unbekannte X ich bei ich >1 Verwendung bereits gefunden (n+1)- Wir nähern uns dem Unbekannten X 1 ,X 2 , ...,X i - 1 und nicht N Näherung, wie in der Jacobi-Methode.

Die Berechnungsformel der Methode in Koordinatenschreibweise sieht folgendermaßen aus:

Die Konvergenzbedingungen und das Kriterium für die Beendigung von Iterationen können wie bei der Jacobi-Methode übernommen werden.

Beispiel 2. Lösen linearer Gleichungssysteme mit der Seidel-Methode.

Betrachten wir parallel die Lösung von 3 Gleichungssystemen:

Reduzieren wir die Systeme auf eine für Iterationen geeignete Form:

Beachten Sie die Konvergenzbedingung
Dies wird nur für das erste System durchgeführt. Berechnen wir jeweils 3 erste Näherungen zur Lösung.

1. System:

Die genaue Lösung wird die folgenden Werte sein: X 1 = 1.4, X 2 = 0.2 . Der iterative Prozess konvergiert.

2. System:

Es ist ersichtlich, dass der Iterationsprozess divergiert.

Genaue Lösung X 1 = 1, X 2 = 0.2 .

3. System:

Es ist ersichtlich, dass der iterative Prozess in Zyklen ablief.

Genaue Lösung X 1 = 1, X 2 = 2 .

Die Matrix des Gleichungssystems A sei symmetrisch und positiv definit. Dann konvergiert die Seidel-Methode für jede beliebige Anfangsnäherung. An die Kleinheit der Norm einer bestimmten Matrix werden keine zusätzlichen Bedingungen gestellt.

Einfache Iterationsmethode.

Wenn A eine symmetrische und positiv definite Matrix ist, dann wird das Gleichungssystem oft auf die äquivalente Form reduziert:

X=X-τ (A X- b), τ – Iterationsparameter.

Die Berechnungsformel der einfachen Iterationsmethode hat in diesem Fall die Form:

X (n+1) =X N- τ (A X (N) - B).

und der Parameter τ > 0 wird so gewählt, dass der Wert möglichst minimiert wird

Seien λ min und λ max die minimalen und maximalen Eigenwerte der Matrix A. Die optimale Wahl des Parameters ist

In diesem Fall
nimmt einen Mindestwert an, der gleich ist:

Beispiel 3. Lösen linearer Gleichungssysteme mit der einfachen Iterationsmethode. (in MathCAD)

Gegeben sei das Gleichungssystem Ax = b

Um einen iterativen Prozess zu konstruieren, finden wir Eigenwerte Matrizen A:

– verwendet eine integrierte Funktion, um Eigenwerte zu finden.

Berechnen wir den Iterationsparameter und überprüfen die Konvergenzbedingung

Die Konvergenzbedingung ist erfüllt.

Nehmen wir die anfängliche Näherung – Vektor x0, stellen Sie die Genauigkeit auf 0,001 ein und ermitteln Sie die anfänglichen Näherungsverfahren mit dem folgenden Programm:

Genaue Lösung

Kommentar. Wenn das Programm die Rez-Matrix zurückgibt, können Sie alle gefundenen Iterationen anzeigen.