数据科学的数学基础L10A=LU

阅读数: 次 2020-04-30

数据科学的数学基础L10:A=LU

A=LU分解的核心目的，利用三角矩阵易于求解的特点求解线性方程组Ax=b;

总体思路：

就是线性方程组的求解过程

对矩阵A进行初等变换，这里的初等变换是某一行的常数倍加到某一行身上。

等A进行完初等变换后，如果是情况比较好的情况则得到了U矩阵。

即$L_1L_2L_3…L_nA=U,A=(L_n^{-1}…L_1^{-1})U$,U在这里是上三角矩阵。

$L_1L_2L_3…L_n$是因为只是处等矩阵的行变换的组合。

此时，回顾线性方程组的求解过程，需要一个一个回带才能求出答案，故此时回代的过程，undo/cancellation的过程，就可以得到L矩阵。

那么这里我将回代的矩阵过程，其实也就是上面求逆的过程。

Algorithm如下：

L=I,U=O;
for k=1 to n-1 do
	for i=k+1 to n do
		l_ik=a_ik/akk %更新L的第k列
	end for
	for j = k to n do
		u_kj = a_kj %更新U的第k行
	end for
	for i=k+1 to n do
		for j=k+1 to n do
			a_ij =a_ij -l_ij u_ij %更新矩阵A(k+1:n,k+1:n)
			end for
		end for
	end for

通过以上的算法，我们会得到唯一形式的LU分解

同样的，如果A是非奇异矩阵，且LU分解存在，A的LU分解是唯一存在的。

但是，注意到上述算法有一个隐藏的问题，即作为分母的$a_{kk}$元素，也就是主元有为0的可能。

什么时候主元为0？主元为0的时候又应该如何处理呢？

所以当主元为0时该如何进行A的LU分解呢?

设矩阵A，假设通过上述LU分解算法可以得到A^(k-1),则主元a_{kk}不为0的充要条件时A的k阶顺序主子式子｜A_k｜不为零。

因为在上述LU分解算法中，我们只讲矩阵的第i行的若干倍加到第k行，这个变换并不改变矩阵的各顺序主子式的值。

所以，为了解决主元为0时的情况，我们还可以进行行变换，进行行变换的处等矩阵记为P，PA=LU,即为我们需要的分解。

PA=LU ,可以从这个角度来解释，也就是对矩阵A的各行做重新排列，对于重新排列后的矩阵做LU分解。

在Algorithem的体现即为：

每对矩阵做初等变换前去判断主元是否为0.

初等矩阵都是可逆的
注意这里的L是单位下三角矩阵,(保留了L的主对角线上的值都为1)

矩阵A写成若干个秩1矩阵和的形式：

A=$l_1u_1^T+l_2u_2^T+…+l_ru_r^T$;

这里r是矩阵A的rank.

我们进一步假设$l_i$和$u_i$的前i-1个元素均为0，并且$l_i$的第i个元素为1，那么我们实际上就可以得到A的LU分解。