6.4 Linear Systems 185
f(xi)≈a 0 +a 1 xi+a 2 x^2 i+···+anxni.We can then obtain the unknown coefficients by rewriting our problem as
1 x 0 x^20 ... ...xn 0
1 x 1 x^21 ... ...xn 1
1 x 2 x^22 ... ...xn 2
1 x 3 x^23 ... ...xn 31 xn x^2 n... ...xnn
a 0
a 1
a 2
a 3an
=
f(x 0 )
f(x 1 )
f(x 2 )
f(x 3 )f(xn)
,
an expression which can be rewritten in a more compact form as
Xa=f,with
X=
1 x 0 x^20 ... ...xn 0
1 x 1 x^21 ... ...xn 1
1 x 2 x^22 ... ...xn 2
1 x 3 x^23 ... ...xn 31 xn x^2 n... ...xnn
This matrix is called a Vandermonde matrix and is by definition non-singular since all points
xiare different. The inverse exists and we can obtain the unknown coefficients by inverting
X, resulting in
a=X−^1 f.
Although this algorithm for obtaining an interpolating polynomial which approximates our
data set looks very simple, it is an inefficient algorithm since the computation of the inverse
requiresO(n^3 )flops. The methods we discussed in chapter 3, together with spline interpola-
tion discussed in the next section, are much more effective from a numerical point of view.
There is also another subtle point. Although we have a data set withn+ 1 points, this does
not necessarily mean that our functionf(x)is well represented by a polynomial of degreen.
On the contrary, our functionf(x)may be a parabola (second-order inn), meaning that we
have a large excess of data points. In such cases a least-square fit or a spline interpolation
may be better approaches to represent the function. Spline interpolation will be discussed in
the next section.
6.4.5 Tridiagonal Systems of Linear Equations.
We start with the linear set of equations from Eq. (6.15), viz
Au=f,whereAis a tridiagonal matrix which we rewrite as
A=
b 1 c 1 0 ... ... ...
a 2 b 2 c 2 ... ... ...
a 3 b 3 c 3 ... ...
... ... ... ... ...
an− 2 bn− 1 cn− 1
an− 1 bn