# Evaluating a polynomial using Horner's algorithm

With Horner's algorithm, I can solve f(x$_{0}$) for a polynomial like this: $a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$

By doing this:

b$_n$ = a$_n$

b$_{n-1}$ = a$_{n-1}$ + b$_n$x$_0$

b$_{n-2}$ = a$_{n-2}$ + b$_{n-1}$x$_0$

...

b$_0$ = a$_0$ + b$_1$x$_0$

Where b$_0$ = f(x$_{0}$). The problem is doing Horner's algorithm on something like this: $a_1 + a_2(x + y_1) + a_3(x + y_1)(x + y_2) + a_4(x + y_1)(x + y_2)(x + y_3) + ... + a_{n+1}(x + y_1)(x + y_2)(x + y_3)...(x + y_n)$

So instead of a going from a$_0$ to a$_n$ it goes from a$_1$ to a$_{n+1}$ so for b$_n$, is it supposed to be b$_n$ = a$_{n+1}$? Also let's say we're trying to solve f(1.53) and we have:

a = -1, 3.3, 0, -2.2, 5, -1.6
y = -1, 1, -1, 1, -1


So if n = 5, this is how I did Horner's algorithm:

b$_5$ = -1.6

x$_0$ = (1.53 - 1)(1.53 + 1)(1.53 - 1)(1.53 + 1) = 1.79801281

b$_4$ = 5 + (-1.6)(1.79801281) = 2.123179504

x$_0$ = (1.53 - 1)(1.53 + 1)(1.53 - 1) = 0.710677

b$_3$ = -2.2 + (2.123179504)(0.710677) = -0.691105159

x$_0$ = (1.53 - 1)(1.53 + 1) = 1.3409

b$_2$ = 0 + (-0.691105159)(1.3409) = -0.926702907

x$_0$ = (1.53 - 1) = 0.53

b$_1$ = 3.3 + (-0.926702907)(0.53) = 2.808847459

b$_0$ = -1 + (2.808847459)(1.53) = 3.297536612

The problem is that f(1.53) = 6.65086 which is not what b$_0$ is so what am I doing wrong?

instead of a going from $a_0$ to $a_n$ it goes from $a_1$ to $a_{n+1}$ so for $b_n$, is it supposed to be b$_n$ = $a_{n+1}$?

The index needs adjusted, indeed. However, that's not the only change you need to make. Unlike in the case of Horner's method, the second expression is not a polynomial, since the terms do not contain consecutive powers of the same $\,x\,$. To account for that, the recurrence must be modified to:

\begin{align} b_{n} &= a_{n+1} \\ b_{n-1} &= a_n + b_n(x+y_n) \\ b_{n-2} &= a_{n-1} + b_{n-1}(x+y_{n-1}) \\ &\cdots \\ b_{1} &= a_{2} + b_{2}(x+y_2) \\ b_{0} &= a_{1} + b_{1}(x+y_1) \\ \end{align}

The above is equivalent to writing the expression as:

$$a_{1}+(x+y_1)\bigg(a_{2}+(x+y_2)\Big(a_{3}+\cdots +(x+y_{n-1})\big(a_{n}+a_{n+1}(x+y_n)\big)\Big)\bigg)$$

$$b_n=a_n$$

for $k$ from $n-1$ to $0$

$$b_k=a_k+b_{k+1}x_0$$

• So are you saying that I should start with bn=an? Also am I right about x0? – Josh Susa Mar 4 '18 at 20:58
• @JoshSusa you start from b_n=a_n and you compute successively b_{n-1}... untill b_0. – hamam_Abdallah Mar 4 '18 at 21:00
• So then for my example, would I start by saying b5 = 5 and then b4 = -2.2 + (5)(1.3409)? – Josh Susa Mar 4 '18 at 21:13
• @JoshSusa continue untill b_0 which is the result. – hamam_Abdallah Mar 4 '18 at 21:17
• Yes I am aware of how Horner's algorithm works. My problem is using Horner's algorithm with the above polynomial. Using Horner's algorithm I got 3.29754 but f(1.53) = 6.65086 which means I must have done something wrong. Maybe I could post what I did and you can tell me where I went wrong? – Josh Susa Mar 4 '18 at 21:22