Rekursion

23.02.2010, 22:11

D@Npower

Auf diesen Beitrag antworten »

Rekursion

Guten Abend allerseits!

Ich hätte eine Frage, was den Beweis einer Rekursion angeht, welche zu folgendem Integral gehört:

$\begin{eqnarray*} I_n = \int_0^1 \! \frac{t^n}{t + 5} \, dt \end{eqnarray*}$

Die dazugehörige Rekursion wäre:
$\begin{eqnarray*} I_k = -5I_{k-1} + \frac{1}{k} \end{eqnarray*}$ , wobei k = 1, ..., n

Wie aber zeige ich, dass dem wirklich so ist?
Per Induktion?
..dann wäre für n=0 zum Beispiel das Integral ln(6/5) - wie würde ich dann aber die Rekursion richtig berechnen?
..dazu müsste ich doch $\begin{eqnarray*} I_0 = 0 \end{eqnarray*}$ annehmen, oder wie würdet ihr hier vorgehen?

Besten Dank im Voraus!

23.02.2010, 22:23

Kühlkiste

Auf diesen Beitrag antworten »

RE: Rekursion
Zu einer Rekursionsformel gehört natürlich immer auch ein Startwert.
Den hast Du ja schon richtig berechnet und kannst somit den Induktionsanfang für n=1 durchführen.

Im Induktionsschritt solltest Du dann mit partieller Integration zu Werke gehen.

23.02.2010, 23:36

D@Npower

Auf diesen Beitrag antworten »

RE: Rekursion
Berechnet ist übertrieben..wie käme man "von Hand" für n=0 auf ln(6/5) ?

Okey, ja..wenn ich das noch wüsste, dann kann ich das vollständig zeigen. smile

smile

23.02.2010, 23:40

AD

Auf diesen Beitrag antworten »

Zitat:

Original von D@Npower
Berechnet ist übertrieben..wie käme man "von Hand" für n=0 auf ln(6/5) ?

Na schlicht durch Ausrechnen von

$\begin{eqnarray*} I_0 = \int_0^1 \frac{1}{t+5} ~ \dd t = \left[ \ln(t+5) \right]_{t=0}^1 \end{eqnarray*}$ ,

wie denn sonst?

Zitat:

Original von Kühlkiste
Im Induktionsschritt solltest Du dann mit partieller Integration zu Werke gehen.

Würde ich hier nicht empfehlen. Eher einen Divisionsschritt im Integranden

$\begin{eqnarray*} \frac{t^n}{t+5} = \frac{(t^n+5t^{n-1})-5t^{n-1}}{t+5} = t^{n-1} - 5\cdot \frac{t^{n-1}}{t+5} \end{eqnarray*}$ .

23.02.2010, 23:59

D@Npower

Auf diesen Beitrag antworten »

Okey - das gilt natürlich nach Definition - ich dachte mehr an ableiten etc. (bin aber nicht mehr ganz sicher, ob man das "braucht", um das Integral zu berechnen)

Zum Induktionsschritt..ich habe den ein wenig anders gemacht: In der Induktionsvoraussetzung habe ich angenommen, dass das Integral = Rekursion (für n) gilt, und habe dann n-->n+1 gezeigt.

Ist diese Vorgehensweise falsch, oder deine einfach besser? smile

smile

24.02.2010, 00:05

AD

Auf diesen Beitrag antworten »

Zitat:

Original von D@Npower
Zum Induktionsschritt..ich habe den ein wenig anders gemacht:

Was ist daran "anders"? Was du da nennst, ist ja wohl die pure Selbstverständlichkeit bei einem Induktionsbeweis und nennt noch keinerlei Details, wie du den Induktionsschritt dann wirklich bewältigen kannst. Und genau zu letzterem habe ich mich geäußert.

Anzeige

24.02.2010, 00:13

Kühlkiste

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von Kühlkiste
Im Induktionsschritt solltest Du dann mit partieller Integration zu Werke gehen.

Würde ich hier nicht empfehlen. Eher einen Divisionsschritt im Integranden

$\begin{eqnarray*} \frac{t^n}{t+5} = \frac{(t^n+5t^{n-1})-5t^{n-1}}{t+5} = t^{n-1} - 5\cdot \frac{t^{n-1}}{t+5} \end{eqnarray*}$ .

Partielle Integration war tatsächlich keine gute Idee.

Alternativ geht's übrigens auch per Substitution (z=t+5):

$\begin{eqnarray*} I_{n+1}=\int_5^6\frac{(z-5)^{n+1}}z~\dd z=\int_5^6(z-5)^n~\dd z-5\int_5^6\frac{(z-5)^n}z~\dd z=\frac 1{n+1}-5I_n \end{eqnarray*}$

24.02.2010, 00:31

D@Npower

Auf diesen Beitrag antworten »

Hehe..das hab ich vorhin auch gleich probiert, und dasselbe herausbekommen smile

smile

super!
..nochmals zur Rekursion - gäbe es hierzu nicht eine andere, gutartige, "äquivalente" Rekursion?

24.02.2010, 00:42

AD

Auf diesen Beitrag antworten »

Wenn du von "gutartig" sprichst, dann meinst du das unter numerischen Aspekten? Dann sag es deutlich, ansonsten ist diese deine Anmerkung nämlich nicht zu verstehen. unglücklich

unglücklich

24.02.2010, 00:59

D@Npower

Auf diesen Beitrag antworten »

Ja, das meine ich unter numerischen Aspekten - es gilt also:
$\begin{eqnarray*} | \epsilon_{x \cdot y} | \leq | C_1 \epsilon_{x} + C_2 \epsilon_{y} | \end{eqnarray*}$ wobei C_1 und C_2 eine (beliebige) Konstante grösser 0 ist.

24.02.2010, 01:04

AD

Auf diesen Beitrag antworten »

Manchmal hilft es, die Sache aus der entgegengesetzten Perspektive zu betrachten - konkret hier:

$\begin{eqnarray*} I_{k-1} = \frac{1}{5k} - \frac{I_k}{5} \end{eqnarray*}$ für $\begin{eqnarray*} k=n_0,n_0-1,\ldots,n+2,n+1 \end{eqnarray*}$

mit einem "geeignet groß" gewähltem $\begin{eqnarray*} n_0 \end{eqnarray*}$ . Überleg dir mal, warum das günstig ist, und das trotz der Tatsache, dass man den Startwert $\begin{eqnarray*} I_{n_0} \end{eqnarray*}$ bei dieser Vorgehensweise nur sehr grob kennt. Augenzwinkern

Augenzwinkern

24.02.2010, 14:40

D@Npower

Auf diesen Beitrag antworten »

Wie meinst du "geeignet gross"?
Falls n_0 eine natürliche Zahl darstellen soll, so wäre die kleinst mögliche Zahl 1, ansonsten kann man sie nicht konkret nennen. (ausser als Beispiel)

Günstig ist das natürlich, dass der Nenner immer durch 5 teilbar ist - was beim Berechnen sehr entgegenkommend ist (sein kann).

24.02.2010, 14:45

D@Npower

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Überleg dir mal, warum das günstig ist (...)

Ich hätte noch eine generelle Frage, zu dieser, aber auch zur Anfangs-Rekursion: Angenommen, man will die Resultate für n von 1 bis 100 angeben, und vielleicht ab n=10 in 10-er Schritten fortfahren, so ist dies gar nicht möglich, denn um bspw. n=50 zu berechnen, ist entweder n=49 oder n=51 nötig..ist das genau der "Witz" an Rekursion? smile

smile

24.02.2010, 20:00

AD

Auf diesen Beitrag antworten »

Durch die Abschätzung $\begin{eqnarray*} \frac{t^n}{6} \leq \frac{t^n}{t+5} \leq \frac{t^n}{5} \end{eqnarray*}$ im betrachteten Integrationsintervall kommt man leicht auf

$\begin{eqnarray*} \frac{1}{6(n_0+1)} \leq I_{n_0} \leq \frac{1}{5(n_0+1)} \qquad (*) \end{eqnarray*}$ .

Sei also $\begin{eqnarray*} \Delta I_{n_0} = \frac{1}{5(n_0+1)}-\frac{1}{6(n_0+1)} = \frac{1}{30(n_0+1)} =: g(n_0) \end{eqnarray*}$ der hier auftretende maximale "Fehler", wenn man den Startwert irgendwo in diesem Intervall (*) festlegt.

Durch die Rekursion

$\begin{eqnarray*} I_{k-1} = \frac{1}{5k} - \frac{I_k}{5} \end{eqnarray*}$

verringert sich nun aber der absolute Fehler in jedem Rekursionsschritt auf ein Fünftel, also $\begin{eqnarray*} \Delta I_{k-1} = \frac{1}{5}\Delta I_k \end{eqnarray*}$ . Ok, dabei habe ich zunächst mal den numerischen Fehler des Summanden $\begin{eqnarray*} \frac{1}{5k} \end{eqnarray*}$ sowie den der Differenzbildung außen vor gelassen, die spielen bei den ersten Schritten ja auch keine Rolle.

Beispiel: Du willst $\begin{eqnarray*} I_{100} \end{eqnarray*}$ auf 8 Nachkommastellen genau berechnen, welches $\begin{eqnarray*} n_0 \end{eqnarray*}$ wäre dann passend? Nun, es ist auf jeden Fall $\begin{eqnarray*} n_0\geq 100 \end{eqnarray*}$ und somit $\begin{eqnarray*} g(n_0) \leq g(100) = \frac{1}{3030} \end{eqnarray*}$ . Um zu $\begin{eqnarray*} \Delta I_{100} < 10^{-8} \end{eqnarray*}$ zu kommen, reichen daher

$\begin{eqnarray*} \left\lceil \log_5\left( \frac{\frac{1}{3030}}{10^{-8}} \right) \right\rceil = 7 \end{eqnarray*}$

Iterationsstufen, also beginnend mit $\begin{eqnarray*} n_0=107 \end{eqnarray*}$ und einem beliebigen (!) Startwert $\begin{eqnarray*} I_{107} \in \left[ \frac{1}{642}, \frac{1}{535} \right] \end{eqnarray*}$ . Wenn das mal nicht robust ist... Augenzwinkern

Augenzwinkern

24.02.2010, 21:20

D@Npower

Auf diesen Beitrag antworten »

Na wem sagst du das! smile

smile

..du hast mich voll und ganz überzeugt!
Evtl. melde ich mich bezüglich dieses Problems noch einmal..ich muss erst alle Schritte noch einmal durchgehen, um sicher zu gehen, dass ich es auch wirklich verstanden habe =)

24.02.2010, 23:58

D@Npower

Auf diesen Beitrag antworten »

Eine Frage hätte ich noch: Wann nennt man eine Rekursion "stabil"?
(im numerischen Sinne)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »