[WS] Eindimensionale Nullstellenprobleme - Beispiele

Neue Frage »

24.08.2007, 12:36

tigerbine

Auf diesen Beitrag antworten »

[WS] Eindimensionale Nullstellenprobleme - Beispiele

Gliederung

Beispiele zum Newton-Verfahren [Workshop - Eindimensionale Nullstellenprobleme 2]

Newton-Verfahren zur Wurzelberechnung (a > 0)
Nur einmal stetig differenzierbare Funktion
Newton-Verfahren bei doppelter Nullstelle (a = 0)
Modifiziertes Newton Verfahren [f(x)=x²]
Newton-Verfahren mit kubischer Konvergenz (1)
Newton-Verfahren mit kubischer Konvergenz (2)

Vergleiche von Verfahren und Sonderfälle

Regula Falsi vs. Bisektion

a. Kandidat 1: Regula Falsi
b. Kandidat 2: Bisektion
c. Zwischenstand nach 3 Schritten
d. Richtige Stellen
Bisektion vs. Sekante vs. Newton

a. Kandidat 1: Bisektion
b. Kandidat 2: Sekanten-Verfahren
c. Kandidat 3: Newton-Verfahren
d. Ergebnis
Bisektion und Singularität (Polstelle)

24.08.2007, 17:38

tigerbine

Auf diesen Beitrag antworten »

1. Newton-Verfahren zur Wurzelberechnung, a > 0
Die n-te Wurzel einer reellen Zahl a > 0 ist eine Nullstelle der Funktion

$\begin{eqnarray*} f(x) = x^n -a,~n \geq 2,~a > 0 \end{eqnarray*}$

Eine kleine Kurvendiskussion, zeigt, dass es für gerades n zwei Lösungen (symmetrisch zu 0) und ungerades n eine Lösungen in den reellen Zahlen gibt. Gesucht ist die nichtnegative Lösung.

Das Newton-Verfahren zur Berechnung von $\begin{eqnarray*} x^*=\sqrt[n]{a} \end{eqnarray*}$ lautet:

$\begin{eqnarray*} x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{(x_k)^n-a}{n \cdot (x_k)^{n-1}} = \frac{1}{n} \cdot \Bigl[ (n-1) \cdot x_k + \frac{a}{(x_k)^{n-1}} \Bigr] \end{eqnarray*}$

Man sieht, dass das Verfahren nicht für $\begin{eqnarray*} x_k=0 \end{eqnarray*}$ definiert ist. Da eine nichtnegative Zahl gesucht ist, wählt man als Startwert ein $\begin{eqnarray*} x_0 >0 \end{eqnarray*}$

Da es sich um eine einfache Nullstelle einer mind. einmal stetig differenzierbaren Funktion handelt, konvergiert das Verfahren, wenn man den Startwert nur nahe genug bei x* wählt. (Beweis)

Hier liegt der Fall sogar noch deutlich besser:

Das Verfahren konvergiert für jeden Startwert $\begin{eqnarray*} x_0 > 0 \end{eqnarray*}$ gegen x*.

Beweis:

$\begin{eqnarray*} x_{k+1} = \frac{1}{n} \ \Bigl((n-1)\cdot x_k + \frac{a}{(x_k)^{n-1}} \Bigr) > 0 \end{eqnarray*}$

Somit sind alle Iterierten größer 0. Weiter ist die Abbildung
Die Funktion

$\begin{eqnarray*} g(x) &&= \frac{1}{n} \ \Bigl((n-1)\cdot x + \frac{a}{x^{n-1}} \Bigr) \\&& = \frac{n-1}{n} \cdot x + \frac{1}{n} \cdot \frac{a}{x^{n-1}} \end{eqnarray*}$

ist strikt konvex (linksgekrümmt), denn für die zweite Ableitung gilt:

$\begin{eqnarray*} g''(x) =(n-1) \cdot \frac{a}{x^{n+1}} >0 \quad \forall x > 0 \end{eqnarray*}$
Es ist desweiteren

$\begin{eqnarray*} \lim_{x \to 0}~g(x) = \lim_{x \to 0}~\frac{1}{n} \ \Bigl((n-1)\cdot x + \frac{a}{x^{n-1}} \Bigr) = + \infty \end{eqnarray*}$

$\begin{eqnarray*} \lim_{x \to \infty}~g(x) = \lim_{x \to \infty}~\frac{1}{n} \ \Bigl((n-1)\cdot x + \frac{a}{x^{n-1}} \Bigr) = + \infty \end{eqnarray*}$
Somit besitzt die Funktion genau ein Minimum (an der Stelle x*), denn

$\begin{eqnarray*} g'(x) = \frac{n-1}{n}\cdot\left(1 - \frac{a}{x^n}\right) \end{eqnarray*}$

$\begin{eqnarray*} g'(x^*) = 0 \end{eqnarray*}$

Auf Grund des Kurvenverlaufs gilt also für k=0,1,..,

$\begin{eqnarray*} x^* \leq g(x_k) \Rightarrow x^* \leq x_{k} \quad \forall~k=1,2,... \end{eqnarray*}$
$\begin{eqnarray*} x_{k+1} = g(x_k) \leq x_k \quad \forall~k=1,2,... \end{eqnarray*}$
$\begin{eqnarray*} \frac{a}{(x_k)^{n-1}} = \underbrace{\frac{(x^*)^{n-1}}{(x_k)^{n-1}}}_{\leq 1} \cdot ~x^* \leq x^* \end{eqnarray*}$

Somit folgt die Abschätzung:

$\begin{eqnarray*} \frac{a}{(x_k)^{n-1}} \leq x^* \leq x_{k+1} \leq x_k \end{eqnarray*}$

Lehrer

Welche man für ein Abbruchkriterium verwenden kann:
$\begin{eqnarray*} 0 \geq e_k := x_k - \frac{a}{(x_k)^{n-1}} \leq \varepsilon \Rightarrow \text{ STOP } \end{eqnarray*}$

Ab wann konvergiert das Verfahren quadratisch?

Da es sich um eine einfache Nullstelle einer C²-Funktion handelt, gibt es sogar eine Umgebung von x* in der das Verfahren quadratisch konvergiert.

Beispiel n=2

$\begin{eqnarray*} x_{k+1} = x_k - \frac{x_k^2-a}{2x_k},~k \geq 1 \end{eqnarray*}$

$\begin{eqnarray*} x_{k+1} - x^* &&= \frac{1}{2} \cdot\left[x_k + \frac{a}{x_k}\right] - x^* =\frac{1}{2} \cdot\left[x_k -2x^*+ \frac{a}{x_k}\right] \\&& = \frac{1}{2x_k} \cdot\left[x_k^2 - 2x_kx^*+a\right] \\&&= \frac{1}{2x_k}\cdot\left(x_t-x^*\right)^2 \end{eqnarray*}$

Wegen $\begin{eqnarray*} x_k \geq x^* \end{eqnarray*}$ folgt dann

$\begin{eqnarray*} |x_{k+1}-x^* |\leq \frac{1}{2x^*} \cdot |x_k-x^*|^2 \end{eqnarray*}$

Mit den Ausführungen zur Konvergenz folgt die Bedingung:

$\begin{eqnarray*} \frac{1}{2x^*} \cdot |x_0 - x^*| < 1 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow x_0 \in\left[0,~3x^*\right] \end{eqnarray*}$

Das nütz natürlich nicht viel, wenn man keine Ahnung über die Lage von x* hat. Dennoch wollen wir, mit der Kenntnis, einmal den Einzugsbereich explizit für ein paar a bestimmen.

$\begin{eqnarray*} a=1:~~x_0 \in[0,3],~x^*=1 \end{eqnarray*}$
$\begin{eqnarray*} a=2:~~x_0 \in[0,4.24],~x^* \approx 1.41 \end{eqnarray*}$
$\begin{eqnarray*} a=3:~~x_0 \in[0,5.20],~x^* \approx 1.73 \end{eqnarray*}$
$\begin{eqnarray*} a=5:~~x_0 \in[0,6.71],~x^* \approx 2.24 \end{eqnarray*}$
$\begin{eqnarray*} a=10:~x_0 \in[0,9.49],~x^* \approx 3.16 \end{eqnarray*}$

24.08.2007, 19:12

tigerbine

Auf diesen Beitrag antworten »

2. Nur einmal stetig diffbare Funktion
Nun betrachten wir eine einmal stetig differenzierbare Funktion mit einer einfachen Nullstelle.

Nullstellenfunktion f

$\begin{eqnarray*} f(x) = \begin{cases} \frac{-x^2+x}{2} & x< 0\\\frac{x^2+x}{2} & x\geq0\end{cases} \end{eqnarray*}$

$\begin{eqnarray*} f(0)=0,~\Rightarrow x^*:=0 \end{eqnarray*}$
$\begin{eqnarray*} f'(x) = \begin{cases} -x+0.5 & x< 0\\ +x + 0.5 & x\geq0\end{cases} \end{eqnarray*}$

$\begin{eqnarray*} f'(0) = 0.5 \end{eqnarray*}$
$\begin{eqnarray*} \lim_{h\to 0}~\frac{f'(0+h)-f'(0)}{h}= \begin{cases} -1 & h< 0\\ +1 & h\geq0\end{cases} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \text{f' nicht differenzierbar in } x^*=0 \end{eqnarray*}$

Newton- Iteration

$\begin{eqnarray*} x_{k+1} = x - \frac{f(x)}{f'(x)} \end{eqnarray*}$

Die zur Newton-Iteration gehörige Fixpunktfunktion g lautet:

$\begin{eqnarray*} g(x) =x - \frac{f(x)}{f'(x)} = \begin{cases}x- \frac{\frac{-x^2+x}{2}}{-x+0.5 } = \frac{-0.5\cdot x^2}{-x+0.5} = 0.5x+0.25-\frac{0.125}{x+0.5} & x< 0\\\\x- \frac{\frac{x^2+x}{2}}{+x+0.5 } = \frac{0.5 \cdot x^2}{+x+0.5} =0.5x-0.25+\frac{0.125}{x+0.5}& x\geq0\end{cases} \end{eqnarray*}$

$\begin{eqnarray*} g(0)=0,~\Rightarrow x^*:=0 \end{eqnarray*}$

Wie konvergiert die Iteration nun?

$\begin{eqnarray*} |x_{k+1}-x^*| \leq q \cdot |x_k-x^*| \end{eqnarray*}$

$\begin{eqnarray*} |1-\frac{f'(\zeta)}{f'(x_k)}| \leq q < 1 \end{eqnarray*}$

Dabei liegt $\begin{eqnarray*} \zeta \end{eqnarray*}$ zwischen x* und $\begin{eqnarray*} x_k \end{eqnarray*}$ . Aufgrund der Gestalt der Funktion f' folgt hier:

$\begin{eqnarray*} 0 < \frac{f'(\zeta)}{f'(x_k)} < 1 \end{eqnarray*}$
$\begin{eqnarray*} |1-\frac{f'(\zeta)}{f'(x_k)}|< 1 \quad \forall k = 0,1, \end{eqnarray*}$

Somit konvergiert die Newton-Iteration für alle Startwerte. Nun muss noch ein q bestimmt werden.

$\begin{eqnarray*} |1-\frac{f'(\zeta)}{f'(x_k)}| \leq |1-\frac{0.5}{f'(x_k)}| \leq |1-\frac{0.5}{f'(x_0)}| = q \end{eqnarray*}$

Dass die Iteration nicht nur linear, sondern superlinear konvergiert wurde ja bereits allgemein im Theorie-Teil gezeigt. Die nächste Frage muss also lauten:

Ist die Funktion f Lipschitzstetig?

Betrachten wir die Funktion auf dem Intervall [0,5]. Sie ist dort strikt konvex.

26.08.2007, 12:51

tigerbine

Auf diesen Beitrag antworten »

3. Newton-Verfahren bei doppelter Nullstelle
Die Funktion $\begin{eqnarray*} f(x) = x^2 \end{eqnarray*}$ hat eine doppelte Nullstelle bei $\begin{eqnarray*} x^*=0 \end{eqnarray*}$ . Es gilt:

$\begin{eqnarray*} f(0) = 0^2 = 0 \end{eqnarray*}$
$\begin{eqnarray*} f'(0) = 2\cdot 0 =0 \end{eqnarray*}$
$\begin{eqnarray*} f''(0) = 2 \end{eqnarray*}$

Nun stellt man die Iterationsvorschrift des Newton Verfahrens auf:

$\begin{eqnarray*} x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^2}{2x_k} \end{eqnarray*}$

Es liegt also für x*=0 eine hebbare Definitionslücke vor. Die Rekursion verläuft also für $\begin{eqnarray*} x^* \neq 0 \end{eqnarray*}$ unproblematisch und man kann zur Untersuchung schreiben:

$\begin{eqnarray*} x_{k+1} = \frac{1}{2} \cdot x_k \end{eqnarray*}$

Das liefert die folgende Konvergenzuntersuchung. Dabei benutzt man x*=0

$\begin{eqnarray*} |x_{k+1}-x^*| = |\frac{1}{2} x_k - x^*| = |\frac{1}{2}\cdot x_k| = \frac{1}{2} \cdot |x_k - x^*| \end{eqnarray*}$

Daher weiß man nun, dass das Verfahren mind. linear konvergiert. Dass die Konvergenz aus der Abschätzung folgt, wurde hier gezeigt.

Lineare Konvergenzrate und Superlineare Konvergenz

$\begin{eqnarray*} \lim_{x \to \infty}~\frac{|x_{x+1}-x^*|}{|x_k-x^*|} = \lim_{x \to \infty} \frac{\frac{1}{2}|x_k-x^*|}{|x_k-x^*|} = \frac{1}{2} \end{eqnarray*}$

Somit liegt keine superlineare und damit auch keine höhere Konvergenordnung (z.B. quadratisch) vor.

Es zeigt sich aber die für C²-getroffene Aussage, dass die lineare Konvergenzrate den Wert $\begin{eqnarray*} \frac{2-1}{2} \end{eqnarray*}$ hat.

Zugehörige Fixpunktiteration

$\begin{eqnarray*} g(x):= x - \frac{f(x)}{f'(x)} = x - \frac{x^2}{2x},~\text{stetig auf } \mathbb R \setminus \{0\},~\text{ differenzierbar auf } \mathbb R \setminus \{0\} \end{eqnarray*}$

$\begin{eqnarray*} g'(x):= 1 - \frac{2x\cdot 2x - x^2 \cdot 2}{[2x]^2} = 1 - \frac{4x^2-2x^2}{4x^2} =1- \frac{x^2}{2x^2} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow\lim_ {x \to 0} ~g'(x) = \lim_ {x \to 0} ~ 1- \frac{x^2}{2x^2} = \lim_ {x \to 0} ~ 1- \frac{1}{2} = \frac{1}{2} \end{eqnarray*}$

Für die stetige Fortsetzung gilt:

$\begin{eqnarray*} \hat g(x) = x - \frac{1}{2}x = \frac{1}{2} x,~\text{stetig auf } \mathbb R,~\text{ differenzierbar auf } \mathbb R \end{eqnarray*}$

$\begin{eqnarray*} \hat g'(x) = \frac{1}{2} \end{eqnarray*}$

So dass, da die Folge ja konvergiert, wir auch die hier gemachte Aussage verifizieren können.

26.08.2007, 15:02

tigerbine

Auf diesen Beitrag antworten »

4. Modifiziertes Newton Verfahren
Vergleiche [Workshop - Eindimensionale Nullstellenprobleme 2]

Nun wollen wir uns noch einmal an der Funktion f(x) = x² versuchen. Diese besitzt bei x*= 0 eine doppelte (p=2) Nullstelle. Es gilt f'(x) = 2x, f''(x) = 2, f'''(x)=0.

Rekursionsvorschrift:

$\begin{eqnarray*} x_{k+1} = x_k - \alpha \cdot \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

$\begin{eqnarray*} x_{k+1} = x_k - 2 \cdot \frac{(x_k)^2}{2x_k} \end{eqnarray*}$

Und es gilt die Abschätzung

$\begin{eqnarray*} |x_{k+1} - x^* | \leq C \cdot |x_k - x^*|^2,~C:=\frac{M}{p\cdot m} \end{eqnarray*}$

$\begin{eqnarray*} p=2 \end{eqnarray*}$

$\begin{eqnarray*} m:=\min_{x\in K_r(x^*)}~|f^{(2)}(x)| = 2 \end{eqnarray*}$

$\begin{eqnarray*} M:=\max_{x\in K_r(x^*)}~|f^{(3)}(x)| = 0 \end{eqnarray*}$

$\begin{eqnarray*} |x_{k+1} - 0 | \leq \frac{0}{2\cdot 2} \cdot |x_k - 0|^2 \end{eqnarray*}$

Somit ist es nicht verwunderlich, dass dieses Verfahren bereits im ersten Iterationsschritt (für jeden Startwert ungleich x*) konvergiert.

$\begin{eqnarray*} x_1 = x_0 - 2\cdot \frac{(x_0)^2}{2\cdot x_0} =x_0-x_0 =0 = x^* \end{eqnarray*}$

03.09.2007, 12:30

tigerbine

Auf diesen Beitrag antworten »

5. Newton-Verfahren mit kubischer Konvergenz
Nach folgendem Satz gilt (siehe [Workshop - Eindimensionale Nullstellenprobleme 2]):

Zitat:

Sei g in einer Umgebung eines Fixpunktes x* p-mal stetig differenzierbar mit p > 1. Dann gilt:

$\begin{eqnarray*} g'(x^*) = ... = q^{(p-1)}(x*)= 0,~g^{(p)}(x^*) \neq 0~ \Leftrightarrow \text{ Fixpunktiteration } x_{k+1} = g(x_k) \text{ hat die Ordnung p} \end{eqnarray*}$

Bislang haben wir als Bestwert nur "lokale quadratische Konvergenz" erhalten. Geht auch noch mehr?

Versuchen wir ein Beispiel:

$\begin{eqnarray*} f(x):= \frac{1}{3} \cdot x^3 - x \Rightarrow f(0)=0 \end{eqnarray*}$

$\begin{eqnarray*} f'(x) = x^2-1\Rightarrow f'(0)=-1 \end{eqnarray*}$

$\begin{eqnarray*} f''(x) = 2x\Rightarrow f''(0)=0 \end{eqnarray*}$

$\begin{eqnarray*} f'''(x) = 2\Rightarrow f'''(0)=2 \end{eqnarray*}$

$\begin{eqnarray*} g(x):=x-\frac{f(x)}{f'(x)} = x - \frac{ \frac{1}{3} \cdot x^3 - x}{x^2-1} \Rightarrow g(0)=0 \end{eqnarray*}$

$\begin{eqnarray*} g'(x)&&=1-\frac{[f'(x)]^2 - f(x)f''(x)}{[f'(x)]^2} = \\&&= \frac{f(x)f''(x)}{[f'(x)]^2} \\\\&&= \frac{\frac{2}{3}x^4 - 2x^2}{[x^2-1]^2} \Rightarrow g'(0) =0 \end{eqnarray*}$

$\begin{eqnarray*} g''(x) && = \frac{\left(\frac{8}{3}x^3-4x\right)\left(x^2-1\right)^4 - 4\left(\frac{2}{3}x^4 - 2x^2\right)\left(x^2-1\right)^3\cdot 2x}{\left[x^2-1\right]^4}\\&&\Rightarrow g''(0)=0 \end{eqnarray*}$

Nun wird es unschön. Daher ein paar Platzhalter.

$\begin{eqnarray*} g'''(x) && = \frac{[]'\cdot [x^2-1]^4-[]\cdot 4 \cdot [x^2-1]^3 \cdot 2x}{[x^2-1]^8} \end{eqnarray*}$

$\begin{eqnarray*} [] = -\frac{8}{3}x^{11}+\frac{32}{3}x^9-32x^7+\frac{56}{3} x^5+\frac{8}{3}x^3-4x \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow [0] = 0,~[0]'\neq0 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow g'''(0) \neq 0 \end{eqnarray*}$

somit konvergiert das Verfahren mit der Konvergenzordnung 3.

03.09.2007, 19:24

tigerbine

Auf diesen Beitrag antworten »

1. Regula-Falsi vs. Bisektion
Nach den Kommentaren im [Workshop - Eindimensionale Nullstellenprobleme 3] sollen hier anhand zweier Beispiele das Konvergenzverhalten von Regula falsi und Bisektion verglichen werden.

Das erste Beispiel

$\begin{eqnarray*} f(x) = \frac{1}{10^5} \cdot e^x-5 \end{eqnarray*}$

Die Nullstelle liegt formal bei

$\begin{eqnarray*} x^* = 5\cdot \ln(10) + \ln(5) \approx 13.12~23~63~38 \end{eqnarray*}$

Als erste grobe Abschätzung kann man treffen, dass sich die Nullstelle im Intervall [0, 15] befindet. Es ist dann:

$\begin{eqnarray*} f(0) = - 5 < 0,~f(15) \approx 27.690173 > 0 \end{eqnarray*}$

$\begin{eqnarray*} a_0=0,~b_0 = 15 \end{eqnarray*}$

$\begin{eqnarray*} I_0=[0,15] \end{eqnarray*}$

http://www.smileygarden.de/smilie/Sport/12.gif Let's get ready to rumble

03.09.2007, 20:08

tigerbine

Auf diesen Beitrag antworten »

a. Kandidat 1: Regula Falsi
$\begin{eqnarray*} I_0=[0,15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Sekantenschritt Nr.1:

$\begin{eqnarray*} c_1 &&= a_0 - \frac{b_0-a_0}{f(b_0)-f(a_0)} \cdot f(a_0) = 0 - \frac{15-0}{27.690173+5}\cdot (-5)\\&&= 2.294267 \end{eqnarray*}$
Es folgt der Bisektionsschritt 1:

$\begin{eqnarray*} f(c_1) = -4.999901 < 0 \end{eqnarray*}$

$\begin{eqnarray*} I_1=[2.294267,~15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Sekantenschritt Nr.2:

$\begin{eqnarray*} c_2 &&= a_1 - \frac{b_1-a_1}{f(b_1)-f(a_1)} \cdot f(a_1) \\&&= 2.294267 - \frac{15-2.294267}{27.690173+4.999901}\cdot (-4.999901) \\&&= 4.237591 \end{eqnarray*}$
Es folgt der Bisektionsschritt 2:

$\begin{eqnarray*} f(c_2) = -4.999306< 0 \end{eqnarray*}$

$\begin{eqnarray*} I_2=[4.237591,~15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Sekantenschritt Nr.3:

$\begin{eqnarray*} c_3 &&= a_2 - \frac{b_2-a_2}{f(b_2)-f(a_2)} \cdot f(a_2) \\&&= 4.237591 - \frac{15-4.237591}{27.690173+4.999306}\cdot (-4.999306) \\&&= 5.883520 \end{eqnarray*}$
Es folgt der Bisektionsschritt 3:

$\begin{eqnarray*} f(c_3) = -4.996409< 0 \end{eqnarray*}$

$\begin{eqnarray*} I_3=[5.883520,~15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Das bisherige einmal im Bild:

03.09.2007, 21:29

tigerbine

Auf diesen Beitrag antworten »

b. Kandidat 2: Bisektion
$\begin{eqnarray*} I_0=[0,15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Mittelwertschritt Nr.1:

$\begin{eqnarray*} c_1 = \frac{a_0+b_0}{2}= \frac{0 + 15}{2} = 7.500000 \end{eqnarray*}$
Es folgt der Bisektionsschritt 1:

$\begin{eqnarray*} f(c_1) = -4.981920 < 0 \end{eqnarray*}$

$\begin{eqnarray*} I_1=[7.500000,~15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Mittelwertschritt Nr.2:

$\begin{eqnarray*} c_2 = \frac{a_1+b_1}{2}= \frac{7.500000 + 15}{2} = 11.25000 \end{eqnarray*}$
Es folgt der Bisektionsschritt 2:

$\begin{eqnarray*} f(c_2) = -4.231201 < 0 \end{eqnarray*}$

$\begin{eqnarray*} I_2=[11.25000,~15] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

Es folgt dann der Mittelwertschritt Nr.3:

$\begin{eqnarray*} c_3 = \frac{a_2+b_2}{2}= \frac{11.25000 + 15}{2} = 13.12500 \end{eqnarray*}$
Es folgt der Bisektionsschritt 3:

$\begin{eqnarray*} f(c_3) = 0.013201 > 0 \end{eqnarray*}$

$\begin{eqnarray*} I_3=[11.25000,~13.12500] \end{eqnarray*}$

--------------------------------------------------------------------------------------------------------------------------

03.09.2007, 21:39

tigerbine

Auf diesen Beitrag antworten »

c. Zwischenstand nach 3 Schritten
Wer liegt nun nach 3 Runden vorne?

Bei der Bisektion bleibt als mittel der Genauigkeitsbestimmung nur die Länge des Intervalls.

Bei der Regula falsi bekommt man mit $\begin{eqnarray*} c_k \end{eqnarray*}$ noch einen Näherungswert zur Lösung x*. Da man aber nur den Funktionswert $\begin{eqnarray*} f(x^*)=0 \end{eqnarray*}$ kennt, muss zur Genauigkeitsbestimmung $\begin{eqnarray*} |f(c_k)| \end{eqnarray*}$ herangezogen werden.

Regula Falsi

$\begin{eqnarray*} I_3=[5.8835200000,~15.000000000] \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow L_3 = 9.1164800000 \end{eqnarray*}$

$\begin{eqnarray*} |f(c_3)| = 4.996409 \end{eqnarray*}$

Bisektion

$\begin{eqnarray*} I_3=[11.2500000000,~13.1250000000] \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow L_3 = 1.8750000000 \end{eqnarray*}$

Somit liegt nach 3 Runden die Bisektion vorne. Nun wissen wir, dass sich beim Bisektionsverfahren die Intervallänge immer halbiert. Kann die Regula falsi noch aufholen?

03.09.2007, 23:52

tigerbine

Auf diesen Beitrag antworten »

d. Richtige Stellen
Nach wie vielen Iterationen erreichen die beiden Verfahren 1,2,...,10 richtige Stellen?

$\begin{eqnarray*} x^*\approx 13.122363377 \end{eqnarray*}$

Regula Falsi

$\begin{eqnarray*} I_{~0}=[00.000000000,~15.000000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{16}=[12.94016838551067,~15.00000000000000],~|f(c_{16})|=\underline{0}.83280594620845 \end{eqnarray*}$

$\begin{eqnarray*} I_{22}=[13.10659678232195,~15.00000000000000],~|f(c_{22})|=\underline{0.0}7821476489994 \end{eqnarray*}$

$\begin{eqnarray*} I_{27}=[13.12036839004407,~15.00000000000000],~|f(c_{27})|=\underline{0.00}996499347825 \end{eqnarray*}$

$\begin{eqnarray*} I_{32}=[13.12211162542613,~15.00000000000000],~|f(c_{32})|=\underline{0.00}125860145662 \end{eqnarray*}$

...

$\begin{eqnarray*} I_{66}=[13.12236337721075,~15.00000000000000],~|f(c_{66})|=\underline{0.000000000}96791 \end{eqnarray*}$

Bisektion

$\begin{eqnarray*} I_{~0}=[00.000000000,~15.000000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{~2}=[\underline{1}1.250000000,~\underline{1}5.000000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{~7}=[\underline{13}.007812500,~\underline{13}.125000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{10}=[\underline{13.1}10351563,~\underline{13.1}25000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{12}=[\underline{13.12}1337891,~\underline{13.12}5000000] \end{eqnarray*}$

$\begin{eqnarray*} I_{15}=[\underline{13.122}253418,~\underline{13.122}711182] \end{eqnarray*}$

$\begin{eqnarray*} I_{18}=[\underline{13.1223}10638,~\underline{13.1223}67859] \end{eqnarray*}$

$\begin{eqnarray*} I_{21}=[\underline{13.12236}0706,~\underline{13.12236}7859] \end{eqnarray*}$

$\begin{eqnarray*} I_{26}=[\underline{13,122363}165,~\underline{13.122363}389 \end{eqnarray*}$

$\begin{eqnarray*} I_{28}=[\underline{13.1223633}33,~\underline{13.1223633}89] \end{eqnarray*}$

$\begin{eqnarray*} I_{32}=[\underline{13.12236337}5,~\underline{13.12236337}8] \end{eqnarray*}$

Somit führt auch noch bei einer Berechnung bis auch 10 Ziffern Genauigkeit die Bisektion. Damit soll der Wettkampf beendet werdet.

Dieses Mal hat also die Bisektion "gewonnen"

http://www.smileygarden.de/smilie/Sport/1er.gif

05.09.2007, 00:56

tigerbine

Auf diesen Beitrag antworten »

2. Bisektion vs. Sekante vs. Newton
Kaum den Titel gewonnen, haben wir 2 neue Herausforderer für das Bisektionsverfahren. Wer hat bei folgender Funktion die Nase vorne:

$\begin{eqnarray*} f(x)=e^x\cdot \ln(x)-x^2 \end{eqnarray*}$

$\begin{eqnarray*} f(x)=e^x\cdot \ln(x) + e^x \cdot \frac{1}{x}-2x \end{eqnarray*}$

Diese Funktion hat eine einfache Nullstelle im Intervall [1,2]

Sieger soll dasjenige Verfahren sein, dass nach 20-Runden die meisten richtigen Ziffern ermittelt hat.

05.09.2007, 02:33

tigerbine

Auf diesen Beitrag antworten »

a. Kandidat 1: Bisektion

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:

   Runde              a                  b
   ======================================================
   1.00000000000000   1.50000000000000   2.00000000000000

   2.00000000000000   1.50000000000000   1.75000000000000

   3.00000000000000   1.62500000000000   1.75000000000000

   4.00000000000000   1.68750000000000   1.75000000000000

   5.00000000000000   1.68750000000000   1.71875000000000

   6.00000000000000   1.68750000000000   1.70312500000000

   7.00000000000000   1.68750000000000   1.69531250000000

   8.00000000000000   1.69140625000000   1.69531250000000

   9.00000000000000   1.69335937500000   1.69531250000000

  10.00000000000000   1.69433593750000   1.69531250000000

  11.00000000000000   1.69433593750000   1.69482421875000

  12.00000000000000   1.69458007812500   1.69482421875000

  13.00000000000000   1.69458007812500   1.69470214843750

  14.00000000000000   1.69458007812500   1.69464111328125

  15.00000000000000   1.69458007812500   1.69461059570313

  16.00000000000000   1.69459533691406   1.69461059570313

  17.00000000000000   1.69459533691406   1.69460296630859

  18.00000000000000   1.69459915161133   1.69460296630859

  19.00000000000000   1.69459915161133   1.69460105895996

  20.00000000000000   1.69460010528564   1.69460105895996

$\begin{eqnarray*} I_{20} = [\underline{1.69460}010528564,~\underline{1.69460}105895996] \end{eqnarray*}$

Macht also über'm Strich 6 Ziffern

05.09.2007, 04:20

tigerbine

Auf diesen Beitrag antworten »

b. Kandidat 2: Sekanten - Verfahren

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

   Runde              Näherung für x*   zug. Funktionswert
  ==========================================================
   1.00000000000000   1.47131941206771  -0.48306468159224

   2.00000000000000   1.63046198381311  -0.16215576999798

   3.00000000000000   1.71087697176913   0.04459090813901

   4.00000000000000   1.69353315094812  -0.00287488751534

   5.00000000000000   1.69458362388888  -0.00004661884760

   6.00000000000000   1.69460093901827   0.00000004990282

   7.00000000000000   1.69460092050323  -0.00000000000087

   8.00000000000000   1.69460092050355                  0

   9.00000000000000   1.69460092050355                  0

Warning: Divide by zero.
> In C:\matlabR12\work\sek.m at line 10
    10   NaN   NaN

Somit nach 8 Schritten 13 übereinstimmende Ziffern.

Somit sehen wie hier nach 9 Schritten das Problem des Verfahrens. Die "Näherung" ist bereits soweit Fortgeschritten, dass es im Nenner zur Auslöschung kommt.

05.09.2007, 14:24

tigerbine

Auf diesen Beitrag antworten »

c. Kandidat 3: Newton - Verfahren

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

   Runde              Näherung für x*   zug. Funktionswert
   ========================================================

   1.00000000000000   2.39221119117733   3.81734431721932

   2.00000000000000   1.98296694460196   1.04091475589428

   3.00000000000000   1.76009539827046   0.18854386808167

   4.00000000000000   1.69865936882817   0.01098334132527

   5.00000000000000   1.69461736534069   0.00004432458551

   6.00000000000000   1.69460092077453   0.00000000073035

   7.00000000000000   1.69460092050355                  0

   8.00000000000000   1.69460092050355                  0

Somit nach 7 Schritten 13 übereinstimmende Ziffern. Das Verfahren ist stabil in der Nähe der gesuchten Lösung x*.

05.09.2007, 14:32

tigerbine

Auf diesen Beitrag antworten »

d. Ergebnis
Somit kommen wir bei dieser Funktion zu folgendem Ranking:

http://www.smileygarden.de/smilie/Sport/1er.gif Newton-Verfahren

http://www.smileygarden.de/smilie/Sport/2eme.gif Sekanten-Verfahren

http://www.smileygarden.de/smilie/Sport/3eme.gif Bisektion

05.09.2007, 15:07

tigerbine

Auf diesen Beitrag antworten »

3. Bisektion und Singularität (Polstelle)
Es wurde im [Workshop - Eindimensionale Nullstellenprobleme 1] erwähnt, dass die Bisektion auf einem Intvall [a,b] mit f(a)f(b) < 0 für stetiges f aufgrund des Zwischenwertsatzes stetiger Funktion konvergieren muss.

Was passiert nun im Falle einer unstetigen Funktion?

Neue Frage »

Antworten »

[WS] Eindimensionale Nullstellenprobleme - Beispiele

Verwandte Themen