Video在线视频

大家好

这一节我们介绍

算法设计方法之递推

递推是算法设计中最常用的

重要的方法之一

有时候也叫迭代

那么 什么是递推呢

所谓递推

就是从给定的边界条件出发

逐步迭代到期望的结果为止

说的直白一点

就是根据已知条件

顺着“藤儿”去摸“瓜”

直到摸着“瓜”为止

这里所说的藤

就是一种线索

一种反映前后项的因果关系

瓜就是我们要求的结果

在很多情况下

待求解的问题

不能归纳出简单的计算关系式

但在其前后项之间

却能够找到某种“因果”关系

也就是递推关系

利用这种关系

便可从已知项的值

递推出未知项的值来

让我们看一个熟悉的例子

用递推算法

来计算函数 f(n)等于n的阶乘

我们知道

n的阶乘乘以n乘n-1的阶乘

而0的阶乘等于1

那么这个递推关系

就是f(n) 等于f(n-1) 乘 n

假定我们要计算10的阶层

可以从递推初始条件

f(0)等于1出发

利用递推关系f(n)等于n 乘 f(n-l)

逐步计算出f(1)

f(2)一直到f(9)

最后求出f(10)的值

它的递推过程是这样的

这个也就是对应的算法

再比如Fibonacci数列

1 1 2 3 5 8 13 等等

它的递推关系是

F(1)等于1

F(2)等于1

F(n)等于F(n-1)加F(n-2)

如果需要得到第50项的值

可以由初始条件F(1)等于1

F(2)等于1出发

利用递推公式逐步求出

F(3) F(4) 等等

最后求出F（50）的值

大家也许会问

用通项公式来计算F(50)的值

不是更方便吗

是的 但事实上有些问题

要找出通项公式是相当困难的

并且即便能找到

它的计算也并非简便

例如

Fibonacci数列的通项公式是这样的

显而易见

寻找这样的通项公式是相当不易的

并且利用这样的式子

计算F(n)也相当费力

与此相反

如果利用递推初始条件

和递推关系

来进行计算就方便多了

我们再看一个例子

计算这么一个多项式的值

假设n x以及系数a1

到an加1均为已知的值

怎么计算呢

秦九韶按照这样的方式

将F(x)进行了改写

得到了这样的式子

不难看出

式中每层括号中的值

都具有以下的形式

也就是Pi等于Pi减1x加ai

只要知道了前项Pi减1

就可以由此计算出后一项Pi

所以秦九韶算法

就可以这样来描述

事实上

递推的方向既可以由前往后

也可以由后向前

广义地说

凡是根据某一关系

从已知的项推出未知的项

都可以视作递推

从这个意义上看

用算式s等于s加n求累加和

用算式p等于p乘n求连乘积

都包含了递推思想的运用

比如

计算 S等于l加2加3

一直加到一千

可以确定

迭代变量S的初始值为0

迭代公式为 S等于S加 n

当n分别取1 2 3 4一直到一千时

重复计算迭代公式

迭代一千次以后

也就可以求出S的值了

在科学计算领域

人们时常会遇到

求解方程 f(x)等于0

或微分方程的数值解

等这样的计算问题

可是人们却很难或者无法用

像一元二次方程的求根公式

那样的解析法去求解

例如

一般的一元五次或更高次方程

几乎所有的超越方程

其解都无法用解析方法表达出来

为此

人们只能用数值方法

求出问题的近似解

如果近似解的误差

可以估计和控制

并且迭代的次数也可以接受

它就是一种求数值近似解的好方法

下面以求方程f(x)等于0的根为例

说明迭代法的基本思想

首先把求解方程进行变换

变换成这么一种迭代的式子

也就是x等于g(x)

然后根据事先估计的一个根

初始值x0

（这是一个近似值）由它出发

用迭代算式xk加1等于g(xk)

求出另一个近似值x1

再由x1确定x2以此类推

最终构造出一个近似根序列

x0 x1 x2一直到xn

以此来逐次

逼近方程f(x)等于0的根

来我们来看一个具体的例子

比如 求方程x3减x减1等于0

在x等于1.5附近的一个根

我们首先将方程进行改写

改写成

x等于x加1开3次方

用给定的初始近似值x0等于1.5

代入上式的右侧

我们可以计算出

x1等于1.3572

再用x1作为近似值再代入上式

又可以计算出

x2等于1.33086

重复同样的步骤

可以逐次求得更精确的值

这一过程即为迭代过程

显然

迭代过程就是通过原值求出新值

用新值替代原值的这么一个过程

对于一个收敛的迭代过程

从理论上讲 经过无限次迭代

总可以得到一个精确解

但实际计算时

只能作有限次迭代

因此 要精选迭代算式

研究算式的收敛性及收敛速度

例如上式如果选择x等于x3减1

作为迭代算式就是不收敛的

使用递推法

求解近似解的基本方法是

先确定一个合适的递推关系

选取一个初始近似值

以及解的误差

然后用循环来实现递推过程

终止循环过程的条件是

前后两次得到的近似值之差

它的绝对值小于或等于

预先给定的误差

并认为最后一次递推得到的

近似值为问题的解

这种递推方法称为逼近迭代

好 这一节就讲到这

谢谢大家