第七章 曲线拟合与函数逼近
/* Approximation Theory */
仍然是已知 x1 … xm ; y1 … ym,求一个简单易算的近似函数 P(x)? f(x)。
但是 ① m 很大；
② yi 本身是测量值，不准确，即 yi? f (xi)
这时没必要取 P(xi) = yi,而要使 P(xi)? yi 总体上 尽可能小。
常见做法：
使 最小 /* minimax problem */|)(|m a x
1 iimi yxP
太复杂?
使 最小?
m
i
ii yxP
1
|)(|
不可导，求解困难?
使 最小 /* Least-Squares method */?
m
i
ii yxP
1
2|)(|
§ 1 最小二乘拟合 多项式 /* L-S approximating polynomials */
确定多项式,对于一组数据 (xi,yi) (i = 1,2,…,n) 使得 达到 极小,
这里 n << m。
nn xaxaaxP,..)( 10
m
i
ii yxP
1
2])([?
naaa 10
实际上是 a0,a1,…,an 的多元函数，即
[ ]?
m
i i
n
inin yxaxaaaaa 1
2
1010,..),...,,(?
在? 的极值点应有
nka
k
,...,0,0
k
im
i
iik a
xPyxP
a?
)(])([20
1
k
i
m
i
n
j
i
j
ij xyxa
1 0
][2
n
j
m
i
k
ii
m
i
kj
ij xyxa
0 11
2
记
m
i
k
iik
m
i
k
ik xycxb 11,?
nnnnn
n
c
c
a
a
bb
bb
..
.
..
.
...
..
.
..
.
..
.
..,00
0
000
法方程组 (或 正规方程组 )
/* normal equations */ 回归系数/* regression coefficients */
§ 1 L-S Approximating Polynomials
定理 L-S 拟合多项式 存在唯一 (n < m)。
证明,记法方程组为 Ba = c,
ΦΦB T?则有 其中
yΦc T?
n
mmm
n
x.,,xx
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x.,,xx
Φ
2
1
2
11
1
1
对任意,必有 。10 nRu 0?uΦ
10 nRu 0?uΦ
若不然，则存在一个 使得 …
即 mkuxn
j
j
j
k,...,1,0
0
是 n 阶多项式
mxx,...,1
nn xuxuuxP,..)( 10 的根则 0|||| 2
2 uΦuΦΦuuBu TTT
B为 正定阵,则非奇异，所以法方程组 存在唯一 解。
Wait a second!
You only gave me a critical point,
but it’s not necessarily a
minimum point !
§ 1 L-S Approximating Polynomials
定理 Ba = c 的解确是? 的 极小点 。即：设 a 为解，则任意 b = (b0 b1 … bn )T 对应的多项式 必有?
n
j
j
j xbxF
0
)(
m
i
m
i
iiii byxFyxPa
1 1
22 )(])([])([)(
证明,
m
i
ii
m
i ii
yxPyxFab
1
2
1
2 ])([])([)()(
m
i
ii
m
i
iiii yxPyxPxPxF
1
2
1
2 ])([])()()([
m
i
iiii
m
i
ii yxPxPxFxPxF
11
2 ])()][()([2)]()([ 0
注,?L-S method 首先要求设定 P(x) 的形式。若设
n=m?1，则可取 P(x) 为过 m 个 点的 m?1阶插值多项式，这时?= 0。
P(x) 不一定是多项式，通常根据经验确定。
§ 1 L-S Approximating Polynomials
例：
x
y
(xi,yi),i = 1,2,…,m
方案一,设 baxxxPy )(
求 a 和 b 使得 最小。
m
i ii
i ybaxxba
1
2)(),(?
But hey,the system of
equations for a and b is
nonlinear !
Take it easy! We just
have to linearizeit …线性化 /* linearization */：令,则xXyY 1,1
bXaY 就是个 线性问题将 化为 后易解 a 和 b。),( ii YX),( ii yx
§ 1 L-S Approximating Polynomials
方案二,设 xbeaxPy /)( ( a > 0,b > 0 )
线性化,由 可做变换xbay lnln
bBaAxXyY,ln,1,ln
BXAY 就是个 线性问题将 化为 后易解 A 和 B),( ii YX),( ii yx
xbA eaxPBbea /)(,,
HW,p.146
#3,#4
/* Approximation Theory */
仍然是已知 x1 … xm ; y1 … ym,求一个简单易算的近似函数 P(x)? f(x)。
但是 ① m 很大；
② yi 本身是测量值，不准确，即 yi? f (xi)
这时没必要取 P(xi) = yi,而要使 P(xi)? yi 总体上 尽可能小。
常见做法：
使 最小 /* minimax problem */|)(|m a x
1 iimi yxP
太复杂?
使 最小?
m
i
ii yxP
1
|)(|
不可导，求解困难?
使 最小 /* Least-Squares method */?
m
i
ii yxP
1
2|)(|
§ 1 最小二乘拟合 多项式 /* L-S approximating polynomials */
确定多项式,对于一组数据 (xi,yi) (i = 1,2,…,n) 使得 达到 极小,
这里 n << m。
nn xaxaaxP,..)( 10
m
i
ii yxP
1
2])([?
naaa 10
实际上是 a0,a1,…,an 的多元函数，即
[ ]?
m
i i
n
inin yxaxaaaaa 1
2
1010,..),...,,(?
在? 的极值点应有
nka
k
,...,0,0
k
im
i
iik a
xPyxP
a?
)(])([20
1
k
i
m
i
n
j
i
j
ij xyxa
1 0
][2
n
j
m
i
k
ii
m
i
kj
ij xyxa
0 11
2
记
m
i
k
iik
m
i
k
ik xycxb 11,?
nnnnn
n
c
c
a
a
bb
bb
..
.
..
.
...
..
.
..
.
..
.
..,00
0
000
法方程组 (或 正规方程组 )
/* normal equations */ 回归系数/* regression coefficients */
§ 1 L-S Approximating Polynomials
定理 L-S 拟合多项式 存在唯一 (n < m)。
证明,记法方程组为 Ba = c,
ΦΦB T?则有 其中
yΦc T?
n
mmm
n
x.,,xx
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x.,,xx
Φ
2
1
2
11
1
1
对任意,必有 。10 nRu 0?uΦ
10 nRu 0?uΦ
若不然，则存在一个 使得 …
即 mkuxn
j
j
j
k,...,1,0
0
是 n 阶多项式
mxx,...,1
nn xuxuuxP,..)( 10 的根则 0|||| 2
2 uΦuΦΦuuBu TTT
B为 正定阵,则非奇异，所以法方程组 存在唯一 解。
Wait a second!
You only gave me a critical point,
but it’s not necessarily a
minimum point !
§ 1 L-S Approximating Polynomials
定理 Ba = c 的解确是? 的 极小点 。即：设 a 为解，则任意 b = (b0 b1 … bn )T 对应的多项式 必有?
n
j
j
j xbxF
0
)(
m
i
m
i
iiii byxFyxPa
1 1
22 )(])([])([)(
证明,
m
i
ii
m
i ii
yxPyxFab
1
2
1
2 ])([])([)()(
m
i
ii
m
i
iiii yxPyxPxPxF
1
2
1
2 ])([])()()([
m
i
iiii
m
i
ii yxPxPxFxPxF
11
2 ])()][()([2)]()([ 0
注,?L-S method 首先要求设定 P(x) 的形式。若设
n=m?1，则可取 P(x) 为过 m 个 点的 m?1阶插值多项式，这时?= 0。
P(x) 不一定是多项式，通常根据经验确定。
§ 1 L-S Approximating Polynomials
例：
x
y
(xi,yi),i = 1,2,…,m
方案一,设 baxxxPy )(
求 a 和 b 使得 最小。
m
i ii
i ybaxxba
1
2)(),(?
But hey,the system of
equations for a and b is
nonlinear !
Take it easy! We just
have to linearizeit …线性化 /* linearization */：令,则xXyY 1,1
bXaY 就是个 线性问题将 化为 后易解 a 和 b。),( ii YX),( ii yx
§ 1 L-S Approximating Polynomials
方案二,设 xbeaxPy /)( ( a > 0,b > 0 )
线性化,由 可做变换xbay lnln
bBaAxXyY,ln,1,ln
BXAY 就是个 线性问题将 化为 后易解 A 和 B),( ii YX),( ii yx
xbA eaxPBbea /)(,,
HW,p.146
#3,#4
