数值模拟导论-第四讲 线性稀疏矩阵的直接解法 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 乘子 } } } 对角元
矩阵分解 LU分解基础 对角占优矩阵的性质 A)对一个对角占优的矩阵进行LU分解时不会 产生零对角元。 B)严格对角占优矩阵经过LU分解它的各个位 置上的值增加不会超过2 SMA-HPC C2003 MIT
LU分解基础 SMA-HPC ©2003 MIT 矩阵分解 对角占优矩阵的性质 A）对一个对角占优的矩阵进行LU分解时不会 产生零对角元。 B）严格对角占优矩阵经过LU分解它的各个位 置上的值增加不会超过 ( 1) 2 n−
定理:在对严格对角占优的矩阵进行高斯消元时 不会产生零对角元。 证明:1)求出第一步消元后的矩阵。 2)考察(n-1)×(n-1)的次矩阵。 仍然是完全对角占优矩阵。 第一步④16 第一步消元后的第二行∑吗 21 21 0.a2 2.2 (12n 由此得出
定理： 在对严格对角占优的矩阵进行高斯消元时 不会产生零对角元。 证明： 1）求出第一步消元后的矩阵。 2）考察（ n － 1）×（ n － 1）的次矩阵。 仍然是完全对角占优矩阵。 第一步 第一步消元后的第二行 由此得出
应用 稀疏矩阵 空间珩架 空间珩架 节点矩阵 XXX XXXXX X 468 XX XXX X XXXX XXX XX ⅩXXX XX X 未知量:节点位置X 方程 合力=0 2x 2 block SMA-HPC C2003 MIT
稀疏矩阵 SMA-HPC ©2003 MIT 应用 空间珩架 空间珩架 节点矩阵 未知量 ：节点位置 方程： 合力＝0
应用 稀疏矩阵 电阻网 M2M4M-mm-ML m+1m+2m+3 m tWrw w (m-1)(m+1) 未知:节点电压 方程:电流和=0 SMA-HPC C2003 MIT
稀疏矩阵 SMA-HPC ©2003 MIT 应用 电阻网 未知： 节点电压 方程： 电流和＝0
电阻网是一种特殊情况,它的数学模型是偏微分方程。(我们将在以后 学习到)我们现在考察一下这个节点矩阵并注意矩阵中的非零数。从一个 4×4的例子中我们可以很容易看出矩阵的特点。一个4×4系统它的节点矩阵 如下: M xx xxx 三角带取决于结触结点之间沿栅格行的相互作用。与三角带相距4的非零数 是由行节点与三角带的耦合产生的
电阻网是一种特殊情况，它的数学模型是偏微分方程。（我们将在以后 学习到）我们现在考察一下这个节点矩阵并注意矩阵中的非零数。从一个 4 × 4的例子中我们可以很容易看出矩阵的特点。一个 4 × 4系统它的节点矩阵 如下： 三角带取决于结触结点之间沿栅格行的相互作用。与三角带相距 4的非零数 是由行节点与三角带的耦合产生的