線型回帰数列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

数学において、p-階の線型回帰数列(せんけいかいきすうれつ、: linear recurrence sequence)または線型循環数列(せんけいじゅんかんすうれつ)とは、各項がある可換体 K(典型的には CR)に値をとる数列であって、体 Kp-個のスカラー a0, a1, …, ap−1 (a0 ≠ 0) を固定するとき、任意の nn0 に対して、p-階の線型漸化式

によって定まるものの総称である。このような数列は、最初の p-項が決まれば、残りの項は漸化式に従ってすべて一意に決定される。

一階の線型回帰列は公比 a0幾何数列と呼ばれるほうが普通である。

高階の線型回帰列を調べることは線型代数学に属する問題である。そのような列の一般項は、列に付随する特性多項式と呼ばれる多項式の根が求まれば、それらによって記述することができる。上記の漸化式を満たす列に付随する特性多項式は

で与えられる。特性多項式の次数は漸化式の階数に等しい。特に二階の回帰列の場合には、特性多項式の次数も 2 であり、その根の様子は判別式を用いて知ることができる。故に、二階線型回帰列は最初の二項の値のみから初等的な算術演算(和・差・積・冪)と正弦余弦函数(考える体が実数体の場合)を用いて記述することができる。この種の数列の例には、よく知られたフィボナッチ数列があり、その各項は黄金比の冪を使って書くことができる。

一階線型回帰列[編集]

一階の線型漸化式は

と書けて、その一般項は

で与えられる。

二階線型回帰列[編集]

係数体 K の二つのスカラー a および b ≠ 0 を固定して、線型漸化式

を考え、便宜のため以下 (R) と呼ぶことにする。

この漸化式を満たす列の一般項が、K における特性多項式の根の値に従って、以下のように与えられることが示される。

  • (ただし、r1 および r2 は多項式 X2aXb の相異なる二根)
  • (ただし、r0 は多項式 X2aXb の二重根)

また、λ と μ は列の最初の二項によって決まる, 初期パラメータである。

前者についてはさらに、多項式 X2aXb の二根 r1, r2 が互いに共軛な複素数 ρeiθ, ρeiθ であるとき、数列の一般項を

と書くことができる。ただし、A, BK は数列の最初の二項から決まるパラメータである。

ここまで数列はある番号 n0 から始まるものとして扱ったが、以下、一般性を失うことなく数列は自然数全体の成す集合 N 上で定義されるものと仮定してよい。実際、数列 (un) が n0 からしか定義されていないとき、N 上で定義される数列 (vn)nNvn = un+n0 によって定めることができる。

基本的な考え方は線型漸化式 (R) を満たす幾何数列を求めること、即ち数列 (rn)nN が (R) を満たすようなスカラー r を見つけることである。そうするとこの問題が、二次方程式 r2arb = 0 を解くことと等価であることが容易に理解される。多項式 r2arb はこの数列の特性方程式と呼ばれ、その判別式は Δ = a2 − 4b で与えられる。特性多項式の根の数によって、いくつかの場合が区別されねばならない。

相異なる二根を持つ場合[編集]

r1r2 が相異なる二根であるとき、数列 (r1n)nN および (r2n)nN はともに漸化式 (R) を満たすから、漸化式の線型性から同様に、一般項が λr1n + μr2n の数列もすべて (R) を満たす。ここから (R) を満足する数列を全て決定するには、そのような数列が初期条件 u0 および u1 によって完全に決まることから、λ と μ に関する次の方程式系

を解けば十分である。しかし、この系の行列式 r2r1 は常に 0 ではないから、(R) を満たす数列は常に (r1n)nN および (r2n)nN の線型結合として表される。このような状況は、数列が実数値で Δ > 0 のときや、数列が複素数値で判別式が 0 でないときに起きる。

二重根を持つ場合[編集]

判別式が 0 のときは、根が r0 一つしかなく、(R) を満たす幾何数列が (λr0n) しか出てこないから、状況が全く変わってくる。考え方としては、一般項が λnr0n となる数列 (un)nN が (R) を満足するような数列 (λn)nN を見つければよい。これは「定数変化法」と呼ばれる手法である。まずは、r0 が 0 でない限り (λn)nN が存在することを確かめよう。(un)nN に対する漸化式は (λn)nN に関する漸化式

に書き直すことができる。a2 + 4b = 0 と r0 = a/2 となる事実を用いれば、算術数列の定義式

が得られるから、従って数列 (λn)nN は一般項が λn = λ + μn の算術数列になる。

故に、(R) を満たす数列 (un) の一般項は

となる。この結果は、数列が実数値でも複素数値でも特性多項式の判別式が 0 ならば適用できる。

異なる二根が特に共軛の場合[編集]

特性多項式が実係数で、その判別式が真に負であるとき、この二次方程式の二つの根は相異なり、C において共軛である。それを

とすると、これは上記の二つの場合の前者であるから、(R) を満足する任意の複素数列は一般項が λ, μ を複素パラメータとして λρeinθ + μρeinθ の形に書ける。パラメータを A = λ L μ, B = i(λ − μ) に取り換えて、一般項を un = ρn(A cos(nθ) + B sin(nθ)) と書き直すこともできる。

従って、(R) を満足する実数列の場合にも一般項を

と書くことができる。実際、(先天的に複素数として与えた)パラメータ A, B が実数ならば、数列も実数値となるし、逆に、u0 = A, u1 = Aρ cos(θ) + Bρ sin(θ) で ρ sin(θ) ≠ 0 に気を付ければ、u0, u1 が実数ならば A, B もそうであることがわかる。

p-階の回帰列[編集]

p-階回帰列の成す p-次元部分空間[編集]

p-階の線型漸化式

を便宜のため (Rp) と呼称することとし、(Rp) を満たす K-値数列全体の成す集合を ERp で表すと、ERpK-値数列全体の成すベクトル空間の線型部分空間となることが、漸化式の線型性から従う。

さらにこの部分空間が p-次元となることもわかる。実際、ERpKp との間のベクトル空間の同型が、ERp の元 (un)nN に対し最初の p-項からなるベクトル (u0, u1, …, up) を対応させることで与えられる。故に、(Rp) を満たす p-個の線型独立な列が得られれば、ERp がそれら p-個の線型独立系から生成されることがわかる。

一般項の導出[編集]

一般項を求めるために、p-階回帰列を Kp に値をとる数列に読み替える。即ち、各数列 (un)nNERp に対し、Kp-値数列 (Un)nN

によって与える。すると、(un)nN に対する漸化式 (Rp) は (Un)nN に対する一階の線型漸化式 Un+1 = AUn に帰着される。ただし A

なる行列(数列の特性多項式の同伴行列)である。故に数列 (Un)nN の一般項は Un = AnU0 で与えられる。

これで問題は解決したようにも思えるが、現実的には A の冪 An, … の計算が容易でないことがしばしばあり、むしろ直接に ERp の基底を求めたほうがよいこともある。

基底の決定[編集]

行列 A特性多項式

で、これは (Rp) を満たす数列 (un)nN の特性多項式に他ならない。

数列 (un)nNvn = un+1 を満たす数列 (vn)nN に対応させる変換 f は線型写像であることに注意しよう。数列 u = (un)nN が (Rp) を満たすという条件は、P(f)u = 0 と書き直せるから、空間 ERp は線型写像 P(f) のに一致する。多項式 PK で可約なとき(K = C のときは常にそうだが)、k-個の根 r1, r2, …, rkk-個の冪指数 α1, α2, …, αk を用いて

と書けているとすると、P(f) の核は (friid)αi の核の直和に表される。従って、ERp の基底を決定するには、これらの核それぞれの基底を知れば十分である。

多項式 Q の次数が αi より真に小さいとき、一般項が Q(n)rin であるような任意の数列が (friid)αi の核に入ることが、αi に関する帰納法で示せる。j = 0, …, αi − 1 に対する数列 (njrin) は αi に対応する直和因子における αi-個の元からなる線型独立系であり、さらに i = 1, …, k として ERp の α1 + α2 + … + αk = p-個の元からなる線型独立系となるから、これは p-次元ベクトル空間 ERp の基底を成すことが確かめられる。従って、ERp の任意の元は、αi よりも真に低い次数を持つ Q に対する Q(n)rin を一般項とする数列の和として表される。

二階の場合の再考[編集]

特性多項式が一次式の積 (Xr1)(Xr2) に書けるなら、前節の多項式 Q は次数 0 であり、ER2 の任意の元は一般項が λ1r1n + λ2r2n の数列となる。

特性多項式の因数分解が (Xr0)2 なら、前節の多項式 Q の次数は 1 であり、ER2 の任意の元は一般項が (λ1n + λ2)r0n の数列となる。

外部リンク[編集]