《数值分析课件完整版第二章线性方程组的数值解法》由会员分享，可在线阅读，更多相关《数值分析课件完整版第二章线性方程组的数值解法（122页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性方程组的数值解法,2.1 消元法,2.2 直接分解法,2.3 向量和矩阵的范数,2.4 雅可比迭代,2.5 高斯-赛德尔迭代,2.6 松弛迭代,直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)（ Gauss消去法及其变形、矩阵的三角分解法）,迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）,直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。 迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一
2、些高阶方程组。,线性方程组的数值解法,AX = b,（2.1）,1三角形方程组的解法-回代法（对角型方程组略）,（2.2）,（2.3）,2.1 消元法,2顺序高斯消去法,基本思想：通过消元将上述方程组 化为三角形方程组进行求解。,（1）消元过程,其中,第一步：若,用,乘第一行,加到第i行中，得到,第二步：若,用 ., ,第k步：若,用,乘第k行,加到第i行中，得到,其中,第n-1步： ,（2）回代过程,若,则,顺序高斯消去算法,高斯消去法计算复杂度,顺序Gauss消去法可执行的前提,定理 1 给定线性方程组 ，如果n阶方阵 的所有顺序主子式都不为零，即 则按顺序Gauss消去法所形成的各主元素
3、 均不为零，从而Gauss 消去法可顺利执行。,注：当线性方程组的系数矩阵为对称正定或严格对角占优阵时，按Gauss消去法计算是稳定的。,顺序Gauss消去法计算过程中的 akk(k) 称为主元素，在第k步消元时要用它作除数,则可能会出现以下几种情况,1、若出现 akk(k) 0，消元过程就不能进行下去。,2、akk(k) 0 ，消去过程能够进行，但若|akk(k)| 过小，也会造成舍入误差积累很大导致计算解的精度下降。,例2-1 在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组,此方程组具有四位有效数字的精确解为,x117.46，x245.76，x35.546,解 用顺序Gaus
4、s消去法求解，消元过程如下,经回代求解得 x35.546，x2100.0，x1104.0,和此方程组的精确解相比,x35.546 ，x245.76， x117.46,有较大的误差。,对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和 x2100.0 已完全失真。,为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。,写出原方程组的增广矩阵：,针对第一列找出绝对值最大的元素，进行等价变换：,求得方程的解为：x35.546，x245.76，x117.46,
5、精确解为： x35.546 ，x245.76， x117.46,由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。,列主元Gauss消去法与顺序Gauss消去法的不同之处在于：,后者是按自然顺序取主元素进行消元,前者在每步消元之前先选取主元素然后再进行消元,3、列主元Gauss消去法计算步骤：,1、输入矩阵阶数n，增广矩阵 A(n,n+1);,2、对于,(1) 按列选主元：选取 l 使,(2) 如果 ，交换 A(n,n+1) 的第k行与第l 行元素,(3) 消元计算 ：,3、回代计算,从2.1中讨论可知，顺序Gauss消去法的消元过程是将增广
6、矩阵A，bA（1），b（1）逐步化为矩阵A（n），b（n）。,现在说明，在消元过程中，系数矩阵AA（1）是如何经矩阵运算化为上三角矩阵A（n）。即,用矩阵运算的观点来看，消元的每一步计算等价于用一个单位下三角矩阵左乘前一步化得到的矩阵。,2.2 直接分解法,若 ，令 ， i2，3，n，,得到下三角矩阵,施行第一步消元，我们得到,若 ，令 ， i2，3，n，则有,施行第二步消元，我们得到,如此下去，施行第n1步消元，得到,(n),由此可见，在顺序Gauss消去法的过程中，系数矩阵 AA（1）经过一系列单位下三角矩阵的左乘运算化为上 三角矩阵A（n），即,这时,由,得,令,容易验证,则从顺序Gau
7、ss消去法的矩阵运算表示式可知，系数矩阵A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，即,其中,第一个方程组的系数矩阵为下三角矩阵，第二个方程组的系数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求解结果如下：,我们将A=LU 称为矩阵A的三角分解,这时线性方程组为：,令,则有,对于,由,解得,对于,由,求得,可以看出对于方程组：,只要对系数矩阵作了三角分解：,由这个简单的计算过程可知，系数矩阵的三角分解很关键，如何进行三角分解更容易？下面介绍几种方法。,通过如下两组公式很容易求解：,注： （1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解 （2）L
8、 为一般下三角阵而 U 为单位上三角阵的分解称为Courant 分解。,定理2 设n阶方阵A的各阶顺序主子式不为零，则存在惟一单位下三角矩阵L和上三角矩阵U使ALU。,2.2.1 Doolittle分解法,前已述及，若在顺序Gauss消去法的过程中，每步消元的主元素 akk(k)0，则矩阵A可分解为ALU，L为单位下三角矩阵，U为上三角矩阵，此分解称为A的 Doolittle（杜利特尔）分解。可以证明akk(k) 0的充要条件是A的各阶顺序主子式不为零，于是有如下定理。,下面介绍矩阵三角分解的Doolittle分解方法。,根据 A=LU 有等式成立：,比较等式两端对应元素，有,可以解得：,当
9、i=1 时,当 j=1 时,当 i 1 时,当 j 1 时,于是，对于矩阵的三角分解：,可按照以下公式进行：,对于 i=2,3, ，n, 计算,（2.4）,（2.5）,（2.6）,用计算公式(2.5)、(2.6)对矩阵A作的分解(2.4),称作Doolittle分解。,下面，我们对具体矩阵进行Doolittle 三角分解。,为了表示和存储方便，可以将分解后的两个矩阵用一 个矩阵表示,例2-2 利用Doolittle三角分解法分解矩阵,解：分解时用到如下公式,1,2,3,4,1,1,1,2,6,12,3,7,6,24,6,24,可以写成：,这时，矩阵的三角分解,如果我们要求解方程组,则由,得到,
10、由,解得,再由,求得方程组的解：,（2.7）,如下的计算公式(2.5)、(2.6)与(2.7)就是求解方程组Axb 的 Doolittle 三角分解方法,包括分解和回代两步。,（2.5）,（2.6）,关于具体求解过程可以按下面例子的方法进行。,例2-3 利用Doolittle三角分解方法解线性方程,解: 进行三角分解ALU，按照公式(2.5)与(2.6)可以对增广 矩阵A,b作三角分解:,1 2 3 -2,-3,2,2,-3,-1,3,3,17,得到,1 2 3 -2,-3,2,2,-3,-1,3,3,17,这时，相应的方程组为：,例2-4 利用Doolittle三角分解方法解线性方 程组,解
11、：对增广矩阵进行三角分解,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,等价方程组通过分解式容易写出为：,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,解得,先计算L 的第一列，再计算U 的第一行，其余类此。类似于多利特尔分解法，得到：对 k=1，2，n,2.2.2 Courant 分解,实现 A=LU，则 Ax=b 可以化为 LUx=b。 令 Ux=y，则 Ly=b。 由 Ly=b解出 yi: 再由 Ux=y 解出 xi:,注：为保证LU分解能够进行，要求 ，既要求A的 所有顺序主子式不为
12、零，而线性方程组有解，只须|A| 0即可。为取消此限制，采用类似列主元消元法处理。,例2-5 用库朗分解求解方程组：,解 设 A=LU，即,解下三角方程组 Ly = b，即 解(单位)上三角方程组 Ux= y，即,2.2.3 追赶法,追赶法是专门用于求解三对角方程组的。这类方程组经常出现于用差分方法或有限元方法求解二阶常微分方程边值问题、热传导问题及三次样条函数插值等问题，三对角方程组Axb的系数矩阵具有如下形式：,在此条件下，可对A进行三角分解，设,比较矩阵的对应元素，根据矩阵乘法规则，可得到,并且满足,条件(i)保证方程组不能降阶，条件(ii)保证三角分解可做到底。,i-1列,i 行,i
13、+1 列,i-1列,i -1行,i-1列,i -1行,i-1列,于是，由以上结果：,分别得到：,也就是说,用这一组公式可以对三对角矩阵进行三角分解：,对于三对角方程组Axb，设A的三角分解为ALU，则原方程组等价于,Lyb，Uxy,由Lyb，即,解得,解得,由Uxy，即,于是，对于三对角矩阵方程组 Ax=b，如下的两组公式便构成了构成了解三对角方程组的追赶法：,例2-6 用追赶法求解三对角方程组,解 : 首先进行系数矩阵的三角分解,求解方程组Lyy，即,得 到 y11/2，y21/3，y31/4，y41,再求解方程组 Uxy，即,得 到 x11，x21，x31，x41,当三对角矩阵A满足对角占
14、优条件时，追赶法是数值稳定的。,追赶法具有计算程序简单，存贮少，计算量小的优点。,解三对角方程组Axb的追赶法，用四个一维数组存放方程组数据 ai，bi， ci， di , di常数项。,输入 方程组数据 ai， bi， ci，di，n,输出 计算解x（x1，x2，xn）T,根据以下算法编写程序,1,2 对于i1，2，n1，计算,3,4,5 输出 x1，x2，xn,2.3 向量和矩阵的范数,向量的范数,向量范数的连续性定理、等价性定理,矩阵的范数、算子范数,矩阵的谱半径,矩阵的条件数,为了研究线性方程组的近似解的误差估计和迭代法的 收敛性, 我们需要对Rn中的向量(或Rnn中的矩阵)的 大小引
15、进某种度量向量(或矩阵)的范数.,先考虑Rn中向量的长度, 然后可定义向量(或矩阵)的范数.,向量的范数,(1) 正定性：,等号当且仅当,时成立；,(2) 齐次性：,(3) 三角不等式：,则称,为向量,的范数或模.,由(3)得,(4),几种常用范数,(无穷范数),(1-范数),(2-范数),(p-范数),可以验证它们都是范数. 易见前三种范数是p-范数的特殊情况,例2-8 计算向量,的几种常用范数,向量范数的连续性定理、等价性定理,向量范数的连续性定理、等价性定理,矩阵的范数、算子范数,定义4(矩阵的范数),(1) 正定性：,等号当且仅当,时成立；,(2) 齐次性：,(3) 三角不等式：,则称,为 矩阵,的范数或模。,（相容性条件）,诱导出的常用范数有：,它们满足如下相容关系：,例7 计算矩阵,的几种常用范数,矩阵的谱半径,矩阵的条件数,求解 时，A 和 的误差对解 有何影响？, 设 A 精确， 有误差 ，得到的解为 ，即,绝对误差放大因子,又,相对误差放大因子,线性方程组的性态和解的误差分析, 设 精确，A有误差 ，得到的解为 ，即,(只要 A充分小，使得,大,定义7：设A 为n 阶非奇矩阵，
