Использование 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-точечную аппроксимацию Паде , чтобы аналитически продолжить функцию, которую я знаю только в заданном количестве точек на воображаемой оси, {z _i }. Часть создания аппроксиманта состоит в том, чтобы сгенерировать набор коэффициентов, _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, тогда вы можете использовать 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}

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

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

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

{f[11], f2[11]}

Out [79] = {683, 683}

Даниэль Лихтблау Wolfram Research

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 очень полезны.

Для небольших ядер метод 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)