数值分析课件 第二章2.2.ppt

数值分析 第二章 解非线性方程的数值方法 一、 二分法 二、 迭代法 三、 Newton法 对给定方程f(x)=0,可以用各种方法转化成等价方程 二、 迭代法 1 迭代法的基本思想 若x*是f(x)的根,即若 ,则有 称x*为函数 的一个不动点. 设x0是一个近似解，可以构造序列 迭代法(2.2)称为简单迭代法或单点迭代法. 称函数 为迭代函数. 简单迭代法(2.2), 若迭代序列{xk}保持有界,全在 定义域内称为适定的;若进一步有 称为是收敛的. 若 收敛，即存在x*使得 则由?的连续性和 可得 x* = ? (x*)，即x*是?的不动点，也就是f (x)的零点。 k xk 0 1 2 3 4 5 6 7 1.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 例 求x3-x-1=0在1.5附近的根x* 解 x y y = x x y y = x x y y = x x y y = x x* x* x* x* y= ?(x) y= ?(x) y= ?(x) y=?(x) x0 p0 x1 p1 x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? x2 ? 2 收敛定理和误差估计 定理1 设 在[a, b]上有连续的一阶导数,且 (1) 有 (2) 则有 (1) 函数 在[a ,b]上存在唯一的不动点x* 由迭代公式(2.2)得到的序列 (2) 都收敛到方程的根x* (3) (4) 证明 (1) 先证明存在性,作函数 由条件(1)可知 由连续函数根的存在定理可知,必有 使得h(x*)=0，即 再证明唯一性,设 也是一个解,即 那么 因为L1, 所以有 (2) 由条件(2)和Lagrange中值定理得 因为L1, 所以当 时, 有 (3)和(4) 利用(2)的方法 令 即分别得 定理1的几点说明 (i) 通常将条件(1)称为映内性； (ii) 条件(2)也可以改为：存在常数L且0L1 使得 结论仍然成立, 这个条件通常称为压缩性； (iii) 结论(3)说明 的误差大概是常数 乘上Lk, 但是一般L未知; (iv) 结论(4)说明 与 有关 因此得到迭代法的终止条件 3 一般迭代法的算法 算法： (1) 取初始点x0,最大迭代次数N和精度要求 并置k=0； (2) 计算 (3) 若 则停止计算； (4) 若k=N, 则停止计算；否则k=k+1, 转(2). 4 局部收敛定理 迭代序列{xk}在区间[a,b]上的收敛性通常称为全局收敛性. 实际应用只在不动点x*的邻近考察收敛性，称为局部收敛性. 定义 设 有不动点x*,如果存在x*的某个邻域 对任意的 迭代(2.2)产生的 序列 且收敛到x*,则称(2.2)局部收敛. 证明 由连续函数的性质,存在x*的某个邻域 对任意的 有 而 根据定理1可以断定迭代过程(2.2)对任意初值 均收敛. 定理2 若x*为迭代函数 的不动点, 在x* 的某个邻域内有连续导数,且 则 迭代法(2.2)局部收敛. 例 只用四则运算不用开方求方程x2-3=0的根 解 k xk 迭代法(1) 迭代法(2) 迭代法(3) 迭代法(4) 0 1 2 3 ? x0 x1 x2 x3 ? 2 3 9 87 ? 2 1.5 2 1.5 ? 2 1.75 1.73475 1.732631 ? 2 1.75 1.732143 1.732051 ? 例 设 试讨论a的取值范围 使迭代公式(2.2)局部收敛到 解 因为 所以 由定理2可知只需 即 所以当 时,迭代公式收敛. 例 5 迭代收敛的阶 则称该迭代为r 阶收敛. (C为常数) (1) 当r =1时称为线性收敛，此时C 1； (2) 当r =2 时称为二次收敛，或平方收敛； (3) 当r =1,C=0时称为超线性收敛. 二分法线性收敛; 定义 设迭代