4 非线性方程(组)的迭代解法.ppt

1、2020/7/2,1,非线性方程求根方法,若 n=1, 称为非线性方程求根问题； n1，称为非线性方程组求解问题。,理论问题： （1）解的存在性。即有解还是无解，有多少解。 （2）解的性态。即孤立解的区域，解的重数，光滑性。,关于解的存在性及其性态，不是数值分析所讨论的问题。我们总认为：,我们的任务是用数值方法求得满足一定精度要求的x*的近似解！,通常求其精确解是困难的,2020/7/2,2, 二分法,内容:, 一般迭代法, 牛顿迭代法,2020/7/2,3,1、二分法,设 在区间 上连续且有 ，则 在区间 内有解，不妨设解唯一！,算法构造原理:,有根区间,2020/7/2,4,x1,x2,a

2、,b,什么时候停止？,或,x*,算法停止的条件,2020/7/2,5,综合上述，得到如下算法，,(1),(2),(3),否则,(4),否则，转(2)；,例1,可得,共计算21次！,注：,其中 为精度控制参数!,2020/7/2,6,二分法只能求有根区间中的奇数重的实根;,关于二分法的讨论,(1),二分法线性收敛;,(2),二分法可用来细化有根区间，这是它的一大优点!,(3),故二分法可以用来确定迭代法的迭代初值!,返回主目录,2020/7/2,7,2、一般迭代法,(1),(2),(3),(一) 构造方法,(1),2020/7/2,8,例2,2020/7/2,9,1.5000 -0.8750 6

3、.7324 -69.7200 1.0275e+8 不收敛,1.5000 1.2870 1.4025 1.3455 1.3752 1.3601 1.3678 1.3639 1.3659 1.3649 1.3654 1.3651 1.3653 1.3652 1.3652,1.5000 0.8165 2.9969 0 -2.9412i 不收敛,1.5000 1.3484 1.3674 1.3650 1.3653 1.3652 1.3652,方法1,方法2,方法3,方法4,收敛与否，以及收敛快慢，取决于迭代函数,15次,6次,2020/7/2,10,(二) 大范围收敛定理,(1),(2),则,(1),

4、(2),(3),证明略！,即 是自映射；,2020/7/2,11,(三) 局部收敛定理,若,由迭代(1)产生的序列 ,注：,当定理条件成立时，,只要x0充分接近x*，就能保证迭代序列xn收敛于x*！,且有与前一定理完全相同的不等式成立！,2020/7/2,12,（四） 收敛阶（速度）的讨论,定义:,p=1 线性收敛；,p=2 平方收敛；,2p1 超线性收敛；,注：,满足局部收敛定理的简单迭代算法至少具有一阶收敛速度。,定理（简单迭代算法m阶收敛的充分条件）,设,在包含x*某个开区间内连续，,若,使得,则,注: 给出了提高收敛速度的方法!,由迭代 产生的序列 xn 以m阶收敛速度收敛到x* 。,

5、2020/7/2,13,例3,解：,迭代函数为,2020/7/2,14,迭代函数为,解：,#,返回主目录,2020/7/2,15,3、牛顿迭代算法,将f(x)在初值x0处做Taylor展开,取其线性部分做为f(x)的近似，有：,若,则有,记为,同理，我们可以得到,2020/7/2,16,这样一直下去，我们可以得到迭代序列,Newton迭代的迭代函数,(2), 牛顿迭代算法(切线法),收敛定理（单根的情形）,2020/7/2,17,应用举例,（1）,对于给定的正数C，应用牛顿法解二次方程 x2-C=0。,可得,可以证明上述迭代算法对任意初值 都收敛！,1）当x00时，收敛于 ；2）当x00时，收

6、敛于 ；,事实上，对（*）式进行配方可得,（*）,下面证明1），,1)得证!,2）,例4,2020/7/2,18,（2）,对于给定的正数C，应用牛顿法求解方程 。,可得,可以证明上述迭代算法对任意初值 都收敛于 ！,事实上，,从而,#,2020/7/2,19,牛顿迭代法的几点说明,牛顿迭代法算法简单，且局部收敛，但初值x0的选择困难！,(1),(2),牛顿迭代每步都要计算导数 ，增加了计算量！,(3),定理表明牛顿迭代求单根有效且平方收敛。,(一),一般来说采用试探法，可以结合二分法或通过做出函数图形来帮助选择初值！,关于初值,(二),导数的计算,(1),利用牛顿迭代法先计算几步，比如计算到了第k