第七章 曲线拟合与函数逼近
/* 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])([?
n a a a 1 0
? 实际上是 a0,a1,…,an 的多元函数，即
[ ] ?
?
? ? ? ? ?
m
i i
n
i n i n y x a x a a a a a 1
2
1 0 1 0,.,),...,,( ?
在 ? 的极值点应有
nka
k
,...,0,0 ???? ?
k
im
i
iik a
xPyxP
a ?
???
?
?? ?
?
)(])([20
1
?
k
i
m
i
n
j
i
j
i j x y x a ? ?
? ?
? ?
1 0
] [ 2
? ? ? ? ?
? ? ?
?
n
j
m
i
k
i i
m
i
k j
i j x y x a
0 1 1
2
记 ? ?
? ?
? ?
m
i
k
i i k
m
i
k
i k x y c x b 1 1,?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
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 x b x F
0
) (
? ?
? ?
? ? ? ? ?
m
i
m
i
i i i i b y x F y x P a
1 1
2 2 ) ( ] ) ( [ ] ) ( [ ) ( ? ?
证明,? ?
? ?
? ? ? ? ?
m
i
i i
m
i i i
y x P y x F a b
1
2
1
2 ] ) ( [ ] ) ( [ ) ( ) ( ? ?
? ?
? ?
? ? ? ? ? ?
m
i
i i
m
i
i i i i y x P y x P x P x F
1
2
1
2 ] ) ( [ ] ) ( ) ( ) ( [
? ?
? ?
? ? ? ? ?
m
i
i i i i
m
i
i i y x P x P x F x P x F
1 1
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
方案一,设 b ax x x P y ? ? ? ) (
求 a 和 b 使得 最小。 ?
?
? ? ?
m
i i i
i y b ax x b a
1
2 ) ( ),( ?
But hey,the system of
equations for a and b is
nonlinear !
Take it easy! We just
have to linearize it … 线性化 /* linearization */：令,则 xXyY 1,1 ??
bX a Y ? ? 就是个 线性问题
将 化为 后易解 a 和 b。 ),( i i Y X ),( i i y x
§ 1 L-S Approximating Polynomials
方案二,设 x b e a x P y / ) ( ? ? ? ( a > 0,b > 0 )
线性化,由 可做变换 x b a y ? ? ln ln
b B a A x X y Y ? ? ? ? ?,ln,1,ln
BX A Y ? ? 就是个 线性问题
将 化为 后易解 A 和 B ),( i i Y X ),( i i y x
xbA eaxPBbea /)(,,?????
HW,p.146
#3,#4