再帰関係

数学において、再帰関係とは、数列の番目の項が、それ以前の項の組み合わせに等しいという方程式です。多くの場合、方程式には、とは無関係なパラメータに対して、数列の前の項のみが現れます。この数は、関係の次数と呼ばれます。数列の最初の数の値が与えられている場合は、方程式を繰り返し適用することで、数列の残りの部分を計算できます。 ${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$

線型再帰では、n番目の項は前の項の線型関数と等しくなります。有名な例はフィボナッチ数列の再発で、 次数は 2 で、線型関数は前の 2 つの項を単に加算するだけです。この例は定数係数 の線型再帰です。これは、線型関数の係数 (1 および 1) が に依存しない定数であるためです。これらの再帰では、数列の一般項をの閉じた形式として表すことができます。同様に、に依存する多項式係数の線型再帰も重要です。これは、多くの一般的な基本関数と特殊関数が、係数がこのような再帰関係を満たすテイラー級数を持つためです (ホロノミック関数 を参照)。 ${\displaystyle k}$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}$$${\displaystyle k}$${\displaystyle n.}$${\displaystyle n}$${\displaystyle n}$

再帰関係を解くということは、の非再帰関数である閉じた形式の解を得ることを意味します。 ${\displaystyle n}$

再帰関係の概念は、多次元配列、つまり自然数の組によってインデックス付けされたインデックス付きファミリに拡張できます。

再帰関係は、シーケンスの各要素を前の要素の関数として表す方程式です。より正確には、直前の要素のみが関係する場合、再帰関係は次の形式になります。

${\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,}$

どこ

${\displaystyle \varphi :\mathbb {N} \times X\to X}$

は関数であり、Xはシーケンスの要素が属する集合である。任意の に対して、これは最初の要素としてを持つ一意のシーケンスを定義し、初期値と呼ばれる。^[1]${\displaystyle u_{0}\in X}$${\displaystyle u_{0}}$

インデックス 1 以上の項から始まるシーケンスを取得するための定義を変更するのは簡単です。

これは1次の再帰関係を定義します。k次 の再帰関係は次の形式を持ちます。

${\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{nk})\quad {\text{for}}\quad n\geq k,}$

ここで、はシーケンスのk個の連続する要素を含む関数です。この場合、シーケンスを定義するには k 個の初期値が必要です。${\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}$

階乗は再帰関係によって定義される

${\displaystyle n!=n\cdot (n-1)!\quad {\text{for}}\quad n>0,}$

そして初期条件

${\displaystyle 0!=1.}$

これは、次数1の多項式係数を持つ線形回帰の例であり、単純な多項式（n） は

${\displaystyle n}$

唯一の係数として。

再帰関係の例としては、次のように定義される ロジスティック写像がある。

${\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}$

与えられた定数に対して、シーケンスの動作は初期条件が変化した場合に大きく依存しますが、安定します。 ${\displaystyle r.}$${\displaystyle r,}$${\displaystyle x_{0}}$

フィボナッチ数列が満たす2次の再帰式は、定数係数を持つ同次線形再帰関係の標準的な例である（下記参照）。フィボナッチ数列は、再帰式を使って定義される。

${\displaystyle F_{n}=F_{n-1}+F_{n-2}$

初期条件付き

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

明示的には、再帰方程式は次のようになる。

${\displaystyle F_{2}=F_{1}+F_{0}}$

${\displaystyle F_{3}=F_{2}+F_{1}}$

${\displaystyle F_{4}=F_{3}+F_{2}}$

等

フィボナッチ数列は、

0、1、1、2、3、5、8、13、21、34、55、89、...

この再帰式は、以下に説明する方法で解くことができ、特性多項式の2つの根の累乗を含むビネの公式が得られる。この数列の生成関数は有理関数である。${\displaystyle t^{2}=t+1}$

${\displaystyle {\frac {t}{1-tt^{2}}}.}$

多次元再帰関係の簡単な例として、二項係数 が挙げられます。これは、要素の集合から要素を選択する方法を数えるものです。再帰関係によって計算できます。 ${\displaystyle {\tbinom {n}{k}}}$${\displaystyle k}$${\displaystyle n}$

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$

基本ケースで。この式を使用してすべての二項係数の値を計算すると、パスカルの三角形と呼ばれる無限配列が生成されます。同じ値は、再帰ではなく、加算だけでなく階乗、乗算、除算を 使用する別の式によって直接計算することもできます。${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

二項係数は一次元再帰で計算することもできます。

${\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}$

初期値で（除算は分数として表示されません。これは、分数を導入しないように、乗算の後に計算する必要があることを強調するためです）。この再帰は、2次元再帰のようにテーブルを作成する必要がなく、階乗の式のように非常に大きな整数が関係するため（使用すると、関係するすべての整数が最終結果よりも小さくなります）、コンピューターで広く使用されています。 ${\textstyle {\binom {n}{0}}=1}$${\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}$

の差分演算子は、シーケンスをシーケンスに、より一般的には関数マッピングする演算子です。これは関数表記法のように 表され、定義されます${\displaystyle \Delta ,}$

${\displaystyle (\Delta f)(x)=f(x+1)-f(x).}$

したがって、これは有限差分の特殊なケースです。

シーケンスにインデックス表記を使用する場合、定義は次のようになります。

${\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}.}$

とを囲む括弧は、通常省略され、シーケンスのインデックスnの項として理解され、要素には適用されません。${\displaystyle \Delta f}$${\displaystyle \Delta a}$${\displaystyle \Delta a_{n}}$${\displaystyle \Delta a,}$${\displaystyle \Delta }$${\displaystyle a_{n}.}$

与えられたシーケンス ${\displaystyle a=(a_{n})_{n\in \mathbb {N} },}$aの最初の違いは${\displaystyle \Delta a.}$

の2つ目の違いは、簡単な計算でわかること です ${\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).}$

${\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}$

より一般的には、 k番目の差は再帰的に次の ように定義され、${\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}$

${\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.}$

この関係は逆転することができ、

${\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}$

あk次差分方程式は、k微分方程式がk次導を関連付けるのと同じように、数列または関数のk1 次を含む方程式です。

上記の 2 つの関係により、次数kの再帰関係を次数kの差分方程式に変換したり、逆に次数kの差分方程式を次数kの再帰関係に変換したりできます。各変換は他の変換の逆であり、差分方程式の解となるシーケンスは、まさに再帰関係を満たすシーケンスです。

例えば、差分方程式

${\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0}$

は再帰関係と同等である

${\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}$

2 つの方程式が同じシーケンスによって満たされるという意味で。

シーケンスが再帰関係を満たすことと差分方程式の解であることは同等であるため、「再帰関係」と「差分方程式」という 2 つの用語は互換的に使用されることがあります。「再帰関係」の代わりに「差分方程式」を使用する例については、 有理差分方程式と行列差分方程式を参照してください。

差分方程式は微分方程式に似ており、この類似性は、微分可能方程式を解く方法を模倣して差分方程式、ひいては再帰関係を解くためによく使用されます。

積分方程式が微分方程式に関係するのと同様に、和分方程式は差分方程式に関係します。差分方程式の理論と微分方程式の理論の統一については、 時間スケール計算を参照してください。

一変数または一次元の再帰関係は、シーケンス（つまり、一次元グリッド上で定義された関数）に関するものです。多変数またはn次元の再帰関係は、-次元グリッドに関するものです。-グリッド上で定義された関数は、偏差分方程式で研究することもできます。^[2]${\displaystyle n}$${\displaystyle n}$

さらに、変数係数を持つ一般的な1次非同次線形回帰関係の場合：

${\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}$

これを解決する良い方法もあります: ^[3]

${\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

させて

${\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}$

それから

${\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}$

公式を に適用し、極限 を取ると、変数係数を持つ 1 階線形微分方程式の公式が得られます。つまり、和は積分になり、積は積分の指数関数になります。 ${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$${\displaystyle h\to 0}$

多くの同次線形回帰関係は、一般化された超幾何級数によって解くことができる。これらの特殊なケースは、直交多項式や多くの特殊関数の回帰関係につながる。例えば、

${\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}$

は次のように与えられる。

${\displaystyle J_{n}=J_{n}(z),}$

ベッセル関数、一方

${\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}$

解決されるのは

${\displaystyle M_{n}=M(n,b;z)}$

合流型超幾何級数。多項式係数を持つ線形差分方程式の解である数列は、P 再帰的と呼ばれます。これらの特定の再帰方程式については、多項式解、有理数解、または超幾何解を 求めるアルゴリズムが知られています。

1 階有理差分方程式は という形式をとります。このような方程式は、それ自体が線形に変化する別の変数の非線形変換として記述することで解くことができます。次に、標準的な方法を使用して の線形差分方程式を解くことができます。 ${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$${\displaystyle w_{t}}$${\displaystyle x_{t}}$${\displaystyle x_{t}}$

順序の線形回帰、 ${\displaystyle d}$

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}$

特性方程式は

${\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}$

再帰は安定しており、これは、固有値（つまり、特性方程式の根）が実数か複素数かに関係なく、絶対値ですべて 1 未満である場合にのみ、反復が漸近的に固定値に収束することを意味します。

一次行列差分方程式では

${\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}$

状態ベクトルと遷移行列を持つ場合、遷移行列のすべての固有値（実数か複素数かに関係なく）の絶対値が 1 未満の 場合にのみ、定常状態ベクトルに漸近収束します。${\displaystyle x}$${\displaystyle A}$${\displaystyle x}$${\displaystyle x^{*}}$${\displaystyle A}$

非線形一次回帰を考える

${\displaystyle x_{n}=f(x_{n-1}).}$

この回帰は局所的に安定であり、つまり 、 の近傍におけるの傾きが絶対値で1より小さい場合、に十分近い点から固定点に収束することを意味します。つまり、 ${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f}$${\displaystyle x^{*}}$

${\displaystyle |f'(x^{*})|<1.}$

非線形再帰には複数の固定点が存在する可能性があり、その場合、一部の固定点は局所的に安定し、他の固定点は局所的に不安定になる可能性があります。連続fの場合 、2 つの隣接する固定点が両方とも局所的に安定することはできません。

非線形回帰関係は、周期のサイクルを持つこともできる。このようなサイクルは安定しており、合成関数が ${\displaystyle k}$${\displaystyle k>1}$

${\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}$

出現回数が同じ基準に従って局所的に安定している： ${\displaystyle f}$${\displaystyle k}$

${\displaystyle |g'(x^{*})|<1,}$

サイクル上の任意の点は どこですか。${\displaystyle x^{*}}$

カオス的再帰関係では、変数は境界領域に留まりますが、固定点や吸引サイクルに収束することはありません。方程式の固定点やサイクルはいずれも不安定です。ロジスティック マップ、二項変換、テント マップも参照してください。 ${\displaystyle x}$

常微分方程式を 数値的に解く場合、通常は再帰関係に遭遇する。例えば、初期値問題を解く場合

${\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}$

オイラー法とステップサイズを用いて、値を計算する。 ${\displaystyle h}$

${\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }$

再発によって

${\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}$

線形一次微分方程式のシステムは、離散化の記事で示した方法を使用して、正確に解析的に離散化できます。

最もよく知られている差分方程式のいくつかは、個体群動態をモデル化する試みに起源を持っています。たとえば、フィボナッチ数はかつてウサギの個体群の成長のモデルとして使用されていました。

ロジスティックマップは、人口増加を直接モデル化するために、またはより詳細な人口動態モデルの出発点として使用されます。この文脈では、結合差分方程式は、2つ以上の人口の相互作用をモデル化するためによく使用されます。たとえば、宿主-寄生虫相互作用のニコルソン-ベイリーモデルは次のように表されます 。

${\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}$

${\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}$

宿主と寄生虫を時間ごとに表します。 ${\displaystyle N_{t}}$${\displaystyle P_{t}}$${\displaystyle t}$

積分差分方程式は、空間生態学にとって重要な再帰関係の一種です。これらの差分方程式やその他の差分方程式は、単化個体群のモデル化に特に適しています。

再帰関係はアルゴリズムの分析においても基本的な重要性を持つ。^{[4] [5]}アルゴリズムが問題を小さなサブ問題に分割するように設計されている場合（分割統治法）、その実行時間は再帰関係によって記述される。

簡単な例としては、最悪の場合、要素 を持つ順序付きベクトル内の要素を見つけるためにアルゴリズムが要する時間です。${\displaystyle n}$

単純なアルゴリズムでは、左から右へ、一度に 1 つの要素を検索します。最悪のシナリオは、必要な要素が最後の要素である場合です。この場合、比較の回数は になります。 ${\displaystyle n}$

より優れたアルゴリズムはバイナリ検索と呼ばれます。ただし、ソートされたベクトルが必要です。まず、要素がベクトルの中央にあるかどうかを確認します。そうでない場合は、中央の要素が探している要素より大きいか小さいかを確認します。この時点で、ベクトルの半分を破棄し、アルゴリズムを残りの半分で再度実行できます。比較の回数は次のように表されます。

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{n/2}}$

その時間計算量は となる。 ${\displaystyle O(\log _{2}(n))}$

デジタル信号処理では、再帰関係はシステム内のフィードバックをモデル化することができ、ある時点の出力が将来の時点の入力になります。したがって、再帰関係は無限インパルス応答(IIR)デジタル フィルタで発生します。

たとえば、遅延の「フィードフォワード」IIRコム フィルタの式は次のようになります。 ${\displaystyle T}$

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}$

ここで は時刻 の入力、は時刻 の出力、 は遅延信号が出力にどれだけフィードバックされるかを制御します。このことから、 ${\displaystyle x_{t}}$${\displaystyle t}$${\displaystyle y_{t}}$${\displaystyle t}$${\displaystyle \alpha }$

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}$

${\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}$

等

再帰関係、特に線形再帰関係は、理論経済学と実証経済学の両方で広く使用されています。^{[6] [7]} 特に、マクロ経済学では、一部のエージェントの行動が遅れた変数に依存する経済のさまざまな広範なセクター（金融セクター、商品セクター、労働市場など）のモデルを開発する場合があります。次に、モデルは、他の変数の過去と現在の値に基づいて、主要な変数（金利、実質GDPなど）の現在の値について解かれます。

• Batchelder, Paul M. (1967).線形差分方程式入門. Dover Publications.
• ミラー、ケネス S. (1968)。線形差分方程式。WA ベンジャミン。
• フィルモア、ジェイ P. 、マルクス、モリス L. (1968)。「線形再帰シーケンス」。SIAM Rev. Vol. 10、第 3 号。pp. 324–353。JSTOR  2027658。
• ブルーソー、アルフレッド (1971)。線形再帰とフィボナッチ数列。フィボナッチ協会。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第2版。MIT Press and McGraw-Hill、1990年。ISBN 0-262-03293-7。第4章：再帰、pp. 62–90。 
• グラハム、ロナルド L.、クヌース、ドナルド E.、パタシュニック、オーレン (1994)。『具体的な数学: コンピュータサイエンスの基礎(第 2 版)』。アディソン・ウェズリー。ISBN 0-201-55802-5。
• Enders, Walter (2010). Applied Econometric Times Series (第3版). 2014-11-10にオリジナルからアーカイブ。
• ポール・カル、メアリー・フラヒヴ、ロビー・ロブソン（2005年）。『差分方程式：ウサギからカオスへ』。シュプリンガー。ISBN 0-387-23234-6。第7章。
• ジャック、イアン (2006)。経済とビジネスのための数学(第 5 版)。プレンティス ホール。pp. 551–568。ISBN 0-273-70195-9。第9.1章: 差分方程式。
• Minh, Tang; Van To, Tan (2006). 「生成関数を使用した線形不同次再帰方程式の解法」(PDF)。Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06 。 pp. 399–404。 2016-03-04 にオリジナル(PDF)からアーカイブ。 2014-08-07に取得。
• ポリアニン、アンドレイ D.「差分と関数方程式：正確な解」。EqWorld - 数式の世界。
• ポリアニン、アンドレイ D.「差分と関数方程式：方法」。EqWorld - 数式の世界。
• Wang, Xiang-Sheng; Wong, Roderick (2012). 「再帰関係による直交多項式の漸近解析」. Anal. Appl . 10 (2): 215–235. arXiv : 1101.4371 . doi :10.1142/S0219530512500108. S2CID  28828175.

• 「再帰関係」、数学百科事典、EMS Press、2001 [1994]
• Weisstein、Eric W.「再帰方程式」。MathWorld。
• 「OEIS インデックス レック」。 OEIS は、数千の線形回帰の例を、順序 (項の数) とシグネチャ (定数係数の値のベクトル) でソートしたインデックスです。