数值模拟导论-第四讲 线性稀疏矩阵的直接解法 Luca daniel 感谢 Deepak ramaswamy, Michal Rewienski Karen Very and Jacob White
数值模拟导论 -第四讲 线性稀疏矩阵的直接解法 Luca Daniel 感谢Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Jacob White
概述 回顾LU分解法 稀疏矩阵 一珩架和节点,电阻网,3d热流 三角矩阵分解 一一般的稀疏矩阵分解 填充和重排列 一图表逼近 稀疏矩阵数据结构 一散布 SMA-HPC C2003 MIT
• 回顾LU分解法 • 稀疏矩阵 • 三角矩阵分解 • 稀疏矩阵数据结构 概述 SMA-HPC ©2003 MIT —珩架和节点，电阻网，3d热流 ―一般的稀疏矩阵分解 ―填充和重排列 —图表逼近 —散布
分解 LU分解基础 图片 M,M,M,M, M M MM M 22 23 31 M M M M 3334 22 M M 42 M M M SMA-HPC C2003 MIT
LU分解基础 SMA-HPC ©2003 MIT 分解 图片
上图便是LU分解的图形表示。第一步,用第一个方程消去第二到第四方程中 的x1。这一过程我们用除第一行外的各行分别减去第一行乘以某个比例因子,从 而使系数a21,a31,a41变为零。再用比例因子(又称之为乘子)代替这些零 位。对于第二行,乘子是a21/a11,因为第二行减去第一行乘以a21a11,a21位 正好为零。由于在消去过程中a2,a23,a24的值也会随之改变,因此我们将他 们变成蓝色。同样在消去a31和a41的过程中,a31和a41也被他们的乘子所代 替。在这一过程中第三行其余的位置的值也会随之改变,因此也将他们变为蓝 色 用同样的方法处理第二行。计算消去第三行和第四行中ⅹ2的乘子,并且用这 些乘子代替出现的零。并且注意在消去过程中改变的量,将他们改为绿色。最后 步,便是用第三行消去第四行中的x3,更新第四行的各个位置,并且将a44变 为粉红色。 我们可以看到乘子在代替矩阵中的零的位置之后,在消去过程中他们并没有 改变
上图便是LU分解的图形表示。第一步，用第一个方程消去第二到第四方程中 的x1。这一过程我们用除第一行外的各行分别减去第一行乘以某个比例因子，从 而使系数a21，a31，a41变为零。再用比例因子（又称之为乘子）代替这些零 位。对于第二行，乘子是a21/a11，因为第二行减去第一行乘以a21/a11，a21位 正好为零。由于在消去过程中a22，a23，a24的值也会随之改变，因此我们将他 们变成蓝色。同样在消去a31和a41的过程中，a31和a41也被他们的乘子所代 替。在这一过程中第三行其余的位置的值也会随之改变，因此也将他们变为蓝 色。 用同样的方法处理第二行。计算消去第三行和第四行中x2的乘子，并且用这 些乘子代替出现的零。并且注意在消去过程中改变的量，将他们改为绿色。最后 一步，便是用第三行消去第四行中的x3，更新第四行的各个位置，并且将a44变 为粉红色。 我们可以看到乘子在代替矩阵中的零的位置之后，在消去过程中他们并没有 改变
矩阵分解 LU分解基础 算法 fori=1到n1{每一行 forj计+1到n{每一要消去的目标行 M Mn对角元 fork=+1到n{对角元后的元素 M tM-M.M ik 乘子 SMA-HPC C2003 MIT
LU分解基础 SMA-HPC ©2003 MIT 矩阵分解 算法 for i=1 到 n-1 {每一行 for j=i+1 到 n {每一要消去的目标行 ji ji ii M M M = for k=i+1 到 n {对角元后的元素 M jk ← M MM jk − ji ik 乘子 } } } 对角元