Newton's Method

Newton's method is an algorithm for finding root of a function $f(x)$ numerically. If $f$ is differentially at a point $x$, then we can use this local information at $x$ to approximate $f$:

This is the tangent line at $x$. We use its intersection with the $x$-axis as the guess of root:

If $f'(x) \neq 0$, then $y = x - \frac{f(x)}{f'(x)}$. Intuitively, $f(x)$ is the height and $f'(x)$ is the slope, hence $\frac{f(x)}{f'(x)} = x - y$ gives the distance between $x$ and $y$. Note that if $f'(x) = 0$, the tangent line does not intersect with $x$-axis.

With a starting point $x_1$, the Newton's Method updates its value iteratively:

Let $z$ be the root of $f$ ($f(z) = 0$). Then under proper condition, $x_n$ converges to $z$ quadratically, that is, $|x_n - z| \le O(2^{-n})$.

Theorem.

Let $f \in C^2$ in some interval $[z \pm c]$ and $f'(x) \neq 0$, $f''(x)$ is bounded for $x \in [z \pm c]$. If $x_0 \in [z \pm c]$, then Newton's Method achieves quadratic convergence.

Proof: By Taylor expansion, $\forall x \in [z \pm c]$, $\exists y$ that lies between $x$ and $z$, such that

Hence

Define $\epsilon_n = (z - x_n)$, and replacing $x$ with $x_n$, we have

Since $f$'s second derivative is continuous, $f''(y)$ is bounded on the closed interval $[z \pm c]$. Further, as $f'(x) \neq 0$, then $\min_{x [z \pm c]} f'(x) > 0$ as $f'(x)$ is continuous on the closed interval $[z \pm c]$. Therefore,

is bounded. Now

If for some $n$ such that $\epsilon_n < 1$, then the number of precise digits doubles for $\epsilon_{n + 1}$.