Rundungsfehleranalyse < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zur Auswertung eines Polynoms der Ordnung k mit
$f(x) = [mm] \sum_{i=0}^{k}a_{i}*x^{i}$
[/mm]
wird gewöhnlich das Horner-Schema verwendet. Hierbei berechnet man im Schritt n:
[mm] $z_{n} [/mm] = [mm] x*z_{n-1} [/mm] + [mm] a_{k-n}$,
[/mm]
wobei [mm] $z_{0} [/mm] := [mm] a_{k}$. [/mm] Dann gilt [mm] $z_{k} [/mm] = f(x)$. Zeigen Sie, dass dieser Algorithmus numerisch stabiler ist als das einzelne Auswerten der Summanden von f(x), indem sie eine Rundungsfehleranalyse beider Verfahren durchführen. |
Hallo!
Bei der obigen Aufgabe stecke ich fest.
Bei der Rundungsfehleranalyse einer Funktion F berechne ich ja den relativen Fehler: [mm] $\frac{F-rd(F)}{F}$, [/mm] wobei $rd(F)$ das F ist, bei welchem während der Rechnungen immer gerundet wurde.
Ich habe nun mit der Analyse des Horner-Schemas begonnen:
[mm] $rd(z_{n}) [/mm] = [mm] \Big(x*rd(z_{n-1})*(1+\epsilon_{1})+a_{k-n}\Big)*(1+\epsilon_{2}) \overset{1.Naeherung}{=} \Big(x*rd(z_{n-1}) [/mm] + [mm] a_{k-n}\Big) [/mm] + [mm] (\epsilon_{1} [/mm] + [mm] \epsilon_{2})*x*rd(z_{n-1}) [/mm] + [mm] \epsilon_{2}*a_{k-n}$
[/mm]
Außerdem ist im n-ten Schritt die exakte Rechnung an der Stelle:
[mm] $z_{n} [/mm] = [mm] x*rd(z_{n-1}) [/mm] + [mm] a_{n-k}$,
[/mm]
So... Nun kann ich den absoluten Fehler berechnen:
[mm] $\Delta z_{n} [/mm] = [mm] z_{n} [/mm] - [mm] rd(z_{n}) [/mm] = [mm] \Big(x*rd(z_{n-1}) [/mm] + [mm] a_{n-k}\Big) [/mm] - [mm] \Bigg(\Big(x*rd(z_{n-1}) [/mm] + [mm] a_{k-n}\Big) [/mm] + [mm] (\epsilon_{1} [/mm] + [mm] \epsilon_{2})*x*rd(z_{n-1}) [/mm] + [mm] \epsilon_{2}*a_{k-n}\Bigg)$
[/mm]
$= [mm] -(\epsilon_{1} [/mm] + [mm] \epsilon_{2})*x*rd(z_{n-1}) [/mm] - [mm] \epsilon_{2}*a_{k-n}$
[/mm]
>>> Das ist jetzt praktisch der absolute Fehler, der während der Rechnung im n-ten Schritt entsteht, oder?
>>> Aber kann ich den absoluten Fehler auch ohne Rekursion darstellen?
Danke für Eure Hilfe,
Stefan
|
|
| |
|
> Zur Auswertung eines Polynoms der Ordnung k mit
>
> [mm]f(x) = \sum_{i=0}^{k}a_{i}*x^{i}[/mm]
>
> wird gewöhnlich das Horner-Schema verwendet. Hierbei
> berechnet man im Schritt n:
>
> [mm]z_{n} = x*z_{n-1} + a_{k-n}[/mm]
>
> wobei [mm]z_{0} := a_{k}[/mm]. Dann gilt [mm]z_{k} = f(x)[/mm]. Zeigen Sie,
> dass dieser Algorithmus numerisch stabiler ist als das
> einzelne Auswerten der Summanden von f(x), indem sie eine
> Rundungsfehleranalyse beider Verfahren durchführen.
Hallo Stefan,
bei der Art von Analyse, wie du sie da durchführst, kenne
ich mich nicht wirklich aus. Aber ich hätte eine kleine
Frage:
Was genau ist denn die alternative Berechnungsweise mit
der "einzelnen Auswertung der Summanden" ? Ich nehme
einmal an, dass dann der i-te Summand [mm] s_i [/mm] so berechnet wird:
$\ [mm] s_i\ [/mm] =\ [mm] a_i*\underbrace{x*x*.....*x}_{i\ Faktoren}$ [/mm]
Damit kommt man natürlich auf viel mehr Multiplikationen,
was die Güte der Rechnung bestimmt beeinträchtigen wird.
Bei einer Multiplikation addieren sich die relativen Fehler,
so dass also bei der Berechnung des Summanden [mm] s_i [/mm] ein
relativer Fehler
[mm] \delta(s_i)=\delta(a_i)+i*\delta(x)
[/mm]
herauskommt.
LG Al
|
|
|
|
