Ch7 非线性方程与方程组的数值解法

第7章 非线性方程与方程组的数 值解法 7.1 方程求根与二分法

7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 非线性方程组的数值解法1

引言例如代数方程 超越方程 x5-x3+24x+1=0, sin(5x2)+e-x=0.

对于不高于4次的代数方程已有求根公式，而 高于4次的代数方程则无精确的求根公式，至于超 越方程 就更无法求出其精确的解，因此，如何求

得满足一定精度要求的方程的近似根也就成为迫切需要解决的问题，为此，本章介绍几种常见的

非线性方程的近似求根方法.2

主要讨论单变量非线性方程 f(x)=0 (1.1) 的求根问题，这里x∈R, f(x)∈C[a, b]. 在科学与工程 计算中有大量方程求根问题，其中一类特殊的问题 是多项式方程

f ( x) a0 x n a1 x n 1 an 1 x an (a0 0), (1.2)其中系数ai(i=0,1, ,n)为实数.

方程f(x)=0的根x*,又称为函数f(x)的零点，它使得 f(x*)=0,若f(x)可分解为 f(x)=(x-x*)mg(x), 其中m为正整数，且g(x*)≠0. 当m=1时，则称x*为单 根，若m>1称x*为(1.1)的m重根，或x*为函数f(x)的m 重零点. 若x*是f(x)的m重零点，且g(x)充分光滑，则

f ( x ) f ( x ) f ( m 1 ) ( x ) 0 , f ( m ) ( x ) 0 .当f(x)为代数多项式(1.2)时，根据代数基本定理 可知，n次代数方程f(x)=0在复数域有且只有n个根(含 复根，m重根为m个根).4

n=1,2时方程的根是大家熟悉的，n=3,4时虽有求 根公式但比较复杂，可在数学手册中查到，但已不适 合数值计算，而n≥5时就不能用公式表示方程的根.因 此，通常对n≥3的多项式方程求根与一般连续函数方 程(1.1)一样都可采用迭代法求根.

迭代法要求给出根x*的一个近似，若f(x)∈C[a, b] 且f(a)f(b)<0,根据连续函数性质中的介值定理可知方 程f(x)=0在(a, b)内至少有一个实根，这时称[a, b]为方 程(1.1)的有根区间.例1 判断方程 f(x)=x3-x-1=0的有根区间.x f(x) 0 0.5 1 1.5 + 2 +5

7.1 方程求根与二分法设f(x)在区间[a, b]上连续, f(a)· f(b)<0, 则在[a, b] 1 内有方程的根. 取[a, b]的中点 x0 (a b ) , 2 将区间一分为二. 若 f (x0)=0, 则x0就是方程的根,否则判别根 x*在 x0 的左侧还是右侧.

若 f(a) · f(x0)<0, 则x*∈(a, x0), 令 a1= a, b1=x0;若f(x0) · f(b)<0, 则x*∈(x0 , b), 令 a1=x0, b1=b. 不论出现哪种情况, (a1, b1)均为新的有根区间, 它 的长度只有原有根区间长度的一半, 达到了压缩有根 区间的目的.6

对压缩了的有根区间, 又可实行同样的步骤, 再压 缩. 如此反复进行, 即可的一系列有根区间套[a , b] [a1 , b1 ] [an , bn ]

由于每一区间都是前一区间的一半，因此区间 [an , bn]的长度为

1 bn an

n (b a ) 2 若每次二分时所取区间中点都不是根，则上述过程将无限进行下去. 当 n→∞ 时，区间必将最终收缩为一 点x* ,显然x*就是所求的根.7

When to stop?a x a0 x*

x2 b

b

xk 1 xk ε1

或

f ( x ) ε2不能保证 x 的精度

2x* x

若取区间[an , bn]的中点 1 xn ( an bn ) 2 作为x*的近似值，则有下述误差估计式

1 1 * x xn ( bn an ) n 1 ( b a ) 2 2x* , xn ( an 1 , bn 1 )只要 n 足够大, (即区间二分次数足够多),误差就可 足够小. 由于在偶重根附近曲线 y=f(x) 为上凹或下凸, 即 f(a)与f(b)的符号相同, 因此不能用二分法求偶重根.9

例2 用二分法求例1中方程 f(x)=x3-x-1=0的实根, 要求误差不超过0.005.

解 由例1可知x*∈(1, 1.5), 要想满足题意，即：|x*-xn|≤0.005 则要

1 2n 1

(b a)

1 2n 1

(1.5 1)

1 2n 2

0.005

2 由此解得 n 1 5.6, 取n=6, 按二分法计算过程见 lg 2 下表, x6 = 1.3242 为所求之近似根.

n 0 1 2 3 4 5 6

an 1.0 1.25 1.25 1.3125 1.3125 1.3125 1.3203

bn 1.5 1.5 1.375 1.375 1.3438 1.3281 1.3281

xn 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242

f(xn) + + + -

说明 (1) f(a)<0, f(b)>0 (2) 根据精 度要求，取 到小数点后 四位 即可.

二分法的优点是算法简单，且总是收敛的，缺 点是收敛的太慢，故一般不单独将其用于求根，只 是用其为根求得一个较好的近似值.11

逐步搜索法从区间[a, b]的左端点 a 出发, 按选定的步长h

一步步向右搜索，若f(a+jh)· f(a+(j+1)h)<0 (j=0,1,2, )

则区间[a+jh, a+(j+1)h]内必有根. 搜索过程也可从b开

始，这时应取步长 h<0.

7.2 不动点迭代法及其收敛性7.2.1 不动点迭代法

将方程f(x)=0改写为等价方程形式 x= (x).

(2.1)

若要求x*满足f(x*)=0,则x*= (x*);反之亦然，称x*为 函数 (x)的一个不动点. 求f(x)的零点就等于求 (x)的 不动点，选择一个初始近似值x0,将它代入(2.1)右端， 即可求得 x1= (x0).

可以如此反复迭代计算 xk+1= (xk) (k=0,1,2, ).

(2.2)

(x)称为迭代函数. 如果对任何x0∈[a, b],由(2.2)得到的序列{xk}有极限

lim x k x .k

则称迭代方程(2.2)收敛. 且x*= (x*)为 (x)的不动点， 故称(2.2)为不动点迭代法.

xk 1 ( xk )k

( k 0,1, 2, )

lim x k x .当 (x)连续时，显然x*就是方程x= (x)之根(不动点). 于是可以从数列{xk}中求得满足精度要求的近似根. 这种求根方法称为不动点迭代法,

xk 1 ( xk ) ( k 0,1, 2, ) 称为迭代格式, (x)称为迭代函数, x0 称为迭代初值,数列{xk}称为迭代序列. 如果迭代序列收敛, 则称迭代格式收敛,否则称为发散. (几何意义的解释见下 页)15

y p1 p0

y=x

y p0

y=x

x0 y

x1 x* y=x x x0 y p0 p0 p1 x1 x0 x* x x0 x* x*

p1 x x1 y=x

p1

x16

x1

例1 用迭代法求方程x4+2x2-x-3=0 在区间[1, 1.2]内的实根.解 对方程进行如下三种变形：

x 1 ( x) (3 x

1 2 x 2 )4

x4 2x2 x 3 0 x 2 ( x) 4

x 4 12

x 3 ( x) x 2x 3分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：

xk 1 1 ( xk ) (3 xk 2 x )

1 2 4 k

x26 x27 1.124123 x6 x7 1.124123

x k 1 2 ( x k ) 4 k

xk 4 12 k

xk 1 3 ( xk ) x 2 x 3 x3 96, x4 8.495307 107

准确根 x* = 1.124123029, 可见迭代公式不同, 收敛情 况也不同. 第二种公式比第一种公式收敛快得多, 而

第三种公式不收敛.18

当方程有多个解时，同一个迭代法的不同初值也可能收敛到不同的根.