Newton’s Method
This is an incredibly powerful technique for obtaining solutions to equations. Particularly, recall how difficult factoring polynomials was using the techniques of algebra alone. In general, we will be able to factor any polynomial to whatever degree of accuracy with any kind of real root with Newton’s Method.
0. Newton’s Method Note Card
$$x_n = x_{n-1} – \frac{f(x_{n-1})}{f'(x_{n-1})}$$
We need to guaranty that $x_n$ is defined. As such, we need to pick an initial $x_{n-1}$ and we need to be sure, at each step, that $f'(x_{n-1}) \neq 0$.
1. The Motivation
We start with some initial guess $x_0$. Then, to obtain $x_1$ we recall that we could write the linearization of as $f(x) \approx f'(x_0)(x – x_0) + f(x_0)$. Now, we are looking for where $f(x) = 0$ so we rewrite this as $0 \approx f'(x_0)(x – x_0) + f(x_0) \rightarrow x = x_0-\frac{f(x_0)}{f'(x_0)}$. Notice that if $f(x_0) = 0$ then $x = x_0$. Graphically, the iterative process happens as depicted below. We find a starting point and then we move $\frac{f(x_0)}{f'(x_0)}$. This intersects the original curve at a new point and continue along what I will term as the path of steepest descent. This is among the MOST IMPORTANT IDEAS you will come across in calculus. Gradient descent methods underlie most of modern computational mathematics from machine learning to solving difficult partial differential equations.
2. An Example
Consider $f(x) = x^2 – 2$. Let’s pick an initial point $x_0 = 4$. Then, we have:
$x_1 = 4 – \frac{f(4)}{f'(4)}$
$x_1 = 4 – \frac{14}{8} = \frac{9}{4}$
$x_2 = \frac{9}{4} – \frac{f(\frac{9}{4})}{f'(\frac{9}{4})} = \frac{113}{72}$
$x_3 = \frac{113}{72} – \frac{f(\frac{113}{72}}{f'(\frac{113}{72}} = \frac{23137}{16272}$
$x_4 = \frac{1064876737}{752970528} \approx 1.4142…$
This is remarkably close approximation to the actual positive root of this polynomial, $\sqrt{2}$ in only four iterations of Newton’s method.
