11
第二章 非线性方程数值解法
在科学计算中常需要求解非线性方程
()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 =．由左向右逐个计算()k f x ，如果有1()()0k k f x f x +<，则区间1[,]k k x x +就是方程的一个较小的有根区间．
一般情况下，只要步长h 足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程(2.1)的根的一个近似．
例2.1 确定出方程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]内有惟一实根．
12
如果希望将有根区间再缩小，可以取步长0.5h =，在点0.5x =，1x =， 1.5x =计算出函数值的符号，最后可知区间[1.5,2]内有一个实根． 二、二分法
二分法是求非线性方程实根近似值的最简单的方法．其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值．
设()f x 在区间[,]a b 上连续，()()0f a f b <，且方程(2.1)在区间(,)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 的一半(如图2.1所示)．
图2.1 二分法示意图
重复上述过程，建立如下嵌套的区间序列
1122[,][,][,][,]k k a b a b a b a b =??
??
其中每个区间的长度都是前一个区间长度的一半，因此[,]k k a b 的长度为
11
()2k k k b a b a --=
-
由*[,]k k x a b ∈和()/2k k k x a b =+，得
*11
()()22k k k k x x b a b a -≤-=-
当k →∞时，显然，有*
k x x →．总结得到如下收敛定理：
13
定理2.1 设()f x 在隔根区间[,]a b 上连续，且()()0f a f b <，则由二分法产生的
序列0{}k k x +∞
=收敛于方程(2.1)在[,]a b 上的根*x ，并且有误差估计
*1
()(1,2,)2k k
x x b a k -≤-= (2.2) 设预先给定根*x 的绝对误差限为ε，要求*k x x ε-≤，只要1
()2
k b a ε-≤成立，
这样求得对分次数
ln()ln ln 2
b a k ε
--≥
． (2.3)
取k 为大于(ln()ln )/ln 2b a ε--的最小整数．此时k x 是方程(2.1)的满足精度要求的根近似值．
注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断()0k f x =几乎不可能满足，取而代之为判断条件0()k f x ε<，其中0ε为根近似值的函数值允许误差限．
总结以上内容，给出如下算法 算法2.1 (二分法)
输入 端点,a b 、根的绝对误差限ε、根近似值的函数值允许误差限0ε； 输出 近似解c 或失败信息；
Step 1 用公式(2.3)计算最大迭代次数k ； Step 2 对1,,n k =循环执行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 =．
例 2.2 用二分法求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 =，利用二分法计算结果见表2.1．
14
二分法具有如下特点
(1) 优点：计算简单，对函数()f x 的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；
(2) 缺点：只能求单实根和奇数重实根，收敛较慢，与1/2为公比的等比级数相同．
当函数()f x '连续时，方程(2.1)的实重根可转换为
()
0()
f x f x ='的实单根． 一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供
初值．
§2.2 简单迭代法
简单迭代法是求解非线性方程根的近似值的一类重要数值方法．本节将介绍
简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法． 一、简单迭代法的基本思想
简单迭代法采用逐步逼近的过程建立非线性方程根的近似值．首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止．
在给定的有根区间[,]a b 上，将方程(2.1)等价变形为
()x x ?= (2.4)
在[,]a b 上选取0x 作为初始近似值，用如下迭代公式
1()k k x x ?+= (0,1,2,k =) (2.5)
建立序列0{}k k x +∞=．如果有*
lim k k x x →∞=，并且迭代函数()x ?在*x 的邻域内连续，对式(2.5)两边取极限，得
**()x x ?=
因而*x 是(2.4)的根，从而也是(2.1)的根．称()x ?为迭代函数，所得序列0{}k k x +∞
=为迭代序列．将这种求方程根近似值的方法称为简单迭代法，简称迭代法．
15
例2.3 试用方程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 =，迭代计算，结果见表2.2．
例 2.3表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛．那么迭代函数()x ?满足什么条
件时才能保证迭代序列收敛? 迭代序列0{}k k x +∞
=的误差如何估计? 怎样才能建立收敛速度快的迭代公式?
定理2.2 若函数()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 ∈，迭代公式(2.5)收敛，且*lim k k x x →∞
=
(3) 迭代公式(2.5)有误差估计式
*11k k k L
x x x x L
--≤-- (2.6)
16
*
101k
k L x x x x L
-≤-- (2.7)
(4) *
*1*lim ()k k k
x x x x x ?+→∞-'=- (2.8) 证明 (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 =，并且有1()k k x x ?+=，**()x x ?=，二者作差，并由微分中值定理得
***1()()()()k k k k x x x x x x ???ξ+'-=-=- (1,2,k = (2.9)
其中，k ξ介于k x 与*x 之间．结合条件②，得
**1k k x x L x x +-≤- (1,2,k = (2.10)
反复递推，有
**2*1*1100k k k k x x L x x L x x L x x ++-≤-≤-≤-≤≤-， (1,2,)k =
因01L <<，故*lim k k x x →∞
=．
(3) 由式(2.10)得
***
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
+-≤
-- (2.11) 又由于
111()()()()k k k k k k k x x x x x x ???η+--'-=-=-
1k k L x x -≤- (1,2,)k =
(2.12)
其中k η介于k x 和1k x -之间．综合式(2.11)及式(2.12)得误差估计
*11k k k L
x x x x L
--≤
-- 由式(2.12)反复递推，得
111210k k k k k x x L x x L x x -----≤-≤
≤-
并代入式(2.6)得误差估计
*
11011k
k k k L L x x x x x x L L
--≤-≤--- (1,2,)k =
(4) 由式(2.9)得
*
1*
()k k k x x x x ?ξ+-'=-
17
两端取极限，并注意到()x ?'的连续性和*lim k k x ξ→∞
=(因为k ξ介于*x 与k x 之间)，得
**1*lim ()k k k
x x x x x ?+→∞-'=-． 误差估计(2.6)称为后验误差估计，也称为误差渐进估计，误差估计(2.7)称为
先验误差估计．定理 2.2条件成立时，对任意0[,]x a b ∈，迭代序列均收敛，故称定理2.2为全局收敛性定理．下面讨论*x 邻近的收敛性，即局部收敛性．
定理 2.3 设存在方程()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 ????ηδδ'-=-=-≤<
由定理2.2知迭代过程1()k k x x ?+=对任意初值*0(,)x U x δ∈均收敛． 二、迭代法的收敛阶
为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念．
定义2.2 设迭代序列0{}k k x +∞=收敛到*x ，记*
k k e x x =-，如果存在常数0c >和实数1p ≥，使得
1lim
k p
k k
e c e +→∞
= (2.13)
则称序列0{}k k x +∞=是p 阶收敛的．当1p =时，称0{}k k x +∞
=为线性收敛的，此时要求
01c <<；1p >为超线性收敛．p 越大，序列0{}k k x +∞
=收敛到*x 越快．c 称为渐进常数，c 越小，收敛越快．所以迭代法的收敛阶是对迭代法收敛速度的一种度量． 显然，由定理 2.2(4)知，当*()0x ?'≠时简单迭代法线性收敛，渐进常数*()c x ?'=．
算法2.2 (简单迭代法)
输入 初始值0x 、容许误差ε； 输出 近似解1x 或失败信息；
Step 1 对1,,n m =循环执行Step 2～3； Step 2 10()x x ?=；
Step 3 若10x x ε-<，则输出1x ，end ；
否则01x x =，转向Step2．
例2.4 求方程()2lg 70f x x x =--=的最大实根的近似值，要求绝对误差不超过31102
-?．
解 (1)确定有根区间．方程等价形式为
27lg x x -=
18
作函数27y x =-和lg y x =的图形，如图 2.2所示，知方程的最大实根在区间[3,4]内．
(2)建立迭代公式，判别收敛性．将方程等价变形为
1
(lg 7)2
x x =+ 迭代函数1
()(lg 7)2
x x ?=+，迭代公式11(lg 7)2k k x x +=+．
由11
()02ln10x x
?'=
?>，[3,4]x ∈，知()x ?在区间[3,4]内
仅有一根．又(3) 3.74?≈，(4) 3.80?≈，所以，当[3,4]x ∈时，()[3,4]x ?∈．
图2.2 函数27y x =-和lg y x =的图形
因为 3.54
max ()(3)0.07x L x ??≤≤''==≈，所以对于一切[3,4]x ∈有
()(3)0.071x ??''≤≈<
由定理2.2知，迭代法收敛．
(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 +→∞
-=-
19
由于它线性收敛，误差减少的速度较慢，值得采用加速技术．下面介绍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 +++-=-
-+ (2.14)
它仍然收敛到*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 ??+=??
==??-?=-?-+?
(2.15)
或者直接写成
21
(())(())2()k k k k k k k
x x x x x x x ????+-=-
-+ (0,1,2
k = 可以证明Steffensen 迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限，但Steffensen 迭代法收敛速度更快，可以达到二阶收敛．证明请参考文献[19]．
例 2.5 对例 2.3用Steffensen 迭代法求方程根的近似值，要求
811
102
k k x x -+-
解 (1) 简单迭代法 将原方程化成12
(10/(4))x x =+，建立迭代公式
1
1104k k x x +??= ?+?
?
易验证该迭代公式在区间[1,2]上满足定理2.2的条件，产生的迭代序列收敛．
(2) Steffensen 迭代法 加速公式为
20
1
2122110410(0,1,2,)
4()2k k k k k s x t k s s x x x t s x +????= ?+????????==
??+???-?=-?-+?
(1) 取初值0 1.5x =，简单迭代法和Steffensen 迭代法计算结果见表2.3． 注意：Steffensen 迭代法每一迭代步的计算量大约是原简单迭代法计算量的两
倍．
§2.3 Newton 迭代法
Newton 迭代法是求解非线性方程根的近似值的一种重要数值方法．其基本思
想是将非线性函数()f x 逐步线性化，从而将非线性方程(2.1)近似地转化为一系列
线性方程来求解．下面讨论其格式的构造、收敛性、收敛速度以及有关变形． 一、Newton 迭代法的构造
设k x 是方程(2.1)的某根的一个近似值，将函数()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 '+-=
近似非线性方程(2.1)．设()0k f x '≠，则用线性方程的根作为非线性方程根的新近似值，即定义
1()()
k k k k f x x x f x +=-
' (2.16)
上式即是著名的Newton 迭代公式．它也是一种简单迭代法，其中迭代函数
21
()
()()
f x x x f x ?=-
' Newton 迭代法具有明显的几何意义(如图2.3所示)．方程()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 迭代法也称为切线法．
图2.3 Newton 迭代法的几何意义
二、收敛性
定理2.4 设*x 是方程(2.1)的单根，在*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 ξ'''==+-+
- (2.17) 其中k ξ介于*x 与k x 之间．又由Newton 迭代公式有
10()()()k k k k f x f x x x +'=+- (2.18)
式(2.17)与式(2.18)相减
22
**
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 +→∞''-=≠'- (2.19) 由迭代法收敛阶的定义知，Newton 迭代法至少具有二阶收敛速度．
上述定理给出了Newton 法局部收敛性，它对初值要求较高，初值必须充分靠近方程根时才可能收敛，因此在实际应用Newton 法时，常常需要试着寻找合适的初值．下面的定理则给出Newton 法在有根区间上全局收敛的一个充分条件．
定理2.5 设*x 是方程(2.1)在区间[,]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)
23
图2.4 定理2.5的几何解释
证明 满足定理条件(1)共有4种情形，如图2.4所示．下面仅以图2.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 ξ+''=-
-' (2.20) 式(2.20)右端的第二项大于零，因此*1n x x +>．由数学归纳法知*k x x >，(0,1,2,)k =． 其次证明0{}k k x ∞=单调递减．
由()0f x '>，*k x x >，*()0f x =知，()0k f x >，()0k f x '>，于是Newton 迭代公式(2.16)的第二项大于零，从而
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 ，利用式(2.20)及式(2.19)知该Newton 迭代序列二阶收敛．
算法2.3 (Newton 迭代法)
输入 初始近似值0x 、 容许误差ε； 输出 近似解1x 或失败信息；
Step 1 对1,,n m =循环执行Step 2～3； Step 2 1000()/()x x f x f x '=-；
Step 3 若10x x ε-<，则输出1x ，end ；
否则01x x =，转向step2．
例 2.6 利用非线性方程230x -=的Newton
的近似值，使得811102
n n x x ---≤?，并证明对任意0(0,)x ∈+∞，该迭代法均收敛．
24
解 (1) 建立计算公式
21
3213(0,1,2,)(2)
k k k k
k k
k x x x x x x +-=-
=+=
其中00x >．
(2) 判断收敛性
在区间(0,)+∞内，()20f x x '=>，()20f x ''=>
，当选取初值0)x ∈+∞时，存在足够大的M
，使得0]x M ∈．由定理 2.5知，该迭代公式产生的迭代序列
0{}k k x ∞=
当选取初值0x ∈时，
1000
13
()2x x x x =
+> 这样，从1x 起，以后的(2)k x k ≥
．
故该迭代公式对任何初值00x >都收敛． (3) 取初值02x =，迭代计算，结果见表2.4．
从表2.4可见，迭代4步后已经满足精度要求，精确解
1.7320508075
6888=． 三、Newton 迭代法的变形
Newton 迭代格式构造容易，迭代收敛速度快，但对初值的选取比较敏感，要求初值充分接近真解，另外对重根收敛速度较慢（仅有线性收敛速度），而且当函数复杂时，导数计算工作量大．下面从不同的角度对Newton 法进行改进． 1 Newton 下山算法
Newton 迭代法的收敛性依赖于初值0x 的选取，如果0x 偏离*x 较远，则Newton 迭代法有可能发散，从而在实际应用中选出较好的初值有一定难度，而Newton 下山法则是一种降低对初值要求的修正Newton 迭代法．
方程(2.1)的根*x 也是()f x 的最小值点，若把()f x 看成()f x 在x 处的高度，则*x 是山谷的最低点．若序列0{}k k x ∞=满足单调性条件
1()()k k f x f x +< (2.21) 则称0{}k k x ∞=为称为()f x 的下山序列．
25
在Newton 迭代法中引入下山因子(0,1]λ∈，将Newton 迭代公式(2.16)修正为
1()(0,1,2,)()
k k k k f x x x k f x λ
+=-=' (2.22)
适当选取下山因子λ，使得单调性条件(2.21)成立，即称为Newton 下山法．
对下山因子的选取是逐步探索进行的．一般地，从1λ=开始反复将因子λ的值减半进行试算，一旦单调性条件(2.21)成立，则称“下山成功”；反之，如果在上述过程中找不到使条件(2.21)成立的下山因子λ，则称“下山失败”，这时可对k x 进行扰动或另选初值0x ，重新计算． 2 针对重根情形的加速算法
假设*x 是方程的(2)m ≥重根，并且存在函数()g x ，使得有
**()()(),()0m f x x x g x g x =-≠ (2.23)
式中()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
lim11()()()
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 ?'<<，由定理2.2知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 +'=-
='''- (2.24)
它至少二阶收敛．
方法二 将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 +=-=' (2.25)
3 割线法
26
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 +--=-
-- (2.26)
上式即是割线法的迭代公式．
割线法也具有明显的几何意义，如图2.5所示，依次用割线方程
11
()()
()()k k k k k k f x f x y f x x x x x ---=+
--
的零点逐步近似曲线方程()0f x =的零点．
割线法的收敛速度比Newton 法稍慢一点，可以证明其收敛阶约为1.618，证明请参考文献[4]．此外在每一步计算时需要前两步的信息1,k k x x -，即这种迭代法也是两步法．两步法在计算前需要提供两个初始值0x 与1x ．
图2.5 割线法的几何意义
例 2.7 已知方程42()440f x x x =-+=
有一个二重根*x =Newton 法(2.16)和重根Newton 法(2.24)和(2.25)求其近似值，要求611
102
n n x x ---≤?
解
32()48,()128f x x x f x x '''=-=-，2()2
()()4f x x x f x x
μ-=
='，2m =．
由Newton 法(2.16)得
221
232(0,1,2,)44k k k k k k
x x x x k x x +-+=-=
=
由Newton 法(2.24) 得
27
2
1
22
(2)4(0,1,2,)22
k k k
k k k k x x x x x k x x +-=-==++
由Newton 法(2.25) 得
221
22(0,1,2,)22k k k k k k
x x x x k x x +-+=-=
=
利用上述三种迭代格式，取初值0 1.4x =，分别计算，结果见表2.5．
3 10
知识结构图
习 题
1 用二分法求方程2
sin 0x e x --=在区间[0,1]内根的近似值，精确到3位有效数
字．
2 方程340x x +-=在区间[1,2]内有一根，试用二分法求根的近似值，使其具有5
位有效数字，至少应二分多少次．
基本概念 （单根、重根、收敛阶）
28
3 已知方程3210x x --=在0 1.5x =附近有根，试判断下列迭代格式的收敛性，并
用收敛的迭代公式求方程根的近似值，比较迭代次数，要求311102
n n x x ---≤? (1) 1211n 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 ∈均收敛，并
求各方程根的近似值，要求411
102
n n x x ---≤?．
5 用迭代法求50.20x x --=的正根，要求准确到小数点后5位．
6 用Steffensen 迭代法求方程31x x =-在区间[1,1.5]内的根，要求准确到小数点后
4位．
7 用Newton 法和割线法分别求方程3310x x --=在02x =附近根的近似值，并比
较迭代次数(根的准确值为* 1.87938524x =，要求准确到小数点后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）
一 选择题(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）矩阵的范数小。
第八章 矩阵特征值问题计算 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 -=== = 计算结果如下：
第7章复习与思考题
求f (X )= 0的零点就等价于求(x )的不动点，选择一个初始近似值X 0，将它代入X =「(X ) 的右端，可求得 X 1 h%X °)，如此反复迭代有 X k 1 二(X k ), k =0,1,2,..., (X)称为迭代函数，如果对任何 X 。? [a,b]，由x k 卜h%x k ),k =0,1,2,...得到的序列 〈X k 1有极限 则称迭代方程收敛，且X* =?(x*)为?(X )的不动点 故称 X k q 二(X k ), k =0,1,2,...为不动点迭代法。 5?什么是迭代法的收敛阶？如何衡量迭代法收敛的快慢？如何确定 X k 1 二「(X k )(k =0,1,2,...)的收敛阶 P219 设迭代过程X k 1'h%X k )收敛于 (X)的根X*，如果当k > 时，迭代误差 e k = x k - x *满足渐近关系式 —t C,C =const 式 0 e/ 则称该迭代过程是 p 阶收敛的，特别点，当 p=1时称为线性收敛，P>1时称为超线性收敛， p=2时称为平方收敛。 以收敛阶的大小衡量收敛速度的快慢。 6?什么是求解f(x)=0的牛顿法？它是否总是收敛的？若 f(X*) =0，X*是单根，f 是光 滑，证明牛顿法是局部二阶收敛的。 牛顿法: 当| f (X k )卜J 时收敛。 7?什么是弦截法？试从收敛阶及每步迭代计算量与牛顿法比较其差别。 在牛顿法的基础上使用 2点的的斜率代替一点的倒数求法。就是弦截法。 收敛阶弦截法1.618小于牛顿法2 计算量弦截法 <牛顿法(减少了倒数的计算量) 8?什么是解方程的抛物线法？在求多项式全部零点中是否优于牛顿法？ P229 X - m X k 1 =X k f (X k ) f (X k )
第一章 绪 论 本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题． §1.1 引 言 计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内利用有限的计算工具计算出模型的有效解答。 由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法． 这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括 (1) 非线性方程的近似求解方法； (2) 线性代数方程组的求解方法； (3) 函数的插值近似和数据的拟合近似； (4) 积分和微分的近似计算方法； (5) 常微分方程初值问题的数值解法； (6) 优化问题的近似解法；等等 从如上内容可以看出，计算方法的显著特点之一是“近似”． 之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关． 计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差． 我们需要在有限的时间段内得到运算结果，就需要将无穷的计算过程截断， 从而产生截断误差． 如 +++=! 21 !111e 的计算是无穷过程，当用 ! 1 !21!111n e n ++++= 作为e 的近似时，则需要进行有限过程的计算，但产生了 截断误差e e n -．
证明：如果求积公式（）对函数f （x ）和g （x ）都准确成立，则它对于线性组合af(x)+bg(x) (a,b 均为常数)亦准确成立. 因此，求积公式（）具有m 次代数精度的充分必要条件是：它对任一小于等于m 次的多项均能准确成立，但对某个m+1次多项式不能准确成立. ()()不能成立 对与题设矛盾多项式都能准确成立，次多，即对任意的线性组合亦准确成立也能准确成立，则对若对的线性组合亦准确成立对次的多项式准确成立对于任意小于等于不准确成立，对的线性组合亦准确成立对成立次的多项式于等于根据定义可知：对于小次代数精度 机械求积公式具有机械求积公式也成立 对于线性组合同理可得 机械求积公式都成立 对于证明： 1m 1321321320 000 0)1(,,,,,,1,,,,,1,,,,,1),1,0()(2)()()] ()([)()()]()([) ()() ()() ()() ()()(),(1++++=======∴+? ∴?∴==∴?+∴+=+≈+∴≈≈∴≈≈∴∑∑?∑?∑?∑? ∑?∑x m x x x x x x x x x x m x x x x x m j x x f m m x bg x af x bg x af A x bg A x af A dx x bg x af x bg A dx x bg x af A dx x af x g A dx x g x f A dx x f x g x f m m m m m m j n k k k n k k k b a n k k k b a n k k k b a n k k k b a n k k k b a n k k k 直接验证中矩形公式具有一次代数精度，而Simpson 公式则具有3次代数精度。
第七章非线性方程求根 一、重点内容提要 （一）问题简介 求单变量函数方程 ()0f x = (7.1) 的根是指求*x （实数或复数），使得(*)0f x =.称*x 为方程(7.1)的根,也称*x 为 函数()f x 的零点.若()f x 可以分解为 ()(*)()m f x x x g x =- 其中m 为正整数,()g x 满足()0g x ≠,则*x 是方程(7.1)的根.当m=1时,称*x 为单根;当m>1时,称*x 为m 重根.若()g x 充分光滑,*x 是方程(7.1)的m 重根,则有 (1)() (*)'(*)...(*)0,(*)0m m f x f x f x f x -====≠ 若()f x 在[a,b]上连续且()()0f a f b <,则方程(7.1)在(a,b)内至少有一个实根,称[a,b]为方程(7.1)的有根区间.有根区间可通过函数作图法或逐次搜索法求得. (二)方程求根的几种常用方法 1.二分法 设()f x 在[a,b]上连续,()()0f a f b <,则()0f x =在(a,b)内有根*x .再设()0f x =在 (a,b)内仅有一个根.令00,a a b b ==,计算0001 ()2x a b =+和0()f x .若0()0f x =则*x x =,结束计算;若00()()0f a f x >,则令10,1a x b b ==,得新的有根区间11[,]a b ;若 00()()0 f a f x <,则令 10,10 a a b x ==,得新的有根区间 11[,]a b .0011[,][,]a b a b ?,11001()2b a b a -=-.再令1111 ()2x a b =+计算1()f x ,同上法得 出新的有根区间22[,] a b ,如此反复进行,可得一有根区间套 1100...[,][,]...[,] n n n n a b a b a b --????
数值分析第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 ∈C [a , b ]，写出三种常用范数2 1 f f 及∞ f 。 2．f , g ∈C [a , b ]，它们的内积是什么？如何判断函数族{? 0, ? 1, …, ? n }∈C [a , b ]在[a ,b ]上线性无关？ 3．什么是函数f ∈C [a , b ]在区[a , b ]上的n 次最佳一致逼近多项式？ 4．什么是f 在[a , b ] 上的n 次最佳平方逼近多项式？什么是数据{}m i f 0的最小二乘曲 线拟合？ 5．什么是[ a , b ]上带权ρ (x )的正交多项式？什么是[ -1, 1 ]上的勒让德多项式？它有什 么重要性质？ 6．什么是切比雪夫多项式？它有什么重要性质？ 7．用切比雪夫多项式零点做插值得到的插值多项式与拉格朗日插值有何不同？ 8．什么是最小二乘拟合的法方程？用多项式做拟合曲线时，当次数n 较大时为什么不直接求解法方程？ 9．哪种类型函数用三角插值比用多项式插值或分段多项式插值更合适？ 10．判断下列命题是否正确？ （1）任何f (x ) ∈C [a , b ]都能找到n 次多项式P n (x ) ∈ H n ，使| f (x ) - P n (x ) | ≤ ε ( ε 为任给的误差限)。 （2）n n H x P ∈)(* 是f (x )在[ a , b ]上的最佳一致逼近多项式，则)()(lim * x f x P n n =∞ →对 ],[b a x ∈?成立。 （3）f (x ) ∈C [a , b ]在[a , b ]上的最佳平方逼近多项式P n (x ) ∈ H n 则)()(lim x f x P n n =∞ →。 （4）)(P ~ x n 是首项系数为1的勒让德多项式，Q n (x ) ∈ H n 是任一首项系数为1的多项式，则 ? ? --1 1 21 1 2d )(d )](P ~ [x x Q x x n n 。 （5）)(T ~ x n 是[-1 , 1]上首项系数为1的切比雪夫多项式。Q n (x ) ∈ H n 是任一首项系数为1的多项式，则 .)(max )(~ max 1 11 1x Q x T n x n x ≤≤-≤≤-≤ （6）当数据量很大时用最小二乘拟合比用插值好。
第三章 函数逼近与曲线拟合 1． ()sin 2 f x x π =，给出[0,1]上的伯恩斯坦多项式1(,)B f x 及3(,)B f x 。 解： ()sin ,2 f x π = [0,1]x ∈ 伯恩斯坦多项式为 (,)()()n n k k k B f x f P x n ==∑ 其中()(1)k n k k n P x x x k -??=- ??? 当1n =时， 01()(1)0P x x ?? =- ??? 1101()(,)(0)()(1)()1(1)sin(0)sin 022P x x B f x f P x f P x x x x ππ=∴=+??=-?+ ??? = 当3n =时， 3 022 122233 31()(1)01()(1)3(1) 03()(1)3(1) 13()3P x x P x x x x x P x x x x x P x x x ?? =- ?????=-=- ????? =-=- ????? == ???
3 3022322 33223 (,)()() 03(1)sin 3(1)sin sin 6 3 2 3(1)(1)25632221.50.4020.098k k k B f x f P x n x x x x x x x x x x x x x x x π π π =∴==+-+-+= --+-=++≈--∑ 2． 当()f x x =时，求证(,)n B f x x = 证明： 若()f x x =，则 (,)()()n n k k k B f x f P x n ==∑ 001 11(1)(1) 11(1)(1)(1)(1)!(1)[(1)(1)1](1)(1)!1(1) 11(1)1[(1)]n k n k k n k n k k n k n k k n k n k k n k n k k n n k x x k n k n n n k x x n k n n k x x k n x x k n x x x k x x x x -=-=-=-=----=-?? =- ???--+=-----+=---??=- ?-??-??=- ?-?? =+-=∑∑∑∑∑ 3．证明函数1,,,n x x 线性无关 证明： 若20120,n n a a x a x a x x R ++++=?∈ 分别取(0,1,2,,)k x k n = ，对上式两端在[0,1]上作带权()1x ρ≡的内积，得
郑州大学研究生课程（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 =′
第八章习题解答 3、设方程()0f x =有根，且'0()m f x M <≤≤。试证明由迭代格式1()k k k x x f x λ+=- (0,1,2,)k =产生的迭代序列{}0k k x ∞=对任意的初值0(,)x ∈-∞+∞，当20M λ<<时，均收敛于方程的根。 证明： 设()()x x f x ?λ=-，可知()x ?在(,)-∞∞上可导 对于任意给定的λ值，满足条件'0()m f x M <≤≤时 （1）''()1()x f x ?λ=- 则1'()11M x m λ?λ-≤≤-< 又20M λ<<，M>0 则02M λ<<时，11M λ-<- 所以11'()11M x m λ?λ-<-≤≤-< 若令max{1,1}L M m λλ=--，则可知'()1x L ?≤< （2）由0()(0)'()(0)'()x x x dx x ?????ε=+=+? 则()lim 1x x L x ?→∞??≤< ??? 所以，存在一个数a ，当x a >时，()x x ?< 同时，()x ?在[,]a a -内有界，即存在0b >使得[,]x a a ?∈-，()x b ?< 我们选取 max{,}c a b =，则对任意x 有0()max{,}x c x ?< 则对给定的任意初值0x ，设0max{,}d c x = 则0[,]x d d ∈-，于是在区间[,]d d -上有()x d ?< 即满足映内性 有（1）、（2）可知，()x ?满足收敛定理 迭代序列0{}k k x ∞=收敛于方程的根 6. 给出计算...222+++=x 的迭代格式，讨论迭代格式的收敛性，并证明2=x 解：构造迭代格式10,1,2,k x k +==??? 2k x ≤ 令()x ?=x ?∈?时，()x ??∈? '() x ?=，当x ?∈?时，1 '()12x ?<<
第一章绪论 1设x 0, x的相对误差为「.，求In x的误差。 * * e* x * _x 解：近似值x*的相对误差为:.=e* x* x* 1 而In x 的误差为e In x* =lnx*「lnx e* x* 进而有；(ln x*)::. 2?设x的相对误差为2%求x n的相对误差。 解：设f(x—，则函数的条件数为Cp^胡1 n A. x nx . 又7 f '(x)= nx n」C p |=n n 又；；r((x*) n) ： C p ；,x*) 且e r (x*)为2 .；r((x*)n) 0.02 n 3 ?下列各数都是经过四舍五入得到的近似数，即误差限不超过最后一位的半个单位，试指 出它们是几位有效数字：X； h.1021 , x；=0.031 , x3 =385.6 x；=56.430, x5 =7 1.0. 解：x；=1.1021是五位有效数字； X2 =0.031是二位有效数字； X3 =385.6是四位有效数字； x4 = 56.430是五位有效数字； x5 -7 1.0.是二位有效数字。 4.利用公式(2.3)求下列各近似值的误差限：⑴ 为+X2+X4,(2) x-i x2x3,(3) x2/ x4. * * * * 其中X1,X2,X3,x4均为第3题所给的数。
解:
* 1 4 ；(x-| ) 10 2 * 1 3 ;(x 2) 10 2 * 1 1 ；(x 3) 10 * 1 3 ；(x 4) 10 2 * 1 1 ；(x 5) 10 2 (1)；(为 X 2 X 4) =；(为)亠：(x 2)亠：(x 4) =1 10 4 1 10 J 丄 10^ 2 2 2 = 1.05 10” * * * (2)(X 1X 2X 3) * * * ** * ** * X 1X 2 8(X 3) + X 2X 3 g(xj + X 1X 3 名(X 2) 1 1 0.031 汉 385.6 汉?汉10鼻 + 1.1021 域 385.6 汉?汉10 (3) XX 2/X 4) X 4 0.031 1 10” 56.430 丄 10’ 2 2 56.430 56.430 =10° 5计算球体积要使相对误差限为 1，问度量半径R 时允许的相对误差限是多少? 4 3 解：球体体积为V R 3 则何种函数的条件数为 =1.1021汉 0.031 汉 * 汉 10」+ 0.215
数值分析第一章作业 1.数值计算方法设计的基本手段是( ). (A) 近似 (B) 插值 (C) 拟合 (D) 迭代 2.为了在有限时间内得到结果,用有限过程取代无限过程所产生的近似解与精确解之间的误差称为( ). (A) 舍入误差 (B) 截断误差 (C) 测量误差 (D) 绝对误差 3.由于计算机的字长有限,原始数据在机器内的表示以及进行算术运算所产生的误差统称为( ). (A) 舍入误差 (B) 截断误差 (C) 相对误差 (D) 绝对误差 4.数值计算方法研究的核心问题可以概括为( )对计算结果的影响. (A) 算法的稳定性 (B) 算法的收敛性 (C) 算法的复杂性 (D) 近似 5.当N 充分大时,利用下列各式计算121N N dx I x +=+?,等式( )得到的结果最好. (A) arctan(1)arctan()I N N =+- (B) 2arctan(1)I N N =++ (C) 21arctan()1I N N =++ (D) 211I N =+ 6. 计算61), 1.4≈,利用下列哪个公式得到的结果最好?为什么? (B) 3(3- (D) 99-7.计算球体的体积,已知半径的相对误差限不超过3310-?,则计算所得体积的相对误差限如何估计? 8.设0x >,近似值*x 的相对误差限为δ,试估计*ln x 的误差限. 9.计算圆柱体的体积,已知底面半径r 及圆柱高h 的相对误差限均不超过δ,则计算所得体积的相对误差限如何估计?. 10.用秦九韶算法求32()431f x x x x =-+-在2x =处的值. 11.已知近似值 1.0000x *=的误差限4()110x ε*-=?,21()16 f x x = ,求(())f x ε*,并说明x *及()f x *的各有几位有效数字. 12. 分析算法011111,,32,1,2,,k k k y y y y y k +-?==???=-=?的数值稳定性.
WORD格式.分享 第5章 复习与思考题 1、用高斯消去法为什么要选主元？哪些方程组可以不选主元？ k答：使用高斯消去法时，在消元过程中可能出现 a的情况，这时消去法无法进行；即 kk k时主元素0 和舍入 增长 a，但相对很小时，用其做除数，会导致其它元素数量级的严重 kk 计 误差的扩散，最后也使得计算不准确。因此高斯消去法需要选主元，以保证计算的进行和 算的准确性。 当主对角元素明显占优（远大于同行或同列的元素）时，可以不用选择主元。计算时一般选择列主元消去法。 2、高斯消去法与LU分解有什么关系？用它们解线性方程组Ax=b有何不同？A要满足什 么条件？ 答：高斯消去法实质上产生了一个将A分解为两个三角形矩阵相乘的因式分解，其中一个 为上三角矩阵U，一个为下三角矩阵L。 用LU分解解线性方程组可以简化计算，减少计算量，提高计算精度。 A需要满足的条件是，顺序主子式（1,2，?，n-1）不为零。 3、楚列斯基分解与LU分解相比，有什么优点？ 楚列斯基分解是LU分解的一种，当限定下三角矩阵L的对角元素为正时，楚列斯基分解具有唯一解。 4、哪种线性方程组可用平方根法求解？为什么说平方根法计算稳定？ 具有对称正定系数矩阵的线性方程可以使用平方根法求解。 ，切对角元素恒为正数，因此，是一个稳定的 平方根法在分解过程中元素的数量级不会增长 算法。 5、什么样的线性方程组可用追赶法求解并能保证计算稳定？ 对角占优的三对角方程组 6、何谓向量范数？给出三种常用的向量范数。 向量范数定义见p53，符合3个运算法则。 正定性 齐次性 三角不等式 x为向量，则三种常用的向量范数为：（第3章p53,第5章p165） 设 n ||x|||x| 1i i1 1 n 22 ||x||(x) 2i i1 ||x||max|x i| 1in
西北工业大学理学院欧阳洁1 常微分方程初值问题的数值解法§3 Runge –Kutta 方法§4 单步法的收敛性、相容性和稳定性§5 线性多步法第八章 §1 常微方分程常微方分程初值问题的数值解法概述§2 几种简单的单步法
西北工业大学理学院欧阳洁2一问题及基本假设 § 1 常微方分程 常微方分程初值问题的数值解法概述 二离散化方法
上述定理称为一阶常微分方程初值问题解 的适定性（存在性、惟一性与稳定性）定理。 对所讨论的一阶常微分方程初值问题，本 章假设该问题是适定的，即解析解y(x)在区间[a,b]上是存在、惟一，且具有充分的光滑度。 因此f(x,y(x))也充分光滑。 西北工业大学理学院欧阳洁4
西北工业大学理学院欧阳洁6 常微分方程初值问题的数值解法分为： ①单(一)步法：计算时，只用到和，即前一步的值。 1+n y n y n n x x ,1+显式单步法的一般形式为②多步法：计算时，除用到和以外，还用到和，即用到前k 步的值。 p n x ?)1;1,2,1(>?=?k k p y p n L 1+n y n y n n x x ,1+对单步法与多步法，有显式与隐式方法之分。显式、隐式多步法的一般形式类似。 隐式单步法的一般形式为) ,,(1h y x h y y n n n n ?+=+),,,(11h y y x h y y n n n n n +++=?数值解法建立的过程：通过一定的离散化方法,将连续性问题的求解转化为有限个离散节点上解析解近似值的求解。 常用的离散化方法： Taylor 展开法；差商直接代替微商；数值积分法。
数值分析作业 第二章 1、用Gauss消元法求解下列方程组： 2x 1-x 2 +3x 3 =1, (1) 4x 1+2x 2 +5x 3 =4, x 1+2x 2 =7; (2) 解： A=[2 -1 3 1;4 2 5 4;1 2 0 7] n=size(A,1);x=zeros(n,1);flag=1; % 消元过程 for k=1:n-1 for i=k+1:n if abs(A(k,k))>eps A(i,k+1:n+1)= A(i,k+1:n+1)-A(k,k+1:n+1)*A(i,k)/A(k,k); else flag=0; return end end end % 回代过程 if abs(A(n,n))>eps x(n)=A(n,n+1)/A(n,n); else flag=0; return end for i=n-1:-1:1 x(i)=(A(i,n+1)-A(i,i+1:n)*x(i+1:n))/A(i,i); end return x A = 2 -1 3 1 4 2 5 4 1 2 0 7
x = 9 -1 -6 11x1-3x2-2x3=3, (2)-23x 1+11x 2 +1x 3 =0, x 1+2x 2 +2x 3 =-1; (2) 解： A=[11 -3 -2 3;-23 11 1 0;1 2 2 -1] n=size(A,1);x=zeros(n,1);flag=1; % 消元过程 for k=1:n-1 for i=k+1:n if abs(A(k,k))>eps A(i,k+1:n+1)= A(i,k+1:n+1)-A(k,k+1:n+1)*A(i,k)/A(k,k); else flag=0; return end end end % 回代过程 if abs(A(n,n))>eps x(n)=A(n,n+1)/A(n,n); else flag=0; return end for i=n-1:-1:1 x(i)=(A(i,n+1)-A(i,i+1:n)*x(i+1:n))/A(i,i); end return x A = 11 -3 -2 3 -23 11 1 0 1 2 2 -1 x = 0.2124 0.5492 -1.1554 4、用Cholesky分解法解方程组 3 2 3 x1 5 2 2 0 x2 3 3 0 12 x3 7