数值计算课件——第二章非线性方程的数值解法

第二章 非线性方程的数值解法 对于非线性方程，由于f(x)的多样性，求其根尚无一 般的解析方法可以使用。 非线性方程求解的基本问题：根的个数；根的位置。 求解方程的根，一般有两种情形： 求出在给定范围内的某个根

求出方程的全部根，而根的数目和位置事先不知道 本章介绍几种方程求根的方法。这些方法大部分是要已 知根的范围，而且在此范围内只有一个根。

求非线性方程根的一些常用方法： 区间分割法(逐步搜索法、 二分法)

迭代法牛顿法

割线法

2.1区间搜索法预备知识： ① 方程的根：单根、重根。

定理 函数 f (x)对于x* 有f (x*) =0,但

f ( x* ) 0

则称 为方程的单根。如果有 f ( x* ) f ( x* ) f(m 1) ( x* ) 0但

f

( m)

(x ) 0*

,则称

x 是方程 的 m重根。

*

②

根的存在性定理：上必有一根；若 f 在[a, b]上连续且单调则 f 在 (a, b) 上有且仅有一根。

定理：若 f 在[a, b]上连续，且 f (a) ·f (b) < 0,则 f 在 (a, b)

2.1.1逐步搜索法例：求连续函数 f(x) 在有根区间[a,b]上的根。 思路：先把区间[a,b]均分为N等分，从初始值x0=a开始，步 长h=(b-a)/N来增值。每跨一步进行一次根的搜索。 计算速度慢，一般用于确定根的位置

2.1.2 二分法思路：二分法的基本思想 就是逐步对分区间,经过对根的搜 索，将有根区间的长度缩小到充分小，从而求出满足精度的 根 的近似值。

二分法

二分法的步骤： 在有根区间 a, b 取中点 值 a b ,若 f 2 a b f 0 2

x

0

1 a b ,计算函数 2x* a b 2

,就得到方程的实根

,

否则检查的根x * 在x0

f x0 与 f a 是否同号，如同号，说明待求

的右侧，这时令 a1 x0 , b1 b ;如 x * 在

x0

的左侧，这时令

a1 a, b1 x0,这样新的有根区间 a , b 1 1

的长度为 a, b 之半。a x a0 1 x* x1 b1

二分法

对压缩了的有根区间 a1 , b1 又可施以同样的手续，即用中点 x1 1 a1 b1 将区间 a1 , b1 分为两

半，然后判定待求的根

2

又确定一个新的有根区间 a2 , b2 ,其长度为 a1 , b1

x *在 x1 的哪一侧，从而

的一半。如此反复，即可得出一系列有根区间

a, b a1 , b1 ak , bk 其中 ak , bk 的长度bk ak 1 b a k 2

二分法

1 每次二等分后，设取有根区间的中点x k a k bk 2

作为根的近似值，则在二分过程中可以获得一个近

似根的序列 x0 , x1 , x2 , ,该序列以根 x *为极限。误差 分析：2 1 1 * 似值，则误差估计为： x xk bk

ak k 1 b a 2 2

若取区间的中点 x k 1 a k bk

作为 x * 的近

所以在实际计算时，只要二分足够多次，便

有 x * x 。这里，为预定精度。 k

二分法

对于给定的精度 ,可估计二分法所需的步数 k :b a ε k 1 2

l g b a l g ε k 1l g2

二分法特点： 优点：简单， 对f (x) 要求不高(只要连续即可) . 缺点：收敛慢( 1 等比级数)2

无法求复根及偶重根注：用二分法求根，最好先给出 f (x) 草图以确定根的大 概位置。或用搜索程序，将[a, b]分为若干小区间，对每一 个满足 f (ak)· f (bk) < 0 的区间调用二分法程序，可找出区 间[a, b]内的多个根，

求方程f(x)=0的根的二分法算法(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 e n dwh ile ; (4)输 出x 1 (a b). 2 [a , b] [a , x ]; [a , b] [ x , b].

2.22.2.1 2.2.2 2.2.3 2.2.4 迭代原理

简单迭代法

迭代的收敛性 迭代的收敛速度 迭代的加速

2.2 简单迭代法 2.2.1迭代法原理：f (x) = 0 f (x) 的根等价变换

x3 x 1 0 x 3 x 1 x 1 x3

x = φ (x) φ (x) 的不动点

从一个初值 x0 出发,计算 x1 = φ(x0), x2 = φ(x1), …, xk+1 = φ(xk), … 若 xk 收敛，即存在 x* 使得 思 lim x x * x k 1 lim x k, ,只要 φ 连续，则 lim 路 k k k k 也就是 x* = φ(x* ),即x* 是 φ 的根，也就是f 的根。 若{ xk}发散，则迭代 法失败。

xk+1 = φ(xk) 称为迭代格式， φ(x) 称为迭代函数 x0 称为迭代初值, 数列 x 称为迭代序列k

迭代法：是一种逐次逼近的方法。它是用某个 固定公式反复校正根的近似值，使之逐步精确，最后 得到满足精度要求的结果。 迭代法思想：将隐式方程 x =φ (x) 的求根问题归 结为计算一组显式xk+1 = φ(xk) ,也就是说，迭代过程是 一个逐步显式化的过程。

例题例2.2.1 试用迭代法求方程

f ( x) x3 x 1 0在区间(1,2)内的实根。

解：由 x 3 x 1 建立迭代关系

xk 1 3 xk 1 k=10,1,2,3…….计算结果如下:

例题

精确到小数点后五位x 1.32472

1 10 5 2

例题

但如果由 x x 3 1建立迭代公式xk 1 xk 13

k 1,2,...

仍取

x0 1.5,则有 x1 2.375, x2 12.39

显然结果越来越大， {x k } 是发散序列

简单迭代法的几何意义：把求方程 y ( x) f ( x ) 0 的根的问题， 转化为求 y x 两曲线

的交点问题，交点的横坐标就是

方程的根 x 。

*