3.2 Horner’s method and deflation
To evaluate \(P(x_0)\) we use the nested form already met in Example 1.2.11: \[P(x_0) = \Bigl (\cdots \bigl ((a_nx_0+a_{n-1})x_0+a_{n-2}\bigr )x_0+\dots +a_1\Bigr )x_0+a_0 ,\] which needs only \(n\) multiplications and \(n\) additions. The intermediate values do more than evaluate \(P\).
Theorem 3.2.1 (Horner’s Method). Let \(P(x) = \sum _{k=0}^na_kx^k\) and define \[b_n = a_n,\qquad b_k = a_k+b_{k+1}x_0\quad (k = n-1,n-2,\dots ,0).\] Then \(b_0 = P(x_0)\). Moreover, if \(Q(x) = b_nx^{n-1}+b_{n-1}x^{n-2}+\dots +b_2x+b_1\), then \[P(x) = (x-x_0)Q(x)+b_0 .\] In particular \(P'(x_0) = Q(x_0)\), and if \(P(x_0) = 0\) then \(P(x) = (x-x_0)Q(x)\) (the factor theorem).
Proof. Expand the right-hand side: \begin {align*} (x-x_0)Q(x)+b_0 &= b_nx^n+(b_{n-1}-b_nx_0)x^{n-1}+\dots \\ &\qquad +(b_1-b_2x_0)x+(b_0-b_1x_0) . \end {align*}
By the definition of the \(b_k\), each bracket \(b_k-b_{k+1}x_0\) equals \(a_k\), and \(b_n = a_n\); so the right-hand side is \(P(x)\). Setting \(x = x_0\) gives \(P(x_0) = b_0\). Differentiating, \(P'(x) = Q(x)+(x-x_0)Q'(x)\), and so \(P'(x_0) = Q(x_0)\). □
The \(b_k\) are conveniently arranged as a table, synthetic division: write the coefficients in the top row, bring down \(a_n\), and at each step multiply by \(x_0\), write the product under the next coefficient, and add. Applying the same process to the \(b_k\) (the coefficients of \(Q\)) gives \(Q(x_0) = P'(x_0)\). So one Newton step for a polynomial needs only two passes of Horner’s method.
Algorithm 3.2.2 (Horner’s method for \(P(x_0)\) and \(P'(x_0)\)). Input: degree \(n\), coefficients \(a_0,\dots ,a_n\), and \(x_0\). Output: \(y = P(x_0)\) and \(z = P'(x_0)\).
- Step 1:
- Set \(y = a_n\) and \(z = a_n\).
- Step 2:
- For \(j = n-1, n-2,\dots ,1\): set \(y = x_0y+a_j\) and \(z = x_0z+y\).
- Step 3:
- Set \(y = x_0y+a_0\). Output \(y\) and \(z\).
Example 3.2.3. Let \(P(x) = 2x^4-3x^2+3x-4\). Use Horner’s method to compute \(P(-2)\) and \(P'(-2)\), and then find a root by Newton’s method from \(x_0 = -2\).
Solution. The coefficients are \(2, 0, -3, 3, -4\) (note the zero for the missing \(x^3\) term). Synthetic division by \(x_0 = -2\):
| \(2\) | \(0\) | \(-3\) | \(3\) | \(-4\) | |
| \(x_0 = -2\) | \(-4\) | \(8\) | \(-10\) | \(14\) | |
| \(2\) | \(-4\) | \(5\) | \(-7\) | \(10\) |
So \(P(-2) = 10\) and \(Q(x) = 2x^3-4x^2+5x-7\). Dividing \(Q\) by \(x+2\) in the same way:
| \(2\) | \(-4\) | \(5\) | \(-7\) | |
| \(x_0 = -2\) | \(-4\) | \(16\) | \(-42\) | |
| \(2\) | \(-8\) | \(21\) | \(-49\) |
So \(P'(-2) = Q(-2) = -49\), and Newton’s method gives \(x_1 = -2-\frac {10}{-49} = -1.795918\). Continuing in the same way, \[x_2 = -1.742432917,\qquad x_3 = -1.738970235,\qquad x_4 = -1.738956257,\qquad x_5 = -1.738956256,\] with \(P(x_4) = 4\times 10^{-4}\) and \(P(x_5) = 7\times 10^{-9}\). Direct differentiation agrees: \(P'(x) = 8x^3-6x+3\) gives \(P'(-2) = -49\).
Deflation
Once an approximate root \(\hat x_1\) has been found, Horner’s method gives \(P(x)\approx (x-\hat x_1)Q_1(x)\), and the remaining roots of \(P\) are approximately the roots of the deflated polynomial \(Q_1\), of degree one less. Repeating this finds all the roots.
Solution. Dividing by \(x-\hat x_1\) with \(\hat x_1 = -1.738956256\) gives the deflated cubic \[Q_1(x) = 2x^3-3.477912513x^2+3.047937724x-2.300230374 .\] Newton’s method on \(Q_1\) from \(x_0 = 1\) gives the real root \(\hat x_2 = 1.254881884\), and deflating again leaves a quadratic whose roots, by the quadratic formula (in complex arithmetic), are \[\hat x_{3,4} = 0.2420372\pm 0.9262455i .\] So \(P\) has two real roots, \(-1.7389563\) and \(1.2548819\), and a pair of conjugate complex roots, as Theorem 3.1.4 allows.
Note. Each deflation uses an approximate root, so the coefficients of \(Q_k\) carry the errors of all the earlier roots, and the later roots can be noticeably less accurate. Two precautions help. First, find and deflate the roots of smallest modulus first. Second, use each root found from a deflated polynomial only as a starting value, and refine it by a few Newton steps on the original \(P\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.