CP4.矩阵的LU分解

2023-11-17

LU分解

将矩阵A分解成 $A=LU$ 的形式，称作矩阵LU分解，L代指下三角矩阵，U代指上三角矩阵。首先用到的是前面讲过的消元法，以下为例子：

$A=\begin{bmatrix} 2&1\\8 &7\end{bmatrix}$

$\begin{bmatrix} 1 &0 \\ -4&1 \end{bmatrix} \begin{bmatrix} 2 &1 \\ 8&7 \end{bmatrix}=\begin{bmatrix} 2 &1 \\ 0&3 \end{bmatrix}$

$E21\,A=U$

通过消元操作，最后矩阵A变成了一个上三角矩阵U，那么只要上式左乘一个 $E_{21}^{-1}$ ，就可以转化为

$A=E_{21}^{-1}U$

这里的 $E_{21}^{-1}$ 就是L矩阵了。 $E_{21}^{-1}=\begin{bmatrix} 1 &0 \\ 4&1 \end{bmatrix}$ ，所以 $A=LU=\begin{bmatrix}1 &0\\4&1 \end{bmatrix} \begin{bmatrix}2 &1\\0&3 \end{bmatrix}$ 。

也可以表达成如下形式，把U矩阵的主元提取出来。

$A=LDU=\begin{bmatrix}1 &0\\4&1 \end{bmatrix} \begin{bmatrix}2 &0\\0&3 \end{bmatrix} \begin{bmatrix}1 &1/2\\0&1 \end{bmatrix}$

对于三阶矩阵不需要换行进行消元的情况，就是说如果一个三阶矩阵，只通过初等行变换就能完成消元的情况下，假设其步骤为：

$E_{32}E_{31}E_{21}A=U$

通过求逆可得矩阵A的LU分解为：

$A=E_{21}^{-1} E_{31}^{-1} E_{32}^{-1} U=LU$

假设某三阶矩阵的消元矩阵如下

$E_{21}=\begin{bmatrix} 1&0&0\\ -2&1&0\\ 0&0&1\end{bmatrix} E_{32}=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-5&1\end{bmatrix} E_{31}=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\end{bmatrix}$

先把这几个矩阵相乘，对A进行初等行变换，然后求逆获得L矩阵

$E=E_{21}E_{31}E_{32}=\begin{bmatrix} 1&0&0\\ -2&1&0\\ 10&-5&1\end{bmatrix}$

很明显，上述矩阵的逆矩阵

$L=E^{-1}=\begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&5&1\end{}$

这里存在一个问题，按常规顺序计算的时候，E矩阵的第三行出现了10这个元素，说明第一行参与了10次运算，被反复调用。那么是否存在更快捷的方法呢？或需我们可以直接计算各消元矩阵的逆，然后直接相乘。

$E_{21}^{-1} E_{32}^{-1}=L=\begin{bmatrix}1&0&0\\ 2&1&0\\0&0&1 \end{}\begin{bmatrix}1&0&0\\ 0&0&1\\0&5&1 \end{}=\begin{bmatrix}1&0&0\\ 2&1&0\\0&5&1 \end{}$

很明显，直接计算L矩阵比利用相乘再求逆要快的多，但是用计算机处理的时候看不出来而已。

消元法计算次数

在进行超大规模矩阵运算的时候，不得不考虑所需要的运算量，如果我们把“先乘后减”记为一次运算，那么对于一个nxn矩阵，对于一行进行消元要进行n次运算，由于有n行所以进行了nxn次运算，结果得到了第一列除第一主元外都消成0的矩阵。随后开始对除第一行第一列之外的剩余部分进行消元，这相当于一个(n-1)x(n-1)的矩阵，那么就要进行(n-1)x(n-1)次运算，以此类推。

最后需要的运算次数为1x1+2x2+……+nxn，利用积分公式可以估算其数值。

$1^2 +2^2+...+n^2=\sum_{i=1}^ni^2=\int_{0}^{n}x^2dx=1/3n^3$

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

代数基础

矩阵