线性递推公式解法（具有递推关系的运算---牛顿法）

牛顿 如上一节讨论的那样，在日常生活和生产实践中，许多求“最好”的问题往往可以归结为求“最大”的问题，而大多数求“最大”的问题都可以借助“递推”的计算方法也就是说，大多数求“最大”的问题都可以借助“模式”化的计算方法实践证明，以牛顿( 1642～1727)命名的计算方法，以及在这个方法基础上衍生出来的方法，是最为简捷、最为实用的方法我们来分析这种方法，从中体会“递推”的功效，下面我们就来说一说关于线性递推公式解法?我们一起去了解并探讨一下这个问题吧!

线性递推公式解法

牛顿

如上一节讨论的那样，在日常生活和生产实践中，许多求“最好”的问题往往可以归结为求“最大”的问题，而大多数求“最大”的问题都可以借助“递推”的计算方法。也就是说，大多数求“最大”的问题都可以借助“模式”化的计算方法。实践证明，以牛顿( 1642～1727)命名的计算方法，以及在这个方法基础上衍生出来的方法，是最为简捷、最为实用的方法。我们来分析这种方法，从中体会“递推”的功效。

图(1) 牛顿法求方程解示意图

我们先讨论方程f(x)=0求解的问题。如图(1) 所示，牛顿法在本质上是一种利用切线的方法，我们在《微积分的产生》中曾经讨论过，函数在某一点的切线斜率可以用导数表示，因此，牛顿法只实用于可以求导的函数。下面我们来分析牛顿法的核心思想以及建立在牛顿法上的计算逻辑。

根据导数的定义我们知道，导数是平均变化率的极限，如果用f’(x)表示函数f(x)的导数，那么函数在x_o处的导数可以表示为：

f’(x₀)=limx→x₀[(f(x)-f(x₀))/(x-x₀)]

如果f(x) =0，则通过上式可以近似得到：

f(x₀) f’(x₀)[x-x₀]=0

由上式又可以得到方程的解为：

x=x₀-f(x₀)/ f’(x₀) (1)

这就是牛顿法的基本算式。因为等号的右边都是基于给定的数，是可以具体计算出数值的，因此可以用这个具体计算出的数值作为下一步计算的点，构建下面的计算逻辑：

输入f(x)，a,n

1．计算f(a)

2．计算f’(a)

3．计算c=a-f(a)/ f’(a)

4．如果|c-a|≤10^-n，到指令7。否则

5．令a=c

6．回到指令1

7．令x*=c。停止

输出x*，f(x*)

其中，输人中的a是一个最初给定的数，通常称其为初始值，或者初值。可以看到，上述计算逻辑的核心就在于不断地更新初值。还可以看到，这个计算逻辑是非常美妙的，把一个复杂的问题抽象得非常简捷，耐人寻味，特别是这个算法收敛的速度非常快，用牛顿法再次计算方程x² x-1=0 ，用x(n)表示第n次的计算结果，可以得到：

x(0)=1

x(1)=0. 61904761904763

x(2) =0. 61803444782168

x(3)=0. 61803398874999

x(4) =0. 61803998874989

x(5)=0. 61803998874989

可以看到，如果初值为1，第二次计算就到达了0. 618，这比用二分法速度要快得多。

现在，我们讨论求最大值的问题。关于最大值问题，内容是丰富多彩的，比如，我们研究炮弹的运行轨迹，那么，根据研究的目的不同，最大值的含义也可以不同：最大值可以是炮弹最高的值，也可以是炮弹最远的值，因为这些值都与炮弹发射后的时间t有关，所以研究的基础是时间的函数f(t)。在通常情况下，可以构建时间t的参数方程：横坐标为x(t)，纵坐标为y(t)；如果注意到炮弹的运行轨迹又与发射的角度有关，那么，通过最大值可以研究炮弹以多大的角度可能发射的最远，这时研究的基础将是一个二元函数f(t，s)，其中s为发射角度。在这样的问题中，称为达到研究目标而设定的函数为目标函数，可以利用牛顿法来求目标函数的最大值。

图(2) 牛顿法求最大值示意图

如图(2)所示，一个连续函数如果存在最大值，那么，这个函数在最大值点的切线必然与横坐标平行，也就是说，这个函数在这一点的导数为0，这启发我们可以利用牛顿法来求函数的最大值。一般情况下，函数的导数也是一个函数，我们称其为一阶导函数。如果用f’(x)表示目标函数f (x)的一阶导数，则求最大值点等价于求方程

f’(x)=0

的解。回忆关于牛顿法的讨论，现在，在计算的过程中我们需要利用一阶导函数的导数，称其为二阶导函数，表示为f’’(x)，那么参照(1)式可以得到求最大值的基础算式：

x=x₀-f’(x₀)/ f’’(x₀) (2)

类似地，通过基本算式(2)可以构建求最大值的计算逻辑，我们就不详细讨论了，有兴趣的读者可以发现，只需要对方程求解的计算逻辑作很小的修改就可以得到求最大值的计算逻辑。

下面，我们尝试地讨论求二元函数最大值的计算逻辑，比如我们曾经讨论过的，炮弹的轨迹就可以是时间和角度的二元函数。求多元函数最大值的问题是非常困难的，也是现代数学研究中的热门话题，人们创造了许多适于计算机的求最大值的计算方法。受辗转数学归纳法论证模式的启发，是否可以在二元函数的两个变量之间构建一个辗转交替的计算逻辑呢？

我们分析如下。

用f(x，y)表示一个二元函数，我们知道，对于任意固定x=a，函数f(a，y)就是变量y的一元函数；同样，对于任意固定y=b，f(x，b)就是变量x的一元函数，因为已经论证了，通过牛顿法可以得到一元函数的最大值，为了讨论问题的方便，称这种方法为NT算法，这样，我们就可以构建一个利用NT算法的辗转交替的计算逻辑：

输入f(x,y),a,b,n

1．令m=0

2．令x(m)=a，y(m)=b

3．利用NT算法计算f(x(m),y)，得到y₀

4．利用NT算法计算f(x,y₀)，得到x₀

5．如果|x₀-x_m| |y₀-y(m)|≤10_-n，到指令9。否则

6．令m=m 1

7．令x(m)=x₀，y(m)=y₀

8．回到指令3

9．停止

输出x₀,y₀,f(x₀,y₀),m。

通过上面的辗转交替的计算逻辑，我们将得到一个由二维向量构成的数列：

x(1)，x(2)，…

y(1)，y(2)，…

现在的问题是，这样得到的二维向量的点列能收敛吗？也就是说，这样的辗转运算最终必然会得到所需要的结果吗？答案是肯定的，只要函数f(x，y)满足·些比较弱的条件，那么上述点列必然收敛，当然，这个证明是相当繁琐的。通过这个例子也可以看到，借助递推关系所构建的汁算逻辑不仅可以作用于一个变量，也可以作用于几个变量之间。

我们通过一些具体问题介绍了计算逻辑。我不知道在其他地方是否也提到过计算逻辑，因为在通常情况下，人们称讨论计算原理的学科为计算方法，在这里之所以称其为计算逻辑，是因为我想强调的是，如果把计算方法中的核心思想归纳出来，是可以形成思维模式的，姑且称其为计算逻辑。可以看到这个思维模式的基础是：所涉及的计算方法都具有递推性，就

这一点而言，计算逻辑在本质上与我们曾经分析过的三段论是一致的，同时，通过上面的讨论也可以看到，计算逻辑的推理也是非常美妙的，是非常直观的，其推理过程有时也是非常困难的；特别是，计算逻辑对书写语句的前后顺序要求非常严格，必须对逻辑过程有了整体构想之后才可以动笔书写，而这一点对于逻辑训练是非常重要的。通过计算逻辑得到的结果是必然的，因此计算逻辑属于演绎推理的范畴。因此我想，在我们的数学教学中，特别是在高中数学的教学中，是否也应当让学生们知道这种建立在计算基础上的逻辑推理模式，这不仅对于学生将来使用、研究计算机很重要，同时，这将是一种很好的逻辑训练，很可能这是一种面向未来的逻辑训练，就创新思维而言，这种逻辑训练的功能要远远超过平面几何，并且，这种逻辑训练要比平面几何实用得多。