GUIDING QUESTION:
How can I compute a solution to an equation?
Geometric motivation. Prime example of a fixed point method.
Motivation
Guiding philosophy:
Dealing with arbitrary functions is hard.
Solving a linear equation is easy! So let's boil down the root finding problem
to solving some linear equations.
You'll soon see that reducing problems to solving linear
equations is a recurring theme in our course!
Motivation
We'll approximate a solution to a non-linear equation (hard)
by iteratively solving a linear equation (easy).
Motivation
Suppose we are given $f$ and we would like to solve $f(x) = 0$. How could
we use a linear equation to approximate a root $p$ of $f$?
Linearize $f$ using a Taylor approximation! When $x = x_n$ is close to $p$,
the graph of $f$
looks a lot like its tangent line at $x_n$, so the point at which the
tangent line crosses the $x$-axis is close to $p$.
This is the basis for our iterative scheme.
Using the Lagrange form of the remainder,
Taylor's theorem implies that if $f$ is twice continuously differentiable on
the interval $I$ between $x = x_n$ and $p$, then for each $x \in I$
there exists a number $\xi \in I$ such that
$$f(x) = \color{var(--emphColor)}{f(x_n) + f'(x_n)(x - x_n)} + {f''(\xi) \over 2}(x - x_n)^2.$$
The tangent line to $f$ at $x = x_n$ omits the second-order remainder
term proportional to $(x_n - x)^2$,
so it is a first-order approximation.
$\pi$ according to Newton
Compute the tangent line at the current iterate and set your
next iterate as the $x$-intercept of the tangent line.
Let's take a closer look
We may compute the tangent line and its zero analytically, thereby obtaining
an explicit relationship between the current iterate and the next.
The tangent line to $f$ at $x = x_n$ is the unique line with slope $f'(x_n)$ containing
$(x_n, f(x_n))$, so it is given by
$y = f(x_n) - f'(x_n)(x- x_n).$
Compare this expression to first terms in Taylor expansion of $f$ around $x = x_n$