使用Fold计算依赖多个先前值的线性递推结果 [英] Using Fold to calculate the result of linear recurrence relying on multiple previous values

问题描述

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

I have a linear recurrence problem where the next element relies on more than just the prior value, e.g. the Fibonacci sequence. One method calculating the n^th element is to define it via a function call, e.g.

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

对于我正在处理的序列，这正是我所做的.(定义在 Module 内，所以我不会污染 Global`.)但是，我将使用 2¹⁰ - 2¹³ 点，所以当我只需要最后一个术语而不需要任何先前元素时，我担心额外的开销.我想使用 Fold 来做到这一点，但 Fold 只传递前一个结果，这意味着它对一般线性递归问题没有直接用处.

and for the sequence I'm working with, that is exactly what I do. (The definition is inside of a Module so I don't pollute Global`.) However, I am going to be using this with 2¹⁰ - 2¹³ points, so I'm concerned about the extra overhead when I just need the last term and none of the prior elements. I'd like to use Fold to do this, but Fold only passes the immediately prior result which means it is not directly useful for a general linear recurrence problem.

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

I'd like a pair of functions to replace Fold and FoldList that pass a specified number of prior sequence elements to the function, i.e.

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

我有一些东西可以做到这一点，但我在保存之前关闭了笔记本.所以，如果我自己重写它，我会发布它.

I had something that did this, but I closed the notebook prior to saving it. So, if I rewrite it on my own, I'll post it.

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

Edit: as to why I am not using RSolve or MatrixPower to solve this. My specific problem is I'm performing an n-point Pade approximant to analytically continue a function I only know at a set number of points on the imaginary axis, {z_i}. Part of creating the approximant is to generate a set of coefficients, a_i, which is another recurrence relation, that are then fed into the final relationship

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

它既不适用于 RSolve 也不适用于 MatrixPower，至少我可以看到.

which is not amenable to either RSolve nor MatrixPower, at least that I can see.

推荐答案

Can RecurrenceTable 为您执行此任务?

Can RecurrenceTable perform this task for you?

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

Find the 1000th term in a recurrence depending on two previous values:

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 进行评估，那么你可以使用条件:

If your recurrence is defined by a function f[m, n] that doesn't like to get evaluated for non-numeric m and n, then you could use Condition:

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}

这篇关于使用Fold计算依赖多个先前值的线性递推结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！