深圳营销型网站建设价格,做网站logo用啥软件,比较放得开的几个直播平台,贵州建设厅网站建筑企业公示栏一、A LU
线性代数很多关键的概念实际上就是矩阵的分解#xff08;factorization#xff09;。原始矩阵 A A A 变成两个或三个特殊矩阵的乘积。第一个分解#xff0c;实际上也是最重要的分解#xff0c;来自消元法。因子 L L L 和 U U U 都是三角形矩阵#xff0c;分…一、A LU
线性代数很多关键的概念实际上就是矩阵的分解factorization。原始矩阵 A A A 变成两个或三个特殊矩阵的乘积。第一个分解实际上也是最重要的分解来自消元法。因子 L L L 和 U U U 都是三角形矩阵分解 A L U ALU ALU 来自消元法。 矩阵 U U U 是上三角矩阵它的主元都在对角线上消元步骤将 A A A 变为 U U U。现在我们要反向这些步骤将 U U U 变为 A A A 通过一个下三角矩阵 L L L 就可以。 L L L 的元素正好就是乘数 l i j l_{ij} lij —— 从行 i i i 减去乘数乘主元行 j j j。 以 2 × 2 2×2 2×2 的矩阵为例矩阵 A A A 有四个元素 2 , 1 , 6 , 8 2,1,6,8 2,1,6,8要消去的元素是 6 6 6。从行 2 2 2 减去 3 3 3 乘行 1 1 1这个正向步骤使用消元矩阵 E 21 E_{21} E21乘数 l 21 3 l_{21}3 l213。从 U U U 到 A A A 的反向步骤使用 L E 21 − 1 LE^{-1}_{21} LE21−1行 2 2 2 加上 3 3 3 乘行 1 1 1。 正向从 A 到 U E 21 A [ 1 0 − 3 1 ] [ 2 1 6 8 ] [ 2 1 0 5 ] U 反向从 U 到 A E 21 − 1 U [ 1 0 3 1 ] [ 2 1 0 5 ] [ 2 1 6 8 ] A 正向从\,A\,到\,U\kern 5ptE_{21}A\begin{bmatrix}10\\-3 1\end{bmatrix}\begin{bmatrix}21\\68\end{bmatrix}\begin{bmatrix}21\\05\end{bmatrix}U\\[1ex]反向从\,U\,到\,A\kern 5ptE_{21}^{-1}U\begin{bmatrix}10\\31\end{bmatrix}\begin{bmatrix}21\\05\end{bmatrix}\begin{bmatrix}21\\68\end{bmatrix}A 正向从A到UE21A[1−301][2618][2015]U反向从U到AE21−1U[1301][2015][2618]A上面第二行就是分解 L U A LUA LUA将 E 21 − 1 E_{21}^{-1} E21−1 用 L L L 代替。更大的矩阵会有很多 E ′ s Es E′s L \pmb L L 包含它们所有的逆矩阵。 A A A 到 U U U 的每一个步骤都要左乘一个矩阵 E i j E_{ij} Eij将位置 ( i , j ) (i,j) (i,j) 的元素变为 0 0 0。为了清晰起见假设没有行交换如果 A A A 是 3 × 3 3×3 3×3 的矩阵需要在左边依次乘 E 21 E_{21} E21 E 31 E_{31} E31 E 32 E_{32} E32乘数 l i j l_{ij} lij 将会使得位置 ( 2 , 1 ) (2,1) (2,1) ( 3 , 1 ) (3,1) (3,1) ( 3 , 2 ) (3,2) (3,2) 位置处的元素都变为 0 0 0它们都在对角线下方消元法在得到一个上三角矩阵后结束。 现在将 E ′ s Es E′s 移到另外一边将它们的逆矩阵乘上 U U U ( E 32 E 31 E 21 ) A U 变为 A ( E 21 − 1 E 31 − 1 E 32 − 1 ) U 就是 A L U ( 2.6.1 ) (E_{32}E_{31}E_{21})AU\kern 10pt变为\kern 10ptA(E_{21}^{-1}E_{31}^{-1}E_{32}^{-1})U\kern 10pt就是\kern 10pt\pmb{ALU}\kern 10pt(2.6.1) (E32E31E21)AU变为A(E21−1E31−1E32−1)U就是ALU(2.6.1) 逆矩阵是反序相乘三个逆矩阵的乘积就是 L L L。我们得到了 A L U ALU ALU。
二、解释与例子
第一点每一个逆矩阵 E − 1 E^{-1} E−1 都是下三角矩阵。它的非主对角线元素是 l i j l_{ij} lij用来恢复 − l i j -l_{ij} −lij 产生的减法。 E E E 和 E − 1 E^{-1} E−1 的主对角线都是 1 1 1。上面的例子中 l 21 3 l_{21}3 l213 E [ 1 0 − 3 1 ] E\begin{bmatrix}10\\-31\end{bmatrix} E[1−301] L E − 1 [ 1 0 3 1 ] LE^{-1}\begin{bmatrix}10\\31\end{bmatrix} LE−1[1301]。 第二点式2.6.1展示了一个下三角矩阵 E i j E_{ij} Eij 的乘积乘 A A A也展示了所有的 E i j − 1 E_{ij}^{-1} Eij−1 乘 U U U 会得到 A A A。 E i j \pmb{E_{ij}} Eij 的逆矩阵的乘积得到的下三角矩阵就是 L \pmb L L。 我们处理这些逆矩阵的一个原因是想要分解 A A A而不是 U U U。它的 “反向形式” 得到了 A L U ALU ALU。另一个原因是我们会得到更多的信息 L L L 是一个很好的矩阵这也是第三点。 第三点每个乘数 l i j l_{ij} lij 可以直接放入 L L L 的 ( i , j ) (i,j) (i,j) 位置不需要改变。通常矩阵的乘法会将这些位置弄乱但是在 L L L 里不会。因为逆矩阵的正确顺序使得 l l l 没有发生变化。在式2.6.3中会给出原因。 第四点每个 E − 1 E^{-1} E−1 的对角线都是 1 1 1 L L L 也是如此。 A L U 消元过程中没有行交换 . 上三角矩阵 U 的 主元在它的对角线上 . 下三角矩阵 L 的主 元都是 1 乘数 l i j 在 L 的对角线下方 . \begin{matrix}ALU\end{matrix}\kern 15pt\begin{matrix}\pmb{消元过程中没有行交换}.上三角矩阵\,U\,的\\主元在它的对角线上.下三角矩阵\,L\,的主\\元都是\,1\,乘数\,l_{ij}\,在\,L\,的对角线下方.\end{matrix} ALU消元过程中没有行交换.上三角矩阵U的主元在它的对角线上.下三角矩阵L的主元都是1乘数lij在L的对角线下方. 【例1】消元法从行 2 2 2 减去 1 2 \displaystyle\frac{1}{2} 21 乘行 1 1 1最后一步从行 3 3 3 减去 2 3 \displaystyle\frac{2}{3} 32 乘行 2 2 2。下三角矩阵 L L L 有 l 21 1 2 l_{21}\displaystyle\frac{1}{2} l2121 l 32 2 3 l_{32}\displaystyle\frac{2}{3} l3232。 L U LU LU 的乘积得到 A A A A [ 2 1 0 1 2 1 0 1 2 ] [ 1 0 0 1 2 1 0 0 2 3 1 ] [ 2 1 0 0 3 2 1 0 0 4 3 ] L U A\begin{bmatrix}210\\121\\012\end{bmatrix}\begin{bmatrix}100\\\displaystyle\frac{1}{2}10\\0\displaystyle\frac{2}{3}1\end{bmatrix}\begin{bmatrix}210\\0\displaystyle\frac{3}{2}1\\00\displaystyle\frac{4}{3}\end{bmatrix}LU A 210121012 12100132001 20012300134 LU因为 A A A 的 ( 3 , 1 ) (3,1) (3,1) 元素是 0 0 0所以 ( 3 , 1 ) (3,1) (3,1) 位置的乘数是 0 0 0即不需要进行操作。
【例2】将 A A A 左上角的元素 2 2 2 改为 1 1 1变成 B B B。则所有的主元都是 1 1 1所有的乘数也是 1 1 1。保持这种模式当 B B B 是 4 × 4 4\times4 4×4 的矩阵时 B [ 1 1 0 0 1 2 1 0 0 1 2 1 0 0 1 2 ] [ 1 1 1 0 1 1 0 0 1 1 ] [ 1 1 0 0 1 1 0 1 1 1 ] B\begin{bmatrix}1100\\1210\\0121\\0012\end{bmatrix}\begin{bmatrix}1\\11\\011\\0011\end{bmatrix}\begin{bmatrix}1100\\110\\11\\1\end{bmatrix} B 1100121001210012 1100110111 1110110011 假设没有行交换如何可以得知 L L L 和 U U U 中哪些元素为 0 0 0 呢 当 A 的某一行从 0 开始则 L 的该行也从 0 开始 当 A 的某一列从 0 开始则 U 的该列也从 0 开始 \pmb{当\,A\,的某一行从\,0\,开始则\,L\,的该行也从\,0\,开始}\\\pmb{当\,A\,的某一列从\,0\,开始则\,U\,的该列也从\,0\,开始} 当A的某一行从0开始则L的该行也从0开始当A的某一列从0开始则U的该列也从0开始如果某一行从 0 0 0 开始那么就不需要消元 L L L 相应的位置就是 0 0 0这将节省电脑的时间。同样的如果某一列从 0 0 0 开始 U U U 相应的位置也为 0 0 0。但是如果 0 0 0 在中间因为消元法是前向消除这些位置在 L L L 或 U U U 的对应的位置大概率就不再是 0 0 0。那么为什么 L L L 相应的位置是乘数 l i j l_{ij} lij而不发生混乱呢 关键原因是 A \pmb A A 为什么等于 L U \pmb{LU} LU当主元行下方的行减去时它们还是 A A A 的原始行吗不是因为在消元过程中它们被改变了。那么它们是 U U U 的行吗是的因为主元不再改变。当计算 U U U 的第三行时我们会减去乘数乘 U U U 前面的行不是 A A A 的行 R o w 3 o f U ( R o w 3 o f A ) − l 31 ( R o w 1 o f U ) − l 32 ( R o w 2 o f U ) ( 2.6.2 ) Row\,\,3\,\,of\,\,U(Row\,\,3\,\,of\,\,A)-l_{31}(Row\,\,1\,\,of\,\,U)-l_{32}(Row\,\,2\,\,of\,\,U)\kern 19pt(2.6.2) Row3ofU(Row3ofA)−l31(Row1ofU)−l32(Row2ofU)(2.6.2)改写这个方程看看行 [ l 31 l 32 1 ] \begin{bmatrix}l_{31}l_{32}1\end{bmatrix} [l31l321] 是如何与 U U U 相乘的 ( R o w 3 o f A ) l 31 ( R o w 1 o f U ) l 32 ( R o w 2 o f U ) 1 ( R o w 3 o f U ) ( 2.6.3 ) (Row\,\,3\,\,of\,\,A)l_{31}(Row\,\,1\,\,of\,\,U)l_{32}(Row\,\,2\,\,of\,\,U)1(Row\,\,3\,\,of\,\,U)\kern 10pt(2.6.3) (Row3ofA)l31(Row1ofU)l32(Row2ofU)1(Row3ofU)(2.6.3)正好就是 ( A L U ) (ALU) (ALU) 的第三行。 L L L 的行 3 3 3 的分量是 l 31 l_{31} l31 l 32 l_{32} l32 1 1 1。无论 A A A 有多大所有的行都是这样。如果没有行交换则有 A L U ALU ALU。 平衡形式 L D U \pmb{LDU} LDU A L U ALU ALU 是不对称的因为 U U U 的对角线上是主元而 L L L 的对角线都是 1 1 1。将 U U U 分成一个举着 D D D 和一个新的矩阵 U U U 相乘矩阵 D D D 是对角线矩阵它的对角线就是 U U U 的主元而新的矩阵 U U U 的对角线就会变成 1 1 1其它元素除以该行的主元
新的上三角矩阵 U U U 的对角线都是 1 1 1。与正常的 L U LU LU 不同的是新形式中间有一个 D D D下三角矩阵 L \pmb L L 乘对角线矩阵 D \pmb D D 乘上三角矩阵 U \pmb U U。 矩阵的三角分解可以写 A L U 或 A L D U 矩阵的三角分解可以写\kern 10pt\pmb{ALU}\,或 \,\pmb{ALDU} 矩阵的三角分解可以写ALU或ALDU 当看到 L D U LDU LDU 的形式时我们就可以知道 U U U 的对角线都是 1 1 1每一行都除以其第一个非零元素 —— 主元 L U LU LU中 U U U 的主元 [ 1 0 3 1 ] [ 2 8 0 5 ] 进一步分解为 [ 1 0 3 1 ] [ 2 5 ] [ 1 4 0 1 ] ( 2.6.4 ) \begin{bmatrix}10\\31\end{bmatrix}\begin{bmatrix}28\\05\end{bmatrix}\kern 10pt进一步分解为\kern 10pt\begin{bmatrix}10\\31\end{bmatrix}\begin{bmatrix}2\\5\end{bmatrix}\begin{bmatrix}14\\01\end{bmatrix}\kern 10pt(2.6.4) [1301][2085]进一步分解为[1301][25][1041](2.6.4)主元 2 2 2 和 5 5 5 进入了 D D D行分别除以 2 2 2 和 5 5 5得到新的 U U U它的对角线都是 1 1 1。乘数 3 3 3 仍然在 L L L 内。
三、一个方形系统 两个三角形系统
矩阵 L L L 包含了高斯消元法的记忆它保存了每次进行消元时的乘数。我们可以使用这些求解 A x b A\boldsymbol x\boldsymbol b Axb。 当存在右侧的 b \boldsymbol b b 时则需要 L L L。因子 L L L 和 U U U 完全取决于左侧矩阵 A A A。在 A x b A\boldsymbol x\boldsymbol b Axb 的右侧我们先使用 L − 1 L^{-1} L−1 再使用 U − 1 U^{-1} U−1。该求解步骤会处理两个三角形矩阵。 1、分解通过对左侧的矩阵 A A A 进行消元得到 L L L 和 U U U 2、求解使用 L L L 对 b \boldsymbol b b 进行前向消元然后使用 U U U 进行回代求得 x \boldsymbol x x 以前我们使用增广矩阵 [ A b ] \begin{bmatrix}A\boldsymbol b\end{bmatrix} [Ab] 同时处理 A A A 和 b \boldsymbol b b。但是电脑大多数会将两侧分开 L L L 和 U U U 都保存有消元的记忆无论何时我们都可以处理 b \boldsymbol b b。因为这样求解一个单一的系统只需要一个子程序。 那么如何使用 b \boldsymbol b b 呢首先对右侧使用前向消元法乘数存储在 L L L 中现在可以使用它会将 b \boldsymbol b b 变成一个新的右侧 c \boldsymbol c c我们现在求解的是 L c b L\boldsymbol c\boldsymbol b Lcb然后使用回代求解 U x c U\boldsymbol x\boldsymbol c Uxc原始系统 A x b A\boldsymbol x\boldsymbol b Axb 就被分解成了两个三角系统 前向与反向 求解 L c b 然后求解 U x c ( 2.6.5 ) \pmb{前向与反向}\kern 10pt求解\kern 5ptL\boldsymbol c\boldsymbol b然后求解\kern 5ptU\boldsymbol x\boldsymbol c\kern 10pt(2.6.5) 前向与反向求解Lcb然后求解Uxc(2.6.5) 要验证 x \boldsymbol x x 就是要求的解 U x c U\boldsymbol x\boldsymbol c Uxc 两侧同时左乘 L L L得到 L U x L c LU\boldsymbol xL\boldsymbol c LUxLc 就是 A x b A\boldsymbol x\boldsymbol b Axb。 强调 这些步骤并没有新的知识。我们使用前向消元求解三角系统 L c b L\boldsymbol c\boldsymbol b Lcb然后回代求解 U x c U\boldsymbol x\boldsymbol c Uxc。
【例3】以 A x b A\boldsymbol x\boldsymbol b Axb 前向消元开始在 U x c U\boldsymbol x\boldsymbol c Uxc 结束 A x b u 2 v 5 4 u 9 v 21 变为 u 2 v 5 v 1 U x c A\boldsymbol x\boldsymbol b\kern 10pt\begin{matrix}u2v5\\4u9v21\end{matrix}\kern 10pt变为\kern 10pt\begin{matrix}u2v5\\\kern 24ptv1\end{matrix}\kern 10ptU\boldsymbol x\boldsymbol c Axbu2v54u9v21变为u2v5v1Uxc乘数 4 4 4 保存在 L L L 中右侧使用 4 4 4 将 21 21 21 变成了 1 1 1 L c b 下三角系统 [ 1 0 4 1 ] [ c ] [ 5 21 ] 求得 c [ 5 1 ] L\boldsymbol c\boldsymbol b\kern 10pt下三角系统\kern 10pt\begin{bmatrix}10\\41\end{bmatrix}[\boldsymbol c]\begin{bmatrix}5\\21\end{bmatrix}\kern 5pt求得\kern 5pt\boldsymbol c\begin{bmatrix}5\\1\end{bmatrix} Lcb下三角系统[1401][c][521]求得c[51] U x c 上三角系统 [ 1 2 0 1 ] [ x ] [ 5 1 ] 求得 x [ 3 1 ] U\boldsymbol x\boldsymbol c\kern 10pt上三角系统\kern 10pt\begin{bmatrix}12\\01\end{bmatrix}[\boldsymbol x]\begin{bmatrix}5\\1\end{bmatrix}\kern 5pt求得\kern 5pt\boldsymbol x\begin{bmatrix}3\\1\end{bmatrix} Uxc上三角系统[1021][x][51]求得x[31] L L L 和 U U U 所使用的也就是以前 A A A 所使用的 n 2 n^2 n2 的存储空间。
四、消元法的成本
这里讨论消元法的成本 —— 即计算时间的问题。我们在计算机上解方程就需要考虑计算成本在科学计算时我们可能会遇到大型系统三维空间的问题就很容易有一百万个未知数如果计算成本太高的话我们不可能让计算机计算成百上千年。 消元法的第一阶段是将列 1 1 1 的第一主元以下的元素全部变为 0 0 0第一行以下的元素全部都需要改变而改变一个元素需要一次乘法和一次减法所以第一阶段大约需要 n 2 n^2 n2 次乘法和 n 2 n^2 n2 次减法实际上会少一些因为第一行不变实际上需要 n ( n − 1 ) n(n-1) n(n−1) 次乘法和加法这里计算的是一个大致成本。 第二阶段我们需要将列 2 2 2 的第二主元下方的元素变为 0 0 0此时我们要考虑的矩阵会小一些是一个 ( n − 1 ) × ( n − 1 ) (n-1)\times(n-1) (n−1)×(n−1) 的矩阵所以这一阶段大约是 ( n − 1 ) 2 (n-1)^2 (n−1)2 次乘法与减法。越往下进行所要考虑的矩阵越小最终要得到矩阵 U U U 则粗略估计需要的次数为 n 2 ( n − 1 ) 2 ⋯ 2 2 1 2 n^2(n-1)^2\cdots2^21^2 n2(n−1)2⋯2212。 上式平方和的公式为 1 3 n ( n 1 2 ) ( n 1 ) \displaystyle\frac{1}{3}n(n\frac{1}{2})(n1) 31n(n21)(n1)当 n n n 很大时就可以忽略里面的 1 2 \displaystyle\frac{1}{2} 21 和 1 1 1总和大约就是 1 3 n 3 \displaystyle\frac{1}{3}n^3 31n3。 x 2 x^2 x2 从 0 0 0 到 n n n 的积分就是 1 3 n 3 \displaystyle\frac{1}{3}n^3 31n3需要注意的是积分是连续的而这里是离散的。 对矩阵 A 使用消元法大概需要 1 3 n 3 次乘法 和 1 3 n 3 次减法 对矩阵 A 使用消元法大概需要 \,\displaystyle\pmb{\frac{1}{3}n^3}\, \pmb{次乘法}和 \displaystyle\frac{1}{3}n^3 次减法 对矩阵A使用消元法大概需要31n3次乘法和31n3次减法 下面考虑右侧的 b \boldsymbol b b我们要计算 L c b L\boldsymbol c\boldsymbol b Lcb得到 c \boldsymbol c c。首先我们从 b 2 , ⋯ , b n b_2,\cdots,b_n b2,⋯,bn 减去乘数乘 b 1 b_1 b1这里需要 n − 1 n-1 n−1 步第二阶段就不需要考虑 b 1 b_1 b1共需要 n − 2 n-2 n−2 步最后一阶段需要 1 1 1 步。 最后考虑回代通过 U x c U\boldsymbol x\boldsymbol c Uxc 求解 x \boldsymbol x x。首先计算 x n x_n xn 需要 1 1 1 步仅需要除以最后一个主元然后计算 x n − 1 x_{n-1} xn−1 需要 2 2 2 步这里需要代入 x n x_n xn然后除以第 n − 1 n-1 n−1 主元最后计算 x 1 x_1 x1 时需要 n n n 步要代入 ( n − 1 ) (n-1) (n−1) 个未知数然后除以第一主元。所有计算右侧的 b \boldsymbol b b 正好需要需要 n 2 n^2 n2 步从前到后再回代 [ ( n − 1 ) ( n − 2 ) ⋯ 1 ] [ 1 2 ⋯ ( n − 1 ) n ] n 2 ( 2.6.6 ) [(n-1)(n-2)\cdots1][12\cdots(n-1)n]n^2\kern 10pt(2.6.6) [(n−1)(n−2)⋯1][12⋯(n−1)n]n2(2.6.6)可以看到右侧的成本要比左侧小很多。 求解 右侧需要 n 2 次乘法 和 n 2 次减法 \pmb{求解}\kern 15pt右侧需要\,\pmb{n^2\,次乘法}和\,n^2\,次减法 求解右侧需要n2次乘法和n2次减法 一个带状矩阵 B B B 只在主对角线的上方和下方有 w w w 个非零对角线带状外的其它元素在消元过程中都保持 0 0 0 不变 L L L 和 U U U 中。第一列需要 w 2 w^2 w2 次乘法和减法在主元下方产生 w w w 个 0 0 0每个 0 0 0 需要使用长度为 w w w 的主元行所以要执行完消元过程共需要 n w 2 nw^2 nw2 次乘法和减法得到 U U U。这样会节省很多时间。 带状矩阵 A 到 U 1 3 n 3 减少到 n w 2 求解 n 2 减少到 2 n w \pmb{带状矩阵}\kern 14pt\pmb{A\,到\,U}\kern 8pt\frac{1}{3}n^3减少到nw^2\kern 10pt\pmb{求解}\kern 6ptn^2\,减少到\,2nw 带状矩阵A到U31n3减少到nw2求解n2减少到2nw 一个三对角矩阵 w 1 w1 w1可以计算的很快不需要存储 0 0 0。
五、主要内容总结
高斯消元法没有行交换将 A A A 分解成 L L L 乘 U U U。下三角矩阵 L L L 包含用来乘主元行的乘数 l i j l_{ij} lij它们使得 A A A 变成 U U U。乘积 L U LU LU 将这些行反向加回去可以恢复成 A A A。在右侧我们求解 L c b L\boldsymbol c\boldsymbol b Lcb前向然后求解 U x c U\boldsymbol x\boldsymbol c Uxc反向。分解 左侧共有 n 3 − n 3 \displaystyle\frac{n^3-n}{3} 3n3−n 次乘法和减法这个结果没有取近似。求解 右侧共有 n 2 n^2 n2 次乘法和减法。对于带状矩阵需要的步骤 1 3 n 3 \displaystyle\frac{1}{3}n^3 31n3 变为 n w 2 nw^2 nw2 n 2 n^2 n2 变为 2 n w 2nw 2nw。
六、例题
【例4】下三角帕斯卡矩阵 L L L 包含著名的 “帕斯卡三角形”这里我们分解帕斯卡。 对称帕斯卡矩阵 P \pmb P P 是帕斯卡矩阵 L \pmb L L 和 U \pmb U U 的乘积。对称的 P P P 矩阵以帕斯卡三角命名所以它的每个元素都是其上方和左侧元素之和。MATLAB 中 n × n n\times n n×n 的对称 P P P 矩阵写成 pascal(n)。 问题建立一个下 - 上三角分解的 P L U PLU PLU。 pascal(4) [ 1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20 ] [ 1 0 0 0 1 1 0 0 1 2 1 0 1 3 3 1 ] [ 1 1 1 1 0 1 2 3 0 0 1 3 0 0 0 1 ] L U \textrm{pascal(4)}\begin{bmatrix}\pmb1\pmb1\pmb1\pmb1\\\pmb1\pmb2\pmb34\\\pmb1\pmb3610\\\pmb141020\\\end{bmatrix}\begin{bmatrix}\pmb1000\\\pmb1\pmb100\\\pmb1\pmb2\pmb10\\\pmb1\pmb3\pmb3\pmb1\end{bmatrix}\begin{bmatrix}\pmb1\pmb1\pmb1\pmb1\\0\pmb1\pmb2\pmb3\\00\pmb1\pmb3\\000\pmb1\end{bmatrix}LU pascal(4) 1111123413610141020 1111012300130001 1000110012101331 LU预测并检验 5 × 5 5\times5 5×5 的帕斯卡矩阵的下一行和下一列。 解 计算 L U LU LU 可以得到 P P P。下面从对称 P P P 矩阵出发利用消元法得到上三角矩阵 U U U P [ 1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20 ] → [ 1 1 1 1 0 1 2 3 0 2 5 9 0 3 9 19 ] → [ 1 1 1 1 0 1 2 3 0 0 1 3 0 0 3 10 ] → [ 1 1 1 1 0 1 2 3 0 0 1 3 0 0 0 1 ] U P\begin{bmatrix}1111\\1234\\13610\\141020\end{bmatrix}\rightarrow\begin{bmatrix}1111\\0123\\0259\\03919\end{bmatrix}\rightarrow\begin{bmatrix}1111\\0123\\0013\\00310\end{bmatrix}\rightarrow\begin{bmatrix}1111\\0123\\0013\\0001\end{bmatrix}U P 1111123413610141020 → 10001123125913919 → 10001100121313310 → 1000110012101331 U上面步骤所用到的乘数 l i j l_{ij} lij 会进入到下三角矩阵 L L L P L U PLU PLU 是一个特别整洁有序的例子。注意到 U U U 的在对角线上的主元都是 1 1 1。 若使用 MATLAB 来计算指令 lu(pascal(4)) 无法生成上述的 U U U这是因为 lu 的子程序会在每一列选取最大的主元这样第二主元就变成了 3 3 3而不是 1 1 1但是使用乔里斯基Cholesky分解不会发生行交换可以产生上述结果U chol(pascal(4)) 【例5】问题求解 P x b ( 1 , 0 , 0 , 0 ) P\boldsymbol x\boldsymbol b(1,0,0,0) Pxb(1,0,0,0)。方程的右侧等于 I I I 的第一列这表明 x \boldsymbol x x 会是 P − 1 P^{-1} P−1 的第一列。这就是高斯 - 若尔当消元法会匹配 P P − 1 I PP^{-1}I PP−1I 的列。我们已知帕斯卡矩阵 L L L 和 U U U 是 P P P 的两个因子 两个三角系统 L c b ( 前向 ) U x c ( 后向 ) \pmb{两个三角系统}\kern 20ptL\boldsymbol c\boldsymbol b\,(前向)\kern 10ptU\boldsymbol x\boldsymbol c\,(后向) 两个三角系统Lcb(前向)Uxc(后向)解 下三角系统 L c b L\boldsymbol c\boldsymbol b Lcb 由上到下求解 c 1 1 c 1 c 2 0 c 1 2 c 2 c 3 0 c 1 3 c 2 3 c 3 c 4 0 解得 c 1 1 c 2 − 1 c 3 1 c 4 − 1 \begin{matrix}c_1\kern 74pt1\\c_1c_2\kern 53pt0\\c_12c_2c_3\kern 27pt0\\c_13c_23c_3c_40\end{matrix}\kern 10pt解得\kern 10pt\begin{matrix}c_11\\c_2-1\\c_31\\c_4-1\end{matrix} c11c1c20c12c2c30c13c23c3c40解得c11c2−1c31c4−1利用 L − 1 L^{-1} L−1 执行前向消元得到上三角形系统 U x c U\boldsymbol x\boldsymbol c Uxc使用回代求解 x \boldsymbol x x上三角系统由下到上求解 x 1 x 2 x 3 x 4 1 x 2 2 x 3 3 x 4 − 1 x 3 3 x 4 1 x 4 − 1 解得 x 1 4 x 2 − 6 x 3 4 x 4 − 1 \begin{matrix}x_1x_2x_3x_41\\\kern 22ptx_22x_33x_4-1\\\kern 44ptx_33x_41\\\kern 81ptx_4-1\end{matrix}\kern 10pt解得\kern 10pt\begin{matrix}x_14\\x_2-6\\x_34\\x_4-1\end{matrix} x1x2x3x41x22x33x4−1x33x41x4−1解得x14x2−6x34x4−1使用 inv(pascal(4)) 指令求得 P P P 的逆矩阵可以看到解就是 P − 1 P^{-1} P−1 的第一列。
