南京大学计算机科学与技术系 数值计算方法(第2章) 非线性方程与方程组的数值

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

本章重点介绍求解非线性方程 f ( x) 0的几种常见和有效的数值方法,同时也对非线性方程组

fi ( x1 , x2 , , xn ) 0

(i 1,2, , n)

求解,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突 破性开拓和补充,许多问题的求解,在解析方法无能为力 时,数值方法则可以借助于计算机出色完成.

2.1二分法 求非线性方程 分为两步：f ( x) 0 的根的方法

确定方程的有根区间计算根的近似值

首先确定有限区间：依据零点定理。 设 f ( x) C[a, b] ,且 f (a) f (b) 0 , 则方程 f ( x) 0 在区间 (a, b)上至少有一个根。 如果 一。 在( x) f' 上恒正或恒负，则此根唯 ( a, b)

等步长扫描法求有根区间

用计算机求有根区间：等步长扫描法。 设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 ,已算出方程的一个根，停 机。

等步长扫描算法

(5) 若 f 0 f1 0 。输出 a, x,[a, x] 为有根区间， 停机 (6) a x ,转 3) 注：如果对足够小的步长h扫描失败。 说明：

在 [a, b] 内无根 在 [a, b] 内有偶重根

二分法

用二分法(将区间对平分)求解。令 a1 a, b1 b, c1 1 (a1 b1 ) 2 若 f (a1 ) f (c1 ) 0 ,则 [a1 , c1 ]为有根区间，否 则 [c1 , b1 ]为有根区间 记新的有根区间为 [a 2 , b2 ] , 则[a1 , b1 ] [a 2 , b2 ]

且

b2 a2 1 (b1 a1 ) 2

二分法

对 [a 2 , b2 ] 重复上述做法得[a1 , b1 ] [a2 , b2 ] ...... [an , bn ] ......

且bn a n 1 2n 1

(b a )

二分法 设 所求的根为 x , 则 x [an , bn ] n 1,2......

即

an x bn

n 1,2......

lim (bn a n ) limn

1 2n 1

n

(b a) 0

取

lim an lim bn x n n

1 x cn (a n bn ) 为 2

x 的近似解

求方程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)令x 2)if 1 ( a b), 计算f ( x ); 2 f (a) f ( x) 0 then else endwhile; ( 4)输出x 1 ( a b). 2 [ a, b] [ a, x]; [ a, b] [ x, b].

求方程f(x)=0的全部实根的二分法算法(1) ( 2) 输入 : a

, b, h, ; a1 a; b1 a1 h; b1 b时做 f ( a1 ) f (b1 ) 0做a1 a; b1 a1 h;

(3) while 1) while

endwhile; 2) while | b1 a1 | 时做 10

1 x ( a1 b1 ); 计算f ( x ); 2

求方程f(x)=0的全部实根的二分法算法20 30 if if f ( x) 0转(3); f (a1 ) f ( x) 0 then else endwhile; 3)输出 : x; a1 x endwhile; h ; b1 a1 h; 10 [a1 , b1 ] [a1 , x] [a1 , b1 ] [ x, b1 ].

例题

例1 设方程

f ( x) x 3 x 1, [a, b] [1,2]

解：取h=0.1,扫描得：f (1.3) 0.61 0 f (1.4) 0.344 0

方程的有根区间为1.3,1.4]. [

又 f ' ( x) 3x 2 1 0, x [1.3,1.4] 即 f ( x) 0在 [1.3,1.4]有唯一根。

2.2一般迭代法

2.2.1 迭代法及收敛性对于 f ( x) 0 有时可以写成 x (x) 形式 如： x 3 x 1 0 x 3 x 1x 1 x3

x cos x 0 x cos x

迭代法及收敛性

考察方程 x (x) 。这种方程是隐式方 程，因而不能直接求出它的根，但如果 x 给出根的某个猜测值 x 0 , 代入 (x) 中 的右端得到 x1 ( x0 ) ,再以 x1为一个猜 测值，代入 x (x) 的右端得 x2 ( x1 )反复迭代得 xk 1 ( xk )k 0,1,......