[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren

Neue Frage »

16.08.2007, 17:45	tigerbine	Auf diesen Beitrag antworten »
[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren Gliederung Eindimensionale Nullstellenprobleme Bisektionsverfahren 2a. Beschreibung des Verfahren 2b. Bewertung Newton-Verfahren 3a. Beschreibung des Verfahrens 3b. Bewertung Sekanten-Verfahren 4a. Newton-Verfahren mit finiten Differenzen 4b. Drei-Term-Rekursion 4c. Probleme Regula falsi Methode der inversen quadratischen Interpolation
16.08.2007, 18:04	tigerbine	Auf diesen Beitrag antworten »
1. Skalare Gleichungen Gesucht ist die Nullstelle x* der Funktion $\begin{eqnarray} f:~\mathbb R \to \mathbb R,~f(x^)=0 \end{eqnarray}$ Skalar, da hier der Fall $\begin{eqnarray} \mathbb R^n,~n=1 \end{eqnarray*}$ betrachtet wird. Im folgenden sollen einige Lösungsverfahren vorgestellt werden.
16.08.2007, 18:25	tigerbine	Auf diesen Beitrag antworten »
2. Bisektionsverfahren Hierbei soll die Nullstelle von f mit Hilfe des Zwischenwertsatzes bestimmt werden. Somit muss f auf dem zu untersuchenden Intervall [a,b] stetig sein. Finden wir also ein Teilintervall mit [a',b'] mit o.B.d.A f(a') < 0 und f(b') > 0, so hat f auf diesem Intervall eine Nullstelle ungerader Vielfachheit.
16.08.2007, 18:37	tigerbine	Auf diesen Beitrag antworten »
2a. Beschreibung des Verfahren Gilt $\begin{eqnarray} f(a) \cdot f(b) < 0 \end{eqnarray}$ , dann hat f in[a,b] mindestens eine Nullstelle. Um sie zu bestimmen, halbieren wir das Intervall. $\begin{eqnarray} [a,c],~[c,b] \quad \text{ mit } c:\frac{a+b}{2} \end{eqnarray}$ Nun werden die Teilintervalle auf Vorzeichenwechsel untersucht. Und die Prozedur in dem Intervall mit Vorzeichenwechsel fortgesetzt. Bei wikipedia finden wir folgende anschauliche Darstellung: http://upload.wikimedia.org/wikipedia/de/f/f0/Bisektion_Ani.gif
16.08.2007, 18:47	tigerbine	Auf diesen Beitrag antworten »
2b. Bewertung Laufzeit $\begin{eqnarray} \frac{b-a}{2^n} < \varepsilon \Rightarrow \log_2 \frac{b-a}{\varepsilon} < n \end{eqnarray}$ Wir haben somit eine logarithmische Laufzeit in Abhängigkeit vom Verhältnis der Intervalllänge zur gewünschten Genauigkeit. Vor- und Nachteile des Verfahrens: Die Bisektion eignet sich für folgende Fälle: Ein Vorzeichenwechsel liegt im gegebenen Intervall vor und die Funktion ist stetig Die Startwerte der klassischen Verfahren (Newton-Verfahren, Regula Falsi) liegen nicht hinreichend nah genug an der Nullstelle, so dass dort keine lokale Konvergenz eintritt Mehrfache Nullstellen mindern die Konvergenzgeschwindigkeit der klassischen Verfahren Nachteile der Bisektion: Bei einfachen Fällen (streng monotone Funktion) ist sie langsamer als ein quadratisch konvergentes Verfahren Ohne Vorzeichenwechsel im gegebenen Intervall sind Zusatzprüfungen notwendig, um ein lokales Minimum von einer Nullstelle zu unterscheiden
16.08.2007, 19:31	tigerbine	Auf diesen Beitrag antworten »
3. Newton-Verfahren Die Nullstelle wird durch lineare Approximation der Funktion f bestimmt. Dazu wird das Taylorpolynom 1ten Grades um den Punkt $\begin{eqnarray} x_k \end{eqnarray}$ bestimmt (entwickelt). Dessen Nullstelle ist dann eine Approximation von $\begin{eqnarray} x^ \end{eqnarray*}$ . Voraussetzung ist hier natürlich das f stetig differenzierbar auf dem zu untersuchenden Intervall [a,b] ist.
Anzeige

16.08.2007, 19:47	tigerbine	Auf diesen Beitrag antworten »
3a. Beschreibung des Verfahrens Es folgt somit die Rekursionsvorschrift: $\begin{eqnarray} f(x_k) + f'(x_k)(x-x_k) = 0 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},~k=0,1,2,... \end{eqnarray}$ mit geeignetem Startwert $\begin{eqnarray} x_0 \end{eqnarray}$ . Bei wikipedia finden wir die folgende Veranschaulichung: http://upload.wikimedia.org/wikipedia/commons/e/e0/NewtonIteration_Ani.gif
16.08.2007, 21:03	tigerbine	Auf diesen Beitrag antworten »
3b. Bewertung Vorteile i.A. schnelle Konvergenz Nachteile nur lokale Konvergenz (Wahl des richtigen Startwertes) Funktion muss differenzierbar sein Ableitung muss berechnet werden Beispiel: Betrachtet werden soll die Umkehrfunktion des Tangens. $\begin{eqnarray} f(x) = \arctan(x),~W_f=]-\frac{\pi}{2},~\frac{\pi}{2}[ \end{eqnarray}$ $\begin{eqnarray} f'(x) = \frac{1}{1+x^2} \end{eqnarray}$ $\begin{eqnarray} x^ = 0 \end{eqnarray*}$ Wählt man nun der Startwert zu weit von 0 entfernt, wird die Tangente zu flach und man entfernt sich immer weiter von der Nullstelle.
17.08.2007, 02:08	tigerbine	Auf diesen Beitrag antworten »
4. Sekanten Verfahren Anstatt wie beim Newton-Verfahren mit den Ableitungen zu rechnen, kann man als deren Näherungen Sekanten verwenden. http://upload.wikimedia.org/wikipedia/commons/a/ad/Sekantenverfahren_Ani2.gif Es ist nach Definition: $\begin{eqnarray} \frac{df}{dx}(x_k) = f'(x_k) = \lim_{x \to x_k} ~\frac{f(x)-f(x_k)}{x-x_k} = \lim_{h \to 0 }~\frac{f(x_k+h)}{h} \end{eqnarray}$ Wählt man nun $\begin{eqnarray} h_k \end{eqnarray}$ klein genug, so gilt $\begin{eqnarray} f'(x_k) \approx \frac{f(x_k+h_k)-f(x_k)}{h_k} \end{eqnarray}$
17.08.2007, 03:05	tigerbine	Auf diesen Beitrag antworten »
4a. Newton-Verfahren mit finiten Differenzen $\begin{eqnarray} x_{k+1} = x_{k}-\frac{f(x_k)\cdot h_k}{f(x_k+h_k) -f(x_k)} \end{eqnarray}$ $\begin{eqnarray} x_0 \end{eqnarray}$ geeigneter Startwert 2 Auswertungen von f pro Iteration (anstelle der Ableitung) finite Differenzen: endliche Differenz $\begin{eqnarray} h_k \end{eqnarray}$
17.08.2007, 03:09	tigerbine	Auf diesen Beitrag antworten »
4b. Sekantenverfahren (Drei-Term-Rekursion) Mit der Wahl von $\begin{eqnarray} h_k:=x_k-x_{k-1} \end{eqnarray}$ kann man sogar mit einer Funktionsauswertung pro Iteration auskommen. $\begin{eqnarray} x_{k+1}=x_k - \frac{f(x_k)\cdot (x_k-x_{k-1})}{f(x_k)-\underbrace{f(x_{k-1})}_{\text{bekannt}}} \end{eqnarray}$ Die benötigten beiden Startwerte können mit (4a) bestimmt werden.
17.08.2007, 03:11	tigerbine	Auf diesen Beitrag antworten »
4c. Probleme Die numerische Gefahr ist hier offensichtlich. Auslöschung im Nenner. Soll für das Verfahren doch gelten $\begin{eqnarray} (x_k)_k \to x^ \end{eqnarray*}$ So folgt aufgrund der Stetigkeit von f, dass sich auch die Funktionswerte immer weiter annähern. dies führt hier zur Gefahr der Division durch 0.
17.08.2007, 03:37	tigerbine	Auf diesen Beitrag antworten »
5. Regula falsi Sei f eine stetige Funktion. Dann ist die Regula falsi eine Kombination aus dem Bisektion-und dem Sekantenverfahren: Bisektion Bestimme Intervall $\begin{eqnarray} [a_0,b_0] \end{eqnarray}$ mit $\begin{eqnarray} f(a_0)\cdot f(b_0) < 0 \end{eqnarray}$ Neue Intervalle $\begin{eqnarray} [a_0,c_0],[c_0,b_0] \end{eqnarray}$ Prüfe $\begin{eqnarray} f(a_0)\cdot f(c_0) < 0 \end{eqnarray}$ und $\begin{eqnarray} f(c_0)\cdot f(b_0) < 0 \end{eqnarray}$ Sekantenverfahren Bestimmung von $\begin{eqnarray} c_0,~c_k \end{eqnarray}$ als Nullstelle der Sekanten $\begin{eqnarray} f(a_k) + \frac{f(a_k)-f(b_k)}{a_k-b_k}\cdot (c_k-a_k) = 0 \end{eqnarray}$ $\begin{eqnarray} \frac{f(a_k)-f(b_k)}{a_k-b_k}\cdot (c_k-a_k) =-f(a_k) \end{eqnarray}$ $\begin{eqnarray} c_k=a_k-\frac{(a_k-b_k)\cdot f(a_k)}{f(a_k)-f(b_k)} \end{eqnarray}$ http://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Regula_falsi.gif/400px-Regula_falsi.gif
17.08.2007, 03:58	tigerbine	Auf diesen Beitrag antworten »
6. Methode der inversen quadratischen Interpolation Wie man durch 3 Punkte ein quadr.Polynom eindeutig legt, kann man im [WS] Polynominterpolation - Theorie sehen. Hier haben wir eine Funktion f gegeben und suchen x* mit f(x)=0. Dieses x ist der Funktionswert der Umkehrfunktion an der Stelle y=0. Tauscht man also den Datensatz (f(x_1),x_1), (f(x_2),x_2), (f(x_3),x_3) so interpoliert man die Umkehrfunktion und p(0) ist eine Näherung für das gesuchte x*. (Link) Auch diese Idee kann man mit der Bisektion kombinieren. (Link). und sollte es auch tun. Im Gegensatz zum Sekanten-Verfahren kann es durchaus vorkommen, dass p(0) außerhalb von [a,b] liegt. Selbst wenn liegt es innerhalb von [a,b], so sind die Teilintervalle wieder auf Vorzeichenwechsel zu untersuchen. Es empfiehlt sich auch zu vergleichen, ob dann das Bisektionsintervall nicht sogar kleiner ist. Man kann sogar noch mehr Verfahren mit einander Verbinden: Brent-Verfahren
17.08.2007, 16:13	tigerbine	Auf diesen Beitrag antworten »
Ausblick Nach dieser Kurzvorstellung der Verfahren wird sich im nächsten Workshop genauer mit dem Newton-Verfahren auseinandergesetzt. Generell bleibt zu sagen, dass der Preis der gesicherten Konvergenz eines Verfahrens seine Geschwindigkeit ist. Ferner kostet einen die bessere Geschwindigkeit des Newtonverfahrens die Berechnung und Auswertung der Ableitung.

Neue Frage »

Antworten »

[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren

Verwandte Themen