Roots of a polynomial

First of all, I don't have any idea what you're talking about. Give a proper URL if you want an answer.

Second, you have posted THE SAME TEXT in two different posts, once to sci.math and once to comp.dsp, sci.eng.control, and sci.math.num-analysis. The one to three newsgroups is in approved form, and doesn't increase bandwith. The one to sci.math DID increase bandwidth.

I can guess what you mean from context, and it's not difficult to code. All you have to do is estimate the derivative of f'(z)/f(z) on a contour (all you need is an upper bound on the absolute value, so you have a Lipschitz constant on the contour), then take a fine enough grid on the parameterization of the contour so as to be able to recognize the discretization of the integral as being close enough to an integral multiple of 2 pi i. This yields the degree of the mapping, which is the count of roots. Perfectly routine.

--Ron Bruck

The book "Numerical Recipes in C" has a polynomial root finder.

"Tim Wescott" schrieb

I keep finding on the web references that are saying that this book is less than optimal. What's the opinion here? Any other good books about numerical methods that can be recommended?

Regards Martin

If you mean by "less than optimal" that a clever programmer can write a more efficient algorithm, that is often true. It is rarely true that the routines don't perform as claimed. Avoiding NR because the code could perhaps be improved is like choosing to walk because the bicycle you've been offered is less than best.

Jerry

Jerry> Martin Blume wrote: >> "Tim Wescott" schrieb >> >>> The book "Numerical Recipes in C" has a polynomial root finder. >>> >> I keep finding on the web references that are saying >> that this book is less than optimal. What's the opinion here? Any >> other good books about numerical methods that can be recommended?

Jerry> If you mean by "less than optimal" that a clever programmer can write Jerry> a more efficient algorithm, that is often true. It is rarely true that Jerry> the routines don't perform as claimed. Avoiding NR because the code Jerry> could perhaps be improved is like choosing to walk because the bicycle Jerry> you've been offered is less than best.

In this particular case, I think they usually mean the NR code is not serious numerical code. It might work for simple cases, but it may be very wrong for other cases. It may not even be all that accurate even for the simple cases.

Ray

In a nutshell, it is often not optimized for correctness. ;-)

Some of the algorithms have a few serious faults too. And the odd typo and quirky indexing from translation out of the original FORTRAN.

But you get what you deserve if you don't cross check that the answer you get from a computer code is correct.

The references given in the book are still OK, and much of their code only fails on difficult problems. If doesn't work for you then chase up a more advanced text. It is still a pretty good general intro for all its faults. There are much better standard libraries about.

Regards, Martin Brown

The DSP group at Rice University have published Matlab code for solving high order polynomials. I believe last year they published a paper in the IEEE Signal Processing Magazine.

Solving polynomials is a difficult problem due to the numerical sensitivity. Once you find some of the roots you have to deflate the order of the polynomial. It's a similar problem to finding Eigenvalues. So if you want the work you should probably be looking at the BLAS or LINPACK libraries.

Cheers, David

Bob

Jenkins & Traub's "rpoly" code, celebrating its 30th anniversary, is your best choice. You will find it at,

Thanks Bob :)

As I recall the website also has their publications.

Cheers, David