数值分析2迭代法.doc

§2简单迭代法 ——不动点迭代(iterate) 迭代法是数值计算中的一类典型方法，被用于数值计算的各方面中。 一、简单迭代法 设方程 f(x)=0 (3) 在[a,b]区间内有一个根，把(3)式写成一个等价的隐式方程 x=g(x) (4) 方程的根代入(4)中，则有 (5) 称为ｇ的不动点（在映射ｇ下，象保持不变的点），方程求根的问题就转化为求(5)式的不动点的问题。 由于方程(4)是隐式的，无法直接得出它的根。可采用一种逐步显式化的过程来逐次逼近，即从某个[a,b]内的猜测值出发，将其代入(4)式右端，可求得 再以为猜测值，进一步得到 重复上述过程，用递推关系——简单迭代公式 (6) 求得序列。如果当k→∞时,就是逼近不动点的近似解序列，称为迭代序列。称(6)式为迭代格式，g(x)为迭代函数，而用迭代格式(6)求得方程不动点的方法，称为简单迭代法，当时，称为迭代收敛。 构造迭代函数g(x)的方法： 【例5】 考察 (1)，或更一般地，对某个； (2)； (3)。 取a=3,=2及根=1.732051，给出三种情形的数值计算结果见表 表 的迭代例子 K情形1 情形2 情形3 0 1 2 32.0 3.0 9.0 87.02.0 1.5 2.0 1.52.0 1.75 1.732143 1.732051问题：如何构造g(x)，才能使迭代序列一定收敛于不动点？误差怎样估计？ 通常通过对迭代序列的收敛性进行分析，找出g(x)应满足的条件，从而建立一个一般理论，可解决上述问题。 二、迭代法的收敛性 设迭代格式为 而且序列收敛于不动点，即 时） 因而有 (7) 由于 当g(x)满足中值定理条件时有 (8) 注意到(8)式中只要时，(7)式成立. 经过上述分析知道,迭代序列的收敛性与g(x)的构造相关,只要再保证迭代值全落在[a,b]内，便得： 【定理1】 假定迭代函数g(x)满足条件 映内性：对任意x∈[a,b]时，有a≤g(x) ≤b； 压缩性：g(x)在[a,b]上可导，且存在正数Ｌ1，使对任意 x∈[a,b]，有 （9） 则迭代格式对于任意初值∈[a,b]均收敛于方程x=g(x)的根，并有误差估计式 （10） 证明 ：收敛性是显然的。以下证误差估计???，因为 据此递推，可得 于是对任意正整数p,有 (11) 在上式中令p→∞，注意到，即得(10)式，定理证毕。 实际计算时可采用计算偏差方法来控制迭代次数。 对任意正整数p，有 (12) 令p→∞,则有 (13) 事后误差估计法终止条件：＜ε (14) 定理1的条件一般不易验证、不易满足。实际使用迭代法时，通常考虑在附近的收敛性－局部收敛性。 【定理2】 设在的邻近连续，且 (15) 则迭代过程在邻近具有局部收敛性。 证明： 因为连续，所在存在的一个邻域Ｒ：，使对任意x∈R,有 成立，并有 即对任意x∈R,有g(x)∈R,因此g(x)满足定理1条件,从而由定理1知,对任意∈R,迭代过程收敛. 证毕 三、计算机算法 步1,提供迭代初值; 步2,迭代计算; 步3,若,则转2,否则,root,转出口。 【例6】 求方程在x=0.5附近的一个根,要求精确到ε=。 解：有根区间为[0.5,0.6]。由于在根附近，选取g(x)＝时，迭代公式为 对初值＝0.5收敛。迭代值列于表 表 例迭代值 kkk0 1 2 3 4 5 60.5 0.6065306 0.5452392 0.5797031 0.5600646 0.5711721 0.56486297 8 9 10 11 12 130.5684380 0.5664094 0.5675596 0.5669072 0.5672772 0.5670673 0.567186314 15 16 17 180.5671188 0.5671571 0.5671354 0.5671477 0.5671407迭代18次时为所求根。 附算法程序： function y=iterate(x)