Is there an algorithm to solve for the zeros of a polynomial of any degree? Could it be programmed into a computer language? Would there be one that would be small enough to program on a TI83 calculator (purely for theoretical purposes, of course:) )?

Thanks,

Brad

You could try various numerical methods; are you familiar with the Newton-Raphson method?
This states that x_n+1=x_n-f(x_n)/f ' (x_n) x_n® x as n®¥, where x is a solution of f(x)=0 (usually, and I think it should work for any polynomial). The solution is usually near to x₀, that is the starting point which you choose to begin the iteration with. Then you'd need some way of finding the range in which roots would be found, which could be done by an inspection of the equation. I don't know if this works for complex roots as well, but there are other, less elegant methods that I think would.

This could all be quite easily done on a computer for a polynomial as you can program the calculation of f'(x). If you tried to do it on a calculator you would be limited by a) speed of calculation, b) memory storage; you need to store n numbers for a polynomial of degree n and c) the way you're supposed to wipe all your programs before going into an exam :).

Tom

By the way, Newton-Raphson does work for complex roots - but only if you make a complex initial guess!

(You can draw some great fractal patterns by shading in areas of the complex plane in different colours according to which root they converge to if used as an initial approximation in Newton's method. Since you're obviously interested in programming, have a try on x³ -1=0 - this needs a PC of course.)


David

To get roots to n significant figures in Newton Raphson, how many times do you have to put it into the function. For example, if the question says do Newton Raphson on x² - 7 = 0 to get positive root to 3 sf, or even 2 dp, how many times do you put it into the function?

Hal.

For a sufficiently well-behaved function and a sufficiently close starting condition, the Newton-Raphson method is quadratically convergent. If you question is directed towards A-level examinations, then the answer is probably 3-4 iterations.

Kerwin

Thanks Kerwin, what do you mean when you said "quadratically convergent"?

Thanks
Hal.

The number of decimal places of accuracy doubles with each iteration.

Thanks Anon.

Hal.

Is there a way to find the symbolic roots? Also, will the Newton Raphson work in, say 20 iterations, even if I've chosen a number for the root that's way off? If not, what way can I narrow down the range for imaginary numbers without a lot of guess and check?

Thanks,

Brad

Brad

use equation solver (Math menu)

dimitri

Brad, you can't solve all polynomials symbolically, I think the equation X⁵ +X+1=0 will give you trouble (or is it X⁵ -X+1=0?). However, there are always symbolic solutions for polynomials of degree 4 or less, but they can be quite disgusting!

That all depends on what you mean by "symbolically". The result you're referring to is from Galois theory. Some polynomials can't be solved using only surds - ie expressing the solution as a sum of products of nth roots of rationals (like how we solve quadratics).

There are other ways to solve polynomials than this though, in particular a Fourier analysis is possible and you'll end up with a series of constants which define solutions although this may well be infinite and difficult to deal with. But symbolically it's a complete solution.

Oh, and pedantically I could always define the symbol urgh to mean an X which satisfies X⁵ +X+1=0. Such an X always exists in the Complex plane by the Fundamental Theorem of Calculus, and I've conveniently found an easy symbolic solution :-)

-Dave

Actually, I found out that there's quite an interesting theory associated to what can and can't be expressed symbolically, for instance it's relatively easy (about 2 or 3 pages, but I certainly can't remember the proof) to prove that the function òx^x dx cannot be expressed in terms of the standard functions like exp, log, sin, cos, +, -, ×, / etc.