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])

我收到的输出是：

0.3333333333333333
0.11111111111111094
0.03703703703703626
0.012345679012342514
0.004115226337435884
0.0013717421124321456
0.00045724737062478524
0.00015241578946454185
5.0805260179967644e-05
1.6935074827137338e-05
5.644977344304949e-06
1.8814687224716613e-06
6.263946716372672e-07
2.0575194713260943e-07
5.63988753916179e-08
-2.994080281313502e-08
-2.049419793790756e-07
-8.481608402251475e-07
-3.402107668470205e-06
-1.361158544307069e-05
-5.444739336201271e-05
-0.00021778992397796082
-0.0008711598127551465
-0.0034846392899683535
-0.013938557172856001
-0.05575422869575153
-0.22301691478444863
-0.8920676591382753
-3.5682706365532617
-14.2730825462131
-57.092330184852415
-228.36932073940963
-913.4772829576384
-3653.909131830553
-14615.63652732221
-58462.546109288836
-233850.18443715532
-935400.7377486213
-3741602.950994485
-14966411.80397794
-59865647.21591176
-239462588.86364704
-957850355.4545882
-3831401421.8183527
-15325605687.27341
-61302422749.09364
-245209690996.37457
-980838763985.4983
-3923355055941.993

这仅对于前 13 个打印值是正确的。我提供的证据是 x _n = 3 ^-n，这在很大程度上与我的脚本的值不匹配。我的计算有问题吗？我已经看不到了。

Answer 1

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

\n\n

Jean-Fran\xc3\xa7ois 关于浮点累积错误的观点是正确的。然而，该fraction模块似乎无法将多个Fraction对象相乘，因此所有数值必须在分数对象中声明。感谢他使用正确的模块来解决这个问题。

\n\n

确切答案

\n\n

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

\n\n

打印输出显示计算结果与证明答案完全匹配。

\n\n

不准确但有启发性的答案

\n\n

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

\n\n

import math\nfrom decimal import *\ngetcontext().prec = 60\n\ndef printRecurrence():\n    x = [0]*51 #initialize list of x values\n    x[0] = Decimal(1)\n    x[1] = Decimal(1)/Decimal(3)\n    for i in range(1, 50):\n        x[i+1] = (Decimal(13)/Decimal(3))*x[i] - (Decimal(4)/Decimal(3))*x[i-1]\n        print(float(x[i+1]), 3**(-(i+1)), float(x[i+1]-Decimal(3)**(-(i+1))))\n\nprintRecurrence()\n

\n\n

与 Jean-Fran\xc3\xa7ois 的答案一样，我打印了结果、3**-n 的计算值和差值。人们可以调整精度级别getcontext().prec来查看对结果的影响。

\n\n

0.111111111111 0.111111111111 -1e-60\n0.037037037037 0.037037037037 -4e-60\n0.0123456790123 0.0123456790123 -1.57e-59\n0.00411522633745 0.00411522633745 -6.243e-59\n0.00137174211248 0.00137174211248 -2.4961e-58\n0.000457247370828 0.000457247370828 -9.984e-58\n0.000152415790276 0.000152415790276 -3.993577e-57\n5.08052634253e-05 5.08052634253e-05 -1.59742978e-56\n1.69350878084e-05 1.69350878084e-05 -6.38971879e-56\n5.64502926948e-06 5.64502926948e-06 -2.5558875048e-55\n1.88167642316e-06 1.88167642316e-06 -1.02235500146e-54\n6.27225474386e-07 6.27225474386e-07 -4.08942000567e-54\n2.09075158129e-07 2.09075158129e-07 -1.63576800226e-53\n6.96917193763e-08 6.96917193763e-08 -6.54307200905e-53\n2.32305731254e-08 2.32305731254e-08 -2.61722880362e-52\n7.74352437514e-09 7.74352437514e-09 -1.04689152145e-51\n2.58117479171e-09 2.58117479171e-09 -4.18756608579e-51\n8.60391597238e-10 8.60391597238e-10 -1.67502643432e-50\n2.86797199079e-10 2.86797199079e-10 -6.70010573727e-50\n9.55990663597e-11 9.55990663597e-11 -2.68004229491e-49\n3.18663554532e-11 3.18663554532e-11 -1.07201691796e-48\n1.06221184844e-11 1.06221184844e-11 -4.28806767185e-48\n3.54070616147e-12 3.54070616147e-12 -1.71522706874e-47\n1.18023538716e-12 1.18023538716e-12 -6.86090827496e-47\n3.93411795719e-13 3.93411795719e-13 -2.74436330998e-46\n1.3113726524e-13 1.3113726524e-13 -1.09774532399e-45\n4.37124217466e-14 4.37124217466e-14 -4.39098129597e-45\n1.45708072489e-14 1.45708072489e-14 -1.75639251839e-44\n4.85693574962e-15 4.85693574962e-15 -7.02557007356e-44\n1.61897858321e-15 1.61897858321e-15 -2.81022802942e-43\n5.39659527735e-16 5.39659527735e-16 -1.12409121177e-42\n1.79886509245e-16 1.79886509245e-16 -4.49636484708e-42\n5.99621697484e-17 5.99621697484e-17 -1.79854593883e-41\n1.99873899161e-17 1.99873899161e-17 -7.19418375532e-41\n6.66246330538e-18 6.66246330538e-18 -2.87767350213e-40\n2.22082110179e-18 2.22082110179e-18 -1.15106940085e-39\n7.40273700597e-19 7.40273700597e-19 -4.60427760341e-39\n2.46757900199e-19 2.46757900199e-19 -1.84171104136e-38\n8.22526333997e-20 8.22526333997e-20 -7.36684416545e-38\n2.74175444666e-20 2.74175444666e-20 -2.94673766618e-37\n9.13918148886e-21 9.13918148886e-21 -1.17869506647e-36\n3.04639382962e-21 3.04639382962e-21 -4.71478026589e-36\n1.01546460987e-21 1.01546460987e-21 -1.88591210636e-35\n3.38488203291e-22 3.38488203291e-22 -7.54364842542e-35\n1.12829401097e-22 1.12829401097e-22 -3.01745937017e-34\n3.76098003645e-23 3.76098003657e-23 -1.20698374807e-33\n1.25366001171e-23 1.25366001219e-23 -4.82793499227e-33\n4.17886668798e-24 4.1788667073e-24 -1.93117399691e-32\n1.39295549185e-24 1.3929555691e-24 -7.72469598763e-32\n

\n