Fehleranalyse: Wie wirken sich die Rundungsfehler in xk-2 und xk-1 auf xk aus?

Question

Aufgabe:

Betrachte die folgende Rekursionsformel
$x_{k}=\frac{16}{3} x_{k-1}-\frac{5}{3} x_{k-2}, \quad k \geq 2$
mit $x_{0}=1$ und $x_{1}=1 / 3$.
a) Zeigen Sie mittels Induktion, dass die Rekursion die Folge $x_{k}=\left(\frac{1}{3}\right)^{k}$ erzeugt.
b) Führen Sie eine Fehleranalyse durch. Zeigen Sie, wie sich Rundungsfehler in $x_{k-2}$ und $x_{k-1}$ auf $x_{k}$ auswirken.

Hinweis: Sei $\epsilon_{k-1}$ der relative Fehler von $x_{k-1}$ also $\tilde{x}_{k-1}:=f l\left(x_{k-1}\right)=x_{k-1}\left(1+\epsilon_{k-1}\right) .$ Wie hängt dann $\epsilon_{k}$ von $\epsilon_{k-2}$ und $\epsilon_{k-1}$ ab?

Problem/Ansatz:

Die vollständige Induktion habe ich noch hinbekommen. Aber was ist mit b.) gemeint?

Comments

Hat Keiner eine Idee? Weil das Einzige was mir noch einfällt ist einfach die Formel des relativen Fehlers zu verwenden und x_n+1 jw. mit x_n und x_n-1 zu vergleichen in der Formel. Wäre das was?

Answer 1

Wenn die Folgenglieder den absoluten Fehler $\Delta_k$ besitzten folgt

$$\frac{16}{3} \left( x_{k-1} + \Delta_{k-1} \right) - \frac{5}{3} \left( x_{k-2} + \Delta_{k-2} \right) = x_k + \frac{16}{3} \Delta_{k-1} - \frac{5}{3} \Delta_{k-2}$$ also

$$\Delta_k = \frac{16}{3} \Delta_{k-1} - \frac{5}{3} \Delta_{k-2}$$

D.h. der absolute Fehler erfüllt die gleiche Rekursionsgleichung wie die Größe $x_k$

Die allg. Lösung obiger Differenzengleichung ist $$\Delta_k = 5^k a_1 +\left( \frac{1}{3} \right)^k a_2$$

wobei sich die Zahlen $a_1$ und $a_2$ aus den Anfangsbedingungen bestimmen.

D.h. $$\begin{pmatrix} a_1 \\ a_2 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 5 & \frac{1}{3} \end{pmatrix}^{-1} \begin{pmatrix} \Delta_0 \\ \Delta_1 \end{pmatrix}$$

Nimmt man z.B. für die Anfangsfehler $\Delta_0 = \varepsilon$ und $\Delta_1 = \varepsilon$ folgt

$$\Delta_k = \frac{1}{7} 5^k \varepsilon + \frac{6}{7} \left( \frac{1}{3} \right)^k \varepsilon$$

Für $k \to \infty$ folgt dann, $$\Delta_k \to \frac{1}{7} 5^k \varepsilon$$ Der Fehler wird in diesem Fall also unendlich groß.