PHYS 251 - Introduction to Computer Techniques in Physics

Non-Equidistant Interpolation

Lagrange's Formula

Notation: Equation numbers are placed in parentheses, (Eq. 1), at the end of the sentence preceding the mathematical presentation of the equation. They should not be read as if they are part of the sentence. When reference is made to an equation, the word "equation" will be spelled out and not abbreviated. Mathematical symbols are not in all cases precise. Greek symbols will show as such on a Windows operating system, but not a Unix or Mac system.

Non-Equidistant Data Interpolation

The previous discussion of interpolation is predicated on equidistant intervals in the independent variable x. Sometimes it is inconvenient or impossible to obtain function values on an equidistant interval. In such cases, Lagrange's formula can be fashioned to only utilize such data as may be available.

The general form of Lagrange's interpolation formula is given by (Eq. 1)

$p(x)\; =$_j=0Sⁿ { [ _i=0Pⁿ ( x - x_i ) ] / [ ( x - x_j ) _{i=0,i not j}Pⁿ ( x_j - x_i ) ] }

where

$$_i=0Pⁿ ( x - x_i ) = ( x - x₁ ) ( x - x₂ )...( x - x_n )

$$_{i=0,i not j}Pⁿ ( x_j - x_i ) = ( x_j - x₀ )...( x_j - x_i-1 ) ( x_j - x_i+1 )...( x_j - x_n )

We should note that

1. lagrange's formula does not involve successive differences as does Newton's, Stirling's and Bessel's interpolation formulas.
2. Lagrange's formula does involve n+1 successive pairs of variables (x_n,f_n).
3. Although Lagrange's formula works for non-equidistant data, it is not restricted to such a limitation, i.e., it can be applied to equidistant data.
4. If we know rates of change (differences) or rates of rates of change of the function, their neglect is to ignore information.

Cubic Lagrangian Interpolation

Suppose one wishes to construct a cubic polynomial through four successive points of a data set which we will label as (x₁,f₁), (x₂,f₂), (x₃,f₃), and (x₄,f₄). This can be accomplished from our general relation for n+1 points where we can construct the following relation (Eq. 2)

$p(x)\; =\; l$_1,4 f₁ + l_2,4 f₂ + l_3,4 f₃ + l_4,4 f₄

where

$l$_1,4 = [ ( x - x₂ ) ( x - x₃ ) ( x - x₄ ) ] / [ ( x₁ - x₂ ) ( x₁ - x₃ ) ( x₁ - x₄ ) ]

$l$_2,4 = [ ( x - x₁ ) ( x - x₃ ) ( x - x₄ ) ] / [ ( x₂ - x₁ ) ( x₂ - x₃ ) ( x₂ - x₄ ) ]

$l$_3,4 = [ ( x - x₁ ) ( x - x₂ ) ( x - x₄ ) ] / [ ( x₃ - x₁ ) ( x₃ - x₂ ) ( x₃ - x₄ ) ]

$l$_4,4 = [ ( x - x₁ ) ( x - x₂ ) ( x - x₃ ) ] / [ ( x₄ - x₁ ) ( x₄ - x₂ ) ( x₄ - x₃ ) ]

If one wishes, this expression can be written in the form (with a little algebra) as

$p(x)\; =\; ax3+\; bx2+\; cx\; +\; d$

However, from the computational point of view there is no real advantage in doing so.

Example

Find the cubic polynomial whose graph contains the four successive points (0,1), (1,2), (2,0), and (3,-2). Setting x₁ = 0, f₁ = 1, x₂ = 1, f₂ = 2, x₃ = 2, f₃ = 0, and x₄ = 3, f₄ = -2, we can form the values of the ls

$l$_1,4 = [ ( x - x₂ ) ( x - x₃ ) ( x - x₄ ) ] / [ ( x₁ - x₂ ) ( x₁ - x₃ ) ( x₁ - x₄ ) ]
= [ ( x - 1 ) ( x - 2 ) ( x - 3 ) ] / [ ( 0 - 1 ) ( 0 - 2 ) ( 0 - 3 ) ]
= [ ( x - 1 ) ( x - 2 ) ( x - 3 ) ] / - 6

$l$_2,4 = [ ( x - x₁ ) ( x - x₃ ) ( x - x₄ ) ] / [ ( x₂ - x₁ ) ( x₂ - x₃ ) ( x₂ - x₄ ) ]
= [ ( x - 0 ) ( x - 2 ) ( x - 3 ) ] / [ ( 1 - 0 ) ( 1 - 2 ) ( 1 - 3 ) ]
= [ x ( x - 2 ) ( x - 3 ) ] / 2

$l$_3,4 = [ ( x - x₁ ) ( x - x₂ ) ( x - x₄ ) ] / [ ( x₃ - x₁ ) ( x₃ - x₂ ) ( x₃ - x₄ ) ]
= [ ( x - 0 ) ( x - 1 ) ( x - 3 ) ] / [ ( 2 - 0 ) ( 2 - 1 ) ( 2 - 3 ) ]
= [ x ( x - 1 ) ( x - 3 ) ] / - 2

$l$_4,4 = [ ( x - x₁ ) ( x - x₂ ) ( x - x₃ ) ] / [ ( x₄ - x₁ ) ( x₄ - x₂ ) ( x₄ - x₃ ) ]
= [ ( x - 0 ) ( x - 1 ) ( x - 2 ) ] / [ ( 3 - 0 ) ( 3 - 1 ) ( 3 - 2 ) ]
= [ x ( x - 1 ) ( x - 2 ) ] / 6 .

Inserting the values for the ls into Equation 2, we have

$f(x)\; =\; l$_1,4 f₁ + l_2,4 f₂ + l_3,4 f₃ + l_4,4 f₄
= { [ ( x - 1 ) ( x - 2 ) ( x - 3 ) ] / - 6 } 1 + { [ x ( x - 2 ) ( x - 3 ) ] / 2 } 2 + { [ x ( x - 1 ) ( x - 3 ) ] / - 2 } 0 + { [ x ( x - 1 ) ( x - 2 ) ] / 6 } - 2
= (-¹/₆) [ ( x - 1 ) ( x - 2 ) ( x - 3 ) ] + [ x ( x - 2 ) ( x - 3 ) ] + (-¹/₃) [ x ( x - 1 ) ( x - 2 ) ] .

Multiplying out the terms and collecting yields the desired polynomial

$f(x)\; =1/$₂x³ - 3x² + ⁷/₂x + 1 .