数值计算
探讨求解的几种方法
摘要
很多科学计算问题都遇到非线性方程的求解问题。
设非线性方程为
()0
m f x x n =-=方程的解*x 称为方程的根或函数()f x 的零点。
对于非线性方程的求解一般没有特殊公式，因此研究其数值解法是很有必要的，在此以求一个数的n 次方根为例探讨几种求近似根的常用方法，即二分法、牛顿迭代法、简化牛顿迭代法法以及割线法。
一、算法设计
计算机配置
内存：2G
处理器主频：2.53GHz
MATLAB 版本：R2011b
1.1二分法
设()f x 在区间[,]a b 上连续，()()0f a f b ∙<，则[,]a b 内有方程的根。
取[,]a b 的中点01()2
x a b =+，将区间一分为二。
若0()0f x =，则0x 就是方程的根，否则判别根*x 在0x 的左侧还是右侧。
若0()()0f a f x ∙<，则*0(,)x a x ∈，令110,a a b x ==；
若0()()0f a f x ∙>，则*0(,)x x b ∈，令101,a x b b ==。
不论出现那种情况，11(,)a b 均为新的有根区间，它的长度只有原有根区间长度的一半，达到了压缩有根区间的目的。
对压缩了的有根区间，又可施行同样的步骤，再次压缩有根区间。
如此反复进行下去，即可得一系列有根区间套
11[,][,][,]n n a b a b a b ⊃⊃⊃⊃
由于每一区间都是前一区间的一半，因此区间[,]n n a b 的长度为
1()2n n n
b a b a -=
-若每次二分时所取区间中点都不是根，则上述过程将无限的进行下去。
当n →∞
时，区间必将最终收缩为一点*x ，显然*x 就是所求之根。
若取区间[,]n n a b 的中点01()2x a b =+作为*x 的近似值，则有下述误差估计式*111()()22n n n n x x b a b a +-≤-=-只要n 足够大（即区间二分次数足够多），n x 的误差就可足够小。
值得注意的是，由于在偶重根附近曲线()y f x =为向上凹或向下凹，即()f a 与()f b 的正负号相同，因此不能用二分法求偶重根。
1.2二分法MATLAB 程序设计
1.3牛顿迭代法
设已知方程()0f x =近似根0x ，且在0x 附近()f x 可用一阶泰勒多项式近似，表示为
'000()()()()
f x f x f x x x ≈+-当'0()0f x ≠时，方程()0f x =可用线性方程近似代替，即
'000()()()0
f x f x x x +-=解此线性方程得
00'0()
()
f x x x f x =-取此x 作为原方程的新近似根1x ，重复以上步骤，于是得迭代公式
1'()
()
k k k k f x x x f x +=-(0,1,)
k = 此式称为牛顿迭代公式，其迭代函数为
'()()()
f x x x f x ϕ=-
当*x 为单根时，*()0f x =，'*()0f x ≠，故
*''*'*
'*2()()()0[()]f x f x x f x ϕ==''*''*
'*()()()f x x f x ϕ=''*()x ϕ不一定为0，根据定理3，牛顿迭代法在根*x 的邻近是平方收敛的。
1.4牛顿迭代法MATLAB
程序设计
1.5简化牛顿迭代法在牛顿迭代公式1'()()
k k k k f x x x f x +=-中，用一常数M 代替'()k f x ，得1()
k k k f x x x M
+=-(0,1,)
k = 此式称为简化牛顿迭代公式，只要M 选择得当，该式子总是收敛的，不过其收敛速度降为线性。
其几何意义可描述为用平行线代替牛顿法中的切线。
1.6简化牛顿迭代法MATLAB
程序设计
1.7割线法
用常数M 来代替'()k f x 虽然简单，但没有充分利用()f x 本身的特性，因此收敛较慢，若在牛顿迭代公式中改用差商11
()()k k k k f x f x x x ----代替导数'()k f x ，得迭代公式
111()()()()k k k k k k k f x x x x x f x f x +--=---可以证明，
它的收敛阶为1(1 1.6182
p =+≈，确实比简化牛顿迭代公式收敛快。
连接曲线()y f x =上的两点(,())k k k P x f x 与111(,())k k k P x f x ---，所得弦线与x 轴交点的横坐标即为由此式求出的1k x +。
因此，称之为双点割线法。
为了使程序简单，也将上述迭代公式中的1k x -改为0x ，即
100()()()()
k k k k k f x x x x x f x f x +=---每步迭代时只利用一个新点k x ，这样的迭代格式称为单点割线法，然而它的收敛速度只是线性的。
1.8割线法MATLAB
程序设计
二、数值试验
2.1
二分法求解x =2.1.1运行结果
(1,2)，精度为8；迭代次数为8；最终收敛值*x 为1.7099758；误差为7.812507e -；运行时间0.188549秒；
2.1.2收敛图
2.2牛顿迭代法求解35
x
精度为8；迭代次数为4；最终收敛值*x为1.7099759；误差为4.822407
e-；运行时间0.000453秒；
2.2.2收敛图
2.3简化牛顿迭代法求解x=
精度为8；迭代次数为11；最终收敛值*x为1.7099761；误差为8.212107
e ；运行时间0.004333秒；
2.3.2收敛图
2.4割线法求解
x=
2.4.1运行结果
精度为8；迭代次数为6；最终收敛值*x为1.7099759；误差为8.719509
e-；运行时间0.005842秒；
2.4.2收敛图
2.5计算结果比较
算法结果误差迭代次数函数值时间二分法 1.70997587.812507
e-8-1.4511e-060.188549
牛顿迭代
法1.7099759 4.822407
e-4 1.1928e-120.000453
简化牛顿迭代法1.70997618.212107
e-11 1.6605e-060.004333
弦截法 1.70997598.719509
e-6-7.6488e-080.005842 2.6计算结果分析
1、二分法相对于其他几种算法，收敛时间较长，即二分法是在大范围内收敛的。
2、牛顿迭代法收敛较快，精度高，误差小。
3、简化牛顿法的收敛也较快，迭代次数多，导致误差较大。
4、弦截法的收敛速度快，迭代次数少，误差最小，总体上较好。
三、参考文献
【1】曹德欣，曹璎珞，计算方法，中国矿业大学出版社，2001。
【2】王正盛，MATLAB与科学计算，国防工业出版社，2011。