第二章 非线性方程数值解法
在科学计算中常需要求解非线性方程
()0f x =
即求函数()f x 的零点．非线性方程求解没有通用的解析方法，常采用数值求解算法．数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列0{}k k x +∞=，使它逐步逼近于方程的某个解．本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、Newton 迭代法及其变形，并讨论它们的收敛性、收敛速度等．
§ 二分法
一、实根的隔离
定义 设非线性方程中的()f x 是连续函数．如果有*x 使*()0f x =，则称*x 为方程的根，或称为函数()f x 的零点；如果有*()()()m f x x x g x =-，且()g x 在*x 邻域内连续，*()0g x ≠，m 为正整数，则称*x 为方程的m 重根．当1m =时，称*x 为方程的单根．
非线性方程根的数值求解过程包含以下两步
(1) 用某种方法确定有根区间．称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；
(2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求．
对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数()f x ，也可以从两个端点函数值符号确定出有根区间．
当函数()f x 连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下
设[,]a b 是方程的一个较大有根区间，选择合适的步长()/h b a n =-，k x a kh =+，(0,1,,)k n =L ．由左向右逐个计算()k f x ，如果有1()()0k k f x f x +<，则区间1[,]k k x x +就是方程的一个较小的有根区间．
一般情况下，只要步长h 足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程的根的一个近似．
例 确定出方程32()3430f x x x x =-+-=的一个有根区间．
解 由22()3643(1)10f x x x x '=-+=-+>知()f x 为(,)-∞∞上的单调递增函数，进而()f x 在(,)-∞∞内最多只有一个实根．经计算知(0)0f <，(2)0f >，所以()0f x =在区间[0,2]内有惟一实根．
如果希望将有根区间再缩小，可以取步长0.5h =，在点0.5x =，1x =， 1.5
x =
计算出函数值的符号，最后可知区间[1.5,2]内有一个实根． 二、二分法
二分法是求非线性方程实根近似值的最简单的方法．其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值．
设()f x 在区间[,]a b 上连续，()()0f a f b <，且方程在区间(,)a b 内有惟一实根*x ．记1a a =，1b b =，中点111()/2x a b =+将区间11[,]a b 分为两个小区间11[,]a x 和11[,]x b ，计算函数值1()f x ，根据如下3种情况确定新的有根区间：
(1) 如果1()0f x =，则1x 是所要求的根； (2) 如果11()()0f a f x <，取新的有根区间2211[,][,]a b a x =； (3) 如果11()()0f x f b <，取新的有根区间2211[,][,]a b x b =．
新有根区间22[,]a b 的长度为原有根区间11[,]a b 长度的一半．对有根区间22[,]a b 施以同样的过程，即用中点222()/2x a b =+将区间22[,]a b 再分为两半，选取新的有根区间，并记为33[,]a b ，其长度为22[,]a b 的一半(如图所示)．
图 二分法示意图
重复上述过程，建立如下嵌套的区间序列
1122[,][,][,][,]k k a b a b a b a b =????L L
其中每个区间的长度都是前一个区间长度的一半，因此[,]k k a b 的长度为
1
1()
2k k k b a b a --=
-
由*
[,]k k x a b ∈和()/2k k k x a b =+，得
*11
()()22
k k k k x x b a b a -≤
-=- 当k →∞时，显然，有*k x x →．总结得到如下收敛定理：
定理 设()f x 在隔根区间[,]a b 上连续，且()()0f a f b <，则由二分法产生的序
列0{}k k x +∞=收敛于方程在[,]a b 上的根*
x ，并且有误差估计
*1
()(1,2,)2k k x x b a k -≤
-=L 设预先给定根*x 的绝对误差限为ε，要求*k x x ε-≤，只要1
()2
k b a ε-≤成立，
这样求得对分次数
ln()ln ln 2
b a k ε
--≥
．
取k 为大于(ln()ln )/ln 2b a ε--的最小整数．此时k x 是方程的满足精度要求的根近似值．
注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断()0k f x =几乎不可能满足，取而代之为判断条件0()k f x ε<，其中
0ε为根近似值的函数值允许误差限．
总结以上内容，给出如下算法 算法 (二分法)
输入 端点,a b 、根的绝对误差限ε、根近似值的函数值允许误差限0ε； 输出 近似解c 或失败信息；
Step 1 用公式计算最大迭代次数k ； Step 2 对1,,n k =L 循环执行Step 3～5； Step 3 ()/2c a b =+，计算()f c ；
Step 4 若0()f c ε<，则输出c ，end ；
Step 5 若()()0f c f b <，则a c =，否则b c =．
例 用二分法求32()4100f x x x =+-=在[1,2]上的根*x 的近似值，要求
*31
102
k x x --<
?． 解 由于在区间[1,2]上，(1)5f =-，(2)14f =，2()38(38)0f x x x x x '=+=+>，故()0f x =在[1,2]上有惟一实根*x ．确定循环次数为11k =，利用二分法计算结果见表．
二分法具有如下特点
(1) 优点：计算简单，对函数()f x 的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；
(2) 缺点：只能求单实根和奇数重实根，收敛较慢，与1/2为公比的等比级数相同． 当函数()f x '连续时，方程的实重根可转换为
()
0()
f x f x ='的实单根． 一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供初值．
§ 简单迭代法
简单迭代法是求解非线性方程根的近似值的一类重要数值方法．本节将介绍
简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法． 一、简单迭代法的基本思想
简单迭代法采用逐步逼近的过程建立非线性方程根的近似值．首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止．
在给定的有根区间[,]a b 上，将方程等价变形为
()x x ?=
在[,]a b 上选取0x 作为初始近似值，用如下迭代公式
1()k k x x ?+= (0,1,2,k =L )
建立序列0{}k k x +∞=．如果有*lim k k x x →∞
=，并且迭代函数()x ?在*x 的邻域内连续，对式两边取极限，得
**()x x ?=
因而*x 是的根，从而也是的根．称()x ?为迭代函数，所得序列0{}k k x +∞=为迭代序列．将这种求方程根近似值的方法称为简单迭代法，简称迭代法．
例 试用方程3()10f x x x =--=的不同形式的变形建立迭代公式，并试求其在1.5附近根的近似值．
解 利用方程的变形建立如下4种迭代公式
(1) 1k x +=，
(2) 3
11k k x x +=-
(3) 1k x += (4) 3112
k k k x x x ++-=
取初值0 1.5x =，迭代计算，结果见表．
例表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛．那么迭代函数()x ?满足什么条件时才能保证迭代序列收敛 迭代序列0{}k k x +∞=的误差如何估计 怎样才能建立收敛速度快的迭代公式
定理 若函数()x ?在区间[,]a b 上具有一阶连续导数，且满足条件 ① 对任意[,]x a b ∈，有()[,]x a b ?∈；
② 存在常数L ：01L <<，使得对任意[,]x a b ∈有()x L ?'≤成立． 则
(1) 方程()x x ?=在[,]a b 上有惟一实根*x
(2) 对任意0[,]x a b ∈，迭代公式收敛，且*lim k k x x →∞
= (3) 迭代公式有误差估计式
*11k k k L
x x x x L --≤
-- *
101k k L x x x x L
-≤--
(4) *
*1*lim ()k k k
x x x x x ?+→∞-'=- 证明 (1)构造函数()()g x x x ?=-，由条件①知()()0g a a a ?=-≤，
()()0g b b b ?=-≥，因此()0g x =在[,]a b 上至少存在一个实根，又由条件②知当[,]x a b ∈时，()1()10g x x L ?''=-≥->，所以()0g x =在[,]a b 内存在惟一实根，即()x x ?=在[,]a b 内存在惟一实根，记为*x ．
(2) 由0[,]x a b ∈及条件①知，[,]k x a b ∈(1,2,)k =L ，并且有1()k k x x ?+=，**()x x ?=，二者作差，并由微分中值定理得
***1()()()()k k k k x x x x x x ???ξ+'-=-=- (1,2,)k =L 其中，k ξ介于k x 与*x 之间．结合条件②，得
**
1k k x x L x x +-≤- (1,2,)k =L
反复递推，有
**2*1*
1100k k k k x x L x x L x x L x x ++-≤-≤-≤-≤≤-L ， (1,2,)k =L
因01L <<，故*lim k k x x →∞
=． (3) 由式得
***
1111*
1k k k k k k k k k k x x x x x x x x x x x x L x x
+++++-=-+-≤-+-≤-+-
从而
*11
1k k k
x x x x L
+-≤
--
又由于
111()()()()
k k k k k k k x x x x x x ???η+--'-=-=-
1
k k L x x -≤- (1,2,)k =L
其中k η介于k x 和1k x -之间．综合式及式得误差估计
*1
1k k k L
x x x x L
--≤
--
由式反复递推，得
111210
k k k k k x x L x x L x x -----≤-≤≤-L
并代入式得误差估计
*
11011k
k k k L L x x x x x x L L
--≤-≤--- (1,2,)k =L
(4) 由式得
*
1*
()k k k x x x x ?ξ+-'=- 两端取极限，并注意到()x ?'的连续性和*lim k k x ξ→∞
=(因为k ξ介于*x 与k x 之间)，得 **1*
lim ()k k k
x x x x x ?+→∞-'=-． 误差估计称为后验误差估计，也称为误差渐进估计，误差估计称为先验误差
估计．定理条件成立时，对任意0[,]x a b ∈，迭代序列均收敛，故称定理为全局收敛性定理．下面讨论*x 邻近的收敛性，即局部收敛性．
定理 设存在方程()x x ?=根*x 的闭邻域***(,)[,](0)U x x x δδδδ=-+>以及小于1的正数L ，使得()x ?'连续且()1x L ?'≤<．则对任意*0(,)x U x δ∈，迭代1()k k x x ?+=收敛．
证明 由()x ?'在*(,)U x δ内连续，且有()1x L ?'≤<，则对任意*(,)x U x δ∈，有
****()()()()x x x x x x L ????ηδδ'-=-=-≤<
由定理知迭代过程1()k k x x ?+=对任意初值*0(,)x U x δ∈均收敛． 二、迭代法的收敛阶
为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念．
定义 设迭代序列0{}k k x +∞=收敛到*
x ，记*k k e x x =-，如果存在常数0c >和实数1p ≥，使得
1lim
k p
k k
e c e +→∞
=
则称序列0{}k k x +∞=是p 阶收敛的．当1p =时，称0{}k k x +∞
=为线性收敛的，此时要求
01c <<；1p >为超线性收敛．p 越大，序列0{}k k x +∞=收敛到*
x 越快．c 称为渐进常数，c 越小，收敛越快．所以迭代法的收敛阶是对迭代法收敛速度的一种度量． 显然，由定理(4)知，当*()0x ?'≠时简单迭代法线性收敛，渐进常数*()c x ?'=．
算法 (简单迭代法)
输入 初始值0x 、容许误差ε； 输出 近似解1x 或失败信息；
Step 1 对1,,n m =L 循环执行Step 2～3； Step 2 10()x x ?=；
Step 3 若10x x ε-<，则输出1x ，end ；
否则01x x =，转向Step2．
例 求方程()2lg 70f x x x =--=的最大实根的近似值，要求绝对误差不超过
31
102
-?．
解 (1)确定有根区间．方程等价形式为
27lg x x -=
作函数27y x =-和lg y x =的图形，如图所示，知方程的最大实根在区间[3,4]内．
(2)建立迭代公式，判别收敛性．将方程等价变形为
1
(lg 7)2
x x =
+ 迭代函数1
()(lg 7)2
x x ?=+，迭代公式11(lg 7)2
k k x x +=+．
由11
()02ln10x x
?'=
?>，[3,4]x ∈，知()x ?在区间[3,4]内仅有一根．又(3) 3.74?≈，(4) 3.80?≈，所以，当[3,4]x ∈时，()[3,4]x ?∈．
图 函数27y x =-和lg y x =的图形
因为 3.5
4
max ()(3)0.07x L x ??≤≤''==≈，所以对于一切[3,4]x ∈有 ()(3)0.071x ??''≤≈<
由定理知，迭代法收敛．
(3) 迭代计算．取0 4.0x =，有
1=3.801030x ，2=3.789951x ，3=3.789317x ，4=3.789280x 因为3431
10 2
x x --≤?，所以方程的最大根*4 3.789280x x ≈=． 三、迭代法的加速
对于收敛的迭代序列，理论上迭代次数足够多时，就可以使计算结果满足任意给定的精度要求．但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因此研究迭代格式的加速方法是非常必要的． 1. 线性收敛序列的Aitken 加速法
设0{}k k x +∞=是一个线性收敛的序列，极限为*
x ．即有小于1的正数c 使得
*1*
lim
k k k x x c x x
+→∞
-=-
由于它线性收敛，误差减少的速度较慢，值得采用加速技术．下面介绍Aitken 加速法．
对充分大的k ，有
*1*,k k x x c x x +-≈- *
2*
1k k x x c x x ++-≈- 由上面两式得
**
12**
1k k k k x x x x x x x x +++--≈
--
解得
2
2*
21
12121()22k k k k k k k k k k k k x x x x x x x x x x x x x +++++++--≈=-
-+-+
利用上式右端的值可定义另一序列0{}k k y +∞=，即得Aitken 加速公式
2
121()2k k k k k k k
x x y x x x x +++-=-
-+
它仍然收敛到*x ，但收敛速度更快．证明请参考文献[19]．
2. Steffensen 迭代法
Aitken 加速方案是对任意线性收敛序列0{}k k x +∞=构建的，并不限定0{}k k x +∞
=如何获得．将Aitken 加速方法用于简单迭代法产生迭代序列时，得到着名的Steffensen 迭代法，具体迭代公式如下
21()()(0,1,2,)
()
2k k k k
k s x t s k s x x x t s x ??+=??
==??-?=-?-+?
L
或者直接写成
2
1
(())(())2()k k k k k k k
x x x x x x x ????+-=-
-+ (0,1,2,)k =L
可以证明Steffensen 迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限，但Steffensen 迭代法收敛速度更快，可以达到二阶收敛．证明请参考文献[19]．
例 对例 用Steffensen 迭代法求方程根的近似值，要求811102
k k x x -+-
2
(10/(4))x x =+，建立迭代公式
1
21
104k k x x +??= ?+?
? 易验证该迭代公式在区间[1,2]上满足定理的条件，产生的迭代序列收敛．
(2) Steffensen 迭代法 加速公式为
1
2122110410(0,1,2,)
4()2k k k k k s x t k s s x x x t s x +????= ?+????????==
??+???-?=-?-+?
L
(1) 取初值0 1.5x =，简单迭代法和Steffensen 迭代法计算结果见表． 注意：Steffensen 迭代法每一迭代步的计算量大约是原简单迭代法计算量的两
倍．
表 简单迭代法和Steffensen 迭代法计算结果
§ Newton 迭代法
Newton 迭代法是求解非线性方程根的近似值的一种重要数值方法．其基本思
想是将非线性函数()f x 逐步线性化，从而将非线性方程近似地转化为一系列线性方程来求解．下面讨论其格式的构造、收敛性、收敛速度以及有关变形． 一、Newton 迭代法的构造
设k x 是方程的某根的一个近似值，将函数()f x 在点k x 处作Taylor 展开
2()
()()()()()2!
k k k k f f x f x f x x x x x ξ'''=+-+
- 取前两项近似代替()f x ，即用线性方程
()()()0k k k f x f x x x '+-=
近似非线性方程．设()0k f x '≠，则用线性方程的根作为非线性方程根的新近似值，即定义
1()
()
k k k k f x x x f x +=-
' 上式即是着名的Newton 迭代公式．它也是一种简单迭代法，其中迭代函数
()
()()
f x x x f x ?=-
' Newton 迭代法具有明显的几何意义(如图所示)．方程()0f x =的根*x 即为曲线()y f x =与x 轴的交点的横坐标．设k x 是*x 的某个近似值，过曲线()y f x =上相应的点(,())k k x f x 作切线，其方程为
()()()k k k x f x y f x x '+-=
它与x 轴的交点横坐标就是1k x +．只要初值0x 取得充分靠近根*x ，序列0{}k k x ∞=就会很快收敛到*x ．所以Newton 迭代法也称为切线法．
二、收敛性
定理 设*x 是方程的单根，在*x 的邻域上()f x ''连续且*()0f x '≠．则存在0δ>，当***0(,)[,]x U x x x δδδ∈=-+时，Newton 法产生的序列0{}k k x ∞=至少二阶收敛． 证明 (1) Newton 法迭代函数的导数为
2
()()
()[()]f x f x x f x ?'''=
'
显然，()x ?'在*x 邻域上连续．又*()0x ?'=，一定存在*x 的某个δ闭邻域*(,)U x δ，当*(,)x U x δ∈时，有
()1x L ?'≤< 从而Newton 法产生的序列0{}k k x ∞=收敛．
(2)将()f x 在k x 处作一阶Taylor 展开
***21
0()()()()()()2!
k k k k k f x f x f x x x f x x ξ'''==+-+
- 其中k ξ介于*x 与k x 之间．又由Newton 迭代公式有 10()()()k k k k f x f x x x +'=+-
式与式相减
**
21()()2()
k k k k f x x x x f x ξ+''-=-
-' 从而
**1*2*()lim 0()2()k k k
x x f x x x f x +→∞''-=≠'- 由迭代法收敛阶的定义知，Newton 迭代法至少具有二阶收敛速度．
上述定理给出了Newton 法局部收敛性，它对初值要求较高，初值必须充分靠近方程根时才可能收敛，因此在实际应用Newton 法时，常常需要试着寻找合适的初值．下面的定理则给出Newton 法在有根区间上全局收敛的一个充分条件．
定理 设*x 是方程在区间[,]a b 上的根且()f x ''在[,]a b 上存在，如果
(1) 对于任意[,]x a b ∈有，()0f x '≠()0f x ''≠； (2) 选取初值0[,]x a b ∈，使00()()0f x f x ''>．
则Newton 法产生的迭代序列0{}k k x ∞=单调收敛于*
x ，并具有二阶收敛速度．
(a)
(b)
(c) (d)
图 定理的几何解释
证明 满足定理条件(1)共有4种情形，如图所示．下面仅以图(a
)情况进行
证明，此时满足
对任意[,]x a b ∈有，()0f x '>，()0f x ''>，初值*0x x >．
首先用数学归纳法证明0{}k k x ∞=有下界*
x ． 当0k =时，*0x x >成立．
假设k n =时，不等式*n x x >成立． 将*()f x 在n x 处作一阶Taylor 展开，得
***
2*()()()()()()0,(,)2!
n n n n n n n f f x f x f x x x x x x x ξξ'''=+-+
-=∈ 于是
**
2()()()()2()
n n n n n n f x f x x x x f x f x ξ''=-
--'' 又由Newton 迭代公式，有
**
21()()2()
n n n n f x x x x f x ξ+''=-
-' 式右端的第二项大于零，因此*1n x x +>．由数学归纳法知*k x x >，(0,1,2,)k =L ． 其次证明0{}k k x ∞=单调递减．
由()0f x '>，*k x x >，*()0f x =知，()0k f x >，()0k f x '>，于是Newton 迭代公式的第二项大于零，从而
1k k x x +>
故迭代序列0{}k k x ∞=单调减少．
序列0{}k k x ∞=单调减少有下界*
x ，它必有极限，记为?x ，它满足*0?x x x ≤<，进而
有?[,]x
a b ∈．对1()
()
k k k k f x x x f x +=-'两端取极限，并利用()f x ，()f x '的连续性，得?()f x
=0．结合函数()f x 在[,]a b 上的单调性知*?x x =． 因此，Newton 法产生的迭代序列0{}k k x ∞=单调收敛于*x ，利用式及式知该Newton 迭代序列二阶收敛．
算法 (Newton 迭代法)
输入 初始近似值0x 、 容许误差ε； 输出 近似解1x 或失败信息；
Step 1 对1,,n m =L 循环执行Step 2～3； Step 2 1000()/()x x f x f x '=-；
Step 3 若10x x ε-<，则输出1x ，end ；
否则01x x =，转向step2．
例 利用非线性方程230x -=的Newton
迭代公式计算的近似值，使得
811
102
n n x x ---≤
?，并证明对任意0(0,)x ∈+∞，该迭代法均收敛． 解 (1) 建立计算公式
21
3213(0,1,2,)(2)
k k k k
k k
k x x x x x x +-=-
=+=L
其中00x >．
(2) 判断收敛性
在区间(0,)+∞内，()20f x x '=>，()20f x ''=>
，当选取初值0)x ∈+∞时，存在足够大的M
，使得0]x M ∈．由定理知，该迭代公式产生的迭代序列0{}k k x ∞=都
收敛于
当选取初值0x ∈时，
1000
13
()2x x x x =
+>>
这样，从1x 起，以后的(2)k x k ≥
． 故该迭代公式对任何初值00x >都收敛． (3) 取初值02x =，迭代计算，结果见表．
从表可见，迭代4 1.73205080756888L ． 三、Newton 迭代法的变形
Newton 迭代格式构造容易，迭代收敛速度快，但对初值的选取比较敏感，要求初值充分接近真解，另外对重根收敛速度较慢（仅有线性收敛速度），而且当函数复杂时，导数计算工作量大．下面从不同的角度对Newton 法进行改进． 1 Newton 下山算法
Newton 迭代法的收敛性依赖于初值0x 的选取，如果0x 偏离*x 较远，则Newton 迭代法有可能发散，从而在实际应用中选出较好的初值有一定难度，而Newton 下山法则是一种降低对初值要求的修正Newton 迭代法．
方程的根*x 也是()f x 的最小值点，若把()f x 看成()f x 在x 处的高度，则*x 是山谷的最低点．若序列0{}k k x ∞=满足单调性条件
1()()k k f x f x +<
则称0{}k k x ∞=为称为()f x 的下山序列．
在Newton 迭代法中引入下山因子(0,1]λ∈，将Newton 迭代公式修正为
1()(0,1,2,)()
k k k k f x x x k f x λ
+=-='L
适当选取下山因子λ，使得单调性条件成立，即称为Newton 下山法．
对下山因子的选取是逐步探索进行的．一般地，从1λ=开始反复将因子λ的值减半进行试算，一旦单调性条件成立，则称“下山成功”；反之，如果在上述过程中找不到使条件成立的下山因子λ，则称“下山失败”，这时可对k x 进行扰动或另选初值0x ，重新计算． 2 针对重根情形的加速算法
假设*x 是方程的(2)m ≥重根，并且存在函数()g x ，使得有 **()()(),()0m f x x x g x g x =-≠
式中()g x 在*x 的某邻域内可导，则Newton 迭代函数
***1**()()()()()
()()()()()()()()()
m m m f x x x g x x x g x x x x x f x m x x g x x x g x mg x x x g x ?---=-=-=-'''-+-+-，
其导数在*x 处的值
*****
**
***
*()()
()()()()()
()lim lim
()1
lim 11()()()
x x x x x x x x g x x x x x mg x x x g x x x x x x g x m mg x x x g x ???→→→---'-+-'==--=-=-'+-
所以*0()1x ?'<<，由定理知Newton 迭代法此时只有线性收敛速度．为了加
速收敛，可以采用如下两种方法
方法一 令()
()()
f x x f x μ='，则*x 是方程()0x μ=的单根，将Newton 迭代函数修改为
2()()()
()()[()]()()
x f x f x x x x x f x f x f x μψμ'=-
=-
''''- 因此有重根加速迭代公式
12()()
(0,1,2,)[()]()()
k k k k k k k f x f x x x k f x f x f x +'=-
='''-L
它至少二阶收敛．
方法二 将Newton 迭代函数改为
()
()()
f x x x m
f x ?=-' 这时*()0x ?'=，由此得到加速迭代公式
1()(0,1,2,)()
k k k k f x x x m
k f x +=-='L
3 割线法
Newton 法每步需要计算导数值()k f x '．如果函数()f x 比较复杂时，导数的计算量比较大，此时使用Newton 法不方便．
为了避免计算导数，可以改用平均变化率11
()()k k k k f x f x x x ----替换Newton 迭代公
式中的导数()k f x '，即使用如下公式
111()
()()()
k k k k k k k f x x x x x f x f x +--=---
上式即是割线法的迭代公式．
割线法也具有明显的几何意义，如图所示，依次用割线方程
11
()()
()()k k k k k k f x f x y f x x x x x ---=+
--
的零点逐步近似曲线方程()0f x =的零点．
割线法的收敛速度比Newton 法稍慢一点，可以证明其收敛阶约为，证明请参考文献[4]．此外在每一步计算时需要前两步的信息1,k k x x -，即这种迭代法也是两步法．两步法在计算前需要提供两个初始值0x 与1x ．
图 割线法的几何意义
例 已知方程42()440f x x x =-+=
有一个二重根*x =，分别用Newton 法和重根Newton 法和求其近似值，要求611102
n n x x ---≤?
解
32
()48,()128f x x x f x x '''=-=-，2()2()()4f x x x f x x
μ-=
='，2m =． 由Newton 法得
22
1
232(0,1,2,)44k k k k k k
x x x x k x x +-+=-=
=L
由Newton 法 得
21
22
(2)4(0,1,2,)22
k k k
k k k k x x x x x k x x +-=-==++L
由Newton 法 得
221
22(0,1,2,)22k k k k k k
x x x x k x x +-+=-=
=L
利用上述三种迭代格式，取初值0 1.4x =，分别计算，结果见表．
表
知识结构图
习 题
1 用二分法求方程2sin 0x e x --=在区间[0,1]内根的近似值，精确到3位有效数
字．
2 方程340x x +-=在区间[1,2]内有一根，试用二分法求根的近似值，使其具有5
位有效数字，至少应二分多少次．
3 已知方程3210x x --=在0 1.5x =附近有根，试判断下列迭代格式的收敛性，并
用收敛的迭代公式求方程根的近似值，比较迭代次数，要求311
102
n n x x ---≤? (1) 121
1n n
x x +=+
；
(2) 1n x +=；
(3) 1n x +．
4 设有方程
(1) cos 0x x -=； (2) 230x x e -=
确定区间[,]a b 及迭代函数()x ?，使1()k k x x ?+=对任意初值0[,]x a b ∈均收敛，并
求各方程根的近似值，要求411102
n n x x ---≤?．
5 用迭代法求50.20x x --=的正根，要求准确到小数点后5位．
6 用Steffensen 迭代法求方程31x x =-在区间[1,1.5]内的根，要求准确到小数点
后4位．
7 用Newton 法和割线法分别求方程3310x x --=在02x =附近根的近似值，并比
较迭代次数(根的准确值为* 1.87938524x =L ，要求准确到小数点后4位)． 8 Halley 法是加速Newton 法收敛的一个途径，Halley 法在()f x 的单根情况下可
达到三阶收敛．Halley 迭代函数是
1
2()()()()1()2(())f x f x f x g x x f x f x -''??
=-- ?
''??
基本概念 （单根、重根、收敛阶）
其中括号中的项是对Newton 迭代公式的改进．
(1) 设函数2()f x x a =-，试给出Halley 迭代公式，取初值02x =求5的近似
值，要
求准确到小数点后10位．
(2) 设函数3()32f x x x =-+，试给出Halley 迭代公式，取初值0 2.4x =计算其
根的近
似值．要求准确到小数点后10位．
9 试建立计算
x Newton 迭代公式，并取初值01x =，要
求611
102
n n x x ---≤?．
10 （数值试验）用二分法和Newton 法求下列方程的惟一正根的近似值
)0.50x x x =
11 （数值试验）设投射体的运动方程为
/15
/15
()9600(1)480()2400(1)t t y g t e
t x h t e --?==--??==-??
１）求当撞击地面时的时间，精确到小数点后10位． ２）求水平飞行行程，精确到小数点后10位．
12 （数值试验）试用Newton 法分别求解方程(1)0m x -=，(3,6,12m =)，观察迭代
序列的收敛情形，分析所发生的现象．能否改造Newton 法使得它收敛更快．
目录 第一章非线性方程求根 (3) 1.1迭代法 (3) 1.2牛顿法 (4) 1.3弦截法 (5) 1.4二分法 (6) 第二章插值 (7) 2.1线性插值 (7) 2.2二次插值 (8) 2.3拉格朗日插值 (9) 2.4分段线性插值 (10) 2.5分段二次插值 (11) 第三章数值积分 (13) 3.1复化矩形积分法 (13) 3.2复化梯形积分法 (14) 3.3辛普森积分法 (15) 3.4变步长梯形积分法 (16) 第四章线性方程组数值法 (17) 4.1约当消去法 (17) 4.2高斯消去法 (18) 4.3三角分解法 (20)
4.4雅可比迭代法 (21) 4.5高斯—赛德尔迭代法 (23) 第五章常积分方程数值法 (25) 5.1显示欧拉公式法 (25) 5.2欧拉公式预测校正法 (26) 5.3改进欧拉公式法 (27) 5.4四阶龙格—库塔法 (28)
数值计算方法 第一章非线性方程求根 1.1迭代法 程序代码： Private Sub Command1_Click() x0 = Val(InputBox("请输入初始值x0")) ep = Val(InputBox(请输入误差限ep)) f = 0 While f = 0 X1 = (Exp(2 * x0) - x0) / 5 If Abs(X1 - x0) < ep Then Print X1 f = 1 Else x0 = X1 End If Wend End Sub 例：求f(x)=e2x-6x=0在x=0.5附近的根（ep=10-10）
1.2牛顿法 程序代码： Private Sub Command1_Click() b = Val(InputBox("请输入被开方数x0")) ep = Val(InputBox(请输入误差限ep)) f = 0 While f = 0 X1 = x0 - (x0 ^ 2 - b) / (2 * b) If Abs(X1 - x0) < ep Then Print X1 f = 1 Else x0 = X1 End If Wend End Sub 例：求56的值。（ep=10-10）
第二章复习与思考题 1.什么是拉格朗日插值基函数？它们是如何构造的？有何重要性质？ 答：若n 次多项式()),,1,0(n j x l j =在1+n 个节点n x x x <<< 10上满足条件 (),,,1,0,, ,0, ,1n k j j k j k x l k j =?? ?≠== 则称这1+n 个n 次多项式()()()x l x l x l n ,,,10 为节点n x x x ,,,10 上的n 次拉格朗日插值基函数. 以()x l k 为例，由()x l k 所满足的条件以及()x l k 为n 次多项式，可设 ()()()()()n k k k x x x x x x x x A x l ----=+- 110， 其中A 为常数，利用()1=k k x l 得 ()()()()n k k k k k k x x x x x x x x A ----=+- 1101， 故 ()()()() n k k k k k k x x x x x x x x A ----= +- 1101 ， 即 ()()()()()()()()∏ ≠=+-+---=--------=n k j j j k j n k k k k k k n k k k x x x x x x x x x x x x x x x x x x x x x l 0110110)( . 对于()),,1,0(n i x l i =，有 ()n k x x l x n i k i k i ,,1,00 ==∑=，特别当0=k 时，有 ()∑==n i i x l 0 1. 2.什么是牛顿基函数？它与单项式基{ }n x x ,,,1 有何不同？ 答：称()()()(){ }10100,,,,1------n x x x x x x x x x x 为节点n x x x ,,,10 上的牛顿基函数，利用牛顿基函数，节点n x x x ,,,10 上的n 次牛顿插值多项式()x P n 可以表示为 ()()()()10010---++-+=n n n x x x x a x x a a x P 其中[]n k x x x f a k k ,,1,0,,,,10 ==.与拉格朗日插值多项式不同，牛顿插值基函数在增加节点时可以通过递推逐步得到高次的插值多项式，例如 ()()()()k k k k x x x x a x P x P --+=++ 011,
一 选择题(55分=25分) (A)1. 3.142和3.141分别作为π的近似数具有（）和（）为有效数字(有效数字) A. 4和3 B. 3和2 C. 3和4 D. 4和4 解,时,, m-n= -3,所以n=4,即有4位有效数字。当时,, ，m-n= -2,所以n=3,即有3位有效数字。 (A)2. 为了减少误差，在计算表达式时，应该改为计算，是属于（）来避免误差。（避免误差危害原则） A.避免两相近数相减； B.化简步骤，减少运算次数； C.避免绝对值很小的数做除数； D.防止大数吃小数 解：由于和相近，两数相减会使误差大，因此化加法为减法，用的方法是避免误差危害原则。 (B)3.下列算式中哪一个没有违背避免误差危害原则（避免误差危害原则） A.计算 B.计算 C.计算 D.计算 解:A会有大数吃掉小数的情况C中两个相近的数相减，D中两个相近的数相减也会增大误差 (D)4.若误差限为,那么近似数0.003400有()位有效数字。(有效数字) A. 5 B. 4 C. 7 D. 3 解：即m-n= -5,，m= -2，所以n=3，即有3位有效数字 (A)5.设的近似数为，如果具有3位有效数字，则的相对误差限为()（有效数字与相对误差的关系） A． B. C. D. 解：因为所以,因为有3位有效数字，所以n=3,由相对误差和有效数字的关系可得a的相对误差限为 二 填空题：(75分=35分)
1.设则有2位有效数字，若则a有3位有效数字。(有效数字) 解:,时,，，m-n= -4,所以n=2,即有2位有效数字。当时, ，m-n= -5,所以n=3,即有3位有效数字。 2.设 =2.3149541...，取5位有效数字，则所得的近似值x=2.3150(有效数字)解：一般四舍五入后得到的近似数，从第一位非零数开始直到最末位，有几位就称该近似数有几位有效数字，所以要取5位有效数字有效数字的话，第6位是5，所以要进位，得到近似数为2.3150. 3.设数据的绝对误差分别为0.0005和0.0002，那么的绝对误差约为 0.0007 。（误差的四则运算） 解：因为，， 4.算法的计算代价是由 时间复杂度 和 空间复杂度 来衡量的。(算法的复杂度) 5.设的相对误差为2%，则的相对误差为 2n% 。（函数的相对误差） 解：， 6.设>0，的相对误差为δ，则的绝对误差为 δ 。（函数的绝对误差） 解：，， 7.设，则=2时的条件数为 3/2 。(条件数) 解:， 三 计算题(220分=40分) 1.要使的近似值的相对误差限小于0.1%，要取几位有效数字？（有效数字和相对误差的关系） 解：设取n位有效数字,由定理由于知=4所以要使相对误差限小于0.1%,则，只要取n-1=3即n=4。所以的近似值取4位有效数字,其相对误差限小于0.1%。 2.已测得某场地长的值为，宽d的值为，已知试求面积的绝对误差限和
第一章绪论 1．设0x >,x 的相对误差为δ，求ln x 的误差。 解：近似值* x 的相对误差为* **** r e x x e x x δ-= == 而ln x 的误差为()1ln *ln *ln ** e x x x e x =-≈ 进而有(ln *)x εδ≈ 2．设x 的相对误差为2%，求n x 的相对误差。 解：设()n f x x =，则函数的条件数为'() | |() p xf x C f x = 又1 '()n f x nx -= , 1 ||n p x nx C n n -?∴== 又((*))(*)r p r x n C x εε≈? 且(*)r e x 为2 ((*))0.02n r x n ε∴≈ 3．下列各数都是经过四舍五入得到的近似数，即误差限不超过最后一位的半个单位，试指 出它们是几位有效数字：*1 1.1021x =,*20.031x =, *3385.6x =, * 456.430x =,*57 1.0.x =? 解：*1 1.1021x =是五位有效数字； *20.031x =是二位有效数字； *3385.6x =是四位有效数字； *456.430x =是五位有效数字； *57 1.0.x =?是二位有效数字。 4．利用公式(2.3)求下列各近似值的误差限：(1) * * * 124x x x ++,(2) ***123x x x ,(3) **24/x x . 其中****1234 ,,,x x x x 均为第3题所给的数。 解：
*4 1* 3 2* 13* 3 4* 1 51()1021()1021()1021()1021()102 x x x x x εεεεε-----=?=?=?=?=? *** 124***1244333 (1)()()()() 1111010102221.0510x x x x x x εεεε----++=++=?+?+?=? *** 123*********123231132143 (2)() ()()() 111 1.10210.031100.031385.610 1.1021385.610222 0.215 x x x x x x x x x x x x εεεε---=++=???+???+???≈ ** 24**** 24422 *4 33 5 (3)(/) ()() 11 0.0311056.430102256.43056.430 10x x x x x x x εεε---+≈ ??+??= ?= 5计算球体积要使相对误差限为1，问度量半径R 时允许的相对误差限是多少？ 解：球体体积为34 3 V R π= 则何种函数的条件数为 2 3'4343 p R V R R C V R ππ=== (*)(*)3(*)r p r r V C R R εεε∴≈= 又(*)1r V ε=
数值计算方法思考题 第一章 预篇 1．什么是数值分析？它与数学科学和计算机的关系如何？ 2．何谓算法？如何判断数值算法的优劣？ 3．列出科学计算中误差的三个来源，并说出截断误差与舍入误差的区别。 4．什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？ 5．什么是算法的稳定性？如何判断算法稳定？为什么不稳定算法不能使用？ 6．判断如下命题是否正确： （1）一个问题的病态性如何，与求解它的算法有关系。 （2）无论问题是否病态，好的算法都会得到好的近似解。 （3）解对数据的微小变化高度敏感是病态的。 （4）高精度运算可以改善问题的病态性。 （5）用一个稳定的算法计算良态问题一定会得到好的近似值。 （6）用一个收敛的迭代法计算良态问题一定会得到好的近似值。 （7）两个相近数相减必然会使有效数字损失。 （8）计算机上将1000个数量级不同的数相加，不管次序如何结果都是一样的。 7．考虑二次代数方程的求解问题 ax 2 + bx + c = 0. 下面的公式是熟知的 a ac b b x 242-±-=. 与之等价地有 ac b b c x 422--= . 对于 a = 1, b = -100 000 000 , c = 1 应当如何选择算法？ 8．指数函数有著名的级数展开 ++++=!3!213 2x x x e x 如果对x < 0用上述的级数近似计算指数函数的值，这样的算法结果是否会好？为什么？ 9．考虑数列x i , i = 1,…, n , 它的统计平均值定义为 ∑==n i i x x x 1 1 它的标准差
1 12)(11??????--=∑-n i i x x n σ 数学上它等价于 1 12211???????????? ??--=∑=n i i x n x n σ 作为标准差的两种算法，你如何评价它们的得与失？ 第二章 非线性方程求根 1．判断如下命题是否正确： (a) 非线性方程的解通常不是唯一的； (b) Newton 法的收敛阶高于割线法； (c) 任何方法的收敛阶都不可能高于Newton 法； (d) Newton 法总是比割线法更节省计算时间； (e) 如果函数的导数难于计算，则应当考虑选择割线法； (f) Newton 法是有可能不收敛； (g) 考虑简单迭代法x k +1 = g (x k )，其中x * = g (x *)。如果| g '(x *) | <1，则对任意的初 始值，上述迭代都收敛。 2．什么叫做一个迭代法是二阶收敛的？Newton 法收敛时，它的收敛阶是否总是二阶 的？ 3．求解单变量非线性方程的单根，下面的3种方法，它们的收敛阶由高到低次序如何？ (a) 二分法 (b) Newton 方法 (c) 割线方法 4．求解单变量非线性方程的解，Newton 法和割线方法，它们每步迭代分别需要计算几 次函数值和导数值？ 5．求解某个单变量非线性方程，如果计算函数值和计算导数值的代价相当，Newton 法和割线方法它的优劣应如何评价？ 第三章 解线性方程组的直接法 1．用高斯消去法为什么要选主元？哪些方程组可以不选主元？ 2．高斯消去法与LU 分解有什么关系？用它们解线性方程组Ax = b 有何不同？A 要满足什么条件？ 3．乔列斯基分解与LU 分解相比，有什么优点？ 4．哪种线性方程组可用平方根法求解？为什么说平方根法计算稳定？ 5．什么样的线性方程组可用追赶法求解并能保证计算稳定？ 6．何谓向量范数？给出三种常用的向量范数。 7．何谓矩阵范数？何谓矩阵的算子范数？给出矩阵A = (a i j )的三种范数|| A ||1，|| A ||2，|| A ||∞，|| A ||1与|| A ||2哪个更容易计算？为什么？ 8．什么是矩阵的条件数？如何判断线性方程组是病态的？ 9．满足下面哪个条件可判定矩阵接近奇异？ （1）矩阵行列式的值很小。 （2）矩阵的范数小。
第二章 非线性方程数值解法 在科学计算中常需要求解非线性方程 ()0f x = (2.1) 即求函数()f x 的零点．非线性方程求解没有通用的解析方法，常采用数值求解算法．数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列0{}k k x +∞=，使它逐步逼近于方程(2.1)的某个解．本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、Newton 迭代法及其变形，并讨论它们的收敛性、收敛速度等． §2.1 二分法 一、实根的隔离 定义 2.1 设非线性方程(2.1)中的()f x 是连续函数．如果有*x 使*()0f x =，则称*x 为方程(2.1)的根，或称为函数()f x 的零点；如果有*()()()m f x x x g x =-，且()g x 在*x 邻域内连续，*()0g x ≠，m 为正整数，则称*x 为方程(2.1)的m 重根．当1m =时，称*x 为方程的单根． 非线性方程根的数值求解过程包含以下两步 (1) 用某种方法确定有根区间．称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值； (2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求． 对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数()f x ，也可以从两个端点函数值符号确定出有根区间． 当函数()f x 连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下 设[,]a b 是方程(2.1)的一个较大有根区间，选择合适的步长()/h b a n =-，k x a kh =+，(0,1,,)k n =L ．由左向右逐个计算()k f x ，如果有1()()0k k f x f x +<，则区间1[,]k k x x +就是方程的一个较小的有根区间． 一般情况下，只要步长h 足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可
第八章 矩阵特征值问题计算 3．用幂法计算下列矩阵的主特征值及对应的特征向量 12732343()341;()463213331a A b A --???? ????=-=-???? ????--???? 当特征值有3位小数稳定代终止。 解：套用幂法公式 010,,,1,2,.... max()k k k k k v u v Au u k v -≠== = 取0(1,1,1)0T u =≠,将A 1代入上式，计算结果见下表 则1A 的主特征值19.605572λ≈，特征向量1(10.6050.394369)T x ≈- 将2A 代入幂法公式，取0(1,1,1)T u =，计算结果见下表 则2A 主住特征值18.869699λ≈，特征向量1(0.604228,1,0.160881)T x ≈- 4．用反幂法求矩阵 621231111A ?? ??=?? ???? 的最接近于6的特征向量。 解：本题按带原点平移的反幂法计算。平移向量p=6,则将
021231115B A pI ?? ??=-=-?? ??-?? 进行三分解：PB=LU ，其中 1 002310101511 001,10,02 221004 2701005 5P L U ? ??? ????-??? ??? ??????===-???????????? ?? ?? ??? ??? 然后1(1,1,1)T Uv =，解得 1 111,max()v v u v = 1,,,2,3,.... max()k k k k k k k v Ly PU Uv y U k v -=== = 计算结果如下：
.证明： (1).如果A 是对称正定矩阵，则1-A 也是对称正定矩阵 (2).如果A 是对称正定矩阵，则A 可以唯一地写成L L A T =，其中L 是具有正对角元的下三角矩阵。 证明： (1).因A 是对称正定矩阵，故其特征值i λ皆大于0，因此1-A 的特征值1 -i λ也皆大于0。因此 1-i λ也皆大于0，故A 是可逆的。又 111)()(---==A A A T T 则1-A 也是对称正定矩阵。 (2).由A 是对称正定，故它的所有顺序主子阵均不为零，从而有唯一的杜利特尔分解 U L A ~ =。又 022211111 1222 11111DU u u u u u u u u u U n n nn =? ???? ???? ???????? ?=????????? ?? ?=M O ΛΛO 其中D 为对角矩阵，0U 为上三角矩阵，于是 0~ ~DU L U L A == 由A 的对称性，得 ~ T T T L D U A A == 由分解的唯一性得 ~ L U T = 从而 ~~ T L D L A = 由A 的对称正定性，如果设),,2,1(n i D i Λ=表示A 的各阶顺序主子式，则有 011>=D d ，01 >= -i i i D D d ，n i ,,3,2Λ=
故 2 12 12 1 2 121D D d d d d d d d d d D n n n =?????? ? ?????? ?????????????? ?=????????????=O O O 因此 T T T LL D L D L L D D L A ===)(21~ 2 1~ ~2 121~ ， 其中2 1~ D L L =为对角元素为正的下三角矩阵。 .用列主元消去法解线性方程组 ??? ??=++-=-+-=+-6 1531815331232 1321321x x x x x x x x x 并求出系数矩阵A 的行列式(即A det )的值。 解 ?? ?? ??????----?→?-=???? ??????----?→??? ??? ?????----??→?- =-=?113/110053/7101513 186 76/3118/176/7053/7101513 186111153312151318)(323 2 18 1 21312 1m b A m m r r 所以解为33=x ，22=x ，11=x ，66det -=A 。
第一章 绪 论 本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题． §1.1 引 言 计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内利用有限的计算工具计算出模型的有效解答。 由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法． 这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括 (1) 非线性方程的近似求解方法； (2) 线性代数方程组的求解方法； (3) 函数的插值近似和数据的拟合近似； (4) 积分和微分的近似计算方法； (5) 常微分方程初值问题的数值解法； (6) 优化问题的近似解法；等等 从如上内容可以看出，计算方法的显著特点之一是“近似”． 之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关． 计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差． 我们需要在有限的时间段内得到运算结果，就需要将无穷的计算过程截断， 从而产生截断误差． 如 +++=! 21 !111e 的计算是无穷过程，当用 ! 1 !21!111n e n ++++= 作为e 的近似时，则需要进行有限过程的计算，但产生了 截断误差e e n -．
习题5 1．导出如下3个求积公式，并给出截断误差的表达式。 (1) 左矩形公式：?-≈b a a b a f dx x f ))(()( (2) 右矩形公式：))(()(a b b f dx x f b a -≈? (3) 中矩形公式：?-+≈b a a b b a f dx x f ))(2 ( )( 解：(1) )()(a f x f ≈， )()()()(a b a f dx a f dx x f b a b a -=≈?? (2) )()(b f x f ≈，??-=≈b a b a a b a f dx b f dx x f ))(()()( )()(2 1)()()()(2 ηηξf a b dx b x f dx b x f b a b a '--=-'=-'=??，),(,b a ∈ηξ (3) 法1 )2 ( )(b a f x f +≈ ， 法2 可以验证所给公式具有1次代数精度。作一次多项式 )(x H 满足 )2()2( b a f b a H +=+，)2 ()2(b a f b a H +'=+'，则有 2 )2 )((!21)()(b a x f x H x f +-''= -ξ， ),(b a ∈ξ 于是 2．考察下列求积公式具有几次代数精度： （1） ?'+ ≈1 )1(2 1 )0()(f f dx x f ； （2） )3 1()31()(1 1f f dx x f +- ≈?-。 解： （1）当1)(=x f 时，左=1，右=1+0=1，左=右； 当x x f =)(时，左21= ，右=2 1 210=+，左=右； 当2 )(x x f =时，左=3 1 ，右=1，左≠右，代数精度为1。
姓名：蒋元义、学号：、专业：测绘工程 一、在区间[-1,1]上分别取10,20n =用两组等距节点对龙格函数2 1 ()125f x x =+作多项式插值及三次样条插值，对每个n 值，分别画出插值函数即()f x 的图形。 解： 当N=10时，代码及图像如下： x=-1:0.2:1; y=1./(1+25*x.^2); x1=linspace(-1,1,10); p=interp1(x,y,x1,'linear'); p1=interp1(x,y,x1,'spline'); plot(x,y,'b'); hold on plot(x1,p,'r'); hold on plot(x1,p1,'k'); legend('龙格函数','多项式插值函数','三次样条插值函数'); grid on; title('N=10的插值函数及原函数图形'); xlabel('x 轴'); ylabel('y ‘轴');
当N=20时，代码及图像如下： x=-1:0.2:1; y=1./(1+25*x.^2); x1=linspace(-1,1,20); p=interp1(x,y,x1,'linear'); p1=interp1(x,y,x1,'spline'); plot(x,y,'b'); hold on plot(x1,p,'r'); hold on plot(x1,p1,'k'); legend('龙格函数','多项式插值函数','三次样条插值函数'); grid on; title('N=20的插值函数及原函数图形'); xlabel('x轴'); ylabel('y轴');
第2章线性方程组的解法 --------学习小结 一、本章学习体会 通过本章知识的学习我首先了解到求解线性方程组的方法可分为两类：直接法和迭代法。计算机虽然运行速度很快，但面对运算量超级多的问题，计算机还是需要很长的时间进行运算，所以，确定快捷精确的求解线性方程组的方法是非常必要的。 本章分为四个小节，其中前两节Gauss消去法和直接三角分解法因为由之前《线性代数》学习的一定功底，学习起来还较为简单，加之王老师可是的讲解与习题测试，对这一部分有了较好的掌握。第三节矩阵的条件数与病态方程组，我 Ax 的系数矩阵A与左端向量b的元素往往是通首先了解到的是线性方程组b 过观测或计算而得到，因而会带有误差。即使原始数据是精确的，但存放到计算机后由于受字长的限制也会变为近似值。所以当A和b有微小变化时，即使求解过程精确进行，所得的解相对于原方程组也可能会产生很大的相对误差。对于本节的学习掌握的不是很好，虽然在课后习题中对课堂知识有了一定的巩固，但整体感觉没有很好的掌握它。第四节的迭代法，初次接触迭代法，了解到迭代法就是构造一个无线的向量序列，使他的极限是方程组的解向量。迭代法应考虑收敛性与精度控制的问题。三种迭代方法的基本思想我已经掌握了，但是在matlab 的编程中还存在很大的问题。 在本节的学习中我认为我最大的问题还是程序的编写。通过这段时间的练习，虽然掌握了一些编写方法和技巧。相比于第一章是对其的应用熟练了不少，但在程序编写上还存在很多问题。希望在以后的学习中能尽快熟练掌握它，充分发挥它强大的作用。 二、本章知识梳理
2.1、Gauss 消去法（次重点） Gauss 消去法基本思想：由消元和回代两个过程组成。 2.1.1顺序Gauss 消去法（对方程组的增广矩阵做第二种初等行变换） 定理 顺序Gauss 消去法的前n-1个主元素) (k kk a (k=1,2,```,n-1)均不为零的充分必要条件是方程组的系数矩阵A 的前 n-1个顺序主子式 )1,,2,1(0)1()1(1 ) 1(1)1(11-=≠=n k a a a a D kk k k K ΛΛM M Λ 消元过程：对于 k=1,2,···,n-1 执行 （1）如果 ,0)(=a k kk 则算法失效，停止计算，否则转入（2） 。 （2）对于i=k+1,k+2,···n,计算 a a k kk k ik k i m )() (,= n k j i m a a a k kj ik k ij k ij ,,1,,) ()() 1(Λ+=-=+ n k i m b b b k k ik k i k i ,,1,) ()() 1(Λ+=-=+ 回代过程： a b x n nn n n n ) () (/= ） （1,,2,1/)() (1 )() (?--=- =∑+=n n k a x a b x k kk j n k j k kj k k k 2.1.2 列主元素Gauss 消去法（把） （n k k i a k kj ,,1,) (?+=中绝对值最大的元素交换到第k 行的主对角线位置）（重点） 定理 设方程组的系数矩阵A 非奇异，则用列主元素Gauss 消去法求解方程组时，各个列主元素a (k=1,2,```,n-1)均不为零。 消元过程：对于 k=1,2,···,n-1 执行 （1）选行号k i ，使 )()(max k i n i k k k i k k a a ≤≤=。 （2）交换A 与b 两行所含的数值。 （3）对于i=k+1,k+2,···n,计算
数值分析第8章 数值积分与数值微分 8.1 填空题 （1）n+1个点的插值型数值积分公式∫f(x)dx b a ≈∑A j n j=0f(x j )的代数精度至少是 n ，最高不超过 2n+1 。【注：第1空，见定理8.1】 （2）梯形公式有 1 次代数精度，Simpson 公司有 3 次代数精度。【注：分别见定理8.1,8.3】 （3）求积公式∫f(x)dx h 0≈h 2[f (0)+f (h )]+ah 2[f ′(0)?f ′(h)]中的参数a= 1/12 时，才能保证该求积公式的代数精度达到最高，最高代数精度为 3 。 解：令f(x)=1,x,x 2带入有， { h 2[1+1]+ah 2[0?0]=h h 2[0+h ]+ah 2[1?1]=12 (h 2)h 2[0+h 2]+ah 2[0?2h ]=13 (h 3) //注：x 的导数=1 解之得，a=1/12，此时求积公式至少具有2次代数精度。 ∴ 积分公式为：∫f(x)dx h 0≈h 2[f (0)+f (h )]+h 2 12[f ′(0)?f ′(h)] 令 f(x)= x 3带入求积公式有：h 2 [0 +h 3]+ h 212 [0?3h 2]=14 (h 4)，与f(x)= x 4的定积分计算值1 4 (h 4)相等， 所以，此求积公式至少具有3次代数精度。 令f(x)= x 4带入求积公式有，h 2[0+h 4]+h 2 12[0?4h 3]=1 6(h 5)，与f(x)= x 5的定积分计算值1 5(h 5)不相等，所以，此求积公式的最高代数精度为3次代数精度。 8.2 确定下列求积公式的求积系数和求积节点，使其代数精度尽量高，并指出其最高代数精度。 解题思路：按照P149 中8.3式进行求解，根据求积公式中未知量n 的数量决定代入多少f(x)，当积分公式代入求积节点x n 的计算结果与定积分的计算结果一致，继续代入求积节点X n+1,，若计算结果与对应的定积分计算结果不一致时，求积公式拥有最高n 次的代数精度。 （1）∫f(x)dx 2h 0≈A 0f (0)+A 1f (h )+A 2f(2h) 解：令f(x)=1,x,x 2代入有,【注：本例中需求解A 0、A 1、A 2共3个未知量，故需3个相异求积节点f(x)】 {A 0+A 1+A 2=2h A 1h +A 22h =1 2(2h )2A 1h 2+A 2(2h )2=1 3(2h )3 求解得A 0=13h ，A 1=43h ，A 2=1 3h ， ∴求积公式为：∫f(x)dx 2h 0≈13hf (0)+43hf (h )+1 3 hf(2h) ∵该求积公式对3个相异节点1,x,x 2均有余项E (f )=0， //注：参见P149定理8.1 ∴该求积公式至少具有2次代数精度。 令f(x)= x 3，代入求积公式有：4 3hh 3+1 3h (2h )3=4h 4 ∵函数f(x) = x 3的定积分结果为：∫x 3dx 2h 0=1 4(2h )4=4h 4 ，与求积公式计算值相等， ∴该求积公式具有3次代数精度。
第二章 习 题 1. 已知函数()f x 在3,1,4x =的值分别为4，2，5，求Lagrange 插值多项式的表达式. 2. 已知函数 ()f x 在3x =和 4的值分别为0.5和0.64，用线性插值求此函数在 3.8x =的函数值. 3. 证明：对于 ()f x 的以01x x <为节点的一次插值多项式1()p x ，有 2 101()()()8 x x f x p x M ??≤，01x x x ≤≤， 其中01 max ()x x x M f x ≤≤′′= . 4. 已知函数 ()f x 的函数值表： x 0.1 0.2 0.3 0.4 0.5 ()f x 0.70010 0.40160 0.10810 -0.17440 -0.43750 试利用这个函数表求函数()f x 在0.3和0.4之间的零点. 5. 设 01,,,n x x x ???为1n +个互异的节点，()k l x 为n 阶 Lagrange 插值基函数， 0()()n k k x x x ω==?∏.证明： （1） 0()1n k k l x =≡∑； （2） 0(),0,1,2,,k n j j k k x l x x j n =≡=???∑； （3） ()()0,0,1,2,,n j k k k x x l x j n =?≡=???∑； （4）() ()()() k k k x l x x x x ωω= ′?.
6. 若73()1f x x x =?+，求0172,2,,2f ???????和018 2,2,,2f ???????. 7. 设 53()1f x x x =++，求以1x =?，-0.8，0，0.5，1为插值节点的Newton 插值多 项式和插值余项. 8. 已知函数值表： x 0 1 4 3 6 ()f x -7 8 5 14 求Newton 插值多项式的表达式. 9. 分别在下列情况下计算 1n ?次多项式()p t 在指定点t 的的值，各需要多少次乘 法运 算？ （a）多项式()p t 按照单项式基函数展开； （b）多项式()p t 按照Lagrange 基函数展开； （c）多项式()p t 按照Newton 基函数展开. 10. 在区间[]0,/2π上使用5个等距节点对函数sin t 进行插值，试计算最大误差. 在 []0,/2π上选取若干点，比较函数值和插值多项式的值，验证误差界. 如果希望最大误 差为10 10 ?，需要多少个插值节点？ 11. 一直平面曲线()y f x =过点（0,1） ，（1,3），（2,4），试求一个三次多项式3()p x ，使其经过这3个点，并且满足3(1)1p ′=；然后给出余项3()()()R x f x p x =?的表达式. 12. 试求一个四次多项式4()p x ，使其满足44 44(0)(0)0(1)(1)1p p p p ′′====，，4(2)1p =. 13. 能否通过使用分段二次多项式进行插值，使插值函数是二次连续可微的？为什么？ 14. 设[]4 (),f x C a b ∈. 求三次多项式()p x ，使之满足插值条件 11 ()(),0,1,2, ()(),i i p x f x i p x f x ==?? ′′=?
第五章最小二乘法与曲线拟合小结 一、本章知识梳理 1、 从整体上考虑近似函数同所给数据点 (i=0,1,…,m)误差 (i=0,1,…,m) (i=0,1,…,m)绝对值的最大值，即误差向量 的∞—范数；二是误差绝对值的和，即误差向量r的1—范数；三是误差 平方和的算术平方根，即误差向量r的2—范数；前两种方法简单、自然，但不便于微分运算，后一种方法相当于考虑 2—范数的平方，因此在曲线拟合 中常采用误差平方和来度量误差 (i=0，1，…，m)的整体大小。 数据拟合的具体作法是：对给定数据 (i=0,1,…，m)，在取定的函 数类中,求,使误差(i=0,1,…,m)的平方和最小，即 从几何意义上讲，就是寻求与给定点 (i=0,1,…,m)的距离平方和为最小 的曲线（图6-1）。函数称为拟合函数或最小二乘解，求拟合 函数的方法称为曲线拟合的最小二乘法。 2、多项式拟合 假设给定数据点 (i=0,1,…,m)，为所有次数不超过的多项式构成的函数类，现求一,使得 (1) 当拟合函数为多项式时，称为多项式拟合，满足式（1）的称为最小二乘 拟合多项式。特别地，当n=1时，称为线性拟合或直线拟合。 显然 为的多元函数，因此上述问题即为求的极值问题。由多元函数求极值的必要条件，得 (2) 即
(3) （3）是关于的线性方程组，用矩阵表示为 (4) 式（3）或式（4）称为正规方程组或法方程组。 可以证明，方程组（4）的系数矩阵是一个对称正定矩阵，故存在唯一解。 从式（4）中解出 (k=0,1,…，n)，从而可得多项式 (5) 可以证明，式（5）中的满足式（1），即为所求的拟合多项式。我 们把称为最小二乘拟合多项式的平方误差，记作 由式(2)可得 (6) 多项式拟合的一般方法可归纳为以下几步： (1) 由已知数据画出函数粗略的图形——散点图，确定拟合多项式的次数n； (2) 列表计算和； (3) 写出正规方程组，求出； (4) 写出拟合多项式。 在实际应用中，或；当时所得的拟合多项式就是拉格朗日或牛 顿插值多项式。 3、曲线拟合： 曲线拟合，即把一组数据拟合为曲线，需遵循最小二乘法。常用双曲线型和指数型函数。
郑州大学研究生课程（2012-2013学年第一学期）数值分析 Numerical Analysis 习题课 第八章常微分方程数值解法
待求解的问题：一阶常微分方程的初值问题/* Initial-Value Problem */: ?????=∈=0 )(] ,[),(y a y b a x y x f dx dy 解的存在唯一性（“常微分方程”理论）：只要f (x , y ) 在[a , b ] ×R 1 上连续，且关于y 满足Lipschitz 条件，即存在与x , y 无关的常数L 使 对任意定义在[a , b ] 上的y 1(x ) 和y 2(x ) 都成立，则上述IVP 存在唯一解。 1212|(,)(,)||| f x y f x y L y y ?≤?一、要点回顾
§8.2 欧拉(Euler)法 通常取(常数),则Euler 法的计算格式 h h x x i i i ==?+1?? ?=+=+) (),(001x y y y x hf y y i i i i i =0,1,…,n ( 8.2 )
§8.2 欧拉(Euler)法(1) 用差商近似导数 )) (,()()()()(1n n n n n n x y x hf x y x y h x y x y +=′+≈+?? ?=+=+) (),(01a y y y x hf y y n n n n 差分方程初值问题向前Euler 方法h x y x y x y n n n ) ()()(1?≈ ′+)) (,() ()(1n n n n x y x f h x y x y ≈?+))(,()(n n n x y x f x y =′
1 第二章作业 问题描述： 不同温度的两种流体进入混合器混合，流出时具有相同的温度。流体A 和B 的热容（单位：cal/(mol ·K)）分别为： 2623.381 1.80410 4.30010pA c T T --=+?-? 1528.592 1.29010 4.07810pB c T T --=+?-? 焓变（单位：cal/mol ）为2 1 T p T H c dT ?= ? 。 A 进入混合器的温度为400℃， B 进入混合器的温度为700℃，A 的量（mol ）是B 的量（mol ）的两倍，试确定流体离开混合器的温度。 问题分析： 初始情况下，气体A 的温度比气体B 的温度低，故在混合过程中，气体A 温度升高，气体B 温度降低。由于没有外界加热或者做功，混合气体整体的焓变应该为零。 设A 有2mol ，B 有1mol ，根据焓变公式计算得到： 2 1 -262400 -22632= 6.762+3.608108.60010)6.762 1.80410 2.867105407.712T T A pA T H c dT T T dT T T T --?=?-?=+?-?-??（ 2 1 -152700 -1253=+1.29010 4.07810)0.64510 1.3591032958.030 T T B pB T H c dT T T dT T T T --?=?-?=+?-?-??（8.5928.592 而0A B H H ?+?=，故该问题最后变成求解方程 2263()15.3548.2541016.4571038365.742f T T T T --=+?-?- 的根的问题。接下来将采用二分法、试位法以及牛顿法进行改方程的求解。方程保存为f.m ，可在压缩文件中找到。 一、 二分法 二分法的基本思想为，确定有根区间，然后不断将区间二等分，通过判断f(x)的符号，逐步将区间缩小，直到有根区间足够小，便可满足精度要求的近似根。 本例中，可以清楚的得到有根区间为(400,700)。取容限误差为-3 0.510%?，可以保证5 位有效数字。程序编写存储于bisec.m 。 其中，bisec 函数定义为： function bisec(f_name,a,c,xmin,xmax,n_points) 调用时： >> bisec('f',400,700,400,700,1000) 相当于取了a=400;c=700;作图时横坐标取得是从400~700的范围，采样点为1000个。
数值分析第五章答案 【篇一：数值分析第五版计算实习题】 第二章 2-1 程序： clear;clc; x1=[0.2 0.4 0.6 0.8 1.0]; y1=[0.98 0.92 0.81 0.64 0.38]; n=length(y1); c=y1(:); or j=2:n %求差商 for i=n:-1:j c(i)=(c(i)-c(i-1))/(x1(i)-x1(i-j+1)); end end syms x df d; df(1)=1;d(1)=y1(1); for i=2:n %求牛顿差值多项式 df(i)=df(i-1)*(x-x1(i-1)); d(i)=c(i)*df(i); end disp(4次牛顿插值多项式); p4=vpa(collect((sum(d))),5) %p4即为4次牛顿插值多项式,并保留小数点后5位数 pp=csape(x1,y1, variational);%调用三次样条函数 q=pp.coefs; disp(三次样条函数); for i=1:4 s=q(i,:)*[(x-x1(i))^3;(x-x1(i))^2;(x-x1(i));1]; s=vpa(collect(s),5) end x2=0.2:0.08:1.08; dot=[1 2 11 12]; figure ezplot(p4,[0.2,1.08]); hold on y2=fnval(pp,x2); x=x2(dot);
y3=eval(p4); y4=fnval(pp,x2(dot)); plot(x2,y2,r,x2(dot),y3,b*,x2(dot),y4,co); title(4次牛顿插值及三次样条); 结果如下： 4次牛顿插值多项式 p4 = - 0.52083*x^4 + 0.83333*x^3 - 1.1042*x^2 + 0.19167*x + 0.98 三次样条函数 x∈[0.2,0.4]时， s = - 1.3393*x^3 + 0.80357*x^2 - 0.40714*x + 1.04 x∈[0.4,0.6]时，s = 0.44643*x^3 - 1.3393*x^2 + 0.45*x + 0.92571 x∈[0.6,0.8]时，s = - 1.6964*x^3 + 2.5179*x^2 - 1.8643*x + 1.3886 x∈[0.8,1.0]时，s =2.5893*x^3 - 7.7679*x^2 + 6.3643*x - 0.80571 输出图如下 2-3（1） 程序： clear; clc; x1=[0 1 4 9 16 25 36 49 64]; y1=[0 1 2 3 4 5 6 7 8];%插值点 n=length(y1); a=ones(n,2); a(:,2)=-x1; c=1; for i=1:n c=conv(c,a(i,:)); end q=zeros(n,n); r=zeros(n,n+1); for i=1:n [q(i,:),r(i,:)]=deconv(c,a(i,:));%wn+1/(x-xk) end dw=zeros(1,n); for i=1:n dw(i)=y1(i)/polyval(q(i,:),x1(i));%系数 end p=dw*q; syms x l8; for i=1:n