BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Mathematics

Interpolation by Intuition

One thing depends on another: a common and easily understood concept. If a train leaves Bristol early in the morning, and arrives in London early in the evening, its location depends upon time of day; we might guess that it would be in Swindon around lunchtime, as Swindon is round about midway between Bristol and London. This estimate is a crude example of the mathematical process known as interpolation.

Interpolation is the determination of an intermediate value of a function, from a number1 of adjacent values, such as the determination of the location of a train using its position at earlier and later times. Interpolation can be performed with quite high accuracy in suitable circumstances, and we shall create an interpolation method using only basic mathematical concepts and a minimum of formulae, by an intuitive process.

A key feature of interpolation is that intermediate values of a function can be determined without knowledge of the precise nature of the function. The technique is applicable to tabulated data values in a considerable number of cases, and is most useful for this reason2.

Mathematical Concepts

We shall make frequent use of the concept of a function, which in turn involves the concept of variables, but neither concept is complicated3.

  • A variable represents a quantity which may have a variety of values, but a specific value in a specific instance. A variable is a convenient notation for any or all such instances.

  • A function encapsulates the idea that one quantity depends upon another. A function provides the value of a dependent variable which is related to another, independent variable. A function may be expressed as a formula, or merely a table of values.

These concepts, and simple arithmetic, are almost all that are required to perform interpolation. The fact that a product of factors is zero whenever any one of the factors is zero, and is one when every factor is one, is also used.

Smooth Variation

There is often a smooth variation of a dependent variable as an independent variable changes. If the train we mentioned above stopped at any stations on its way, its progress would not be smooth. But when variation is smooth, we can expect to perform accurate interpolation. We will now forget the train, and as an ongoing example use the decay of a radioactive substance, having a radiation intensity which is initially 16 but which halves each day. The intensity is also divided by √2 every half day, and so on, as tabulated below.

Day  0  0.51233.54
Intensity1611.31371-8421.41421+1
The values for days 0.5 and 3.5 are intended to be typical examples of values which might be unknown unless produced by interpolation, for instance if the intensity is only measured daily.

The radioactive intensity r after d days is given the formula r = 16 x 2–d, but this formula can be difficult to evaluate, and might even be unknown4, but we do know the intensity varies smoothly as time elapses.

Linear Interpolation

The simplest interpolation method is known as linear interpolation, as it is based on a straight line approximation. This approximation is obtained by assuming that the total change over an interval is produced by a constant rate of change, and using this rate of change pro–rata to find intermediate values. For this reason, the method is also known as interpolation by proportional parts.

Using our example values and focussing on days 0 and 4, the intensity falls from 16 to 1 over 4 days, a rate of change of –3.75 per day. Alternatively, referring to days 0 and 2, the average rate of change is –6 per day, as then the intensity falls from 16 to 4 over 2 days. These approximations obviously differ, and the interpolation results obtained from both of them are tabulated below.

Interpolation based on Days 0 and 4
DayApproximationIntensityError
0  16 16  0
0.5  14.125 11.31371+2.81129
1  12.25   8+4.25
2    8.5   4+4.5
3    4.75   2+2.75
3.5    2.875   1.41421+1.46079
4    1   1  0
Interpolation based on Days 0 and 2
DayApproximationIntensityError
0  16 16  0
0.5  13 11.31371+1.68629
1  10   8+2
2    4   4  0
3  –2   2–4
3.5  –5   1.41421–6.41421
4  –8   1–9

In both cases the results are inaccurate, but do demonstrate several features of interpolation in general5.

  • Intermediate values obtained by interpolation over a short interval are usually more accurate than those obtained from use of a larger interval. (The values for days 0.5 and 1 are more accurate when based on days 0 and 2 than when based on days 0 and 4.)

  • The intermediate values closest to the values upon which the interpolation is based tend to be more accurate. (When based upon days 0 and 4, the value for day 0.5 is more accurate than the value for day 1, and the value for day 3.5 is more accurate than the value for day 3.)

  • The error increases rapidly outside the interval upon which the interpolation is based, and such values are strictly speaking obtained by extrapolation. (The values for days 3, 3.5 and 4 based on days 0 and 2 are grossly inaccurate.)

Weight Functions

Linear interpolation can be performed another way, which is slightly less direct, but gives an insight which may be helpful when more advanced interpolation methods are considered. Instead of working with average rate of change, we instead choose two weight functions, specifically designed to facilitate the interpolation. We shall show how this is done by reworking the interpolation based on days 0 and 2.

The linear function with the value 1 on day 0 and 0 on day 2, will be denoted by L0 = 1 – d / 2. and the linear function with the value 0 on day 0 and 1 on day 2, will be denoted by L2 = d / 2. Remembering that L0 and L2 are both functions, note that the sum aL0 + bL2 gives the value a on day 0, and b on day 2, because L2 is 0 on day 0 and L0 is 0 on day 2. To obtain the required values for days 0 and 2, we need to choose a = 16 and b = 4. The detailed calculations are tabulated below.

Weighted Interpolation based on Days 0 and 2
Day dL0L216L04L2ApproximationIntensityError
0  10  16  0   16 16  0
0.5  0.750.25  12  1   13 11.31371+1.68629
1  0.50.5    8  2   10   8+2
2  01    0  4     4   4  0
3–0.51.5  –8  6   –2   2–4
3.5–0.751.75–12  7   –5   1.41421–6.41421
4–12–16  8   –8   1–9

Thus, using linear weight functions, we have recreated the interpolated values obtained by the direct method.

More Complicated Weight Functions

Postponing their derivation momentarily, we will now use the weight functions Q0 = ( d2 – 6d + 8 ) / 8, Q2 = ( –d2 + 4d ) / 4 and Q4 = ( d2 – 2d ) / 8, forming the sum 16Q0 + 4Q2 + Q4 to obtain approximations based on days 0, 2 and 4. The approximations obtained are tabulated below.

Weighted Interpolation based on days 0, 2 and 4
Day dQ0Q2Q416Q04Q2ApproximationIntensityError
0  10  0 160   16 16  0
0.5  0.656250.4375–0.09375 10.51.75   12.15625 11.31371+0.84254
1  0.3750.75–0.125   63    8.875   8+0.875
2  01  0   04     4   4  0
3–0.1250.75  0.375 –23     1.375   2–0.625
3.5–0.093750.4375  0.65625 –1.51.75     0.90625   1.41421–0.50796
4  00  1   00     1   1  0

This example (hopefully) clarifies the role of the weight functions. For each point of interest, there is a weight function which has the value 1 there, and has the value 0 at all the other points of interest. A suitable multiple of the weight function gives the approximation its intended value at that point, independently of the others, so that as each chosen multiple of a weight function is added, one more function value is faithfully reproduced. When all the weight functions have been used in this way, the resulting approximation is a smooth function6 which is exact at every point of interest.

This more elaborate interpolation, based on three points, has resulted in a considerable reduction in the error at intermediate points. A critical review of the results indicates some anomalies however. Although the errors are lower than either of the linear approximations previously found, the new approximation suggests that the intensity is rising by day 4, since a lower value is given at day 3.5, a behaviour which contradicts physical reality. It is also embarrassing that this more elaborate method gives WORSE approximation than simple linear interpolation over the range 2 to 4 days7. This example does demonstrate further features of interpolation in general, though.

  • The error typically changes sign when passing through one of the points on which the interpolation is based (in this case, the error is positive before day 2, and negative afterward).

  • Non-linear interpolation, that is interpolation based on more than two points, may lead to approximations with oscillatory behaviour (in this case, the rising approximations approaching day 4 are evidence of this).

  • The accuracy is not necessarily improved by taking account of values outside of an interval, particularly if large changes occur outside the interval (here, the linear approximation over days 2 to 4 is not improved by taking account of the value at day 0, although the linear approximation over days 0 to 2 is improved by taking account of the value at day 4).

Although there are many potential dangers when non-linear interpolation is attempted, it is still used, normally over ranges in which the interpolated function exhibits far less variation than our example. We did not expect a straight line to adequately approximate so severe a curve, and to an extent the problems we have noted arise because we are expecting too much of a simple quadratic curve. We will show this with one more example, but first the derivation of weight functions is described

Building Weight Functions

We have described the use of weight functions, indirectly specifying the properties these functions require. To describe how these functions are constructed, we need a good notation8, so that we can refer to a number of different points and a number of different functions in a systematic fashion.

The goal is to interpolate some function so that at n + 1 given different points denoted by x0x1  xn, we obtain the corresponding function values f0f1  fn exactly. These points are usually known as collocation points. It is more convenient to number the collocation points from 0 to n and count them as n + 1 points, because this will result in products of n factors (and polynomials of nth degree). We need to construct a weight function associated with each point in turn, so let's call the weight function Wi when it's associated with the point xi. We will write Wi (x) to emphasise that Wi is a function of x. Although it would be more correct to write Wi (x,x0,x1  xn), this cumbersome form will not be used, because in any particular case it is convenient to think of the collocation points as given constants.

If xj is one of the collocation points, then xi is another collocation point provided i ≠ j. The simple linear term [ x – xj ] is zero if x = xj, and non-zero if x ≠ xj. The modifed linear term [ x – xj ] / [ xi – xj ] in which only x is variable, is 0 when x = xj, but when i ≠ j and x = xi it has the value 1. There are n such terms for each xi, one for each of the other collocation points, and we may form their product. When x = xi, all such factors will have the value 1, and so will the product. When any factor is zero, the product will be zero, and thus for any x = xj if j ≠ i. This is precisely what we require for Wi, which, being a product of n linear terms, will be a polynomial of nth degree.

In the preceding examples of interpolation using weight functions, we have given a formula for each one. Now we will find the cubic weight functions for the collocation points 0, 1, 2 and 3, for use in a final example.

W0 (x) = { [ x – 1 ] / [ 0 – 1 ] } { [ x – 2 ] / [ 0 – 2 ] } { [ x – 3 ] / [ 0 – 3 ] } = –[ x3 – 6x2 + 11x – 6 ] / 6
W1 (x) = { [ x – 0 ] / [ 1 – 0 ] } { [ x – 2 ] / [ 1 – 2 ] } { [ x – 3 ] / [ 1 – 3 ] } = [ x3 – 5x2 + 6x ] / 2
W2 (x) = { [ x – 0 ] / [ 2 – 0 ] } { [ x – 1 ] / [ 2 – 1 ] } { [ x – 3 ] / [ 2 – 3 ] } = –[ x3 – 4x2 + 3x ] / 2
W3 (x) = { [ x – 0 ] / [ 3 – 0 ] } { [ x – 1 ] / [ 3 – 1 ] } { [ x – 2 ] / [ 3 – 2 ] } = [ x3 – 3x2 + 2x ] / 6

For interpolation alone, it is not really necessary to derive these formulae, and in fact the final example was created by a spread sheet, without using the algebraic forms of the weight functions.

Final Interpolation Example

The above formulae for the collocation points 0, 1, 2 and 3 are applied to our radioactive decay example. The tabulated results contain more intermediate values than given before, which unfortunately makes the table rather long. It shows we have at last obtained reasonably accurate interpolation, and gives some indication of how the error varies between collocation points.

Interpolation based on Days 0, 1, 2 and 3
DayW0W1W2W316W08W14W22W3ApproxIntensityError
0  1  0  0  0  16  0    0  0  1616  0
0.1  0.8265  0.2755–0.1305  0.0285  13.224  2.204  –0.522  0.057  14.96314.92853+0.03447
0.2  0.672  0.504–0.224  0.048  10.752  4.032  –0.896  0.096  13.98413.92881+0.05519
0.3  0.5355  0.6885–0.2835  0.0595    8.568  5.508  –1.134  0.119  13.06112.99604+0.06496
0.4  0.416  0.832–0.312  0.064    6.656  6.656  –1.248  0.128  12.19212.12573+0.06627
0.5  0.3125  0.9375–0.3125  0.0625    5  7.5  –1.25  0.125  11.37511.31371+0.06129
0.6  0.224  1.008–0.288  0.056    3.584  8.064  –1.152  0.112  10.60810.55606+0.05194
0.7  0.1495  1.0465–0.2415  0.0455    2.392  8.372  –0.966  0.091    9.889  9.84916+0.03984
0.8  0.088  1.056–0.176  0.032    1.408  8.448  –0.704  0.064    9.216  9.18959+0.02641
0.9  0.0385  1.0395–0.0945  0.0165    0.616  8.316  –0.378  0.033    8.587  8.57419+0.01281
1  0  1  0  0    0  8    0  0    8  8  0
1.1–0.0285  0.9405  0.1045–0.0165  –0.456  7.524    0.418–0.033    7.524  7.46426–0.01126
1.2–0.048  0.864  0.216–0.032  –0.768  6.912    0.864–0.064    6.944  6.9644–0.0204
1.3–0.0595  0.7735  0.3315–0.0455  –0.952  6.188    1.326–0.091    6.471  6.49802–0.02702
1.4–0.064  0.672  0.448–0.056  –1.024  5.376    1.792–0.112    6.032  6.06287–0.03087
1.5–0.0625  0.5625  0.5625–0.0625  –1  4.5    2.25–0.125    5.625  5.65685–0.03185
1.6–0.056  0.448  0.672–0.064  –0.896  3.584    2.688–0.128    5.248  5.27803–0.03003
1.7–0.0455  0.3315  0.7735–0.0595  –0.728  2.652    3.094–0.119    4.899  4.92458–0.02558
1.8–0.032  0.216  0.864–0.048  –0.512  1.728    3.456–0.096    4.576  4.59479–0.01879
1.9–0.0165  0.1045  0.9405–0.0285  –0.264  0.836    3.762–0.057    4.277  4.28709–0.01009
2  0  0  1  0    0  0    4  0    4  4  0
2.1  0.0165–0.0945  1.0395  0.0385    0.264–0.756    4.158  0.077    3.743  3.73213+0.01087
2.2  0.032–0.176  1.056  0.088    0.512–1.408    4.224  0.176    3.504  3.4822+0.0218
2.3  0.0455–0.2415  1.0465  0.1495    0.728–1.932    4.186  0.299    3.281  3.24901+0.03199
2.4  0.056–0.288  1.008  0.224    0.896–2.304    4.032  0.448    3.072  3.03143+0.04057
2.5  0.0625–0.3125  0.9375  0.3125    1–2.5    3.75  0.625    2.875  2.82843+0.04657
2.6  0.064–0.312  0.832  0.416    1.024–2.496    3.328  0.832    2.688  2.63902+0.04898
2.7  0.0595–0.2835  0.6885  0.5355    0.952–2.268    2.754  1.071    2.509  2.46229+0.04671
2.8  0.048–0.224  0.504  0.672    0.768–1.792    2.016  1.344    2.336  2.2974+0.0386
2.9  0.0295–0.1305  0.2755  0.8265    0.456–1.044    1.102  1.653    2.167  2.14355+0.02345
3  0  0  0  1    0  0    0  2    2  2  0
3.1–0.0385  0.1705–0.3255  1.1935  –0.616  1.364  –1.302  2.387    1.833  1.86607–0.03307
3.2–0.088  0.384–0.704  1.408  –1.408  3.072  –2.816  2.816    1.664  1.7411–0.07710
3.3–0.1495  0.6435–1.1385  1.6445  –2.392  5.148  –4.554  3.289    1.491  1.6245–0.1335
3.4–0.224  0.952–1.632  1.904  –3.584  7.616  –6.528  3.808    1.312  1.51572–0.20372
3.5–0.3125  1.3125–2.1875  2.1875  –510.5  –8.75  4.375    1.125  1.41421–0.28921
3.6–0.416  1.728–2.808  2.496  –6.65613.824–11.23  4.992    0.928  1.31951–0.39151
3.7–0.5355  2.2015–3.4965  2.8305  –8.56817.612–13.99  5.661    0.719  1.23114–0.51214
3.8–0.672  2.736–4.256  3.192–10.7521.888–17.02  6.384    0.496  1.1487–0.6527
3.9–0.8265  3.3345–5.0895  3.5815–13.2226.676–20.36  7.163    0.257  1.07177–0.81477
4–1  4–6  4–1632–24  8    0  1–1

The interpolation produced in this case is much more successful. The oscillatory behaviour has gone, and the approximations are now much more accurate than before. Notice, however, that the accuracy is reasonable only within the range of the collocation points - the error grows rapidly outside that range, so that extrapolation is still a risky business.

Practical Considerations

It must be emphasised that this method of interpolation should only be used when the approximated function is known to be smooth, and when the function values at the collocation points are known to be accurate. The following points should be borne in mind.

  • The function to be interpolated must be smooth. Interpolation by this method should not be attempted near an exceptional value (for example, to interpolate a table of reciprocals near the origin).
  • It cannot increase the accuracy beyond that of the tabulated values.

  • It is unsuitable if the base data is influenced by statistical variation, and will tend to amplify 'noise' if used.

It has been mentioned that the interpolation can be performed by a spreadsheet program. The following tips are offered for such an implementation.

  • Generate the weight functions individually. The zero and one values that these must have at the collocation points provide an easy and useful check.

  • Little purpose is served by tabulating the individual multiples of the weight functions. The reproduction of table values at the collocation points furnishes an easy check of the sum of multiples of the weight functions.

  • It is relatively easy to interpolate given data in more than one way, so that approximations can be compared for the purpose of error estimation (for example, cubic interpolation using collocation points 0, 1, 2 and 3 could be compared with cubic interpolation using collocation points 1, 2, 3 and 4, or quartic interpolation based on 0, 1, 2, 3 and 4).

Summary

The interpolation method developed here is the foundation of many techniques of numerical mathematics. In fact, it is a simple interpretation of the famous Lagrange Interpolation formula. A major factor in its widespread use is its generality; it can be used with functions of unknown form, tabulated at irregular intervals, and is relatively easy to compute.

Using ever-higher orders of interpolation formula can be compared with using ever greater numbers of terms in an infinite series. A series is usually developed in the vicinity of a point, whereas interpolation immediately applies to a definite range, and approximates over the whole of that range.

The exposition above has concentrated on finding intermediate values. Instead, the focus could have been on finding the coefficients of the polynomials. Simple transformations of these coefficients would then enable either derivatives or integrals to be approximated.

There are other methods of interpolation, notably those based on the trigonometric functions, which are closely related to Fourier series. There are even other methods of polynomial interpolation, based on least-square curve fitting, or families of orthogonal polynomials. The method given here can be expressed in a variety of forms of equivalent forms, producing exactly the same results but organising the calculations very differently.


1 The number must be two or more.
2 It can be used for other purposes too. It enables tabulated values to be described by a formula, which can then be manipulated to provide, for example, approximate derivatives and integrals.
3 Much of mathematics is devoted to elaboration upon these concepts.
4 The formula has been chosen because exact polynomial interpolation is impossible.
5 Examples which invalidate these observations can be constructed.
6 A finite sum of smooth functions is always a smooth function.
7 Performing this linear interpolation is left as a simple exercise.
8 There is more notation than mathematics here.

Discuss this Entry  People have been talking about this Guide Entry. Here are the most recent Conversations:

Invisible Table Headers in Brunel
(Last Posting: Apr 6, 2004)




Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A2163151 (Edited)

Written and Researched by:
Old Hairy

Edited by:
Wildman - I'm not really mad, I've just been in a very bad mood for 40 years!


Date: 05   April   2004


Text only
Like this page?
Send it to a friend


Related BBC Pages
Figure it out
5 Numbers


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy