解线性方程组的迭代法 (2)讲稿.ppt

《解线性方程组的迭代法 (2)讲稿.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法 (2)讲稿.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于解线性方程组的迭代法(2)第一页，讲稿共三十四页哦内容提要内容提要n n引言引言n n简单迭代法简单迭代法n n赛得尔迭代法赛得尔迭代法n n迭代解法的收敛性迭代解法的收敛性 n nMATLAB的线性方程组求解函数的线性方程组求解函数2n n小结小结第二页，讲稿共三十四页哦 根据给定方程组，设计出一个迭代公式，构造一数组的序根据给定方程组，设计出一个迭代公式，构造一数组的序根据给定方程组，设计出一个迭代公式，构造一数组的序根据给定方程组，设计出一个迭代公式，构造一数组的序列列列列 ，代入迭代公式，计算出，代入迭代公式，计算出，代入迭代公式，计算出，代入迭代公式，计算出 ，再代入迭代公式，经

2、过，再代入迭代公式，经过，再代入迭代公式，经过，再代入迭代公式，经过k k次迭代运算后得到次迭代运算后得到次迭代运算后得到次迭代运算后得到 ，若，若，若，若 收敛于某一极限数组收敛于某一极限数组收敛于某一极限数组收敛于某一极限数组x xi i，则，则，则，则x xi i就是方程组的近似解。就是方程组的近似解。就是方程组的近似解。就是方程组的近似解。迭代过程本质上就是计算极限的过程，一般不能得到精确迭代过程本质上就是计算极限的过程，一般不能得到精确迭代过程本质上就是计算极限的过程，一般不能得到精确迭代过程本质上就是计算极限的过程，一般不能得到精确解。解。解。解。迭代法的优点是程序简单，适合于大型

3、方程组求解，迭代法的优点是程序简单，适合于大型方程组求解，迭代法的优点是程序简单，适合于大型方程组求解，迭代法的优点是程序简单，适合于大型方程组求解，但缺点是要判断迭代是否收敛和收敛速度问题。但缺点是要判断迭代是否收敛和收敛速度问题。但缺点是要判断迭代是否收敛和收敛速度问题。但缺点是要判断迭代是否收敛和收敛速度问题。1.1.雅可比雅可比雅可比雅可比(Jacobi(1804-1851)(Jacobi(1804-1851)迭代法（简单迭代法）迭代法（简单迭代法）迭代法（简单迭代法）迭代法（简单迭代法）2.2.赛得尔赛得尔赛得尔赛得尔 (Seidel(Seidel(1821-1896)(1821-1

4、896)迭代法迭代法迭代法迭代法迭代解法的基本思想迭代解法的基本思想迭代解法的基本思想迭代解法的基本思想1 1、引言、引言、引言、引言第三页，讲稿共三十四页哦设线性代数方程组为设线性代数方程组为设线性代数方程组为设线性代数方程组为2 2、简单迭代法、简单迭代法、简单迭代法、简单迭代法展开为展开为展开为展开为第四页，讲稿共三十四页哦若对角元素若对角元素若对角元素若对角元素逐一变量分离得方程组逐一变量分离得方程组逐一变量分离得方程组逐一变量分离得方程组第五页，讲稿共三十四页哦即即即即此即为迭代公式此即为迭代公式此即为迭代公式此即为迭代公式简单迭代解法的过程如下：简单迭代解法的过程如下：1 1 设定

5、一组初值设定一组初值设定一组初值设定一组初值2 2 第一次迭代：第一次迭代：第一次迭代：第一次迭代：得到得到得到得到第六页，讲稿共三十四页哦3 3 第二次迭代：第二次迭代：第二次迭代：第二次迭代：得到得到得到得到4 4 同样做法，得到第同样做法，得到第同样做法，得到第同样做法，得到第k+1k+1次迭代：次迭代：次迭代：次迭代：第七页，讲稿共三十四页哦迭代次数迭代次数迭代次数迭代次数k k k k的取值与精度要求有关，按下式判断：的取值与精度要求有关，按下式判断：的取值与精度要求有关，按下式判断：的取值与精度要求有关，按下式判断：若满足则停止迭代若满足则停止迭代若满足则停止迭代若满足则停止迭代为

6、了便于编程，为了便于编程，为了便于编程，为了便于编程，迭代公式可改写为：迭代公式可改写为：迭代公式可改写为：迭代公式可改写为：第八页，讲稿共三十四页哦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：线性方程组的右端项：线性方程组的右端项%-x

7、0%-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=l

8、ength(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

9、);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 ite

10、r=iter_max exitflag=0;exitflag=0;endend第九页，讲稿共三十四页哦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：初始向量，默认值

11、为零向量：初始向量，默认值为零向量%-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 na

12、rgin5;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

13、(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

14、endendend第十一页，讲稿共三十四页哦例：求解方程组例：求解方程组例：求解方程组例：求解方程组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.0

15、047 -0.0047 1.0010 1.0010n=n=5 5第十二页，讲稿共三十四页哦 赛得尔迭代法与简单迭代法类似，只是迭代公式有所改进。赛得尔迭代法与简单迭代法类似，只是迭代公式有所改进。赛得尔迭代法与简单迭代法类似，只是迭代公式有所改进。赛得尔迭代法与简单迭代法类似，只是迭代公式有所改进。3、赛得尔迭代法、赛得尔迭代法、赛得尔迭代法、赛得尔迭代法简单迭代法简单迭代法简单迭代法简单迭代法赛得尔迭代法赛得尔迭代法赛得尔迭代法赛得尔迭代法第十三页，讲稿共三十四页哦MATLABMATLAB程序设计程序设计程序设计程序设计function x,n=gauseidel(A,b,x0,eps,M)

16、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:迭代次数太多，可能不收敛！迭代次数太多，可能不收敛！迭代

17、次数太多，可能不收敛！迭代次数太多，可能不收敛！););return;return;end endendend第十四页，讲稿共三十四页哦例：线性代数方程组的迭代解法例：线性代数方程组的迭代解法例：线性代数方程组的迭代解法例：线性代数方程组的迭代解法-赛赛赛赛得得得得尔尔尔尔迭代法迭代法迭代法迭代法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)

18、;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第十五页，讲稿共三十四页哦 迭代解法的前提条件是迭代解出的近似解序列必须具有收迭代解法的前提条件是迭代解出的近似解序列必须具有收迭代解法的前提条件是迭代解出的近似解序列必须具有收迭代解法的前提条件是迭代解出的近似解序列必须具有收

19、敛性。如果近似解序列是发散的，敛性。如果近似解序列是发散的，敛性。如果近似解序列是发散的，敛性。如果近似解序列是发散的，迭代法则不能获得解。迭代法则不能获得解。迭代法则不能获得解。迭代法则不能获得解。4 4、迭代解法的收敛性迭代解法的收敛性迭代解法的收敛性迭代解法的收敛性第十六页，讲稿共三十四页哦以下列初值进行简单迭代以下列初值进行简单迭代以下列初值进行简单迭代以下列初值进行简单迭代kX1X2X30000111-14-32-6981663-499-374-42944851-7149-2124第十七页，讲稿共三十四页哦迭代收敛条件：严格对角占优矩阵迭代收敛条件：严格对角占优矩阵迭代收敛条件：严格

20、对角占优矩阵迭代收敛条件：严格对角占优矩阵若不满足收敛条件，适当调整方程次序或作一定若不满足收敛条件，适当调整方程次序或作一定的线性组合，就可能满足收敛条件。的线性组合，就可能满足收敛条件。第十八页，讲稿共三十四页哦格式格式格式格式solvesolve(eqn1,eqn2,.,eqnN,var1,var2,.,varN)(eqn1,eqn2,.,eqnN,var1,var2,.,varN)5、MATLAB的线性方程组求解函数的线性方程组求解函数2第十九页，讲稿共三十四页哦第二十页，讲稿共三十四页哦格式格式格式格式X=fsolve(FUN,X0)X=fsolve(FUN,X0)Matlab非线性

21、方程组求解非线性方程组求解非线性方程组求解非线性方程组求解说明：说明：说明：说明：求解方程形式求解方程形式求解方程形式求解方程形式F(X)=0F(X)=0 X X、F F可以是向量或矩阵可以是向量或矩阵可以是向量或矩阵可以是向量或矩阵 X0 X0 初值初值初值初值第二十一页，讲稿共三十四页哦第二十二页，讲稿共三十四页哦实例：基于实例：基于实例：基于实例：基于Matlab的透镜中心偏测量光轴拟合的透镜中心偏测量光轴拟合的透镜中心偏测量光轴拟合的透镜中心偏测量光轴拟合光学中心偏测量仪作为精确测定和严格校正光学系统中心偏误差的仪器光学中心偏测量仪作为精确测定和严格校正光学系统中心偏误差的仪器光学中心

22、偏测量仪作为精确测定和严格校正光学系统中心偏误差的仪器光学中心偏测量仪作为精确测定和严格校正光学系统中心偏误差的仪器,它可以指出透镜组中的各镜面相对于光轴的中心偏移数值大小和方向。它可以指出透镜组中的各镜面相对于光轴的中心偏移数值大小和方向。它可以指出透镜组中的各镜面相对于光轴的中心偏移数值大小和方向。它可以指出透镜组中的各镜面相对于光轴的中心偏移数值大小和方向。它的测量结果具有两个方面的意义它的测量结果具有两个方面的意义它的测量结果具有两个方面的意义它的测量结果具有两个方面的意义:其一是通过根据被测光学件各面其一是通过根据被测光学件各面其一是通过根据被测光学件各面其一是通过根据被测光学件各面

23、的中心误差是否超出的中心误差是否超出的中心误差是否超出的中心误差是否超出,来判定光学件是否合格来判定光学件是否合格来判定光学件是否合格来判定光学件是否合格;其二是根据测量的结其二是根据测量的结其二是根据测量的结其二是根据测量的结果来指导光学系统的装校。果来指导光学系统的装校。果来指导光学系统的装校。果来指导光学系统的装校。为消除被测件在测量仪器上的安装定位过程带来的误差为消除被测件在测量仪器上的安装定位过程带来的误差为消除被测件在测量仪器上的安装定位过程带来的误差为消除被测件在测量仪器上的安装定位过程带来的误差,必须对直接测必须对直接测必须对直接测必须对直接测量的数据进行修正。光轴拟合就是对测

24、量数据的优化和修正的量的数据进行修正。光轴拟合就是对测量数据的优化和修正的量的数据进行修正。光轴拟合就是对测量数据的优化和修正的量的数据进行修正。光轴拟合就是对测量数据的优化和修正的过程。提出一种光轴拟合的数学模型过程。提出一种光轴拟合的数学模型过程。提出一种光轴拟合的数学模型过程。提出一种光轴拟合的数学模型,该数学模型结合了解析方法该数学模型结合了解析方法该数学模型结合了解析方法该数学模型结合了解析方法和数值分析方法和数值分析方法和数值分析方法和数值分析方法,考虑了中心偏测量的实际情况考虑了中心偏测量的实际情况考虑了中心偏测量的实际情况考虑了中心偏测量的实际情况,在严格的数学模型基在严格的数

25、学模型基在严格的数学模型基在严格的数学模型基础上做了合理的简化础上做了合理的简化础上做了合理的简化础上做了合理的简化,使光轴的拟合问题最终转化为对线性方程使光轴的拟合问题最终转化为对线性方程使光轴的拟合问题最终转化为对线性方程使光轴的拟合问题最终转化为对线性方程组的求解。组的求解。组的求解。组的求解。第二十三页，讲稿共三十四页哦第二十四页，讲稿共三十四页哦3)3)应用最小二乘法得到关于四参数的线性方程组。应用最小二乘法得到关于四参数的线性方程组。应用最小二乘法得到关于四参数的线性方程组。应用最小二乘法得到关于四参数的线性方程组。得到各面球心的位置坐标后得到各面球心的位置坐标后得到各面球心的位置

26、坐标后得到各面球心的位置坐标后,按照一般直线拟合的方法按照一般直线拟合的方法按照一般直线拟合的方法按照一般直线拟合的方法,应使各球心对优应使各球心对优应使各球心对优应使各球心对优化轴距离的平方和最小化轴距离的平方和最小化轴距离的平方和最小化轴距离的平方和最小,符合数学上的最小二乘法。符合数学上的最小二乘法。符合数学上的最小二乘法。符合数学上的最小二乘法。N N个球心到优化轴个球心到优化轴个球心到优化轴个球心到优化轴距离的平方和距离的平方和距离的平方和距离的平方和:第二十五页，讲稿共三十四页哦第二十六页，讲稿共三十四页哦第二十七页，讲稿共三十四页哦第二十八页，讲稿共三十四页哦扩展：基于扩展：基于

27、扩展：基于扩展：基于MATLABMATLAB的非线性方程组遗传解法的非线性方程组遗传解法胡斐，赵治国胡斐，赵治国胡斐，赵治国胡斐，赵治国(同济大学汽车学院，上海同济大学汽车学院，上海同济大学汽车学院，上海同济大学汽车学院，上海201804)201804)遗传算法是一种基于自然选择的用于求解有约束和无约束最优问题的遗传算法是一种基于自然选择的用于求解有约束和无约束最优问题的遗传算法是一种基于自然选择的用于求解有约束和无约束最优问题的遗传算法是一种基于自然选择的用于求解有约束和无约束最优问题的方法。遗传算法反复修改包含若干个体的种群。遗传算法在每一步中，方法。遗传算法反复修改包含若干个体的种群。遗

28、传算法在每一步中，方法。遗传算法反复修改包含若干个体的种群。遗传算法在每一步中，方法。遗传算法反复修改包含若干个体的种群。遗传算法在每一步中，随机从当前种群中选择若干个个体作为父辈，并用它们产生下一代子随机从当前种群中选择若干个个体作为父辈，并用它们产生下一代子随机从当前种群中选择若干个个体作为父辈，并用它们产生下一代子随机从当前种群中选择若干个个体作为父辈，并用它们产生下一代子辈。在若干代之后，种群就朝着最优解辈。在若干代之后，种群就朝着最优解辈。在若干代之后，种群就朝着最优解辈。在若干代之后，种群就朝着最优解“进化进化进化进化”。我们可以利用遗。我们可以利用遗。我们可以利用遗。我们可以利用

29、遗传算法去解决各种最优化问题，包括目标函数是不连续、不可微、传算法去解决各种最优化问题，包括目标函数是不连续、不可微、传算法去解决各种最优化问题，包括目标函数是不连续、不可微、传算法去解决各种最优化问题，包括目标函数是不连续、不可微、随机或者高度非线性的问题。随机或者高度非线性的问题。随机或者高度非线性的问题。随机或者高度非线性的问题。MATLABMATLAB的遗传算法与直接搜索工具箱（的遗传算法与直接搜索工具箱（的遗传算法与直接搜索工具箱（的遗传算法与直接搜索工具箱（Genetic Algorithm and Genetic Algorithm and Direct Search Toolb

30、oxDirect Search Toolbox，简称，简称，简称，简称GADSGADS）是）是）是）是MATLABMATLAB的一个优化工具的一个优化工具的一个优化工具的一个优化工具箱。它有两种使用方式：一种是通过命令行调用箱。它有两种使用方式：一种是通过命令行调用箱。它有两种使用方式：一种是通过命令行调用箱。它有两种使用方式：一种是通过命令行调用gaga函数，另一种函数，另一种函数，另一种函数，另一种是通过图形界面调用。是通过图形界面调用。是通过图形界面调用。是通过图形界面调用。第二十九页，讲稿共三十四页哦第三十页，讲稿共三十四页哦第三十一页，讲稿共三十四页哦第三十二页，讲稿共三十四页哦小小 结结线性方程组求根方法的几何意义线性方程组求根方法的几何意义线性方程组求根方法的几何意义线性方程组求根方法的几何意义线性方程组求根函数线性方程组求根函数线性方程组求根函数线性方程组求根函数的理解与应用的理解与应用的理解与应用的理解与应用第三十三页，讲稿共三十四页哦感谢大家观看第三十四页，讲稿共三十四页哦