一、斐波那契数列问题背景



斐波那契（Leonardo Pisano Fibonacci）约出生于1170年，大约于1250年在现在意大利 的比萨逝世，他履行的足迹遍布欧洲和北非。他著有多本数学课本，此外还把阿拉伯数字表示法引入欧洲。虽然他的书都是手抄本，但它们还是广为流传。斐波那契最著名的一本书是LiberAbaci，出版于1202年。其中提出了下述问题：



某人将一对兔子 放在一个四周都是围墙的地方，如果假设每对兔子每个月生出一对兔子，且新生的兔子从第二个月开始就能生育，那么一年之后由最初的那对兔子一共产生多少对兔子



这个问题的解就是被称为斐波那契数列的集合：1、1、2、3、5、8、13....



通项公式为



注意，这个表述稍微转换一种说法——如果没有假设新生出的兔子需要一个月才能够成熟，进而能够生育，那么将不会有这个以斐波那契的名字命名的序列。因为这样的话，兔子的对数每过一个月就会翻倍，n个月过后，会有总共 



 对兔子，虽然规律共容易，但在数学上没啥独特性。



二、标准的递归解-程序实现



MATLAB版-带有缓存机制





三、线性代数视角下的对角化解



3.1 原理探讨



通过上面的讨论，我们有 斐波那契数列的递推式为

总体思路：我们可以使用矩阵对角化来解决，将上面的式子化成 

 的形式，继而化成



•  ，为了容易计算 

• 

•  ，我们采用对角化的方式



1. 1、组成方程组：

2. 

3. 2、根据上述方程组成矩阵表达式：

4. 

5. 3、求系数矩阵A的特征值和特征向量已对A进行对角化，

6. 

7. 4、特征向量矩阵S为：

8. 

9. 5、将 



 用特征向量表示， 



 表示斐波那契数列的前两项



6、最终结果为



所以给出k值，可以直接算出需要的斐波那契数列值，不必递归才能得到。



3.2代码实现



使用matlab编写上述步骤：



>>> slogan = "Life is short, I use Python"
>>> print
>>> <built-in function print>
>>> print(slogan)
>>> Life is short, I use Python
>>> len
>>> <built-in function len>
>>> len(slogan)
>>> 27



结果为：

1234



学习线性代数真是有趣~



更多内容：https://zhuanlan.zhihu.com/p/119395137



https://zhuanlan.zhihu.com/p/119395137



参考来源



《MATLAB数值计算》书籍



《线性代数及其应用》书籍



《MIT线性代数》课程，这门课真是精彩！