第六章 线性方程组的数值解法 课件.ppt

第六章 线性方程组的数值解法,在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组求解线性方程组的数值方法简介；,高斯(Gauss)消去法、列主元高斯消去法；,三角分解法（高斯消去法的变形）,求解线性方程组的迭代法；,本章主要内容,第一节 引言,设线性方程组,简记 AX=b,(2)莱姆规则在理论上尽管是完善的, 但在实际应用中存在很大的困难，或者说实际计算中没有什么实用价值本章讨论求解线性方程组的数值方法线性方程组的数值求解方法有两大类：,一类称为直接法，就是通过有限个步骤直接计算出问题的“精确解”的方法（不计原始数据的误差和计算过程的舍入误差）但实际计算中误差总是存在的，因而该方法求出的也只能是近似解此法适用于中低阶方程组另一类称为迭代法，它是把线性方程组的解看作是某种迭代过程的极限，通过有限步迭代求出问题“精确解”的具有指定精度的近似解的方法。

此方法适用于高阶、稀疏矩阵（零元素较多的矩阵）对应的方程组第二节 高斯消去法,高斯消去法是一种古老的直接法，由它改进得到的选主元消去法，是目前计算机上最常用的求低阶稠密线性方程组的有效方法其基本思想是通过消元将线性方程组的求解问题转化成三角形式方程组的求解问题一、高斯消去法的基本思想,用例子来说明高斯消去法的基本思想,例1：解方程组,第一步：-2 x（1）+（2）； -1 x（1）+（3）得,第二步： x（5）+（6）,回代得：x=1,2,3T,二、求解过程,高斯消去法实现的目标： 记系数矩阵为： 记右端向量为：,,增广矩阵,. 消元得到上三角形方程组,对一般的n阶方程组，消去过程分n-1步：第一步消去a11下方元素第二步消去a22下方元素，，第n-1步消去an-1,n-1下方元素2. 回代得方程组的解,举例 用消元法解方程组 第一步：-2 x（1）+(3)得,第二步：1 x（2）+（4） 回代得：x=1,2,3T,三、高斯消元法的计算量 （1）消元过程乘除法的计算量 除法计算量：第k步消元的除法计算量为n-k，其中k=1,2,3,,n-1 所以：除法计算量为： 乘法计算量：第k步消元法的计算量为： 该步每行从k1个数开始到n1个数都需乘一个数（lik）共有：n+1-k次乘法； 该步共有n-k行。

所以乘法计算量为：,,所以高斯消元过程乘除法的计算量为：,,,（2）消元过程加减法的运算量 可以从第k步消元计算过程得到： 第k步消元时候，从第k+1行开始到第n行为止；每行的第k+1个数开始到第n+1个数止进行加法运算 所以该步的加减法次数为：(n-k)(n+1-k) 消元过程总的加减法运算次数为：,（3）回代过程的计算量 乘除法的计算量为： 加减法的计算量为： （4）高斯消元法总过程的计算量 乘除法的计算量为： 加减法的计算量为：,与Grammer法则相比较，Gauss消去法的计算量大大减少计算量过大的问题得到了根本解决四、顺序高斯消去法存在的问题,高斯消去法消元过程中，是按顺序通过，，，， 作为除数来达到消元目的的在实际计算时，由于舍入误差的影响，计算结果会改变很大，甚至完全失真解下方程组：P119 准确到九位小数的解是x1=0.250 001 875，x2=0.499 998 749，若在4位计算机上按高斯消去法求解解： 回代解得 =0.5， =0，显然严重失真 造成这种结果的原因，就是小主元的出现用它做除数产生大乘数，出现大数吃小数产生舍入误差，从而 有误差代回第一个方程 时，因10-6x1+2x2=1， 10-6 +2 =1 该两个式相减得到：,表明 x2的误差被放大2000 000倍， x1 自然失真。

根据误差知识，绝对值较小的数做除数会带来较大的误差，而绝对值较大的数做除数具有较好的数值稳定性，也就是说，计算结果受运算过程中舍入误差的影响较小所以顺序高斯消去法常常会使计算结果产生较大的误差，因而提出了列主元素消去法五、列主元素高斯消去法,基本思想：为避免用绝对值较小的元素作除数，在每次消元前，选择绝对值最大的元素作为约化主元素(作为除数)，在第k步的第k列的元素中选主元，即在其中找出绝对值最大的元素 ，然后交换第k和第p行，继续进行消去过程交换行相当于改变方程顺序，不会影响原方程组的解这种消去法称为列主元消去法例：,例求解方程组,（1）用顺序高斯消去法,（2）用列主元消去法,3、例题 P120 例63,第三节 向量范数和矩阵范数,向量范数和矩阵范数是研究迭代法及其收敛性、估计方程组近似解的误差的一种有力工具，本节简要介绍其相关概念 一、向量范数 1、向量范数的定义 （1）绝对值 范数的最简单的例子，是绝对值函数： 并且有三个熟知的性质： x 0 x 0 x = 0当且仅当x = 0 ax = a x a为常数 x+ y x + y ,（2）范数的另一个简单例子是二维欧氏空间的长度 欧氏范数也满足三个条件： 设x = (x1, x2) x 0 x 0 ax = a x a为常数 x+ y x + y 前两个条件显然，第三个条件在几何上解释为三角形一边的长度不大于其它两边长度之和。

因此，称之三角不等式勾股定理）,（3）下面我们给出n维空间中向量范数的概念： 设X = (x1, x2, , xn)T，记为X R n 定义1：设X R n， 表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质： 非负性：即对一切X R n，X 0, 0 齐次性：即为任何实数a R，X R n， 三角不等式：即对任意两个向量X、Y R n，恒有,2、常用的范数 设X = (x1, x2,, xn)T，则有： （1）向量的1范数 （2）向量的2范数 （3）向量的无穷范数 不难验证，上述三种范数都满足定义的条件3、举例 例1：求向量范数 解：,例2：P128 设下x=1 2 3T，求x的1范数，2范数和无穷范数 解：根据定义可以得到：,二、矩阵范数 1、定义 对于任意n阶方阵A，按一定的规则由一实数与之对应，记为 ，若 满足： 则称 为矩阵A的范数正定,奇次,三角不等,2、矩阵范数与向量范数的相容性 对于任意的n维向量x，都有： 这一性质称为矩阵范数与向量范数的相容性3、常用的矩阵范数 （1）矩阵的1范数,,,（2）矩阵的无穷范数,,,（3）矩阵的2范数 矩阵的谱半径： 矩阵B的诸特征值为： 则特征值的最大绝对值称为B的谱半径，记为： 则： 矩阵的2范数其实为ATA的谱半径的1/2次方。

4、矩阵的收敛性,5、举例 例1：求矩阵A的 各常用范数 解：,先求ATA的特征值： 特征方程为： 解之可得ATA特征值：,可得： 所以： 对各个常用范数比较：,,容易计算,,计算较复杂,对矩阵元素的 变化比较敏感,使用最广泛,性质较好,第四节 解线性方程组的迭代法,迭代法也是解线性代数方程组的一类重要方法这类方 法主要适用于大型稀疏线性方程组的求解其基本思想是通 过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组 的解 因此，要解决的基本问题是： （1） 如何构造迭代格式 （2）迭代序列是否收敛,一、迭代法的基本思想 设有线性代数方程组： a11x1+a12x2++a1nxn=b1 a21x1+a22x2++a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2++annxn=bn 用矩阵表示： Ax =b 其中A 为系数矩阵，非奇异且设aii0；b为右端，x为解向量 做方程组的一个等价变换为：x=Bx+f,任取初始向量x(0)，按照下列公式构造迭代序列： 结论：如果迭代序列 收敛，则它一定收敛到方程组的解 概念：迭代公式： 迭代矩阵：B 不同的迭代矩阵构成不同的迭代法，先介绍两种迭代法：雅可比迭代法和高斯赛得尔迭代法。

二、雅可比（ Jacobi ）迭代法 1、公式 方程组： a11x1+a12x2++a1nxn=b1 a21x1+a22x2++a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2++annxn=bn,迭代格式：,,,迭代格式中B0，f 与D、 L、 U、 b的关系为：,编程实现,2、举例 例1：用Jacobi迭代法求解方程组,误差不超过1e-4 解：,则：,即：雅克比迭代公式为：,即 ：,可以得到：,依此类推,得方程组满足精度的解为x12,迭代次数 为12次,x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004 x12 = 3.0000 2.0000 1.0000 d = 3.0647e-005,例2：用Jacobi迭代法求解方程组的解 P131,三、高斯赛德尔迭代法 1、高斯赛德尔迭代法的推导 分析Jacobi迭代法的迭代过程，将其公式细化,,三、高斯赛德尔迭代法,观察雅可比迭代法发现：,高斯赛德尔迭代格式：,上式称为Gauss-Seidel迭代法,简称G-S法,2、举例： 用高斯赛德尔迭代法求解方程组,误差不超过1e-4 解：,通过迭代，至第7步得到满足精度的解x7 从该例可以看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要高,x1 =2.5000 2.0909 1.2273 d =3.4825 x2=2.9773 2.0289 1.0041 d =0.5305 x3 =3.0098 1.9968 0.9959 d =0.0465 x4 =2.9998 1.9997 1.0002 d =0.0112 x5 =2.9998 2.0001 1.0001 d =3.9735e-004 x6 =3.0000 2.0000 1.0000 d =1.9555e-004 x7 =3.0000 2.0000 1.0000 d =1.1576e-005,四、迭代法的收敛性 1、迭代法收敛的充要条件 设解线性方程组的迭代格式： 而线性方程组的精确解为 ： 将两式相减,得：,因此迭代法收敛的充要条件： 可转变为： 有引理： 即：,,则有定理，迭代格式收敛的充要条件为：,,2、迭代收敛的充分条件 因为矩阵的谱半径不超过其任一种算子范数,即 于是又可得到 且：,,,3、迭代收敛的充分条件和充要条件的说明 由迭代收敛的充分条件：如果对于任一矩阵范数有 则由迭代所产生的序列： 必收敛到方程组的解。

由此得到：,、举例：判别下列方程组用J法和G-S法求解是否收敛 解：(1) 求Jacobi法的迭代矩阵,显然： 用充要条件进行判断： 所以： 即Jaobi迭代法收敛,(2) 求Gauss-Seidel法的迭代矩阵 用必要条件进行判断： 所以Gauss-Seidel迭代法发散 在前面的例子中,G-S法收敛速度比J法要高 但该例却说明G-S法发散时而J法却收敛 因此,不能说G-S法比J法更好,、对于某些特殊矩阵,从。