In my institute we study all possible sources of errors while evaluating sin(x) using its Taylor expansion. So we must evaluate some polynome and we use different methods for that. What I am interested in is the Horner's method. Our teacher says that it is unstable and error gets magnified as the calculations proceed. But I cannot understand the reasons of errors growth. Futhermore, I am also to modify this method so it would become stable. Please, explain me this method and its modification.

I wouldn't be so hasty to conclude that Horner's scheme for polynomial evaluation is unstable. Sure, for some classes of polynomials Horner's can give demonstrably wrong examples, but for all the others, Horner is the most efficient and accurate way of evaluating a polynomial.

Now about your question. The reason calculating sin() via its Taylor series is unstable is that the series is altenating, and that the absolute values of the terms are first increasing in magnitude before decaying slowly to zero. It is due to this that Taylor series, in general are usually not very good for function approximation quite far away from its expansion point.

The best way you can minimize round-off is probably to sum backwards. How far away? Your calculus book may offer some tips. (~_^)

Hope this helps.

Jan M. (^_^)

I suppose that our teacher meant that exactly for Taylor series of sin(x) Horner's method becomes unstable. I don't know, maybe this is due to the fact that all the coefficients of Taylor expansion are less than 1 in absolute value? Thanx, Jan, your post is familiar for me :-) We have 4 methods of evaluating the polynome: sum forwards; backwards; substract the sum of all negative terms from the sum of all positive terms (which is the most unstable method); and Horner's scheme. And we can visually estimate the stability of all these approaches with special software. And I can see that with the same number of terms Horner's method is almost the worst one. With the growth of x it gives a significant error :( Why is that? Please, my educator wil tear me asunder!

I'll quote you first:

"...maybe this is due to the fact that all the coefficients of Taylor expansion are less than 1 in absolute value?"

Yes, that's true; ((2n+1)!)^-1 is surely a sequence that decreases quickly! However, these coefficients come with LARGE powers of x (that is, if x is quite far away from the expansion point).

Using Horner's scheme on the Taylor polynomial for sin() would look something like this:

x*(1 + x^2*((-1/3!) + x^2*((1/5!) + x^2*(... +(-1)^n/(2n+1)!*x^2)))

I can try to explain why Horner's performs badly in this example, but methinks you can figure out why if you do the Horner evaluation step-by-step (i.e., by hand!). THEN tell me what you get.

I didn't quite get you :-) You think I'm a lazy imbecile that doesn't want to do anything? :-))) And so you try to make me do something? I assure you, that I have posted this thread after 4 days of permanent thinking. I tried to do evaluations step by step using pen, sheet of paper and the Horner's scheme in the form you have written above. I thought at first that in this scheme small coefficients are multiplied by just x^2 and this can bring about some error. But then this x^2/((n+2)!) is summed with 1/n! and these 2 numbers don't differ too much in absolute value, so none of them is neglected in computer. This damned thing now lurks deeply in my mind, it even bothers me in my dreams. What am I missing in my cogitation? That is beyond my understanding.

I shall quote you again:

"...But then this x^2/((n+2)!) is summed with 1/n! and these 2 numbers don't differ too much in absolute value..."

Yes, they are almost the same in absolute value; however, they DIFFER in sign. You, my friend, have just become a victim of the phenomenon called "subtractive cancellation"; the same reason why the strategy of "subtract the sum of all negative terms from the sum of all positive terms" is quite a bad idea, too. The problem is that attempting to add two numbers almost equal in magnitude, but different in sign, causes you to lose a lot of significant bits in floating-point arithmetic. See any good numerical analysis book for details.

My apologies if I might have offended you. Hope the last paragraph may be of some help. Good luck!

Jan M. (^_^)

Thanx a lot, I finally got it! Yes, it is true, subtracting two close numbers can give us great errors, now I know that. So to the second part of my question. How can we modify Horner's scheme to make it stable? I will go and think over it but, please, if you know it, tell me, my time for thoughts is almost over :))