非线性方程的求根方法3.ppt

1、1,Other Kinds of Newton Method Newton 迭代法几个变形,2,简化Newton法（平行弦法） 弦截法，又称割线法，弦位法，线性插值法 Newton下山法 Newton法对重根的求解 抛物线法（muller法），又称二次插值法 代数多项式求根,3,若| (x)|=|1-cf (x)|1，即取0cf (x)2在x*附近成立，则收敛。 若取c=1/f (x0) or 1/f (xk)，则称简化Newton法。,简化Newton法（平行弦法）,迭代公式：,（c0,k=0,1,）,迭代函数：,4,在Newton迭代格式中，用差商近似导数，,弦截法（割线法），弦位法,称弦

2、截法.,得,5,弦截法的几何意义：,弦线PkPk-1的方程：,当y0时，,6,证明略，因弦截法非单步法，不能用前述定理判别 证明参考（关治，陆金甫 数值分析基础）。,7,例 用简化Newton法和弦截法计算方程 x3-3x+1=0的根。,解 设f(x)=x3-3x+1，则f (x)=3x2-3,由简化的Newton法，得,由弦截法，得,8,x0=0.5 x1= 0.3333333333 x2 = 0.3497942387 x3 = 0.3468683325 x4 = 0.3473702799 x5 = 0.3472836048 x6 = 0.3472985550 x7 = 0.34729597

3、59 x8 = 0.3472964208 x9 = 0.3472963440 x10 = 0.3472963572 x11 = 0.3472963553,x0=0.5; x1=0.4; x2 = 0.3430962343 x3 = 0.3473897274 x4 = 0.3472965093 x5 = 0.3472963553 x6 = 0.3472963553,简化Newton法,弦截法,要达到精度10-8，简化Newton法迭代11次，弦截法迭代5次（ Newton迭代法迭代4次）。,9,无论前面哪种迭代法：,（Newton迭代法、,简化Newton法、,弦截法）,Newton迭代法,是否

4、收敛均与初值的位置有关。,例,x0 = 2 x1 = -3.54 x2 = 13.95 x3 = -279.34 x4 = 122017,x0 =1 x1 = -0.5708 x2 = 0.1169 x3 = -0.0011 x4 = 7.9631e-010 x5 = 0,收敛,发散,10,为防止Newton法发散，可增加一个条件： |f(xk+1)|f(xk)|，满足该条件的算法称下山法。 可用下山法保证收敛，Newton法加速收敛。,Newton下山法,（01,下山因子）,记,11,下山因子选取法,12,例 求解方程,要求达到精度|xn-xn-1|10-5，取x0=-0.99.,解：先用N

5、ewton迭代法：f (x)=x2-1,13,用Newton下山法，结果如下：,14,设f(x)=(x-x*)m g(x) ,m 2，m为整数，g(x*)0,则x*为方程f(x)=0的m重根。此时有 f(x*)=f (x*)= f(m-1) (x*)=0, f(m) (x*) 0,Newton法对重根的求解,方法一：只要f (xk ) 0，仍可用Newton法计算，此时为线性收敛。,方法二：若取,则(x*)=0，用迭代法 求m重根，则具2阶 收敛，但要知道m。,15,令,称之为带参数m的Newton迭代法, 它是求方程(x)=0m重根的具有平方收敛的迭代法.,方法二简证：设是方程(x)=0的m

6、重根，则：(x)=(x-)mh(x),其中h(x)在x=处连续且h()0。,则恰是方程F(x)=0的单根, 应用Newton迭代法:,16,方法三：还可令 则 故x*是(x)=0的单根，对(x)用Newton法，可得 它是平方阶收敛的。,这是求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根的重数.,17,例 利用Newton迭代法求方程 (x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正实根.,解 y=(x)的图形为,由图可知,方程在x=4附近有一个重根,在x=7附近有一单根.,18,迭代5次就得到满足精度的解x5=7.348469229,利用求重根的New

7、ton迭代法求重根,取x0=4,可得 x3=4.300000, x4=4.300000, |x4-x3|=0.000000006,若用一般的Newton迭代法求重根,取x0=4,虽然也收敛,却需要迭代19次才能得到满足精度要求的解.,迭代4次就得到满足精度的解x4=4.300000.,19,类似割线法，过三点做f(x)的二次插值多项式,抛物线法（muller法）,20,21,(1) 要有三个初始值 (2) 收敛速度是 1.84 阶。（单根） 二重根的收敛阶是1.23。,各种插值方法的比较,22,代数多项式求解,Splitting Method 劈因子法 秦九韶算法,23,设n次代数方程 用Newton迭代法求有限区间的实根，则要计算 ，一般采用秦九韶算法。,24,由Taylor展式,25,26,27,同理,28,比较x的同次幂系数得： 故代数方程的Newton迭代公式,29,代数方程的Newton迭代法算法,30,Splitting Method 劈因子法,求多项式的根,目标：r = r ( u*, v* ) = 0，s = s ( u*, v* ) = 0。,31,将r 和 s 在初值点( u, v )