02.3 – Fehler bei Auswertung eines Polynoms

 

Auszuwerten ist das Polynom

p\left( x \right) = {a_0}+{a_1}x+{a_2}{x^2}+ \ldots +{a_{n-1}}{x^{n-1}}+{a_n}{x^n}

an der Stelle {x_0} mit gegebenen Koeffizienten {a_0}, \ldots ,{a_n}. Eine äquivalente Schreibweise ist

p\left( x \right) = \left( { \ldots \left( {\left( {{a_n}x+{a_{n-1}}} \right)x+{a_{n-2}}} \right)x+ \ldots +{a_1}} \right)x+{a_0}

Die Auswertung des Polynoms an der Stelle {x_0} gemäß der zweiten Darstellung entspricht dem Hornerschema. Bestimmen Sie ein Polynom \tilde p = {\tilde a_0}+{\tilde a_1}x+ \ldots +{\tilde a_n}{x^n}, so dass der mit dem Hornerschema berechnete Wert als exakter Wert für die Auswertung von \tilde p an der Stelle {x_0} interpretiert werden kann. Schätzen Sie den relativen Fehler im Koeffizienten {\tilde a_n} ab.

Lösung

p\left( x \right) = {a_0}+{a_1}x+{a_2}{x^2}+ \ldots +{a_{n-1}}{x^{n-1}}+{a_n}{x^n}

y = p\left( {{x_0}} \right)

Hornerschema:

y = a(n);
for k = n – 1 : -1 : 0
   y = y * x0+a(k)
end

Annahme: {x_0} und {a_k}\quad \left( {k = 0, \ldots ,n} \right) sind exakt.

Dann gilt:

yt = a(n);
for k = n – 1 : -1 : 0
   yt = (yt * x0 * (1+m(k))+a(k)) * (1+e(k))
end

Es ist

\tilde y = \tilde p\left( {{x_0}} \right) = {{\tilde a}_0}+{{\tilde a}_1}{x_0}+ \ldots +{{\tilde a}_n}x_0^n

{{\tilde a}_n} = {a_n}\left( {1+{\mu _{n-1}}} \right)\left( {1+{\varepsilon _n}} \right)\left( {1+{\mu _{n-2}}} \right)\left( {1+{\varepsilon _{n-2}}} \right) \ldots \left( {1+{\mu _0}} \right)\left( {1+{\varepsilon _0}} \right)

{{\tilde a}_k} = {a_k}\left( {1+{\varepsilon _k}} \right)\left( {1+{\mu _{k-1}}} \right)\left( {1+{\varepsilon _{k-1}}} \right) \ldots \left( {1+{\varepsilon _0}} \right)

Abschätzung des relativen Fehlers \left| {\frac{{{{\tilde a}_n}-{a_n}}}{{{a_n}}}} \right|:

Es gilt

\left| {{\mu _k}} \right| \leq \varepsilon ,\quad \left| {{\varepsilon _k}} \right| \leq \varepsilon

{{\tilde a}_n} \leq {a_n}{\left( {1+\varepsilon } \right)^{2n}}

Mit der binomischen Formel \left( {1+\varepsilon } \right)\left( {1-\varepsilon } \right) = 1-{\varepsilon ^2} < 1 folgt 1+\varepsilon < \frac{1}{{1-\varepsilon }}.

Insgesamt ist dann

{\tilde a_n} \leq {a_n}\frac{1}{{{{\left( {1-\varepsilon } \right)}^{2n}}}}

Bernoullische Ungleichung:

{\left( {1-\varepsilon } \right)^n} \geq 1-n\varepsilon \quad \forall 0 < \varepsilon < 1

Einsetzen:

{\tilde a_n} \leq {a_n}\frac{1}{{1-2n\varepsilon }} = {a_n}\frac{{1-2n\varepsilon +2n\varepsilon }}{{1-2n\varepsilon }} = {a_n}\left( {1+\frac{{2n\varepsilon }}{{1-2n\varepsilon }}} \right)

Damit können wir nun den relativen Fehler berechnen:

\left| {\frac{{{{\tilde a}_n}-{a_n}}}{{{a_n}}}} \right| \leq \frac{{{a_n}\left( {1+\frac{{2n\varepsilon }}{{1-2n\varepsilon }}} \right)-{a_n}}}{{{a_n}}} = \frac{{{a_n}\frac{{2n\varepsilon }}{{1-2n\varepsilon }}}}{{{a_n}}} = \frac{{2n\varepsilon }}{{1-2n\varepsilon }}