发布时间 : 星期四 文章数学与应用数学毕业论文设计计算机科学中的重要数学思想—迭代更新完毕开始阅读051576c09e3143323968939e
计算机科学中的重要数学思想—迭代法
第一章 迭代法
1.1 迭代法简介
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代法常用于求方程或方程组的近似根。
1.2 运用迭代法的前提准备
一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件
- 4 -
第二章 不动点迭代法
2.1 不动点的寻找
我们先探讨不动点的存在性和介绍不动点迭代的方法。
定义2.1 函数g（x）的一个不动点是指一个实数P，满足P=g（P）。 定义2.2 迭代Pn+1=g(Pn),其中n=0，1，?称为不动点迭代 定理 2.1 g（x）为连续函数且?[a,b] 我们有
①g（x）?[a,b] 任意x?[a,b] 则g(x)一定有不动点 ②g?(x)?1 则g（x）不动点唯一
证明：①如果g（a）=a或g（b）=b，则为真；否则g（a）必须满足g（a）? ?a,b?,g(b)的值必须满足g（b）??a,b?。f（x）?x?g?x?有如下特性：f?a??a?g?a??0且f(b)?b?g(b)?0 对f(x)应用中值定理，而且由于常量L=0，可推断出存在数P?(a,b)满足f（p）?0。因此，P=g（P），且P为不动点。
②我们可以采用反证法。设存在两个不动点P1与P2.根据均值定理，可推断出存在数d?(a,b),满足 g?(d)?得g?(d)?g(p2)?g(p1)根据假设，有g(p1)?p1且g(p2)?p2，对前式子简化
p2?p1p2?p1?1。但这与题意矛盾，故得证P点唯一。 p2?p1下面我们给定一个定理来判断，迭代所产生的序列是收敛的还是发散的。
定理 2.2 设有
①g,g??C[a.b],②K是一个正常数，③p0?(a,b),④对于所有x??a,b?,有g(x)?[a,b]如果对于所有x?[a,b],有g?(x)?K?1,则迭代Pn=g(Pn-1)将收敛到唯一的不动点P ?[a,b].在这种情况下，P称为吸引不动点。如果对于所有
- 5 -
x?[a,b]，有g?(x)>1,则迭代将不会收敛到P，此时P点称为排斥不动
点。
我们可以证明定理中的吸引不动点。
证：首先要证明Pn都位于（a，b）内。从P0开始，可推导出存在
一个值C满足c0?(a,b)满足
c0?(a,b)P?p1?g(P)?g(p0)?g?(c0)(P?p0)?g?(c0)?KP?p0?P?p0(P?p0)因此，P1比P0更接近于P。同上可以归纳出Pn比
Pn-1更接近于P点。所以所有的点都在(a,b)中。
P?pn接下来证明。limn???0
?KnP?p0P?pn首先用数学归纳法证明可建立下面的不等式limn??0?limP?pn?limKnP?p0?0，P?pnn??n??。因此
的极限压缩在左右2边的0之间，
P?pn=0，这样就有limpn=p,，所以得证迭代Pn=g（Pn-1）收敛故limn??n??到不动点P
例题：设g(x)=0.5x?1.5，且P0=4，找去函数的不动点。
解：设迭代Pn?1?g(Pn)，由P0=4得 P1=3.5 P2=3.25 P3=3.125 ????
由此序列，不难得出P=3
2.2 绝对误差与相对误差
在迭代运算中，迭代结果与真实值间总存在误差，我们算误差方法分为：绝对误差
和相对误差 绝对误差：e?x*?x
- 6 -
相对误差：e?
x*?xx* （其中
x*为真实的结果，
x为迭代计算的结果）
- 7 -