计算方法第六章线性方程组的数值解ppt课件.pptx
第六章 线性方程组的数值求解,6.1 高斯顺序消去法6.2 高斯列主元消去法6.5 追赶法6.6 向量与矩阵的范数6.7 误差分析6.8 迭代法,引言,线性方程组的数值解法一般有两类：1、直接解法：经过有限次的算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。本章主要研究此类问题的解法。2、迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法。迭代法具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。,6.1 高斯顺序消去法,求解三角方程组后,得,高斯顺序消去法的条件,矩阵三角分解法,Ax=b是线性方程组, A是nn方阵, 并设A的各阶顺序主子式不为零。令 A(1)=A, 当高斯消元法进行第一步后, 相当于用一个初等矩阵左乘A(1) 。不难看出，这个初等矩阵为,重复这个过程，最后得到,一般地,这就是说，高斯顺序消去法实质上产生了一个将A分解为两个三角形矩阵相乘的因式分解，于是我们得到如下重要定理。,当A进行LU分解后，Ax=b就容易解了. 即Ax=b等价于:,6.2 高斯列主元素消去法,列主元消去法,在四位浮点十进制数的计算机上, 结果为 x1=0 x2=1,例5 用高斯顺序消元法解线性方程组，并假设求解是在四位浮点十进制数的计算机上进行,0.0001x1+x2=1 x1+x2=2,9999 x2=9998,0.0001x1+x2=1,解： 消元，得,这与实际结果相差甚远。,假设求解是在四位浮点十进制数的计算机上进行,0.0001x1+x2=1 x1+x2=2,将两个方程对调，得 x1+x2=2 0.0001x1+x2=1,在四位浮点十进制数的计算机上,上式为 x1+x2=2 即 x1+x2=2 (0.1000101-0.00001 101）x2=1 x2=1,（1-0.0001) x2=1,x1+x2=2,消元，得,解得： x1=1， x2=1,现在我们再用列主元法解例3,6.5 追赶法 在一些实际问题中， 例如解常微分方程边值问题，热传导方程以及船体数学放样中建立三次样条函数等问题，都会要求解系数矩阵为对角占优的三对角线方程组,其中|i-j|1时, 系数矩阵元素aij=0,且满足如下的对角占优条件:(1)|b1|c1|0,|bn|an|0(2)|bi|ai|+|ci|, aici0, i=2,3,n-1.,6.6 向量和矩阵的范数,定义( 向量范数) x 和 y 是 Rn 中的任意向量 , 向量范数是定义在 Rn上的实值函数, 它满足:,(1) x 0, 并且当且仅当 x=0 时, x =0;,(2) k x =|k| x , k 是一个实数;,(3) x + y x + y ,常使用的向量范数有三种,设 x=(x1,x2,xn)T,常使用的矩阵范数有三种,设 x=(x1,x2,xn)T,6.7 误差分析,Ax=b的误差分析,迭代法适用于求解大型稀疏的线性方程组，其基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题是：1. 如何构造迭代格式 2.迭代序列是否收敛,一 . 基本迭代法的格式及收敛性二 . 几种实用的基本迭代法三 . 应用实例,6.8 迭代法,一 . 基本迭代法的格式及收敛性,设有线性代数方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2+annxn=bn,用矩阵表示： Ax =b A 为系数矩阵，非奇异且设aii0；b为右端，x为解向量,注：分解A是一个重要问题,在Rn中，点列的收敛等价于每个分量的收敛。即,二.几种实用的基本迭代法,1、Jacobi迭代法2、Gauss-Seidel迭代法3、超松弛迭代法（SOR),1、Jacobi 迭代,Jacobi迭代矩阵,推导其分量形式,第i个方程除以aii(i =1,2,n),得,Jacobi迭代的分量形式,则 x(k+1)=BJx(k)+g ，这里 BJ=D-1(L+U) , g=D-1b,Jacobi迭代公式（分量形式）,给出初始向量 x(0), 即可得到向量序列： x(1),x(2),x(k),若 x(k) x*, 则x*是解。,例1：设方程组为,解：Jacobi迭代格式为,试写出其Jacobi分量迭代格式以及相应的迭代矩阵，并求解。,故Jacobi迭代矩阵为,取 x(0)=(0,0,0)t, e=10-3,终止准则：x(k)-x(k-1)e,2、高斯塞德尔迭代法,例2：设方程组为,解： Gauss-Seidel迭代格式为,试写出Gauss-Seidel迭代格式.,2、Gauss-Seidel迭代法,Gauss-Seidel迭代的分量形式,推导Gauss-Seidel迭代法的矩阵形式,Gauss-Seidel迭代矩阵,Gauss-Seidel迭代公式,给出初始向量 x(0), 即可得到向量序列： x(1),x(2),x(k),若 x(k) x*, 则x*是解。,Ab.ma(1,1)=1/2+1/4+1/3;a(1,2)=-1/4;a(1,3)=-1/3;a(2,1)=a(1,2);a(2,2)=1/4+1/3+1/5;a(2,3)=-1/5;a(3,1)=a(1,3);a(3,2)=a(2,3);a(3,3)=1/3+1/5+1/3;b(1)=20/2;b(2)=0;b(3)=5/3;,function x,k=gs(A,b)n n=size(A);x=zeros(1,n);for k=1:1000 error=0; for i=1:n s=0;xb=x(i); for j=1:n if i=j,s=s+A(i,j)*x(j);end end x(i)=(b(i)-s)/A(i,i); error=error+abs(x(i)-xb); endif error/n0.0001,break;endendfprintf(k.no.=%3.0f,error=%7.2en,k,error),|A|=12+4-15=1, |2D-A|=12-4-15=-7,例:讨论用Gauss-Seidel迭代法求解方程组Ax=b时的收敛性，已知,解:(1)对A：不是严格对角占优的矩阵，无法用充分准则I，(2)考虑充分准则II，计算Jacobi迭代矩阵BJ=D-1（L+U）=I-D-1A,不满足充分准则II，故无法判断。,先求出Gauss-Seidel迭代矩阵 BG=(D-L)-1U,(3)考虑用准则II的充分条件,不满足准则II的充分条件，故无法判断。,(4)再用准则I的充要条件,例:讨论用Jacobi迭代法和Gauss-Seidel迭代法求解方程组Ax=b时的收敛性，如果收敛，并比较哪种方法收敛较快，其中,解: (1)对Jacobi方法，迭代矩阵,(2)对Gauss-Seidel方法，迭代矩阵,Gauss-Seidel方法比Jacobi方法收敛快。,3、超松弛迭代法（SOR法）,以三阶方程为例，推导超松弛迭代法（SOR法）的分量形式,SOR迭代公式（分量形式）,推导SOR迭代格式的矩阵形式（以三阶方程为例）,推导SOR迭代格式的矩阵形式,SOR法收敛性的结论：,（1）SOR方法收敛的必要条件为0 2,（2）若系数阵A对称正定，则当0 2时， SOR方法收敛,（3）若系数阵A严格对角占优，则当0 1时， SOR方法收敛。,在计算机上采用动态计算形式,(1) x(i)=0 (i=1,2,n) (2)对k =1,Kmax,循环计算到第(7)步(3)置ER=0,第六章解线性代数方程组的迭代法,内容提要6.1 引言6.2 基本迭代法6.3 迭代法的收敛性,即AX=b 其中A为非奇异矩阵，当A为低阶稠密矩阵时，线性方程组用直接法(如高斯消去法和三角分解法)是有效的，但对于由工程技术中产生的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多），利用迭代法求解是适合的。在计算机内存和运算两方面，迭代通常都可利用A中有大量零元素的特点。,考虑线性方程组,6.1 引言,本章将介绍迭代法的一般理论及雅可比迭代法、高斯塞德尔迭代法、超松弛迭代法，研究它们的收敛性。,6.2 基本迭代,一、雅可比迭代法,二、高斯塞德尔迭代法,SOR迭代法的计算公式:对k=0,1,三、逐次超松驰(SOR)迭代法,说明: 1)=1,即为GS（高斯-赛德尔迭代法）; 2)1，称为超松驰法； 1，称为低松驰法； 3) SOR方法每迭代一次主要运算量是计算一次矩阵 与向量的乘法。,例6-3 用SOR迭代法解线性代数方程组,6.3 迭代法的收敛性一、一阶定常迭代法的基本定理,注：定理5中的矩阵是迭代矩阵，常用格式的迭代矩阵如下：,1) 雅可比迭代法: BJ=D-1(L+U)，fJ=D-1b;2) 高斯-赛德尔迭代法: BG=(D-L)-1U，fG= =(D-L)-1b;3) SOR迭代法: BSOR=(D-L)-1(1-)D+U，fSOR=(D-L)-1b.,例6-4 考察用雅可比迭代法求解线性方程组,二、某些特殊方程组的迭代收敛性,定义3 （1）按行严格对角占优,（2）按行弱对角占优,上式至少有一个不等号严格成立。,定理8(对角占优定理)若矩阵A按行(或列)严格对角占优，或 按行(或列)弱对角占优且不可约；则矩阵A非奇异。,定理9 若矩阵A按行(或列)严格对角占优,或按行(或列)弱对 角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都收敛。,定理12 对于线性方程组Ax=b，若(1) A为对称正定矩阵，(2)02，则解Ax=b的SOR迭代收敛。,定理13 对于线性代数方程组Ax=b， 若A按行(或列)严格对角占优，或按行(或列)弱对角占优不可约；则当01时，SOR迭代收敛。,知识结构图六,迭代法解方程组,迭代法基本概念,高斯-赛德尔迭代法,迭代格式收敛条件（充要条件、充分条件四个）,SQR迭代法,迭代法收敛速度,雅可比迭代法,迭代格式收敛条件（充要条件、充分条件四个）,迭代格式收敛条件（充要条件、必要条件、 充分条件五个）,
