解线性方程组的迭代法 (2)精选PPT.ppt

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