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.

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:

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

Steps 2 to 4 are repeated, giving a more accurate result each time, until the result is as close as you want it to be.

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.

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).

We draw a line between points **A** and **B** (shown in blue below).

Let's say that the line crosses the x axis at $x = m$, and call the corresponding point on the curve **M**. This is shown here:

In this case, **M** is below the x-axis and **B** is above the x-axis, so the solution must be between **M** and **B**.

For the second iteration, we will set point **A** equal to the previous value of **M**, and repeat the same procedure. Here is the new line **AB**:

And here is the new point **M**:

This time, again, the solution is between **M** and **B**.

An important factor that we conveniently ignored in the description above is how to calculate $m$ from **A** and **B**. Here is a diagram:

Point **A** has an $x$ value of $a$, and similarly point **B** has an $x$ value of $b$.

The two triangles marked 1 and 2 are similar triangles (they are both right angled triangles, and they have the same angle at $m$). This means that their corresponding sides have equal ratios.

Triangle 1 has base $a - m$ and height $f(a)$. Triangle 2 has base $b - m$ and height $f(b)$. Since they are similar, this means that:

$$ \frac {a - m}{b - m} = \frac{f(a)}{f(b)} $$

If we use the substitution:

$$ r = \frac{f(a)}{f(b)} $$

We can solve for $m$:

$$ m = \frac{b.r - a}{r - 1} $$

For the first iteration, we know the values of $a$ and $b$. We can calculate $f(a)$, $f(b)$, then $m$ and $f(m)$.

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

a | b | f(a) | f(b) | m | f(m) |
---|---|---|---|---|---|

1 | 2 | -1 | 2 | 4/3 | -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 | f(a) | f(b) | m | f(m) |
---|---|---|---|---|---|

4/3 | 2 | -2/9 | 2 | 1.4 | -0.04 |

Again, $f(b)$ and $f(m)$ have opposite signs so 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.

Copyright (c) Axlesoft Ltd 2021