数值分析10-方程求根的迭代法.ppt

《数值分析10-方程求根的迭代法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章方程求根的迭代法高云方程求根需要考虑的问题求f(x)=0的根代数方程：f(x)=a0+a1x+...+anxn超越方程：f(x)含超越函数，如sin(x),ex,lnx等实根与复根根的重数f(x)=(x–x*)m·g(x)且g(x*)0,则x*为f(x)的m重根有根区间：[a,b]上存在f(x)=0的一个实根在有根的前提下求出方程的近似根。研究内容：迭代法的基本思想基本思路同解迭代公式给定初值存在等价于迭代函数？转换是否唯一几何意义转换例子(1)x=1(x)=x3-6x2+10x-2;(2);(3);(4);例：已知方程x3-6x2+9x

2、-2=0在[3,4]内有一根，考虑迭代？哪种转换方法好几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1压缩映像定理定理设(x)C[a,b]且可导，若(2)0L<1，使得

3、’(x)

4、L对x[a,b]成立(1)a(x)b对一切x[a,b]都成立则有(a)对任意x0[a,b]，由xk+1=(xk)产生的迭代序列均收敛到(x)在[a,b]中的唯一不动点x*。(b)有如下的误差估计可用

5、

6、xk+1-xk

7、来控制收敛精度L越小收敛越快压缩映像定理证明(a)由压缩映像定理可知，不动点x*存在且唯一。压缩映像定理证明(b)又全局收敛与局部收敛定理的条件保证了不动点迭代的全局收敛性。即迭代的收敛性与初始点的选取无关。这种在x*的邻域内具有的收敛性称为局部收敛性。定理中的条件

8、’(x)

9、L<1可以适当放宽(2’)’(x)在x*的某个邻域内连续，且

10、’(x*)

11、<1由’(x)的连续性及

12、’(x*)

13、<1即可推出：存在x*的某个邻域N(x*)=[x*-,x*+],使得对xN(x*)都有

14、’(x)

15、L<1,则由x0N(

16、x*)开始的迭代都收敛。迭代过程的收敛速度定义则称该迭代为r阶收敛。(1)当r=1时称为线性收敛，此时C<1；(2)当r=2时称为二次收敛，或平方收敛；(3)当r>1时称为超线性收敛。二分法线性收敛不动点迭代中，若’(x*)0，则取极限得(C为常数)线性收敛P阶收敛设迭代xk+1=(xk)，若(p)(x)在x*的某邻域内连续，则该迭代法具有p阶收敛的充要条件是定理并且有证明：充分性.根据泰勒展开有必要性的证明必要性.设迭代xk+1=(xk)是p阶收敛。迭代两边取极限，由(x)的连续性可知x*=(x*)。设p0是满足的最小正整数。由充分

17、性的证明过程可知迭代p0阶收敛。又若p0

18、*的某个邻域N(x*)=[x*-,x*+],使得对x0N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*。Newton迭代Newton法也可以看作一类特殊的加速迭代取(x)=x-f(x)收敛性定理定理设fC2[a,b]，且f满足(1)f(a)f(b)<0(2)对x[a,b]，f’(x)0且f”(x)0；(3)初始点x0[a,b]满足f(x0)f”(x0)>0；则Newton法产生的序列收敛到f在[a,b]的唯一零点x*。全局收敛性定理定理设fC2[a,b]，且f满足(1)f(a)f(b)<0(2)对x

19、[a,b]，f’(x)0且f”(x)0；则对任意初始点x0[a,b]，Newton法产生的序列收敛到f在[a,b]的唯一零点x*。(3)举例（一）例：设计一个二阶收敛算法计算(a>0)。解：转化为求x2-a=0的正根Newton迭代：二阶收敛mynewton.m重根情形设x*是f(x)的m(m2)重根，Newton法是否收敛？Taylor展式Newton迭代：线性收敛。且重数m越高，收敛越慢。提高收敛阶提高收敛速度但m通常无法预先知道！法一：取二阶收敛法二：将求f(x)的重根转化为求另一个函数的单根。构造针对(x)的具有二阶收敛的Newt

20、on迭代：令，则x*是(x)的单重根。降低初始点的要求例：求sin(x)-x/6=0的正根。mynewton.mNewt