Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Horner's method vs (x-1)^n

  1. Mar 21, 2012 #1
    Firstly, I am not sure if I am in the right section. Pardon me.

    I was reading something related to computational efficiency when evaluating polynomials. Suppose we want to evaluate
    [itex]f(x)=1-4 x+6 x^2-4 x^3+x^4[/itex]
    it would take n=4 additions and (n^2+n)/2 =10 multiplications to evaluate this f(x) on computer.

    We know that it would be better (efficiency and stability) to evaluate f(x) using Horner's method, i.e
    [itex]f(x)=1+x (-4+x (6+(-4+x) x))[/itex]
    which only take n=4 additions and n=4 multiplications on the computer, (i.e. round-off error will be minimised).

    So here is my question: wouldn't it better to evaluate
    since it would only need 1 addition and 4 multiplication?

    Could anyone share some insights on this?
    Last edited: Mar 21, 2012
  2. jcsd
  3. Mar 21, 2012 #2
    no, in my opinion, because you need to do some work to go from 1-4x+6x^2-4x^3+x^4 to (x-1)^4. It is not obvious that the two functions are the same.
  4. Mar 21, 2012 #3
    Well, it is just the binomial expansion of (x-1)^4.

    I don't understand why we should not evaluate the f(x) directly using (x-1)^4 in terms of computational efficiency.

    I believe this is something trivial, but I can't see it myself. Hope someone could give some idea.

    I wrote some codes and plotted all the three variations of the functions with x around integer 1. It seems that only Horner's method give a desirable result. Significant numerical error occurs for the other two.

    I understand that f(x)=1-4x+6x^2-4x^3+x^4 is give worse numerical result because of the number of multiplications and the rounding error accumulates.

    But for f(x)=(x-1)^4, what other reasons (other than number of calculations) could that be?
  5. Mar 21, 2012 #4
    "Well, it is just the binomial expansion of (x-1)^4."

    when you are given "f(x)=1-4x+6x^2-4x^3+x^4" do you immediately recognize it as (x-1)^4? Using (x-1)^4 to calculate the value of the function around x~1 propagates the numerical errors which does not happen with Horner's. (x-1)^4 should be fine for x not close to 1.
  6. Mar 21, 2012 #5
    Alright. I agree that needs some time.

    Thanks. This is what I am looking for.
    Could you please explain a little bit more on how numerical errors accumulate for (x-1)^4 when is x is about 1?
    I am still not fully understand.
  7. Mar 21, 2012 #6
    "Could you please explain a little bit more on how numerical errors accumulate for (x-1)^4 when is x is about 1?"

    I took the numerical analysis course a long time ago. I am not sure I can provide you with an explanation. It has to do with substracting numbers that are almost equal...
  8. Mar 21, 2012 #7


    User Avatar
    Science Advisor

    It looks to me like 1 addition and 2 multiplications (2 successive squares).
  9. Mar 21, 2012 #8
    epsi00, thanks. I think I understand now. I nearly forgot catastrophic cancellation.
    Last edited: Mar 21, 2012
  10. Mar 22, 2012 #9
    Calculating (x-1)^4 by first calculating (x-1) and then calculating the fourth power seems to be the only way to get reasonable accuracy, when x is close to 1.

    Suppose a multiplication gives a relative error of e, and addition/subtracton gives an error of e/(operand with largest absolute value)

    suppose you calculate (x-1)^4 for x=1.01

    (x-1) will produce a result of 0.01+e, (hopefully e<0.01)

    (x-1) will produce a result of 10^(-8) + 4 * 10^(-8) e, so you get a relative error of 4e.
    (ignoring higher powers of e)

    The final addition when using horner rule will produce an error of at least e, on a result of 10^(-8), so a relative error of 10^8 (e) (ignoring the errors in the earlier steps),
    so Horners' rule is a factor of 2.5 * 10^7 less accurate.
  11. Mar 22, 2012 #10
    Thanks willem. I just realised that I made some mistake in my code and horner's method is less accurate that (x-1)^4.

    Thank you very much.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook