逐步逼近法

逐步逼近法是最基本也是最重要的数学方法. 第一章我们曾谈到了“穷竭法”. 阿基米德称用“穷竭法”计算出球的体积之外，还用一系列抛物线内接三角形面积之和来逼近抛物线拱形面积.我国魏末晋初的数学家刘徽用一系列圆内接正多边形的周长或面积来逼近圆的周长或面积，创造了“割圆术”. 其数学成就位于世界前列.

微积分中用定积分来求曲边梯形的面积，实质上还是用一系列矩形面积之和去逼近曲边梯形的面积，这种方法虽然古老，但却是现代严格极限理论的基础. 逐步逼近是贯穿数学分析的一条基本线索: 实数理论是用有理数逼近无理数、极限理论中的闭区间套和单调有界原理、微分学中用平均变化率逼近瞬时变化率、积分学中用有限和逼近无限和、级数理论中用多项式逼近函数等，都是各种方式的“逐步逼近”.

4.2.2 递推法

形如

an+p=F(n，an，an+1，…，an+p-1)

的关系式，使得当已知序列a1，a2…的最初p项时，就可以算出它所有的项，我们称为递推关系. 一个与自然数有关的数学问题，当某些初始值确定之后，通过递推关系获得全部解决，这种方法称之为递推法. 这个方法是探索数学规律和解题思路的重要方法之一，它在各个数学分支几乎都有重要作用.

递推关系是从很多计数问题中自然产生的，也是递推思想的数学描述. 比如，要求回答: 平面上有n条直线，其中任意两条不平行，任意三条不共点，问这n条直线把平面要成多少个区域? 显然，这n条直线把平面分成的区域数，是由n决定的，是n的函数，记为f(n)，其定义域和值域都属于自然数集N. 设平面被n条直线划分的区域为f(n)，易知f(1) =2，f(2) =4，f(3) =7，f(4) =11. 前面两项容易理解. 当n=2时，即有两条直线l1， l2相交于A1点，这两条相交直线把原来的两区域又分为两部分，即f(2) =f(1) +2，当n=3时，原来两条直线把所添的直线l3分成三段，每一段又把所在的区域分成两部分，即增加3区域，即有f(3) =f(2) +3.

有了前面几项，就可以作递推了，当n=k时，是在n=k-1的基础上作直线lk，与l1，l2，…，lk-1，分别相交于A1，A2，…， Ak-1点，这k-1个点又把lk分成k段，每一段把所在区域分成两部分，即增加了k部分，因而

f(k) =f(k-1) +k (4.5)

有了关系式(4.5)，即可进行计算.

因 f(k) =f(k-1) +k，令k=1，2，…，n，有

f(1) =2

图4.5

f(2) =f(1) +2

f(3) =f(2) +3



f(n) =f(n-1) +n

将上述n个等式两边相加化简

f(n) =2+2+3+…+n

=1+(1+2+3+…+n)

=(n2+n+2)

递推法的计算是逐步递进的，先求f(0)的值，再由f(0)的值求出f(1)的值，再由f(1)的值求出f(2)的值，…，在数学上就叫递推.

递推的例子很多，著名的裴波那数列就可用下列递推公式计算:

F(0) =1，F(1) =1.

F(n) =F(n-1) +F(n-2) (n＞1) (4.6)

由式(4.6)可以算出

F(2) =2，F(3) =3，F(4) =5，F(5) =8.F(6) =13，….

设a1，a2，…，an是n个不同的元素，从这n个不同元素中取出k个不重复的组合数为

是一个递推关系，用数学归纳法可以证明

式(4.8)就是式(4.7)的解.

如果用f(n，k)表示n个不同元素a1，a2，…，an的k个可重复的组合数，f(n，k)的递推关系可以分两种情况来思考: 第一种是包含an的k元重复组合，它的总数应是f(n，k-1); 第二种是不包含an的k元重复组合，它的总数应是f(n-1，k)，于是，递推关系式是

f(n，k) =f(n，k-1) +f(n-1，k) (4.9)

显然，对任何正整数n来说有 f(n，1) =n，而f(1，k) =1，反复运用式(4.9)

f(n，2) =f(n，1) +f(n-1，2) =…

=f(n，1) +f(n-1，1) +…+f(2，1) +f(1，2)

=n+(n-1) +…+2+1

即

由上式递推

式(4.10)是式(4.9)的解.

由前面论述可知，建立递推关系需要认真分析，求解则需要认真综合. 总之，必须先建立某种递推关系，再据关系求解. 求解递推关系的方法很多，上述两例用的是列举累加法.

为要求数列a1=1，an+an+1=-3n的通项，把递推关系变形为

即

亦即

令

所以

an=bn-(1-(-1)n)-，即为所求通项公式. 这个方法称为辅助数列法.

如果数列{an}，成立关系an+1=pan+qan-1(n=2，3…)，其中p，q为常数. 可设α，β为二次方程x2-px-q=0的两个根，则数列{an+1-αan}是以β为公比的等比数列(读者试证之).

对于裴波那契数列，考虑方程x2-x-1=0两根

数列{an+1-αan}是公比为β的等比数列，由于首项为a2-αa1=1-α=β，故有

an+1-αan=βn　①

互换α与β的位置，从而数列{an+1-βan}是首项α，公比为α的等比数列，故有

an+1-βan=αn　②

①-②得 (β-α)an=βn-αn，又因β-α=

所以

即

这种求通项的方法，叫做特征方程法.

特征方程法，在解常系数齐次线性微分方程中也很有用.

以二阶齐次线性微分方程为例:

y″+py'+qy=0 (4.11)

如果p，q全为常数，称为齐次线性微分方程，否则为二阶变系数齐次线性微方程. 求解二阶常系数微分方程的通解步骤是:

(1)写出微分方程的特征方程 r2+pr+q=0;

(2)求出特征方程的两根r1，r2;

(3)根据特征方程两根的情况，按照表4-1得出微分方程的通解.

表4-1

下面介绍差分方程法. 先看乘积数列.

例4.12 求Sn=(1·2+2·3+…+n(n+1).

上面的过程看似简单，若不熟悉第一项的来源，这个问题就会搁浅. 这里介绍一个差分方程法.

假设yn=y(n)是依赖于整数变量n=0，±1，±2，…的函数， Δyn=yn+1-yn，Δm+1yn=Δ(Δmyn)，Δ1yn=Δyn，m=1，2，…是有限差分，Δmyn含有函数y在m+1个点n，…，n+m上的值，公式

成立，方程

F(n;yn，Δyn，…，Δmyn)=0 (4.13)

称为差分方程，其中y是未知函数，F是给定函数. 用由所求函数值表示的表达式(4.12)代替式(4.13)中的有限差分，它就化成形如

F(n; yn，yn+1，…，yn+m) =0 (4.14)

的方程，如果≠0，即方程(4.14)确实含有yn和yn+m，则方程(4.14)称为m阶差分方程. 方程

am(n)yn+m+…+a0(n)yn=fn(4.15)

是m阶线性差分方程，其中fn=f(n)是给定函数，ak(n)(k=0， 1，…，m)为已知系数，am(n)≠0，a0(n)≠0; 满足方程(4.13)的函数yn=y(n)称为差分方程的解. 和微分方程一样，差分方程的解也有特解和通解之别. 若fn=0，则方程为

an(n)yn+m+…+a0(n)yn=0 (4.16)

称为齐次差分方程，相应地式(4.15)称为非齐次差分方程.

若给出yn=y(n)的某些特殊值: y1=y(1)，y2=y(2)，…， ym=y(m)，这些值称为y(n)的初始值，或解的初始条件. 以二阶差分方程为例，设二阶非齐次差分方程为

a2(n)yn+2+a1(n)yn+1+a0(n)yn=fn(4.17)

相应的齐次差分方程为:

a2(n)yn+2+a1(n)yn+1+a0(n)yn=0 (4.18)

下面的命题成立:

(1)若un和vn是方程(4.18)的解，以及c1，c2是任意常数，则函数c1un+c2vn也是方程(4.18)的解，称为方程(4.18)的一般解(通解);

(2)非齐次差分方程(4.17)的通解是它的任意一个特解与齐次差分方程(4.18)的通解的和，非齐次方程(4.17)的特解可以从齐次方程的通解用参数变易法来构造.

若˜yn是非齐次方程(4.17)的任一特解，yn是相应齐次方程(4.18)的通解，则yn=˜yn+yn，是方程(4.17)的通解.

如果方程(4.17)中系数为常数，即a2(n) =a2，a1(n) =a1， a0(n) =a0，方程即为

a2yn+2+a1yn+1+a0yn=fn(4.19)

称为常系数差分方程. 当fn=0时即为常系数齐次差分方程.

a2yn+2+a1yn+1+a0yn=0 (4.20)

设方程(4.20)的特征方程

a2q2+a1q+a0=0

具有根

若q1=q2，则(4.20)的一般解为yn=

若q1，q2是复共轭. q1，q2=ρ(cosφ±isinφ)

则通解为

其中c1，c2为任意常数.

非齐次差分方程的解法据(2)，先求其特解˜yn，再求相应齐次方程的通解y，即为yn=˜yn+yn.

现在用差分方程来求例4.12的通项公式.

因为Sn=Sn-1+n(n+1)，则Sn-Sn-1=n(n+1)，这是一个简单的非齐次差分方程. 而相应齐次差分方程的通解为

由非齐次项fn=n2+n的特点，fn=lp(n)，lp(n)=n2+n)→l=1， P(n) =n2+n是一个二次多项式，故非齐次差分方程的特解有

其中a，b，c为待定系数，把˜Sn代入Sn-Sn-1=n(n+1)中，比较系数，得a=，b=1，c=.

所以

由S1=2，得C=0.

所以

这种算法虽然较麻烦，但我们学到了一种更一般的方法.

例4.13 设一个回路有n个顶点和n条边，用k各颜色对每个点着色，使每两个有边相连的顶点着不同的颜色，问这样的着色法共有多少种?

设n个顶点为V1，V2，…，Vn，先对V1着色有k种方法，继而对V2着色使与V1颜色不同，有k-1种方法，…，最后着色Vn也有k-1种方法，故总数应是k(k-1)n-1，而这些着色法可分成两类: 一类是Vn与V1不同颜色共Pn(k)种方法; 另一类是Vn与V1同色，就可把n个顶看成n-1个顶点，有Pn-1(k)种着色方法，从而得Pn(k)+Pn-1(k)=k(k-1)n-1.

即 Pn+Pn-1=k(k-1)n-1.

显然，齐次差分方程的通解为Pn=C(-1)n，C为任意常数，非齐次线性方程的特解为˜Pn=(k-1)n，所以

Pn=C(-1)n+(k-1)n

由P2=K(k-1)得C=k-1，所以

Pn=(-1)n(k-1)+(k-1)n

从上面问题的解法看出，只要所求整标函数y(n)有一个递推关系，这个递推关系就可看作一个差分方程，当系数简单时，即可用差分方程求解.

4.2.2.2 递归法

表面上看，似乎递归和递推差不多，实际上是不一样的. 递归法，是在算法论和数理逻辑的研究中定义函数的一种方法. 一般来说，如果计算从f(0)→f(1)→f(2)→…→f(n)，称为递推.而如果是“倒退着”的，n→n-1→n-2→…→2→1，便是递归了.还有并非所有的递归都能表示成递推，有解的递归也不一定能直接表成递推形式. 自然数的阶乘n!，定义为n! =n(n-1)·…· 2·1. 若用f(n)来表示求n! 的函数，则f(n)可以写为:

f(0) =1，f(n) =nf(n-1) (n＞0) (4.21)

式(4.21)就是阶乘函数的递归式.

在数学上，递归是一个非常重要、非常基本的概念，它不但定义了一种基本的计算原则，而且给为什么是可计算的划定了一个界线. 递归函数理论断言: 一切可计算的函数，都可以归结为几种基本的递归函数的组合. 最简单和最广泛用的模式是原始递归，原始递归函数共三个，我们总认定它定义在整数集上(以后再逐步扩展).

由原始递归，可定义两类基本操作: 第一类叫函数的复合，即把一个函数放到另一个函数的参变量的位置上，例如

S(S(S(x))) =((x+1) +1+1) =x+3

U2(N(x)，S(N(x))≡1，….

一般地，如果已知f(x1，…，xn)是原始递归函数，g1，…，gn也是原始递归函数，则f(g1，…，gn)也是一个原始递归函数. 可以把它写成h(y1，y2，…，ym)的形式，这里诸yi构成的集合是g1，g2，…，gn中所有参变量的并集.

第二类操作叫原始递归，就是类似于用递推的办法来定义新原始递归函数，阶乘函数(4.21)可改写为

f(0) =1

f(n+1)=mul(S(n)，f(n)) n≥0 (4.23)

这里的mul是一个新函数，表示乘法，mul(x，y) =x·y.

原始递归是最简单和最广泛用的递归模式，人们在日常计算中用到的函数，几乎都可以归入它. 设函数g(x1，…，xn)与h［y，f(x1，…，xn)，x2，…，xn］是已知原始递归函数，f地要确定的函数，满足

f(0，x1，x2，…，xn) =g(x1，…，xn)

f(y+1，x2，…，xn)=h［y，f(y，x1，…，xn)，x1，…，xn］ (4.24)

其中y是实施递归的变元，x1，…，xn是不介入递归的参数，则函数f(y，x2，…，xn)称为可原始递归方式定义.

但是，原始递归函数类不能概括所有的可计算函数，为此，必须对原始递归函数类加以扩充，其办法是借助于一种新操作，叫μ操作:

设f(y，x1，…，xn)是一个函数，式子

h(x1，…，xn) =μy［f(y，x1，…，xn)］ (4.25)

定义了一个新的函数h，对每一组具体变元的值(a1，…，an)，h的函数值使f(y，a1，…，an) =0的最小的y值. 若这样的值不存在，则认为h在(a1，…，an)处无定义. 把在式(4.25)出现的μ的算子称为极小化算子，而μ操作也称为极小化操作.这样操作以后的函数类称为μ递归函数类，又称部分递归函数类. 一般地，有一个部分函数称为μ递归的，若它是由基本函数(原始递归函数)经过有限次复合、原始递归和极小化算子而得. 处处有定义的μ递归函数(部分递归函数)称为全递归函数. 可以证明

(1)阿克曼函数是全递归函数;[1]

(2)μ递归函数一定是图灵机可计算函数; [2]

(3)图灵机可计算函数一定是μ递归函数.

递归方法应用十分广泛，在算法论和数理逻辑的一些分支(如模型论，递归论)中，有着举足轻重的作用，是计算数学的重要工具，计算机程序设计和分形算法所必备. 下面略举几例.

例4.14 递归数列.

对任何自然数n，由k个初始项a1=α1，a2=α2，…，ak=αk，并有关系an+k=f(an+k-1，an+k-2，…，an+1，an)确定的数列{an}称为递归数列，其中k(≥1)称为递归数列的阶数.

(1)若数列{an}第k项以后的任一项，都是其前k项的线性组合，即

an+k=λ1an+k-1+λ2an+k-2+…+λkan(4.26)

其中n∈N，λ1，λ2，…，λk是常数，且ak≠0，则称{an}为常系数k阶线性齐次递归数列. (4.26)式称{an}的递归方程，而当

an+k=λ1an+k-1+λ2an+k-2+…+λkan+f(n) (4.26')

且f为非零时，{an}为线性非齐次递归数列.

把与k阶线性齐次递归数列的递归方程(4.26)相对应的方程

xk=λ1k-1+λ2xk-2+…+λk-1x+λk(4.27)

叫做k阶线性齐次递归数列的特征方程，利用特征方程，即可求得该数列的通项.例如，数列{an}满足:a1=0，且an-2an-1=n2-3(n=2，3，…)，求an.由an-2an-1=n2-3的规律进行三次代换得

an=5an-1+9an=2-7an-3+2an-4=0

知数列为常系数4阶齐次递归数列，其特征方程是

x4-5x3+9x2-7x+2=0

解之得 x2=x2=x3=1，x4=2

于是 an=(c1+c2n+c3n2)·1n+c4·2n

由a1=0，an-2an-1=n2-3，求得a2=1，a3=8，a4=29.

得方程组

解方程组得c1=-3，c2=-4，c3=-1，c4=4

所以 an=-3-4n-n2+4·2n=-n2-4n-3+2n+2

=2n+2-n2-4n-3

即为数列{an}的通项公式.

(2)由给定的a1及递推关系

确定的数列{an}，称之为分式线性递归数列，其中a，b，c，d为复常数，且c≠0，ad≠bc.

将方程

称为由式(4.28)所确定的分式线性递归数列的特征方程.

若α，β为特征方程(4.29)的两根，则λ=为分式线性递归数列的特征值.

要使分式线性递归数列是无穷数列，其充要条件与通项公式[3]

是:(ⅰ)特征值λ=1时不为自然数;此时，{an}的通项公式为an=

(ⅱ)特征值λ≠1时，方程λx=无自然数解.此时，{an}的通项公式为an=

这是一个分式线性递归数列，特征方程是

解之，x1=2(=α)，x2=-1(=β)，于是λ=，

此时，a=-3，c=1，因为λ≠1，故有

例4.15 分形图形的递归算法.

计算机图形学是计算机科学的一个重要分支，分形理论的发展离不开计算机图形学的支持，如果一个分形构造的表达不用计算机的帮助是很难让人理解的. 分形是自然界的几何学，产生于20世纪70年代，既是一种新几何理论，也是一种方法论. 分形是一种形状，更是一种方法，分形方法是人类观察事物的第三轴，它是从纵深的角度认识世界，并提供了一种新的思维方式，以达到从有限认识无限，从局部认识整体，从瞬时认识永恒. 分形作为一种方法，在图形学领域主要是利用迭代、递归等技术来实现某一具体的分形构造.这样的例子很多，我们只举谢尔宾斯基垫片为例. 它是谢尔宾斯基(W.Sierpinski，1882—1920，波兰数学家)1915年创造的一种分形. 谢氏正三角形，它具有无穷周长和有限面积.下面给出两种算法.

(1)递归算法

步骤: ①给出初始三角形中心点坐标(x，y)和三角形的边长l，计算出三角形三个顶点的坐标，并画出初始三角形(如图4.6所示).

图4.6

②根据

计算△ABC各边中点的坐标，并画出3条边中点之间的连线，从而形成4个小三角形△ADE，△BEF，△CDF，△DEF.

③设定递归深度，利用递归算法，分别对△ADE，△BEF，△CDF执行第②步，每次执行边长为上一步的一半，即l=，并压入堆栈，同时使递归深度值减1，直到递归深度值等于1时，释放堆栈，并画出相应三角形，如图4.6所示.

算法说明:

①此算法的优点是可以构造正三角形的谢尔宾斯基垫片图形，但不能构造任意三角形的谢尔宾斯基垫片图形;

②此算法采用的是设置递归浓度变量初值的方法来控制其递归深度，这样可以更好地掌握递归的层次数.

程序设计(略).

(2)迭代函数系统算法

谢尔宾斯基垫片的仿射变换:

图4.7

其中x，y为原图坐标，x'，y'为新图坐标.

于是谢尔宾斯基垫片可以用3个仿射变换来表示.

由于生成的3个小三角形的面积相等，所以可以让ω1、ω2、ω3出现的概率相同或相近，即 p1=0.333，p2=0.333， p3=0.334.并保证p1+p2+p3=1.

由6个仿射变换系数和一个概率(P)组成IFS码如表4-2所示.

表4-2

算法与步骤:

①生成随机数R，并使R的值在0，1之间;

②分配ω1，ω2，ω3这3个仿射变换的概率空间，分别为［0，0.333］，(0.333，0.666］，(0.666，1〛;

③判断随机数落入哪一个概率空间，并调用相应的仿射变换所具有的IFS码值，付给相应的参数ai，bi，ci，di，ei，fi;

④根据计算仿射变换关系式，计算仿射变换后的x'，y'值;

⑤在(x'，y')处画一点;

⑥循环执行步骤①～⑤，并将上一次计算出的x'，y'值作为这一次的x，y值参加计算;

⑦完成循环次数并按控制键结束.

程序设计(略).

图4.8

[1] 满足下面三式: A(0，n) =n+1; A(m，0) =A(m-1，1); A(m，n) =A(m-1，A(m，n-1)的A(m，n)称为阿克曼函数.

[2] 一种关于计算的数学模型，后世称之为图灵机，图灵机可计算作为能行可计算的代名词，图灵的思想为电子计算机诞生奠定了理论基础;

[3] 杨世明主编.《中国初等数学研究文集》. 郑州: 河南教育出版社，1992: 428.