6.2迭代法.ppt

1第二节第二节第二节第二节 迭代法迭代法迭代法迭代法2 2009,Henan Polytechnic University22 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 它是一种逐次逼近的方法它是一种逐次逼近的方法,用某个固定公式反复用某个固定公式反复校正根的近似值校正根的近似值,使之逐步精确化，最后得到满足精使之逐步精确化，最后得到满足精度要求的结果。度要求的结果。3 2009,Henan Polytechnic University32 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根6.2.1 迭代法的基本思想迭代法的基本思想 为求解非线性方程为求解非线性方程f(x)=0的根，先将其写成便于的根，先将其写成便于迭代的等价方程迭代的等价方程其中其中 为为x的连续函数的连续函数。4 2009,Henan Polytechnic University42 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 即如果数即如果数 使使 f(x)=0,任取一个初值任取一个初值 ,代入式代入式 的的右端右端,得到得到则也有则也有反之反之,若若 ,则也有则也有再将再将 代入式代入式 的右端的右端,得到得到 5 2009,Henan Polytechnic University52 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根上式称为求解非线性方程的简单迭代公式上式称为求解非线性方程的简单迭代公式,依此类推依此类推,得到一个数列得到一个数列其一般表示其一般表示 称称 为迭代函数为迭代函数 。6 2009,Henan Polytechnic University62 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 例例1 1 试用迭代法求方程试用迭代法求方程 在区间在区间(1，2)内的实根。内的实根。解：由解：由 建立迭代关系建立迭代关系计算结果如下计算结果如下:k=0,1,2,3.7 2009,Henan Polytechnic University72 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根精确到小数点后五位精确到小数点后五位kk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.324948 2009,Henan Polytechnic University82 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根但如果由但如果由 建立迭代公式建立迭代公式仍取仍取 ，则有，则有显然结果越来越大，显然结果越来越大，是发散序列是发散序列9 2009,Henan Polytechnic University92 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根（全局收敛定理）（全局收敛定理）6.2.2 收敛性分析收敛性分析10 2009,Henan Polytechnic University102 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根存在唯一性存在唯一性做辅助函数做辅助函数，则有，则有所以，存在点所以，存在点若若，则有：则有：又，又，11 2009,Henan Polytechnic University112 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根则则所以，任意的初值都收敛所以，任意的初值都收敛12 2009,Henan Polytechnic University122 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根误差估计误差估计13 2009,Henan Polytechnic University132 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 注：注：L越小，收敛越快。越小，收敛越快。14 2009,Henan Polytechnic University142 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根例例2 2 证证明明函函数数 在在区区间间11，22上满足迭代收敛条件。上满足迭代收敛条件。证明：证明：15 2009,Henan Polytechnic University152 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 16 2009,Henan Polytechnic University162 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根若取迭代函数若取迭代函数 不满足定理，故不能肯定不满足定理，故不能肯定 收敛到方程的根。收敛到方程的根。17 2009,Henan Polytechnic University172 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 定理定理 设设 是方程是方程 的根，如果满足条的根，如果满足条件件 ：（1 1）迭代函数）迭代函数 在在 的邻域可导；的邻域可导；（2 2）在）在 的某个邻域的某个邻域 ，对于任意，对于任意 ，有，有 局部收敛性局部收敛性18 2009,Henan Polytechnic University182 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 则对于任意的初始值则对于任意的初始值 ，由迭代公式，由迭代公式 产生的数列产生的数列 收敛于方程的根。收敛于方程的根。（这时称迭代法在（这时称迭代法在 的的S S邻域具有局部收敛性。）邻域具有局部收敛性。）19 2009,Henan Polytechnic University192 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根例例3 3 设设 ，要使迭代过程，要使迭代过程 局部收敛到局部收敛到 ,求求 的取值范围。的取值范围。解：解：由在根由在根 邻域具有局部收敛性时，邻域具有局部收敛性时，收敛条件收敛条件 20 2009,Henan Polytechnic University202 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根所以所以 21 2009,Henan Polytechnic University212 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 实实际际计计算算中中当当然然不不可可能能也也没没必必要要无无穷穷多多步步地地做做下下去去,对预先给定的精度要求对预先给定的精度要求，只要某个，只要某个n满足满足即可结束计算并取即可结束计算并取 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。22 2009,Henan Polytechnic University222 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根xyy=xx*y=g(x)x0p0 x1p1 xyy=xx*y=g(x)x0p0 x1p1简单迭代收敛情况的几何解释简单迭代收敛情况的几何解释23 2009,Henan Polytechnic University232 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根定义定义 设迭代过程设迭代过程 收敛于收敛于 的的根根 ,记迭代误差记迭代误差若存在常数若存在常数p（p1）和和c（c0），），使使 则称序列则称序列 是是 p 阶收敛的阶收敛的,c称渐近误差常数。特别称渐近误差常数。特别地地,p=1时称为线性收敛时称为线性收敛,p=2时称为平方收敛。时称为平方收敛。1 p 2时称为超线性收敛。时称为超线性收敛。6.2.3 迭代法的收敛速度迭代法的收敛速度24 2009,Henan Polytechnic University242 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根 数数p的大小反映了迭代法收敛的速度的慢，的大小反映了迭代法收敛的速度的慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。对迭代法收敛速度的一种度量。25 2009,Henan Polytechnic University252 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根定理定理 设迭代过程设迭代过程 ,若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程在则迭代过程在 邻域是邻域是p阶收敛的。阶收敛的。证证:由于由于所以所以 有局部收敛性有局部收敛性,将将 在在 处处泰勒展开泰勒展开即在即在 邻域邻域 ,26 2009,Henan Polytechnic University262 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根根据已知条件得根据已知条件得 由迭代公式由迭代公式 及及有有27 2009,Henan Polytechnic University272 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根例例4 4 已知迭代公式已知迭代公式 收敛于收敛于证明该迭代公式平方收敛。证明该迭代公式平方收敛。证证:迭代公式相应的迭代函数为迭代公式相应的迭代函数为将将 代入，代入，根据定理可知，迭代公式平方收敛。根据定理可知，迭代公式平方收敛。28 2009,Henan Polytechnic University282 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度,可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 p29 2009,Henan Polytechnic University292 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根（1 1）迭代）迭代-加速公式（加权法）加速公式（加权法）设设 是根是根 的某个近似值的某个近似值,用迭代公式校正一次得用迭代公式校正一次得 6.2.4 迭代过程的加速迭代过程的加速又又根据中值定理有根据中值定理有30 2009,Henan Polytechnic University302 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根可见可见,若将迭代值若将迭代值 与与 加权平均加权平均,则可得到的则可得到的 是比是比 更好的近似根更好的近似根则有：则有：当当 范围不大时范围不大时,设设 变化不大变化不大,其估计值为其估计值为L L 31 2009,Henan Polytechnic University312 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根迭代：迭代：改进：改进：或合并写成：或合并写成：32 2009,Henan Polytechnic University322 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根例例5 5 用加权法加速技术求方程用加权法加速技术求方程 在在0.50.5附近的一个根。附近的一个根。取取L=-0.6=-0.6，建立如下迭代公式建立如下迭代公式解：解：因为在因为在 附近附近33 2009,Henan Polytechnic University332 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根仍取仍取 ,逐次计算得逐次计算得 =0.56658 =0.56714。迭代迭代4 4次便可得到精度次便可得到精度 的的结果结果,而不用加速技术需迭代而不用加速技术需迭代1818次次,效果显著。效果显著。34 2009,Henan Polytechnic University342 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根（2 2）埃特金）埃特金（Aitken）方法方法 在在加加权权法法中中,估估计计L L的的值值有有时时不不太太方方便便。假假设在求得设在求得 以后以后,先求出先求出由由 利用中值定理可得利用中值定理可得(在求根区间变化不大在求根区间变化不大,用某个定值用某个定值L L近似地替代之近似地替代之)35 2009,Henan Polytechnic University352 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根将迭代值将迭代值 再迭代一次再迭代一次,得新的迭代值得新的迭代值 将上述两个方程联立消去常数将上述两个方程联立消去常数L化简可得化简可得 则则36 2009,Henan Polytechnic University362 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根这样得到埃特金加速公式这样得到埃特金加速公式37 2009,Henan Polytechnic University372 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根例例6 6 用埃特金方法求方程用埃特金方法求方程 在初值在初值 附近的一个根附近的一个根,精度要求精度要求 ，取迭代格式取迭代格式解解 埃特金方法迭代格式为埃特金方法迭代格式为38 2009,Henan Polytechnic University382 2 2 2 迭代法迭代法迭代法迭代法第六章第六章第六章第六章 方程求根方程求根方程求根方程求根只迭代二次就得到满足精度要求的解。只迭代二次就得到满足精度要求的解。