A question about the Taylor series and polynomails

This topic is 3121 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

In a previous thread, the Taylor series was suggested for solving polynomials. I've finally gotten around to it, only to run into a lot of problems. Problems which would make more sense if: The Taylor series was suggested after I posted a polynomial solver that resolves polynomial roots; I therefore assumed that the Taylor series resolves polynomial roots. However, if what I'm thinking is correct, the Taylor series solves for X, which is very different than what I'm aiming for. If that is correct and the Taylor series is not useful for my purposes (Solving for f(x) = 0, or in other words, resolving roots for = 0), what would be a good, fast way of resolving roots? I've already implemented the Brent algorithm, which Wikipedia suggested. Thanks.

Share on other sites
I'm not sure what you're referring to. The Taylor series isn't a "method" and it doesn't "solve" for anything. It's just a way to approximate a function at a point using its derivatives.

AFAIK, Brent's method converges to a root of a polynomial if you start knowing that it lies in some interval. Would you instead like to find all roots, or to figure out what intervals to use?

If so, there's a very simple algorithm to find all the distinct real roots; I don't know its name, but IIRC Dave Eberly posted it a while back, and in essence it works like this: You repeatedly differentiate the polynomial until you've got a line, and then work your way back up...

I'll describe it in a second; first, however, I need to mention that the technique also needs a bound on the location of real roots. One is due to Cauchy. Call the polynomial 'p' and suppose it is of the form

p(x) = x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0

for real coefficients a_{n-1}, ..., a_0. Then Cauchy's bound states that all roots lie in the interval [-1 - A, 1 + A], where A is the largest absolute value of a coefficient. I'll also define B = 1+A, so I can just say that all the roots are in [-B,B].

Now, on to the derivatives. Consider the sequence of polynomials

p_n = p
p_{n-1} = D p_n
...
p_1 = D p_2

where 'D' denotes differentiation. You can do this on a computer; it's just operations on the coefficients.

Now, consider the polynomial of degree 1, a line, p_1: It has one root which you can find analytically; call it r_1. Once you've found it, you know that p_2 is monotonic on [-B,r_1] and [r_1,B], and hence for each of these intervals that it contains a real root if and only if p_2 differs in sign at its endpoints. If it does contain a real root, then you can reliably find it by e.g. the bisection method (the false position method and Brent's algorithm should also work here). (Note also that the endpoints themselves can also happen to be roots.)

Now that you know the zeros of p_2, you know the intervals in which p_3 is monotonic. Hence you can bracket the roots of p_3 and find them reliably. Once you have the roots of p_3, you move up to p_4, and so on, until you've found all the zeros of p_n.

Share on other sites
Perhaps I worded things a bit less than clearly. So, in response, "Thereby solving that function (To some degree of precision) for input X".

Thank you for that algorithm. It looks like a much more evolved version of the algorithm I have and should result in a considerable improvement.

Not sure where you've got the word "method" from.

(Edited to alter questionable grammar. Not in a good mood)

Share on other sites
Quote:
 Original post by Narf the MousePerhaps I worded things a bit less than clearly. So, in response, "Thereby solving that function (To some degree of precision) for input X".

Yep, got that.

Quote:
 (Edited to alter questionable grammar. Not in a good mood)

Missed that. Anyway, good luck.

Share on other sites
Thanks - My current eventual goal with this is calculating things like course matches for things like spaceships, missiles and such - I'm building libraries towards game making and as a hobby.

A thought - A modified Runge-Kutta (Modified towards picking the lowest number, perhaps with a divide by average/multiply by average first and last steps) could probably converge rather fast per step, but would it be any faster than just doing four bisections?

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 11
• 15
• 12
• 14
• 9
• Forum Statistics

• Total Topics
633352
• Total Posts
3011483
• Who's Online (See full list)

There are no registered users currently online

×