====================================
Newton's Method
====================================

Root-Finding Problems
++++++++++++++++++++++++++

Given a scalar equation :math:`f(x)=0`, where :math:`f:[a,b]
\rightarrow {\mathbb R}` is a
continuous function, we want to compute its
approximate solutions (i.e. roots of the function :math:`f`).



Iterative Methods
+++++++++++++++++++++++++++

**Definition.** An `iterative method` is a mathematical procedure that 
generates a sequence of improving approximate solutions to a problem. An iterative method starts with an initial approximation,
which is often called an `initial guess`.

**Convergence:** Let :math:`r` be the exact solution to a given root-finding
problem, i.e. :math:`f(r)=0`. Let  :math:`x_0` be the initial guess
and consider a sequence :math:`x_1, x_2, \dotsc, x_n, x_{n+1}, \dotsc`
of improving approximate solutions generated by an iterative method. Consider the absolute
approximation error   :math:`\varepsilon_{n} =
|r-x_n|`. The iterative method is said to be `convergent` for the
given initial guess, if its
corresponding sequence converges to :math:`r`, that is, if :math:`\lim_{n
\rightarrow \infty} \varepsilon_n =0`.

**Linear convergence:** An iterative method is said to be `linearly
convergent` if :math:`\lim_{n
\rightarrow \infty} \frac{\varepsilon_{n+1}}{\varepsilon_{n}} = S
<1`.

**Quadratic convergence:** An iterative method is said to be `quadratically
convergent` if :math:`\lim_{n
\rightarrow \infty} \frac{\varepsilon_{n+1}}{\varepsilon_{n}^2} = M
<\infty`.

**Stopping criterion I:** A stopping criterion tells us when to terminate an iterative
algorithm. Given a small error tolerance :math:`TOL`, a common stopping
criterion is :math:`\varepsilon_n =
|r-x_n| \le TOL`. This will determine the number of iterations
:math:`n` necessary to obtain an approximate solution :math:`x_n` within the error tolerance. Note that in order to use this criterion we will need to know the exact root :math:`r`, which is often not available. The following criteria are hence more practical.
      

**Stopping criterion II:** In most practical root-finding problems we do not have
access to the exact root :math:`r`. In such cases we may consider the
quantity :math:`(E_{\rm abs})_{n} = |x_{n+1}-x_n|`, which
approximates the absolute error :math:`\varepsilon_{n} =
|r-x_{n}|`. The corresponding stopping criterion will then be :math:`(E_{\rm abs})_{n} =
|x_{n+1}-x_n| \le TOL`. Note that this is an acceptable criterion
since it is an indication of the convergence of :math:`x_n`.


**Stopping criterion III:** Usually when :math:`x_n` is a small value,
we may use the approximate relative error in the stopping criterion :math:`(E_{\rm rel})_{n} =
|x_{n+1}-x_n| / |x_{n+1}| \le TOL`.

**Remark.** In addition to an stopping criterion, we also need to set
a limit on the maximum number of steps in case convergence fails.



Newton's Method
+++++++++++++++++++++++++++++++++++++

Newton's method is a simple iterative method for finding roots of
functions. The basic idea behind the method is to approximate the
function with the tangent line and then approximate the root of the
function by the root of the tangent line. 


**Algorithm:** Let :math:`x_0` be an initial guess for a root of :math:`f`. For
:math:`n=0,1, 2, \dotsc` iteratively compute :math:`x_{n+1}` in terms of the just computed :math:`x_n` by: :math:`x_{n+1} = x_n -f(x_n)/f'(x_n)`. Then for most functions and reasonable initial guesses, the sequence converges to a root of :math:`f`.


.. figure:: _static/newton_fig.png
    :width: 400px
    :align: center
    :height: 250px
    :alt: alternate text
    :figclass: align-center

    A demonstration of Newton's method converging to a root of a function.	       

**Convergence:** Let :math:`f` be a twice differentiable function with
a root :math:`r`, i.e. :math:`f(r)=0`. If :math:`f'(r) \neq 0`, then
for a reasonable initial guess (one that is sufficiently close to :math:`r`)
Newton's method is quadratically converging to :math:`r`, with :math:`\lim_{n
\rightarrow \infty} \frac{\varepsilon_{n+1}}{\varepsilon_{n}^2} =
M=\frac{|f"(r)|} {2 \ |f'(r)|} < \infty`.

**Remark.** The convergence of Newton's method will be quadratic if:

1. The initial guess is not too far from the root :math:`r`, or
   equivalently the
   intial error :math:`\varepsilon_0 = |r - x_0|` is not too large.

2. The derivative of :math:`f` at :math:`x_n` (which appears in the
   denominator) is not too close to :math:`0`. This means that the
   function :math:`f` is not too flat at :math:`x_n`, otherwise the
   tangent line would be almost parallel to the :math:`x`-axis and
   would intersect it far away. In particular we need :math:`f'(r)
   \neq 0`.

3. The second derivative of :math:`f` is not too big in absolute value
   near the root. A large second derivative means the function is very
   concave or very convex and hence turns away from the tangent line
   quickly.


Modified Newton's method
+++++++++++++++++++++++++++++++++++++++++

If :math:`r` is a multiple root of the function :math:`f`
with multiplicity :math:`m\ge 2`, that is, if :math:`f(r) = f'(r) =
\dotsc = f^{(m-1)}(r) = 0`, but :math:`f^{(m)}(r) \neq 0`, 
then Newton's method will not converge quadrtically. In this case
Newton's method with be linearly convergent with  :math:`\lim_{n
\rightarrow \infty} \frac{\varepsilon_{n+1}}{\varepsilon_{n}} = S =
\frac{m-1}{m} < 1`.

If the multiplicity :math:`m` of the root is known in advance, it is
possible to modify Newton's method and obtain quadratic
covergence. In this case The modified Newton's method reads :math:`x_{n+1} = x_n -m
f(x_n)/f'(x_n)`.