Die Lipschitz-Bedingung für die Konvergenz einer nichtlinearen Gleichung. Systeme nichtlinearer Gleichungen. Einfache Iterationsmethode

Übung:

1) Lösen Sie das System mit der Iterationsmethode

2) Lösen Sie das System mit der Newton-Methode

nichtlineare Gleichungen mit einer Genauigkeit von 0,001.

Aufgabe №1Löse das System der nichtlinearen Gleichungen mit der Iterationsmethode mit einer Genauigkeit von 0,001.

Theoretischer Teil.

Iterationsverfahren e Es ist eine Möglichkeit, mathematische Probleme numerisch zu lösen. Sein Wesen besteht darin, einen Suchalgorithmus für eine bekannte Näherung (Näherungswert) des gewünschten Werts der nächsten, genaueren Näherung zu finden. Es wird in dem Fall verwendet, wenn die Folge von Näherungen gemäß dem angegebenen Algorithmus konvergiert.

Diese Methode auch als Methode der sukzessiven Annäherung, Methode der wiederholten Substitutionen, Methode der einfachen Iterationen usw. bezeichnet.

Newtons Methode, Newtons Algorithmus (auch bekannt als Tangentenmethode) ist ein iterativer Algorithmus numerische Methode Finden der Wurzel (Null) der gegebenen Funktion. Die Methode wurde erstmals von dem englischen Physiker, Mathematiker und Astronomen Isaac Newton (1643-1727) vorgeschlagen. Die Lösungssuche erfolgt durch sukzessive Approximation und basiert auf den Prinzipien der einfachen Iteration. Das Verfahren hat quadratische Konvergenz. Eine Verbesserung der Methode ist die Methode der Akkorde und Tangenten. Das Newton-Verfahren kann auch zur Lösung von Optimierungsproblemen verwendet werden, bei denen es erforderlich ist, den Nullpunkt der ersten Ableitung oder des Gradienten im Fall eines mehrdimensionalen Raums zu bestimmen. Begründung

Um die Gleichung numerisch durch die einfache Iterationsmethode zu lösen, muss sie auf die folgende Form reduziert werden: , wobei die Kontraktionsabbildung ist.

Für die beste Konvergenz des Verfahrens am Punkt der nächsten Näherung muss die Bedingung erfüllt sein. Die Lösung dieser Gleichung sucht man in der Form , dann gilt:

Vorausgesetzt, der Annäherungspunkt ist "nah genug" an der Wurzel, und das gegebene Funktion stetig ist, lautet die endgültige Formel für:

Vor diesem Hintergrund wird die Funktion durch den Ausdruck definiert:

Diese Funktion in der Nähe der Wurzel führt eine Kontraktionsabbildung durch, und der Algorithmus zum Finden einer numerischen Lösung der Gleichung wird auf ein iteratives Berechnungsverfahren reduziert:

Aufgabenoptionen

№1. 1)
2)

№2. 1)
2)

№3. 1)
2)

№4. 1)
2)

№5. 1)
2)

№6. 1)
2)

№7. 1)
2)

№8. 1)
2)

№9. 1)
2)

№10.1)
2)

№11.1)
2)

№12.1)
2)

№13.1)
2)

№14.1)
2)

№15.1)
2)

№16.1)
2)

№17.1)
2)

№18.1)
2)

№19.1)
2)

№20.1)
2)

№21. 1)
2)

№22. 1)
2)

№23. 1)
2)

№24. 1)
2)

№25. 1)
2)

№26. 1)
2)

№27. 1)
2)

№28. 1)
2)

№29. 1)
2)

№30. 1)
2)

Abschluss der Beispielaufgabe

№1. 1)
2)

Ein Beispiel für das Lösen eines Systems nichtlinearer Gleichungen durch Iteration

Schreiben wir um dieses System als:

Die Trennung der Wurzeln erfolgt grafisch (Abb. 1). Aus dem Diagramm sehen wir, dass das System eine Lösung hat, die in der Fläche eingeschlossen ist D: 0<X<0,3;-2,2<j<-1,8.

Stellen wir sicher, dass das Iterationsverfahren anwendbar ist, um die Lösung des Systems zu verfeinern, wofür wir es in der folgenden Form schreiben:

Seit haben wir in der Region D

+ = ;

+ =

Somit sind die Konvergenzbedingungen erfüllt.

Tischnummer 2

P
	0,15	-2	-0,45	-0,4350	-0,4161	-0,1384
	0,1616	-2,035	-0,4384	-0,4245	-0,4477	-0,1492
	0,1508	-2.0245	-0,4492	-0,4342	-0,4382	-0,1461
	0.1539	-2,0342.	-0,4461	-0.4313	-0,4470	-0,1490
	0.1510	-2,0313	-0,4490	-0,4341	-0,4444	-0.1481
	0,1519	-2,0341	-0,4481	-0,4333	-0,4469	-0,1490
	0,1510	-2.0333	-0.449	-0,4341	-0.4462	-0,1487
	0.1513	-2.0341	-0,4487	-0,4340	-0,4469	-0.1490
	0.1510	-2,0340

Wir nehmen als erste Annäherungen x o=0,15, y 0 =-2.

(Tab. Nr. 2). Dann wird die Antwort lauten:

Ein Beispiel für die Lösung eines Systems nichtlinearer Gleichungen nach der Newton-Methode

Die Trennung der Wurzeln erfolgt grafisch (Abb. 2). Um Funktionsgraphen zu zeichnen, erstellen wir eine Tabelle mit Funktionswerten und , enthalten in der ersten und zweiten Gleichung (Tabelle I).

Werte für x können basierend auf den folgenden Bedingungen entnommen werden: aus der ersten Gleichung 1 ≤ 1,2 x + 0,4 ≤ 1, d.h. 1,16 ≤ x ≤ 0,5; aus der zweiten Gleichung, d.h. . Auf diese Weise, .

Das System hat zwei Lösungen. Lassen Sie uns einen davon verfeinern, der zum Bereich D: 0,4 gehört<x<0,5;

0,76<j<0,73. За начальное приближение примем Имеем:

Tisch 3

x	-1,1	-1	-0,8	-0,6	-0,2	-0,4		0,2	0,4	0,5
x 2	1.21		0,64	0,36	0,04	0,16		0,04	0.16	0,25
0,8x 2	0,97	0,8	0,51	0,29	0,032	0,13		0,032	0,13	0,2
1 -0,8x 2	0,03	0,2	0,49	0,71	0,97	0,87		0,97	0.87	0,8
	0,02	0,13	0,33	0,47	0,65	0,58	0,67	0,65	0,58	0.53
	±0,14	±0,36	±0,57	±0,69	±0,81	±0,76	±0,82	±0,81	±0,76	±0,73
1,2x	-1,32	-1,2	-0,9b"	-0,72	-0,24	-0,48		0,24	0,48	0,6
0,4+1,2x	-0,92	-0,8	-0,56	-0,32	0,16	-0,08	0,4	0,64	0.88
2x-y	-1.17	-0,93	-0,59	-0,33	0,16	-0,08	0,41	0,69	2.06 1,08	1,57
	-1,03	-1,07	-1,01	-0,87	-0,56	-0,72	-0,41	-0,29	-1,26 -1,28	-0.57

Wir verfeinern die Wurzeln nach Newtons Methode:

wo ; ;

;
;

Alle Berechnungen erfolgen nach Tabelle 3

Tisch 3			0,10	0,017	-0,0060	0,0247	-0,0027	-0,0256	0,0001	0,0004
		0,2701	0,0440	-0,0193	0,0794	-0,0080	-0,0764	-0,0003	0,0013
		2,6197	3,2199	2,9827	3,1673
		-0,0208	-2,25	0,1615	-2,199	0,1251	-2,1249	0,1452	-2,2017
		-1,1584	0,64	-1,523	0,8	-1,4502	0,7904	-1,4904	0,7861
		0,1198	-0,0282	-0,0131	0,059	-0,0007	-0,0523	-0,0002	0,0010
		0,9988	0,0208	0,9869	-0,1615	0,9921	-0,1251	-0,9894	-0,1452
	0,55	0,733	1,6963	1,7165
		0,128	0,8438	0,2	0,8059	0,1952	0,7525	0,1931	0,8079
		0,4	0,75	0,50	-0,733	0,4940	-0,7083	0,4913	-0,7339	0,4912	-0,7335	Antworten: x≈0,491 j≈ 0,734
n

Testfragen

1) Stellen Sie in der Grafik die möglichen Fälle der Lösung eines Systems aus zwei nichtlinearen Gleichungen dar.

2) Formulieren Sie die Problemstellung zur Lösung eines n-linearen Gleichungssystems.

3) Geben Sie die Iterationsformeln des einfachen Iterationsverfahrens für ein System aus zwei nichtlinearen Gleichungen an.

4) Formulieren Sie einen Satz über die lokale Konvergenz des Newton-Verfahrens.

5) Nennen Sie die Schwierigkeiten, die bei der Anwendung des Newton-Verfahrens in der Praxis auftreten.

6) Erklären Sie, wie das Newtonsche Verfahren modifiziert werden kann.

7) Zeichnen Sie in Form von Blockdiagrammen einen Algorithmus zum Lösen von Systemen zweier nichtlinearer Gleichungen unter Verwendung einfacher Iterationen und Newton-Verfahren.

Labor Nr. 3

Dienstzuweisung. Der Online-Rechner dient dazu, die Wurzeln der Gleichung zu finden Iterationsmethode.

Die Entscheidung wird im Word-Format getroffen.

Eingaberegeln für Funktionen

Beispiele
≡ x^2/(1+x)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)

Eine der effizientesten Möglichkeiten, Gleichungen numerisch zu lösen, ist Iterationsmethode. Das Wesentliche dieser Methode ist wie folgt. Gegeben sei die Gleichung f(x)=0.
Ersetzen wir es durch die äquivalente Gleichung
Wir wählen die anfängliche Näherung der Wurzel x 0 und setzen sie auf der rechten Seite von Gleichung (1) ein. Dann bekommen wir eine Zahl

x 1 \u003d φ (x 0). (2)

Wenn wir nun auf der rechten Seite von (2) anstelle von x 0 die Zahl x 1 einsetzen, erhalten wir die Zahl x 2 \u003d φ (x 1). Wenn wir diesen Vorgang wiederholen, haben wir eine Folge von Zahlen

xn = φ(xn-1) (n=1,2..). (3)

Wenn diese Folge konvergent ist, das heißt, es eine Grenze gibt, dann gehen wir zur Grenze in Gleichung (3) und nehmen an, dass die Funktion φ(x) stetig ist, finden wir

Oder ξ=φ(ξ).
Somit ist die Grenze ξ die Wurzel von Gleichung (1) und kann mit beliebiger Genauigkeit aus Formel (3) berechnet werden.

Reis. 1a Abb. 1b

Reis. 2.

|φ′(x)|>1 - divergenter Prozess

In den Fig. 1a, 1b in der Nähe der Wurzel |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, dann kann der Iterationsprozess abweichend sein (siehe Abb. 2).

Hinreichende Bedingungen für die Konvergenz des Iterationsverfahrens

Satz 7. Sei die Funktion φ(x) definiert und differenzierbar auf der Strecke , und all ihren Werten φ(x)∈ und sei |φ′(x)|≤q<1 при x∈. Тогда процесс итерации x n = φ(x n -1) сходится независимо от начального значения x 0 ∈ и предельное значение является единственным корнем уравнения x= φ(x) на отрезке .
Nachweisen: Betrachten Sie zwei aufeinanderfolgende Näherungen x n = φ(x n – 1) und x n +1 = φ(x n) und nehmen Sie ihre Differenz x n+1 – x n = φ(x n) – φ(x n – 1). Nach dem Satz von Lagrange kann die rechte Seite dargestellt werden als

φ'(xn)(xn-xn-1)

Wo x n ∈
Dann bekommen wir

Angenommen n=1,2,...

|x 2 – x 1 |≤q|x 1 – x 0 |
|x 3 – x 2 |≤q|x 2 – x 1 |≤q²|x 1 – x 0 |
|x n+1 – x n ≤q n |x 1 – x 0 | (vier)

Aus (4) wegen der Bedingung q<1 видно, что последовательность {x n } сходится к некоторому числу ξ, то есть

, und daher

(aufgrund der Stetigkeit der Funktion φ(x))
oder ξ= φ(ξ) q.t.d.
Für den Fehler der Wurzel ξ kann die folgende Formel erhalten werden.
Wir haben xn = φ(xn-1).
Weiter ξ-x n =ξ-φ(x n-1) = φ(ξ)-φ(x n-1) →
Nun ist φ(x n-1)=φ(x n)-φ′(c)(x n -x n-1) →
φ(ξ)-φ(xn)+φ'(c)(xn-xn-1)
Als Ergebnis erhalten wir

ξ-xn = φ'(c 1)(ξ-xn-1)+φ'(c)(xn-xn-1)
oder
|ξ-xn |≤q|ξ-xn |+q|xn-xn-1 |

Von hier

, (5)

woraus ersichtlich ist, dass für q nahe 1 die Differenz |ξ – x n | sehr groß sein kann, obwohl |x n - x n -1 |<ε, где ε-заданная величина. Для того, чтобы вычислить ξ с точностью ε необходимо обеспечить

. (6)

Wenn wir dann (6) in (5) einsetzen, erhalten wir |ξ – x n |<ε.
Wenn q sehr klein ist, kann man statt (6) verwenden

|xn-xn-1 |<ε

Konvergenz der Iterationsmethode linear mit Konvergenzkoeffizient α=q. Tatsächlich haben wir
ξ-x n = φ(ξ)-φ n-1 = φ'(c) (ξ-x n-1), daher |ξ-x n |≤q·|ξ-x n-1 |.

Kommentar. In irgendeiner Umgebung der Wurzel ξ∈(a,b) der Gleichung x= φ(x) behalte die Ableitung φ’(x) ein konstantes Vorzeichen und die Ungleichung |φ’(x)|≤q<1. Тогда, если φ’(x) положительна, то последовательные приближения x n = φ(x n -1) сходятся к корню монотонно.
Wenn φ'(x) negativ ist, dann oszillieren sukzessive Approximationen um die Wurzel.
Betrachten Sie eine Möglichkeit, die Gleichung f(x)=0 in der Form x= φ(x) darzustellen.
Die Funktion φ(x) muss so spezifiziert werden, dass |φ'(x)| war in der Nähe der Wurzel klein.
Seien m 1 und M 1 bekannt - die kleinsten und größten Werte der Ableitung f’(x)
0Ersetzen wir die Gleichung f(x)=0 durch ihre äquivalente Gleichung
x = x - λf(x).
Sei φ(x) = x- λf(x). Wählen wir den Parameter λ so, dass in einer Umgebung der Wurzel ξ die Ungleichung

0 ≤ |φ'(x)|=|1 – λf'(x)|≤q≤1

Daher erhalten wir aufgrund von (7).

0 ≤ |1 – λM 1 | ≤ |1 – λm 1 | ≤ q

Wenn wir dann λ = 1/M 1 wählen, erhalten wir
q = 1-m 1 /M 1< 1.
Wenn λ \u003d 1 / f '(x), dann geht die iterative Formel x n \u003d φ (x n -1) in die Newtonsche Formel ein

x n \u003d x n -1 - f (x n) / f '(x).

Iterationsmethode in Excel

In Zelle B2 tragen wir den Beginn des Intervalls a ein, in Zelle B3 tragen wir das Ende des Intervalls b ein. Zeile 4 ist unter der Tabellenüberschrift belegt. Wir organisieren den Prozess der Iterationen in den Zellen A5:D5 .

Der Prozess, die Nullstellen einer Funktion durch Iteration zu finden besteht aus folgenden Schritten:

Holen Sie sich eine Vorlage mit diesem Service.
Verfeinern Sie die Intervalle in den Zellen B2, B3.
Iterationszeilen bis zur erforderlichen Genauigkeit kopieren (Spalte D).

Notiz: Spalte A - Iterationsnummer, Spalte B - Wurzel der Gleichung X, Spalte C - Funktionswert F(X) , Spalte D - Genauigkeit eps .

Beispiel. Finde die Wurzel der Gleichung e -x -x=0, x=∈, ε=0.001 (8)
Lösung.
Wir stellen Gleichung (8) in der Form x=x-λ(e -x -x) dar
Finden Sie den Maximalwert der Ableitung der Funktion f(x)= e - x -x.
max f'(x) = max(-(e -x +1)) ≈ -1,37. Bedeutung . Damit lösen wir die folgende Gleichung
x=x+0,73(e-x-x)
Die Werte der sukzessiven Annäherungen sind in der Tabelle angegeben.

n	x ich	f(xi)
1	0.0	1.0
2	0.73	-0.2481
3	0.5489	0.0287
4	0.5698	-0.0042
5	0.5668	0.0006

Das System der nichtlinearen Gleichungen hat die Form:

Hier sind unbekannte Variablen, und System (7) wird ein System normaler Ordnung genannt, wenn mindestens eine der Funktionen nichtlinear ist.

Das Lösen von Systemen nichtlinearer Gleichungen ist eines der schwierigsten Probleme in der Computermathematik. Die Schwierigkeit besteht darin festzustellen, ob das System eine Lösung hat, und wenn ja, wie viele. Die Verfeinerung von Lösungen in einem bestimmten Bereich ist eine einfachere Aufgabe.

Lassen Sie Funktionen in Bereichen definiert werden. Dann ist die Region die Region, in der die Lösung gefunden werden kann. Die gebräuchlichsten Methoden zur Verfeinerung der Lösung sind die Methode der einfachen Iterationen und die Newton-Methode.

Methode einfacher Iterationen zum Lösen von Systemen nichtlinearer Gleichungen

Vom ursprünglichen System (7) gelangen wir durch äquivalente Transformationen zu einem System der Form:

Durch Formeln definierter iterativer Prozess

Sie können mit einer ersten Annäherung beginnen. Eine hinreichende Bedingung für die Konvergenz des iterativen Prozesses ist eine von zwei Bedingungen:

Schreiben wir die erste Bedingung:

Schreiben wir die zweite Bedingung:

Betrachten wir eine der Möglichkeiten, das System (7) in die Form (8) zu bringen, die konvergente Iterationen zulässt.

Gegeben sei ein System zweiter Ordnung der Form:

Es ist erforderlich, es zum Formular zu bringen:

Wir multiplizieren die erste Gleichung des Systems mit einer unbekannten Konstante, die zweite - mit, addieren sie dann und addieren sie zu beiden Seiten der Gleichung. Wir erhalten die erste Gleichung des transformierten Systems

Wir bestimmen die unbekannten Konstanten aus den hinreichenden Konvergenzbedingungen

Lassen Sie uns diese Bedingungen detaillierter schreiben:

Unter der Annahme, dass die Ausdrücke unter dem Moduluszeichen gleich Null sind, erhalten wir ein System von vier Gleichungen mit vier Unbekannten zur Bestimmung der Konstanten:

Bei einer solchen Parameterwahl sind die Konvergenzbedingungen erfüllt, wenn sich die partiellen Ableitungen der Funktionen und in der Nähe des Punktes nicht sehr schnell ändern.

Um das System zu lösen, müssen Sie die anfängliche Näherung festlegen und die Werte der Ableitungen und an dieser Stelle berechnen. Die Berechnung wird bei jedem Iterationsschritt durchgeführt, während z.

Die Methode der einfachen Iterationen ist selbstkorrigierend, universell und einfach auf einem Computer zu implementieren. Wenn das System eine große Ordnung hat, wird die Verwendung dieser Methode, die eine langsame Konvergenzrate hat, nicht empfohlen. In diesem Fall wird das Newton-Verfahren verwendet, das eine schnellere Konvergenz hat.

Newtons Methode zum Lösen von Systemen nichtlinearer Gleichungen

Es soll ein System nichtlinearer Gleichungen der Form (7) gelöst werden. Nehmen Sie an, dass die Lösung in einem Bereich existiert, in dem alle Funktionen stetig sind und mindestens die erste Ableitung haben. Das Newton-Verfahren ist ein iterativer Prozess, der nach einer bestimmten Formel folgender Form durchgeführt wird:

Schwierigkeiten bei der Anwendung des Newton-Verfahrens:

Gibt es eine inverse Matrix?

Geht es außerhalb des Bereichs?

Newtons modifiziertes Verfahren erleichtert die erste Aufgabe. Die Modifikation besteht darin, dass die Matrix nicht an jedem Punkt berechnet wird, sondern nur am Anfang. Somit hat das modifizierte Newton-Verfahren die folgende Formel:

Aber das modifizierte Newton-Verfahren gibt keine Antwort auf die zweite Frage.

Der Iterationsprozess gemäß den Formeln (8) oder (10) endet, wenn die folgende Bedingung erfüllt ist

Der Vorteil des Newton-Verfahrens ist seine schnelle Konvergenz im Vergleich zum Verfahren der einfachen Iterationen.

Lösen nichtlinearer Gleichungen

Lassen Sie es erforderlich sein, um die Gleichung zu lösen

Wo
ist eine nichtlineare stetige Funktion.

Methoden zum Lösen von Gleichungen werden in direkte und iterative unterteilt. Direkte Methoden sind Methoden, mit denen Sie eine Lösung mithilfe einer Formel berechnen können (z. B. um die Wurzeln einer quadratischen Gleichung zu finden). Iterative Methoden sind Methoden, bei denen eine anfängliche Annäherung gegeben ist und eine konvergierende Folge von Annäherungen an die exakte Lösung konstruiert wird, wobei jede nachfolgende Annäherung unter Verwendung der vorherigen berechnet wird.

Die vollständige Lösung des Problems kann in 3 Phasen unterteilt werden:

Legen Sie Anzahl, Art und Ort der Wurzeln von Gleichung (1) fest.

Finden Sie ungefähre Werte der Wurzeln, d.h. Geben Sie die Lücken an, in denen die Wurzeln gefunden werden (trennen Sie die Wurzeln).

Finden Sie den Wert der Wurzeln mit der erforderlichen Genauigkeit (geben Sie die Wurzeln an).

Zur Lösung der ersten beiden Probleme gibt es verschiedene grafische und analytische Methoden.

Das anschaulichste Verfahren zum Trennen der Wurzeln von Gleichung (1) besteht darin, die Koordinaten der Schnittpunkte des Graphen der Funktion zu bestimmen
mit der Abszissenachse. Abszissen Schnittpunkte des Diagramms
mit Achse
sind die Wurzeln von Gleichung (1)

Die Isolationsintervalle der Wurzeln von Gleichung (1) können analytisch erhalten werden, basierend auf Sätzen über die Eigenschaften von Funktionen, die auf einem Segment stetig sind.

Wenn zum Beispiel die Funktion
kontinuierlich auf dem Segment
und
, dann nach dem Satz von Bolzano-Cauchy auf dem Segment
es gibt mindestens eine Wurzel von Gleichung (1) (eine ungerade Anzahl von Wurzeln).

Wenn die Funktion
die Bedingungen des Bolzano-Cauchy-Theorems erfüllt und auf diesem Segment monoton ist, dann weiter
es gibt nur eine Wurzel von Gleichung (1), also hat Gleichung (1) eine
die einzige Wurzel, wenn die Bedingungen erfüllt sind:

Wenn eine Funktion auf einem gegebenen Intervall stetig differenzierbar ist, dann kann man das Korollar des Satzes von Rolle verwenden, wonach zwischen zwei Wurzeln immer mindestens ein stationärer Punkt liegt. Der Algorithmus zur Lösung des Problems in diesem Fall lautet wie folgt:

Ein nützliches Werkzeug zum Trennen von Wurzeln ist auch die Verwendung des Satzes von Sturm.

Die Lösung des dritten Problems wird durch verschiedene iterative (numerische) Verfahren durchgeführt: das Dichotomie-Verfahren, das einfache Iterationsverfahren, das Newton-Verfahren, das Akkordverfahren usw.

Beispiel Lösen wir die Gleichung
Methode einfache Iteration. Legen wir fest
. Lassen Sie uns einen Graphen der Funktion erstellen.

Die Grafik zeigt, dass die Wurzel unserer Gleichung zum Segment gehört
, d.h.
ist das Isolationssegment der Wurzel unserer Gleichung. Prüfen wir dies analytisch, d.h. Erfüllung der Bedingungen (2):

Erinnern Sie sich, dass die ursprüngliche Gleichung (1) in der einfachen Iterationsmethode in die Form transformiert wird
und Iterationen erfolgen nach der Formel:

(3)

Das Durchführen von Berechnungen gemäß Formel (3) wird als eine Iteration bezeichnet. Die Iterationen werden beendet, wenn die Bedingung erfüllt ist
, wo ist der absolute Fehler beim Finden der Wurzel, oder
, wo -relativer Fehler.

Das einfache Iterationsverfahren konvergiert, wenn die Bedingung
zum
. Funktionsauswahl
in Formel (3) für Iterationen kann man die Konvergenz des Verfahrens beeinflussen. Im einfachsten Fall
mit Plus- oder Minuszeichen.

In der Praxis wird es oft geäußert
direkt aus Gleichung (1). Wenn die Konvergenzbedingung nicht erfüllt ist, wird sie in die Form (3) umgewandelt und ausgewählt. Wir stellen unsere Gleichung in der Form dar
(Wir drücken x aus der Gleichung aus). Überprüfen wir die Konvergenzbedingung der Methode:

zum
. Beachten Sie, dass die Konvergenzbedingung nicht erfüllt ist
, also nehmen wir das Root-Isolationssegment
. Nebenbei bemerken wir das bei der Darstellung unserer Gleichung in der Form
, ist die Konvergenzbedingung des Verfahrens nicht erfüllt:
auf dem Segment
. Das zeigt die Grafik
steigt schneller als die Funktion
(|tg| Neigungswinkel der Tangente an
auf dem Segment
)

Lass uns aussuchen
. Wir organisieren Iterationen nach der Formel:

Wir organisieren den Prozess der Iterationen programmatisch mit einer bestimmten Genauigkeit:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

während abs(x1-x)> eps tun

x1:=f1(x):

print(evalf(x1,8)):

print(abs(x1-x)):

:printf("Anzahl der Iterationen=%d ",k):

Ende:

Bei Iteration 19 haben wir die Wurzel unserer Gleichung erhalten

mit absolutem Fehler

Lösen wir unsere Gleichung Newtons Methode. Iterationen im Newton-Verfahren werden nach der Formel durchgeführt:

Das Newton-Verfahren kann als Methode der einfachen Iteration mit einer Funktion betrachtet werden, dann kann die Konvergenzbedingung des Newton-Verfahrens geschrieben werden als:

In unserer Bezeichnung
und die Konvergenzbedingung auf dem Segment erfüllt ist
was auf der Grafik zu sehen ist:

Denken Sie daran, dass das Newton-Verfahren quadratisch konvergiert und die anfängliche Näherung ausreichend nahe an der Wurzel gewählt werden muss. Machen wir die Berechnungen:
, erste Annäherung, . Wir organisieren Iterationen nach der Formel:

Wir organisieren den Prozess der Iterationen programmatisch mit einer bestimmten Genauigkeit. Bei 4 Iterationen erhalten wir die Wurzel der Gleichung

Mit
Wir haben Methoden zum Lösen nichtlinearer Gleichungen unter Verwendung von kubischen Gleichungen als Beispiel betrachtet; natürlich werden verschiedene Arten von nichtlinearen Gleichungen durch diese Methoden gelöst. Zum Beispiel die Gleichung lösen

Newtonsche Methode mit
, finden wir die Wurzel der Gleichung auf [-1,5;-1]:

Übung: Lösen Sie nichtlineare Gleichungen mit Präzision

Halbieren eines Segments (Dichotomie)

einfache Iteration.

Newton (Tangente)

Sekante - Akkord.

Aufgabenoptionen werden wie folgt berechnet: Die Listennummer wird durch 5 geteilt (
), entspricht der ganzzahlige Teil der Gleichungsnummer, der Rest entspricht der Methodennummer.

MINISTERIUM FÜR BILDUNG UND WISSENSCHAFT DER UKRAINE

SUMY STAATLICHE UNIVERSITÄT

Institut für Informatik

KURSARBEIT

DURCH DEN KURS:

Numerische Methoden

"Iterative Methoden zum Lösen von Systemen nichtlinearer Gleichungen"

1. Methoden zum Lösen von Systemen nichtlinearer Gleichungen. allgemeine Informationen

2.1 Methode einfacher Iterationen

2.2 Aitken-Transformation

2.3 Newtonsche Methode

2.3.1 Modifikationen des Newton-Verfahrens

2.3.2 Quasi-Newtonsche Methoden

2.4 Andere iterative Methoden zum Lösen von Systemen nichtlinearer Gleichungen

2.4.1 Picard-Methode

2.4.2 Gradientenabstiegsverfahren

2.4.3 Entspannungsverfahren

3. Implementierung iterativer Verfahren programmatisch und unter Verwendung des mathematischen Pakets Maple

3.1 Einfaches Iterationsverfahren

3.2 Gradientenabstiegsverfahren

3.3 Newtonsche Methode

3.4 Modifiziertes Newton-Verfahren

Verzeichnis der verwendeten Literatur

1. Methoden zum Lösen nichtlinearer Gleichungen. Allgemeine Informationen.

Gegeben sei ein Gleichungssystem, wobei

- einige nichtlineare Operatoren: (1.1)

Es kann auch in Matrixform dargestellt werden:

(1.1)

Seine Lösung heißt ein solcher Wert

, wofür

Ein sehr häufiges Rechenproblem besteht darin, einige oder alle Lösungen des Systems (1.1) zu finden n nichtlineare algebraische oder transzendente Gleichungen mit n Unbekannt.

Bezeichne mit X Spaltenvektor ( X 1 , X 2 ,..., xn)T und schreiben Sie das Gleichungssystem in Form von Formel (1.2): F(X) = 0, wo F=(f 1 , f 2 ,...,Fn)T.

Solche Gleichungssysteme können direkt, beispielsweise beim Entwurf physikalischer Systeme, oder indirekt entstehen. So zum Beispiel bei der Lösung des Problems der Minimierung einer bestimmten Funktion G(X) ist es oft notwendig, diejenigen Punkte zu bestimmen, an denen die Steigung dieser Funktion gleich Null ist. Vorausgesetzt F= Grad g, wir erhalten ein nichtlineares System.

Im Gegensatz zu Systemen linearer algebraischer Gleichungen, die mit beiden gelöst werden können gerade(oder präzise), so und iterativ(oder ungefähr)-Methoden kann die Lösung von Systemen nichtlinearer Gleichungen nur durch näherungsweise, iterative Verfahren erfolgen. Sie erlauben es, eine Folge von Annäherungen zu erhalten

. Konvergiert der Iterationsprozess, so ist der Randwert die Lösung des gegebenen Gleichungssystems.

Für ein vollständiges Verständnis der Methoden zum Finden einer Lösung für das System ist es notwendig, ein solches Konzept wie die "Konvergenzrate" zu erklären. Wenn für die Sequenz x n, bis an die Grenze konvergieren X *, die Formel stimmt

(k eine positive reelle Zahl ist), dann k heißt Konvergenzrate der gegebenen Folge.

2. Iterative Verfahren zum Lösen von Systemen nichtlinearer Gleichungen

2.1 Methode einfacher Iterationen

Die Methode der einfachen Iterationen (sukzessiven Approximationen) ist eine der Hauptmethoden in der Computermathematik und wird verwendet, um eine große Klasse von Gleichungen zu lösen. Lassen Sie uns dieses Verfahren für Systeme nichtlinearer Gleichungen der Form beschreiben und begründen

f ich (x 1 , x 2 , ... x n) = 0, ich=1,2,..n;

Wir bringen das Gleichungssystem auf eine spezielle Form:

(2.1)

Oder in Vektorform

. (2.2)

Außerdem sollte der Übergang zu diesem System nur unter der Bedingung erfolgen, dass

ist eine Kontraktionsabbildung.

Unter Verwendung einer anfänglichen Annäherung X(0) = (x 1 (0) ,x 2 (0) ,...x n (0))

konstruieren Sie einen iterativen Prozess X (k+1) =  (X (k)). Die Berechnungen werden fortgesetzt, bis die Bedingung erfüllt ist

. Dann ist die Lösung des Gleichungssystems der Fixpunkt der Abbildung.

Lassen Sie uns die Methode in einer bestimmten Norm begründen

Räume.

Stellen wir einen Konvergenzsatz vor, dessen Erfüllung zur Lösung des Systems führt.

Satz (über Konvergenz). Lassen

eines). Die Vektorfunktion Ä(х) ist im Definitionsbereich definiert

; die Bedingung

3). faire Ungleichheit

Dann in einem iterativen Prozess:

, – Lösung des Gleichungssystems; ,

Kommentar. Die Ungleichung von Bedingung 2) ist die Lipschitz-Bedingung für die Vektorfunktion Ä(х) im Definitionsbereich S mit einer Konstante

(Kompressionszustand). Es zeigt, dass F ist der Kontraktionsoperator in der Domäne S, d.h. Gleichung (2.2) unterliegt dem Kontraktionsabbildungsprinzip. Die Aussagen des Satzes bedeuten, dass Gleichung (2.2) im Bereich eine Lösung hat S, und sukzessive Näherungen konvergieren gegen diese Lösung mit der Rate einer geometrischen Folge mit Nenner q.

Nachweisen. Weil die

, dann haben wir für die Näherung aufgrund von Annahme 3) . Es bedeutet das. Zeigen wir, dass , k=2,3,… und für benachbarte Näherungen die Ungleichung (2.3) erfüllt ist

Wir werden per Induktion argumentieren. Bei

die Aussage ist wahr, weil und . Nehmen wir an, dass die Näherungen zu S gehören und Ungleichung (2.3) für gilt. Da gilt dann für die Berücksichtigung von Bedingung 2) des Satzes .

Nach der Induktionsannahme