Solving equations using linear interpolation

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

An earlier article show 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 start 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.

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

We now find the midpoint of the interval:

$$ m = (a + b) /2 = 1.5 $$

We use this to divide the original interval in half to create 2 intervals $[a, m]$ and $[m, b]$:

The solution of the equation is the point where the curve crosses the x-axis. In this case, the solution is in the lower interval $[1, 1.5]$.

Second iteration

The second iteration starts with the new interval $[1, 1.5]$. Again, we have zoomed in further:

The new midpoint is 1.25:

This time the solution is in the upper interval $[1.25, 1.5]$.

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 the first iteration, we know the values of $a$ and $b$. We can calculate $m$, and then the values of $f(a)$, $f(b)$, and $f(m)$. In this case, $f()$ 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 1.5 -1 2 0.25

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

For the second iteration, we therefore start with $a = 1$, $b = 1.5$ and calculate again:

a b m f(a) f(b) f(m)
1 1.5 1.25 -1 0.25 -0.4375

This time, $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.25$, $b = 1.5$, and so on.

Copyright (c) Axlesoft Ltd 2021