Python中的递归关系

Question

我正在研究“x_n+1=（13/3）x_n-（4/3）x_n-1”。我试图编写一个Python脚本来打印x_n的前50个值，其中x₀=1和x₁=1/3。这是我当前的代码：

import math
def printRecurrence():
    x = [0]*51 #initialize list of x values
    x[0] = 1
    x[1] = 1/3
    for i in range(1, 51):
        x[i+1] = (13/3)*x[i] - (4/3)*x[i-1]
        print(x[i])

我收到的输出是：

^{pr2}$

它只对前13个打印值正确。我得到的证据是x_n=3^-n，这在很大程度上与我的脚本值不匹配。我的计算有错吗？我一直看不见。在

Answer 1

您遇到浮点累积错误。在

由于当前结果依赖于以前的结果，而float类型只是一个近似值，所以运行的重复次数越多，累积误差增加的越多。在

因为您正在处理有理数，所以我建议使用fraction模块。在

import fractions
def printRecurrence():
    x = [0]*51 #initialize list of x values
    x[0] = fractions.Fraction(1,1)
    x[1] = fractions.Fraction(1,3)
    for i in range(1, 50):
        x[i+1] = fractions.Fraction(13/3)*x[i] - fractions.Fraction(4/3)*x[i-1]
        print(float(x[i]),3**(-i),x[i]-3**(-i))

打印重复（）

我已经打印了结果，3**-n的计算值和差值：

^{pr2}$

在20次复发后，差别会增加，但已经好多了。在

编辑：davidanswer让我意识到，分数到浮点的转换会破坏一切。在

fraction模块只在2个精确计算的整数之间执行除法，但是转换为float会破坏精度。在

Answer 2

这种递归关系可以通过使用fractions模块或使用decimal模块以可变精度级别精确回答，这表明精确计算50次迭代所需的非常高的精度。在

让-弗朗索瓦关于浮点累积误差的观点是正确的。但是fraction模块似乎无法将多个Fraction对象相乘，因此所有的数值都必须在fraction对象中声明。感谢他使用了正确的模块来解决这个问题。在

确切答案

import math
import fractions

def printRecurrence():
    x = [0]*51 #initialize list of x values
    x[0] = fractions.Fraction(1,1)
    x[1] = fractions.Fraction(1,3)
    for i in range(1, 50):
        x[i+1] = fractions.Fraction(13*x[i]/3) - fractions.Fraction(4*x[i-1]/3)
        print(float(x[i+1]), 3**(-(i+1)), x[i+1]-(3)**(-(i+1)))

printRecurrence()

打印结果表明，计算结果与证明答案完全吻合。在

不准确但有启发性的回答

decimal模块允许自定义精度级别；要达到50次迭代，需要60点或更高的精度。在

^{pr2}$

和让-弗朗索瓦的回答一样，我已经打印了结果，3**-n的计算值和差值。可以使用精度级别getcontext().prec来查看对结果的影响。在

0.111111111111 0.111111111111 -1e-60
0.037037037037 0.037037037037 -4e-60
0.0123456790123 0.0123456790123 -1.57e-59
0.00411522633745 0.00411522633745 -6.243e-59
0.00137174211248 0.00137174211248 -2.4961e-58
0.000457247370828 0.000457247370828 -9.984e-58
0.000152415790276 0.000152415790276 -3.993577e-57
5.08052634253e-05 5.08052634253e-05 -1.59742978e-56
1.69350878084e-05 1.69350878084e-05 -6.38971879e-56
5.64502926948e-06 5.64502926948e-06 -2.5558875048e-55
1.88167642316e-06 1.88167642316e-06 -1.02235500146e-54
6.27225474386e-07 6.27225474386e-07 -4.08942000567e-54
2.09075158129e-07 2.09075158129e-07 -1.63576800226e-53
6.96917193763e-08 6.96917193763e-08 -6.54307200905e-53
2.32305731254e-08 2.32305731254e-08 -2.61722880362e-52
7.74352437514e-09 7.74352437514e-09 -1.04689152145e-51
2.58117479171e-09 2.58117479171e-09 -4.18756608579e-51
8.60391597238e-10 8.60391597238e-10 -1.67502643432e-50
2.86797199079e-10 2.86797199079e-10 -6.70010573727e-50
9.55990663597e-11 9.55990663597e-11 -2.68004229491e-49
3.18663554532e-11 3.18663554532e-11 -1.07201691796e-48
1.06221184844e-11 1.06221184844e-11 -4.28806767185e-48
3.54070616147e-12 3.54070616147e-12 -1.71522706874e-47
1.18023538716e-12 1.18023538716e-12 -6.86090827496e-47
3.93411795719e-13 3.93411795719e-13 -2.74436330998e-46
1.3113726524e-13 1.3113726524e-13 -1.09774532399e-45
4.37124217466e-14 4.37124217466e-14 -4.39098129597e-45
1.45708072489e-14 1.45708072489e-14 -1.75639251839e-44
4.85693574962e-15 4.85693574962e-15 -7.02557007356e-44
1.61897858321e-15 1.61897858321e-15 -2.81022802942e-43
5.39659527735e-16 5.39659527735e-16 -1.12409121177e-42
1.79886509245e-16 1.79886509245e-16 -4.49636484708e-42
5.99621697484e-17 5.99621697484e-17 -1.79854593883e-41
1.99873899161e-17 1.99873899161e-17 -7.19418375532e-41
6.66246330538e-18 6.66246330538e-18 -2.87767350213e-40
2.22082110179e-18 2.22082110179e-18 -1.15106940085e-39
7.40273700597e-19 7.40273700597e-19 -4.60427760341e-39
2.46757900199e-19 2.46757900199e-19 -1.84171104136e-38
8.22526333997e-20 8.22526333997e-20 -7.36684416545e-38
2.74175444666e-20 2.74175444666e-20 -2.94673766618e-37
9.13918148886e-21 9.13918148886e-21 -1.17869506647e-36
3.04639382962e-21 3.04639382962e-21 -4.71478026589e-36
1.01546460987e-21 1.01546460987e-21 -1.88591210636e-35
3.38488203291e-22 3.38488203291e-22 -7.54364842542e-35
1.12829401097e-22 1.12829401097e-22 -3.01745937017e-34
3.76098003645e-23 3.76098003657e-23 -1.20698374807e-33
1.25366001171e-23 1.25366001219e-23 -4.82793499227e-33
4.17886668798e-24 4.1788667073e-24 -1.93117399691e-32
1.39295549185e-24 1.3929555691e-24 -7.72469598763e-32