数值分析3(不动点迭代)

1、1/25迭代法回顾迭代法回顾11-1-1111110.5(), () ()0()0.5(), () ()0nnnnnnnnnnxaf xf axxxbf xf b 如如果果如如果果二分法二分法: 设设f(x) = 0的根为的根为 x*,通过迭代计算产生序列通过迭代计算产生序列: 0101()()nnxxxxx *limnnxx 15:062/25设设f(x) = 0的根为的根为 x*,通过迭代计算通过迭代计算,产生序列产生序列: 迭代的思想迭代的思想0101()()nnxxxxx 迭代法研究包括方面迭代法研究包括方面: :迭代初值迭代初值迭代格式迭代格式判别收敛及收敛速度判别收敛及收敛速度*l

2、imnnxx 15:063/25数值分析3不动点迭代法不动点迭代法不动点迭代的收敛性不动点迭代的收敛性迭代序列的收敛速度迭代序列的收敛速度序列收敛加速方法序列收敛加速方法15:064/25引子引子 选择任意的数字选择任意的数字x。Matlab中输入命令中输入命令x=your number。例如。例如x = 3。 Matlab中输入命令中输入命令x=sqrt(1+x)。命令计算。命令计算(1+x)1/2并用最新的结果替代以前的结果。重复上并用最新的结果替代以前的结果。重复上述过程述过程(up-arrow键键), 得到如下结果得到如下结果: 3 2 1.7321 1.6529 1.6288 1.6

3、213 1.6191 1.6184 1.6181 1.6181 1.6180 1.6180 1.61805/25 Matlab中等号是赋值算子。即计算等式右边的中等号是赋值算子。即计算等式右边的值并将值存储到左边的变量。命令计算值并将值存储到左边的变量。命令计算(1+x)1/2并并用最新的结果替代以前的结果。重复上述过程得用最新的结果替代以前的结果。重复上述过程得到如下最后结果为到如下最后结果为1.6180(黄金比例黄金比例 )。 而数学中等号的意思有所不同。方程而数学中等号的意思有所不同。方程 的根称为函数的根称为函数 f(x)=(1+x)1/2的不动点。函数的不动点。函数f(x)有一个不动

4、点有一个不动点(1+(5)1/2)/2。1xx启示启示: 两种不同的思路计算方程的根两种不同的思路计算方程的根: 1) 寻寻找根的显式计算公式找根的显式计算公式; 2)通过重复简单的不通过重复简单的不动点计算并赋值来逐步逼近方程的解。动点计算并赋值来逐步逼近方程的解。6/25等价变换等价变换f (x) 的根的根的不动点的不动点不动点迭代不动点迭代(Fixed Point Iteration)对于对于f(x)=0, 不动点可以构造为不动点可以构造为:( )( )xxf x ( )( ) ( )xxx f x*()xx ( )x 1()nnxx x*称为不称为不 动点动点15:06*()0f x

5、7/25不动点迭代不动点迭代(Fixed Point Iteration)选择适当的初始值选择适当的初始值x0,按照如下的迭代格式计算按照如下的迭代格式计算:( )xx 1(), =0,1,2,nnxxn 如果数列如果数列xn有极限有极限 , 则称迭代是收则称迭代是收敛的。敛的。 是非线性方程的根和是非线性方程的根和 的不动点。的不动点。*x( )x *limnnxx 基本思想是将非线性方程求解归结为一系列显基本思想是将非线性方程求解归结为一系列显式的函数值计算。式的函数值计算。8/25例例1 方程方程 x3 + 4x2 10 = 0 在在 1, 2 上有一个上有一个根根, 构造求根的不动点迭

6、代格式。构造求根的不动点迭代格式。(1)10 /4xxx ( )10/4xxx 5 . 1)(01 xxxnn ( n = 0, 1, 2, )5 . 1)(01 xxxnn ( n = 0, 1, 2, )4/(10)( xx (2)4/(10 xx15:069/254101 nnxx 1.5000 0.8165 2.9969 (-8.65)1/2 0.5487 1.6317 0123n xn | xn x* | 1.5000 1.3484 1.3674 1.3650 1.3653 1.3652 1.3652 0.0168 0.0022 2.0e-04 1.0e-04 0 00123456n

7、 xn | xn - x* |110 /4nnnxxx 什么样的迭代格式收敛？什么样的迭代格式收敛？15:0610/25中值定理中值定理: 若函数若函数f(x) 满足满足:(i)在在a,b连续连续;(ii)在在(a,b)可导可导;则在则在 (a, b) 内至少存在一点内至少存在一点 ,使得使得 ( )( )( )f bf afba 15:0611/25*2.1( ) , (1) ( ) (2) |( )|1( ) , xabaxbxLxa bx 引引理理 如如果果在在上上具具有有连连续续的的一一阶阶导导数数且且满满足足条条件件和和 则则在在有有唯唯一一的的不不动动点点。证证 若若 或或 ,显然

8、显然 有不动点有不动点aa )( bb )( )(x 设设 , 则有则有 ,aa )( bb )( aa )( bb )( 记记 则有则有xxx )()( 0)()( ba 所以所以, 存在存在 x*使得使得即即 , 故故 x* 是是 的不动点。的不动点。0*)( x )(*xx )(x 15:0612/2515:0613/25如果如果 有两个不同的不动点有两个不同的不动点 则有则有)(x *2*1xx )(*1*1xx )(*2*2xx 两式相减得两式相减得)()(*2*1*2*1xxxx 由拉格朗日中值定理知由拉格朗日中值定理知, 存在存在 介于介于 和和 之间之间*1x*2x )()()

9、(*2*1*2*1*2*1xxxxxx *121212| |( )| |xxxxL xx 与与L1 条件矛盾条件矛盾故不动点唯一。故不动点唯一。15:0614/25证证 )()(*1xxxxnn | )(| )()(|*1*1*xxxxxxnnn |*1*xxLxxnn 15:060+1*12.2( ) , (1) ( ) (2) |( )|1 , ,(),1 |1nnnnnnxabaxbxLxa bxxxxxxxxL 引引理理 如如果果在在上上具具有有连连续续的的一一阶阶导导数数且且满满足足条条件件和和。则则对对任任意意的的迭迭代代格格式式产产生生的的序序列列收收敛敛到到不不动动点点且且满满

10、足足压缩映像压缩映像15/25|*0*xxLxxnn0|lim|lim*0* xxLxxnnnn( 0L0 , p0 使得使得1|*|lim|*|npnnxxaxx 则称数列则称数列xn p 阶收敛。阶收敛。特别特别: (1) 收敛阶收敛阶p =1时时,称为线性收敛称为线性收敛; (2) 收敛阶收敛阶p 1时时,称为超线性收敛称为超线性收敛; (3) 收敛阶收敛阶p =2 时时,称为平方收敛。称为平方收敛。序列的收敛阶数越高序列的收敛阶数越高, 则收敛速度越快。则收敛速度越快。18/251*()( *)( )(*)nnnxxxxxx 1|*|lim|( *)| 0|*|nnnxxxxx 15:

11、0621(1)()1( *)*()( *)( *)(*)(*)2( *)( ) +(*)(*)(1)!nnnnppppnnxxxxxxxxxxxxxxxpp 19/25定理定理2.6 设设x*是是 的不动点的不动点,且且)(x0*)(*)(*)()1( xxxp 而而 则则 p阶收敛阶收敛0*)()( xp )(1nnxx | )(|!|*|*)()(|*|)(1nppnnnpxxxxxx 由由Taylor公式公式其中其中, 介于介于xn和和x*之间之间. 所以所以n |*)(|!1| )(|lim!1|*|*|lim)()(1xppxxxxpnpnpnnn 故迭代法故迭代法p阶收敛。阶收敛。

12、15:0620/25例例2 用不同迭代格式求方程用不同迭代格式求方程 x2-3=0的根。的根。214( )(3)xxx (a)*3122()1, ()10.1341xxx 则则312( )()xxx (b)2*312()(1), ()0 xxx 则则2( )3xxx (c)*()21, ()2311xxx 则则( )3 /xx (d)*()1x 则则21/25xk(a)(b)(c)(d) x02222 x11.75001.750031.5000 x21.7344 1.732192 x31.73241.7321871.5000 x4 1.73211.73217653222/25*lim()nnx

13、x 0101()()nnxxxxx 不动点框架不动点框架:15:06收敛性收敛性 收敛速度收敛速度(1)()( *)( *)( *)0 ( *)0ppxxxx |( )| 1x 23/25 Everyone loves a good cup of coffee, mathematicians especially. But did you know there is a beautiful pure mathematics theorem at work every time you make yourself a mug of that deliciously addictive stuff

14、? 一个数学家就是一台把咖啡转化为数学定理的机器。一个数学家就是一台把咖啡转化为数学定理的机器。 P. Erdos24/25 Brouwers Fixed Point Theorem says precisely “every continuous function from a compact subset in n-dimensional Euclidean space to the same subset has a fixed point”. Well take your mug and fill it up with coffee, give it a good old stir and then let it come to rest again. This theorem guarantees that there is at least one point in the cup (what we call the “fixed point”) that ends up in the exact same position as the position it started in.25/25Aitken加速方法加速方法(松弛思想松弛思想)21112()2nnnnnnnxxy