矩阵乘法问题——一些负面结果

Question

我尝试使用矩阵乘法求斐波那契数列。但我对负面结果有疑问。

import numpy as np

a = np.array([[1, 1],[1, 0]])
b = np.array([[1, 1],[1, 0]])
for i in range(100):
    if b[0][0] < 0:
        print(i)
    b = np.matmul(b, a)
#output: 91, 93, 94, 95, 97

是我的数学太差而无法理解负面结果，还是在 python / numpy 中我必须考虑一些事情？

Answer 1

你的计算是正确的。您运行限制了类型 int64 的大小。 int64 最大可以是 (2**63) - 1。您的矩阵类型为 int64，您可以使用 a.dtype.

检查

如果您在第一个否定之前查看迭代 i=90，您会得到

[[7540113804746346429, 4660046610375530309],
 [4660046610375530309, 2880067194370816120]]

但是 7540113804746346429 之后的下一个斐波那契数是 12200160415121876738 = 7540113804746346429 + 4660046610375530309，它比 2**63 - 1 大。所以它不能表示为 int64 类型。这会导致溢出，您可以阅读有关 here 的更多信息，但这就是您得到负数的原因。

浮点数为您提供了更大范围的数字。如果您使用浮点数而不是整数，您将避免使用负数。有多种方法可以做到这一点，但最简单的方法是修改 a 和 b 的初始矩阵定义以包含小数，如下所示：

a = np.array([[1., 1.],[1., 0.]])                              
b = np.array([[1., 1.],[1., 0.]])

然后你会注意到你所有的迭代都是正数。浮点数可能有其自身的错误来源，因为并非每个数字都可以准确表示，因此您必须根据自己的情况更好地决定您想要什么。

旁注：您可以使用 b @ np.linalg.matrix_power(a, n) 而不是使用 for 循环来获得第 n 次迭代（在您的代码中为 100），这相当于 a 本身乘以 n 次，然后乘以 b 或 B @ A^n。 NumPy 对其进行了优化，因此效率更高。

矩阵乘法问题——一些负面结果

Problems with matrix multiplication - some negative results

python

numpy

matrix

fibonacci