チェビシェフの多項式

作成日：2013-09-15

最終更新日：

チェビシェフの多項式の実装

チェビシェフの多項式とは、 `n` をゼロを含む自然数とするとき、 `cos(n theta) = f(cos theta)` で定義される`n`次の多項式 `f_n(x)` のことである。 `n` を指定したとき、この多項式は具体的にどのように表示されるのか知りたく思い、 JavaScript でプログラムを組んでみた。

まず、`n` 次のチェビシェフの多項式の係数を、昇ベキで `n-1` 次の配列に格納する。演算としては、多項式の和をとる操作と、多項式に 2x を乗じる操作を作ればよい。多項式に 2x を乗じるときには、まず x を乗じる処理、すなわち配列を一つずつ右にずらす処理のあと、各項に 2 を乗じる処理をすればよい。

たとえば、2 次と 3 次のチェビシェフの多項式`f_2(x), f_3(x)`はそれぞれ `2x^2 - 1, 4x^3 - 3x` で表される。したがって、配列 `a_2` は `a_2[0] = -1, a_3[1] = 0, a_3[2] = 2` であり、配列 `a_3` は `a_3[0] = 0, a_3[1] = -3, a_3[2] = 0, a_3[3] = 4` である。

チェビシェフ多項式が満たす漸化式

`T_(n+2) (x) = 2 x T_(n+1)(x) - T_n(x) `

最初の数項

`T_0(x) = 1`
`T_1(x) = x`
`T_2(x) = 2x^2 - 1`
`T_3(x) = 4x^3 - 3x`
`T_4(x) = 8x^4 - 8x^2 + 1`
`T_5(x) = 16x^5 - 20x^3 + 5x`

明示的な係数

`T_n(x)` の係数については次が成り立つ。

定数項は、 `n` が偶数なら `(-1)^(n/2)` 、`n` が奇数なら 0 　
1 次の係数は、`n` が偶数なら 0、`n` が奇数なら `(-1)^((n-1)/2) n`
2 次の係数は、`n` が偶数なら `(-1)^(n/2 - 1) n^2/2` 、`n` が奇数なら 0 　
`n` 次の係数は `2^(n-1)`

最初のスクリプト

まず最初は、非効率でもよいので正しい答が出るスクリプトを書いてみることにした。 `T_n(x)` の係数を、関数 Chebyshev(n) が返す配列に収めることにする。これは昇ベキで配列に格納することにした。たとえば次数 n = 3、返す配列を a[i] としよう。 `T_3(x) = a_0 + a_1x + a_2x^2 + a_3x^3` であるとき、配列 a の長さは 4 で、a[0] = 0, a[1] = -3, a[2] = 0, a[3] = 4 である。

関数 Chebyshev(n) を再帰関数で実装した最初のバージョンは次の通りである。

function Chebyshev(n) {
  if (n == 0) { 
    return [0]; 
  }
  if (n == 1) {
    return [0, 1];
  }
  if (n == 2) {
    return [-1, 0, 2];
  }
  if (n > 50) {
    return [];
  }
  let c = (Chebyshev(n - 1)).slice(0) // コピーを作る 
  c.unshift(0);                       // x をかけることに相当
  for (let i = 0; i < c.length - 2; i++)  { // T(n-2) の項の数だけ
    c[i] *= 2;                       // 係数を２倍する
    c[i] -= (Chebyshev(n-2))[i];      // - T(n-2) に相当
  }
  c[c.length - 1] *= 2;           // 最高次の係数を２倍
  return c;
}

このプログラムは非常に効率が悪い。Chebyshev(20) を求めようとしたら JavaScript がフリーズしそうになった。実際に求められたのは Chebyshev(17) までだった。計算機に強い人はすぐにわかるだろうが、このプログラムはフィボナッチ数を定義通り計算したときの非効率性と同じ考え方に基づく。

では、どうすれば計算を速くできるか。それが次のスクリプトである。

第２のスクリプト

最初のスクリプトを改造して、`T_20(x)` も計算できるようにしたスクリプトをお見せする。

function Chebyshev(n) {
  let c0 = [1];
  let c1 = [0, 1];

  function f(a, b, m) { // 下請関数
    if (m <= 1) {
      return a;
    }
    let c= a.slice(0) // コピーを作る 
    c.unshift(0);                       // x をかけることに相当

    // F_n(x) = 2x F_(n-1)(x) - F_(n-2)(x) 

    for (let i = 0; i < c.length; i++)  { 
      c[i] *= 2;                       // 係数を２倍する
    }
    for (let i = 0; i < b.length; i++)  { 
      c[i] -= b[i];                   
    }

    return f(c, a, m - 1);
  };

  if (n > 50) {
    return []; /* エラー */
  }

  if (n == 0) return c0;
  if (n == 1) return c1;
  return f(c1, c0 , n); /* T_1(x), T_0(x), n */
}

このスクリプトでわかる通り、下請け関数を呼び出して、次数が低い式を１回だけ呼び出すようにしている。

n が 0 以上 50 以下の `T_n(x)`

このスクリプトであれば、n = 20 もすぐに表示できる。下記は、n = 50 までのチェビシェフ多項式である。

更新：表示に使う関数を document.write から innerHTMLに変更。2021-04-21

リンク

参考サイト

普通の数学 5. n 倍角の公式(www10.plala.or.jp)
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列に O 記法を学ぶ(blog.livedoor.jp)

数式表示

数式表示は長らく旧版の ASCIIMathML を用いていたが、このたび MathJax に差し替えた。2021-04-21

まりんきょ学問所＞ JavaScript 手習い＞チェビシェフの多項式