Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.1
Lecture 13
Data Analysis: Interpolation and
Curve Fitting II
Millikan Oil-Drop Experiment
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 II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.2
Contents
1 Divided Differences
2 Spline Curves
The Equation for a Cubic Spline
3 Least-Squares Approximations
Nonlinear Data (Curve Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.3
Interpolation and Cu rve Fitting II
Divided Differences
These provide a more efficient way to construct an
interpolating polynomial, one that allows one to readily change
the degree of the polynomiall.
Spline Curves
Using special polynomials, splines, one can fit polynomials to
data more accurately than with an inter polating polynomial. At
the expense of added computational effort, some important
problems that one has with interpolating polynomials is
overcome.
Least-S quares Approximat ions
Least-Squares Approximations are methods by which
polynomials and other functions can be fitted to data that are
subject to errors likely in experiments. These approximations
are widely used to analyze experimental observations.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.4
Divided Differences I
•
There are two disadvantages to using the Lagrangian
polynomial or Neville’s method for interpolation.
1 It involves more arithmetic operations than does t he
divided-difference method.
2 More importantly, if we d esire to add or subtract a point from
the set used to construct the polynomial, we essentially
have to start over
in the computati ons.
•
Both the Lagrangian polynomials and Neville’s method
also must repeat all of the arithmetic if we must interpolate
at a new x-value.
•
The divided-difference method avoids all of this
computation.
•
Actually, we will not get a polynomial different from that
obtained by Lagrange’s technique.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.5
Divided Differences II
•
Every n
th
-degree polynomial that passes through the
same n + 1 points is identical
.
•
Only the way that the polynomial is expressed is different.
The function, f (x ), is known at several
values for x :
x
0
f
0
x
1
f
1
x
2
f
2
x
3
f
3
•
We do not as sume that the x ’s are evenly spaced or even
that the values are arranged in any particular order.
•
Consider the n
th
-degree polynomial written as:
P
n
(x) = a
0
+(x−x
0
)a
1
+(x−x
0
)(x−x
1
)a
2
+(x−x
0
)(x−x
1
) . . . (x−x
n−1
)a
n
•
If we chose the a
i
’s so that P
n
(x) = f (x ) at the n + 1
known points, then P
n
(x) is an interpolating polynomial.
•
The a
i
’s are readily determined by using what are called
the divided differences of the tabulated values.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.6
Divided Differences III
•
A special standard notation for divided differences is
f [x
0
, x
1
] =
f
1
− f
0
x
1
− x
0
called the first divided difference between x
0
and x
1
.
•
And, f [x
0
] = f
0
= f (x
0
) (zero-order difference).
f [x
s
] = f
s
•
Second- and higher-order differences are defined in terms
of lower-order differences.
f [x
0
, x
1
, x
2
] =
f [x
1
, x
2
] − f [x
0
, x
1
]
x
2
− x
0
•
For n-terms,
f [x
0
, x
1
, . . . , x
n
] =
f [x
1
, x
2
, . . . , f
n
] − f [x
0
, x
1
, . . . , f
n−1
]
x
n
− x
0
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.7
Divided Differences IV
Using the standard notation, a divided-difference table is
shown in symbolic form in Table 1.
x
i
f
i
f [x
i
, x
i+1
] f [x
i
, x
i+1
, x
i+2
] f [x
i
, x
i+1
, x
i+2
, x
i+3
]
x
0
f
0
f [x
0
, x
1
] f [x
0
, x
1
, x
2
] f [x
0
, x
1
, x
2
, x
3
]
x
1
f
1
f [x
1
, x
2
] f [x
1
, x
2
, x
3
] f [x
1
, x
2
, x
3
, x
4
]
x
2
f
2
f [x
2
, x
3
] f [x
2
, x
3
, x
4
]
x
3
f
3
f [x
3
, x
4
]
Table : Divided-difference table in symbolic form.
x
i
f
i
f [x
i
, x
i+1
] f [x
i
, x
i+1
, x
i+2
] f [x
i
, . . . , x
i+3
] f [x
i
, . . . , x
i+4
]
3.2 22.0 8.400 2.856 -0.528 0.256
2.7 17.8 2.118 2.012 0.0865
1.0 14.2 6.342 2.263
4.8 38.3 16.750
5.6 51.7
Table : Divided-difference table in numerical values.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.8
Divided Differences V
•
Table 8 shows specific numerical values.
f [x
0
, x
1
] =
f
1
− f
0
x
1
− x
0
=
17.8 − 22.0
2.7 − 3.2
= 8.4
f [x
1
, x
2
] =
f
2
− f
1
x
2
− x
1
=
14.2 − 17.8
1.0 − 2.7
= 2.1176
f [x
0
, x
1
, x
2
] =
f [x
1
, x
2
] − f [x
0
, x
1
]
x
2
− x
0
=
2.1176 − 8.4
1.0 − 3.2
= 2.8556
and the others..
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.9
Divided Differences VI
x = x
0
: P
0
(x
0
) = a
0
x = x
1
: P
1
(x
1
) = a
0
+ (x
1
− x
0
)a
1
x = x
2
: P
2
(x
2
) = a
0
+ (x
2
− x
0
)a
1
+ (x
2
− x
0
)(x
2
− x
1
)a
2
.
.
.
.
.
.
x = x
n
: P
n
(x
n
) = a
0
+ (x
n
− x
0
)a
1
+ (x
n
− x
0
)(x
n
− x
1
)a
2
+ . . .
+(x
n
− x
0
) . . . (x
n
− x
n−1
)a
n
•
If P
n
(x) is to be an interpolating polynomial, it must match
the table for all n + 1 entries:
P
n
(x
i
) = f
i
for i = 0, 1, 2, . . . , n.
•
Each P
n
(x
i
) will equal f
i
, if a
i
= f [x
0
, x
1
, . . . , x
i
]. We then
can write:
P
n
(x) = f [x
0
] + (x − x
0
)f [x
0
, x
1
] + (x − x
0
)(x − x
1
)f [x
0
, x
1
, x
2
]
+(x − x
0
)(x − x
1
)(x − x
2
)f [x
0
, . . . , x
3
]
+(x − x
0
)(x − x
1
) . . . (x − x
n−1
)f [x
0
, . . . , x
n
]
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.10
Divided Differences VII
•
Write interpolating polynomial of degree-3 that fits the data
of Table 8 at all points x
0
= 3.2 to x
3
= 4.8.
P
3
(x) = 22.0 + 8.400(x − 3.2) + 2.856(x − 3.2)(x − 2.7)
−0.528(x − 3.2)(x − 2.7)(x − 1.0)
•
What is the fourth-degree polynomial that fits at all five
points?
•
We only have to add one more term to P
3
(x)
P
4
(x) = P
3
(x) + 0.2568(x − 3.2)(x − 2.7)(x − 1.0)(x − 4.8)
•
If we compute the interpolated value at x = 3.0, we get the
same result: P
3
(3.0) = 20.2120.
•
This is not surprising, because all third-degree
polynomials that pass through the same four points
are identical.
•
They may look different but they can all be reduced to
the same form.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.11
Divided Differences VIII
Example py-file: Constructs a table of divided-difference
coefficients. Diagonal entries are coefficients of the
polynomial. mydivDiffTable_interpolation.py
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.12
Divided Differences IX
•
Divided differences for a polynomial
•
It is of interest to look at the divided differences for
f (x) = P
n
(x).
•
Suppose that f (x ) is the cubic
f (x) = 2x
3
− x
2
+ x − 1.
•
Here is its divided-difference table:
x
i
f [x
i
] f [x
i
, x
i+1
] f [x
i
, x
i+1
f [x
i
, . . . f [x
i
, . . . f[x
i
, . . .
, x
i+2
] , x
i+3
] , x
i+4
] , x
i+5
]
0.30 -0.736 2.480 3.000 2.000 0.000 0.000
1.00 1.000 3.680 3.600 2.000 0.000
0.70 -0.104 2.240 5.400 2.000
0.60 -0.328 8.720 8.200
1.90 11.008 21.020
2.10 15.212
Table : Divided-difference table in numerical values for a polynomial.
•
Observe that the third divided differences are all the same.
•
It then follows that all higher divided differences will be
zero.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.13
Divided Differences X
P
3
(x) = f [x
0
] + (x − x
0
)f [x
0
, x
1
] + (x − x
0
)(x − x
1
)f [x
0
, x
1
, x
2
]
+(x − x
0
)(x − x
1
)(x − x
2
)f [x
0
, x
1
, x
2
, x
3
]
1 i m port numpy as np
2 D=np . a rray ( [ [ − 0.73 6] , [ 2 . 4 8 0 ] , [ 3 . 0 0 0 ] , [ 2 . 0 0 0 ] ] )
3 p r i n t ( np . transpose (D) )
4 # [[ − 0.736 2.48 3. 2. ] ]
5 impo rt sympy as sym
6 x = sym. Symbol ( ’ x ’ )
7 P3=D[ 0 ] + ( x− 0.3)
*
D[ 1 ] + ( x − 0.3)
*
( x−1)
*
D[ 2 ] + ( x− 0.3)
*
( x−1)
*
( x − 0.7)
*
D[ 3 ]
8 p r i n t ( P3)
9 # [2. 4 8
*
x + 2 . 0
*
( x − 1)
*
( x − 0. 7 )
*
( x − 0 .3 ) + 3 . 0
*
( x − 1)
*
( x −
0. 3 ) − 1. 4 8]
10 p r i n t ( sym . expand ( 2 . 48
*
x + 2 . 0
*
( x − 1)
*
( x − 0. 7 )
*
( x − 0 .3 ) + 3 . 0
*
( x
− 1)
*
( x − 0 .3 ) − 1. 48) )
11 # 2.0
*
x
**
3 − 1.0
*
x
**
2 + 1.0
*
x − 1.0
which is same with the starting polynomial.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.14
Spline Curves I
Figure: Fitting with different degrees of the polynomial.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.15
Spline Curves II
•
There are times when fitting an interpolating polynomial to
data points is very difficult.
•
Figure 1a is plot of f (x) = cos
10
(x) on the interval [−2, 2].
•
It is a nice, smooth curve but has a pronounced maximum
at x = 0 and is near to the x-axis for |x| > 1.
•
The curves of Figure 1b,c, d, and e are for polynomials of
degrees −2, −4, −6, and −8 that match the function at
evenly spaced points.
•
None of the polynomials is a good representation of
the function.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.16
Spline Curves III
Figure: Fitting with quadratic in subinterval.
•
One might think that a solution to the problem would be
to break up the interval [−2, 2] into subintervals
•
and fit separate polynomials to the function in these
smaller intervals.
•
Figure 2 shows a much better fit if we use a quadratic
between x = −0.65 and x = 0.65 and with P(x) = 0
outside that interval.
•
That is better but there are discontinuities in the slope
where the separate polynomials join.
•
This solution is known as spline curves.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.17
Spline Curves IV
•
Suppose that we have a set of n + 1 points (which do not
have to be evenly spaced):
(x
i
, y
i
), with i = 0, 1, 2, . . . , n.
•
A spline fits a set of n
th
-degree polynomials, g
i
(x),
between each pair of points, from x
i
to x
i+1
.
•
The points at which the splines join are called knots.
Figure: Linear spline.
•
If the polynomials are all of degree 1, we have a linear
spline and the curve would appear as in the Fig. 3.
•
The slopes are discontinuous where the segments
join.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.18
The Equation for a Cubic Spline I
Figure: Cubic spline.
•
We will create a succession of cubic splines over
success ive intervals of the data (See Fig. 4).
•
Each spline must join with its neighbouring cubic
polynomials at the knots where they join with the same
slope and curvature.
•
We write the equation for a cubic polynomial, g
i
(x), in
the i
th
interval, between points (x
i
, y
i
), (x
i+1
, y
i+1
) (solid
line).
•
It has this equation:
g
i
(x) = a
i
(x − x
i
)
3
+ b
i
(x − x
i
)
2
+ c
i
(x − x
i
) + d
i
•
The dashed curves are other cubic spline polynomials.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.19
The Equation for a Cubic Spline II
•
Thus, the cubic spline function is of the form
g(x) = g
i
(x) on the interval[x
i
, x
i+1
], for i = 0, 1, . . . , n − 1
•
and meets these conditions:
g
i
(x
i
) = y
i
, i = 0, 1, . . . , n − 1 and g
n−1
(x
n
) = y
n
(1)
g
i
(x
i+1
) = g
i+1
(x
i+1
), i = 0, 1, . . . , n − 2 (2)
g
′
i
(x
i+1
) = g
′
i+1
(x
i+1
), i = 0, 1, . . . , n − 2 (3)
g
′′
i
(x
i+1
) = g
′′
i+1
(x
i+1
), i = 0, 1, . . . , n − 2 (4)
•
Equations say that the cubic spline fits to each of the
points Eq. 1, is continuous Eq. 2, and is continuous in
slope and curvature Eq. 3 and Eq. 4, throughout the
region spanned by the points.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.20
Least-Squares Approximations I
•
Until now, we have assumed that the data are accurate,
•
but when these values are derived from an experiment,
there is some error in the measurements.
Figure: Resistance vs Temperature
graph for the Least-Squares
Approximation.
•
Some students are
assigned to find the effect
of temperature on the
resistance of a metal wire.
•
They have recorded the
temperature and resistance
values in a table and have
plotted their findings, as
seen in Fig.
5.
•
The graph suggest a
linear relationship.
R = aT + b
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.21
Least-Squares Approximations II
•
Values for the parameters, a & b, can be obtained from the
plot.
•
If someone else were given same data and asked to draw
the line,
•
it is not likely that they would draw exactly the same line
and they would get differ ent values for a & b.
•
A way of fitting a line to experimental data that is to
minimize the deviations of the points from the line.
•
The usual method for doing this is called the
least-squares method.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.22
Least-Squares Approximations III
•
The deviations are determined by the distances between
the points and the line.
Figure: Minimizing the deviations
by making the sum a minimum.
•
Consider the case of only two
points (See Fig.
6).
•
Obviously, the best line
passes through each point,
•
but any line that passes
through the midpoint of the
segment connecting them has
a sum of errors equal to zero.
•
We might first suppose we could minimize the deviations
by making their sum a minimum
, but this is not an
adequate criterion.
•
We might ac cept the criterion that we make the magnitude
of the maximum err or a minimum (the so-called minimax
criterion).
•
The usual criterion is to minimize the sum of the squares
of the errors, the least-squares principle.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.23
Least-Squares Approximations IV
•
Let Y
i
represent an experimental value, and let y
i
be a
value from the equation
y
i
= ax
i
+ b
where x
i
is a particular value of the variable assumed to
be free of error.
•
We wish to determine the best values for a & b so that the
y’s predict the function values that correspond to x-values.
•
Let errors defined by e
i
= Y
i
− y
i
= Y
i
− (ax
i
+ b )
•
The least-squares criterion requires that S be a minimum.
S = e
2
1
+ e
2
2
+ . . . + e
2
n
=
P
N
i=1
e
2
i
=
P
N
i=1
(Y
i
− ax
i
− b )
2
N is the number of (x, Y )-pairs.
•
We reach the minimum by proper choice of the parameters
a & b, so they are the variables of the problem.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.24
Least-Squares Approximations V
•
At a minimum for S, the two partial derivatives will be zero.
∂S/∂a & ∂S/∂b
•
Remembering that the x
i
and Y
i
are data points unaffected
by our choice our values for a and b, we have
∂S
∂a
= 0 =
P
N
i=1
2(Y
i
− ax
i
− b )(− x
i
)
∂S
∂b
= 0 =
P
N
i=1
2(Y
i
− ax
i
− b )(− 1)
•
Dividing each of these equations by −2 and expanding the
summation, we get the so-called normal equations
a
P
x
2
i
+ b
P
x
i
=
P
x
i
Y
i
a
P
x
i
+ bN =
P
Y
i
From i = 1 to i = N.
•
Solving these equations simultaneously gives the values
for slope and intercept a & b.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.25
Least-Squares Approximations VI
•
For the data in Fig. 5 we find that
N = 5,
X
T
i
= 273.1,
X
T
2
i
= 18607.27,
X
R
i
= 4438,
X
T
i
R
i
= 254932.5
•
Our normal equations are then
18607.27a + 273 .1b = 254932.5
273.1a + 5b = 4438
•
From these we find a = 3.395, b = 702.2, and
R = 702.2 + 3.395T
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.26
Least-Squares Approximations VII
•
In many cases, data from experimental tests are not linear,
so we need to fit to them some function other than a
first-degree polynomial.
•
Popular forms are the exponential form
y = ax
b
or y = ae
bx
•
The exponential forms are usually linearized by taking
logarithms before determining the parameters, for the
case y = ax
b
:
lny = lna + blnx or lny = lna + bx
•
We now fit the new variable z = lny as a linear function of
lnx or x as described earlier.
•
Here we do not minimize the sum of s quares of the
deviations of Y from the curve, but rather the deviations of
lnY .
•
In effect, this amounts to minimizing the squares of the
percentage errors, which itself may be a desirable feature.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.27
Least-Squares Approximations VIII
•
Because polynomials can be r eadily manipulated, fitting
such functions to data that do not plot linearly is c ommon.
•
We assume the functional relationship
y = a
0
+ a
1
x + a
2
x
2
+ . . . + a
n
x
n
(5)
with errors defined by
e
i
= Y
i
− y
i
= Y
i
− (a
0
+ a
1
x + a
2
x
2
+ . . . + a
n
x
n
)
•
We again use Y
i
to represent the observed or
experimental value corresponding to x
i
, with x
i
free of
error.
•
We minimize the sum of squares;
S =
N
X
i=1
e
2
i
=
N
X
i=1
(Y
i
− a
0
− a
1
x − a
2
x
2
− . . . − a
n
x
n
)
2
At the minimum, all the partial derivatives ∂S/∂a
0
, ∂S/∂a
n
vanish.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.28
Least-Squares Approximations IX
•
Writing the equations for these gives n + 1 equations:
∂S
∂a
0
= 0 =
P
N
i=1
2(Y
i
− a
0
− a
1
x
i
− a
2
x
2
i
− . . . − a
i
x
n
i
)(−1)
∂S
∂a
1
= 0 =
P
N
i=1
2(Y
i
− a
0
− a
1
x
i
− a
2
x
2
i
− . . . − a
i
x
n
i
)(−x
i
)
.
.
.
∂S
∂a
n
= 0 =
P
N
i=1
2(Y
i
− a
0
− a
1
x
i
− a
2
x
2
i
− . . . − a
i
x
n
i
)(−x
n
i
)
•
Dividing each by −2 and rearranging gives the n + 1
normal equations to be solved simultaneously:
a
0
N + a
1
P
x
i
+ a
2
P
x
2
i
+ . . . + a
n
P
x
n
i
=
P
Y
i
a
0
P
x
i
+ a
1
P
x
2
i
+ a
2
P
x
3
i
+ . . . + a
n
P
x
n+1
i
=
P
x
i
Y
i
a
0
P
x
2
i
+ a
1
P
x
3
i
+ a
2
P
x
4
i
+ . . . + a
n
P
x
n+2
i
=
P
x
2
i
Y
i
.
.
.
a
0
P
x
n
i
+ a
1
P
x
n+1
i
+ a
2
P
x
n+2
i
+ . . . + a
n
P
x
2n
i
=
P
x
n
i
Y
i
(6)
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.29
Least-Squares Approximations X
•
Putting these equations in matrix form shows the
coefficient matrix;
N
P
x
i
P
x
2
i
P
x
3
i
. . .
P
x
n
i
P
x
i
P
x
2
i
P
x
3
i
P
x
4
i
. . .
P
x
n+1
i
P
x
2
i
P
x
3
i
P
x
4
i
P
x
5
i
. . .
P
x
n+2
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
P
x
n
i
P
x
n+1
i
P
x
n+2
i
P
x
n+3
i
. . .
P
x
2n
i
[a] =
P
Y
i
P
x
i
Y
i
P
x
2
i
Y
i
.
.
.
P
x
n
i
Y
i
(7)
All the summatins in Eqs.
6 and 7 run from 1 to N. We will
let B stand for the coeffic ient matrix.
•
Equation 7 represents a linear system.
•
Degrees higher than 4 are used very infrequently. It is
often better to fit a series of lower-degree polynomials to
subsets of the data.
•
Matrix B of Eq. 7 is called the normal matrix for the
least-squares problem.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.30
Least-Squares Approximations XI
•
There is another matrix that corres ponds to this, called the
design matrix. It is of the form;
A =
1 1 1 1 1
x
1
x
2
x
3
. . . x
N
x
2
1
x
2
2
x
2
3
. . . x
2
N
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
n
1
x
n
2
x
n
3
. . . x
n
N
•
AA
T
is just the coefficient matrix of Eq. 7. It is easy to see
that Ay , where y is the column vector of Y -values, gives
the right-hand side of Eq.
7. We can rewrite Eq. 7 in
matrix form, as
AA
T
a = Ba = Ay
so it is to find the solution.
•
It is illustrated the use of Eq. 6 to fit a quadratic to the data
of Table 4. Figure 7 shows a plot of the data.
•
The data are actually a perturbation of the relation
y = 1 − x + 0.2x
2
.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.31
Least-Squares Approximations XII
To set up the normal equations, we
need the sums tabulated in Table
4.
Table : Data to illustrate curve fitting.
Figure: Figure for
the data to illustrate
curve fitting.
•
The equations to be solved are:
11a
0
+ 6.01a
1
+ 4.6545a
2
= 5.905
6.01a
0
+ 4.6545a
1
+ 4.1150a
2
= 2.1839
4.6545a
0
+ 4.1150a
1
+ 3.9161a
2
= 1.3357
The result is a
0
= 0.998, a
2
= −1.018, a
3
= 0.225.
•
So the least- squares method gives
y = 0.998 − 1.018x + 0.225x
2
which we compare to y = 1 − x + 0.2x
2
. Errors in the data
cause the equations to differ.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.32
Least-Squares Approximations XIV
Example py-file: Fitting an 4
th
order polynomial to y = cosx
function in [0,π] by Least-Square Approximation. Gaussian
elimination & back substitution. Pivoting.
mylsa.py
0.5 1.0 1.5 2.0 2.5 3.0
x
−1.00
−0.75
−0.50
−0.25
0.00
0.25
0.50
0.75
1.00
cos
(x)
Least-Square Approximation and Exact Solution for
y
(
x
) =
cosx
Exact
Approximate
Figure: Polynomial Least-Square Approximation.
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.33
Millikan oil-drop experiment I
•
In 1910, Millikan succeeded in measuring the electron
charge for the first time with a very sensitive experiment.
•
In this experiment, electrically charged oil droplets
remained suspended in the air under the influence of a
force that balanced the electric field applied between the
plates of a capacitor and the gravitational force.
•
From the equation qV /d = mg, the electric charge of each
droplet could be calculated by measuring the potential
difference and masses.
•
When Millikan listed these electric charges from smallest
to largest, he showed that they were multiples of a basic
unit of charge, and from there he determined the electric
charge as e = 1.65 × 10
−9
C (Today ’s value is
e = 1.602 × 10
−9
C).
Data Analysis:
Interpolation and Curve
Fitting II
Dr. Cem Özdo
˘
gan
LOGIK
Divided Differences
Spline Curves
The Equation for a Cubic
Spline
Least-Squares
Approximations
Nonlinear Data (Curve
Fitting)
Least-Squares Polynomials
Millikan oil-drop experiment
13.34
Millikan oil-drop experiment II
Example py-file: Millikan oil-drop experiment by Least-Square
Approximation. Gaussian elimination & back substitution.
Pivoting.
mylsa_millikan.py
4 6 8 10 12 14 16 18
n
10
15
20
25
30
q (10
−19
C)
a=1.638279 ×10
−19
C
b=0.028536
Millikan oil
-drop
experiment
y
(
x
) =
ax
+
b
Exact
Approximate
Figure: Millikan oil- drop experiment.
