斐波那契数列的定义为前两项是0和1，从第三项开始每一项都等于前两项之和，即F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。当我们需要计算第n项斐波那契数时，传统的递归方法时间复杂度为O(2^n)，迭代方法为O(n)，而基于矩阵幂运算的方法可以将时间复杂度降低到O(log n)，在n较大时优势十分明显。
斐波那契数列的矩阵递推关系
我们可以将斐波那契数列的递推关系转化为矩阵乘法的形式，已知：
F(n) = F(n-1) + F(n-2)
F(n-1) = F(n-1)
将其写成矩阵形式可以得到：
[ F(n) ] = [1 1] * [F(n-1)] [F(n-1) ] [1 0] [F(n-2)]
通过递推可以得到更一般的形式：
[ F(n) ] = [1 1]^(n-1) * [F(1)] [F(n-1) ] [1 0] [F(0)]
其中F(0)=0，F(1)=1，因此我们只需要计算矩阵[1 1; 1 0]的(n-1)次幂，再取结果矩阵的第一个元素，就能得到F(n)的值。
使用NumPy实现矩阵幂运算计算斐波那契数
NumPy的linalg模块提供了matrix_power函数，可以直接计算矩阵的整数次幂，我们使用这个函数来实现斐波那契数的计算。
基础实现代码
import numpy as np
def fibonacci_by_matrix_power(n):
# 处理边界情况
if n < 0:
raise ValueError("n必须为非负整数")
if n == 0:
return 0
if n == 1:
return 1
# 定义递推矩阵
base_matrix = np.array([[1, 1], [1, 0]], dtype=object)
# 计算矩阵的(n-1)次幂，dtype=object避免整数溢出
power_matrix = np.linalg.matrix_power(base_matrix, n-1)
# 结果矩阵的第一个元素就是F(n)
return power_matrix[0, 0]
# 测试计算前10项斐波那契数
for i in range(10):
print(f"F({i}) = {fibonacci_by_matrix_power(i)}")
上述代码中我们将矩阵的数据类型设置为object，是为了避免当n较大时整数超出NumPy默认整数类型的范围导致溢出。运行代码后会输出前10项斐波那契数的正确结果。
优化后的通用实现
如果需要计算多个斐波那契数，我们可以进一步优化实现，同时支持返回前n项斐波那契数列：
import numpy as np
def fibonacci_sequence_by_matrix_power(n):
if n <= 0:
return []
if n == 1:
return [0]
# 递推矩阵
base_matrix = np.array([[1, 1], [1, 0]], dtype=object)
result = [0, 1]
# 从第二项开始计算到第n-1项
for i in range(2, n):
power_matrix = np.linalg.matrix_power(base_matrix, i-1)
result.append(power_matrix[0, 0])
return result
# 计算前15项斐波那契数列
fib_seq = fibonacci_sequence_by_matrix_power(15)
print("前15项斐波那契数列：", fib_seq)
不同方法的性能对比
我们可以通过实际测试对比矩阵幂运算方法和传统迭代方法的性能差异，测试计算第10000项斐波那契数的耗时：
import numpy as np
import time
# 迭代方法实现
def fibonacci_iterative(n):
if n < 0:
raise ValueError("n必须为非负整数")
if n == 0:
return 0
if n == 1:
return 1
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# 测试矩阵幂运算方法耗时
start = time.time()
fib_matrix = fibonacci_by_matrix_power(10000)
matrix_time = time.time() - start
# 测试迭代方法耗时
start = time.time()
fib_iter = fibonacci_iterative(10000)
iter_time = time.time() - start
print(f"矩阵幂运算方法耗时：{matrix_time:.6f}秒")
print(f"迭代方法耗时：{iter_time:.6f}秒")
print(f"两种方法计算结果是否一致：{fib_matrix == fib_iter}")
实际测试可以看到，当n为10000时，矩阵幂运算方法的耗时远小于迭代方法，充分体现了O(log n)时间复杂度的优势。
注意事项
- 计算大指数矩阵幂时，建议使用
dtype=object的矩阵，避免整数溢出问题。 - 当n较小时，矩阵幂运算的开销可能比迭代方法更高，因为矩阵运算本身有一定的初始化和计算成本，此时可以根据n的大小选择不同的方法。
- NumPy的
matrix_power函数要求幂次为非负整数，因此需要对输入的n做合法性校验。
矩阵幂运算计算斐波那契数列的核心是利用线性代数中的矩阵递推关系，将数列问题转化为矩阵运算问题，结合NumPy的高效数值计算能力实现快速求解，适合需要处理大项数斐波那契数的场景。