数值分析教教案20

第5章求解线性代数方程组的迭代法5.1求解线性代数方程组的迭代法的根底知识迭代法的根本概念对于阶数不太高的线性方程组，用直接法比拟有效，但对于由工程技术产生的高阶方程组，假设其系数矩阵是无规律稀疏阵〔即矩阵的阶数较大，但零元素较多〕，直接法就很难解决存储问题，所以提出了用迭代思想求解线性方程组的方法。迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，它需要计算机的存储单元较少，因为它可不必存储系数矩阵的零元素。迭代法的根本思想是给定方程组，构造一个序列，使其收敛到某个极限向量，其中是方程组的精确解。在讨论迭代法的过程中要用到向量范数、矩阵范数及序列极限等概念，为此，先介绍这方面的根本知识。向量范数向量范数是用来度量向量长度的。定义1：对，假设有实数与之对应，且这种对应法满足下面三个性质：1.，，而且，当且仅当〔非负性〕。2.，〔齐次性〕。3.，有〔三角形不等式〕，那么称该实数为向量的范数。利用定义1中的性质3可以证明对，有。事实上，由所以，。，定义：(5-1)其中。可以根据定义1验证满足范数定义的条件，所以为的范数。由(5-1)式可知道，给定一个向量，它的范数定义可以有无穷多种，经常采用的范数是，，时的定义。给定中的，常用的范数为：〔5-2〕〔5-3〕〔5-4〕【例5-1】计算向量的各种范数。解：=1+2+4=7；=；=4由向量范数的定义，可以讨论向量的收敛问题。假设中的向量序列满足条件：，那么称在范数意义下收敛于中的向量。1.向量范数的连续性定理：给定中的任意向量，非负函数为向量的任意一向量范数，那么是的各分量的连续函数。2.向量范数的等价定理：给定，对于上的任意两种范数，总存在与无关的正常数，，使关系式：，对一切成立。3.在中，假设在某一种范数意义下向量序列收敛，那么在任何范数意义下该向量序列仍收敛，即：。这里是向量的任意一种范数。4.在中，向量序列收敛于向量的充要条件为：，其中分别表示和的第个分量。矩阵范数设，定义矩阵的范数为：，那么由定义可知矩阵范数具有以下性质：1.，，而且当且仅当〔非负性〕。2.，有〔齐次性〕。3.，有〔三角形不等式〕。4.，，。5.，6.，其中为单位阵。设，如果存在使得：，那么称为矩阵的一个特征值。就是特征值对应的特征向量。式〔5-2〕～〔5-4〕定义的三种常用向量范数对应的矩阵范数定义为：〔列范数〕〔2-范数〕其中表示的最大特征值。〔行范数〕【例5-2】给定求，，。解：由，，得。又由，，得。由：得的特征多项式为：解，得的特征值，。从而：。对应于向量范数的等价性，矩阵范数也有等价性结论：给定，对于上的任意两种范数，，总存在与无关的正常数，，使关系式：成立，即上的任意两种范数，是等价的。为上的矩阵序列，假设存在上的矩阵，使得：成立，那么称矩阵序列是收敛的，称为矩阵序列的收敛极限。由矩阵范数的等价性与矩阵收敛性的定义知，对矩阵序列收敛到矩阵，假设对上的一种范数成立，那么其他范数也成立。所以通常记矩阵序列是收敛于为：，而不特别强调是在哪种范数意义下收敛。上的矩阵序列是收敛于的充要条件为：，其中和分别表示和的第行第列的元素。谱半径对于的上的矩阵，设的特征值为，称=max{}为矩阵的谱半径。【例5-3】给定，求。解：特征多项式为：，那么的特征为，，从而。对于上的矩阵，有。此定理给出矩阵范数与谱半径的关系。如果对于上的矩阵有，那么为非奇异矩阵，且有估计式：成立。给定，那么的充要条件是，其中表示的次幂。迭代法的收敛性从任意选取的初始向量出发，利用迭代格式构造迭代序列，向量序列收敛到方程组的精确解的条件是什么呢？下同面给出了4个定理。其中前两个定理适用于所有具有迭代格式的迭代法，后两个定理是针对Jacobi迭代法、Gauss-Seidel迭代法和逐次超松弛迭代法提出的一些特殊的结论。1.对任意初始向量和常数项，由迭代格式〔〕产生的向量序列收敛的充要条件为。其中为所选迭代格式的迭代矩阵。2.对任意初始向量和常数项，由迭代格式〔〕产生的向量序列收敛的充要条件为：，其中为所选迭代格式的迭代矩阵。3.假设矩阵满足：且至少有一个值，使上式中严格的不等号成立，那么称矩阵具有对角优势。假设对所有值上式中的严格不等号都成立，那么称矩阵是严格对角占优矩阵。如果矩阵是严格对角占优矩阵，那么矩阵非奇异。4.假设系数矩阵严格对角占优，那么Jacobi迭代法和Gauss-Seidel迭代法必定收敛。逐次超松弛迭代法的必要条件是。迭代法的误差估计上节得出的迭代法收敛的充要条件为或者，其中为迭代格式的迭代矩阵，在实际问题中，这两种条件都很难验证的，对于上的矩阵，有得，所以可以用作为的一种估计得到迭代收敛的充要条件，即当时迭代必收敛。关于这个充要条件的误差计算，有以下定理。在方程组的迭代公式中，如果迭代矩阵满足，那么第次迭代结果对于精确解有误差估计式：和。5.2求解线性代数方程组的迭代方法迭代法是解线性方程组的一个重要的实用方法，特别适用于求解在实际中大量出现的系数矩阵为稀疏阵的大型线性方程组。本节介绍求解线性方程组的Jacobi迭代法、Gauss-Seidel迭代法和松弛迭代法。Jacobi迭代法Jacobi迭代法又称简单迭代法。1.Jacobi迭代原理设有线性方程组Ax＝b，即〔5-5〕的系数矩阵非奇异，不妨设。将方程组〔5-5〕变形为〔5-6〕其中。假设记那么方程组〔5-6〕可简记为〔5-7〕选取初始向量代入迭代公式〔5-8〕产生向量序列，由上述计算过程所给出的迭代法称为Jacobi迭代法，又叫简单迭代法。式〔5-8〕为它的迭代公式，迭代矩阵为。式〔5-8〕的分量形式为〔5-9〕这是Jacobi迭代法的计算公式。如果用系数矩阵来表示，那么有其中，现把矩阵分解成如下形式：那么。方程组改写成相应的矩阵形式的迭代公式为〔5-10〕简记为〔5-11〕式中，〔5-12〕迭代公式〔5-10〕或〔5-11〕也称为Jacobi迭代，同时称式〔5-12〕中的为Jacobi迭代矩阵。【例5-4】用Jacobi迭代法求解线性方程组。解由Jacobi迭代法的计算公式〔5-9〕，有取，代入上式得如此继续下去，迭代结果见表5-1。表5-100.00000.00000.000017.20008.30008.400029.710010.700011.5000310.570011.570012.4820410.853511.835412.8282510.951011.951012.9414610.983411.983412.9504710.994411.998112.9934810.998111.994112.9978910.999411.999412.9992迭代9次，得近似解，容易验证，方程组的精确解为，从表5-1中可以看出，当迭代次数增加时，迭代结果越来越接近精确解。2.Jacobi迭代法的MATLAB实现function[x,k,flag]=Jacobi(A,b,delta,max1)%求解线性方程组的迭代法,其中,%A为方程组的系数矩阵;%b为方程组的右端项;%delta为精度要求,缺省值为1e-5;%max1为最大迭代次数,缺省值100;%x为方程组的解;%k为迭代次数;%flag为指标变量flag='OK!'表示迭代收敛到指标要求,%flag='fail!'表示迭代失败.ifnargin<4max1=100;endifnargin<3delta=1e-5;endn=length(A);k=0;x=zeros(n,1);y=zeros(n,1);flag='OK!';while1fori=1:ny(i)=b(i);forj=1:nifj~=iy(i)=y(i)-A(i,j)*x(j);endendifabs(A(i,i))<1e-10|k==max1flag='Fail';return;endy(i)=y(i)/A(i,i);endifnorm(y-x,inf)<delta%无穷大范数break;endx=y;k=k+1;end【5-5】求解性线方程组。解：在命令窗口输入系数矩阵和右端项：>>A=[41-1;1-5-1;2-1-6],b=[13-8-2]'回车得到：