Finding the irrational zeros of a polynomial

G

Guest

Guest
Ok, I am making a computer program to find all of the zeros of any polynomial. So far, the program finds all rational and imaginary solutions. It does not, however find the irrational or irrational imaginary solutions. I would realy like it to. I have searched on google and other websites to see how to find the irrational solutions, but none of the information seemed very clear to me. I could not find one that would work for any equation. Most would find a few rational solutions, then would use the equations it got from putting those into synthetic divition to find the irrational. What if all zeros are irrational? How do you find them? My math teacher has said that they are represented graphically as a bump in the line, but wouldent that be a minimum or maximum, not always a zero? How are zeros represented on the graph?

I know that I am supposed to post my work, but I realy dont have time, so sorry!
Any help on this subject would be greatly apreciated!
 
The "bump" normally would represent a min or max. Very good. The point that may not be obvious, is that roots lie between the bumps, if the roots are Real.

A general polynomial solver would have two features:

1) Find a root.
2) Reduce the polynomial
 
My program already finds all the rational and imaginary roots, it also already simplifies and reduces the equation as much as it can, but it does not find irrational roots, and I would like to add that feature.

Thanks for the reply, but I need some more help.
 
You program "solves" only by factoring?

You will have to switch to numerical methods to solve for anything that cannot be reduced to a quadratic - unless you REALLY want to code the general solutions to cubics and quartics. I'm guessing you don't want to do that.
 
I don't remember saying that my program solves by factoring. The way that my program solves is by finding all possible rational solutions, then puting them into synthetic devision to see if they equal zero.

What do you mean by "numerical methods"?

I will code whatever, if I think that it will be worth the time. Could you tell me what the "general solutions to cubics and quartics" are?

I guess a more simple version of my question is "How do you find the zeros of a polynomial if it has no rational zeros?"

If you have an irrational zero, and put it into synthetic devision, will it equal zero?
 
blitznerd said:
I don't remember saying that my program solves by factoring. The way that my program solves is by finding all possible rational solutions, then puting them into synthetic devision to see if they equal zero.
Click to expand...
Essentially factoring.

What do you mean by "numerical methods"?
Click to expand...
Anything that cannot provide the exact answer, but can provide a solution to any degree of accurace allowed by your implementation.

Could you tell me what the "general solutions to cubics and quartics" are?
Click to expand...
I could, but seriously, they are theoretical constructs and are of little or no value in any commercial or useful application. You can find descriptions on the internet if you are REALLY interested. Waste of time if you ask me. It is important to know that they exist.

I guess a more simple version of my question is "How do you find the zeros of a polynomial if it has no rational zeros?"
Click to expand...
I'm still puzzled by this. What difference does it make whether or not any are Rational?

If you have an irrational zero, and put it into synthetic division, will it equal zero?
Click to expand...
Within the rounding precision of your process.
 
Thanks for the help!
About "What difference does it make whether or not any are Rational?"
The way I find the possible rational zeros is by dividing the last term and all of its factors by the first term and all of its factors. For example:
4x^3 - 7x^2 + 5x + 3
The possible rational zeros are:
+- 3/4 , 1/4 , 3/2 , 1/2 , 3/1 , and 1/1

So, I guess my question is, how to find the possible irrational solutions. Is there a way to find them? Is there a certain range that they will always be in (ex: I think that I heard that all solutions will be between -last term and last term, is that always true, or only with the rational zeros?)
 
Have you met the Upper Bound Theorem? If everything across the bottom of the synthetic division tableau is positive, there are no more solutions for anything greater than the value that produced all the positive values. There is a similar result for negative values.

The advantage of a polynomial is that it has very predictable behavior, except perhaps for a predictable SubDomain. ANY odd-order polynomial has a Real solution. Read up on Newton's Method. It is very quick when it works. It will zip you right to any root of your polynomial with a very high degree of reliability. It doesn't care if it is Rational.
 
Ok, I think I have newtons method figured out. When will it not work?

Thanks for the Upper Bound Theorem refrence. What is the "similar result for negative values?"

Are there any other theorems or things that might tell me within what 2 x coodinates all the roots lie?
 
Thanks, it is good to know that that is a good one, but I think I have found enough links to different methods on then "root finding algorithms" wikipedia page. I am now more interested in finding what two x coordinates all roots are between. I also would like to know how to have my program find aproximations of roots that I can then plug into either newton's, Laquerre's, or some other method.
 
tkhunny said:
A general polynomial solver would have two features:

1) Find a root.
2) Reduce the polynomial
Click to expand...
Reducing a polynomial by factoring out a root is called deflation. Iterating between finding a root and deflating is the general method of solving polynomials.

Searching for "deflation root polynomial" using Ask.com produced this link, which has a lot of good information in it. (I'm finding Ask.com often produces better search results than Google.)
 
Have you read my previous posts?
I already said that my program reduces (or deflates) the polynomial as far as it can, but it needs at least one rational zero to do that. My question (stated in a previous post) is how to find the zeros if all of them are irrational.
 
blitznerd said:
Have you read my previous posts?
I already said that my program reduces (or deflates) the polynomial as far as it can, but it needs at least one rational zero to do that. My question (stated in a previous post) is how to find the zeros if all of them are irrational.
Click to expand...
Yes, I read your posts. I see I did not explicitly address your immediate concern about finding a root. But I did not see you acknowledge what the basic algorithm would be.

To find a root, call Laguerre's method with initial value 0. One of the benefits of Laguerre's method is that it has good global convergence properties. Deflate with root found. Iterate.

This algorithm will generally work just fine, but there a some situations where it can fail. If you really want a program that handles all the possibilities, I suggest you find a current textbook on numerical analysis and look at the section on finding roots of polynomials.
 
blitznerd said:
Ok, I think I have newtons method figured out. When will it not work?

Thanks for the Upper Bound Theorem refrence. What is the "similar result for negative values?"

Are there any other theorems or things that might tell me within what 2 x coodinates all the roots lie?
Click to expand...
Examine f(-x) for results in the other direction.

Root finding is not so tricky with polynomials. They tend to be quite well-behaved. Just pick something and and let the iterations work for you. If you run out of Real roots, simply start with a Complex guess. Once you get it down to a quadratic, your done.

Newton's method can fail if you happen to start at a stationary point. Just count your iterations. If you aren't getting anywhere after a few iterations, start from some other guess value.

I've never used Laguerre. It might be fun to investigate. Still, more calculation for faster convergence is a common trade-off.
 
Laguerre's method has a few advantages.
  • Global convergence when polynomial has only real roots. Performs well with complex roots but is not guaranteed.[/*:m:17k0mhuk]
  • Can start searching complex plane on it own from real initial value. Newton's won't.[/*:m:17k0mhuk]
  • Faster convergence but with more computations.[/*:m:17k0mhuk]
I favor Laguerre's because it is recommended by my numerical analysis textbook.
 
Seems like it should be required reading. I wonder how I managed to miss it. It wouldn't be the first time I fell asleep in class.
 
Thanks for the replies! Quite usefull!

Do you know of any good online numerical analysis books? Calculus books?

I just realized that I need more info if I am going to use irrational numbers. How do you deflate with an irrational root? Plug it into synthetic devision? Won't that get inacurate if there a lot of irrational roots?
 
I found my college text book, W. Allen Smith, Elementary Numerical Analysis, 1979. Laguerre is mentioned on one page, and it is only a reference, not even a discussion.

In another text I acquired a few years later, Burden, Faires, Reynolds, Numerical Analysis, 1981 (2nd Edition). Laguerre Polynomials are quite prominent, but the "Method", again, is only a single reference.

Time to update!
 
My college textbook is even older: Bjork and Dahlquist, Numerical Methods, 1974. I've found recent references to Laguerre's method, so it has stood the test of time. But I've also found alternatives not in that book; it pays to stay current.

Here is a link to an online numerical analysis book:



Fortran 77 sounds pretty ancient (back to the days of my textbook), but the book does have fairly recent editions. Chapter 9.5 covers roots of polynomials.
 
You must log in or register to reply here.
Top