数值分析-

数值方法第三章线性代数方程组的迭代解法基本概念Jacobi迭代法和Gauss-Seidel迭代法超松弛迭代法3.1迭代法的基本概念迭代法与直接方法不同,不是通过预先规定好的有限步算术运算求得方程组的解,而是从某初始向量出发,用设计好的步骤逐次算出近似解向量x(k),从而得到向量序列{x(0),x(1),x(2),…}.如果此序列存在极限向量,则可以分析它是否为方程组的解.Rn中的向量序列{x(0),x(1),x(2),…}也记为,或简记为{x(k)}.同理Rn×n中的矩阵序列记为或{A(k)}.()0{}kkx()0{}kkA3.1迭代法的基本概念2.向量序列和矩阵序列的极限()()()()()()()()T1212()()lim0,{},lim.{}.=(,,,),(,,,),limlim=1,2,,.nnkkkkkkkkkknnkkiikkxxxxxxxxinRxRxxxxxxxxxxx定义了范数的向量空间中,若存在满足则称记为由于向量范数的等价性，的收敛性与所选的范数无关设则，即向量序列的收敛性等价于由向量收敛于分量构成的(){}.knx个数列的收敛性,我们也称按分量收敛3.1迭代法的基本概念2.向量序列和矩阵序列的极限()()()()()()()()lim0,{},lim.{}.=[],[],limlim=,1,2,,.nnnnkkkkkkkkijijkkijijkkaaaaijnRARAAAAAAAAAAA定义了范数的向量空间中,若存在满足则称记为同理，的收敛性与所选的范数收敛于无关设则，3.1迭代法的基本概念2.向量序列和矩阵序列的极限()()()()()()()()()()limlim,,limlim=0.,lim=0.lim,lim=kkknkkkkkkknkkknjkkkjkjjAAxxRAxAxAAxRAxAxxRxeAeA：的充分必要条件是：对任意一种矩阵从属范数有，所以,若，则对有成立，必要性得证若成立,取为第个坐标单位向量,则意味定着第列元证的理1明各素00000()1,2,,limkkjnA极限为零,当,就证明了充分性得证.定理证毕.0,3.1迭代法的基本概念2.向量序列和矩阵序列的极限,1:lim.2()1.12,,=,=,.lim1,lim=,lim=0.lim=lim=0.01,()1.2nnkkkkkkkkkkkkkkkkBRBBBxBxxBxxxBxBBxBxxxxBB定理证明：设则下列两个命题等价：命题命题：：：设的一个特征值为对应特征向量满足则有得设由定理有所以即得因的所有特征值都满足即000,03.1迭代法的基本概念*2.向量序列和矩阵序列的极限121()1,,()+.,()+1,1.lim..,lim().3kkkkknnkkBBBBBBBBBRBB：设根据线代基础知识,对任意实数0,存在一种从属的矩阵范数使适当选择使便有由定理证毕：设为任意一种矩阵范数,定理则03.1迭代法的基本概念3.迭代公式的构造-1-1-1-1-1(1)()(0)(1)(2),+.=,,.=01,kknkAx=bAAA=M-NMAx=bx=MNxMbB=MNIMAf=Mbx=Bx+fx=Bx+fBxRxx对方程组，设系数矩阵非奇异,将分裂为其中为非奇异矩阵,则由方程组可得令得到方程组的一个等价方程组由上式可构造解此方程组的迭代法：，，，，其中称为.如果迭代矩阵给定初始向量按上式就可以计算，，，这样就产生向量序列(){}.kx3.1迭代法的基本概念3.迭代公式的构造()()(0)(1)()(1)(),{}lim,=01..nkknkkkkkkxRxxxxRx=Bx+fx=Bx+fxx=Bx+fxAx=b若存在向量由迭代法产生的序列满足，则称迭代法，，，，是的.显然，若迭代法收敛，则满足方程从而向量是方程组收的解敛P71,3.1.33.1迭代法的基本概念4.迭代法的收敛性分析()(1)()()()(+1)(+1)()()()(0)(0)(0)(),.{},.==01==(),==,.lim0nkkkkkkkkkkkkkkkxRxAx=bx=Bx+fxx=Bx+fexxexxBxxBeeBeexxe设是方程组的解,它也是等价方程组的解,即对于迭代法产生的序列有记为，，，，则有由此递推得，其中它与无关所以迭代法收敛就意味着差向量，误(0).neR3.1迭代法的基本概念4.迭代法的收敛性分析(1)()()(0)()(0)(0)(0)(=01)()1.lim.=lim=.1lim=2lim=()1..()1,4kkknkkkknkkkkkkx=Bx+fBeeReBeBeeRBBBB：迭代法，，收敛的充分必要条件是：迭代法收敛等价于，由迭代法收敛的充分必要条件是，由定理知,上式成立由定理，定理得定理证明证实际判别往往较难检验有时用000.01.B作为收敛的充分条件较为方便3.1迭代法的基本概念4.迭代法的收敛性分析(1)()()()(1)()(1)(0)=1,,,1.15kkkkkkkqqqqqxx=Bx+fBx=Bx+fxxxxxxxx：设是方程组的唯一解,是一种向量范数,从属与它的矩阵范数则迭代法敛定收且理3.1迭代法的基本概念*4.迭代法的收敛性分析()()(1)(1)()()()(1)()()()(1)()()()(1)()(1)(1)(-2)()1,4lim.=()()(),()().,.1=(kkkkkkkkkkkkkkkkkkkkkBBxxxxBxxBxxBxxxxBxxBxxBxxBxxBxxxxBxxBxx：由于由定理知而所以即得式1反复得证递推明(1)(-2)),2..kkqxx即得式定理证毕3.1迭代法的基本概念4.迭代法的收敛性分析(1)()()()(1)()(1)()5,1-2--,,.1,,.5,,..kkkkkkkkqBxxxxxxBxxxxB利用定理作误差估计一般可取范数、范数或范数.从定理可见,只要不是很接近1,若相邻两次迭代向量和已经很接近则和已经相当接近所以可用来控制迭代计算结束但是若即使很小也不能判断很小从定理可见越小则迭代收敛越快下面分析收敛速度的概念3.1迭代法的基本概念4.迭代法的收敛性分析(0)(0)(1)()()()(0)(0)()(0)()(0)(0)(0)(0)00()(0)(=01),()1,=.=maxmax,.,kkkkkkkkkkkkkkkkkeex=Bx+fBeeBeBeeBeeeBBeeeBee设迭代法，，收敛即则第次迭代的误差向量满足设即给出了迭代次后误差向量的范数与初始误差向量的范数之比的最大值这样迭代次后平均每次迭代误差向量范数的压01.kkB缩率可以看成是3.1迭代法的基本概念4.迭代法的收敛性分析11111()(0)1,=101,,,lnln,ln.lnln.kkkkkkskkkkkkkkeeBBBBB如果要求迭代次后有其中那么只要满足即可这等价于即可见最小迭代次数反比于3.1迭代法的基本概念4.迭代法的收敛性分析11(1)()(1)()(=01)()ln.().3,lim(),lim()ln().:()ln(),.(),()kkkkkkkkkkkkkkRRkRRRx=Bx+fBBBBBBBBBx=Bx+fBBB平均收敛迭代法，，的定义为平均收敛率依赖于迭代次数和所选择的矩阵从属范数由定理知称为迭代法的或称与迭代次数及取的何种范数无关率渐近当收敛率渐近收敛速度定义越小时,.ln()kRB迭代收敛就越快可用估计所需迭代次数3.2Jacobi迭代法和Gauss-Seidel迭代法1122121312123231321,12,10000,.0000,det0,[].=,=diag(,,),,nnijnnnnnnnnnnaaaaaaaaaaaaaaaaAx=bARAAADLUDALULUA对于方程组，其中可将系数矩阵分解为其中即的对角部分而即-和-分别是的严格下、上三角部分.3.2Jacobi迭代法和Gauss-Seidel迭代法JJ-1-1-1JJ(1)()JJ(1)()(0,1,2,,,.,,,,=()=.,0,1,,,.1(JacobiJJ1.JacobiiikkkkiiijjijjiiainkxbaxaxaDM=DN=L+UA=M-Nx=Bx+fBDL+UIDAfDbx=Bx+fAx=b=设即非奇异取由可将方程组改写为等价方程组且，由此构造迭代法称为解方程组的简称或分量形迭代法迭代式法法迭代法1)11),1,,.inkjjiin3.2Jacobi迭代法和Gauss-Seidel迭代法-1-1-1(1)()(1)(1)Gauss-SeidelGS.,,,,=()=()().,0,1,,,1.Gauss-Seide(lGGGGkkGGkkiiijjijjiikxbaxaxaM=DLN=UA=MNx=Bx+fBDLUIDLAfDLbx=Bx+fAx=b=取由可将方程组改写为等价方程组且，由此构造迭代迭代法GS迭代法法称为解方程组的法简称或分量形式２迭代法1()11),1,,.inkjjiin3.2Jacobi迭代法和Gauss-Seidel迭代法JGJGJ()1,GS()1,JGS.,,JGS.3.JGS::BBBBAAx=b法收敛的充分必要条件是法收敛的充分必要条件是其中和分别是法和法的迭代矩阵设为严格对角占优矩阵或为不可约的弱法和法的收敛性定对角占优矩阵则解方程组的法和法理理都收敛定3.2Jacobi迭代法和Gauss-Seidel迭代法111111:,0(1,2,,),(1)J,=diag(,,,).(2)GS.,JGS,.,0(1,2,,).iiiiainaaaainAAx=bA2DADAx=bAA设对称且对角元则解方程组的迭代法收敛的充要条件是及均为正定矩阵其中解方程组的迭代法收敛的充要条件是为正定矩阵对于一个给定的方程组法和法可能两者都收敛或都不收敛也可能其一收敛而另一个不收敛如果是对称正定矩阵必有定理则GS,J.法一定收敛而法却不一定收敛3.3超松弛迭代法1.逐次超松弛迭代公式(1)(1)(1)(1)1211(1)(1)()11(1)()(1)(1)()(),GS.,,,,,GS1(),,=+(1)kkkkiinkkkiiijjijjjjiiikkiikkkkiiiixxxxbaxaxaxxxxxxx=为了提高收敛速度对法进一步改进假设计算第k+1个近似解时分量已经算好可以如的公式那样计算再用参数作和的加权平均即(1)()1(1)()(1)()11(),=(1)+(),1,2,,.,(succesiseover-relaxatSion),.=1,SORGS.ORSORkkiiinkkkkiiiijjijjjjiiixxxxbaxaxina逐次超松弛迭或这称为简称或称为时法代法迭就是代法法弛因子法松3.3超松弛迭代法*1.逐次超松弛迭代公式(1)()1(1)()(1)()()(1)()-1-11.SOR(1)+(),()[(1)].=+(),SOR:=()[(1