68 COMPUTER AIDED ENGINEERING DESIGN

which is a system of n linear equations in ai,i = 0, ..., n−1, and can be solved by inverting an
n× n matrix. This inversion may prove cumbersome if the number of data points is large. It is possible
to reduce some effort in computation by posing the interpolating polynomial in a slightly different
manner. For example, in the Newton’s divided differences approach, the polynomial is posed as

y≡ p(x) = α 0 +α 1 (x− x 0 )+α 2 (x− x 0 ) (x− x 1 ) + ... + αn− 1 (x− x 0 ) (x− x 1 )... (x− xn− 2 ) (3.3)

so that at the data points, the equations in unknowns αi take the form

y 0 = α 0

y 1 = α 0 + α 1 (x 1 – x 0 )

y 2 = α 0 + α 1 (x 2 – x 0 ) + α 2 (x 2 – x 0 )(x 2 – x 1 )

...
yn–1 = α 0 + α 1 (xn–1 – x 0 ) +... + αn–1(xn–1 – x 0 ) (xn–1 – x 1 )... (xn–1 – xn–2) (3.4)

The unknowns αi can be determined by a series of forward substitutions. Note that α 0 depends only
ony 0 ,α 1 depends on y 0 and y 1 ,α 2 depends on y 0 ,y 1 and y 2 , and so on. If, additionally, a new data
point, (xn,yn) is introduced, an equation is further added with only one unknown αn to be determined,
that is, the addition of a new data point does not alter the previously calculated coefficients. This is
in contrast to the system of equations in (3.2) wherein the addition of a data point requires all the
n + 1 coefficients to be recomputed by inverting an (n + 1) × (n + 1) matrix.
The third possibility in curve interpolation due to Lagrange does not require computing the
coefficients and can be elucidated using the following example. For three data points (x 0 ,y 0 ), (x 1 ,y 1 )
and (x 2 ,y 2 ), consider the expression

Lx

xx xx

(^0) xxxx
2 12
010 2
() =
( – )( – )
( – )( – ) (3.5)
On setting x = x 0 , Lx 02 ()becomes unity, however, for x = x 1 or x 2 , Lx 02 () = 0. Similarly,
Lx
xx xx
(^1) xxxx
2 02
1012
() =
( – )( – )
( – )( – )
is 1 for x = x 1 and 0 for x = x 0 and x = x 2 and that
Lx
xx xx
(^2) xxxx
2 01
2021
() =
( – )( – )
( – )( – )
is 1 for x = x 2 and 0 for x = x 0 and x = x 1. Using the functions
LxLx^20 ( ), ( ) and ( ), 12 Lx^22 which are all quadratic in x (the superscript denotes the degree in x), and
they values, we can construct a quadratic function
Px Lxy Lxy LxyL^2 () =^20 () + 0 21 () + 1 22 () 2 (3.6)
which passes through the three data points. In general, Lxin–1() are termed as Lagrangian interpolation
coefficients where the subscript i signifies that Lxin–1() is the weight of yi in Eq. (3.8). The superscript
n−1 denotes the degree of interpolating polynomial. By inspection from Eq. (3.5) and the related
expressions,Lxni–1() may be written as
Lx
xx xx xx xx
xx xx xx xx
xx
i x
n ii n
iii i i i n jij
n j
i
–1 0–1+1 –1
0–1+1 –1=0
–1
() =
( – )... ( – ) ( – )... ( – )
( – )... ( – )( – )... ( – )

( – )
( –

Π

≠

xxj) (3.7)

The interpolating polynomial then becomes