Rating

1. The root of the equation $f(x)=0$ is difficult to solve for directly.

2. It is relatively easy to make an initial guess $x_0$ close to the root.

3. For any $x$ (encountered by the iteration rule described below), the values $f(x)$ and $f'(x)$ are easy to compute.

1. Although the value of $\sqrt{2}$ is common knowledge, we don't have a formula or procedure to compute its value to arbitrary precision.

2. Despite this, we do know that the value is between $1$ and $2$, so we might guess $x_0 = 1$.

3. For any $x$, it is straightforward to compute $$f(x) = x^2 -2$$ and $$f'(x) = 2x.$$

This can be done in several ways. For example, one may use the method of bisection (see the HowDo linked below) to find an interval surrounding the root, or one may sketch the graph to get an idea of the position of the root.

Draw a vertical line intersecting the graph of the function at $P_0 = (x_0, f(x_0))$.

For our example $f(x) = x^2 - 2$, this point is $(1, -1)$.

At $P_0$, draw the tangent line $T_0$ of the function $f$ at $P_0$. The equation of this line is found to be $$y - f(x_0) = f'(x_0)(x - x_0).$$

(To learn how to find the equation of the tangent line, check out our HowDo linked below)

For our example, $x_0 = 1$, $f(x_0) = -1$, and $f'(x_0) = 2$, so the equation becomes $y + 1 = 2(x - 1)$, or, $y = 2x - 3$.

Now we find the x-intercept of the tangent line we've just found in step 2.

In general, we let $y=0$ in the formula to solve for $x_1$. In more detail, we write

$$0 - f(x_0) = f'(x_0) (x_1 - x_0),$$ from which we find $x_1 = x_0 - f(x_0)/f'(x_0)$.

In our example, we find $x_1 = 3/2$.

We see that by performing the above procedure, the new value $x_1$ got closer to the real root of the function. We may perform the operations again and again to improve even further, using the general rule

$$x_{n+1} = x_n - f(x_n)/f'(x_n). $$

This amounts to performing the geometrical operations mentioned above repeatedly.

We compute $f(x_1)$, $f'(x_1)$, and then use the formula $$x_2 = x_1 - f(x_1)/f'(x_1).$$

For our example,

$x_1 = 3/2$,

$f(x_1) = x^2 - 2 = 1/4$,

$f'(x_1) = 2\times(3/2) = 3$, and so

$x_2 = 3/2 - (1/4)/3 = 3/2 - 1/12 = 17/12$, which is about $1.417$. As you can see from the graph, it is now quite close to the real value than the previous guess $x_1$!

We may proceed in exactly the same way from our most current guess $x_n$ to the next guess $x_{n+1}$, by computing $f(x_n)$, $f'(x_n)$ and apply the rule

$$x_{n+1} = x_n - f(x_n)/f'(x_n)$$ to get $x_{n+1}$.

In practice, we do not have to think about the geometric aspect of the procedure. Only three things matter:

1. An initial guess $x_0$

2. The update rule $$x_{n+1} = x_n - f(x_n)/f'(x_n),$$ which allows us to proceed from $x_n$ to $x_{n+1}$.

3. Stop when we believe the approximation is "good enough" (see next card)

If the sequence $x_n$ converges to a definite value, that value is guaranteed to be a root of $f(x)$. There’re two ways to test convergence in practice

1. If $x_n$ does not change much in each update, then it is usually quite close.

2. If $f(x_n)$ becomes very close to zero, then usually $x_n$ is not very far from the root.

In our example of using Newton's method to find the square root of two, the general rule is specialized into

$$x_{n+1} = \frac{1}{2}(x_n + \frac{2}{x_n}).$$

Play around with this and see how fast it improves the guesses!