Euler-Tschebyschow-Verfahren

Das Euler-Tschebyschow-Verfahren (nach Leonhard Euler und Pafnuti Lwowitsch Tschebyschow; auch Verfahren der berührenden Parabeln) bezeichnet in der numerischen Mathematik ein iteratives 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
F(x)=0F(x)=0 einer Funktion F:D⊂Rn→RnF:D\subset\mathbb{R}^n \to \mathbb{R}^n
und einen hinreichend guten Startwert x0x_0, so erhält man über eine näherungsweise Berechnung der Nullstelle der abgebrochenen Taylorentwicklung
0=F(xk)+F′(xk)(x−xk)+12F′′(xk)(x−xk)20=F(x^k)+F'(x^k)(x-x^k)+\dfrac{1}{2}F''(x^k)(x-x^k)^2
in jedem Schritt das folgende Verfahren. Die genaue Herleitung des Verfahrens ist in Halley-Verfahren im Abschnitt zum mehrdimensionalen Fall beschrieben.

Algorithmus

  1. Wähle einen Startwert x0∈Rnx_0 \in \mathbb{R}^n, ein ε>0, N∈N\varepsilon>0,\, N \in \mathbb{N}, setze k=0k=0
    1. Falls ∥F(xk)∥<ε\|F(x_k)\|<\varepsilon oder k>Nk>N Stopp
    2. Löse :F′(xk)sk=−F(xk)F'(x_k)s_k=-F(x_k), (Newton-Schritt)
    3. Löse :F′(xk)tk=−12F′′(xk)(sk,sk)F'(x_k)t_k=-\dfrac{1}{2}F''(x_k)(s_k,s_k), (quadratische Korrektur)
    4. Setze xk+1=xk+sk+tk, k=k+1x_{k+1}=x_k+s_k+t_k,\, k=k+1

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 f(x)=x+exf(x)=x+e^x mit dem Startwert 0 genommen werden. Die erste Ableitung ist f ´(x)=1+exf\, ´(x)=1+e^x die zweite Ableitung f ′′(x)=exf\, ''(x)=e^x
  • Schritt 1
    • f(0)=1f(0)=1, f ′(0)=2 f\, '(0)=2, f ′′(0)=1f\, ''(0)=1
    • s0=−f(0)f′(0)=−0 5s_0=-\dfrac{f(0)}{f'(0)}=-0\, 5
    • t0=−12⋅f′′(0)⋅s02f ′(0)=−0 0625t_0=-\dfrac{1}{2}\cdot \dfrac{f''(0) \cdot s_0^2}{f\, '(0)}=-0\, 0625
    • x1=x0+s0+t0=−0 5625x_1=x_0+s_0+t_0=-0\, 5625
  • Schritt 2
    • f(−0 5625)=0 0073f(-0\, 5625)=0\, 0073, f ′(−0 5625)=1 5698f\, '(-0\, 5625)=1\, 5698, f ′′(−0 5625)=0 5698f\, ''(-0\, 5625)=0\, 5698
    • s1=−f(−0 5625)f ′(−0 5625)=−0 0046s_1=-\dfrac{f(-0\, 5625)}{f\, '(-0\, 5625)}=-0\, 0046
    • t1=−12⋅f′′(−0 5625)⋅s12f ′(−0 5625)=−3 9063⋅10−6t_1=-\dfrac{1}{2}\cdot \dfrac{f''(-0\, 5625) \cdot s_1^2}{f\, '(-0\, 5625)}=-3\, 9063 \cdot 10^{-6}
    • x2=x1+s1+t1=−0 5671x_2=x_1+s_1+t_1=-0\, 5671
Nach dem 2. Schritt erhält man als Funktionswert f(−0 5671)=8 3450⋅10−10f(-0\, 5671)=8\, 3450\cdot 10^{-10} und kann abbrechen.

Literatur

 
 

In der Mathematik gibt es keine Autoritäten. Das einzige Argument für die Wahrheit ist der Beweis.

K. Urbanik

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Euler-Tschebyschow-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren