1. 不动点和不动点迭代法

设 f                             是连续函数，为了解方程

把方程变换为等价的方程

其中φ 是连续函数。若x* 是f 的零点，即f(x*)=0 则有

x*称为函数φ 的一个不动点.构造的迭代法

这称为一种不动点迭代法， 称为迭代函数。由(1.3)式产生的序列 {xk}如果满足 ,

则 x*是φ的一个不动点。即方程(1.1)的一个根。

2.函数在区间上不动点的存在性和唯一性及推论

定理 2.1    设 φ∈C[a,b]且满足

则 φ 在[a,b] 上一定存在不动点。若φ 满足(2.1),又存在常数L∈(0,1) 使

则φ 在[a,b] 的不动点是唯一的。

条件 (2.2)称为Lipschitz条件，L称为Lipschitz常数。

定理 2.1的推论 设函数φ满足(2.1)，又 φ'∈C[a,b]，且存在常数L∈(0,1) ，使

则φ 在[a,b] 上存在唯一的不动点。

3.迭代法在区间[a,b]的收敛性  

定理3.1    设φ∈C[a,b]，满足条件(2.1)和(2.2),其中L∈(0,1)。则对任意的x0∈[a,b]，由迭代法(1.3) 产生的序列{xk}收敛到φ在[a,b]上的不动点x* ,而且对整数P≥1，

定理3.1描述了对任意的x0∈[a,b]，{xk}收敛到[a,b]唯一的不动点x*，这可以说是在区间[a,b]上的全局收敛性。

局部收敛性

定义 设函数φ在区间[a,b]上有不动点x* , 如果存在x*的一个邻域

对任意的 x0∈S，迭代法(1.3)产生的序列{xk}∈S，且{xk}收敛到x*，就称迭代法(1.3)局部收敛。

定理3.2   设 x*为函数φ 的不动点， 在φ'在x*的某个邻域上存在且连续，且

则迭代法(1.3)局部收敛。

4.牛顿迭代法

设x*是f的零点，并已有一个近似值xk≈x*，如果f''存在且连续，由Taylor展开式得

         ,       

其中ξ在xk和x*之间。因为f(x*)=0，如果f'(xk)≠ 0，略去最后一项即得

.                        

这就是Newton迭代法，又称Newton-Raphson迭代法。

牛顿迭代法的局部收敛性

Newton迭代法对应的迭代函数是

定理4.1    设f(x*)=0 ，f'(x*)≠ 0，且f在包含x*的一个区间上有二阶连续导数，则牛顿迭代法(4.2)局部收敛到x* 。

练习题：设 a＞0, 求平方根

可以转化为解方程

求迭代公式及迭代公式在(0,+∞)上的全局收敛性。并和二分法比较。

练习题解答请参考：点击打开链接

5.参考文献

最优化理论与算法(第二版).陈宝林编著.

原文出处