超定方程组
3/46
19:25
离散数据的线性拟合 x x1 x2 f(x ) y1 y2
· · · · · · · · · · xm · · · · · · · · · · ym
求拟合函数: ( x ) a00 ( x) a11 ( x)
0 ( x1 ) 1 ( x1 ) 0 ( xm ) 1 ( xm ) y1 n ( x1 ) a0 y2 n ( xm ) an y m
( u1 , vk ) ( u1 , u1 )

uk -1 +uk
23/46
Gram-Schmidt正交化的矩阵编码
v1 u1 v2 v3 vk
( u1 , v2 ) ( u1 , u1 ) ( u1 , v3 ) ( u1 , u1 )
u1 u2 u1 ( u22 ,u32 ) u2 u3 u1
19:25 pinv(X)*y, norm(X\y) , norm(pinv(X)*y) X\y,
14/46
1范数意义下的残差最小
Sparse and Redundant Representations:
参考文献:
From Theory to Applications in Signal and Image Processing
定理: Gb是不相容矩阵的最小范数最小二乘解当且仅当 AGA=A, (AG)H=AG, GAG=G, (GA)H=GA。
注释: 最小范数最小二乘广义矩阵即Moore-Penrose矩阵。
19:25
12/46
总结 相容方程
Ax b Ax b
arg min Ax b
x 2 2
矩阵可逆则解唯一, 如果矩阵秩亏损的情形, 则所有解 中有唯一的最小范数解。
19:25
1 1 2 1 1 x1 1 x 2 3 3 9
18/46
1.7500 0.7500 1.9500 0.9500
直接方法: 高斯消元法
A(n – 1) = Fn-1Fn-2· · · · · · · F1 A
定理 矩阵A列满秩时, 最小二乘解唯一x= (ATA ) -1ATb。
19:25
11/46
不相容方程解的唯一性 是否存在某种意义下的唯一性? 最小范数最小二乘解 (minimum norm least squares solution)
若存在G满足 Gb 2 x 2 其中x {x : Ax b 2 Az b 2 z }, 则称Gb 是最小范数最小二乘解, G称为最小范数最小二乘广义矩阵。
19:25
15/46
最小二乘拟合问题研究包括:
模型的选取
存在唯一性 最小二乘解的计算
19:25
16/46
为什么不直接求解正规方程?
正规方程(normal equation) AT Ax AT b
A Rmn , 其中m n, AT Ax AT b注意AT A Rnn cond ( A A) (cond ( A))
Matlab: pinv (Pseudoinverse) 比较back slash和pinv的区别。
1 2 3 16 4 5 6 17 X 7 8 9 , y 18 10 11 12 19 13 14 15 20
2/46
离散数据的多项式拟合 x x1 x2 f(x ) y1 y2
求拟合函数:
1 1
· · · · · · · · · · xm · · · · · · · · · · ym
n
( x) a0 a1 x
x1 xm
n 1
an x
y1 x a0 y2 n xm an y m
19:25
9/46
不相容方程解的存在性
Ax b
x arg min || Ax b ||2 2
x
不相容方程的最小二乘解总是存在的。 证明: 即证明正规方程是相容方程。 rank([ATA, b])=rank(ATA)
设rank( A) k , 则rank( AT A) rank( AT ) rank( A) k , rank([ AT A, AT b]) rank( AT A) k 由于[ AT A, AT b] AT [ A, b], 故rank([ AT A, AT b]) min{rank( AT ),rank([ A, b])} rank([ AT A, AT b]) k 综上所述 ,rank([ AT A, AT b]) rank(AT A) k
a1n (1) a2 n ( n 1 ) a nn
19/46
矩阵LU分解是高斯消元法的矩阵编码。
回顾:
不相容Ax b
m n
超定方程Ax b, 其中A R
x
,m n
最小二乘解 x arg min || Ax b ||2 （least squares） 2
T 2
1 1
x1 xm
1 1 2 1 1 T X 0 , X X 2 1 1 19:25 0
y1 x a0 y2 n xm an y m
|| y || || Qx || || x ||
2 2 2 2
x 2 2
2 2
2 2
x arg min || QAx Qb || arg min || Rx Qb ||
x
19:25
21/46
—— Gram-Schmidt正交化——
u1 v1 u2 v2 u3 v3 uk vk

( x ) c1 c2 x

y1 1 x1 1 x c y 1 2 2 Ac=y c2 1 x m ym
超定方程组
c1 c2 xm ym
19:25
19:25
10/46
定理 如果矩阵A 列满秩, 则ATA可逆。
证明 : 如果矩阵列满秩则矩阵列向量1 , 2 , 线性无关, 则对于任意的非零向量c Ac c11 c2 2 cn n 0, 进一步有对任意非零向量c A Ac 0,
T T
, n
因为矩阵AT A正定, AT A可逆。
—— Gram-Schmidt正交化——
v1 u1 v2 v3 vk
19:25
( u1 , v2 ) ( u1 , u1 ) ( u1 , v3 ) ( u1 , u1 )
u1 u2 u1 u1
( u2 , v3 ) ( u2 , u2 )
u2 u3
( uk 1 , vk ) ( uk 1 , uk 1 )
19:25
( u1 , v2 ) ( u1 , u1 ) ( u1 ,v3 ) ( u1 , u1 )
u1 u1 u1
( u2 , v3 ) ( u2 , u2 )
u2
( uk 1 , vk ) ( uk 1 , uk 1 )
( u1 ,vk ) ( u1 , u1 )

uk -1
22/46
19:25
8/46
相容方程解的唯一性 是否存在某种意义下的唯一性?
最小范数解(minimum norm solution):
如果存在G满足 Gb 2 = min x 2 , 则称Gb为相容方程的最小范数解,
Ax b
广义逆矩阵G为最小范数广义逆矩阵。
定理: Gb是相容矩阵的最小范数解当且仅当 AGA=A, (GA)H=GA。 参考: 张贤达, 矩阵分析与应用, 清华大学
初等变分原理 arg min Ax b 2 AT Ax AT b ( normal eqaution )
x 2
19:25
20/46
正交矩阵QTQ=QQT=I 半正交矩阵QTQ=I(列正交)或QQT=I (行正交)
回顾:正交矩阵乘向量,则向量2范数不变。 QTQ= I , y =Qx
yT y (Qx)T (Qx) xT QT Qx xT x
如果m =n且A非奇异, 则方程的解为x A-1b。一个自然的问题是在 m n和A为秩亏缺( rank ( A) min{m , n})的情况下是否存在一个与 x A-1b相类似的解, 比如x Gb是相容方程的解?
定理: 相容方程Ax=b对y不等于零有解x=Gb当且仅当 AGA=A。(G称为是A的广义逆generalized inverse)
《数值分析》 16
最小二乘解的存在唯一性
最小二乘解的数值方法
19:25
1/46
离散数据的直线拟合 x x1 x2 f(x ) y1 y2
求拟合函数:
· · · · · · · · · · xm · · · · · · · · · · ym
c1 c2 x1 y1 c1 c2 x2 y2
ann ( x)
超定方程组
19:25
4/46
回顾:
Ax b
m n
2 2
超定方程Ax b, 其中A R
x
,m n
最小二乘解 x arg min || Ax b ||（next best）
初等变分原理 arg min Ax b 2 AT Ax AT b ( normal eqaution )
1 k ( ukk1 , uk 1 ) uk -1 +uk