计算方法大作业
题目：非线性方程求根的新方法
班级：xxx
学号：xxx
姓名：xxx
非线性方程求根的新方法
一、问题引入
在计算和实际问题中经常遇到如下非线性问题的求解：
F(x)=0 (1)
我们经常采用的方法是经典迭代法：
经典迭代方法
不动点迭代方法是一种应用广泛的方法，其加速方法较多，如Stiffensen加速方法的局
部收敛阶(以下简称为收敛阶)为2阶；牛顿迭代方法的收敛阶亦为2阶，且与其相联系的一
些方法如简化牛顿法、牛顿下山法、弦截法的收敛阶阶数介于1和2之间；而密勒法的收敛
阶与牛顿法接近，但计算量较大且涉及零点的选择问题，同时收敛阶也不够理想。
因此本文介绍一种新的迭代方法
从代数角度看，牛顿法和密勒法分别是将f(x)在xk附近近似为一线性函数和二次抛物插
值函数，一种很自然的想法就是能否利用Taylor展开，将f(x)在xk附近近似为其他的二次函
数?答案是肯定的.其中的一种方法是将f(x)在Xk处展开3项，此时收敛阶应高于牛顿法，这
正是本文的出发点．
二、算法推导
设函数f(x)在xk附近具有二阶连续导数，则可将f(x)在xk处进行二阶Taylor展开，方程(1)
可近似为如下二次方程：
f(xk)+f’(xk)(x-xk)+2^(-1)f’’(xk)(x-xk)^2=0，(2)
即
2^(-1)f’’(xk)x^2+(f’(xk)-xkf’’(xk))x+2^(-1)f’’(xk)xk^2-xkf’(xk)+f(xk)=0(3)
利用求根公式可得
X=xk-(f’’(xk))^(-1)(f’(xk))-sqrt((f’(xk)^2±2f’’(xk)f(xk)))(4)
其中±符号的选取视具体问题而定，从而可构造迭代公式
X k+1=xk-(f’’(xk))^(-1)(f’(xk))-sqrt((f’(xk)^2±2f’’(xk)f(xk)))(5)
确定了根号前正负号的迭代公式(5)，可称为基于牛顿法和Taylor展开的方法，简记为BNT
方法．
为描述方便起见，以下将f(xk)，f’(xk)，f’’(xk)分别记为f,f’,f’’．首先，二次方程(3)对应于一
条抛物曲线，其开口方向由f’’(xk)，x∈U(xk)的符号确定，其中U(xk)为xk的某邻域，其顶点
为
P(xk-(f’’)^(-1)f’，fk-(2f’’)^(-1)(f’)^2)．为使(5)式唯一确定x k+1，须讨论根式前正负号的取舍问
题．下面从该方法的几何意义分析(5)式中正负号的取舍．
1)当f(xk)=o时，z。即为所求的根．
2)当f(xk)>O时，根据y=f(x)的如下4种不同情形(见图1)确定(5)式中根号前的符号．
(a)当f’’(xk)
f’’(xk)
f’’(xk)>o，f(xk)
算法1
Step 1：取初始迭代值z。，给出最大迭代次数N和精度￡，并令累计迭代次数k=0．
Step 2：k=k+1．
Step 3：若f’’(xk)=0，则此时f(x)可近似为线性函数，采用牛顿法求之；否则计算△=
(f’(xk))^2—2f’’(xk)f(xk)．
Step 4：判定△的符号，若△<0，则算法停止；否则利用(5)进行计算，得到x k+1．
Step 5：判定是否停止迭代，如果k>N或|x k+1-xk|≤￡，则停止迭代；否则回到Step2．
注：①当k>N时，非线性迭代不收敛，当Iz川一z。I≤￡时，非线性迭代收敛；②当△<0
时，该非线性方程在该区间不存在实根；③该方法可推广到非线性方程组的情形．
2．2局部收敛阶
类似于牛顿法，可将BNT方法视为一种不动点方法，则对应的迭代函数为
φ x =x−(f′′(x))−1(𝑓′(𝑥)∓ 𝑓′ 𝑥 2−2𝑓′′(𝑥)𝑓(𝑥)_))(6)
利用迭代函数(6)，通过计算与推导，可得BNT方法的局部收敛阶．
设f(x)∈𝑐3[a，b]，x为φ x 的不动点，BNT方法的局部收敛阶为3阶．
3 数值实验
为验证BNT方法的有效性，下面进行数值实验．
例:求方程f(x)=𝑥
3
−𝑥−1=0在区间[1，2]上的根．
首先，可构造两种不同的不动点迭代方法，分别为x𝑘+1=(𝑥𝑘+1)1/3,x
𝑘+1=𝑥𝑘
1/3
−1,k=1，
2，3，⋯，并简记为FPl，FP2．将BNT方法与FPl，FP2，FP2的Stenffensen加速、牛顿法
和密勒法求根进行比较，数值实验中初始迭代值取x。=1．5，近似真解为x=1．324 7，结
果如表l所示．由表1可知：
BNT方法的收敛速度最快，且较牛顿法快，从而验证了本文
方法的有效性．
表1 对比实验结果
迭代方法 迭代次数
FP1 7
FP2
不收敛
FP2的Stenffensen加速
6
牛顿法
4
密勒法
5
BNP方法
3