电子科大MATLAB第7节迭代法.

第三章线性方程组求解的数值方法第四节迭代法迭代法（iterativemethod）•迭代法是从初始猜测值开始，通过依次逼近获得问题解的方法。•应用：–线性方程组求解、非线性方程求解、非线性方程组求解、特征值求解、最优化方法、分形……–数字信号处理：维纳滤波、卡拉曼滤波……•典型方法：–数值计算：Jacobi法、Gauss-Seidel法、Newton迭代法、最快下降法（SteepestDescent）分形（fractal）迭代法能从简单的规则出发，通过迭代得到复杂的结果。最直观的展示就是“分形图形”分形是一种粗糙的或分裂的几何形状，其每一部分都是整体的缩小比例的复制（自相似性）NOVA纪录片：huntingthehiddendimension“寻找隐藏的维度”•分形应用：计算机虚拟现实技术；天线设计；医学；分形fractal科赫雪花（Kochsnowflake）：1、初始为正三角形；2、将每条边等分三段；3、以中段为底向外做等边三角形4、移除被三等分的边的中段。5、如此迭代。分形图形分形图形分形图形分形图形分形图形分形图形•clearall•closeall•clc•shg•clfreset•set(gcf,'color','white','menubar','none','numbertitle','off','name','??')•x=[-0.1;0.5]•h=plot(x(1),x(2),'.')•mycolor=[0,2/3,0];•set(h,'markersize',10,'color',mycolor,'erasemode','none');•axis([-3,3,0,10]);•axisoff•%stop=uicontrol('style','toggle','string','stop','background','white')•%drawnow•p=[0.85,0.92,0.99,1.00];•A1=[0.85,0.04;-0.04,0.85];•b1=[0;1.6];•A2=[0.20,-0.26;0.23,0.22];•b2=[0;1.6];•A3=[-0.15,0.28;0.26,0.24];•b3=[0;0.44];•A4=[0,0;0,0.16];•foriii=1:10000•r=rand;•ifrp(1)•x=A1*x+b1;•elseifrp(2)•x=A2*x+b2;•elseifrp(3)•x=A3*x+b3;•else•x=A4*x;•end•set(h,'xdata',x(1),'ydata',x(2));•drawnow•%pause(0.001)•end•msgbox('end')迭代法解方程•迭代序列的基本公式：(1)()0(),kkxxxaff（x）为：任意n维空间到n维空间的函数。•迭代法基本原理：如果迭代序列｛x（k+1）=f（x（k））｝收敛，则其极限点为方程f（x）=x的解。f（x）可为线性方程（组）、非线性方程（组）。迭代法可用于各类方程（组）求解问。迭代法解方程()()*(1)()(1)*()*(1)*()*(1)()(1)(){}0,,2()()+-()kkkkkkkkkkkkxKkKxxxxxxxxxxxxxxxfx，：，收敛则有:使得∀时，满足即：收敛又有：，则：()()()()**()-lim()-0()0()kkkkkfxxfxxfxxfxx，x*称为函数f（x）的不动点（fixedpoint）证明：迭代函数的构造•例：用迭代法求解方程2x=1(1)()1(1)()2(1)()3(1)()4()11()(1)/3(1)/3()2(11.5)2(11.5)()(110)/12(110)/12kkkkkkkkxxxxxxxxxxxxxxxx()0()()0()fxfxxxafxafxxx•步骤二、构造迭代函数：•下列方程（组）等价。•步骤一、写出等价方程：11102112(11.5)312xxxxxxxxx()0()fxxx010203000.20.40.60.81f(x)=1-x0102030-1-0.500.511.52x108f(x)=2*(1-1.5x)010203000.10.20.30.40.5f(x)=(1+10x)/12010203000.10.20.30.40.5f(x)=(1+x)/3振荡序列收敛序列发散序列收敛序列•迭代法的关键问题：–迭代函数收不收敛–收敛速度快不快迭代法程序•clearall•closeall•clc•formatlong•%迭代法求解2x=1•x0=0%迭代初值•N=30%迭代次数•%方法1：f(x)=1-x•x1(1)=x0;•foriii=2:N•x1(iii)=1-x1(iii-1);•end•figure;•plot(x1,'o-')•title('f(x)=1-x')•%方法2：f(x)=(1+x)/3•x2(1)=x0;•foriii=2:N•x2(iii)=(1+x2(iii-1))/3;•end•figure;•plot(x2,'o-')•title('f(x)=(1+x)/2')•%方法3：f(x)=2*(1-1.5x)•x3(1)=x0;•foriii=2:N•x3(iii)=(1-2*x3(iii-1));•end•figure;•plot(x3,'o-')•title('f(x)=2*(1-1.5x)')•%方法4：f(x)=(1+10x)/12•x4(1)=x0;•foriii=2:N•x4(iii)=(1+10*x4(iii-1))/12;•end•figure;•plot(x4,'o-')•title('f(x)=(1+10x)/12')迭代法求解线性方程组•迭代公式的构建：–将方程Ax=b改写为：x=Mx+c，M称为迭代矩阵。迭代法求解线性方程组•迭代公式一：最简单的构造0()AxbAxbAIxbx(1)()()kkxAIxbMAI•迭代公式二：最有效的构造111,=AAxAbxxAbM00迭代法求解线性方程组•迭代公式三（Jacobi迭代）：11221331111112211211222222211233221112nnnnnnnnnnnnnngxbxbxbxaxaxaxbgaxaxaxbxbxbxbxaxaxaxb112233nnnnngxbxbxbx11000...000nnaDa定义对角矩阵：)11(1)(()kkMIJacDAobixbxggDM：迭代公式为迭代法求解线性方程组迭代次数x的第一分量x的第二分量00.00.510.60.220.360.6830.7440.48840.59040.795250.83620.672360.73790.868970.89510.7903………………•例：利用Jacobi迭代求解方程组54,(1,1).45TAb100.8(),0.80JMDLU1(0.2,0.2)TJgDb迭代法求解线性方程组•迭代公式三（Gauss-Seidel迭代）：一般认为新近似解要比老近似解更接近真实解，将已计算出的x（k+1）分量替换Jacobi迭代公式中x（k）相应分量即可得到Gauss-Seidel迭代。迭代法求解线性方程组•例：利用Gauss-Seidel迭代求解方程组541,.451Ab100.8(),0.80JMDLU1(0.2,0.2)TJgDb•步骤1、构造Jacobi迭代公式•步骤2、选择初值(0)[0,0.5]x•步骤3、利用Jacobi迭代公式计算一次迭代的第一分量：(1)1000.80.20.60.5x迭代法求解线性方程组•步骤4、将步骤3得到的一次迭代的第一分量替换初值的第一分量，计算一次迭代的第二分量：(1)20.800.20.680.50.6x•步骤5、如果第三分量存在，利用一次迭代的第一、二分量计算第三分量，直到计算出所有迭代向量分量；•步骤6、重复步骤3-5，进行迭代；迭代法求解线性方程组迭代次数x的第一分量x的第二分量00.00.510.60.6820.7440.79530.83620.868940.89510.916150.93280.946360.95700.965670.97250.9780………………JacobiGauss与相比，只需一组工作单元存放近似解。迭代法求解线性方程组•Gauss-Seidel迭代矩阵：(1)()()()112213311(1)()()22332(12)211(1(1))112kkkknnkkkknnnnnkkgxbxbxbxgxbxxbbxxxb(1)(1)2,11kknnnnbxbxg1212,000U000000nnbbb2112000000000nnLbbb(1)(1)()(1)()(1)1()1()()()kkkkkkkxLxUxgILxUxgxILUxILg11()JacobixMxgLUxgILxUxgxILUxILg迭代法求解线性方程组•Gauss-Seidel迭代矩阵：12131212323132112111111(1)1(000000000,()()nnnnnnnnkkaaaaaaLaaUaaaaLDLUDUILDDDLDDLxILUx如果用矩阵A来表示，记则由)(1)1()111()()()(-)kkxDLUxDILgMDLUGaussdeblLSei。式中矩阵为迭代法的迭代矩阵迭代法求解线性方程组•迭代公式四（超松弛迭代/SOR）：()(1)(1)()(1)(1()()(1)()(1)())()1()---(1)()kkGkkGkkkkkkkkGGGkkSORGaussSeidelxxGaussSexxidelxxxSORxxxxxxxxxx是迭代法的一种加速法。假设:已知，为迭代法结果，定义:，则,迭代法的表达式为：11-1GaussSeidel其中，称为松弛因子。当时称为低松弛；是迭代；时称为超松弛法。相当于在高斯迭代法的基础上再向前（ω1）或向后（ω1）移动一段距离。迭代法求解线性方程组•超松弛迭代/SOR迭代矩阵：(1)1(1)1()1(1)()1(1)1()1()(1)()()1(1)1()1()()1(1)1()==()()(1)kkkkkkkkkkkkkkkkkxDLxDUxDbxxxDLxDUxDbxxxxxDLxDUxDbxxDLxDUxD根据高斯迭代法的矩阵表示：1-1-11-1(1)1)111(-1-(-)()[(1)](()[(1)]())kkbIDLIDLDLxDLDUxMDLDUgDLDLbb－因为,故（）与存在，有：松弛法的迭代矩阵为:Code12•clearall•closeall•clc•shg•clfres