第二章 非线性方程的数值解法2

f ( x * ) = f ′( x * ) = ⋯ = f
( m −1 )
( x * ) = 0, f
(m )
(x* ) ≠ 0
第二章 非线性方程的数值解法
当f(x)不是x的线性函数时，称对应的函数方程 f(x)不是x的线性函数时， 不是 为非线性方程。如果f(x)是多项式函数， 为非线性方程。如果f(x)是多项式函数，则称为代数 f(x)是多项式函数 方程，否则称为超越方程（三角方程，指数、 方程，否则称为超越方程（三角方程，指数、对数方 程等）。一般称n 程等）。一般称n次多项式构成的方程 ）。一般称
y
50 a
a+1 a
a (e
+e 2
−
50 x a
)
= a +1
要计算电缆的长度, 要计算电缆的长度,必 须先求出上述方程中
-50
O
50
x
,由于它是关于 的非线性方程, 由于它是关于a 的a ,由于它是关于a的非线性方程,没有现 成的公式可用,,因此只能寻求其他解法. ,,因此只能寻求其他解法 成的公式可用,,因此只能寻求其他解法.
2.1.1确定有根区间的方法 确定有根区间的方法
a n x + a n −1 x
n
n −1
+ ⋯ + a1 x + a 0 = 0
( a n ≠ 0)
为n次代数方程,当n＞1时,方程显然是非线性的 次代数方程, 一般稍微复杂的3次以上的代数方程或超越方程, 一般稍微复杂的3次以上的代数方程或超越方程, 很难甚至无法求得精确解。 很难甚至无法求得精确解。本章将介绍常用的求解 非线性方程的近似根的几种数值解法
记笔记
2.2 二分法

区间,如此反复,直到求出满足精度要求的近似根.
具体步骤如下：
10
令 (a, b) (a0 , b0 )
取a0 , b0 中点 x0
a0 b0 2
将其二分，
这时有三种情况： 若 f x0 0 , 则 x x0 ; 否则， x f a f x 0 , 则 a , x0 , 令 a1 a , b1 x0 ; 若 0
1 1 b2 a2 (b1 a1 ) 2 (b a ) , 2 2 ba bk ak k 2
ak bk 区间 ak , bk 的中点 xk 形成一个序列 x0 , x1 ,, xk ,, 2
显然有 lim x k x .
k
13
实际计算中，对于给定的根的允许误差 0 ,
5
求方程根的近似值，需要解决的问题：
⑴ 根的存在性. ⑵ 根的隔离. 要判断方程有没有根，有几个； 找出有根区间，使得在较小的区间内
方程只有一个根，以得到根的近似值.
⑶ 根的精确化. 利用合适的数值计算方法，逐步 把根精确化，直至满足精度要求.
6
二、逐步搜索法
假设f(x)在有根区间[a,b]单值连续，且f(a)<0.
一般步骤：
取合适的步长
y
ba h , n
f(x) 0 a x* b x
从x0=a出发，按步长逐步向右跨进行搜索，
若发现f(xk)与f(a)异号，则确定一个缩小的有根区间
[ xk 1 , xk ], 其宽度等于步长h.
特别地，若f(xk)=0,则xk就是所求的根.
7
例 对方程f (x)=x3-x-1=0 搜索有根区间.
12

xk x* ( xk 1 ) ( x* ) ' ( ) xk 1 x* L xk 1 x*
其中ξ 介于 xk 1与x* 之间，故有
x k x * L x k 1 x * ... Lk x 0 x * , k 1,2,...
L x x* x x*
其中在x与x*之间，即S。
故 x S , ( x) S。 证毕
Remark1：全局与局部收敛定理中的条件都是充分 条件，条件满足则迭代法收敛，不满足则不能判定， 此时可以用试算来判定迭代法的是收敛性。
1 Remark2：可以证明，若在根 x * 的邻域中 ' ( x) ，则 可以以邻域内任何一点 x 0 为初始值，用迭代过程产生 的序列就一定不会收敛于 x * 。事实上，
*
Remark2：也可以使用 f ( xk ) 来控制误 差。 Remark3：二分法的优点是方法及相应的程序均 简单，且对f(x)性质要求不高，只要连续即可。 但二分法不能用于求复数根和偶数重根，且收 敛速度比较慢。因此，一般常用该方法求根的 初始近似值，然后再用其它的求根方法精确化。
定义f (x)
2.事后误差估计： 给定ε，每步检查 若成立，则取
1 xk 1 x k 1 (b a) 2
*
，
x* xk 1 ，否则继续对分。
Remark1：由于 故也可以用
1 xk 1 x xk 1 xk k 1 (b a) ， 2 xk 1 xk 来控制误差（最常用）
故由连续函数的介值定理知，至少存在 x* [a, b],
使g ( x* ) 0,即 ( x* ) x*，即 x *是方程 x ( x)的根。

x [1,2]
所以 ( x)是区间 [a, b]上严格单调增函数。
例题
而 (1) 3 2 1 ， (2) 3 3 2
即[ (1), (2)][1,2]，所以 ( x)满足条件（ 1 ）。
又 1 | ' ( x) || ( x 1) 3
2 3
|
1 3 4
(1) ( 2) 输入 : 有根区间 [a, b]的a, b值及精度控制量 ; if f ( a ) f (b) 0 then 返回第 1步, 重新
输入a, b值else转第3步; (3) while | a b | 时做 1 1)令x ( a b), 计算f ( x); 2 2)if f (a) f ( x) 0 then else endwhile; ( 4)输出x 1 ( a b). 2 [ a, b][ a, x]; [ a, b][ x, b].
a x13 1.365173390 本题的精确解为： a 1.36523001 ... 故绝对误差( x) x* x 0.000056 ... 二分法的区间每次只缩 小一半，因此它是一种 收敛 速度很慢的方法。
等步长扫描法求有根区间

用计算机求有根区间：等步长扫描法。 设h>0是给定的步长，取 x0 a, x1 a h ，
f ( x0 ) f ( x1 ) 0
若
则扫描成功；否则令
x0 x1 , x1 x0 h ，继续上述方法，直到成
功。如果 x1 b 则扫描失败。再将h 缩小，
继续以上步骤。
等步长扫描算法
算法：（求方程 f ( x) 0 的有根区间） (1) 输入 a, b, h ； (2) f 0 f (a) ； (3) x a h, f1 f ( x)，若 x b 输出失败信息， 停机。 (4)若 f1 0。输出 x ，已算出方程的一个根，停 机。

p!
(
p
)
(
)(
xk
)p
xk1
1
p!
(
p)
(1
)(
xk
)p
lim
k
xk1 xk p
1 ( p) ( )
p!
0
必要性 （略）
例 能不能用迭代法求解方程x=4-2x，如果不能
时，试将方程改写成能用迭代法求解的形式.
方程为x-4+2x =0.设f(x)= x-4+2x ，则f(1)<0，f(2)>0， f‘(x)= 1+2x ln2>0,故方程f(x)=0仅在区间(1, 2)内有唯一根.
称该迭代法是全局收敛的。
迭代法的局部收敛性
定义2 设方程x=(x) 根α, 如果存在α 的某个邻域 : x-α，对任意初值
x0，迭代过程所产生的序列均收敛 于根α ，则称该迭代法是局部收敛的.
迭代过程的收敛速度
定义3 记 ek = α- xk ，若
则称迭代过程kli是m pee阶kk1p收 敛C 的0. 特别地，当p=1时，称为线性收敛；
题中 (x)=4-2x，当时x(1,2)时,' (x)=-2xln2>2ln2>1 ,由
定理1.2不能用 xk1 4 2xk 来迭代求根.
把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1°当x[1,2]时， (x)[1,ln3/ln2] [1,2]
2°x(1,2) ，有
单点迭代法
将方程f(x)=0改写成等价形式
x=(x)
(1)
建立迭代公式
xk+1=(xk)
(2)
在根的附近任取一点x0，可得一序列

例如，对于求解非线性方程$f(x)=0$的 应用实例中需要注意选择合适的初始近
根，可以先选择一个初始近似解$x_0$， 似解和设置合适的精度要求，以确保算
然后按照弦截法的迭代过程逐步逼近方
法能够快速收敛到真实解。
程的真实解。
05 共轭梯度法
共轭梯度法的原理
它利用共轭方向的概念，通过迭代过程中不断更新搜 索方向，使得函数值逐渐减小，最终找到方程的解。
牛顿法的实现步骤
确定初始点x0，计算f(x0)和f'(x0)，如果f(x0)不等于0，则按照牛顿法的迭代公式 进行迭代，直到满足精度要求。
1. 选取初始点x0；2. 计算函数值f(x0)和导数值f'(x0)；3. 如果f(x0)不等于0，则 按照牛顿法的迭代公式x1=x0-f(x0)/f'(x0)进行迭代；4. 重复步骤2和3，直到满 足精度要求。
以求解非线性方程为例，通过选择合 适的迭代法和初值，可以有效地求解 非线性方程的近似解。
03 牛顿法
牛顿法的原理
01
基于函数f(x)的泰勒级数的前两项， 通过迭代的方式逼近方程f(x)=0 的解。
02
牛顿法的基本思想是通过泰勒级 数的近似，将非线性方程f(x)=0 转化为线性方程，然后利用线性 方程的解来逼近非线性方程的解。
当达到预设的迭代次数或满足一定的收敛 条件时，停止迭代，输出结果。
共轭梯度法的收敛性分析
共轭梯度法具有全局收敛性和局部收敛性，即只要初始点 选择得当，算法能够找到方程的解，且在局部范围内具有 快速收敛的特点。
收敛性分析主要涉及算法的迭代矩阵和函数的性质，如连 续性和可微性等。
共轭梯度法的应用实例
牛顿法的收敛性分析
在一定的条件下，牛顿法是收敛的， 且具有二阶收敛速度。

2.2 二分法
表2-2 计算结果
k
0 1 2 3 4 5 6 7
ak
1 1 1.25 1.25 1.3125 1.3125 1.3125 1.3203
bk
2 1.5 1.5 1.375 1.375 1.3438 1.3281 1.3281
xk
1.5 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242
ab ；否则，回 2
5.2 二分法
说明：
x*
(ⅰ)上述计算步骤（2）和（3）每执行一次就把新的区间分成两份，根的范围也 缩小一半. 如果第 k 次二分后得到的区间记 为 [ak , bk ]，根的近似值记为 xk ，则 ba (a b ) 有 bk ak k ， xk k k ，那么当时 k ， bk ak 0，这说明如果二分过 2 2 程无限继续下去，这些区间必将收敛于一点，即为所求根. (ⅱ) 第
3
2 f ( x ) 3 x 1 0, x [1, 2] 解 已知 f (1) 1 0, f (2) 5 0 且 ，
则方程
f ( x) x 3 x 1 0
在区间
(1, 2)
内只有一个实根.
当 k 1 ， x1
bk ak 102 ，继续二分；
2.1 引言
通常隔离区间的确定方法为 （1）作 y f ( x) 的草图, 由 y f ( x)与横轴交点的大致位置来确定； 或 者将 f1 ( x) f 2 ( x) 改写成 f ( x) 0 ， 根据 y f1 ( x) 和 y f 2 ( x) 交点横坐标来确定
根的隔离区间.
当 k 2 ， x2

方程根的数值计算步骤
判断根的存在 确定根的分布范围 根的精确化
计 根的存在定理(零点定理)：
f(x)为[a,b]上的连续函数，若 f(a)· f(b)<0，则 方 [a,b]中至少有一个实根。如果f(x)在[a,b]上还是单 法 调递增或递减的，则f(x)=0仅有一个实根。
算
计 算
根的分布范围:
k 1 k
方 法
取初值
x0 0
3 0
x1 2 x 1 1
x2 2x 1 3 ⇒
3 1
同样的方程
不同的迭代格式 有不同的结果
什么形式的迭代 法能够收敛呢? 如何构造迭代函 数呢?
x3 2 x 1 55
3 2
由此可见，这种迭代格式是发散的
若从任何可取的初值出发都能保证收敛，则称它 算 为大范围收敛。如若为了保证收敛性必须选取初值充 方 分接近于所要求的根，则称它为局部收敛。
h=(b-a)/n 其中n是正整数，在[a,b]内取定节点： xi=x0＋ih
(i=0,1,2，……，n)
计算f(xi)的值,依据函数值异号及实根的个数确 定隔根区间,通过调整步长，总可找到所有隔根 区间。
计 对于m次代数方程 f (x) = xm+am-1xm-1+ …+a1x+a0=0其根的 模的上下界有如下结论： 算 (1)若μ= max { |am-1| , ……, |a1| , |a0| }，则方程根的模小于μ+1 方 1 1 …… 法 (2)若ν= max {1， |am-1| , , |a1| },则方程根的模大于 1 a1 xk ε1
或
f ( x ) ε2
计 误差 分析： 算 方 法 第1步产生的

计 算
方 第二章 非线性方程的数值解法
法
王新年 大连海事大学信息工程学院
信号与图像处理研究所
计
算 简介（Introduction）
方
法我子们，知例道如在实际应用中有许多非线性方程的例
（1）在光的衍射理论（the theory of diffraction of light)中,我们需要求x-tanx=0的根
满足方程的x值通常叫做方程的根或解， 也叫函数f(x)=0的零点。
计 方程根的数值计算步骤
算 判断根的存在 方 确定根的分布范围 法 根的精确化
计 根的存在定理(零点定理)： 算 f(x)为[a,b]上的连续函数，若 f(a)·f(b)<0，则[a,b] 方 中至少有一个实根。如果f(x)在[a,b]上还是单调递 法 增或递减的，则f(x)=0仅有一个实根。
形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在 的子区间即为含根区间。
例如，求方程3x-1-cosx=0的隔根区间。
将方程等价变形为3x-1=cosx ，易见y=3x-1与 y=cosx的图像只有一个交点位于[0.5，1]内。
计 (2)逐步搜索法
算
方 运用零点定理可以得到如下逐步搜索法：
f’’(x)=sinx , f’’(0)=0;
f (3)(x)=cosx , f (3)(0)=1;
由定理1, x*=0是3重零点.
§2.1 对分区间法
计
(Bisection Method )
算
方
法
a
aax121 x*
xb2 bb1
停机条件（termination condition ）：
xk1 xk ε1 或 f ( x) ε2

解： 将方程化成等价形式
x 1 1 ex 5 10
此时，迭代函数 g ( x ) 1 1 e x。由于 f ( x ) e x 10 x 2 , 于是有 5 10
f (0 ) 1 0 , f (1) e 8 0
所以函数 f ( x )在区间 [0 ,1]内至少有一个根。
又由于 g ' ( x ) 1 e x ,当 x [0 ,1]时有： 10
表明，要使
，只x*要xn 1
1 1Lxn1xn
1.
因此，当取 (1时L，)由1 就能保证 x* xn 1.
xn1xn
2021/4/10
25
2021/4/10
26
***1***
2021/4/10
27
2021/4/10
***2***
28
2.2.5 迭代法的收敛阶
对非线性方程 f(x)=0 求解，我们可选取不同的迭代函数。 即使由这些迭代函数产生的迭代序列都收敛，它们也会有 快慢之分。如何反映迭代序列收敛的快慢呢？这就要引进 迭代法收敛阶的概念。
x*xn 11Lxn1xn.
（2.6) （证明见P25略）
2021/4/10
23
证：将满足方程的解的 相减，由所给条件并用
等式 x * g ( x * )与迭代格式 x n 1 g ( x n ) 微分中值定理可得
x * x n 1 g ( x * ) g ( x n ) g ' ( ) x * x n ， U ( x * , )。
2021/4/10
11
2021/4/10
12
五. 二分法的优缺点 1.二分法简单有效，它所对求方程根的函f 数 (x),
仅要求在有根区间上续连。