Root-finding algorithm: Difference between revisions

Revision as of 17:30, 23 December 2004

Revision as of 16:00, 18 January 2005

Line 7:

==Specific algorithms==

The simplest root-finding algorithm is the [[bisection method]]: we start with two points ''a'' and ''b'' which bracket a root, and at every iteration, we pick either the subinterval [''a'', ''c''] or [''c'', ''b''], where ''c'' = (''a'' + ''b'') / 2 is the midpoint between ''a'' and ''b''. The algorithm always selectselects a subinterval which contains a root. The bisection method is guaranteed to converge to a root, however, its progress is rather slow (the [[rate of convergence]] is linear).

[[Newton's method]], also called the Newton-Raphson method, linearizes the function ''f'' at the current approximation to the root. This yields the [[recurrence relation]]