使用 Fold 依赖多个先前值来计算线性递归的结果

Question

我有一个线性递归问题，其中下一个元素不仅仅依赖于先前的值，例如斐波那契序列。计算第 n^th 元素的一种方法是通过函数调用来定义它，例如

Fibonacci[0] = 0; Fibonacci[1] = 1;
Fibonacci[n_Integer?Positive] := Fibonacci[n] + Fibonacci[n - 1]

，对于我正在使用的序列，这正是我所做的。 （定义位于 Module 内部，因此我不会污染 Global`。）但是，我将将此与 2¹⁰ - 2¹³ 点，因此当我只需要最后一项而不需要任何先前元素时，我担心额外的开销。我想使用 Fold 来执行此操作，但 Fold 只传递前一个结果，这意味着它对于一般线性递归问题并不直接有用。

我想要一对函数来替换 Fold 和 FoldList ，将指定数量的先前序列元素传递给函数，即

In[1] := MultiFoldList[f, {1,2}, {3,4,5}] (* for lack of a better name *)
Out[1]:= {1, 2, f[3,2,1], f[4,f[3,2,1],2], f[5,f[4,f[3,2,1],2],f[3,2,1]]}

我有这样做的东西，但我在保存之前关闭笔记本。所以，如果我自己重写它，我会发布它。

编辑：至于为什么我不使用RSolve或MatrixPower来解决这个问题。我的具体问题是我正在执行 n 点 Pade 近似 分析地继续一个函数，我只知道虚轴上的一组点，{z_i}。创建近似值的一部分是生成一组系数 a_i，这是另一种递归关系，然后将其输入到最终关系中，

A[n+1]== A[n] + (z - z[[n]]) a[[n+1]] A[n-1]

该关系不适合 RSolve 也不是 MatrixPower，至少我可以看到。

Answer 1

RecurrenceTable 可以为您执行此任务吗？

根据之前的两个值查找循环中的第 1000 项：

In[1]:= RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], 
  a[1] == a[2] == 1}, a, 
   {n, {1000}}]

Out[1]= {4346655768693745643568852767504062580256466051737178040248172\
9089536555417949051890403879840079255169295922593080322634775209689623\
2398733224711616429964409065331879382989696499285160037044761377951668\
49228875}

编辑：如果您的循环是由函数 f[m, n] 定义的，而该函数不喜欢得到评估非数字 m 和 n，那么您可以使用条件：

In[2]:= f[m_, n_] /; IntegerQ[m] && IntegerQ[n] := m + n

递归以 f 表示的表格：

In[3]:= RecurrenceTable[{a[n] == f[a[n - 1], a[n - 2]], 
  a[1] == a[2] == 1}, a, {n, {1000}}]

Out[3]= {4346655768693745643568852767504062580256466051737178040248172\
9089536555417949051890403879840079255169295922593080322634775209689623\
2398733224711616429964409065331879382989696499285160037044761377951668\
49228875}

Answer 2

多个折叠列表可能很有用，但它不是评估大型输入的线性递归的有效方法。有几种替代方法是使用 RSolve 或矩阵幂乘以初始值向量。

以下是适用于第 n 项等于 n-1 项加两倍 n-2 项的示例的这些方法。

f[n_] =  f[n] /. RSolve[{f[n] == f[n - 1] + 2*f[n - 2], f[1] == 1, f[2] == 1},
  f[n], n][[1]]

输出[67]= 1/3 (-(-1)^n + 2^n)

f2[n_Integer] := Last[MatrixPower[{{0, 1}, {2, 1}}, n - 2].{1, 1}]

{f[11], f2[11]}

输出[79]= {683, 683}

Daniel Lichtblau
沃尔夫勒姆研究公司

Answer 3

几乎是一个令人费解的笑话，但您可以使用 NestWhileList 的副作用 性能

fibo[n_] := 
  Module[{i = 1, s = 1}, 
   NestWhileList[ s &, 1, (s = Total[{##}]; ++i < n) &, 2]];  

还不错：

In[153]:= First@Timing@fibo[10000]
Out[153]= 0.235  

通过将最后一个 2 更改为任何整数，您可以将最后 k 个结果传递给您的函数（在本例中为 Total[]）。

Answer 4

LinearRecurrence 和 RecurrenceTable 非常有用。

对于小内核，Daniel 给出的 MatrixPower 方法是最快的。

对于某些问题，这些可能不适用，您可能需要自己解决。

我将使用 Nest，因为我相信这适合解决这个问题，但类似的构造也可以用于 Fold。

一个具体的例子，斐波那契数列。这可能不是最干净的，但我相信随着我的继续，你会看到这个实用程序。

fib[n_] :=
  First@Nest[{##2, # + #2} & @@ # &, {1, 1}, n - 1]

fib[15]

Fibonacci[15]

在这里，我使用 Apply (@@)，这样我就可以使用 #、#2 等来寻址元素。 ，而不是 #[[1]] 等。我使用 SlotSequence 从旧列表中删除第一个元素，并将其 Sequence 放入同时新名单。

如果您要立即对整个列表进行操作，那么简单的 Append[Rest@#, ... 可能会更好。任何一种方法都可以很容易地推广。例如，一个简单的线性递归实现是

 lr[a_, b_, n_Integer] := First@Nest[Append[Rest@#, a.#] &, b, n - 1]

 lr[{1,1}, {1,1}, 15]

（内核与内置的 LinearRecurrence 的顺序相反）