線型回帰数列

数学において、p-階の線型回帰数列（せんけいかいきすうれつ、英: linear recurrence sequence; 線型循環数列）とは、各項がある可換体 K（典型的には複素数体 C や実数体 R）に値をとる数列であって、体 K の p 個のスカラー a0, a1, …, ap−1 (a0 ≠ 0) が存在して、任意の n ≥ n0 に対して、p-階の線型漸化式 u n + p = a 0 u n + a 1 u n + 1 + ⋯ + a p − 1 u n + p − 1 {\displaystyle u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\dotsb +a_{p-1}u_{n+p-1}} を満たすものの総称である。より一般には、係数 ai は n の函数とすることもできるが、本項においては基本的に定数係数の場合を扱う。このような数列は、最初の p 項（初期値あるいは初期条件と呼ばれる）が決まれば、残りの項は漸化式に従ってすべて一意に決定される。この数列または漸化式（離散力学系）が安定であるとは、任意の初期値集合に対して n を無限大に飛ばした極限（定常状態）が存在するときに言う。 高階の線型回帰列を調べることは線型代数学に属する問題である。そのような列の一般項は、列に付随する特性多項式と呼ばれる多項式の根が求まれば、それらによって記述することができる。上記の漸化式を満たす列に付随する特性多項式は P ( X ) = X p − ∑ i = 0 p − 1 a i X i = X p − a p − 1 X p − 1 − a p − 2 X p − 2 − ⋯ − a 1 X − a 0 {\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}=X^{p}-a_{p-1}X^{p-1}-a_{p-2}X^{p-2}-\dots -a_{1}X-a_{0}} で与えられ、特性多項式の根は特性根と呼ばれる。特性多項式の次数は漸化式の階数に等しい。特に二階の回帰列の場合には、特性多項式の次数も 2 であり、その根の様子は判別式を用いて知ることができる。故に、二階線型回帰列は最初の二項の値のみから初等的な算術演算（和・差・積・冪）と正弦・余弦函数（考える体が実数体の場合）を用いて記述することができる。この種の数列の例には、よく知られたフィボナッチ数列があり、その各項は黄金比の冪を使って書くことができる。 一般に差分方程式は様々な文脈で用いられ、例えば経済学において、国内総生産やインフレ率、為替レートなどの時間発展する変数をモデル化する。差分方程式をそのような時系列のモデル化に用いるのは、それら変数の値が離散的間隔でのみ測られるからである。そのような応用において、線型差分方程式は自己回帰モデル (AR) や AR とその他の特徴を組み合わせたベクトル自己回帰（英語版） (VAR) および自己回帰移動平均モデル (ARMA) など、推計学的な言葉でモデル付けられる。 一般に体 K 上の（函数係数）p-階線型差分方程式 (linear difference equation) あるいは線型漸化式 (linear recurrence relation) とは、数列 (fn)n∈N に関する漸化式で、n ≥ p なるとき ∑ i = 0 p a i ( n ) f n − i = b ( n ) ( ∀ n ∈ K , a p ( n ) ≠ 0 ) {\displaystyle \sum _{i=0}^{p}a_{i}(n)f_{n-i}=b(n)\quad (\forall n\in \mathbb {K} ,a_{p}(n)\neq 0)} の形に書けるものを言う。ここに、各係数函数 ai および函数 b は、自然数 n を変数とする K-値函数である。すべての ai, b が n に依らない一定の値をとるとき、漸化式は定数係数であるという。 n ≥ p なる全ての n に対して、上記の漸化式を満足する数列 (fn)n∈N をこの差分方程式の解と呼ぶ。解は明らかに最初の p 項の値によって特徴付けられる。 任意の n に対して b(n) = 0 のとき、差分方程式は斉次 (homogeneous) であるといい、そうでないとき非斉次 (inhomogeneous, non-homogeneous) と言う。任意の n に対して fn = 0 となる数列は明らかに斉次方程式を満たし、斉次方程式の自明解と呼ばれる。 一般性を失うことなく a0 = −1 として、別な表現 f n = a 1 ( n ) f n − 1 + a 2 ( n ) f n − 2 + ⋯ + a p ( n ) f n − p − b ( n ) = ∑ i = 1 p a i ( n ) f n − i − b ( n ) {\displaystyle f_{n}=a_{1}(n)f_{n-1}+a_{2}(n)f_{n-2}+\dots +a_{p}(n)f_{n-p}-b(n)=\sum _{i=1}^{p}a_{i}(n)f_{n-i}-b(n)} を与えることができる。これは fn が直前の p 項から決定されるという形になっている。 F, G が同じ斉次方程式の解ならば、αF + βG (α, β ∈ K) も同じ斉次方程式の解である F, G が同じ非斉次方程式の解ならば、F − G は付随する斉次方程式の解になる。 非斉次方程式の解の一つ F が既知（特殊解）ならば、非斉次方程式の他の解は付随する斉次方程式の一般解 G との和として書ける。 b ≠ 0 として非斉次の定数係数方程式 y n = a 1 y n − 1 + ⋯ + a p y n − p + b {\textstyle y_{n}=a_{1}y_{n-1}+\cdots +a_{p}y_{n-p}+b} を解くには、斉次形に変形するのが便利である。そのためにはまず、n を無限大に飛ばしたときの定常値 y*（それはこの線型変換の不動点である）を求めることが必要である。これは上記の方程式における任意の yn を y* と置いて解けば y ∗ = b 1 − a 1 − ⋯ − a p {\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{p}}}} と得られる（この分母が 0 ならば、定常値は存在しない）。 定常値がわかれば、上記の差分方程式は定常値からの各項の偏差に関する方程式 ( y n − y ∗ ) = a 1 ( y n − 1 − y ∗ ) + ⋯ + a p ( y n − p − y ∗ ) {\displaystyle (y_{n}-y^{*})=a_{1}(y_{n-1}-y^{*})+\dotsb +a_{p}(y_{n-p}-y^{*})} に書き直せて、これは非斉次項を持たない。xn ≔ yn − y* と置けばより簡潔に x n = a 1 x n − 1 + ⋯ + a p x n − p {\textstyle x_{n}=a_{1}x_{n-1}+\dotsb +a_{p}x_{n-p}} となる。 定常でない場合には、方程式 y n = a 1 y n − 1 + ⋯ + a p y n − p + b {\textstyle y_{n}=a_{1}y_{n-1}+\dotsb +a_{p}y_{n-p}+b} と添字を一つずらした方程式 y n − 1 = a 1 y n − 2 + ⋯ + a p y n − ( p + 1 ) + b {\textstyle y_{n-1}=a_{1}y_{n-2}+\dotsb +a_{p}y_{n-(p+1)}+b} から b を消去すれば y t − a 1 y t − 1 − ⋯ − a n y t − n = y t − 1 − a 1 y t − 2 − ⋯ − a n y t − ( n + 1 ) {\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}} が、もとの方程式より階数が一つ大きいものの斉次方程式として得ることができる。 一階の斉次線型漸化式 u n + 1 = q u n {\displaystyle u_{n+1}=q\,u_{n}} の解は幾何数列と呼ばれる。その一般項は u n = u n 0 q n − n 0 {\textstyle u_{n}=u_{n_{0}}q^{n-n_{0}}} で与えられる。 非斉次一階線型漸化式 un+1 = q⋅un + r の解は算術幾何数列である。 係数体 K の二つのスカラー a および b ≠ 0 を固定して、線型漸化式 u n + 2 = a u n + 1 + b u n {\displaystyle u_{n+2}=au_{n+1}+bu_{n}} (R) を満たす列の一般項が、K における特性多項式の根の値に従って、以下のように与えられることが示される。 λ r 1 n + μ r 2 n {\displaystyle \lambda r_{1}^{n}+\mu r_{2}^{n}} （ただし、r1, r2 は多項式 X2 − aX − b の相異なる二根） ( λ + μ n ) r 0 n {\displaystyle (\lambda +\mu n)r_{0}^{n}} （ただし、r0 は多項式 X2 − aX − b の二重根） また、λ と μ は列の最初の二項によって決まる, 初期パラメータである。 前者についてはさらに、多項式 X2 − aX − b の二根 r1, r2 が互いに共軛な複素数 ρeiθ, ρe−iθ であるとき、数列の一般項を ρ n ( A cos ⁡ ( n θ ) + B sin ⁡ ( n θ ) ) {\displaystyle \rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))} と書くことができる。ただし、A, B ∈ K は数列の最初の二項から決まるパラメータである。 ここまで数列はある番号 n0 から始まるものとして扱ったが、以下、一般性を失うことなく数列は自然数全体の成す集合 N 上で定義されるものと仮定してよい。実際、数列 (un) が n0 からしか定義されていないとき、N 上で定義される数列 (vn)n∈N を vn = un+n0 によって定めることができる。 基本的な考え方は線型漸化式 (R) を満たす幾何数列を求めること、即ち数列 (rn)n∈N が (R) を満たすようなスカラー r を見つけることである。そうするとこの問題が、二次方程式 r2 − ar − b = 0 を解くことと等価であることが容易に理解される。多項式 r2 − ar − b はこの数列の特性方程式と呼ばれ、その判別式は Δ = a2 − 4b で与えられる。特性多項式の根の数によって、いくつかの場合が区別されねばならない。 r1 と r2 が相異なる二根であるとき、数列 (r n 1 )n∈N および (r n 2 )n∈N はともに漸化式 (R) を満たすから、漸化式の線型性から同様に、一般項が λr n 1  + μr n 2  の数列もすべて (R) を満たす。ここから (R) を満足する数列を全て決定するには、そのような数列が初期条件 u0, u1 によって完全に決まることから、λ, μ に関する次の方程式系 { λ + μ = u 0 λ r 1 + μ r 2 = u 1 {\displaystyle {\begin{cases}\lambda +\mu =u_{0}\\\lambda r_{1}+\mu r_{2}=u_{1}\end{cases}}} を解けば十分である。しかし、この系の行列式 r2 − r1 は常に 0 ではないから、(R) を満たす数列は常に (r n 1 )n∈N および (r n 2 )n∈N の線型結合として表される。このような状況は、数列が実数値で Δ > 0 のときや、数列が複素数値で判別式が 0 でないときに起きる。 判別式が 0 のときは、根が r0 一つしかなく、(R) を満たす幾何数列が (λr n 0 ) しか出てこないから、状況が全く変わってくる。考え方としては、一般項が λn⋅r n 0  となる数列 (un)n∈N が (R) を満足するような数列 (λn)n∈N を見つければよい。これは「定数変化法」と呼ばれる手法である。まずは、r0 が 0 でない限り (λn)n∈N が存在することを確かめよう。(un)n∈N に対する漸化式は (λn)n∈N に関する漸化式 r 0 2 λ n + 2 = a r 0 λ n + 1 + b λ n {\displaystyle r_{0}^{2}\lambda _{n+2}=ar_{0}\lambda _{n+1}+b\lambda _{n}} に書き直すことができる。a2 + 4b = 0 と r0 = a/2 となる事実を用いれば、算術数列の定義式 λ n + 2 − λ n + 1 = λ n + 1 − λ n {\displaystyle \lambda _{n+2}-\lambda _{n+1}=\lambda _{n+1}-\lambda _{n}} が得られるから、従って数列 (λn)n∈N は一般項が λn = λ + μn の算術数列になる。 故に、(R) を満たす数列 (un) の一般項は u n = ( λ + μ n ) r 0 n {\displaystyle u_{n}=(\lambda +\mu n)r_{0}^{n}} となる。この結果は、数列が実数値でも複素数値でも特性多項式の判別式が 0 ならば適用できる。 特性多項式が実係数で、その判別式が真に負であるとき、この二次方程式の二つの根は相異なり、C において共軛である。それを r 1 = ρ e i θ , r 2 = ρ e − i θ {\displaystyle r_{1}=\rho e^{i\theta },\quad r_{2}=\rho e^{-i\theta }} とすると、これは上記の二つの場合の前者であるから、(R) を満足する任意の複素数列は一般項が λ, μ を複素パラメータとして λρeinθ + μρe−inθ の形に書ける。パラメータを A = λ + μ, B = i(λ − μ) に取り換えて、一般項を un = ρn(A⋅cos(nθ) + B⋅sin(nθ)) と書き直すこともできる。 従って、(R) を満足する実数列の場合にも一般項を u n = ρ n ( A cos ⁡ ( n θ ) + B sin ⁡ ( n θ ) ) {\displaystyle u_{n}=\rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))} と書くことができる。実際、（先天的に複素数として与えた）パラメータ A, B が実数ならば、数列も実数値となるし、逆に、u0 = A, u1 = Aρθ⋅cos(θ) + Bρθ⋅sin(θ) で ρθ⋅sin(θ) ≠ 0 に気を付ければ、u0, u1 が実数ならば A, B もそうであることがわかる。 p-階の線型漸化式 u n + p = a 0 u n + a 1 u n + 1 + ⋯ + a p − 1 u n + p − 1 {\displaystyle u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}} (Rp) を満たす K-値数列全体の成す集合 ERp は K-値数列全体の成すベクトル空間の線型部分空間となることが、漸化式の線型性から従う。 さらにこの部分空間が p-次元となることもわかる。実際、ERp と Kp との間のベクトル空間の同型が、ERp の元 (un)n∈N に対し最初の p-項からなるベクトル (u0, u1, …, up) を対応させることで与えられる。故に、(Rp) を満たす p 個の線型独立な列が得られれば、ERp がそれら p 個の線型独立系から生成されることがわかる。 一般項を求めるために、p-階回帰列を Kp に値をとる数列に読み替える。即ち、各数列 (un)n∈N ∈ ERp に対し、Kp-値数列 (Un)n∈N を U n = ( u n , u n + 1 , … , u n + p − 1 ) {\displaystyle U_{n}=(u_{n},u_{n+1},\ldots ,u_{n+p-1})} によって与える。すると、(un)n∈N に対する漸化式 (Rp) は (Un)n∈N に対する一階の線型漸化式 Un+1 = AUn に帰着される。ただし A は A = ( 0 1 0 ⋯ 0 0 0 1 ⋯ 0 ⋮ ⋱ ⋱ ⋯ ⋮ 0 ⋯ ⋯ 0 1 a 0 a 1 ⋯ ⋯ a p − 1 ) {\displaystyle A={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\ddots &\ddots &\cdots &\vdots \\0&\cdots &\cdots &0&1\\a_{0}&a_{1}&\cdots &\cdots &a_{p-1}\end{pmatrix}}} なる行列（数列の特性多項式の同伴行列）である。故に数列 (Un)n∈N の一般項は Un = AnU0 で与えられる。 これで問題は解決したようにも思えるが、現実的には A の冪 An, … の計算が容易でないことがしばしばあり、むしろ直接に ERp の基底を求めたほうがよいこともある。 行列 A の特性多項式は P ( X ) = X p − ∑ i = 0 p − 1 a i X i {\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}} で、これは (Rp) を満たす数列 (un)n∈N の特性多項式に他ならない。 数列 (un)n∈N を vn = un+1 を満たす数列 (vn)n∈N に対応させる変換 f は線型写像であることに注意しよう。数列 u = (un)n∈N が (Rp) を満たすという条件は、P(f)u = 0 と書き直せるから、空間 ERp は線型写像 P(f) の核に一致する。多項式 P が K で可約なとき（K = C のときは常にそうだが）、k 個の根 r1, r2, …, rk と k 個の冪指数 α1, α2, …, αk を用いて P = ∏ i = 1 k ( X − r i ) α i {\displaystyle P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}} と書けているとすると、P(f) の核は (f − ri⋅id)αi の核の直和に表される。従って、ERp の基底を決定するには、これらの核それぞれの基底を知れば十分である。 多項式 Q の次数が αi より真に小さいとき、一般項が Q(n)⋅r n i  であるような任意の数列が (f − ri⋅id)αi の核に入ることが、αi に関する帰納法で示せる。j = 0, …, αi − 1 に対する数列 (nj⋅r n i ) は αi に対応する直和因子における αi 個の元からなる線型独立系であり、さらに i = 1, …, k として ERp の α1 + α2 + ⋯ + αk = p 個の元からなる線型独立系となるから、これは p-次元ベクトル空間 ERp の基底を成すことが確かめられる。従って、ERp の任意の元は、αi よりも真に低い次数を持つ Q に対する Q(n)⋅r n i  を一般項とする数列の和として表される。 特性多項式が一次式の積 (X − r1)(X − r2) に書けるなら、前節の多項式 Q は次数 0 であり、ER2 の任意の元は一般項が λ1⋅r n 1  + λ2⋅r n 2  の数列となる。 特性多項式の因数分解が (X − r0)2 なら、前節の多項式 Q の次数は 1 であり、ER2 の任意の元は一般項が (λ n 1  + λ2)⋅r n 0  の数列となる。 線型回帰数列 x n = c 1 λ 1 n + ⋯ + c p λ p n {\displaystyle x_{n}=c_{1}\lambda _{1}^{n}+\cdots +c_{p}\lambda _{p}^{n}} において、実根に対応する一つの項が n を無限大に飛ばす極限で 0 に収束するのは、その実特性根の絶対値が 1 より小さいときである。絶対値が 1 に等しいときは、特性根が +1 ならば n の増加に伴って一定であり、−1 のときは二つの値を行き来する。絶対値が 1 より大きい特性根の項は n とともに発散する。同様に、互いに複素共軛な特性根に対応する二項は、それら根の絶対値が 1 より小さいとき、減衰振動しながら 0 に収束する。絶対値が 1 に等しいときは一定振幅で振動し、また絶対値が 1 より大きければ際限なく大きくなりつつ振動する。 したがって、この数列 xn が n の増加に伴って 0 に収束するの（安定の場合）は、全ての特性根の絶対値が 1 より小さいことである。 最大の根が絶対値 1 ならば、0 に収束することも無限大に発散することもない。絶対値 1 の根がすべて正の実根ならば、xn はそのような根に対応する係数 ci の和に収束する。安定の場合と異なり、この収束値は初期条件に依存し、始点が異なれば長い時間の後異なる点へ導かれる。何れかの根が –1 のときは、それに対応する項は永続的に二値間の振動として寄与する。絶対値 1 の複素根があれば、xn は定振幅の変動を続ける。 最後に、何れかの特性根が 1 より大きい絶対値を持てば xn は無限大に発散するか、絶対値を大きくしながら正の値と負の値の間を振動する。 イサイ・シューアの定理が述べるところによれば、任意の根の絶対値が 1 より小さいこと（安定の場合）の必要十分条件は、行列式の特定の並びが全て正となることである[訳語疑問点] 非斉次の線型差分方程式を上で述べたように斉次化したならば、もとの非斉次方程式の安定性と循環性は斉次化した方程式でも同じで、安定の場合の収束先は 0 でなく定常値 y* になる。