Quelltext der Seite Euler-Tschebyschow-Verfahren

Das '''Euler-Tschebyschow-Verfahren''' (nach [[Leonhard Euler]] und [[Pafnuti Lwowitsch Tschebyschow]]; auch ''Verfahren der berührenden Parabeln'') bezeichnet in der [[Numerische Mathematik|Numerischen Mathematik]] ein [[Iteration|iterativ]]es Verfahren zum Lösen nichtlinearer Gleichungen. Es ist vergleichbar mit dem [[Newton-Verfahren]], hat jedoch die [[Konvergenzordnung]] 3. 
== Beschreibung ==
Hat man eine nichtlineare Gleichung in Nullstellenform
:<math>F(x)=0</math> einer Funktion <math>F:D\subset\mathbb{R}^n \to \mathbb{R}^n</math>
und einen hinreichend guten Startwert <math>x_0</math>, so erhält man über eine näherungsweise Berechnung der Nullstelle der abgebrochenen Taylorentwicklung
:<math>0=F(x_k)+F'(x_k)(x-x_k)+\frac{1}{2}F''(x_k)(x-x_k)^2</math>
in jedem Schritt das folgende Verfahren. Die genaue Herleitung des Verfahrens ist in [[Halley-Verfahren]] im Abschnitt zum mehrdimensionalen Fall beschrieben.

== Algorithmus ==
# Wähle einen Startwert <math>x_0 \in \mathbb{R}^n</math>, ein <math>\varepsilon>0</math>, <math>N \in \mathbb{N}</math>, setze <math>k=0</math>
## Falls <math>\|F(x_k)\|<\varepsilon</math> oder <math>k>N</math> Stopp
## Löse :<math>F'(x_k)s_k=-F(x_k)</math>, (Newton-Schritt)
## Löse :<math>F'(x_k)t_k=-\frac{1}{2}F''(x_k)(s_k,s_k)</math>, (quadratische Korrektur)
## Setze <math>x_{k+1}=x_k+s_k+t_k</math>, <math>k=k+1</math>

== Eigenschaften ==
Offenbar benötigt man im Gegensatz zum Newton-Verfahren die 2. Ableitung der Funktion. Die Erhöhung der Konvergenzordnung lohnt sich also nur, wenn die Berechnung der 2. Ableitung im Vergleich mit der Berechnung von Funktionswert und erster Ableitung leicht ist. Über andere Näherungen der Nullstelle der Taylorentwicklung erhält man andere Verfahren. Ein Beispiel dafür wäre das [[Halley-Verfahren]].

== Beispiel ==
Als einfaches eindimensionales Beispiel soll die Berechnung der Nullstelle von <math>f(x)=x+e^x</math> mit dem Startwert 0 genommen werden. Die erste Ableitung ist <math>f'(x)=1+e^x</math> die zweite Ableitung <math>f''(x)=e^x</math>
* Schritt 1
**<math>f(0)=1</math>, <math>f'(0)=2</math>, <math>f''(0)=1</math>
** <math>s_0=-\frac{f(0)}{f'(0)}=-0{,}5</math>
** <math>t_0=-\frac{1}{2}\cdot \frac{f''(0) \cdot s_0^2}{f'(0)}=-0{,}0625</math>
** <math>x_1=x_0+s_0+t_0=-0{,}5625</math>
* Schritt 2
**<math>f(-0{,}5625)=0{,}0073</math>, <math>f'(-0{,}5625)=1{,}5698</math>, <math>f''(-0{,}5625)=0{,}5698</math>
** <math>s_1=-\frac{f(-0{,}5625)}{f'(-0{,}5625)}=-0{,}0046</math>
** <math>t_1=-\frac{1}{2}\cdot \frac{f''(-0{,}5625) \cdot s_1^2}{f'(-0{,}5625)}=-3{,}9063 \cdot 10^{-6}</math>
** <math>x_2=x_1+s_1+t_1=-0{,}5671</math>
Nach dem 2. Schritt erhält man als Funktionswert <math>f(-0{,}5671)=8{,}3450\cdot 10^{-10}</math> und kann abbrechen.

== Literatur ==
* Hubert Schwetlick: ''Numerische Lösung nichtlinearer Gleichungen.'' Deutscher Verlag der Wissenschaften, Berlin 1979, 346 S.

{{SORTIERUNG:Eulertschebyschowverfahren}}
[[Kategorie:Numerische Mathematik]]
[[Kategorie:Leonhard Euler als Namensgeber]]
[[Kategorie:Pafnuti Lwowitsch Tschebyschow]]