Root Finding

What is it?

We use root finding to find the value(s) such that, for a given function , either:

for a given maximum error

or

for

What do we use it for?

There are some functions with computationally expensive closed-form solutions.  Root-finding methods offer reasonable* approximations without being prohibitively complex.  The trade-off between accuracy and computation time vary between methods, and depending on how well defined the functions are, some methods may not be usable.

*Reasonable varies per application, but most methods can increase accuracy through increased iteration or more exact calculation.

What are some methods we use?

Bisection

Recursively splitting an interval into two pieces, selecting the piece which contains a zero and repeating until maximum error specified error.

Fixed Points

Fixed points are such that .  They are found through iteration, and are applicable to root-finding since has a root at the fixed point .

Newton’s Method

Newton’s method uses a function’s first derivative to approximate an unknown point.  At each iteration, the last functional value is used, along with its derivative, to estimate the value one step away.  This is repeated until (# steps) * = .