image.png

员工培训的时候，员工提了一个问题，说当年大学数学学了那么久，从来没有感觉到有什么用处。限于时间，当时我没有做很深入的举例说明。于是特地在此举出下面这个例子，来切实的感受了一下数学对于我们实际工作的用处。

问题背景

问题是这样的，对于斐波那契数列，我们经常可以看到如下形式的递归实现

    function fib(n) {
        if (n < 0) throw Error('Illegal argurment n = ' + n + ', need n >= 0');
        if (n == 0 || n == 1) return 1;
        return fib(n-1) + fib(n-2);
    }

很显然，这个递归算法是一个非常低效的实现，时间复杂度在O(2^n)上。将其用迭代方式改造后，可以将时间复杂度和空间复杂度都控制在O(n)上，算是一个不错的办法。具体的做法无关本文，就不在这里展开了。但是，如果能够直接给出fib(n)的通项公式，那么这个函数的复杂度将保持在O(1)上，将是一个非常理想的实现。

众所周知的是，斐波那契数列具有初等形式的通项公式。这是一个非常幸运的事情，并非所有的数列都具有初等形式的通项公式。我们的问题就是，这个通项公式如何获得。

如果仅仅是背书知道这个公式，其实没有多少实际意义，更关键的地方是在我们知道如何获得这个公式，从而理解获得它的方法，使之能够推广到其它类似的情况去。这个就是我们展示数学的实际用处的地方。虽然说这个展示依旧很数学化，但是确确实实已经非常贴近实际了。

构造解空间

观察斐波那契数列的递推公式

    fib(n) = fib(n-1) + fib(n-2)          (n>=2, n in Z)

或者写为

    fib(n+2) = fib(n+1) + fib(n)        (n>=0, n in Z)

我们发现假如 f(n) 函数和 g(n) 函数都满足这个公式，对于所有实数 k 和 h，都有 p(n) = kf(n) + hg(n) 也满足这个公式，这个非常容易验证。这个性质就是所谓的线性性质。

进一步我们可以发现，如果 f(n) 函数满足这个公式，那么 p(n) = -f(n) 函数也满足这个公式。

类似的如果 f(n) 恒等于0，那么它同样也满足这个公式。

看到这里，其实就应该意识到了，原来斐波那契的递推公式约束了一系列的函数，这些函数的整体满足线性空间的各个定义条件，所有的可选函数构成了一个线性空间。而这些函数是这个线性空间中的一个向量。线性空间其它定义条件的满足性读者也可以自行尝试证明一下。这个线性空间就是斐波那契递推公式的解空间。

寻找解空间的基底

读过线性空间的话，知道一个线性空间是有确定的维数的，它标记了这个空间里面的向量的自由度。如果一个线性空间有 n 维，那么一定可以找到 n 个线性无关的向量，构成这个线性空间的基底，而所有线性空间的向量，可以用这组基底的线性组合表示出来。

对于斐波那契数列，如果我们找到了这组基底，假如说是 f1(n)，f2(n)，...，fs(n) 那么我们就可以给出满足前述递推公式的所有的函数的一个统一的表示形式

    f(n) = a1 * f1(n) + a2 * f2(n) + ... + as * fs(n)

而由于这组基底是已知的函数，所以求解斐波那契数列的问题，就转化为求这些系数 a1, a2, ..., as 的问题了，而这些系数可以通过初值代入法非常容易的得到。

所以说，获得通项公式的关键在于获得这组基底函数。那么如何得到这组基底呢？其实线性代数的教材中线性变换的部分是给出了答案的。

线性变换派上用场

考虑函数 f(n) ，考虑这样的线性变换 H[f]，它得到的函数 g = H[f] 正好是原来函数错一位以后的结果，也就是说 g(n) = f(n+1)，那么斐波那契数列的递退公式可以理解为

    H^2[f] = H[f] + f

也就是

    (H^2 - H - 1) f = 0

这里的 1 指代的是恒等变换 1[f] = f . 那么这个递推公式其实是给出了一个变换方程

    T[f] = 0        (T = H^2 - H - 1)

寻找本征向量

借助线性变换的观点，我们重新理解了这个递推公式，同时也为我们打开了寻找基底的窗户。一个线性变换的存在一组本征向量是线性无关的，且其数量与这个线性变换的秩相等。所以去寻找T的一组线性无关的本征向量是我们下一步自然而然要做的事情。

寻找T的本征向量前，如果先得到了H的本征向量，满足

      H[f] = lambda*f

其中lambda是这个本征向量 f 所对应的本征值，那么显然，f 也是 T 的本征向量，满足

    T[f] = (H^2 - H - 1) f = (lambda^2 - lambda - 1) f

即其对应的本征值为 lambda^2 - lambda - 1

所以只需要去寻找 H 的本征向量即可，于是问题转化为

    H[f] = lambda * f

即

    f(n+1) = lambda * f(n)

这个其实就是一个等比数列，通项公式可以写作

    f(n) = lambda^n * f(0)

这样我们就找到了这个 H 的本征向量了，同时也是 T 的本征向量。

得到结果

这时候再回过头来看原来的那个变换方程

    T[f] = (H^2 - H - 1) f = 0

如果 f 正好是刚才的那个本征向量，那么就有

    (H^2 - H - 1) f = (lambda^2 - lambda - 1) f = 0

注意到不是所有的本征向量都是恒为0的，要让上式成立，就需要满足

    lambda^2 - lambda - 1 = 0

注意到 lambda 是一个实数，上面这个方程其实是一个代数方程。求解这个方程，我们可以得到两个不同的实根 lambda1, lambda2。这样我们就获得了两个线性无关的本征函数

    f1(n) = lambda1^n * f1(0)
    f2(n) = lambda2^n * f2(0)

所以斐波那契递推公式的通解就是

    fib(n) = a * lambda1^n + b * lambda2^n

通过代入初值fib(0)和fib(1)我们就可以最终确定 a，b 从而得到它的通项公式。

结语

这个例子是一个非常生动的利用线性空间理论求解差分方程的情况。斐波那契递推公式其实就是一个二阶线性差分方程。其实理工科的毕业生基本上都学过线性常微分方程的解法，和这里介绍的其实是同一套方法，只是这里换来处理差分方程问题而已。不过对于大多的程序员而言，解微分方程的情况很可能比较少碰得上，但是通过求解查分方程优化算法一定是不难碰到的。所以这个应该算是一个比较生动的例子了。

这里所使用的理论都是成熟了许多年甚至几个世纪的理论了，在各个大学的线性代数教材中都可以看到相关的内容，在此就不列出参考文献了。