10
$\begingroup$

I'm trying to evaluate a polynomial recursively using Horner's method.

It's rather simple when I have every value of $x$ (like: $x+x^2+x^3...$), but what if I'm missing some of those? Example: $-6+20x-10x^2+2x^4-7x^5+6x^7$.

I would also appreciate it if someone could explain the method in more detail, I've used the description listed here but would like some more explanation.

  • 3
    If you are missing terms, the corresponding coefficient to use in the method is 0.2011-07-02

3 Answers 3

10

$6x^7-7x^5+2x^4-10x^2+20x-6$ =

$6x^7+0x^6-7x^5+2x^4+0x^3-10x^2+20x-6$

The method is essentially start with the coefficient of the highest power, multiply by $x$ and add the next coefficient. Stop when you add the constant coefficient.

So steps in the iteration go:

$6$

$6x[+0]$

$6x^2-7$

$6x^3-7x+2$

$6x^4-7x^2+2x[+0]$

$6x^5-7x^3+2x^2-10$

$6x^6-7x^4+2x^3-10x+20$

$6x^7-7x^5+2x^4-10x^2+20x-6$

Trust this helps

7

Horner's method or form is also sometimes called nested form. You can think of it as starting with the whole polynomial $6x^7-7x^5+2x^4-10x^2+20x-6,$ setting aside the constant term (if it's zero, you can set aside a zero here) and factoring out an $x$ from the remaining terms $(6x^6-7x^4+2x^3-10x+20)x-6,$ and then repeating the process for the innermost polynomial (the part that isn't yet fully in nested form: $((6x^5-7x^3+2x^2-10)x+20)x-6$ $(((6x^4-7x^2+2x)x-10)x+20)x-6$ $((((6x^3-7x+2)x+0)x-10)x+20)x-6$ $(((((6x^2-7)x+2)x+0)x-10)x+20)x-6$ $((((((6x)x-7)x+2)x+0)x-10)x+20)x-6$ $(((((((6)x+0)x-7)x+2)x+0)x-10)x+20)x-6$

Alternately, if your polynomial is $p(x)=\sum_{k=0}^{n}a_kx^k=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,$ you can think of $p(x)$ in nested form as $p_0$ where $p_n=a_n$ and $p_{k-1}=p_kx+a_{k-1}$. That is, start with the leading coefficient ($a_n$). Multiply by $x$ and add the next coefficient (adding zero to fill in for "missing" powers of $x$), repeating until you've added the constant term ($a_0$). Back to the same example: $\begin{align} p_7&=6\\ p_6&=(6)x+0\\ p_5&=((6)x+0)x-7\\ p_4&=(((6)x+0)x-7)+2\\ p_3&=((((6)x+0)x-7)+2)x+0\\ p_2&=(((((6)x+0)x-7)+2)x+0)-10\\ p_1&=((((((6)x+0)x-7)+2)x+0)-10)+20\\ p_0&=(((((((6)x+0)x-7)+2)x+0)-10)+20)-6 \end{align}$

  • 0
    @Mark: I just $n$oticed that about the example (so just edited that li$n$e out of my a$n$swer)... apparently, I need to work on reading the original question better.2011-07-02
6

You can also carry it out in a synthetic division table. Suppose you want to evaluate $f(x) = x^4 - 3x^2 + x - 5$ for $x = 3$. Set up a table like this

                1    0     -3    1     5           3              -------------------------               1 

Now multiply the number on the bottom and total as follows.

                1    0     -3    1     5           3        3              -------------------------               1    3 

Work your way across in this manner.

                1    0     -3    1     -5           3        3      9   18    57              -------------------------               1    3      6   19    52 

We have $f(3) = 52$. Let's run a check

$ f(3) = 81 -3*9 + 3 - 5 = 54 - 2 = 52.$ $ f(3) = 54 - 2 = 52.$

This is a clean, tabular way to see Horner's method work.

  • 0
    You have multiple typos; -5 in the table and 52 in the result.2018-02-11