Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.1
Lecture 12
Data Analysis: Interpolation and
Curve Fitting I
Interpolating Polynomials
IKC-MH.55 Scientific Computing with Python at January 12,
2024
Dr. Cem Özdo
˘
gan
Engineering Sciences Department
˙
Izmir Kâtip Çelebi University
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.2
Contents
1 Interpolation and Curve Fitting
Interpolating Polynomials
Interpolation versus Curve Fitting
Fitting a Polynomial to Data
Lagrangian Polynomials
Neville’s Meth o d
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.3
Interpolation and Curve Fitting I
•
Sines, logarithms, and other nonalgebraic functions from
tables.
•
Those tables had values of the function at uniformly
spaced values of the argument.
•
Most often interpolated linearly:
The value for x = 0.125 was computed as at the
halfway point
between x = 0.12 and x = 0.13.
•
If the function does not vary too rapidly and the tabulated
points are close enough together, this linearly estimated
value would be accurate enough.
•
As a conclusion:
Data can be interpolated to estimate values.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.4
Interpolation and Curve Fitting II
Interpolating Polynomials:
Describes a straightforward but computationally inconvenient
way to fit a polynomial to a set of data points so that an
interpolated value can be computed.
Divided Differences
Spline Curves
Least-S quares Approximations
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.5
Interpolating Polynomials
•
We have a table of x and y -values.
•
Two entries in this table might be
y = 2.36 at x = 0.41 and
y = 3.11 at x = 0.52.
•
If we desire an estimate for y at x = 0.43, we would use
the two table values for that estimate.
•
Why not interpolate as if y(x) was linear between the two
x-values (similar triangles)?
y(0.43) ≈ 2.36 +
2
11
(3.11 − 2.36) = 2.50
where
2
11
=⇒
0.43 − 0.41
0.52 − 0.41
•
We will be most interested in techniques adapted to
situations w here the data are far from linear.
•
The basic principle is to fi t a polynomial curve to the data.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.6
Interpolation versus Curve Fitting
Given a set of data y
i
= f (x
i
) i = 1, . . . , n
obtained from an experiment or from some calculation.
In curve fitting,
the approximating function passes near t he data poin ts, but
(usually) not exactly through them. There is s ome uncertainty.
In interpolati on,
process inherently assumes that the data have no uncertainty.
The interpolation function passes exactly through points.
Figure shows a plot of
some hypothetical
experimental data, a
curve fit function and
interpolating with
piecewise-linear
function.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.7
Fitting a Polynomial to Data I
•
Interpolation involves constr ucting and then evaluating an
interpolating function
.
•
interpolant, y = F (x), determined by requiring that it
pass th rough the known data (x
i
, y
i
).
•
In its mos t general form, interpolation involves
determining the coefficients a
1
, a
2
, . . . , a
n
•
in the linear combination of n basis functions, Φ(x), that
constitute the interpolant
F (x) = a
1
Φ
1
(x) + a
2
Φ
2
(x) + . . . + a
n
Φ
n
(x)
•
such that F(x) = y
i
for i = 1, . . . , n. The basis function
may be polynomial
F (x) = a
1
+ a
2
x + a
3
x
2
+ . . . + a
n
x
n−1
•
or trigonometric
F (x) = a
1
+ a
2
e
ix
+ a
3
e
i2x
+ . . . + a
n
e
i(n−1)x
•
or some other suitable set of functions.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.8
Fitting a Polynomial to Data II
Polynomials are often used for interpolation because they are
easy to evaluate and easy to manipulate analytically.
Table: Fitting
a polynomial
to data.
x f(x)
3.2 22.0
2.7 17.8
1.0 14.2
4.8 38.3
5.6 51.7
•
Suppose that we have a data set.
•
First, we need to select the points that
determine our polynomial.
•
The maximum degree of the polynomial
is always one less than the number of
points.
•
Suppose we choose the fi rst four points.
If the cubic is ax
3
+ bx
2
+ cx + d ,
•
We can write four equations involving the unknown
coefficients a, b, c, and d;
when x = 3.2 ⇒ a(3.2)
3
+ b(3.2)
2
+ c(3.2) + d = 22.0
when x = 2.7 ⇒ a(2.7)
3
+ b(2.7)
2
+ c(2.7) + d = 17.8
when x = 1.0 ⇒ a(1.0)
3
+ b(1.0)
2
+ c(1.0) + d = 14.2
when x = 4.8 ⇒ a(4.8)
3
+ b(4.8)
2
+ c(4.8) + d = 38.3
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.9
Fitting a Polynomial to Data III
•
Solving these equations gives
a = −0.5275
b = 6.4952
c = −16.1177
d = 24.3499
•
and our polynomial is
−0.5275x
3
+ 6.4952x
2
− 16.1177x + 24.3499
•
At x = 3.0, the estimated value is 20.212.
•
if we want a new polynomial that is also made to fit at the
point (5.6, 51.7) ?
•
or if we want to see what difference it would make to use a
quadratic instead of a cubic?
•
Example py-file: Polynomial Interpolation. Gaussian
elimination & back substitution. No pivoting.
myGEshow_interpolation.py
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.10
Fitting a Polynomial to Data IV
1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5
x-data
15
20
25
30
35
y-data
Fitting a Polynomial to Data
Known Data
Interpolation
Figure: Polynomial Interpolation.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.11
Fitting a Polynomial to Data V
Table:
Interpolation
of gasoline prices.
year price
1986 133.5
1988 132.2
1990 138.7
1992 141.5
1994 137.6
1996 144.2
•
Another example;
•
Use the polynomial order 5, why?
P = a
1
+ a
2
y + a
3
y
2
+ a
4
y
3
+ a
5
y
4
+ a
6
y
5
•
Make a guess about the prices of
gasoline at year of 1991 (2011).
•
Example py-file: Interpolation of gasoline prices.
Gaussian elimination & back substitution. No pivoting.
myGEshow_gasoline.py
• Now, try with the shifted dates
(Xdata=Xdata-np.me an(Xdata)).
• Make the necessary corrections for the array A.
• What differs in the plot and why?
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.12
Fitting a Polynomial to Data VI
1986 1987 1988 1989 1990 1991 1992
year
132
134
136
138
140
142
gasoline price, (cents)
Fitting a Polynomial to Data - Gasoline
Known Data
Interpolation
Figure: Polynomial Interpola tion - Gasoline Case.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.13
Lagrangian Polynomials I
•
Straightforward approac h-the Lagrangian polynomial.
•
The s implest way to exhibit the existence of a polynomial
for interpolation with unevenly spaced data.
• Linear interpolation
• Quadratic interpolati on
• Cubic interpolat ion
•
Lagrange polynomials have two important advantages
over interpolating polynomials.
1 the constructi on of the interpolating polynomi als does not
require the solution of a system of equations (such as
Gaussian elimination).
2 the evalua tion of the Lagrange p olynomial s is much less
susceptible to rou ndoff.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.14
Lagrangian Polynomials II
•
Linear int erpo lat ion
P
1
(x) = c
1
x + c
2
•
put the values
y
1
= c
1
x
1
+ c
2
y
2
= c
1
x
2
+ c
2
•
then
c
1
=
y
2
− y
1
x
2
− x
1
c
2
=
y
1
x
2
− y
2
x
1
x
2
− x
1
•
substituting back and rearranging
P
1
(x) = y
1
x − x
2
x
1
− x
2
+ y
2
x − x
1
x
2
− x
1
•
redefining as
P
1
(x) = y
1
L
1
(x) + y
2
L
2
(x)
•
where Ls are the first-degree Lagrange interpolating
polynomials.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.15
Lagrangian Polynomials III
•
Quadratic interpolation
P
2
(x) = y
1
L
1
(x) + y
2
L
2
(x) + y
3
L
3
(x)
where L
s
are not the same with the previous L
s
!
L
1
(x) =
(x − x
2
)(x − x
3
)
(x
1
− x
2
)(x
1
− x
3
)
, L
2
(x) =
(x − x
1
)(x − x
3
)
(x
2
− x
1
)(x
2
− x
3
)
,
L
3
(x) =
(x − x
1
)(x − x
2
)
(x
3
− x
1
)(x
3
− x
2
)
.
•
Cubic interpolation
•
Suppose we have a table of data with four pairs of x- and
f (x)-values, with x
i
indexed by variable i:
i x f(x)
0 x
0
f
0
1 x
1
f
1
2 x
2
f
2
3 x
3
f
3
Through these four data
pairs we can pass a
cubic.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.16
Lagrangian Polynomials IV
•
The Lagrangian for m is
P
3
(x) =
(x − x
1
)(x − x
2
)(x − x
3
)
(x
0
− x
1
)(x
0
− x
2
)(x
0
− x
3
)
f
0
+
(x − x
0
)(x − x
2
)(x − x
3
)
(x
1
− x
0
)(x
1
− x
2
)(x
1
− x
3
)
f
1
+
(x − x
0
)(x − x
1
)(x − x
3
)
(x
2
− x
0
)(x
2
− x
1
)(x
2
− x
3
)
f
2
+
(x − x
0
)(x − x
1
)(x − x
2
)
(x
3
− x
0
)(x
3
− x
1
)(x
3
− x
2
)
f
3
•
This equation is made up of four terms, each of which is a
cubic
in x; hence the sum is a cubic.
•
The pattern of each term is to form the numerator as a
product of linear factors of the form (x − x
i
), omitting one
x
i
in each term.
• The omitted value being used to form the denominator by
replacing x in each of the numerator factors.
• In each term, we multiply by the f
i
.
• It will have n + 1 terms when the degree is n.
•
Fit a cubic through the first four points of the preceding
Table 1 (first four points) and use it to find the interpolated
value for x = 3.0.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.17
Lagrangian Polynomials V
Table:
Fitting
a polynomial
to data.
x f(x)
3.2 22.0
2.7 17.8
1.0 14.2
4.8 38.3
5.6 51.7
P
3
(x) =
(x − 2.7)(x − 1.0)(x − 4.8)
(3.2 − 2.7)(3.2 − 1.0)(3.2 − 4.8)
22.0+
(x − 3.2)(x − 1.0)(x − 4.8)
(2.7 − 3.2)(2.7 − 1.0)(2.7 − 4.8)
17.8+
(x − 3.2)(x − 2.7)(x − 4.8)
(1.0 − 3.2)(1.0 − 2.7)(1.0 − 4.8)
14.2+
(x − 3.2)(x − 2.7)(x − 1.0)
(4.8 − 3.2)(4.8 − 2.7)(4.8 − 1.0)
38.3
•
Carrying out the arithmetic, P
3
(3.0) = 20.21.
•
In general
P
n−1
(x) = y
1
L
1
(x)+y
2
L
2
(x)+. . .+y
n
L
n
(x) =
n
X
j=1
y
j
L
j
(x)
where L
j
(x) =
n
Y
k=1,k 6=j
x − x
k
x
j
− x
k
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.18
Lagrangian Polynomials VI
Example py-file: Interpolation of gasoline prices. Lagrange
Interpolation.
myLagInt_gasoline.py
1986 1987 1988 1989 1990 1991 1992
year
132
134
136
138
140
142
gasoline
price, (cents)
Lagrange Interpolation - Gasoline
Known Data
MyLagInt
SciPy
Figure: Lagrange Polynomial Interpolation - Gasoline Case.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.19
Lagrangian Polynomials VII
•
Error of Int erpo lation; When we fit a polynomial P
n
(x) to
some data points, it will pass exactly through those points
,
• but between those points P
n
(x) will not be precisely the
same as the function f (x) that generated the po ints (unless
the function is that polynomial) .
• How much is P
n
(x) different from f (x)?
• How large is the error of P
n
(x)?
•
It is most important that you never fit a polynomial of a
degree higher than 4 or 5 to a set of points.
•
If you need to fit to a set of more than six points, be sure to
break up the set into subsets
and fit separate polynomials
to these.
•
You cannot fi t a function that is discontinuous or one
whose derivative is discontinuous with a polynomial.
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.20
Neville’s Method I
•
The trouble with the s tandard Lagrangian polynomial
technique is that we d o not know which degree of
polynomial to use.
•
If the degree is t oo low, the int erpolating polynomial does
not give good estimates of f (x).
•
If the degree is t oo high, undesirable os cillations in
polynomial values can occur.
•
Neville’s method can overcome this difficulty.
•
It computes the interpolat ed value with polynomials of
successively
higher degree,
•
stoppin g when the successive values are close t ogether.
•
The s uccessive approximations are actually computed by
linear interpolation from the previous values.
•
The Lagrange formula for linear interpolation to get f (x)
from two data pairs, (x
1
, f
1
) and (x
2
, f
2
), is
f (x) =
(x − x
2
)
(x
1
− x
2
)
f
1
+
(x − x
1
)
(x
2
− x
1
)
f
2
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.21
Neville’s Method II
•
Neville’s method begins by arranging the given data pairs,
(x
i
, f
i
).
•
Such that the successive values are in order of the
closeness of the x
i
to x .
•
Suppose we are given
these data
x f(x)
10.1 0.17537
22.2 0.37784
32.0 0.52992
41.6 0.66393
50.5 0.63608
and we want to
interpolate for x = 27.5.
We first rearrange the data
pairs in order of closeness to
x = 27.5:
i |x-x
i
| x
i
f
i
=P
i0
0 4.5 32.0 0.52992
1 5.3 22.2 0.37784
2 14.1 41.6 0.66393
3 17.4 10.1 0.17537
4 23.0 50.5 0.63608
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.22
Neville’s Method III
•
Neville’s method begins by renaming the f
i
as P
i0
.
•
We build a table
i x P
i0
P
i1
P
i2
P
i3
P
i4
0 32.0 0.52992 0.46009 0.46200 0.46174 0.45754
1 22.2 0.37784 0.45600 0.46071 0.47901
2 41.6 0.66393 0.44524 0.55843
3 10.1 0.17537 0.37379
4 50.5 0.63608
•
Thus, the value of P
01
is computed by
f (x) =
(27.5 − x
1
)
(x
0
− x
1
)
∗ 0.52992 +
(27.5 − x
0
)
(x
1
− x
0
)
∗ 0.37784
substituting all;
P
01
=
(27.5 − 22.2)
(32.0 − 22.2)
∗0.52992 +
(27.5 − 32.0)
(22.2 − 32.0)
∗0.37784 = 0.46009
Data Analysis:
Interpolation and Curve
Fitting I
Dr. Cem Özdo
˘
gan
LOGIK
Interpolation and
Curve Fitting
Interpolating Polynomials
Interpolation versus Curve
Fitting
Fitting a Polynomial to
Data
Lagrangian Polynomials
Neville’s Method
12.23
Neville’s Method IV
•
Once we have the column of P
i1
’s, we compute the next
column.
P
22
=
(27.5 − 41.6) ∗ 0.37379 + (50.5 − 27.5) ∗ 0.44524
50.5 − 41.6
= 0.55843
•
The remaining columns are computed similarly.
•
The general formula for computing entries into the table is
p
i,j
=
(x − x
i
) ∗ P
i+1,j−1
+ (x
i+j
− x) ∗ P
i,j−1
x
i+j
− x
i
•
The top line of the table represents Lagrangian
interpolates at x = 27.5 using polynomials of degree equal
to the s econd subscript of the P
′
s.
i x P
i0
P
i1
P
i2
P
i3
P
i4
0.52992 0.46009 0.46200 0.46174 0.45754
•
The preceding data are for sines of angles in degrees and
the correct value for x = 27.5 is 0.46175.
