非线性方程求根§5.2.ppt

* §5.2 迭代法 1. 简单迭代法 2. 迭代法的收敛性 3. 局部收敛性与收敛速度 4. 迭代法的加速 1. 简单迭代法 　对非线性方程　　　 f(x)=0 　　(5.1) 若可化为等价形式的方程 由此得递推公式 x = ?(x) 　 (5.2) xk?1 = ?(xk) 　 k ? 0,1,? (5.3) 给定初值x0后可得序列x0 , x1 , ? , xk , ? 如果当k??时，序列?xk?有极限x?，且?(x)在x?附近连续，则 即x? = ?(x?) 因而x?是方程(5.2)的根．由于方程(5.2)和方程(5.1)等价，因而x?是方程(5.1)的根． 　一般地我们称式(5.3)为迭代格式，也称迭代公式， ?xk?为迭代序列， x0为迭代初值， ?(x)为迭代函数．相应地，用迭代格式(5.3)求得方程近似根的方法称为简单迭代法，或称逐次逼近法，也简称为迭代法． 　当迭代序列收敛时，称迭代法收敛． 　当x0? x?时，如果序列?xk?无极限，则称迭代法发散． 　然而，这种等价转换的方法很多，不同的转换方法得到不同的迭代函数?(x) ，对应不同的迭代法．现在的问题是，由方程得到的迭代格式是否一定收敛？考察一个简单的例子． 例5.5 求方程 x 3?x ? 1?0在区间(1,1.5)内的一个实根． 解 看来序列可能收敛（实际上， x? =1.324717951?）． 看来序列可能发散． 　由(1)和(2)表明，同一个方程得到的不同迭代格式，有的收敛，有的发散．那么迭代格式要满足什么条件才能使迭代序列收敛呢？这正是下面要讨论的问题． 2. 迭代法的收敛性 定理 5.1 若?(x)在[a,b]上具有一阶连续导数，且满足条件： (1)当x?[a,b]时，?(x)?[a,b]； (2) 存在正数 L1，使对任意 x?[a,b]，有 ???(x)? ? L1，则有 (1)方程x ? ?(x)在区间[a,b]上存在唯一根 x? ； (2) 对任何初值 x0?[a,b]，由xk?1= ?(xk) k ? 0,1,?确定的 xk收敛于x? ； 证明 (1)作函数 g(x)?x??(x)，由条件(1)知g(a)?a??(a)?0 g(b)?b??(b)?0，因而g(x)?0在区间[a,b]上至少存在一个根．又因g ?(x)?1???(x)?1?L0，知g(x)?0在区间[a,b]上至多有一个根,因而g(x)?0在[a,b]内存在唯一根，即 x ? ?(x)在[a,b]内存在唯一根，记为x? ． (2) 由x0?[a,b]及条件(1)知xk?[a,b] (k ? 1,2,? )，因 ?xk?1 ?x??= ??(xk) ? ?(x?)? = ?(xk ?x?)??(?k)? ?k在xk与x?之间 (3) 因?xk?x??= ??(xk?1) ??(x?)? = ?(xk?1?x?)??(?)? ?在xk?1与x?之间 ?L?xk ?x?? ? ?? Lk?1?x0 ?x???0 (k?? ) ?L?xk?1?x??= L?xk?1?xk?xk?x?? ? L?xk?x??? L?xk ?xk?1? (4) 因?xk?xk?1?= ??(xk?1) ??(xk?2)? = ?(xk?1?xk?2)??(?)? ?L?xk?1?xk?2 ?? L2?xk?2?xk?3? ? ? ? Lk?1?x1?x0? (1) 因 ?xk?x??= ?xk?1?x??xk?xk?1? ? ?xk?1?x????xk?xk?1? ? L?xk?x????xk?xk?1?，因而 所以常用 ?xk?1 ? xk? ? ? 来控制精度． (2) 若L很接近于1时，则收敛可能很慢．(?)式是直接用计算结果xk与xk?1 来估计误差的，因而称为误差事后估计式． (3)而(??)式是在尚未计算时即能估计出第k次迭代近似值xk的误差? x??xk?，因此称为误差事前估计式．用它可求得需要迭代的步数． 定理 5.1? 设方程x??(x)在[a,b]内有根x?，且当x?[a,b]时， ???(x)??1，则对任意初始值x0?[a,b]且x0?x?，迭代公式xk?1=?(xk)发散． 不满足定理条件． 例5.6 用迭代法求方程 f(x) ? x (x?1)2?1?0 在区间[0,1]内的 解 一个实根，精确至4位有效数字． 当x?[0,1]时， ?(x)?[?(1), ?(0)]?[0.25,1]?[0,1]，于是定理5.1的条件(1)满足，但???(0)??2，条件(2)不满足．因此需要缩小 有根区间．从x0 ? 0开始，以h?0.2为步长，逐步验证，得f(0.2)0， f(0.4)0， f(0.6)0，由此可