Least Squares Curve Fitting: Numerical Methods
Least Squares Curve Fitting: Numerical Methods
Least Squares Curve Fitting: Numerical Methods
1
Lecture 18
Introduction to Least
Squares
2
Motivation
Given a set of experimental data:
x 1 2 3
y 5.1 5.9 6.3
3
Motivation
In engineering, two types of applications are
encountered:
Trend analysis: Predicting values of dependent
variable, may include extrapolation beyond data points
or interpolation between data points.
Hypothesis testing: Comparing existing mathematical
model with measured data.
1. What is the best mathematical function f that
represents the dataset?
2. What is the best criterion to assess the fitting of
the function f to the data?
4
Curve Fitting
Given a set of tabulated data, find a curve
or a function that best represents the
data.
Given:
1. The tabulated data
2. The form of the function
g k ( x) are known.
7
Decide on the Criterion
1. Least Squares Regression :
n
minimize i
( y f ( x i )) 2
i 1
8
Least Squares Regression
Given: xi x1 x2 …. xn
yi y1 y2 …. yn
ei 2 ( yi f ( xi )) 2 ( f ( xi ) yi ) 2
The difference is assumed to be the result of
experimental error.
9
Determine the Unknowns
10
Determine the Unknowns
Necessary condition for the minimum :
( a, b)
0
a
( a, b)
0
b
11
Determining the Unknowns
n
( a , b)
2 a bxi yi 0
a i 1
n
( a , b)
2 a bxi yi xi 0
b i 1
12
Normal Equations
n n
n a xi b yi
i 1 i 1
n n 2 n
xi a xi b xi y i
i 1 i 1 i 1
13
Solving the Normal
Equations
n n n
n xi yi xi yi
b i 1 i 1 i 1
2
n n
n xi xi
2
i 1 i 1
1 n n
a yi b xi
n i 1 i 1
14
Example 1: Linear
Regression
Assume :
f(x) a bx x 1 2 3
y 5.1 5.9 6.3
Equations :
n n
n a xi b yi
i 1 i 1
n n 2 n
xi a x i b xi y i
i 1 i 1 i 1
15
Example 1: Linear
Regression
i 1 2 3 sum
xi 1 2 3 6
yi 5.1 5.9 6.3 17.3
xi2 1 4 9 14
xi yi 5.1 11.8 18.9 35.8
Equations :
3 a 6 b 17.3
6a 14 b 35.8
Solving : a 4.5667 b 0.60
16
Multiple Linear Regression
Example: t 0 1 2 3
x 0.1 0.4 0.2 0.2
Given the following data:
y 3 2 1 2
f(x,t) = a + b x + c t
That best fits the data with the least sum of the
square of errors.
17
Solution of Multiple Linear
Regression
Construct , the sum t 0 1 2 3
of the square of the
x 0.1 0.4 0.2 0.2
error and derive the
necessary conditions by y 3 2 1 2
equating the partial
derivatives with respect
to the unknown
parameters to zero, then
solve the equations.
18
Solution of Multiple Linear
Regression
n
f ( x, t ) a bx ct , ( a, b, c ) a bxi cti yi 2
i 1
Necessary conditions :
n
( a , b, c )
2 a bxi cti yi 0
a i 1
n
( a , b, c )
2 a bxi cti yi xi 0
b i 1
n
( a , b, c )
2 a bxi cti yi ti 0
c i 1
19
System of Equations
n n n
a n b xi c ti y i
i 1 i 1 i 1
n n n n
a x i b ( x i ) 2 c ( x i ti ) ( xi y i )
i 1 i 1 i 1 i 1
n n n n
a ti b ( xi ti ) c (ti ) (ti yi )
2
i 1 i 1 i 1 i 1
20
Example 2: Multiple Linear
Regression
i 1 2 3 4 Sum
ti 0 1 2 3 6
xi 0.1 0.4 0.2 0.2 0.9
yi 3 2 1 2 8
xi2 0.01 0.16 0.04 0.04 0.25
xi t i 0 0.4 0.4 0.6 1.4
xi yi 0.3 0.8 0.2 0.4 1.7
ti2 0 1 4 9 14
t i yi 0 2 2 6 10
21
Example 2: System of
Equations
4a 0.9b 6c 8
0.9a 0.25b 1.4c 1.7
6a 1.4b 14c 10
Solving :
a 2.9574, b 1.7021, c 0.38298
f ( x, t ) a bx ct 2.9574 1.7021 x 0.38298 t
22
Lecture 19
Nonlinear Least Squares
Problems
23
Polynomial Regression
The least squares method can be extended to fit
the data to a higher-order polynomial
2 2 2
f ( x ) a bx cx , ei ( f ( x ) yi )
n 2
Minimize ( a, b, c ) a bxi cxi2 yi
i 1
Necessary conditions :
( a , b, c ) ( a , b, c ) ( a, b, c )
0, 0, 0
a b c
24
Equations for Quadratic
Regression
n 2
Minimize ( a, b, c ) a bxi cxi2 yi
i 1
n
( a , b, c )
2 a bxi cxi2 yi 0
a i 1
n
( a , b, c )
2 a bxi cxi2 yi xi 0
b i 1
n
( a , b, c )
2 a bxi cxi2 yi xi2 0
c i 1
25
Normal Equations
n n n
a n b xi c xi2 yi
i 1 i 1 i 1
n n n n
a xi b 2
xi c 3
xi xi y i
i 1 i 1 i 1 i 1
n n n n
a xi2 b xi3 c xi4 xi2 yi
i 1 i 1 i 1 i 1
26
Example 3: Polynomial
Regression
Fit a second-order polynomial to the following data
xi 0 1 2 3 4 5 ∑=15
yi 2.1 7.7 13.6 27.2 40.9 61.1 ∑=152.6
x i2 0 1 4 9 16 25 ∑=55
x i3 0 1 8 27 64 125 225
x i4 0 1 16 81 256 625 ∑=979
xi yi 0 7.7 27.2 81.6 163.6 305.5 ∑=585.6
27
Example 3: Equations and
Solution
6 a 15 b 55 c 152.6
15 a 55 b 225 c 585.6
55 a 225 b 979 c 2488.8
Solving . . .
a 2.4786, b 2.3593, c 1.8607
f ( x ) 2.4786 2.3593 x 1.8607 x 2
28
How Do You Judge Functions?
Given two or more functions to fit the data,
How do you select the best?
Answer :
Determine the parameters for each function,
then compute for each one. The function
resulting in smaller (least sum of the squares
of the errors) is the best.
29
Quadratic is preferable
than Linear Regression
y y
x x
30
Fitting with Nonlinear
Functions
xi 0.24 0.65 0.95 1.24 1.73 2.01 2.23 2.52
31
Fitting with Nonlinear
Functions
n
( a, b, c ) ( a ln( xi ) b cos( xi ) c e xi yi ) 2
i 1
Necessary condition for the minimum :
( a, b, c )
0
a
( a, b, c )
0 Normal Equations
b
( a, b, c )
0
c 32
Normal Equations
n n n n
a (ln xi ) b (ln xi )(cos xi ) c (ln xi )( e ) yi (ln xi )
2 xi
i 1 i 1 i 1 i 1
n n n n
a (ln xi )(cos xi ) b (cos xi ) c (cos xi )( e ) yi (cos xi )
2 xi
i 1 i 1 i 1 i 1
n n n n
a (ln xi )( e ) b (cos xi )(e ) c ( e ) yi ( e xi )
xi xi xi 2
i 1 i 1 i 1 i 1
33
Example 4: Evaluating
Sums
xi 0.24 0.65 0.95 1.24 1.73 2.01 2.23 2.52 ∑=11.57
yi 0.23 -0.23 -1.1 -0.45 0.27 0.1 -0.29 0.24 ∑=-1.23
(ln xi)2 2.036 0.1856 0.0026 0.0463 0.3004 0.4874 0.6432 0.8543 ∑=4.556
ln(xi) cos(xi) -1.386 -0.3429 -0.0298 0.0699 -0.0869 -0.2969 -0.4912 -0.7514 ∑=-3.316
ln(xi) * exi -1.814 -0.8252 -0.1326 0.7433 3.0918 5.2104 7.4585 11.487 ∑=25.219
yi * ln(xi) -0.328 0.0991 0.0564 -0.0968 0.1480 0.0698 -0.2326 0.2218 ∑=-0.0625
cos(xi)2 0.943 0.6337 0.3384 0.1055 0.0251 0.1808 0.3751 0.6609 ∑=3.26307
cos(xi) * exi 1.235 1.5249 1.5041 1.1224 -0.8942 -3.1735 -5.696 -10.104 ∑=-14.481
yi*cos(xi) 0.223 -0.1831 -0.6399 -0.1462 -0.0428 -0.0425 0.1776 -0.1951 ∑=-0.8485
(exi)2 1.616 3.6693 6.6859 11.941 31.817 55.701 86.488 154.47 ∑=352.39
yi * exi 0.2924 -0.4406 -2.844 -1.555 1.523 0.7463 -2.697 2.9829 ∑=-1.9923
34
Example 4: Equations &
Solution
4.55643 a 3.31547 b 25.2192 c 0.062486
3.31547 a 3.26307 b 14.4815 c 0.848514
25.2192 a 14.4815 b 352.388 c 1.992283
35
Example 5: Self
Reading/Optional
xi 1 2 3
Given:
yi 2.4 5 9
n
2 ae bxi yi e bxi 0
a i 1 Difficult to Solve
n
2 ae bxi yi a xi e bxi 0
b i 1 36
Linearization Method
Find a function f(x) ae bx that best fits the data.
Define g ( x ) ln( f ( x )) ln(a ) b x
Define zi ln( yi ) ln(a ) bxi
Let ln(a ) and zi ln( yi )
n 2
Instead of minimizing : ( a , b) ae bxi
yi
i 1
n
Minimize : ( , b) bxi zi 2 ( Easier to solve)
i 1
37
Example 5: Equations
n
( , b) b xi zi 2
i 1
Normal Equations are obtained using :
n
2 b xi z i 0
i 1
n
2 b xi z i xi 0
b i 1
n n n n n
n b xi zi and xi b xi2 ( xi zi )
i 1 i 1 i 1 i 1 i 1
38
Evaluating Sums and Solving
xi 1 2 3 ∑=6
yi 2.4 5 9
zi=ln(yi) 0.875469 1.609438 2.197225 ∑=4.68213
x i2 1 4 9 ∑=14
x i zi 0.875469 3.218876 6.591674 ∑=10.6860
Equations :
3 6 b 4.68213 ln(a ), a e
6 14 b 10.686 a e 0.23897 1.26994
Solving Equations :
f ( x ) ae bx 1.26994 e 0.66087 x
0.23897, b 0.66087
39