2.4直接三角分解法

4 直接三角分解法 一 教学设计一 教学设计 1 教学内容 Doolittle 分解法 Crout 分解法 紧凑格式的 Doolittle 分解法 部分选主元 的 Doolittle 分解法 2 重点难点 紧凑格式的 Doolittle 分解法 部分选主元的 Doolittle 分解法 3 教学目标 了解直接三角分解法的基本思想 掌握基本三角分解法及其各种变形 4 教学方法 讲授与讨论 二 教学过程二 教学过程 在上节中我们用矩阵初等变换来分析 Gauss 消去法 得到了 重要的矩阵分解定理 定理 3 1 3 2 由此我们将得到LU Gauss 消去法的变形 直接三角分解法 直接三角分解法的 基本想法是 一旦实现了矩阵 A 的分解 那么求解方程LU 组的问题就等价于求解两个三角形方程组bx A 1 求 by Ly 2 求 yx Ux 而这两个三角形方程组的求解是容易的 下面我们先给出 这两个三角形方程组的求解公式 然后研究在或LUA 时 的元素与 A 的元素之间的直接关系 LUPA UL 4 0 三角形线性方程组的解法 设 nnnn lll ll l L 21 2221 11 11121 222 n n nn uuu uu U u 则为下三角形方程组 它的第 个方程为by Li 2 1 11 2211 1 nibylylylylyl iiiiiiiii i j jij 假定 按的顺序解得 0 ii l n yyy 21 3 2 1 1 1111 ni l byl y lby ii i i j jij i 上三角形方程组的第 个方程为yx Ui 2 1 11 niyxuxuxuxu ininiiiiii n ij jij 假定 按的顺序求解得 0 ii u 121 xxxx nn 1 2 2 1 1 nni u yxu x uyx ii i n ij jij i nnnn 4 1 基本的三角分解法 设矩阵的各阶顺序主子式均不为零 由定理 nnij aA 3 1 A 有分解如下LU nnnrnn rnrrrr nr nr aaaa aaaa aaaa aaaa 21 21 222221 111211 LU u uu uuu uuuu lll ll l nn rnrr nr nr nrnn rr 2222 111211 21 21 21 1 1 1 1 比较等式两边的第 1 行上的相应元素 得的第 1 行元素 U 4 4 2 1 11 niau ii 比较等式两边的第 1 列上的相应元素 从第 2 开始 得 的第 1 列元素 L 4 5 3 2 11 1 1 ni u a l i i 比较等式两边的第 2 行上的相应元素 从第 2 开始 得 iii uula 21212 故得的第 2 行元素 U 3 2 12122 niulau iii 比较等式两边的第 2 列上的相应元素 从第 3 开始 得 2222121iii aulul 得 的第 2 列元素 L 4 3 22 1212 2 ni u ula l ii i 假设已求得的第 1 至行 的第 1 至列 比较等式U1 rL1 r 两边的第 行上的相应元素 从第 开始 得rr rnrnnrrrnrnr rrrrrrrrrrrr rrrrrrrrrrrr auululul auululul auululul 11 2211 1 1 1 11 1 221 11 11 2211 即 1 1 1 nrriauul riri r k kirk 故得的第 行元素 Ur 4 6 3 2 1 1 1 nrnrriulau r k kirkriri 比较等式两边的第 列上的相应元素 从第开始 得r1 r nrrrnrrrrnrnrn rrrrrrrrrrrrrr rrrrrrrrrrrrrr aulululul aulululul aulululul 11 2211 2 2 11 222 211 2 1 1 11 122 111 1 即 2 1 1 1 nrriaulul irrrir r k krik 故得 的第 列元素 Lr 4 7 1 3 2 2 1 1 1 nrnrri u ula l rr r k krikir ir 称由 4 4 4 7 式所表示的矩阵分解为 Doolittle 分解 它的计算顺序为 的第 1 行 的第 1 列 的第 2 行 ULU 的第 2 列 的第 行 的第 列 的第行LUrLrU1 n 的第列 的第 行 r 从 1 到 n 循环即可 L1 nUn 实现了系数矩阵 A 的 Doolittle 分解后 求解方程组的bx A 问题就等价于求解两个三角形方程组 1 求 by Ly 2 求 利用 4 0 节有关结论 立得 Doolittleyx Ux 分解相应的求解公式为 3 2 1 1 11 nrylby by r i irirr 1 2 2 1 1 nnr u xuy x uyx rr n ri irir r nnnn 类似地 可以推导 Crout 分解的计算公式 2 1 1 1 1 nrnrriulal r k krikirir 1 2 1 1 1 1 nrnri l ula u rr r k kirkri ri 它的计算顺序为 的第 1 列 的第 1 行 的第 2 列 的第 2 行 LULU 的第 列 的第 行 的第列 的第行 LrUrL1 nU1 n 的第 行Ln Crout 分解相应的求解公式为 3 2 1 1 1111 nr l ylb y lby rr r i irir r 1 2 2 1 1 nnrxuyx yx n ri irirr nn 小结 Doolittle 分解计算 A LU 1 计算的第 1 行元素 U 2 1 11 niau ii 如果 则计算停止 0 11 u 2 计算 的第 1 列元素 L 3 2 11 1 1 ni u a l i i 3 对于nr 3 2 1 计算的第 行元素 Ur 1 1 1 nrriulau r k kirkriri 如果 则计算停止 0 rr u 2 计算 的第 列元素 Lr 2 1 1 1 nrri u ula l rr r k krikir ir 4 求解计算 yxby UL 3 2 1 1 11 nrylby by r i irirr 1 2 1 1 nnr u xuy x uyx rr n ri irir r nnnn 例 用 Doolittle 法解方程组 7 2 5 10 139144 4321 131243 30102 4 3 2 1 x x x x 直接利用公式计算 从中总结 Doolittle 分解的计算规律 图示中还可清楚地看到存贮情况 Gauss 消去法逐步对 A 施加变换 逐步获得 L U 而 Doolittle 分解公式则集中了前 r 1 次变换 一次性付诸实施 的第 1 行与 的第 1 列 UL nnnn n n aaa aaa aaa 21 22221 11211 的第 2 行与 的第 2 列 UL nnninn iniiii ni ni aaal aaal aaal uuuu 21 21 222221 111211 nnninn iniiii ni ni aaal aaal uuul uuuu 21 21 222221 111211 的第 3 行与 的第 3 列 UL nnninnn iniiiii ni ni ni aaall aaall aaall uuuul uuuuu 321 321 33333231 22232221 11131211 nnninnn iniiiii ni ni ni aaall aaall uuull uuuul uuuuu 321 321 33333231 22232221 11131211 的第 行与 的第 列 UrLr1 3 2 nr nnninrrnn iniiirrii rnrirrrrr nrirrrrrr nirr aaall aaall aaall uuuul uuuuu 1 1 1 1 1 1 1 1 11 11 1 1111 111 nnninrrnn iniiirrii rnrirrrrr nrirrrrrr nirr aaall aaall uuull uuuul uuuuu 1 1 1 1 1 1 1 1 11 11 1 1111 111 最后计算的第 行 实际上只有一个元素 Un nn u nnnnn nnnnn nn all uul uuu 1 1 11 11 1 11 111 注意在计算和解 的公式中 如果将 看作 的第列 UybA1 n 它们遵循着相同的规则 事实上 由 得ybLLUA 据此 我们可得到紧凑格式的 Doolittle 分解 1 byALU 即将上述分解过程处理的对象由 A 改为增广矩阵 用 bA 同样的方法处理第列 从而在获得系数矩阵的 Doolittle1 n 分解的同时 存放在增广矩阵第列中的元素就是 UL 1 ny 注意此时在公式 4 4 4 6 中计算时 应到为止 ri ui1 n 编程计算时 应注意所有的元素都存贮在增广矩阵yx UL 中 紧凑格式的紧凑格式的 Doolittle 分解的算法设计 分解的算法设计 小结 分解计算 A LU 1 对于nr 3 2 1 1 计算的第 行元素 Ur 1 1 1 1 1 1 nrriaaaulaua r k kirkri r k kirkririri 如果 则计算停止 0 rr a 2 计算 的第 列元素 Lr 2 1 1 1 1 1 nrri a aaa u ula la rr r k krikir rr r k krikir irir 4 求解计算 yxby UL 1 2 2 1 1 1 1 1 1 1 1 nnr a aaa a u xuy x aaauyx rr n ri nirinr nr rr n ri irir r nnnnnnnnnn 例 用紧凑格式的 Doolittle 法解上述例子中的方程组 A 2 10 0 3 10 3 4 12 13 5 1 2 3 4 2 4 14 9 13 7 r 1 2 10 0 3 10 3 2 4 12 13 5 1 2 2 3 4 2 2 14 9 13 7 r 2 2 10 0 3 10 3 2 11 12 17 2 20 1 2 3 11 3 4 2 2 6 11 9 13 7 r 3 2 10 0 3 10 3 2 11 12 17 2 20 1 2 3 11 3 11 2 11 17 11 2 6 11 9 13 7 r 4 2 10 0 3 10 3 2 11 12 17 2 20 1 2 3 11 3 11 2 11 17 11 2 6 11 9 4 16 L 1 0 0 0 3 2 1 0 0 1 2 3 11 1 0 2 6 11 9 1 U 2 10 0 3 0 11 12 17 2 0 0 3 11 2 11 0 0 0 4 y 10 20 17 11 16 x 1 2 3 4 4 2 部分选主元的 Doolittle 分解 1 部分选主元的三角分解法 当用分解法解方程组时 从第 步分解计算公式可r 2 1 nr 知 1 1 1 nrriulau r k kirkriri 2 1 1 1 nrri u ula l rr r k krikir ir 当时 分解计算将中断 或 但很小时 按上0 rr u0 rr u rr u 式计算 进行计算可能引起舍入误差的累积 扩大 因此 ir l 可采用与列主元消去法类似方法 先选列主元 再进行分 解计算 即将直接三角分解法修改为部分选主元的三角分 解法 部分选主元的 Doolittle 分解法与列主元消去法在理 论上是等价的 设用紧凑格式的 Doolittle 法已完成了第 步分1 r 1nr 解 则增广矩阵 A的元素如下 rr Ab 1 1 1 1 1 1 1 1 1 11 11 1 1 1111 111 nnnnnrrnn nrnrrrrrr nrnrrrrrr nnrr aaall aaall uuuul uuuuu A 第 步分解 为避免用绝对值小的数作除数 首先在 A 的第r 列主对角元以下 含主对角元 选主元 具体步骤如下 r 1 对于进行 部分 选主元的分解计算 实际 rnr 2 1 从 1 到 n 1 即可 因第 n 步不需要选主元 而在分解计算中 只需在完成循环后 补充 A n n 1 的计算 1 计算中间量作为可能的主元 并存入 1 nrriSi ir a 1 1 1 1 1 nrriaaaulaSa r k krikir r k krikiriir 2 挑选绝对值最大的 即确定行号 使满足 i S r i i nir i SS r max 3 交换两行 当时 交换 A 的第 行与第 行的对应rir r r i 元素 交换后的元素以它在 A 中所处的新位置记 此时处 在 A 的第位置的元素就是主元交换前的交 rr rr u rii rr aS 换后的应该是中绝对值最大者 rr a 1 nrriSi 4 分解计算 以下两步可调换次序 因已计算 rr a 已 1 1 1 1 1 1 nriaaaulaua r k kirkri r k kirkririri ri 算出 时 2 1 1 1 nrri a a S S u ula la rr ir r i rr r k krikir irir nr 程序自动不做 按上述方法完成分解 便实现了系数矩阵分解 只LUPA 是 P 没有记录下来 于是解等价于解 或bx AbxPPA 即且的解 已解出 存放在 AbxPLU yxby UPL byPL y 的第列中 接下来只要解即可得最终解 1 nyx Ux 2 求解计算 1 2 2 1 1 1 1 1 1 1 1 nnr a aaa a u xuy x aaauyx rr n ri nirinr nr rr n ri irir r nnnnnnnnnn 例 用部分选主元的 Doolittle 法解方程组 1 4 1 294 642 311 3 2 1 x x x 解 r 1 中间量 1 1 3 1 2 4 6 4 4 9 2 1 1 3 4 9 2 1 2 4 6 4 1 1 3 1 分解计算 4 9 2 1 1 2 4 6 4 1 4 1 3 1 r 2 中间量 4 9 2 1 1 2 1 2 6 4 1 4 5 4 3 1 2 3 4 9 2 1 1 4 5 4 3 1 1 2 1 2 6 4 分解计算 4 9 2 1 1 4 5 4 5 2 3 4 1 2 2 5 6 4 r 3 分解计算 4 9 2 1 1 4 5 4 5 2 3 4 1 2 2 5 4 16 5 L 1 0 0 1 4 1 0 1 2 2 5 1 U 4 9 2 0 5 4 5 2 0 0 4 y 1 3 4 16 5 x 12 5 1 4 5 2 紧凑格式的 Doolittle 法用于解系列方程组 2 1 mjA jj bx 令 2121mm BXbbbxxx 则解系列方程组相当于解矩阵方程 实现系数矩阵分BAX 解后 解等价于解 或以下两个三LUPA BAX PBLUX 角形矩阵方程 1 求矩阵 2 求矩阵 PBLY 21m Yyyy YUX m Xxxx 21 利用 部分选主元 Doolittle 法紧凑格式对增广矩阵 施行 Doolittle 分解 可同时求得 然后解 m 个上 BAYU 三角形方程组 2 1 mjU jj yx 解为 2 1 1 2 1 2 1 1 mjnr u yuy x mjuyx rr n rk kjrkrj rj nnnjnj 例 用部分选主元 Doolittle 法紧凑格式解矩阵方程 BAX 其中 3411 0111 3322 1211 A 84 42 4020 168 B 4241 3231 2221 1211 xx xx xx xx X 解 r 1 中间量 1 1 2 1 8 16 2 2 3 3 20 40 1 1 1 0 2 4 1 1 4 3 4 8 1 2 2 2 3 3 20 40 1 1 2 1 8 16 1 1 1 0 2 4 1 1 4 3 4 8 分解计算 2 2 3 3 20 40 1 2 1 2 1 8 16 1 2 1 1 0 2 4 1 2 1 4 3 4 8 r 2 中间量 2 2 3 3 20 40 1 2 0 2 1 8 16 1 2 2 1 0 2 4 1 2 0 4 3 4 8 2 3 2 2 3 3 20 40 1 2 2 1 0 2 4 1 2 0 2 1 8 16 1 2 0 4 3 4 8 分解计算 2 2 3 3 20 40 1 2 2 1 2 3 2 8 16 1 2 0 2 1 8 16 1 2 0 4 3 4 8 r 3 中间量 2 2 3 3 20 40 1 2 2 1 2 3 2 8 16 1 2 0 1 2 1 8 16 1 2 0 5 2 3 4 8 3 4 2 2 3 3 20 40 1 2 2 1 2 3 2 8 16 1 2 0 5 2 3 4 8 1 2 0 1 2 1 8 16 分解计算 2 2 3 3 20 40 1 2 2 1 2