Horner's Method vs (x-1)^n: Which is More Accurate for Evaluating Polynomials?

  • Context: Undergrad 
  • Thread starter Thread starter rukawakaede
  • Start date Start date
  • Tags Tags
    Method
Click For Summary

Discussion Overview

The discussion revolves around the evaluation of polynomials, specifically comparing Horner's method with the expression (x-1)^4 for the polynomial f(x)=1-4x+6x^2-4x^3+x^4. Participants explore the computational efficiency and numerical stability of these methods, considering their implications in practical applications.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants argue that Horner's method is more efficient and stable for evaluating f(x) due to fewer operations and reduced round-off error.
  • Others question the direct equivalence of f(x) and (x-1)^4, noting that recognizing the binomial expansion is not immediate and requires additional work.
  • One participant mentions that using (x-1)^4 can propagate numerical errors when x is close to 1, while Horner's method does not exhibit this issue.
  • Another participant discusses the concept of catastrophic cancellation when evaluating (x-1)^4, particularly in the context of subtracting nearly equal numbers.
  • Some participants provide examples and calculations to illustrate how numerical errors accumulate differently between the methods, particularly when x is near 1.
  • A later reply indicates that a mistake in code led to a realization that Horner's method was less accurate than initially thought.

Areas of Agreement / Disagreement

Participants express differing views on the efficiency and accuracy of the two methods, with no consensus reached on which is definitively better. The discussion remains unresolved regarding the comparative advantages of each approach in specific contexts.

Contextual Notes

Participants highlight limitations related to recognizing polynomial forms, the impact of numerical errors in calculations, and the conditions under which each method performs optimally. These factors contribute to the complexity of the discussion without reaching a definitive conclusion.

rukawakaede
Messages
58
Reaction score
0
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
f(x)=1-4 x+6 x^2-4 x^3+x^4
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
f(x)=1+x (-4+x (6+(-4+x) x))
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
f(x)=(x-1)^4
since it would only need 1 addition and 4 multiplication?

Could anyone share some insights on this?
 
Last edited:
Physics news on Phys.org
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.
 
epsi00 said:
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.

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?
 
"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.
 
epsi00 said:
when you are given "f(x)=1-4x+6x^2-4x^3+x^4" do you immediately recognize it as (x-1)^4?
Alright. I agree that needs some time.

epsi00 said:
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.
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.
 
"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...
 
rukawakaede said:
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
f(x)=1-4 x+6 x^2-4 x^3+x^4
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
f(x)=1+x (-4+x (6+(-4+x) x))
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
f(x)=(x-1)^4
since it would only need 1 addition and 4 multiplication?

Could anyone share some insights on this?
It looks to me like 1 addition and 2 multiplications (2 successive squares).
 
epsi00 said:
"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...

epsi00, thanks. I think I understand now. I nearly forgot catastrophic cancellation.
 
Last edited:
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.
 
  • #10
willem2 said:
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.

Thanks willem. I just realized that I made some mistake in my code and horner's method is less accurate that (x-1)^4.

Thank you very much.
 

Similar threads

Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
5K
Undergrad Looking for a creative or quick method for finding roots in GF(p^n)
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Quintic Polynomial Tschirnhaus Transform: Possible complex Bring Radicals
  • · Replies 0 ·
Replies
0
Views
3K
MHB Irreducible Polynomial g = X^4 + X + 1 over F2
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Generators of Galois group of ## X^n - \theta ##
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad I think I've hit upon a very easy proof of impossibility of quintic
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Splitting Fields and Separable Polynomials ....
  • · Replies 6 ·
Replies
6
Views
5K
High School Understanding Horner's Method: A Brief Explanation for Confusion
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad A question I have about my L.A. textbook (2)
  • · Replies 6 ·
Replies
6
Views
2K