Solving equations using linear interpolation

By Martin McBride, 2021-04-05
Tags: solving equations linear interpolation
Categories: numerical methods pure mathematics


An earlier article showed how to use interval bisection to solve equations of the form $f(x) = 0$.

In this article we will look at another method, linear interpolation. This involves slightly more calculations per iteration, but it usually converges more quickly so requires less iterations to obtain a result of the required accuracy.

Example problem

We will use the same example that we used to illustrate interval bisection, solving the equation:

$$x^2 - 2 = 0$$

Again we will look for just one of the two solutions, positive $\sqrt 2$.

Linear interpolation starts in a similar way to interval bisection. We sketch a graph of the function and identify a suitable starting interval containing exactly one root:

As before we will start with the interval $[1, 2]$.

The process of linear interpolation proceeds as follows:

  1. Start with an initial interval (1 to 2 in this case).
  2. Use linear interpolation to divide the interval into new intervals.
  3. Determine whether the solution is in the lower interval or the upper interval.
  4. Repeat step two with the selected interval.

Steps 2 to 4 are repeated until a sufficiently accurate result is obtained, as described in the solving equations article. On each pass, the interval width gets smaller, so the approximation becomes more accurate. When the result is accurate enough, the process ends.

A graphical explanation of linear interpolation

To gain an intuitive understanding of the process, we will go through a couple of iterations and show the results on a graph. This is for illustration only, you don't need to draw an accurate graph to use this method.

First iteration

The first iteration starts with an interval $[1, 2]$. Here is the graph where we have zoomed in to the region of interest.

Point A is the point on the curve when $x = 1$. It has coordinates (1, -1).

Point B is the point on the curve when $x = 2$. It has coordinates (2, 2).

Next we draw a line between points A and B (shown in blue below). The point where this line crosses the x-axis is our next guess at the solution.

If the coordinate of point A is $(x_0, y_0)$, and the coordinate of point B is $(x_1, y_1)$, we can calculate the point $x_m$ where the line crosses the x-axis using this formula (see below):

$$ x_m = x_0 - y_0 \frac{x_1 - x_0}{y_1 - y_0} $$

$x_m$ is exactly $4/3$, as shown here:

The solution is in the upper interval $[4/3, 2]$.

Second iteration

The second iteration starts with the new interval $[4/3, 2]$. Again, we have zoomed in further:

The new $x_m$ is 1.4:

This time the solution is still in the upper interval $[1.4, 2]$.

Formula for calculation of xm

How is $x_m$ calculated? Here is a simplified diagram of the points A, B, and M:

We know $(x_0, y_0)$ and $(x_1, y_1)$. We also know that the two triangles (the small red triangle AMD and large blue triangle ABC) are similar by the AA rule:

  • They are both right angled triangles.
  • Angle DAM and CAB are the same angle.

The width and height of the blue triangle ABC are:

$$ AC = x_1 - x_0 $$

$$ CB = y_1 - y_0 $$

The width and height of the red triangle AMD are:

$$ AD = x_m - x_0 $$

$$ DM = 0 - y_0 = -y0 $$

For two similar triangles, the ratio of the lengths of two equivalent sides are the same:

$$ \frac{AD}{DM} = \frac{AC}{CB} $$

So:

$$ \frac{x_m - x_0}{-y0} = \frac{x_1 - x_0}{y_1 - y_0} $$

This can be rearranged to give the earlier result:

$$ x_m = x_0 - y_0 \frac{x_1 - x_0}{y_1 - y_0} $$

Interval bisection by calculation

In the example above, we have relied on the fact that we have a very accurate graph of the function to determine whether the solution is in the first or second half of the interval. But is it possible to determine this by calculation alone. Of course, it is still useful to have an initial sketch graph to find a suitable starting interval.

For each iteration:

  • Start with the current values of $a$ and $b$.
  • Calculate the values of $f(a)$, $f(b)$, and $f(m)$.
  • Calculate $m$ using the formula above.
  • Calculate the value of $f(m)$.
  • Based on the signs of $f(a)$, $f(b)$, and $f(m)$, determine if the solution is in $[a, m]$ or $[m, b]$.
  • Repeat with the new range.

In this case, $f(x)$ is our function:

$$f(x) = x^2 - 2$$

Here is the calculation based on $a = 1$, $b = 2$.

a b m f(a) f(b) f(m)
1 2 4/3 -1 2 -2/9

Notice that $f(b)$ and $f(m)$ have opposite signs. This means that the root must be somewhere between $m$ and $b$.

For the second iteration, we therefore start with $a = 4/3$, $b = 2$ and calculate again:

a b m f(a) f(b) f(m)
4/3 4 1.4 -2/9 2 -0.04

Again, $f(b)$ and $f(m)$ have opposite signs. This means that the root must be somewhere between $m$ and $b$.

For the third iteration, we therefore start with $a = 1.4$, $b = 2$, and so on.

See also



Join the GraphicMaths Newletter

Sign up using this form to receive an email when new content is added:

Popular tags

adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex modulus complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon eigenvalue eigenvector ellipse equilateral triangle euler eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function hyperbolic functions infinity integration by parts integration by substitution interior angle inverse hyperbolic function inverse matrix irrational irregular polygon isosceles trapezium isosceles triangle kite koch curve l system line integral locus maclaurin series major axis matrix matrix algebra mean minor axis nand gate newton raphson method nonagon nor gate normal normal distribution not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule proof pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root sech set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves standard deviation star polygon statistics straight line graphs surface of revolution symmetry tangent tanh transformation transformations trapezium triangle turtle graphics variance vertical volume of revolution xnor gate xor gate