求解线性方程组
# 0x1.最小二乘分析
如果线性方程组:Ax=b
其中,A∈R^mxn^,b∈R^m^, m≤n, rank A=m。
中,由b不属于矩阵A的值域空间,则称该方程是矛盾的或过定的,在这种情况下,方程组无解。
求解该方程就变成了寻找一个向量x,使得 || Ax - b ||^2^最小。
# 引理12.1
A∈R^mxn^,m≤n,当且仅当rank A^T^A=n(即方正非奇异)时,rank A=n。
# 定理12.1 x*唯一
x*具有唯一性。
# 0x3.线性方程组的最小范数解
某线性方程组为:Ax=b
其中,A∈R^mxn^,b∈R^m^, m≤n, rank A=m。
此时,方程组可能有无数个解,但是只存在一个最接近原点的解。
令x*表示这个解,所以对于任意满足Ax=b的x,都有|| x* || ≤ || x ||。
# 定理12.2 x*=A^T^(AA^T^)^-1^b
x*=A^T^(AA^T^)^-1^b
缺点是需要求(AA^T^)^-1^逆矩阵,当m较大时,计算耗时。
而这个缺点可以由下面的Kaczmarz算法改进。
# 0x4.Kaczmarz算法
继续考虑12.3节中定义的方程组Ax=b, A∈R^mxn^, b∈R^m^, m≤n, rank A=m。本 节介绍一种迭代求解算法,该算法由Kaczmarz于1937年首次提出[70], 能够在不直接计算AA^T^逆矩阵的情况下收敛到x*=A^T^(AA^T^)^-1^b。这一点使得该算法非常实用,尤其是在z矩阵A的行数非常多的情况下。 令a~j~^T^ 表示矩阵A的第j行, b,表示向量b的第j个元素, μ为正实数,满足0<μ<2。 Kaczmarz算法的步骤为
# 0x5.一般意义下的线性方程组的求解
一般意义下:
A∈R^mxn^,b∈R^m^, m≤n, rank A=r,且有r≤min{m,n}。
当rank A=n时,方程有唯一解x*=A^-1^b。
# 定义 12.1 伪逆矩阵A^+^
给定矩阵A∈R^mxn^,如果A^+^∈R^mxn^满足:
AA^+^A=A
且存在两个矩阵U∈R^mxn^,V∈R^mxn^,使得:
A^+^=UA^T^和A^+^=A^T^V
则称A^+^是矩阵A的伪逆。
# 引理12.3 满秩分解
矩阵A∈R^mxn^,rank A=r,且有r≤min{m,n}。存在矩阵B∈R^mxr^和矩阵C∈R^rxn^,使得A=BC。
其中rank A = rank B = rank C = r
# 定理 12.4 如果伪逆A^+^存在,则唯一
矩阵A∈R^mxn^,如果伪逆A^+^存在,则唯一
# 定理12.5 A^+^=C^+^B^+^
矩阵A∈R^mxn^的满秩分解为A=BC,rank A = rank B = rank C = r,B∈R^mxr^,C∈R^rxn^,那么有:
A^+^=C^+^B^+^
# 定理12.6 x*=A^+^b
x*=A^+^b时|| Ax - b ||^2^范数最小,且唯一
# 运算规则
- (A^T^)^+^=(A^+^)^T^
- (A^+^)=A
- AA^+^A=A
- A^+^AA^+^=A^+^
- (AA^+^)^T^=AA^+^
- (A^+^A)^T^=A^+^A