资源描述
第六章第六章逐次逼近法逐次逼近法6.3 解非线性方程的迭代法解非线性方程的迭代法华长生制作1第六章 逐次逼近法6.3 解非线性方程的迭代法数值计算方本本节主要内容主要内容3-1 解非线性方程的简单迭代法解非线性方程的简单迭代法3-2 Newton迭代法及其变形迭代法及其变形本节主要内容3-1 解非线性方程的简单迭代法 6.3 6.3 非线性方程的迭代法非线性方程的迭代法 方程是在科学研究中不可缺少的工具，方程求解是科方程是在科学研究中不可缺少的工具，方程求解是科学计算中一个重要的研究对象学计算中一个重要的研究对象.设函数方程设函数方程统称为非线性方程统称为非线性方程 几几百百年年前前就就已已经经找找到到了了代代数数方方程程中中二二次次至至五五次次方方程程的的求求解解公公式式,但但是是,对对于于更更高高次次数数的的代代数数方方程程目目前前仍仍无无有有效效的的解解析析解解法法，对对于于无无规规律律的的超超越越方方程程的的求求解解也也无无精精确确解解法法.因此因此,研究非线性方程的数值解法成为必然研究非线性方程的数值解法成为必然.6.3 非线性方程的迭代法 方程是在科学研注注.(1)非线性方程一般情况下很难求得其解析解非线性方程一般情况下很难求得其解析解,所以往往采用数值方法求解所以往往采用数值方法求解.(2)非线性方程中非线性方程中,通常假设函数通常假设函数 f(x)是连续的是连续的.求非线性方程求非线性方程的根的根.f(x)=0-(3.1)求非线性方程的根求非线性方程的根,即求曲线即求曲线 y=f(x)与与 x 轴的交点轴的交点单根区间单根区间:方程在区间方程在区间 a,b 只有一根只有一根多根区间多根区间:方程在区间方程在区间 a,b 有多个根有多个根有根区间有根区间xyy=f(x)aAb0B保证有解注.(1)非线性方程一般情况下很难求得其解析解,(2)3-13-1简单迭代法迭代法思思路路2.建立迭代格式建立迭代格式:求解非线性方程问题转化为求序列极限问题求解非线性方程问题转化为求序列极限问题1.将将 化为与它同解的方程化为与它同解的方程:-(3.2)即若存在即若存在,使使 ,则有则有 ;反之也成立反之也成立.-(3.3)称称(3.3)为求解非线性方程的为求解非线性方程的(简单简单)迭代法迭代法迭代过程迭代过程迭代格式迭代格式.若当若当 时时 ,则迭代法则迭代法(3.3)收敛收敛,就是就是方程方程(3.1)的解的解,否则迭代法发散否则迭代法发散.3.从初值从初值 出发出发,得到序列得到序列迭代函数3-1 简单迭代法思路2.建立迭代格式:求解非线性方程问题 根的存在与唯一性根的存在与唯一性:方程有没有根？若有根方程有没有根？若有根,是否唯一是否唯一?研究研究内容内容 迭代格式的收敛性迭代格式的收敛性:如何构造收敛的迭代格式如何构造收敛的迭代格式？定理3.1:解的存在与唯一性定理 收敛速度的确定；收敛速度的确定；收敛阶的概念及判定定义3.1,定理3.2 根的存在与唯一性:方程有没有根？若有根,研究 迭代格例例1 用迭代法求用迭代法求 的根的根.(1)化为等价方程化为等价方程:取取 ,代入上式得代入上式得:得迭代格式得迭代格式:显然显然,当当 时时,即迭代法收敛即迭代法收敛.另外另外 即即 是方程是方程 f(x)=0 的根的根.解解:例1 用迭代法求 (2)由由 还可得等价方程还可得等价方程:得迭代格式得迭代格式:取取 ,代入上式得代入上式得:显然显然,当当 时时,即迭代法发散即迭代法发散.迭代法的收迭代法的收敛与发散敛与发散,依赖于迭代依赖于迭代函数的构造函数的构造!迭代函数要迭代函数要满足什么足什么条件条件,迭代法才收迭代法才收敛？(2)由 还可得等价方程:得迭代格定理3.1(P225)判断迭代是否可终止的依据判断迭代是否可终止的依据定理3.1(P225)判断迭代是否可终止的依据若迭代函数满足定理若迭代函数满足定理 3.1 的条件的条件,则迭代法收敛则迭代法收敛.那么那么迭代迭代过程何程何时结束？束？l 由由(3.4)(3.4)知知,只要相邻两次计算值的差只要相邻两次计算值的差 达到事先给达到事先给定的精度要求定的精度要求 ,迭代过程可终止迭代过程可终止,即即l 由由(3.5)(3.5)知知,若已知若已知 L L 的范围的范围,则由给定的精度可大致估计则由给定的精度可大致估计 迭代所需次数迭代所需次数 k(3.4)(3.5)判断迭代可终止的条件判断迭代可终止的条件估计迭代次数估计迭代次数迭代法的结束条件迭代法的结束条件如何确定迭代次数？如何确定迭代次数？迭代法次数的确定迭代法次数的确定若迭代函数满足定理 3.1 的条件,则迭代法收敛.那么迭代过局部收敛问题局部收敛问题 定理定理3.1的条件一般难于验证的条件一般难于验证,且在大区间且在大区间 a,b 上上,这这些条件未必满足些条件未必满足,因此使用迭代法时，往往只在根因此使用迭代法时，往往只在根附近进附近进行行.即只要假定即只要假定 在在的附近的小邻域内连续的附近的小邻域内连续,且满足且满足则存在则存在的某个邻域的某个邻域 ,在在S上上 满足定理满足定理3.1的条件的条件,称这种收敛为称这种收敛为局部收敛局部收敛.一般一般,在给定精度下在给定精度下,要求方程在某点附近的根要求方程在某点附近的根.局部收敛问题 定理3.1的条件一般难于验证,且在大区间 例例2 求求 在在 附近的一个根附近的一个根,要求精度要求精度 .解解(2)利用定理利用定理3.1验证所建立迭代格式的收敛性验证所建立迭代格式的收敛性(1)首先化等价方程首先化等价方程,建立迭代格式建立迭代格式 当当 时时,所建迭代格式所建迭代格式 满足定理满足定理3.1的条件的条件,对于初始对于初始值值 收敛收敛.确定迭代区间确定迭代区间,取取 一般选择根附近的一个小区间 当当 时，时，是单调递减函数是单调递减函数.当当 时，时，例2 求 在 0 0.5 0.606 531 0.106531 迭代结果迭代结果:1 0.606 531 0.545 239 0.061 292 2 0.545 239 0.579 703 0.034 464 3 0.579 703 0.560 065 0.019 638 4 0.560 065 0.571 172 0.011 107 5 0.571 172 0.564 863 0.006 309 6 0.564 863 0.568 439 0.003 576 7 0.568 439 0.566 409 0.002 030 8 0.566 409 0.567 560 0.001 151 9 0.567 560 0.566 907 0.000 6530.566 907 是方程在是方程在 x=0.5 附近的计算根附近的计算根.0 0.5 从从定理定理3.1可见可见,一方面一方面,当当 L 或或 的值越小的值越小,迭代收敛的速度越迭代收敛的速度越快快;另一方面另一方面,当当 L 1 称为超线性收敛称为超线性收敛;p=2 称为平方收敛称为平方收敛.p越大越大,迭代法收敛速度越快迭代法收敛速度越快定义定义3.1 设迭代格式设迭代格式 xk+1=(xk),当当k时时,xk+1,记误记误差差 。若存在实数。若存在实数 p 1 和和 c 0 满足满足则称迭代法为则称迭代法为 p 阶收敛阶收敛.-(3.7)如何定量判断如何定量判断收收敛速度速度?从定理3.1可见,一方面,当 L 或 收敛阶的判定收敛阶的判定定理定理3.2 如果如果 x=(x)中中,迭代函数迭代函数 (x)在根在根附近附近满足：满足：（1 1）(x)存在存在 p 阶导数且连续；阶导数且连续；（2 2）()=()=(p-1)()=0,(p)()0 则迭代法则迭代法 xk+1=(xk)为为 p 阶阶收敛收敛.例例3 设设 ,证明由证明由建立的迭代法至少是平方收敛的建立的迭代法至少是平方收敛的.-(3.8)Newton 迭代法迭代法证明证明 只需证明只需证明 ,见教材见教材 p228.收敛阶的判定定理3.2 如果 x=(x)中,迭代函3-2Newton3-2Newton迭代法及其迭代法及其变形形 用迭代法解非线性方程时，如何构造迭代函数是非用迭代法解非线性方程时，如何构造迭代函数是非常重要的常重要的.主要介绍：主要介绍：1）Newton迭代法迭代法2）弦截法）弦截法1、Newton迭代法（又称作切线法）迭代法（又称作切线法）Newton法法是是求求解解方方程程 f(x)=0的的一一种种重重要要的的迭迭代代法法。这这种种方方法法的的基基本本思思想想是是设设法法将将非非线线性性方方程程 f(x)=0逐逐步步转转化为某种线性方程求解。化为某种线性方程求解。3-2 Newton迭代法及其变形 用迭代法解如果将非线性方程如果将非线性方程化为等价方程化为等价方程所以可以令所以可以令 ，这样就能保证，这样就能保证(1)(1)式对应的迭代法至式对应的迭代法至少是平方收敛的。少是平方收敛的。即：即：那么如何确定那么如何确定k(x)的形式使上式成立并使其所对应的迭的形式使上式成立并使其所对应的迭代法收敛呢？代法收敛呢？（1）如果将非线性方程化为等价方程所以可以令 ，这样于是取于是取(2)-(3.10)注注意意：1)Newton迭迭代代法法的的优优点点:收收敛敛速速度度快快（至至少少是是平平方方收收敛敛的的）。2)Newton迭迭代代法法的的缺缺点点：需需要要计计算算导导数数 ，如如果果函函数数f(x)比比较较复复杂杂，使使用用Newton公公式式是是不不方方便便的的。为为了了避避开开导导数数的的计计算算，可可以以用用导导数数的的近近似似值值来来替替代代 ，得到所谓的，得到所谓的弦截法弦截法。于是取(2)-(3.10)注意：1)Newton迭代法2、弦截法、弦截法中含有函数的导数中含有函数的导数,不方便求不方便求.-(3.10)代入代入(3.10)得得Newton迭代法迭代法:可用导数的近似式代替，即可用导数的近似式代替，即-(3.11)弦截法弦截法的收敛阶为p1.6182、弦截法中含有函数的导数,不方便求.-BAxk-1xkxk+2xk+1xk+1xk+2y=f(x)f(xk)f(xk-1)Newton迭代法与弦截法的几何意义迭代法与弦截法的几何意义xy弦截法不需要求导弦截法不需要求导,但但需要两个初始值需要两个初始值;Newton 法虽需求导法虽需求导,但只需一个初始值但只需一个初始值.二者比较二者比较:Newton 法法又称切线法又称切线法BAxk-1xkxk+2xk+1xk+1xk+2y=f例例4（P230）用用Newton法和弦截法分别计算方程法和弦截法分别计算方程在在 x=1.5 附近的根附近的根.时停止计算时停止计算解解取初值取初值 x0=1.5,代入上式代入上式,得计算解序列：得计算解序列：x11.347 83,x21.325 20,x31.324 72,x41.324 72，(1)用用Newton法：法：注意：注意：1）Newton法在根法在根 附近收敛，初值应选在附近收敛，初值应选在 附近；附近；初值选的不合适会导致初值选的不合适会导致Newton迭代法发散迭代法发散;2）Newton法的收敛速度与初值、收敛阶数有关。法的收敛速度与初值、收敛阶数有关。因此因此 1.324 72例4（P230）用Newton法和弦截法分别计算方程解取取初值取初值 x0=1.5,x1=1.4 代入上式代入上式,得计算解序列：得计算解序列：x21.335 22,x31.325 41,x41.324 72,x51.324 72，(3)若用若用Newton法法,取初值取初值 x0=0,得得x1=1,x2=-0.5,x30.33,x4-1.44 发散震荡！两个初值!(2)用弦截法用弦截法:因此因此 1.324 72初始值的选取影响初始值的选取影响Newton法的收敛性！法的收敛性！取初值 x0=1.5,x1=1.4 代入上式,得1.32472x1=1.34783x0=1.5x2=1.325 20收敛1.32472x1=1.34783x0=1.5x2=x30.33x1=-1x2=-0.5x4-1.44x0=0发散x30.33x1=-1x2=-0.5x4-1.44x
展开阅读全文