《 线性代数及其应用 （原书第4版）》—— 2.5 矩阵因式分解

本节书摘来自华章出版社《 线性代数及其应用 （原书第4版）》一书中的第2章，第2.5节，作者:（美）戴维C. 雷（David C. Lay）马里兰大学帕克学院 著刘深泉 张万芹 陈玉珍 包乐娥 陆 博 译，更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.5 矩阵因式分解

矩阵A的因式分解是把A表示为两个或更多个矩阵的乘积，矩阵乘法是数据的综合（把两个或更多个线性变换的作用结合成一个矩阵），矩阵因式分解是数据的分解，在计算机科学的语言中，将A表示为矩阵的乘积是对A中数据的预处理，把这些数据组成两个或更多部分，这种结构可能更有用，或者更便于计算.
矩阵的因式分解，以及以后的线性变换的分解将在许多关键地方出现. 本节主要讨论一种在许多重要的计算机程序核心部分出现的因式分解，某些其他的分解在习题中介绍.
LU分解
下面所述的 分解，是一些在工业与商业问题中常见的，解一系列具有相同系数矩阵的线性方程（见32题）：
（1）
在5.8节中，逆幂法通过逐个求解一系列形如（1）中的方程来估计矩阵的特征值.
当A为可逆，可计算 ，然后计算 ， ，等等. 然而，在实践中，（1）中第一个方程是由行变换解出的，并同时得出A的 LU分解，因而剩下的方程由 LU分解求解.
首先，设A是 矩阵可以行化简为阶梯形而不必行对换（此后，我们将处理一般情形），则A可写成形式 A=LU，L 是 下三角矩阵，主对角线元素全是1，U是A的一个等价的 阶梯形矩阵. 例如，见图2-11. 这样一个分解称为 LU分解，矩阵L是可逆的，称为单位下三角矩阵.

在研究如何构造L和U之前，我们将看看它们为什么这么有用. 当A=LU 时，方程Ax=b 可写成 L(Ux)=b，把 Ux写成 y，可以由解下面一对方程来求解x：
（2）
首先解 Ly=b然后解Ux=y 求得x ，见图2-12. 每个方程都比较容易解，因L和U都是三角矩阵.

例1 可以证明

应用A的 LU分解来解Ax=b ，其中 .
解 解Ly=b 仅需6次乘法和6次加法，因这些运算仅需对第5列进行.（在L 的每个主元下的零会在行变换的选取中自动产生.）

对 Ux=y，行化简的向后步骤需要4次除法，6次乘法和6次加法.（例如，把 [U y]的第4列变成零需要1次除法和3次乘法——把第4行的倍数加到上面各行.）

为求x 需28次算术运算，或“浮算”（浮点运算），不包括求L 和 U的运算在内. 相反[A b]， [I x]行化简成为 需62次运算.
LU 分解的计算效率依赖于如何求L和U ，下面的算法证明，把 A行化简为阶梯形U的运算同时也求出L而基本上不需要额外的运算，因而也求出 LU分解. 在第一次行化简后，L和 U就可用来解系数矩阵为 A的额外的方程.
LU分解算法
设A 可以化为阶梯形U . 化简过程中仅用行倍加变换，即把一行的倍数加于它下面的另一行. 这样，存在单位下三角初等矩阵 使
（3）
于是

其中
（4）
可以证明，单位下三角矩阵的逆也是单位下三角矩阵. （例如见19题.）于是L是单位下三角矩阵.
注意（3）中的行变换，它把 A化为U ，所以也把（4）中的L化为I ，因

这一点是构造L 的关键.
LU分解的算法

1. 如果可能的话，用一系列的倍加变换把A化为阶梯形.
2. 填充L的元素使相同的行变换把L变为I.
   第1步不是永远可能的，但当它可能时，上述讨论指出 LU分解存在. 例2将说明如何实现第2步. 根据上面的说明，L要满足使用与（3）中相同的 ，有

于是，依可逆矩阵定理，L是可逆的， . 由（3）， ，所以步骤2可求出所要的L .
例2 求下列矩阵的LU 分解：

解 因 有4行，L应为矩阵，L的第一列应该是 A的第一列除以它的第一行主元元素：

比较 A和L的第一列. 把A 的第一列的后3个元素变成零的行变换同时也将L 的后3个元素变成0，同样的道理对L的其他各列也是成立的，让我们看一下 A变成阶梯形U 的过程. 即每个矩阵中标出的元素，这些元素用于确定把A变成U的行变换顺序.（见（5）中标出的元素.）
（5）
上式中标出的元素确定了将 A化为 U的行变换，在每个主元列，把标出的元素除以主元后将结果放入L：

容易证明，所求出的L和 U满足LU=A .
在实际工作中，行对换几乎总是必要的，因为部分主元法可以用来提高精确度.（回忆这种算法总是选择一列中可以做为主元的元素中绝对值最大的一个作主元.）为了处理行对换，上述的 LU分解算法可以稍做改变，以产生一个置换下三角矩阵 L，就是说经过行的置换后它成为（单位）下三角矩阵. 所得的置换LU 分解可与前面一样的途径解方程Ax=b，只要在把 [L b]化简为 [I y]时按照L 中主元的顺序从左到右进行，并从第一列主元开始. 介绍LU 分解的参考书通常包含 L为置换下三角矩阵的可能性. 详见学习指导书.
数值计算的注解 下列运算次数的计算适用于 稠密矩阵 A（大部分元素非零），n 相当大，例如 .

1. 计算A 的LU 分解大约需要 浮算（大约与把 [A b]行化简的次数相同），而求 大约需要 浮算.
2. 解 Ly=b和 Ux=y大约需要 浮算，因任意
   三角方程组可以用大约 浮算解出.
3. 把 b乘以 也需要 浮算，但结果可能不如由L和U 得出的精确（由于计算 及 的舍入误差）.
4. 若A 是稀疏矩阵（大部分元素为0），则 L和U 可能也是稀疏的，然而 很可能是稠密的. 这时，用 LU分解来解方程 Ax=b很可能比用 快很多，见习题31.
   电子工程中的矩阵因式分解

矩阵因式分解在构造具有某些性质的电子网络中碰到. 下列讨论仅是矩阵分解与电路设计联系的一个大概.
设图2-13中的方框表示某种电路，具有输入与输出. 用 表示输入电压与电流（电压以伏特为单位，电流用安培为单位），输出电压与电流为 ，通常，变换 为线性的，也就是说，存在矩阵A，称为传递矩阵，使

图2-14表示梯级网络，它有两个回路（也可以更多），它们串联起来，所以第一个电路的输出是第二个电路的输入. 图2-14左边的电路称为串联电路，具有电阻 （单位为欧姆），右 端电路称为并联电路，有电阻 ，应用欧姆定律，可以证明串联电路与并联电路的传递矩阵为

例3

1. 计算图2-14中梯级网络的传递矩阵.
2. 设计一个传递矩阵为 的梯级网络.
   解
3. 设 和 分别为串联电路与并联电路的传递矩阵，则输入向量x 首先变换为 ，然后变为 ，两个电路的串联对应于变换的复合，所以梯级网络的传递矩阵为（注意顺序）
   （6）
4. 我们希望把矩阵 分解成两个传递矩阵的乘积，如（6）式，故我们要找出图2-14中 和 满足
   

由（1,2）元素， 欧姆，由（2,1）元素 ，而 欧姆，对电阻的这些值，图2-14中网络有所需传递矩阵.
网络的传递函数总结了网络的输入－输出行为（设计规范），而不必去了解电路内部，为了物理上建立网络，使它有特定性质，工程师首先确定这样的网络是否可实现. 然后尝试把传递矩阵分解为对应于较小回路的传递矩阵的积，这些较小回路已经制造出来. 在交流电的情况下，传递矩阵的元素通常是有理复值函数（见2.4节习题19和20，3.3节例2），标准问题是要找一个使用最少电子元件的最小实现.
练习题
求矩阵 的 LU分解.
（注：A仅有3个主元列，故例2的方法将仅产生 L的前三列. L 的余下两列由 得到.）
习题2.5