Revise Numerical solution of equations for Cambridge 9709 (3.6)

Before we can find a root, we need to know roughly where it is. The change-of-sign rule is a simple but fundamental concept for this. If a continuous function $f(x)$ is positive at one point, $x=a$, and negative at another, $x=b$, it must have crossed the x-axis somewhere between $a$ and $b$. This crossing point is a root of the equation $f(x)=0$.

Once we have an interval containing a root, we can use an iterative method to home in on it. This involves rearranging the original equation $f(x)=0$ into the form $x = g(x)$. We then pick a starting value $x_0$ inside our interval and use it to generate a sequence of values: $x_1 = g(x_0)$, $x_2 = g(x_1)$, and so on. If the iteration converges, this sequence will get closer and closer to the actual root.

x_{n+1} = g(x_n)

Not all rearrangements of $f(x)=0$ lead to a convergent iteration. For the sequence to converge to a root $\alpha$, the condition $|g'(\alpha)| < 1$ must be met. This means the gradient of the curve $y=g(x)$ must be less steep than the line $y=x$ near the root. We can visualise this with staircase diagrams (for $0 < g'(x) < 1$) and cobweb diagrams (for $-1 < g'(x) < 0$). If $|g'(x)| > 1$, the iteration will diverge, moving away from the root.

The Newton-Raphson method is another, often much faster, iterative method. It works by using the tangent to the curve $y=f(x)$ at an approximation $x_n$ to find the next, better approximation $x_{n+1}$. The next approximation is where the tangent line intersects the x-axis. This process is repeated until the desired accuracy is achieved.

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$