Abbruchkriterium bei Rekursion

03.09.2005, 15:43

poiz

Abbruchkriterium bei Rekursion

Folgende Aufgabe bereitet mir Schwierigkeiten:

Berechnen Sie mit einem geeigneten numerischen Rechnungsverfahren:
$\begin{eqnarray*} f(x) = cos(x) = x = g(x) \end{eqnarray*}$

Wie viele Rechenschritte sind notwendig, damit der Approximationsfehler $\begin{eqnarray*} E < 10^{-3} \end{eqnarray*}$ ist?

Durch einsetzen von $\begin{eqnarray*} x = 0 \end{eqnarray*}$ in $\begin{eqnarray*} g(x) \end{eqnarray*}$ bzw. $\begin{eqnarray*} f(x) \end{eqnarray*}$ sehe ich, dass die Lösung im Intervall $\begin{eqnarray*} [0,\frac{\pi }{2}] \end{eqnarray*}$ liegen muss.

Dann nehem ich einfach die Mitte, also $\begin{eqnarray*} x = \frac{\pi }{4} \end{eqnarray*}$ und vergleiche nochmals. Weil $\begin{eqnarray*} f(x) < g(x) \end{eqnarray*}$ ist, verschiebe ich jeweils die rechte Grenze zur Mitte des Intervalls. Somit erhalte ich für das nächste Intervall $\begin{eqnarray*} [\frac{\pi }{4}, \frac{3\pi}{8}] \end{eqnarray*}$ und vergleiche erneut. Dies gibt eine "Art" Rekursion, die ich solange ausführen muss, bis ich die gewünschte Genauigkeit erreicht habe. Doch wie kann ich bestimmen, wie viele Schritte das sind, ohne die Rekursion x mal im TR auszuführen...?

Danke

03.09.2005, 16:37

JochenX

Auf diesen Beitrag antworten »

da du die rekursion eh ausführen musst um deine näherung bestimmen zu können, würde ich mal fragen: wozu willst du denn die anzahl der schritte ohne die schritte selbst auszuführen?

03.09.2005, 16:58

poiz

Auf diesen Beitrag antworten »

Ja, das ist schon richtig...

Aber angenommen, eine "frühere" Näherung hätte bereits gereicht....und ich müsste zusätzlich die Anzahl Schritte für $\begin{eqnarray*} x = 0.739 \end{eqnarray*}$ (die erforderliche Genauigkeit) angeben.

Es muss doch ein "rechnerisches" Verfahren geben, um nur die Anzahl Schritte zu bestimmen (ohne diese auszuführen). Oder sehe ich das falsch?

Bei einer geometrischen Reihe wärs ja einfach(er)...

03.09.2005, 17:59

Mathespezialschüler

Auf diesen Beitrag antworten »

Worum geht es denn überhaupt?? Um die Berechnung von $\begin{eqnarray*} x \end{eqnarray*}$ in der Gleichung

$\begin{eqnarray*} \cos x-x=0 \end{eqnarray*}$ ?

Ich nehme das jetzt mal an. Was du machst, ist eine Intervallschachtelung nach dem Intervallhalbierungsverfahren. Die Funktion $\begin{eqnarray*} h(x)=\cos x-x \end{eqnarray*}$ ist auf ganz $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ streng monoton fallend. Wenn du jetzt irgendwann bei einem Intervall $\begin{eqnarray*} [a,b] \end{eqnarray*}$ angelangt bist, für das gilt, dass

$\begin{eqnarray*} |h(a)-h(b)|<10^{-3} \end{eqnarray*}$ ,

dann bist du fertig. Du weißt auf jeden Fall schonmal $\begin{eqnarray*} 0<a<b<\frac{\pi}{2} \end{eqnarray*}$ , was dir im Folgenden helfen könnte. Du musst nämlich jetzt nur noch

$\begin{eqnarray*} |\cos a-a-\cos b+b|<10^{-3} \end{eqnarray*}$

bekommen. Das musst du jetzt geeignet umformen, um daraus dann eine Bedingung für die Intervalllänge zu bekommen. Damit kannst du dann sofort berechnen, wie viele Schritte du brauchst.

Gruß MSS

03.09.2005, 18:33

Trazom

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
da du die rekursion eh ausführen musst um deine näherung bestimmen zu können, würde ich mal fragen: wozu willst du denn die anzahl der schritte ohne die schritte selbst auszuführen?

Aus der A-Priori-Abschätzung des Banach-Fixpunkt-Satzes. Man muss es nich ausführen, um abzuschätzen, wieviele Schritte man mindestens braucht. Mit der A-posteriori-Abschätzung kann man dann hinterher ausrechnen, wieviele Schritte man wirklich gebraucht hat.

http://de.wikipedia.org/wiki/Fixpunktsatz_von_Banach

04.09.2005, 11:23

poiz

Auf diesen Beitrag antworten »

Hallo MSS!

Zitat:

Original von Mathespezialschüler
Worum geht es denn überhaupt?? Um die Berechnung von $\begin{eqnarray*} x \end{eqnarray*}$ in der Gleichung

$\begin{eqnarray*} \cos x-x=0 \end{eqnarray*}$ ?

Genau!

Zitat:

$\begin{eqnarray*} |\cos a-a-\cos b+b|<10^{-3} \end{eqnarray*}$

Mir fehlt leider die Idee, wie ich die Intervalllänge in dieser Gleichung miteinbeziehen kann. Hab's mir wirklich überlegt, komm aber nicht drauf verwirrt

04.09.2005, 11:26

Mathespezialschüler

Auf diesen Beitrag antworten »

Zuerst mal kannst du die Betragsstriche weglassen (Warum?). Dann gibt es da eine schöne Formel, nämlich:

$\begin{eqnarray*} \cos a-\cos b=2\sin\frac{a+b}{2}\sin\frac{b-a}{2} \end{eqnarray*}$ .

Damit solltest du mal was versuchen! Augenzwinkern

Gruß MSS

04.09.2005, 11:50

poiz

Auf diesen Beitrag antworten »

Ich versteh einfach nicht, wie ich mit der Gleichung auf ein Intervall schliessen soll. Denn für $\begin{eqnarray*} a \end{eqnarray*}$ bzw. $\begin{eqnarray*} b \end{eqnarray*}$ setze ich ja Werte zwischen $\begin{eqnarray*} 0 \end{eqnarray*}$ und $\begin{eqnarray*} \frac{\pi}{2} \end{eqnarray*}$ ein.

Die Gleichung sagt doch einfach aus, dass (mittels Halbierungsverfahren) die beiden Intervalle $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ so nahe beim gesuchten Wert liegen, dass sich die Differenz davon erst an der 3. Stelle unterscheidet.

Ich weiss nicht, was ich mit dieser Gleichung machen soll, um auf das Intervall zu schliessen....

04.09.2005, 12:05

Mathespezialschüler

Auf diesen Beitrag antworten »

Also, du willst

$\begin{eqnarray*} \cos a-a-\cos b+b=\cos a-\cos b+b-a=2\sin\frac{a+b}{2}\sin\frac{b-a}{2}+b-a<10^{-3} \end{eqnarray*}$

bekommen. Es gilt doch, dass $\begin{eqnarray*} b-a>0 \end{eqnarray*}$ ist. Für $\begin{eqnarray*} x>0 \end{eqnarray*}$ gilt aber $\begin{eqnarray*} \sin x<x \end{eqnarray*}$ . Außerdem ist natürlich $\begin{eqnarray*} \sin x\leq 1 \end{eqnarray*}$ für alle reellen $\begin{eqnarray*} x \end{eqnarray*}$ . Schaffst du es damit,

$\begin{eqnarray*} 2\sin\frac{a+b}{2}\sin\frac{b-a}{2} \end{eqnarray*}$

geeignet nach oben abzuschätzen? Augenzwinkern

Gruß MSS

04.09.2005, 12:38

poiz

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} \cos a-a-\cos b+b=\cos a-\cos b+b-a=2\sin\frac{a+b}{2}\sin\frac{b-a}{2}+b-a<10^{-3} \end{eqnarray*}$

So weit kann ich folgen...

Zitat:

$\begin{eqnarray*} b-a>0 \end{eqnarray*}$

Ok, deshalb hast du ja auch die Betragsstriche "weggelassen"

Zitat:

Für $\begin{eqnarray*} x>0 \end{eqnarray*}$ gilt aber $\begin{eqnarray*} \sin x<x \end{eqnarray*}$

Ok...

Zitat:

Außerdem ist natürlich $\begin{eqnarray*} \sin x\leq 1 \end{eqnarray*}$ für alle reellen $\begin{eqnarray*} x \end{eqnarray*}$ .

Auch klar!

So langsam wirds mir peinlich... Ich soll also
$\begin{eqnarray*} 2\sin\frac{a+b}{2}\sin\frac{b-a}{2} \end{eqnarray*}$
abschätzen bzw. $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ bestimmen, um Näherungsweise auf $\begin{eqnarray*} 1 * 10^{-3} \end{eqnarray*}$ zu kommen? Ich versteh noch immer nicht, was dies mit der Intervalllänge zu tun haben soll!? Eigentlich verseht ich überhaupt nicht, in welche Richtung das gehen soll... unglücklich

04.09.2005, 12:46

Mathespezialschüler

Auf diesen Beitrag antworten »

Mein Ziel ist es, $\begin{eqnarray*} b-a \end{eqnarray*}$ abzuschätzen, denn das ist die Intervalllänge und das geht so:

$\begin{eqnarray*} \sin\frac{a+b}{2}\leq 1 \end{eqnarray*}$

$\begin{eqnarray*} \sin\frac{b-a}{2}<\frac{b-a}{2} \end{eqnarray*}$ .

Also gilt:

$\begin{eqnarray*} 2\sin\frac{a+b}{2}\sin\frac{b-a}{2}<2\cdot 1\cdot \frac{b-a}{2}=b-a \end{eqnarray*}$ .

Daraus folgt:

$\begin{eqnarray*} \cos a-a-\cos b+b=\cos a-\cos b+b-a \end{eqnarray*}$

$\begin{eqnarray*} =2\sin\frac{a+b}{2}\sin\frac{b-a}{2}+b-a<b-a+b-a=2(b-a) \end{eqnarray*}$ .

Kannst du damit jetzt weiterarbeiten?

Gruß MSS

04.09.2005, 13:09

poiz

Auf diesen Beitrag antworten »

Mein ursprüngliches Ziel war ja die Anzahl notwendiger Schritte im "Intervallhalbierungsverfahren" zu finden, bis die gewünschte Genauigkeit erreicht ist.

Aber ich hab den Durchblick total verloren...und kann dir nicht folgen. Vielleicht sollte ich den Thread später nochmals in Ruhe durchdenken und es jetzt erst mal sein lassen....

Vielen Dank aber für deine Geduld und Hilfe!

(Bin ja gespannt, wie ich morgen an der Vordiplom Prüfung in Mathe abschneiden werde...)

04.09.2005, 13:52

Mathespezialschüler

Auf diesen Beitrag antworten »

Du hast doch jetzt eine Bedingung für die Intervalllänge des Intervalls, was du erreichen willst. Jetzt guckst du, wie viele Schritte du brauchst, um auf diese Intervalllänge zu kommen. Dein Anfangsintervall hatte eine Länge von $\begin{eqnarray*} \frac{\pi}{2} \end{eqnarray*}$ . Nach einem Schritt war die Länge $\begin{eqnarray*} \frac{1}{2}\cdot \frac{\pi}{2} \end{eqnarray*}$ , wie lang ist das Intervall nach $\begin{eqnarray*} n \end{eqnarray*}$ Schritten? Sei $\begin{eqnarray*} l_n \end{eqnarray*}$ die Länge nach dem $\begin{eqnarray*} n \end{eqnarray*}$ -ten Schritt. Wenn für die Länge die Ungleichung

$\begin{eqnarray*} l_n\leq \frac{10^{-3}}{2} \end{eqnarray*}$ ,

gilt, dann folgt, wenn $\begin{eqnarray*} [a,b] \end{eqnarray*}$ das zu $\begin{eqnarray*} l_n \end{eqnarray*}$ zugehörige Intervall nach dem $\begin{eqnarray*} n \end{eqnarray*}$ -ten Schritt ist:

$\begin{eqnarray*} b-a\leq \frac{10^{-3}}{2} \end{eqnarray*}$

oder also

$\begin{eqnarray*} 2(b-a)\leq 10^{-3} \end{eqnarray*}$ .

Da $\begin{eqnarray*} |h(b)-h(a)|<2(b-a) \end{eqnarray*}$ war, folgt auch

$\begin{eqnarray*} |h(b)-h(a)|<10^{-3} \end{eqnarray*}$

und dann ist man fertig. Du musst also nur die Ungleichung

$\begin{eqnarray*} l_n<\frac{10^{-3}}{2} \end{eqnarray*}$

nach $\begin{eqnarray*} n \end{eqnarray*}$ auflösen.

Gruß MSS

Neue Frage »

Antworten »

Abbruchkriterium bei Rekursion

Verwandte Themen