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

[rukawakaede]

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?

 

[epsi00]

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.

 

[rukawakaede]

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?

 

[epsi00]

"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.

 

[rukawakaede]

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.

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.

 

[epsi00]

"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...

 

[mathman]

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).

 

[rukawakaede]

"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.

 

[willem2]

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.

 

[rukawakaede]

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.