《数值模拟导论-第三讲》由会员分享，可在线阅读，更多相关《数值模拟导论-第三讲（50页珍藏版）》请在金锄头文库上搜索。
1、数值模拟导论-第三讲求解线性系统的基本方法求解线性系统的基本方法 雅克比雅克比怀特怀特感谢感谢Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Jacob White解的存在和唯一性 高斯消元法解的存在和唯一性 高斯消元法 LU分解 对角元和等比级数 逐步逼近法 适应条件分解 对角元和等比级数 逐步逼近法 适应条件摘要摘要应用范围应用范围SMA-HPC 2003 MIT无电源或刚性支承无电源或刚性支承 对角和严格对角占优矩阵对角和严格对角占优矩阵 nn方阵方阵线性方程线性方程SMA-HPC 2003 MIT要求加权变量要求加权变量x，使得矩阵
2、，使得矩阵M各列的加权和等于右边的各列的加权和等于右边的b。线性方程线性方程SMA-HPC 2003 MIT疑问解答疑问解答给定给定 Mx=b 这个方程是否有解？ 解是否唯一？这个方程是否有解？ 解是否唯一？ 看是否有解看是否有解? 存在一组变量存在一组变量x1,.xn，使得：，使得：由此看出：只有当由此看出：只有当b在由在由M各列组成 的向量空间内，解才存在。各列组成 的向量空间内，解才存在。1122.NNx Mx Mx Mb+=?1122.NNx Mx Mx Mb+=?1122.NNx Mx Mx Mb+=?1122.NNx Mx Mx Mb+=?1122.NNx Mx Mx Mb+=?1
3、122.NNx Mx Mx Mb+=?1122.NNx Mx Mx Mb+=?线性方程线性方程SMA-HPC 2003 MIT疑问解答续疑问解答续解是否唯一？解是否唯一？ 假设存在非零的变量假设存在非零的变量，使得又如果，则使得又如果，则 M(x+y)=b。 由此可见：当且仅当矩阵由此可见：当且仅当矩阵M的各列向 量线性无关，方程解唯一。的各列向 量线性无关，方程解唯一。1122.NNy My My Mb+=?1122.NNy My My Mb+=?1,nyy线性方程线性方程SMA-HPC 2003 MIT疑问解答续疑问解答续 方阵方阵给定，其中给定，其中M为为N*N方阵方阵 如果对任意给定的
4、如果对任意给定的b，方程均有解，那么对每一 个，方程均有解，那么对每一 个b所对应的解都是唯一的。所对应的解都是唯一的。 因为对任意的因为对任意的b都有解，那么矩阵都有解，那么矩阵M列向量所组成的 向量空间必定是列向量所组成的 向量空间必定是N维向量空间。又因为矩阵维向量空间。又因为矩阵M有有N 列，所以矩阵列，所以矩阵M的列向量必定线性无关。的列向量必定线性无关。 各列向量相互线性不相关的方阵称之为非奇 异阵。各列向量相互线性不相关的方阵称之为非奇 异阵。高斯消元基础高斯消元基础SMA-HPC 2003 MIT重要工具重要工具用高斯消元法解线性方程Mxb=一种“直接”的方法 有限步求准确解（
5、不计 舍入误差）。 求解增广矩阵的精确解 计算所消耗的机时。高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 3*3方阵方阵高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 解题思路解题思路用矩阵的第一行消去第二和第三行的x11x高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 矩阵形式矩阵形式乘子乘子对角元对角元高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 消去第三行中的消去第三行中的X2乘子乘子对角元对角元高斯消元基础高斯消元基础SMA-HPC 2003 MIT举例说明举例说
6、明 符号简化表示符号简化表示高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 消去第三行的消去第三行的x2乘子乘子对角元对角元高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 形成的三角阵形成的三角阵高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 右边向量的变化右边向量的变化高斯消元法基础高斯消元法基础SMA-HPC 2003 MIT举例说明举例说明 组合各部分组合各部分LU分解基础分解基础SMA-HPC 2003 MIT解方程Mxb=第一步第二步 消元过程 解方程Lyb=第三步 回代过程 解方程Uxy=回顾
7、线性代数我们可以知道，一个矩阵回顾线性代数我们可以知道，一个矩阵A可以用高斯消去法分解成一个下三角阵和一个 上三角阵乘积的形式。高斯消去法的基本思想是用第一行消去除第一行外所有行中的可以用高斯消去法分解成一个下三角阵和一个 上三角阵乘积的形式。高斯消去法的基本思想是用第一行消去除第一行外所有行中的 x1，然后用第二行消去除第一，二行外所有行中的，然后用第二行消去除第一，二行外所有行中的x2，依此类推，从而将系统转化成为 上三角矩阵。在这里我们需要了解更多的关于高斯消去的知识。，依此类推，从而将系统转化成为 上三角矩阵。在这里我们需要了解更多的关于高斯消去的知识。LU分解基础分解基础SMA-HP
8、C 2003 MIT解方程Mxb=第一步第二步 消元过程 解方程Lyb=第三步 回代过程 解方程Uxy=回顾线性代数我们可以知道，一个矩阵回顾线性代数我们可以知道，一个矩阵A可以用高斯消去法分解成一个下三角阵和一个 上三角阵乘积的形式。高斯消去法的基本思想是用第一行消去除第一行外所有行中的可以用高斯消去法分解成一个下三角阵和一个 上三角阵乘积的形式。高斯消去法的基本思想是用第一行消去除第一行外所有行中的 x1，然后用第二行消去除第一，二行外所有行中的，然后用第二行消去除第一，二行外所有行中的x2，依此类推，从而将系统转化成为 上三角矩阵。在这里我们需要了解更多的关于高斯消去的知识。，依此类推，
9、从而将系统转化成为 上三角矩阵。在这里我们需要了解更多的关于高斯消去的知识。LU分解基础分解基础SMA-HPC 2003 MIT解三角矩阵解三角矩阵 矩阵特点矩阵特点第一个方程只有y1一个未知量第二 个方程只有y1和y2两个未知量LU分解基础分解基础SMA-HPC 2003 MIT解三角矩阵解三角矩阵 算法算法解三角矩阵方程是直接的但又是费时的。y1可以用一个除法运算直接求得，y2可以用一 乘法，一个减法，一个除法求得。一旦求得yk1，yk可以由k1步乘法，k2步加法，一 减法和一个除法求得。算法的运算数量是： N除法0加/减1加/减、N-1加/减0乘法1乘法N-1乘法 注释：求y1 求y2
10、求yn求y1 求y2 求yn（N-1）（N-2）加/减（N-1）（N-2）乘N除 N2步LU分解基础分解基础SMA-HPC 2003 MIT分解分解 图片图片上图便是上图便是LU分解的图形表示。第一步，用第一个方程消去第二到第四方程中的分解的图形表示。第一步，用第一个方程消去第二到第四方程中的x1。这一 过程我们用除第一行外的各行分别减去第一行乘以某个缩放因子，从而使系数。这一 过程我们用除第一行外的各行分别减去第一行乘以某个缩放因子，从而使系数a21， a31，a41变为零。再用缩放因子（又称之为乘子）代替这些零位。对于第二行，乘子是变为零。再用缩放因子（又称之为乘子）代替这些零位。对于第二
11、行，乘子是 a21/a11，因为第二行减去第一行乘以，因为第二行减去第一行乘以a21/a11，a21位刚好为零。由于在消去过程中位刚好为零。由于在消去过程中 a22，a23，a24的值也会随之改变，因此我们将他们变成蓝色。同样在消去的值也会随之改变，因此我们将他们变成蓝色。同样在消去a31和和a41的 过程中，的 过程中，a31和和a41也被他们的乘子所代替。在这一过程中第三行其余的位置的值也会随 之改变，因此也将他们变为蓝色。 用同样的方法处理第二行。计算消去第三行和第四行中也被他们的乘子所代替。在这一过程中第三行其余的位置的值也会随 之改变，因此也将他们变为蓝色。 用同样的方法处理第二行。
12、计算消去第三行和第四行中x2的乘子，并且用这些乘子 代替出现的零。注意在消去过程中改变的量，将他们改为绿色。最后一步，便是用第三 行消去第四行中的的乘子，并且用这些乘子 代替出现的零。注意在消去过程中改变的量，将他们改为绿色。最后一步，便是用第三 行消去第四行中的x3，更新第四行的各个位置的值，并且将，更新第四行的各个位置的值，并且将a44变为粉红色。 我们可以看到乘子在代替矩阵中的零的位置之后，在消去过程中他们的值并没有改 变。变为粉红色。 我们可以看到乘子在代替矩阵中的零的位置之后，在消去过程中他们的值并没有改 变。LU分解基础分解基础SMA-HPC 2003 MIT分解分解 算法算法fo
13、r i=1到 n-1 每一行 for j=i+1到 n 每一要消去的目标行ji ji iiMMM= Mii为对角元 for k=i+1到 n 对角元后面的元素jkjkjijkMMM M乘子 SMA-HPC 2003 MIT分解分解 对角元为零对角元为零LU分解基础分解基础第i步第第i行第行第j行行如果Mii0怎么办？不能得到jiiiMM 做一下简单变形（部分对角元） 00iiiiIfMfindMji= 第j行和第i行交换。LU分解基础SMA-HPC 2003 MIT分解分解 零对角元零对角元两重要定理两重要定理1）只有当）只有当M为非奇异矩阵时列主元法（交换行）才 能有效。为非奇异矩阵时列主元
14、法（交换行）才 能有效。2）对严格对角占优矩阵）对严格对角占优矩阵LU分解将不会产生零对角 元。分解将不会产生零对角 元。定理： 在对严格对角占优的矩阵进行高斯消元时 不会产生零对角元。 证明：1）求出第一步消元后的矩阵。 2）考察（n1）（n1）的次矩阵。仍然是完全对角占优矩阵。 第一步 第一步消元后的第二行由此得出LU分解基础分解基础SMA-HPC 2003 MIT数值问题数值问题 小对角元小对角元特例特例我们能够解释这种现象吗？我们能够解释这种现象吗？为了求出精确解，我们进行第一步消元：出第二步回代：求出：在浮点运算中LU分解基础SMA-HPC 2003 MIT数值问题数值问题 小对角元
15、小对角元 浮点运算的一个性质双精度数浮点运算的一个性质双精度数主要问题：主要问题：结论：结论： 避免大小数之间相加减避免大小数之间相加减符号位符号位有效数位有效数位8LU分解基础SMA-HPC 2003 MIT数值问题数值问题 小对角元小对角元回过头来看这个例子回过头来看这个例子LU分解基础SMA-HPC 2003 MIT数值问题数值问题 小对角元小对角元列主元法减小误差 如果maxiiji j iMM那么第i行和最大的jiM所在行交换可以看出乘子变小了这一项被圆整列主元法是怎么起作用的应看下面：求得我们知道不用列主元法时是，圆整为右边的数值3被圆整时忽略掉了，而现在他还保 留着。继续回代过程：LU分解基础SMA-HPC 2003 MIT数值问题数值问题 小对角元小对角元如果在如果在LU分解过程中，矩阵是对角占优或采 用了列主元法来减小舍入误差那么存在以下的特 点：分解过程中，矩阵是对角占优或采 用了列主元法来减小舍入误差那么存在以下的特 点：1）乘子总是最小的。2）LU因子各位上的最大值将小于等于原始矩阵各位最大值的(1)2n倍列主元法是怎么起作用的应看下面：求得我们知道不用列主元法时是，圆整为右边的数值3被圆整时忽略掉了，而现在他还保 留着。继续回代过程：逐步逼近法逐步逼近法SMA-HPC 2003 MIT实例实例
