解线性方程组的迭代法

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十讲解线性方程组的迭代解法,内容提要,引言,简单迭代法,赛得尔迭代法,迭代解法的收敛性,MATLAB,的线性方程组求解函数,2,小结,根据给定方程组，设计出一个迭代公式，构造一数组的序列 ，代入迭代公式，计算出 ，再代入迭代公式，经过,k,次迭代运算后得到 ，若 收敛于某一极限数组,x,i,，则,x,i,就是方程组的近似解。,迭代过程本质上就是计算极限的过程，一般不能得到精确解。,迭代法的优点是程序简单，适合于大型方程组求解，但缺点是要判断迭代是否收敛和收敛速度问题。,雅可比,(Jacobi(1804-1851),迭代法（简单迭代法）,赛得尔,(Seidel,(1821 - 1896),),迭代法,迭代解法的基本思想,1,、引言,设线性代数方程组为,2,、简单迭代法,展开为,若对角元素,逐一变量分离得方程组,即,此即为迭代公式,简单迭代解法的过程如下：,1,设定一组初值,第,i,个变量,第,k,次迭代,2,第一次迭代：,得到,3,第二次迭代：,得到,4,同样做法，得到第,k+1,次迭代：,迭代次数,k,的取值与精度要求有关，按下式判断：,若满足则停止迭代,为了便于编程，,迭代公式可改写为：,function x,iter,exitflag=Jacobi_iter(A,b,x0,eps,iter_max),%,线性方程组的,Jacobi,迭代求解,(,向量形式,),%,输入参数：,% -A,：线性方程组的系数矩阵,% -b,：线性方程组的右端项,% -x0,：初始向量，默认值为零向量,% -eps,：精度要求，默认值为,1e-6,% -iter_max,：最大迭代次数，默认值为,100,%,输出参数：,% -x,：线性方程组的近似解,% -iter,：迭代次数,% -exitflag,：迭代成功与否的标志：,exitflag=1,表示迭代成功,% exitflag=0,表示迭代失败,n=length(b);,if nargin5|isempty(iter_max);iter_max=100;end,if nargin4|isempty(eps);eps=1e-6;end,if nargin3|isempty(x0);x0=zeros(n,1);end,iter=0;exitflag=1;,D=diag(diag(A);L=tril(A,-1);U=triu(A,1);,J=-inv(D)*(L+U);f=inv(D)*b;,while iteriter_max,x=J*x0+f;,if norm(x-x0,inf)eps,break,end,x0=x;iter=iter+1;,end,if iter=iter_max,exitflag=0;,end,function x,iter,exitflag=Jacobi_iteration(A,b,x0,eps,iter_max),%,线性方程组的,Jacobi,迭代求解,(,分量形式,),%,输入参数：,% -A,：线性方程组的系数矩阵,% -b,：线性方程组的右端项,% -x0,：初始向量，默认值为零向量,% -eps,：精度要求，默认值为,1e-6,% -iter_max,：最大迭代次数，默认值为,100,%,输出参数：,% -x,：线性方程组的近似解,% -iter,：迭代次数,% -exitflag,：迭代成功与否的标志：,exitflag=1,表示迭代成功,% exitflag=0,表示迭代失败,n=length(b);,if nargin5;iter_max=100;end,if nargin4;eps=1e-6;end,if nargin3;x0=zeros(n,1);end,x=zeros(n,1);iter=0;exitflag=1;,while iteriter_max,for i=1:n,x(i)=(b(i)-A(i,1:i-1,i+1:n)*x0(1:i-1,i+1:n)/A(i,i);,end,if norm(x-x0,inf)eps),x1=x;,x=(I-A)*x1+b;,n = n + 1;,if(n=M),disp(Warning:,迭代次数太多，现在退出！,);,return;,end,end,例：求解方程组,clear all;,A = 1.0170 -0.0092 0.0095;,-0.0092 0.9903 0.0136;,0.0095 0.0136 0.9898;,b=1 0 1;,x0 = 0 0 0;,x,n=richason(A,b,x0),x =,0.9739,-0.0047,1.0010,n =,5,赛得尔迭代法与简单迭代法类似，只是迭代公式有所改进。,3,、赛得尔迭代法,简单迭代法,赛得尔迭代法,MATLAB,程序设计,function x,n=gauseidel(A,b,x0,eps,M),if nargin=3,eps= 1.0e-6;,M = 200;,elseif nargin = 4,M = 200;,elseif nargin=eps,x0=x;,x=G*x0+f;,n=n+1;,if(n=M),disp(Warning:,迭代次数太多，可能不收敛！,);,return;,end,end,例：线性代数方程组的迭代解法,-,赛得尔迭代法,clear all;,A = 9 53 381;,53 381 3017;,381 3017 25317;,b=76 489 3547;,x0=zeros(3,1);,x,n=gauseidel(A,b,x0,1e-4,10),Warning:,迭代次数太多，可能不收敛！,x =,-0.8037,3.3330,-0.2450,n = 200,迭代解法的前提条件是迭代解出的近似解序列必须具有收敛性。如果近似解序列是发散的， 迭代法则不能获得解。,4,、,迭代解法的收敛性,以下列初值进行简单迭代,k,X,1,X,2,X,3,0,0,0,0,1,11,-14,-3,2,-69,81,66,3,-499,-374,-429,4,4851,-7149,-2124,迭代收敛条件：严格对角占优矩阵,若不满足收敛条件，适当调整方程次序或作一定的线性组合，就可能满足收敛条件。,格式,solve,(eqn1,eqn2,.,eqnN,var1,var2,.,varN),5,、,MATLAB,的线性方程组求解函数,2,格式,X=fsolve(FUN,X0),Matlab,非线性方程组求解,说明：,求解方程形式,F(X)=0,X,、,F,可以是向量或矩阵,X0,初值,实例：基于,Matlab,的透镜中心偏测量光轴拟合,光学中心偏测量仪作为精确测定和严格校正光学系统中心偏误差的仪器,它可以指出透镜组中的各镜面相对于光轴的中心偏移数值大小和方向。它的测量结果具有两个方面的意义,:,其一是通过根据被测光学件各面的中心误差是否超出,来判定光学件是否合格,;,其二是根据测量的结果来指导光学系统的装校。,为消除被测件在测量仪器上的安装定位过程带来的误差,必须对直接测量的数据进行修正。光轴拟合就是对测量数据的优化和修正的过程。提出一种光轴拟合的数学模型,该数学模型结合了解析方法和数值分析方法,考虑了中心偏测量的实际情况,在严格的数学模型基础上做了合理的简化,使光轴的拟合问题最终转化为对线性方程组的求解。,3),应用最小二乘法得到关于四参数的线性方程组。,得到各面球心的位置坐标后,按照一般直线拟合的方法,应使各球心对优化轴距离的平方和最小,符合数学上的最小二乘法。,N,个球心到优化轴距离的平方和,:,扩展：基于,MATLAB,的非线性方程组遗传解法,胡斐，赵治国,(,同济大学汽车学院，上海,201804),遗传算法是一种基于自然选择的用于求解有约束和无约束最优问题的方法。遗传算法反复修改包含若干个体的种群。遗传算法在每一步中，随机从当前种群中选择若干个个体作为父辈，并用它们产生下一代子辈。在若干代之后，种群就朝着最优解,“,进化,”,。我们可以利用遗传算法去解决各种最优化问题，包括目标函数是不连续、不可微、随机或者高度非线性的问题。,MATLAB,的遗传算法与直接搜索工具箱（,Genetic Algorithm and Direct Search Toolbox,，简称,GADS,）是,MATLAB,的一个优化工具箱。它有两种使用方式：一种是通过命令行调用,ga,函数，另一种是通过图形界面调用。,小 结,线性方程组求根方法的几何意义,线性方程组求根函数,的理解与应用,谢 谢 ！,