Fixpunktiteration
Eine Fixpunktiteration (oder auch ein Fixpunktverfahren) ist in der Mathematik ein numerisches Verfahren zur näherungsweisen Bestimmung von Lösungen einer Gleichung oder eines Gleichungssystems. Die Gleichung muss dazu zuerst in eine Fixpunktgleichung, also in eine Gleichung der Form
- <math>\varphi(x) = x</math>
mit einer Funktion <math>\varphi</math> umgeformt werden. Anschließend wird eine Startnäherung <math>x_0</math> gewählt und <math>x_1 = \varphi(x_0)</math> berechnet. Das Ergebnis wird wieder in die Funktion <math>\varphi</math> eingesetzt, <math>x_2 = \varphi(x_1)</math> und so weiter. Unter geeigneten Zusatzvoraussetzungen nähert sich die so erhaltene Folge <math>x_0, x_1, x_2, \dotsc</math> einer Lösung von <math>\varphi(x) = x</math> und somit einer Lösung des ursprünglichen Problems immer weiter an.
Allgemeines Verfahren
Gegeben seien eine Funktion <math>\varphi\colon M \to M</math>, die eine Menge <math>M</math> in sich selbst abbildet, sowie ein Startelement <math>x_0 \in M</math>. Die durch das zugehörige Fixpunktverfahren erzeugte Folge <math>(x_k)_{k \in \N_0}</math> in <math>M</math> ist dann iterativ definiert durch
- <math>x_{k+1} = \varphi(x_k)</math> für <math>k \in \N_0</math>.
Wenn auf der Menge <math>M</math> ein Konvergenzbegriff vorhanden ist, kann man sich fragen, ob diese Folge gegen einen Fixpunkt von <math>\varphi</math>, das heißt gegen ein <math>x^*</math> mit <math>\varphi(x^*) = x^*</math> konvergiert. Der banachsche Fixpunktsatz gibt relativ allgemeine Bedingungen an, unter denen das der Fall ist: Ist <math>M</math> ein vollständiger metrischer Raum, also beispielsweise eine abgeschlossene Teilmenge des <math>\R^n</math> oder ein Banachraum, und <math>\varphi</math> eine Kontraktion, dann existiert in der Menge <math>M</math> genau ein Fixpunkt <math>x^*</math> von <math>\varphi</math> und die durch das Fixpunktverfahren erzeugte Folge konvergiert für beliebige <math>x_0 \in M</math> gegen <math>x^*</math>.
Beispiele
Gesucht ist die positive Lösung der Gleichung
- <math>2-x^2 = e^x</math>.
Durch Logarithmieren erhält man die Fixpunktgleichung
- <math>\ln(2-x^2) = x</math>.
Die durch <math>\varphi(x) = \ln(2-x^2)</math> gegebene Iterationsfunktion bildet beispielsweise das Intervall <math>M = [0{,}2; 0{,}7]</math> in sich selbst ab und ist auf <math>M</math> eine Kontraktion (siehe nebenstehende Abbildung).
Ausgehend vom Startwert <math>x_0 = 0{,}2</math> ergibt sich für die nächsten Iterationsschritte <math>x_1 = \varphi(x_0) \approx 0{,}6729</math>, <math>x_2 = \varphi(x_1) \approx 0{,}4364</math>, <math>x_3 = \varphi(x_2) \approx 0{,}5931</math> usw. Bei der Näherung nach 20 Schritten <math>x_{20} \approx 0{,}5373</math> stimmen bereits die ersten vier Nachkommastellen mit der exakten Lösung überein.
Auch das Heron-Verfahren stellt eine Fixpunktiteration dar.<ref>{{#if:2019-08-22|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C{{#if:Passende Umformungen: Nullstellen und Fixpunkte|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1=https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Passende Umformungen: Nullstellen und Fixpunkte}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7Cja}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Passende Umformungen: Nullstellen und Fixpunkte}}}}|[{{#invoke:URLutil|getNormalized|1=http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Passende Umformungen: Nullstellen und Fixpunkte}}}}]}}{{#if:| ({{{format}}}{{#if:jaMontanuniversität Leoben2005-02-23https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ;
| )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}}%7C%7C}}}}{{#if:Passende Umformungen: Nullstellen und Fixpunkte|{{#if:{{#invoke:WLink|isValidLinktext|1=Passende Umformungen: Nullstellen und Fixpunkte|lines=0}}||}}}}{{#if: Montanuniversität Leoben| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Montanuniversität Leoben}}}}{{#if: | {{{hrsg}}}{{#if: 2005-02-23https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C,%7C{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: 2005-02-23| {{#if:{{#invoke:DateTime|format|2005-02-23|noerror=1}}
|{{#invoke:DateTime|format|2005-02-23|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2005-02-23|class=Zitationswartung}} }}{{#if: https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C,%7C{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C,%7C{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html{{#invoke:TemplUtl%7Cfaculty%7Cja}}%7C+{{#if:2005-02-23%7C{{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7Carchiviert%7Cehemals}}%7C{{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7CArchiviert%7CEhemals}}}}+{{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7Cvom%7Cim}}+Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|ja}}| (nicht mehr online verfügbar)}}{{#if: 2019-08-22| am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|2019-08-22{{#if:223867||(?)}}}}}}{{#if: 2019-08-27|;}}}}{{#if: 2019-08-27| {{#if:2005-02-23https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html{{#invoke:TemplUtl%7Cfaculty%7Cja}}%7Cabgerufen%7CAbgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2019-08-27 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2019-08-27|class=Zitationswartung}} }} {{#invoke:DateTime|format|2019-08-27|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:jaMontanuniversität Leoben2005-02-23https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:de|de|de}}|de||
{{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2005-02-23https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html{{#if: 2019-08-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|ja}}|{{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7C%7C{{#ifeq: ja | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if:{{#invoke:URLutil|isWebURL|http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if:{{#invoke:URLutil|isWebURL|http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if:{{#invoke:URLutil|isWebURL|http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html | {{#if:{{#invoke:URLutil|isWebURL|http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html%7CVorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> Für <math display="inline">a > 0</math> hat die Funktion <math display="inline">\varphi(x) = \frac{1}{2}\cdot\left(x + \frac{a}{x}\right)</math> den (positiven) Fixpunkt <math display="inline">x = \sqrt{a}</math>, so dass <math display="inline">\varphi(x)</math> zur numerischen Bestimmung von <math display="inline">\sqrt{a}</math> verwendet werden kann.
Ein Satz zur Existenz und Eindeutigkeit
Sei <math>f\colon [a,b] \to [a,b]\subset\R</math> eine stetig differenzierbare Funktion mit <math>f(a)>a, f(b)<b</math> und <math>f'(x)\ne 1</math> für alle <math>x</math> aus <math>(a,b)</math>. Dann existiert genau ein Fixpunkt <math>x^*</math> aus <math>(a,b)</math> mit <math>f(x^*)=x^*</math>.
Beweis
Man setze <math>F(x):=f(x)-x</math>. Dann ist <math>F(a)>0, F(b)<0</math>. Aus dem Zwischenwertsatz folgt, dass es mindestens eine Nullstelle <math>x^*\in [a,b]</math> gibt mit <math>F(x^*)=0</math>. Gäbe es eine zweite Nullstelle, etwa <math>x^{**}</math>, dann müsste es wegen <math>F(x^*)=F(x^{**})</math> nach dem Satz von Rolle einen Punkt <math>\check x </math> aus dem Intervall <math>(x^*,x^{**})</math> geben mit <math>F'(\check x) = 0</math>, was <math>f'(\check x)=1</math> impliziert im Widerspruch zur Annahme. Also ist der Fixpunkt <math>x^*</math> eindeutig.
Beispiel
Für die Funktion <math>f(x)=\frac{x^3-1} {x^3-2}</math> gilt auf <math> [-1, +1]</math>:
- <math>f(-1) > 0 > -1 </math>.
- <math>f(+1)=0<1</math>.
- <math>f'(x)=\frac {-3x^2} {(x^3-2)^2} \ne 1</math> für alle <math> x
\in (-1,+1)</math>.
Daraus folgt mit dem Satz oben, dass <math> f</math> in <Math>(-1,+1)</math> genau einen Fixpunkt besitzt (<math>x^*\approx 0{,}4722129517</math>).
Lineare Fixpunktverfahren
Konstruktionsidee
Ein wichtiger Spezialfall der Fixpunktiteration sind die Splitting-Verfahren. Um ein lineares Gleichungssystem
- <math>Ax = b</math>
mit einer nichtsingulären n×n-Matrix <math>A</math> und einem Vektor <math>b</math> in eine Fixpunktgleichung umzuformen, zerlegt man die Matrix <math>A</math> mit Hilfe einer nichtsingulären n×n-Matrix <math>B</math> in
- <math>A = B + (A - B)</math>.
Damit folgt
- <math>Ax = b</math>
- <math>Bx + (A - B)x = b</math>
- <math>\Rightarrow x = B^{-1}b - B^{-1}(A-B)x = (E - B^{-1}A)x + B^{-1}b</math>,
wobei <math>E</math> die Einheitsmatrix bezeichnet.
Das lineare Gleichungssystem <math>Ax=b</math> ist dann äquivalent zu der Fixpunktaufgabe <math>x = \varphi(x)</math> mit
- <math>\varphi(x) = (E - B^{-1}A)x + B^{-1}b</math>.
Man erhält für einen vorgegebenen Startvektor <math>x_0</math> folgendes Iterationsverfahren für <math>k = 0,1,\ldots</math>
- <math>x_{k+1} = (E - B^{-1}A)x_k + B^{-1}b</math>,
und die zugehörige Iterationsmatrix lautet: <math>E - B^{-1}A</math>.
Konvergenz
Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor <math>x_0</math> konvergieren, falls der Spektralradius der Iterationsmatrix
- <math>\rho(E - B^{-1}A) = \max_i|\lambda_i(E - B^{-1}A)| < 1</math>.
<math>\rho(E - B^{-1}A)</math> sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.
Spezielle Verfahren
Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren zur Lösung von linearen Gleichungssystemen:
- Gauß-Seidel-Verfahren oder auch Einzelschrittverfahren (ESV)
- Jacobi-Verfahren oder auch Gesamtschrittverfahren (GSV)
Bemerkungen
Iterationsverfahren der Form <math>x_{k+1} = Mx_k + v</math>, k = 0, 1, ... sind
- linear, d. h. xk+1 hängt linear nur von xk ab,
- stationär, d. h. M und v sind unabhängig von der Schrittnummer der Iteration,
- einstufig, d. h. nur der letzte und nicht noch weitere Näherungsvektoren werden verwendet.
Nichtlineare Gleichungen
Das Newton-Verfahren kann als Fixpunktiteration betrachtet werden. Allgemein wird die Konvergenz mit Hilfe des banachschen Fixpunktsatzes sichergestellt, die betrachtete Funktion muss also insbesondere im betrachteten Gebiet eine Kontraktion sein.
Literatur
- Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2.
- Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065665-7.
Einzelnachweise
<references />
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Numerische Mathematik