§3-4 Newton迭代法 、迭代法的收敛阶 定义1设a市方程x=x(x)的根(或不动点),当x充分接近a时,由公式 n1=x(x)得到的序列{xn改收敛于a若存在常数p≥1和正常数c,使得 n→) 则称序列{xn}是p阶收敛的,或称{xn的收敛阶为,称(x)是p阶迭代函数 二、 Newton法迭代格式 设x是方程f(x)=0的一个近似根,将f(x)在x处作7ayo展开 f(x)f(x)+f(x(x-x) 以线性方程 f(n)+f(rn(x-xn)=0 代替非线性方程f(x)=0.若f(xn)≠0.,则其解
§ 3-4 Newton迭代法 一、迭代法的收敛阶 { } { } ( ) . ( ) { } . 1 , 1 ( ) 1 n 1 0 lim 则称序列 是 阶收敛的，或称 的收敛阶为 ，称 是 阶迭代函数 得到的序列 收敛于 若存在常数 和正常数 使得 定义 设 市方程 的根（或不动点），当 充分接近 时，由公式 x p x p z x p c x x x z x x p c x z x x n n p n n n n n = − − = = + → + 二、Newton法迭代格式 代替非线性方程 若 则其解 以线性方程 设 是方程 的一个近似根，将 在 处作 展开 ( ) 0. ( ) 0, ( ) ( )( ) 0 ( ) ( ) ( )( ) ( ) 0 ( ) = + − = + − = n n n n n n n n n f x f x f x f x x x f x f x f x x x x f x f x x Taylor
(n=0,132,…) (3-4-1 按以上迭代公式求方程f(x)=0的近似解的方法称为 Newton法 (3-4-1)称为NeOm法迭代公式 、 Newton法的几何意义 以f(x)为斜率做过(x02f(x)点的直线,即作f(x)在点x的 切线方程 y-f(xo)=f'lxoXx-xo) 令y=0则得此切线与x轴的交点x,即 x1=x0-f(x)(x) 再作f(x)x处的切线,得交点x2,逐步逼近方程的根a,如图
）称为 法迭代公式 按以上迭代公式求方程 的近似解的方法称为 法， （ ） Newton f x Newton n f x f x x x n n n n (3 4 1 ( ) 0 ( 0,1,2, ) 3 4 1 ( ) ( ) 1 − − = = − − + = − 三、Newton法的几何意义 ( ( )) ( ) ( ) ( )( ) ( ) ( ) 再作 ( )的 处的切线，得交点 ，逐步逼近方程的根 ，如图 令 则得此切线与 轴的交点 ，即 切线方程 以 为斜率做过 点的直线，即作 在点 的 1 2 1 0 0 0 1 0 0 0 0 0 0 0 0 ( ) , f x x x x x f x f x y x x y f x f x x x f x x f x f x x = − = − = −
四、 Newton法的收敛性 定理1设f(x)在a的某一邻域有二阶连续导数,f(a)=0,且f(a)≠0,则 当x充分接近a时,由 Newton法所产生的序列{xn收敛于方程f(x)=0的根 且收敛阶不小于2
四、Newton法的收敛性 ( ) ( ) ( ) ( ) 2 Newton { } 0 1 0 0 0 且收敛阶不小于 当 充分接近 时，由 法所产生的序列 收敛于方程 的根， 定理 设 在 的某一邻域有二阶连续导数， ，且 ，则 = = x x f x f x f f n
定理2设函数()在区间ab存在二阶导数,且满条件: 1°f(a)f(b)<0 f(x)≠0,x∈[a,b 3f"(x)ab上不变号; φ取初始值x∈[a,b],使得f(x)f"(x)>0 则由 Newton迭代公式产生的序列xn收敛于方程fx)=0在a,b的唯一根a 且收敛阶为2 五、 Newton迭代算法 目标求方程(x)=0根 输入初始值x允许误差G:迭代的最大次数N 输出近似解x或方法失败的信息 步骤s1对n=12.…,N做S11-12 S11置x=x0-f(x)f(x) S12若x-x<E,则输出x,停机 否则x S2输入“ Method failed”;停机
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2. { } 0 [ , ] 4 [ , ], 0. 3 [ , ] 2 0, [ , ]; 1 0; 2 [ , ] 0 0 0 0 0 0 0 且收敛阶为 则由 迭代公式产生的序列 收敛于方程 在 的唯一根 ， 取初始值 使得 在 上不变号； 定理 设函数 在区间 上存在二阶导数，且满足条件： Newton x f x a b x a b f x f x f x a b f x x a b f a f b f x a b n = 五、Newton迭代算法 . 输入 初始值x0；允许误差；迭代的最大次数N 步骤 输出 近似解x或方法失败的信息 S1 ( ) ( ) . 12 , ; . 11 ; 1,2, , 11 ~ 12. 0 0 0 0 0 x x S x x x S x x f x f x n N S S = − = − = 否则 若 则输出 停机 置 对 做 S2 输入“Method failed”；停机. 目标 求方程f (x) = 0的根
例用 Newton迭代法求c(c>0,p=土1,+2, 解:设x=cV,则x-c=0, 取f(x)=x-C 则f(x)=px2 所以 Newton法的迭代公式为: P n+1- P x +c p>0 p) -cx p<
例 用 Newton 迭代法求 c 1 p (c 0), p = 1,2, , 0, 1 x = c x −c = p 则 p 取 f x x c p ( ) = − 解： 设 则 ( ) −1 = p f x px 所以 Newton法的迭代公式为： ( ) ( ) ( ) ( ) − − − − + = − = − − − + − 1 0 1 0 1 1 1 1 p cx p p x p x c x p p px x c x x p n n p n n p n p n n n