漸化式

階乗は漸化式によって定義される

${\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つの根のべき乗を含むビネの公式が得られます。$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,}$

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

1 変数または 1 次元の漸化式は、数列 (つまり、1 次元グリッド上で定義された関数) に関するものです。多変数または n 次元の漸化式は、${\displaystyle n}$次元グリッド。関数は上で定義されます。${\displaystyle n}$-グリッドは偏差分方程式を用いて解析することもできる。^{[ 5 ]}

さらに、可変係数を持つ一般的な一次非同次線形漸化式については、次のようになる。

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

それを解決する良い方法もあります: ^{[ 6 ]}

${\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)}$

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

多くの同次線形漸化式は、一般化超幾何級数を用いて解くことができる。これらの特殊な場合から、直交多項式や多くの特殊関数の漸化式が得られる。例えば、の解は

${\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-再帰的と呼ばれます。これらの特定の再帰方程式については、多項式、有理数、または超幾何解を求めるアルゴリズムが知られています。

さらに、定数係数を持つ一般的な非同次線形漸化式については、パラメータの変化に基づいて解くことができる。^{[ 7 ]}

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未満である場合に限る。

1次行列差分方程式において

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

状態ベクトル付き${\displaystyle x}$遷移行列${\displaystyle A}$、${\displaystyle x}$定常状態ベクトルに漸近的に収束する${\displaystyle x^{*}}$遷移行列のすべての固有値が${\displaystyle A}$（実数か複素数かを問わず）絶対値が1未満である 。

非線形一次漸化式を考える

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

この再帰は局所的に安定しており、固定点に収束する。${\displaystyle x^{*}}$十分に近い地点から${\displaystyle x^{*}}$傾きが${\displaystyle f}$ 近隣では${\displaystyle x^{*}}$絶対値が1より小さい、つまり、

${\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}$同じ基準によれば、timesは局所的に安定している。

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

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

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

最もよく知られている差分方程式のいくつかは、個体群動態をモデル化しようとする試みに端を発している。例えば、フィボナッチ数はかつてウサギの個体群増加のモデルとして用いられていた。

ロジスティック写像は、個体群増加を直接モデル化するためにも、より詳細な個体群動態モデルの出発点としても使用されます。この文脈では、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}$。

積分差分方程式は、空間生態学において重要な漸化式の一種である。これらの差分方程式は、特に年1世代の個体群をモデル化するのに適している。

アルゴリズムの解析においても、漸化式は根本的に重要である。^{[ 8 ] [ 9 ]}アルゴリズムが問題をより小さな部分問題に分割するように設計されている場合（分割統治）、その実行時間は漸化式によって記述される。

簡単な例としては、アルゴリズムが順序付きベクトル内の要素を見つけるのにかかる時間があり、${\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}}$

等

漸化式、特に線形漸化式は、理論経済学と実証経済学の両方で広く使用されています。^{[ 10 ] [ 11 ]} 特にマクロ経済学では、経済のさまざまな広範なセクター（金融セクター、財セクター、労働市場など）のモデルを開発することができ、その中で一部のエージェントの行動は過去の変数に依存します。その後、モデルは、他の変数の過去および現在の値を使用して、主要変数（金利、実質GDPなど）の現在の値について解かれます。

• バッチェルダー、ポール M. (1967).線形差分方程式入門. ドーバー出版.
• ミラー、ケネス・S. (1968).線形差分方程式. WAベンジャミン.
• フィルモア、ジェイ P.、マルクス、モリス L. (1968)。「線形再帰シーケンス」。SIAM Rev. Vol. 10 、no. 3 、 pp. 324–353。JSTOR 2027658。  
• ブロソー、アルフレッド（1971）。線形再帰とフィボナッチ数列。フィボナッチ協会。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、1990年。ISBN 0-262-03293-7第4章：再発、62～90ページ 。
• グラハム、ロナルド・L.、クヌース、ドナルド・E.、パタシュニク、オレン（1994）。『具体数学：コンピュータ科学の基礎』（第2 版）。アディソン・ウェスリー。ISBN 0-201-55802-5。
• エンダース、ウォルター（2010）。応用計量経済学時系列（第3 版）。 2014年11月10日にオリジナルからアーカイブ済み。
• Cull, Paul; Flahive, Mary ; Robson, Robbie (2005).差分方程式：ウサギからカオスへ. Springer. ISBN 0-387-23234-6。第7章
• ジャック、イアン（2006）。経済学とビジネスのための数学（第5 版）。プレンティス・ホール。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 .