数值模拟导论--Read.PDF

数值模拟导论-第四讲 线性稀疏矩阵的直接解法 Luca Daniel 感谢Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Jacob White 概述 • 回顾LU分解法 • 稀疏矩阵 —珩架和节点，电阻网，3d热流 • 三角矩阵分解 ―一般的稀疏矩阵分解 ―填充和重排列 — 图表逼近 • 稀疏矩阵数据结构 —散布 SMA-HPC ©2003 MIT 分解 LU分解基础 图片 SMA-HPC ©2003 MIT 上图便是LU分解的图形表示。第一步，用第一个方程消去第二到第四方程中 的x1 。这一过程我们用除第一行外的各行分别减去第一行乘以某个比例因子，从 而使系数a21，a31，a41变为零。再用比例因子（又称之为乘子）代替这些零 位。对于第二行，乘子是a21/a11，因为第二行减去第一行乘以a21/a11，a21位 正好为零。由于在消去过程中a22，a23，a24的值也会随之改变，因此我们将他 们变成蓝色。同样在消去a31和a41的过程中，a31和a41也被他们的乘子所代 替。在这一过程中第三行其余的位置的值也会随之改变，因此也将他们变为蓝 色。 用同样的方法处理第二行。计算消去第三行和第四行中x2 的乘子，并且用这 些乘子代替出现的零。并且注意在消去过程中改变的量，将他们改为绿色。最后 一步，便是用第三行消去第四行中的x3 ，更新第四行的各个位置，并且将a44变 为粉红色。 我们可以看到乘子在代替矩阵中的零的位置之后，在消去过程中他们并没有 改变。 矩阵分解 LU分解基础 算法 for i=1 到 n-1 {每一行 for j=i+1 到 n {每一要消去的目标行 M M ji ji M ii 对角元 for k=i+1 到 n {对角元后的元素 M ←M −M M j k j k j i ik 乘子 } } } SMA-HPC ©2003 MIT 矩阵分解 LU分解基础 对角占优矩阵的性质 A ）对一个对角占优的矩阵进行LU分解时不会 产生零对角元。 。 B ）严格对角占优矩阵经过LU分解它的各个位 置上的值增加不会超过2(n−1) SMA-HPC ©2003 MIT 定理：在对严格对角占优的矩阵进行高斯消元时 不会产生零对角元。 证明：1）求出第一步消元后的矩阵。 2 ）考察（n－1）×（n－1）的次矩阵。 仍然是完全对角占优矩阵。 第一步 第一步消元后的第二行