[WS] Eindimensionale Nullstellenprobleme 3 - Vergleich

29.08.2007, 09:07	tigerbine	Auf diesen Beitrag antworten »
[WS] Eindimensionale Nullstellenprobleme 3 - Vergleich Gliederung Fibonacci - Zahlen Sekanten - Methode Regula Falsi
30.08.2007, 00:53	tigerbine	Auf diesen Beitrag antworten »
1. Fibonacci-Zahlen Die Fibonacci-Folge ist wie folgt rekursiv definiert: $\begin{eqnarray} a_0 = a_1=1 \end{eqnarray}$ $\begin{eqnarray} a_{n+1} = a_n+ a_{n-1},~\quad n \in\mathbb N \end{eqnarray}$ Für den Quotient aufeinander folgernder Folgenglieder gilt: $\begin{eqnarray} \lim_{n \to \infty}~\frac{a_{n+1}}{a_n} = \Phi = \frac{1 + \sqrt{5}}{2} = 1{,}618033988\dots \end{eqnarray}$ (Goldener Schnitt) Ansatz: $\begin{eqnarray} \frac{a_{n+1}}{a_n} = \frac{a_n+a_{n-1}}{a_n} = 1+\frac{a_{n-1}}{a_n} \end{eqnarray}$ Sofern die Folge also gegen einen Grenzwert c konvergiert, gilt dann: $\begin{eqnarray} c = 1 + \frac{1}{c} \end{eqnarray}$ und somit gilt $\begin{eqnarray} c = \Phi \end{eqnarray}$ Direkte Berechnungsvorschrift (Binet) $\begin{eqnarray} a_n = \frac{1}{\sqrt{5}}(\Phi^n - \bar \Phi^n) \end{eqnarray}$ mit $\begin{eqnarray} \bar \Phi = 1-\Phi = \frac{1-\sqrt{5}}{2} \end{eqnarray}$ berechnen. Die Ganzzahligkeit der Folgenglieder ist dadurch gewährleistet, dass sich ungerade Potenzen von $\begin{eqnarray} \sqrt{5} \end{eqnarray}$ stets aufheben.
30.08.2007, 01:39	tigerbine	Auf diesen Beitrag antworten »
2. Sekanten - Verfahren In der Einführung [Workshop - Eindimensionale Nullstellenprobleme 1] wurde die Methode ja bereits vorgestellt. Nun soll sich mit der Frage beschäftigt werden: "Ist die Sekante die bessere Tangente?" Die Iterationsvorschrift lautet hier nun also, mit dem Differenzenquotient: $\begin{eqnarray} x_{k+1} &&= x_k - \frac{f(x_k)}{\frac{f(x_k)-f(x_{k-1})}{x_k-x_{x-1}}} \\ && = x_k - f(x_k) \cdot \frac{x_k-x_{x-1}}{f(x_k)-f(x_{k-1})} \end{eqnarray}$ Wie schon erwähnt, ist dies eine Drei-Term-Rekursion. Zum Start benötigt man also 2 Werte $\begin{eqnarray} x_0, x_1 \end{eqnarray}$ . Nun soll in Analogie zum Newton-Verfahren die Konvergenz und das Konvergenzverhalten untersucht werden.
30.08.2007, 02:40	tigerbine	Auf diesen Beitrag antworten »
2a. Sekanten - Verfahren für C²-Funktion Sei f auf [a,b] zweimal stetig differenzierbar mit einfacher Nullstelle in x. Gilt dann auf dem Intervall $\begin{eqnarray} ,f'(x) \neq 0,~f''(x^) \neq 0 \end{eqnarray}$ , so konvergiert das Sekantenverfahren mit der Ordnung $\begin{eqnarray} p =\frac{1+\sqrt{5}}{2} \end{eqnarray}$ Beweis: Schritt 1: Aufgrund der Kompaktheit des Intervalls und der Stetigkeit der Funktionen f', f'' existieren: $\begin{eqnarray} m:= \min_{x \in[a,b]}~\|f'(x)\| > 0 \end{eqnarray}$ $\begin{eqnarray} M:= \max_{x \in [a,b]}~\|f''(x)\| < 0 \end{eqnarray}$ Betrachte man nun den Differenzenquotienten $\begin{eqnarray} \frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}} \end{eqnarray}$ So folgt aus dem Mittelwertsatz der Differentialrechung die Abschätzung: $\begin{eqnarray} \frac{\|f(x_k) - f(x_{k-1})\|}{\|x_k-x_{k-1}\|} \geq {m} > 0 \end{eqnarray}$ Schritt 2: Nun benötigen man Wissen aus dem [Workshop - Polynominterpolation]. Man bestimmt ein Interpolationspolynom und den zugehörigen Interpolationsfehler. Interpoliert wird in den Punkten $\begin{eqnarray} x_k,~x_{k-1} \end{eqnarray}$ . Dann lautet die Newton-Form des IPs (beachte die Gestalt der dividierten Differenzen): $\begin{eqnarray} p_2(x) = f(x_k) + (x-x_k) \cdot \frac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}} \end{eqnarray}$ Für den Interpolationsfehler gilt: $\begin{eqnarray} \varepsilon(x) = (x-x_k)(x-x_{k-1}) \cdot \frac{f''(\xi)}{2},~\xi \in [a,b] \end{eqnarray}$ Somit erhält man: $\begin{eqnarray} 0 = f(x^) = f(x_k) + (x^-x_k) \cdot \frac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}}+(x^-x_k)(x^-x_{k-1}) \cdot \frac{f''(\xi)}{2} \end{eqnarray}$ $\begin{eqnarray} 0 =f(x_k) + (x^-x_k) \cdot \frac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}}+(x^-x_k)(x^-x_{k-1}) \cdot \frac{f''(\xi)}{2} \end{eqnarray}$ Mit der Iterationsvorschrift des Sekantenverfahrens $\begin{eqnarray} x_{k+1} = x_k - f(x_k) \cdot \frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} \Leftrightarrow f(x_k)=(x_k-x_{k-1}) \cdot \frac{f(x_k) -f( x_{k+1})}{x_k - x_{k-1}} \end{eqnarray}$ ergibt sich dann: $\begin{eqnarray} (x^-x_{k+1}) \cdot \frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}+(x^-x_k)(x^-x_{k-1}) \cdot \frac{f''(\xi)}{2}=0 \end{eqnarray}$ Schritt 3: Nun stellt man das Ergebnis von 2 um $\begin{eqnarray} (x^-x_{k+1}) = - \frac{1}{\frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}} \cdot (x^-x_k)(x^-x_{k-1}) \cdot \frac{f''(\xi)}{2} \end{eqnarray}$ Betragsmäßig also $\begin{eqnarray} \|x^-x_{k+1}\| = \| \frac{1}{\frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}}\| \cdot \|x^-x_k\|\cdot \|x^-x_{k-1}\| \cdot \|\frac{f''(\xi)}{2}\| \end{eqnarray}$ Mit den Abschätzungen aus Schritt 1 folgt nun also $\begin{eqnarray} \|x^-x_{k+1}\| \leq \frac{M}{2m} \cdot \|x^-x_k\|\cdot \|x^-x_{k-1}\| \end{eqnarray}$ (#) Diese Art der Abschätzung kennt man schon aus [Workshop - Eindimensionale Nullstellenprobleme 2] Daraus folgt, dass die Sekantenmethode konvergieren wird, wenn man die Startwerte nur nahe genug bei x wählt. Was nun noch fehlt die Bestimmung des Exponenten q (Bezeichnung siehe Linkverweis). Nun setzt man $\begin{eqnarray} \|x^-x_k\| = K \cdot \|x^-x_{k-1}\|^q \end{eqnarray}$ und damit erhält man auch $\begin{eqnarray} \|x^-x_{k+1}\| = K \cdot \|x^-x_{k}\|^q = K \cdot \Bigl( K\cdot \|x-x_{k-1}\|^q\Bigr)^q = K^{q+1}\cdot \|x^-x_{k-1}\|^{q \cdot q} \end{eqnarray}$ Eingesetzt in (#) ergibt sich dann: $\begin{eqnarray} K^{q+1}\cdot \|x^-x_{k-1}\|^{q \cdot q}\leq \frac{M}{2m} \cdot K\cdot \|x^-x_{k-1}\|^{q+1} \end{eqnarray}$ Nun kommen wir zur Grenzwertbetrachtung. Da die Folge für geeignete Startwerte konvergiert, nähern sich die beiden Seiten also beliebig nahe an. Aus dem $\begin{eqnarray} \leq \end{eqnarray}$ wird also beim Übergang ein $\begin{eqnarray} = \end{eqnarray}$ $\begin{eqnarray} K =( \frac{M}{2m})^{\frac{1}{q}} \end{eqnarray}$ $\begin{eqnarray} q^2 = q+1 \Rightarrow q = \frac{1 + \sqrt{5}}{2} \end{eqnarray}$ Somit gilt also die behauptete asymptotische Konvergenzordnung für geeignete Startwerte.
31.08.2007, 02:09	tigerbine	Auf diesen Beitrag antworten »
2b. Sekante oder Tangente? Kommen wir nun zur dieser Frage zurück. Was ist besser Sekantenverfahren oder Newton-Verfahren? Beim Sekantenverfahren ist je Schritt nur eine neue Funktionsauswertung nötig, wogegen beim Newton-verfahren die Funktion und die Ableitung ausgewertet werden müssen. Faßt man nun 2 Schritte des Sekantenverfahrens zusammen, so erhält man ein Verfahren mit der asymtotischen Ordnung von $\begin{eqnarray} (\frac{1+\sqrt{5}}{2})^2 \approx 2.168 \end{eqnarray}$ Lokal ist das Sekantenverfahren also schneller als das Newton-verfahren. Jedoch kann es diesen Vorteil auch sofort wieder verlieren, da es in der Nähe der gesuchten x* bei (nicht alternierenden Vorzeichen ) im Nenner zur Auslöschung kommen kann. Und nun? Die Lösung liegt in einem Mittelweg. Der Regula Falsi.
31.08.2007, 02:15	tigerbine	Auf diesen Beitrag antworten »
3. Regula Falsi Die Probleme beim Sekantenverfahren sollen nun dadurch beseitigt werden, dass sichergestellt wird, dass gilt: $\begin{eqnarray} f(x_k)\cdot f(x_{k-1}) < 0 \end{eqnarray}$ Damit dies möglich ist, muss es sich bei x* um eine Nullstelle mit Vorzeichenwechsel handeln (ungerade Vielfachheit). Das Verfahren konvergiert sicher gegen die Nullstelle, die Konvergenzordnung ist i.A. jedoch nur linear. Es kann in Extremfällen sogar langsamer konvergieren als das einfache Intervallschachtelungsverfahren.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »