Bisection method and multiple roots

[nikolafmf]

Hello,

I have a polynomial of order n and I want to find all it's roots with bisection method. Is it possible? I already wrote an algorithm to find a root and it's works nice for finding one of it's roots, but what about others?


Nikola

 

[jbriggs444]

I have a polynomial of order n and I want to find all it's roots with bisection method. Is it possible? I already wrote an algorithm to find a root and it's works nice for finding one of it's roots, but what about others?

The method only finds real-valued roots. It does not find complex-valued roots. It also requires that you first find two points where the function value has opposite signs.

However, off the top of my head, I think that you can exploit the method to find all real-valued roots. Start by recursively finding all roots of the first derivative. Those are the candidates for local extrema of the polynomial in question. Between these points the polynomial will either be strictly increasing or strictly decreasing.

Say you start with a polynomial of degree n. There are at most n-1 zeroes of the first derivative. If you sort them in order, they divide the real number line into at most n-2 open intervals plus one open-ended interval on the right and one on the left.

Within each of these intervals there can be at most one real root of the polynomial. It is straightforward to determine whether or not a root exists in each interval. If a root exists, it is straightforward to find function values of opposite sign. That will then provide a starting point to allow the bisection method to find the root.

 

[AlephZero]

I suppose you are looking for real roots (not complex roots) since you want to use the bisection method.

You can find an interval containing all the real roots using http://en.wikipedia.org/wiki/Samuelson's_inequality

You can use http://en.wikipedia.org/wiki/Descartes'_rule_of_signs to find the number of real roots, and http://en.wikipedia.org/wiki/Sturm's_theorem to find intervals that each contain one root.

Note, the bisection method might not work if the polynomial has repeated roots. For example, try to find the roots of $x^2 - 2x + 1 = 0$.

 

[mathman]

http://en.wikipedia.org/wiki/Sturm's_theorem

I had found that, using Sturm's sequence (above), you can get intervals for all real roots of polynomials. Personal note: many years ago I implemented the procedure and it worked well on polynomials of eighth degree using double precision arithmetic.

 

[AlephZero]

http://en.wikipedia.org/wiki/Sturm's_theorem

Personal note: many years ago I implemented the procedure and it worked well on polynomials of eighth degree using double precision arithmetic.

The general concept of a Sturm sequence has other uses in numerical analysis. For example it can be used to count the number of eigenvalues of a matrix less than a given value. (Of course you can relate that theoretically to counting the roots of the characteristic polynomial, but you don't want to find the polynomial explicitly for a matrix of size 100,000 x 100,000!)

Finding eigenvalues using only Sturm sequences and interval bisection would not be very efficient for large matrices, but it's a valuable check that faster but possibly less reliable numerical methods have found all the eigenvalues in an interval.

It is efficient if you can first reduce the matrix to a special form, e.g. tridiagonal. That type of method was the state of the art back in the 1960s and 70s, for matrices of order up to about 500 (or 1000 if you got lucky).

 

[lurflurf]

Note, the bisection method might not work if the polynomial has repeated roots. For example, try to find the roots of $x^2 - 2x + 1 = 0$.

Many things can go wrong. One thing to do is find the roots of the derivative.

 

[mathman]

Many things can go wrong. One thing to do is find the roots of the derivative.

Using Sturm sequence method, you will find an interval containing 2 real roots (although, the numerics may give you 0 rather than 2). The interval can be repeatably shrunk.