当前位置：文档之家› 第二章迭代法的一般原理

第二章迭代法的一般原理

非线性方程组无论从理论上还是计算方法上，都比线性方程组复杂得多。一般的非线性方程组很难求出解析解，往往只能求出其数值解，且往往只能借助于迭代法。本章我们将讨论迭代法的一般原理、迭代法的一般构造及迭代收敛速度的衡量标准。

2-1 迭代法与不动点定理

设n n R R D →?:f ，考虑方程

()0=x f (2-1)

若存在D *∈x ，使()0=*x f ，则称*x 为方程(2-1) 的解。

用迭代法求解(2-1) ，先将(2-1)化为等价的方程

()x g x = (2-2)

这里映象n n R R D →?:g 。

方程(2-2)的解*x (即()**x g x =)称为映象g 的不动点。因此用迭代法解方程(2-1)，就是求(2-2)中映象g 的不动点。这样以及g 是否存在不动点自然就是我们关心的问题。

定理2-1 若n n R R D →?:g 为有界闭集D D ?0上的严格非膨胀映象，()00D D ?g ，则g 在0D 内有唯一不动点。

证唯一性设g 在0D 内至少有两个不动点1x ，2x ，则

()()2121x x x g x g x x 21-≤-=-α

因1<α，所以由上式推得21x x =。唯一性得证。

记()()x g x x -=?，由g 及泛数的连续性可知1:R R D n →??连续。因0D 为有界闭集，故在0D 上有最小值。设0D *∈x 为最小点，即

()()x g x x -=∈min 0

D x *?

则*x 为g 的不动点。因为若不然，则有()**x g x ≠，再由g 严格非膨胀，可得

()()()()()***x g g x g x g -=?()()***x x g x ?=-<

这与*x 为的最小点相矛盾，故*x 为g 的不动点。

注定理中0D 的有界闭性、g 的压缩性和g 映0D 入自身，此3个条件缺一不可。例如，()x

x x g 1+=在[)+∞=,D 10上严格非膨胀，但它在0D 中却没有不动点。

下面我们介绍在应用上非常广泛的不动点定理。

定理2-2 (Brouwer 不动点定理) 设n n R R D →?:g 在有解闭凸集D D ?0上连续，且()00D D G ?，则g 在0D 至少有一个不动点。

本定理在一维情形下叙述为：[]b a f ,: []b a ,→则f 在[]b a ,中至少有一个不动点。几何解释见图2-1。

b a a

图2-1 一维Brouwer 定理

2-2 迭代格式的构造

前一节我们谈到，用迭代法求解方程(2-1)，是先将这个方程化为等价的方程(2-2)，然后求映象g 的不动点，通常(也是最简单的情形)构造如下迭代序列：

()k k x g x =+1, ,,,k 210= (2-3)

我们希望这个迭代序列{}k x 收敛到g 的不动点*x ，亦即方程()0=x f 的解。如果g 是压缩的，可望迭代序列收敛。图2-2展示了一维迭代收敛的一种情形。

对于(2-3)形式的迭代形式，g 可以有各种表示方式。g 可能只依赖于f 和f '。如果g 不依赖于迭代步k 只依赖于k x ，则称迭代(2-3)为单步定常迭代。如果迭代还依赖于迭代步k ，则迭代形式可表示为

()k k k x g x =+1, ,,,k 210= (2-4)

并称之为单步非定常迭代。有时得到新的近似1+k x 除依赖k x 外，还依赖前几次的得到信息，这时的迭代为多步迭代。例如，如获得1+k x 依赖于

11+--m k k k x ,,x ,x

则迭代可写为

x 021(x ) 图2-2 迭代序列收敛

()11,,+-+=m k k k x x g x (2-5)

称这种迭代为m 步迭代。类似地有m 步非定常迭代。

通常称g 或k g 为迭代函数。用不同的方法构造的迭代函数可得到不同的得到法。设n n R R D →?:g ，如果一个迭代法得到的序列{}

D k ?x 则称得到序列是适定的，适定性是迭代法的起码要求。

若D *∈x 是方程(2-1)的解，且序列{}k x 满足

*k k x x =∞

→lim 则称迭代序列收敛于*x 。

定义2-1 设n n R R D →?:f ，D *∈x 是方程()0=x f 的一个解。若存在*x 的一个邻域D S ?，使对任何初始值S ∈0x (对于m 步迭代法，初值为10,,-m x x S ∈)，迭代序列{}k x 总是适定的且收敛于*x ，则称*x 是迭代序列的吸引点。

不少迭代法都是设法使迭代函数g 是压缩的，这时迭代序列的吸引点恰是g 的不动点。有时候也可使g 具有某种单调性，构成单调单调法。

2-3 迭代法的收敛性与收敛阶

前面谈到，一个迭代法，当其产生的迭代序列在适定和收敛时才有意义。单步迭代格式(2-3)在实际中被采用得最多，这里，我们不加证明地给出三个与(2-3)格式有关的收敛性定理。

定理2-4 设*x 是方程()x g x =的解，n n R R D →?:g 。若存在一个开球S = ()D ,x S *?δ和常数()10,∈α，使得对一切S ∈x ，有

()()**x x x g x g -≤-α

(2-7)

则对任意S ∈0x ，*x 是迭代序列(2-3)的一个吸引点。

定理2-5 (Ostrowski) 设映象n n R R D →?:g 有一不动点()D *int ∈x ，且在*x 处F-可导，()

*x g '的谱半径(即特征值的最大模) ()()1<='σρ*x g (2-9)

则存在开球()D ,S S *?=δx ，对任意初值S ∈0x ，*x 是迭代序列的一个吸引点。

定理2-4与2-5都是指出迭代在解的小球中即解的充分小的邻域中收敛，这种收敛称为局部收敛，也就是说在已知方程(2-1)的解存在的情况下讨论的。如果在不知道方程(2-1)的解是否存在的情况下，只根据迭代初始近似0x 满足的条件就能证明迭代序列{} ,,k k 10=x 收敛到方程的解*x ，就称这种迭代法具有半局部收敛性。局部收敛性与半局部收敛性都要求初始近似0x 充分接近解*x ，这给实际计算带来很大的不便。如果一个迭代法对求解域D 中任一点0x 作为近似，迭代序列{} ,,k k 10=x 都能收敛到所求方程的解，这种收敛称为大范围收敛，这种收敛对实际计算很有意义。

对于定理2-5中的g 若是仿射的，即()b Ax x g +=，()n R L ∈A ，则条件(2-9) 变为()1

下面我们给出一个非常实用的判断迭代全局收敛的定理。

定理2-6设

(){}i i i n b x a x ,,x ,x D ≤≤= 21

这里i a ，i b ，(n ,,i 1=)为常数，映象n n R R D →?:g 具有一阶连续偏导数，()D D ?g 。若存在常数1

这里()x i g 为()x g 的第i 个分量函数，则迭代序列(2-3)对于任意初始近似D ∈0x 收敛于g 的不动点D *∈x ，并且有估计

∞∞--≤-*k *

k L L x x x x 11

对于一个迭代法，除了考虑其收敛性，研究其收敛速度对实际计算也是十分重要的。为了衡量收敛速度，我们这里引入收敛阶的概念。

定义2-2 设迭代序列{} ,,k k 10=x 收敛到*x ，如果存在1≥p 及常数0>α,使得当0k k ≥时有

p *k *k x x x x -≤-+α1 (2-13)

则称序列{}k x 至少p 阶收敛。当1=p 时(这时必须有10<<α)，称序列至少线性收敛。特别地，当2=p ，0>α称序列至少平方收敛。