02.2 – Iterative Berechnung von Integralen

 

Zu berechnen sind die Integrale

{I_n} = \frac{1}{e}\int_0^1 {{x^n}{e^x}dx} ,\quad n \geq 0

a) Zeigen Sie die Abschätzung 0 \leq {I_n} \leq \frac{1}{{n+1}}\quad \forall n \geq 0

b) Zeigen Sie, dass die Integrale {I_n} der linearen Rekursion {I_n} = 1-n{I_{n-1}} genügen

c) Wir gehen im Folgenden von exakter Gleitpunktarithmetik aus. Der Startwert {I_0} = \frac{{e-1}}{e} lässt sich im Rechner nicht exakt darstellen. Stattdessen wird ein gerundeter Wert {\tilde I_0} = {I_0}+\Delta {I_0} verwendet. Wie pflanzt sich der Fehler \Delta {I_0} fort?

d) Zu berechnen sei nun {I_0}. Wäre {I_k} für ein gewisses k > 1 bekannt, könnte man die Rückwärtsrekursion {I_{k-1}} = \frac{1}{k}\left( {1-{I_k}} \right) verwenden. Wie pflanzt sich der Startfehler \Delta {I_k} fort? Wie groß muss k sein, um das Integral {I_0} in Matlab mit voller Genauigkeit zu berechnen, wenn man als Startwert {\hat I_k} = \frac{1}{2} \cdot  \frac{1}{{k+1}} wählt?

Lösung

a )

Da {x^n}{e^x} \geq 0\quad \forall x \in \left[ {0,1} \right], folgt sofort {I_n} \geq 0

{I_n} = \frac{1}{e}\int_0^1 {{x^n}{e^x}dx}  \leq \frac{e}{e}\int_0^1 {{x^n}dx}  = \left[ {\frac{1}{{n+1}}{x^{n+1}}} \right]_0^1 = \frac{1}{{n+1}}

b )

Zeigen: {I_n} = 1-n{I_{n-1}}

Dies erhält man am einfachsten durch partielle Integration:

{I_n} = \frac{1}{e}\int_0^1 {\underbrace {{x^n}}_f\underbrace {{e^x}}_{{g^\prime }}dx}  = \frac{1}{e}\left( {\left[ {\underbrace {{x^n}}_f\underbrace {{e^x}}_g} \right]_0^1-\int_0^1 {\underbrace {n{x^{n-1}}}_{{f^\prime }}\underbrace {{e^x}}_gdx} } \right) = \frac{1}{e}\left( {e-n\int_0^1 {{x^{n-1}}{e^x}dx} } \right) = 1-n{I_{n-1}}

c )

exakter Startwert: {I_0} = \frac{{e-1}}{e}

angenäherter Wert: {\tilde I_0} = {I_0}+\Delta {I_0}

Wir treffen die folgende Vereinfachung: Die Rekursion läuft mit exakter Arithmetik ab, also ohne weitere Rundungsfehler.

Wir betrachten den ersten durch die Rekursion berechneten Wert:

{{\tilde I}_1} = 1-1 \cdot  {{\tilde I}_0} = 1-\left( {{I_0}+\Delta {I_0}} \right) = \underbrace {1-{I_0}}_{ = {I_1}}-\Delta {I_0} = {I_1}-\Delta {I_0}

\quad  \Rightarrow \quad \Delta {I_1} = \left( {-1} \right)\Delta {I_0}

Für den nächsten Rekursionsschritt gilt:

\Delta {I_2} = {{\tilde I}_2}-{I_2} = 1-2{{\tilde I}_1}-{I_2} = 1-2\left( {{I_1}+\Delta {I_1}} \right)-{I_2} = 1-2{I_1}-2\Delta {I_1}-{I_2}

\Delta {I_2} = \left( {-2} \right)\Delta {I_1} = \left( {-2} \right)\left( {-1} \right)\Delta {I_0} = 2\Delta {I_0}

Analog gilt für den dritten Schritt:

\Delta {I_3} = \left( {-3} \right)\left( {-2} \right)\left( {-1} \right)\Delta {I_0}

und so weiter. Wir stellen damit die allgemeine Formel auf und beweisen diese mit Hilfe der vollständigen Induktion:

Induktionsannahme: \Delta {I_n} = {\left( {-1} \right)^n}n!\Delta {I_0}

Induktionsanfang: bereits oben gezeigt

Induktionsschritt: n \to n+1

\Delta {I_{n+1}} = {\tilde I_{n+1}}-{I_{n+1}} = 1-\left( {n+1} \right){\tilde I_n}-{I_{n+1}} = 1-\left( {n+1} \right)\left( {{I_n}+\Delta {I_n}} \right)-{I_{n+1}}

= -\left( {n+1} \right)\Delta {I_n}

Einsetzen der Induktionsannahme:

-\left( {n+1} \right)\Delta {I_n} = -\left( {n+1} \right){\left( {-1} \right)^n}n!\Delta {I_0} = {\left( {-1} \right)^{n+1}}\left( {n+1} \right)!\Delta {I_0}

\quad  \Rightarrow \quad \Delta {I_{n+1}} = {\left( {-1} \right)^{n+1}}\left( {n+1} \right)!\Delta {I_0}

d )

Aus Teilaufgabe b übernehmen wir: {I_{n-1}} = \frac{1}{n}\left( {1-{I_n}} \right)

Es gilt:

\Delta {I_{n-1}} = {\tilde I_{n-1}}-{I_{n-1}} = \frac{1}{n}\left( {1-{{\tilde I}_n}} \right)-{I_{n-1}} = \frac{1}{n}\left( {1-{I_n}-\Delta {I_n}} \right)-{I_{n-1}}

=-\frac{1}{n}\Delta {I_n}

Mit Induktion folgt dann:

\Delta {I_0} = {\left( {-1} \right)^n}\frac{1}{{n!}}\Delta {I_n}

Es gibt also eine starke Dämpfung von n!, wodurch auch ein beliebig schlechter Startwert zum richtigen Ergebnis führt.

Für den Startwert {\tilde I_k} = \frac{1}{2} \cdot  \frac{1}{{k+1}} gilt nach Teilaufgabe a: \Delta {I_k} = \frac{1}{2} \cdot  \frac{1}{{k+1}}, da der Fehler höchstens die Hälfte der Intervalllänge sein kann. Es folgt:

\left| {\Delta {I_0}} \right| \leq \frac{1}{{k!}}\Delta {I_k} = \frac{1}{2} \cdot  \frac{1}{{\left( {k+1} \right)!}}

Damit die Maschinengenauigkeit ausgeschöpft wird, gilt:

\left| {\Delta {I_0}} \right| < {10^{-16}} für \frac{1}{2} \cdot  \frac{1}{{\left( {k+1} \right)!}} < {10^{-16}}\quad  \Rightarrow \quad k = 17