方程组迭代法

作业P911(2),2,3(2),4,5,61第四章线性方程组的迭代法思路Axb将改写为等价形式，建立迭代。从初值出发，得到序列。xBxg1kkxBxg0x{}kx研究内容：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？2§4.1三种基本的迭代法4.1.1．雅克比（Jacobi）迭代法（以三阶方程组为例）111122133121122223323113223333axaxaxbaxaxaxbaxaxaxb3假设0i=1,2,3iia则方程组可写为：1112213311222112332233311322331()1()(4.1)1()xbaxaxaxbaxaxaxbaxaxa111122133121122223323113223333axaxaxbaxaxaxbaxaxaxb4(1)()()1112213311(1)()()2221123322(1)()()33311322331()1()1()mmmmmmmmmxbaxaxaxbaxaxaxbaxaxa任选一初值向量：(0)(0)(0)(0)123(,,)Xxxx称为雅可比(Jacobi)迭代5对于n阶方程组,0(i=1,2,,n),iiAxba设则雅可比迭代公式为:(0)(0)(0)(0)121(1)()()11(,,,)1()1,2,,.0,1,2,.Tninmmmiiijjijjjjiiixxxxxbaxaxainm6(1)()()()111122111(1)()()()222112222(1)()()()1122101010mmmmnnmmmmnnmmmmnnnnnnnxbxaxaxaxbaxxaxaxbaxaxxa+++轾=----犏臌轾=----犏臌轾=----犏臌LLLLLLLLL(0,1,2,)m=LLn阶方程的Jacobi迭代格式:7若用矩阵来表示雅可比迭代，则如下:令A=D-L-U，其中A=-L-UD8Ax=b,(D–L–U)x=bDx=(L+U)x+b迭代Dx(m+1)=(L+U)x(m)+b,若则D可逆,于是得0(i=1,2,,n)iia(1)1()1()J11()=B(),mmmJJJxDLUxDbxfBDLUfDb称为雅可比迭代矩阵.JB则有：94.1.2高斯—赛德尔迭代法(Gauss-Seidel)对雅可比迭代法作如下的改进：将初值代入4.1的第一个方程可得,用代入第二个方程得,用代入第三个方程得,这样一直做下去,直到得到满意的解为止.(0)(0)(0)(0)123(,,)Xxxx(0)1x(1)(0)(0)123(,,)xxx(1)2x(1)(1)(0)123(,,)xxx(1)3x10这种迭代称为高斯—赛德尔(Gauss-Seidel)迭代法（G-S）(1)()()1112213311(1)(1)()2221123322(1)(1)(1)33311322331()1()1()mmmmmmmmmxbaxaxaxbaxaxaxbaxaxa11(1)()()()111122111(1)(1)()()222112222(1)(1)(1)()1122101010mmmmnnmmmmnnmmmmnnnnnnnxbxaxaxaxbaxxaxaxbaxaxxa++++++轾=----犏臌轾=----犏臌轾=----ê臌LLLLLLLLLú(0,1,2,)m=LLn阶方程的G-S迭代格式:12用矩阵表示：1(1)(1)()111()1,2,,;0,1,2,.(4.8)inmmmiiijjijjjjiiixbaxaxainm(1)(1)()mmmDXbLXUX即：(1)1()1()G()()=BmmmGXDLUXDLbXf称为高斯-赛德尔迭代矩阵n阶方程的G-S迭代格式:1()GBDLU-=-13例1（p75）：分别Jacobi及G-S迭代法解下列线性方程组。初值均取(0，0，0)T解:具体解法见课本。用matlab求解,程序如下123911718071098xxx14%用雅可比法解P75例1a=[9,-1,-1;-1,8,0;-1,0,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-b);U=-(triu(a)-b);xo=[0;0;0];bo=[7;7;8];ep=0.0001;dx=1;k=0;whiledxepk=k+1;x=D\(L+U)*xo+D\bo;dx=abs(norm(x)-norm(xo));xo=x;endk,x%用G-S法解P75例1a=[9,-1,-1;-1,8,0;-1,0,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-b);U=-(triu(a)-b);xo=[0;0;0];bo=[7;7;8];ep=0.0001;dx=1;k=0;whiledxepk=k+1;x=(D-L)\U*xo+(D-L)\bo;dx=abs(norm(x)-norm(xo));xo=x;endk,x15从计算结果可以看到：如果两种迭代法都收敛，那么Jacobi迭代法慢于G-S迭代法。这个结论具有一般意义。164.1.3超松弛迭代法（SOR）一、考虑分裂法:()JacobiADLU:()GSADLU11:()(1)SORADLDU17AXb11()(1)DLDUXb11()(1)DLXDUXb()(1)DLXDUXb11()(1)()XDLDUXDLb18称SOR迭代阵()mBXf(1)1()1()(1)()mmXDLDUXDLb故SOR迭代格式为：19二、换个角度看SORG-S可看作：(1)(1)()1()mmmiiijjijjjijiiixbaxaxa()(1)()()1()mmmmiiijjijjiiijijiiixbaxaxaxa()(1)()1()mmmiiijjijjjijiiixbaxaxa(1)()mmiiiirxa20SOR的基本原理:令希望通过选取合适的来加速收敛。(1)(1)()mmmiiiiirxxa(1)()mmXBXf与是统一的。说明如下：表达式21(1)()1(1)()(1)()mmmmXXDLXUXb()(1)()(1)()mmmiiijjijjjijiiixbaxaxa(1)(1)()mmmiiiiirxxa其向量形式为：(1)1(1)()1()1(1)mmmmXDLXXDUXDb(1)()()(1)mmDLXDUXb(1)1()1()(1)()mmXDLDUXDLb()mBXf22写成分量式的计算公式为:此方法称为带有松弛因子ω的松弛迭代法.当ω1时称为超松弛迭代法(SOR法);当ω1时称为低松弛迭代法;当ω=1时就是G-S迭代法.1(1)()(1)()1()(i=1,2,,n.m=0,1,2,)inmmmmiiiijjijjjjiiixxbaxaxa23例2(p78):用SOR法求解方程1234241021710341097xxx解：根据p78公式（4.10），写出SOD迭代格式：(1)()()()()11123(1)()(1)()()22123(1)()(1)(1)()33123[10424]4[321710]17[74109]9mmmmmmmmmmmmmmmxxxxxxxxxxxxxxx=+-++=++--=+-+--24%用SOR法解P96例2a=[4,-2,-4;-2,17,10;-4,10,9];D=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);xo=[0;0;0];bo=[10;3;-7];omiga=1.46;ep=0.000001;dx=1;k=0;whiledxepk=k+1;x=(D-omiga*L)\(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)\bo*omiga;dx=abs(norm(x)-norm(xo));xo=x;endk,x25Matlab的关于三种迭代法的通用程序%雅可比法解方程的通用程序%A为线性方程组,X为初值function[x,k]=ya2(A,X)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledxepk=k+1;x=D\(L+U)*xo+D\bo;dx=norm(x-xo);xo=x;end1.雅可比迭代法的通用程序262.高斯_塞德尔迭代法的通用程序%G_S法解方程组的通用程序%A为线性方程组,X为初值function[x,k]=ya4(A,X)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledxepk=k+1;x=(D-L)\U*xo+(D-L)\bo;dx=norm(x-xo);xo=x;end273.SOR法解线性方程组的通用程序%SOR法解方程组的通用程序%A为线性方程组,X为初值%omiga为松弛因子function[x,k]=ya3(A,X,omiga)n=length(A');a=A(:,1:n-1);bo=A(:,n);N=size(X);ifN(1)N(2)xo=X';elsexo=XendD=-(a-triu(a)-tril(a));L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;whiledxepk=k+1;x=(D-omiga*L)\(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)\bo*omiga;dx=norm(x-xo);xo=x;end284.2迭代法的收敛条件前面介绍了三种常用迭代法.它们可能收敛，也可能发散。(1)()mmxBxf一般迭代格式：下面从理论上探讨一般迭代的收敛性.B称为迭代阵294.2.1迭代法收敛的概念定义4.2设x*是方程组Ax=b的解,对于给定的初始向量x(0),若由某种迭代法产生的向量序列{x(n)}有()*limnnxx则称该方法收敛,否则称该方法发散.30引理1证:()*()*limlim0nnnnxxxx()*()*n()*()*1limlim()0(i=1,2,,n)limmax0lim0nniinmmiinninxxxxxxxx由再由范数的等价性有()*()*limlim0nnnnxxxx314.2.2迭代法收敛的判定定理定理4.1设(1)(),mmxBxf若1pBq则对任意