Bounds for the Cost of Root Finding

Details Bounds for the Cost of Root Finding Bounds for the Cost of Root Finding

2009-03-21

arxiv.org/abs/0903.3674v2

Mathematics

Numerical Analysis

37 pages, 12 figures

Scientific paper

We analyze a path-lifting algorithm for finding an approximate zero of a complex polynomial, and bound the number of iterates required in several ways: For any polynomial $f\in\PDone$ and appropriate starting value, we bound the number of iterates required to locate an approximate zero. This bound depends only on the value of the function at the initial point, how close the algorithm comes to certain critical values, and the derivative of the polynomial at the root it converges to. For any polynomial $f$, the average number of steps required over all starting values is bounded by a constant times the logarithm of the condition number of $f$. Averaging over all polynomials $f\in\PDone$, the number of steps required for a typical starting value is $\OO(d)$. The analysis of the cost of this algorithm exploits the geometry of the branched Riemann surface for the inverse of a polynomial.

Affiliated with

Also associated with

No associations

Rating

Bounds for the Cost of Root Finding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds for the Cost of Root Finding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds for the Cost of Root Finding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636781