第二章 迭代法的一般原理.doc
第二章 迭代法的一般原理非线性方程组无论从理论上还是计算方法上，都比线性方程组复杂得多。一般的非线性方程组很难求出解析解，往往只能求出其数值解，且往往只能借助于迭代法。本章我们将讨论迭代法的一般原理、迭代法的一般构造及迭代收敛速度的衡量标准。2-1 迭代法与不动点定理设，考虑方程(2-1)若存在，使，则称为方程(2-1) 的解。用迭代法求解(2-1) ，先将(2-1)化为等价的方程(2-2)这里映象。方程(2-2)的解(即)称为映象g的不动点。因此用迭代法解方程(2-1)，就是求(2-2)中映象g的不动点。这样以及g是否存在不动点自然就是我们关心的问题。定理2-1 若为有界闭集上的严格非膨胀映象，则g在内有唯一不动点。证 唯一性 设g在内至少有两个不动点，则因，所以由上式推得。唯一性得证。记，由g及泛数的连续性可知连续。因为有界闭集，故j在上有最小值。设为最小点，即则为g的不动点。因为若不然，则有，再由g严格非膨胀，可得这与为j的最小点相矛盾，故为g的不动点。注 定理中的有界闭性、g的压缩性和g映入自身，此3个条件缺一不可。例如，在上严格非膨胀，但它在中却没有不动点。下面我们介绍在应用上非常广泛的不动点定理。定理2-2 (Brouwer不动点定理) 设在有解闭凸集上连续，且，则g在至少有一个不动点。本定理在一维情形下叙述为： 则f在中至少有一个不动点。几何解释见图2-1。xybaab图2-1 一维Brouwer定理2-2 迭代格式的构造前一节我们谈到，用迭代法求解方程(2-1)，是先将这个方程化为等价的方程(2-2)，然后求映象g的不动点，通常(也是最简单的情形)构造如下迭代序列：,(2-3)我们希望这个迭代序列收敛到g的不动点，亦即方程的解。如果g是压缩的，可望迭代序列收敛。图2-2展示了一维迭代收敛的一种情形。xx0x2x1yy = g(x)图2-2 迭代序列收敛对于(2-3)形式的迭代形式，g可以有各种表示方式。g可能只依赖于f和。如果g不依赖于迭代步k只依赖于，则称迭代(2-3)为单步定常迭代。如果迭代还依赖于迭代步k，则迭代形式可表示为,(2-4)并称之为单步非定常迭代。有时得到新的近似除依赖外，还依赖前几次的得到信息，这时的迭代为多步迭代。例如，如获得依赖于则迭代可写为(2-5)称这种迭代为m步迭代。类似地有m步非定常迭代。通常称g或为迭代函数。用不同的方法构造的迭代函数可得到不同的得到法。设，如果一个迭代法得到的序列则称得到序列是适定的，适定性是迭代法的起码要求。若是方程(2-1)的解，且序列满足则称迭代序列收敛于。定义2-1 设，是方程的一个解。若存在的一个邻域，使对任何初始值(对于m步迭代法，初值为 )，迭代序列总是适定的且收敛于，则称是迭代序列的吸引点。不少迭代法都是设法使迭代函数g是压缩的，这时迭代序列的吸引点恰是g的不动点。有时候也可使g具有某种单调性，构成单调单调法。2-3 迭代法的收敛性与收敛阶前面谈到，一个迭代法，当其产生的迭代序列在适定和收敛时才有意义。单步迭代格式(2-3)在实际中被采用得最多，这里，我们不加证明地给出三个与(2-3)格式有关的收敛性定理。定理2-4 设是方程的解，。若存在一个开球S = 和常数，使得对一切，有(2-7)则对任意，是迭代序列(2-3)的一个吸引点。定理2-5 (Ostrowski) 设映象有一不动点，且在处F-可导，的谱半径(即特征值的最大模)(2-9)则存在开球，对任意初值，是迭代序列的一个吸引点。定理2-4与2-5都是指出迭代在解的小球中即解的充分小的邻域中收敛，这种收敛称为局部收敛，也就是说在已知方程(2-1)的解存在的情况下讨论的。如果在不知道方程(2-1)的解是否存在的情况下，只根据迭代初始近似满足的条件就能证明迭代序列收敛到方程的解，就称这种迭代法具有半局部收敛性。局部收敛性与半局部收敛性都要求初始近似充分接近解，这给实际计算带来很大的不便。如果一个迭代法对求解域D中任一点作为近似，迭代序列都能收敛到所求方程的解，这种收敛称为大范围收敛，这种收敛对实际计算很有意义。对于定理2-5中的g若是仿射的，即，则条件(2-9) 变为，它是用迭代法解线性方程组的收敛的充分必要条件，而对非线性方程组而言，条件(2-9) 仅为迭代(2-3)局部收敛的充分条件，这是线性和非线性的不同之处。下面我们给出一个非常实用的判断迭代全局收敛的定理。定理2-6设这里，()为常数，映象具有一阶连续偏导数，。若存在常数满足(2-10)这里为的第i个分量函数，则迭代序列(2-3)对于任意初始近似收敛于g的不动点，并且有估计对于一个迭代法，除了考虑其收敛性，研究其收敛速度对实际计算也是十分重要的。为了衡量收敛速度，我们这里引入收敛阶的概念。定义2-2 设迭代序列收敛到，如果存在及常数,使得当时有(2-13)则称序列至少p阶收敛。当时(这时必须有)，称序列至少线性收敛。特别地，当，称序列至少平方收敛。如果“一收敛序列至少是p阶收敛的” 这一结论对都成立，而对都不成立，则称这个序列的收敛阶是。
