Wikipedia · einfach zusammengefasst · Stand
Euler-Tschebyschow-Verfahren
... Mathematik ein iteratives Verfahren zum Lösen nichtlinearer Gleichungen. Es ist vergleichbar mit dem Newton-Verfahren, hat jedoch die Konvergenzordnung 3.
Inhalt4 Abschnitte
Grundidee und mathematische Grundlage
Das Euler-Tschebyschow-Verfahren ist ein iteratives Verfahren der Numerischen Mathematik zum Lösen nichtlinearer Gleichungen. Es wird auch als Verfahren der berührenden Parabeln bezeichnet. Das Verfahren ist mit dem Newton-Verfahren vergleichbar, besitzt aber die Konvergenzordnung 3.
Ausgangspunkt ist eine Gleichung in Nullstellenform:
F(x) = 0
Dabei ist F eine Funktion F: D ⊆ ℝⁿ → ℝⁿ, und x₀ ist ein hinreichend guter Startwert. In jedem Iterationsschritt wird die Taylorentwicklung von F an der Stelle xₖ nach dem quadratischen Term abgebrochen:
0 = F(xₖ) + F′(xₖ)(x − xₖ) + 1/2 F″(xₖ)(x − xₖ)².
Die Näherung der Nullstelle dieser abgebrochenen Taylorentwicklung führt zu einem Newton-Schritt und einer zusätzlichen quadratischen Korrektur.
Ablauf des Verfahrens
Für den Startwert x₀ ∈ ℝⁿ, eine Genauigkeit ε > 0 und eine maximale Iterationszahl N wird k = 0 gesetzt.
In jedem Schritt gilt:
- Ist ‖F(xₖ)‖ < ε oder k > N, wird das Verfahren beendet.
- Zuerst wird der Newton-Schritt sₖ aus F′(xₖ)sₖ = −F(xₖ) bestimmt.
- Danach wird die quadratische Korrektur tₖ aus F′(xₖ)tₖ = −1/2 F″(xₖ)(sₖ, sₖ) bestimmt.
- Anschließend wird der nächste Näherungswert berechnet: xₖ₊₁ = xₖ + sₖ + tₖ.
- Danach wird k um 1 erhöht und der nächste Schritt begonnen.
Die Vektoren sₖ und tₖ werden also beide über Gleichungssysteme mit der ersten Ableitung F′(xₖ) bestimmt. Der erste Anteil entspricht dem Newton-Verfahren; der zweite berücksichtigt zusätzlich den quadratischen Anteil der Taylorentwicklung.
Eigenschaften und Einsatzbedingungen
Im Gegensatz zum Newton-Verfahren benötigt das Euler-Tschebyschow-Verfahren die zweite Ableitung der Funktion. Die höhere Konvergenzordnung lohnt sich deshalb nur dann, wenn die Berechnung der zweiten Ableitung im Vergleich zur Berechnung von Funktionswert und erster Ableitung leicht ist.
Über andere Näherungen der Nullstelle der Taylorentwicklung entstehen andere Verfahren. Als Beispiel wird das Halley-Verfahren genannt. Die genaue Herleitung des Euler-Tschebyschow-Verfahrens ist im mehrdimensionalen Fall des Halley-Verfahrens beschrieben.
Eindimensionales Rechenbeispiel
Betrachtet wird die Funktion f(x) = x + eˣ mit dem Startwert x₀ = 0. Ihre Ableitungen sind f′(x) = 1 + eˣ und f″(x) = eˣ.
Im ersten Schritt gilt:
- f(0) = 1, f′(0) = 2 und f″(0) = 1.
- Der Newton-Schritt ist s₀ = −f(0)/f′(0) = −0,5.
- Die quadratische Korrektur ist t₀ = −1/2 · (f″(0) · s₀²)/f′(0) = −0,0625.
- Damit ergibt sich x₁ = x₀ + s₀ + t₀ = −0,5625.
Im zweiten Schritt werden f(−0,5625) = 0,0073, f′(−0,5625) = 1,5698 und f″(−0,5625) = 0,5698 verwendet. Daraus folgen s₁ = −0,0046 und t₁ = −3,9063 · 10⁻⁶. Somit ist x₂ = x₁ + s₁ + t₁ = −0,5671.
Nach dem zweiten Schritt beträgt der Funktionswert f(−0,5671) = 8,3450 · 10⁻¹⁰. Damit kann das Verfahren wegen der erreichten Genauigkeit abgebrochen werden.
