Why is Horner's method for evaluating polynomials not suitable for root finding?

Question

$$ p = \sum_{k = 0}^n a_k x^k $$

Horner's method for evaluating a polynomial:

$$ \begin{align} p_H &= a_0 + x \left( a_1 + x \left( a_2 + x \left( a_3 + .... + x \left( a_{n -1} + x a_n \right) \right) \right) \right) \\ &... \\ & = a_0 + x \left( a_1 + x b_2 \right) \\ & = a_0 + x b_1 \\ & = b_0 \end{align}$$

So, if $y = (x - 2)^9$ evaluated with $\Delta x = 10^{-4}$, I get this:

My questions are:

1. Why is less precise than directly computing the value of the polynomial?
2. Why does the error oscillate like that?

I've tried finding the error in each case:

$$ \Delta p = \Delta x \sum_{k = 1}^n k |a_k| |x^{k - 1}| $$

$$ \begin{align} \Delta p_H &= \Delta x |b_1| + |x| \Delta b_1 \\ &= \Delta x |b_1| + \Delta x |b_2| + |x| \Delta b_2 \\ &... \\ &= \Delta x(|b_1| + |b_2| + ... + |b_n|) + |a_n| |x| \Delta x \\ &= \Delta x \left( \sum_{k = 1}^n |b_n| + |a_n| |x| \right) \end{align}$$

So it seems that

$$ \sum_{k = 1}^n |b_n| + |a_n| |x| > \sum_{k = 1}^n k |a_k| |x^{k - 1}| $$

but by how much? What is the intuition behind this?

Answer 1

Without knowing exactly how you plotted the two functions, it is not possible to know for sure. However, the Horner's method is subject to loss of significance due to many floating point additions but the $y=(x−2)^9$ method only does one subtraction. I was able to duplicate essentially the plot you got using Mathematica two ways. For those interested, here is my code:

ClearAll[x, y, z, horner]; y = (x - 2)^9; z = y // Expand;
horner[p_, w_, x0_] := With[{a = Reverse@CoefficientList[p, w]}, 
  Fold[x0*#1 + #2 &, Prepend[a, 0]]];
DiscretePlot[{1*^10*horner[z, x, t], 1*^10*y/.x->t}, {t,1.92,2.08,.001}, 
  PlotRange -> {-1.5, 1.5}, AspectRatio -> 1, Filling -> False, 
  PlotLegends -> Placed[{"Horner's", "(x-2)^9"}, Above]]
Plot[{1*^10*horner[z, x, t], 1*^10*(y/.x->t)}, {t, 1.92, 2.08}, 
  PlotRange -> {-1.5, 1.5}, AspectRatio -> 1, PlotPoints -> 3, 
  PlotLegends -> Placed[{"Horner's", "(x-2)^9"}, Above]]