求方程根的近似方法.pptVIP

f(x)=0的根(或f(x)的零点)，当f(x)复杂时，很难求（需要找到有效简单的近似方法去求）。,第二章 求方程根的近似方法,2.1 二分法,x1,x2,a,b,何时停下来?,或,不能保证 x 的精度,x*,2,解： f(1)=-50 -(1,2)+ x1=1.5 f(1.5)0 (1,1.5) x2=1.25 f(1.25)0 (1.25,1.375) x4=1.313 f(1.313)0 (1.360,1.368) x8=1.364,例2.1.1 用二分法求 在(1,2)内 的根，要求绝对误差不超过,误差 分析：,第 k 步产生的 xk 有误差,对于给定的精度 , 可估计二分法所需的步数 k ：,缺点：收敛速度慢， 不易求偶数重根. 如图,注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,优点：条件和方法简单(只要求f(x)连续即可)，方法收敛；,一. 迭代法的建立与收敛性,所以, 为f的根的充要条件是为的不动点。,2.2 迭代法,前者收敛：1.5; 1.35721; 1.33086; 1.32588; 1.32494; 1.32476; 1.32473; 1.32472; 1.32472; 后者发散: 1.5; 2.375; 12.39; 问题：何时收敛？,2.收敛定理,定理2.2.1,注1：L越小，收敛越快。 由定理结论(3)或(2.2.2)，只要前后两次迭代值的差值足 够小，就可使近似值 达到任意的精度。在实际计算 中，一般用 来控制迭代过程结束。,注2：定理条件非必要条件，可将a, b缩小，定义局部收敛性：,定义2.2.1 若存在 的某 邻域 B = x | | x | , 使由x0B 开始的迭代都收敛, 则称迭代法具有局部收敛性。,定理2.2.2 设(x)在的某邻域内具有连续的一阶导数， 且 | () | 1， 则迭代法xn+1 = (xn)具有局部收敛性。 证明 省略。,3编程停机判断,时，由（2.2.2）式知,比较小，此时停机，,二.迭代法的收敛阶(收敛速度),则称xn p阶收敛,相应的迭代法称为p阶方法. 特别, p=1时叫线性收敛,此时要求0C1; p=2时叫平方收敛; p越大越好.(why?),定理2.2.3 设(x)在的某邻域 内有充分多阶连续导数，则迭代法xn+1 = (xn)为p阶收敛的充要条件是 () = () = = (p-1)() =0， (p)() 0.,证明 利用Taylor展开式（略）,2.3 牛顿（Newton）法,Taylor展开线性化,近似于,将f(x)在xn点Taylor展开,一. Newton 迭代法,1.迭代公式的建立：,2.Newton迭代法的几何意义, 则,3. Newton迭代法的收敛定理（定理 2.3.1）,解：设,4.Newton迭代法的收敛阶(收敛速度)（定理 2.3.2）,本章基本要求：,1. 熟悉区间二分法； 2.熟