Computational methods

1. Introduction

Computational (numerical) methods obtain approximate answers to problems that cannot be solved neatly by algebra. This unit covers the Newton-Raphson method for finding roots of equations, the simplex method for solving two-variable linear programming problems, and the trapezoidal and Simpson's rules for evaluating definite integrals numerically. Each method trades exactness for a controlled, estimable error, and each is judged by its accuracy, its rate of convergence and its efficiency.

---

2. The Newton-Raphson method

To solve $f(x) = 0$, the Newton-Raphson method starts from an initial guess $x_0$ close to a root and improves it by following the tangent to the curve down to the axis. The iteration is

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, \qquad n = 0, 1, 2, \dots,$$

repeated until successive values agree to the required accuracy. The method converges quadratically (the number of correct digits roughly doubles each step) when the guess is close enough and $f'(x_n) \neq 0$, which makes it much faster than the bisection method, though it can fail if the derivative is near zero or the starting value is poor.

Worked example. Find $\sqrt{2}$ by solving $f(x) = x^2 - 2 = 0$, for which $f'(x) = 2x$, so

$$ \begin{aligned} x_{n+1} &= x_n - \frac{x_n^2 - 2}{2x_n} \ &= \frac{1}{2}\left(x_n + \frac{2}{x_n}\right). \end{aligned} $$

Starting from $x_0 = 1.5$,

$$ \begin{aligned} x_1 &= \frac{1}{2}\left(1.5 + \frac{2}{1.5}\right) \ &= 1.41667 \ x_2 &= \frac{1}{2}\left(1.41667 + \frac{2}{1.41667}\right) \ &= 1.41422 \end{aligned} $$

which already matches $\sqrt2 = 1.41421\ldots$ to five decimal places.

---