Editing Horner's method (section)

== Divided difference of a polynomial ==

Horner's method can be modified to compute the divided difference <math>(p(y) - p(x))/(y - x).</math> Given the polynomial (as before)
<math display="block">p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,</math>
proceed as follows<ref name="Fateman & Kahan">{{harvnb|Fateman|Kahan|2000}}</ref>
<math display="block">\begin{align}
b_n & = a_n,                 &\quad d_n &= b_n, \\
b_{n-1} & = a_{n-1} + b_n x, &\quad d_{n-1} &= b_{n-1} + d_n y, \\
& {}\  \  \vdots             &\quad &  {}\ \ \vdots\\
b_1 & = a_1 + b_2 x,         &\quad d_1 &= b_1 + d_2 y,\\
b_0 & = a_0 + b_1 x.
\end{align}</math>

At completion, we have
<math display="block">\begin{align}
p(x) &= b_0, \\
\frac{p(y) - p(x)}{y - x} &= d_1, \\
p(y) &= b_0 + (y - x) d_1.
\end{align}</math>
This computation of the divided difference is subject to less [[round-off error]] than evaluating <math>p(x)</math> and <math>p(y)</math> separately, particularly when <math> x \approx y</math>.  Substituting <math>y = x</math> in this method gives <math>d_1 = p'(x)</math>, the derivative of <math>p(x)</math>.