1/10連続系アルゴリズムノート

1/23試験！

離散フーリエ変換

K = 2^k
w = e^(-2πi / k)(1のK乗根)
- w^K = 1
- w^(K / 2) = -1
- w^(K / 4) = -i
- w^(3K / 4) = i
- w^(K + h) = w^h
離散フーリエ変換（DFT）
- べき表現のK-1次多項式p(x)に対しp(w^h)をすべて求めよ
- （h = 0, 1, 2, ・・・, K - 1）
- 普通にやればO(K^2)くらいでできる。horner法とか使えば
高速フーリエ変換（FFT）
- p(x)を偶数次・奇数次に分ける
- - p(x) = q(x^2) + xs(x^2)
  - q・sはK / 2 - 1次
  - 再帰的に
    - q(w^2h), s(w^2h)
    - を計算していく
    - h = 0, 1, 2, 3, ・・・, K / 2 - 1
  - p(w^h) = q(w^2h) + xs(w^2h)
  - p(w^(h + π / 2) = q(w^2h) - xs(w^2h)
- 計算量はO(KlogK)
- O(K^2)よりはだいぶ速い
逆高速フーリエ変換（IFFT）
- p(w^h)の値 h = 0, 1, 2, ・・・, K - 1まで与えられていたとする
- このとき、多項式pのべき表現の係数をすべて求める
- やはり分割統治法
  - p(x) = q(x^2) + xs(x^2)
  - 次の２つの式からq(x^2)とs(x^2)がわかる
    - p(w^h) = q(w^2h) + xs(w^2h)
    - p(w^(h + π / 2) = q(w^2h) - xs(w^2h)
- あとは自分で考える
応用（１）多項式の積
- p(x) * q(x) = r(x)
- r(x) はK-1次以下（となるようにKを設定）
- 次のようにして求める
  1. p(w^h), q(w^h)をFFTで求める.O(KlogK)
  2. r(w^h) = p(w^h) * q(w^h).O(K)
  3. IFFTでr(x)の係数を求める。O(KlogK)
- 合計O(KlogK)でできる
- p(x) = a[n]x^n + ・・・ + a[1]x + a[0]
- 10進数 3217 = 3 * 10^3 + 2 * 10^2 + 1 * 10^1 + 7 * 10^0
- みたいにかけるので、多倍長の掛け算とかにも使える
応用（２）巡回畳み込み
- p(x), q(x) をK-1次多項式とする
- 応用（１）と同じ計算をする
- w^K = 1, w^(K + h) = w^K
- x^(K + h) の係数が x^h の係数に見える
- p(x) = a[0] + a[1]x + ・・・+ a[k - 1]x^(k - 1)
- q(x) = b[0] + b[1]x + ・・・+ b[k - 1]x^(k - 1)
- r(x) = c[0] + c[1]x + ・・・+ c[k - 1]x^(k - 1)
- c[h] = Σ{n + m = h}(a[n]b[m])Σ{n * m = K + h}(a[n]b[m]) = Σ{n = 0 to K - 1}a[n]b[h - n]
- bの添え字jが負の数なら、b[K + j]とする（Kを足す）

最小二乗法
- S = ||AZ - v||^2
- 解は一意に決まらないが
- min S（残差）を最小にする
- という問題にするとwell-definedの問題になる
- ||Ax - v||^2 = (Ax - b)^T * (Ax - b)
- = (x^T)(A^T)Ax - 2(x^T)(A^T)b + (b^T)b
- xで微分して＝０とする
- - -> 2(A^T)Ax - 2(A^T)b = 0
  - -> (A^T)Ax - (A^T)b = 0
- (A^T)Aを作ってLU分解はあまりおすすめでない
- - 条件数がほぼ2乗になるので精度が落ちる
- QR分解を使う
- - A = QR
  - Q：直交行列
  - R：上三角行列
  - Gram-Schmidtの直交化を使う
  - - 丸め誤差が起こるので修正Gram-Schmidt法を使う
- QR分解の使い方
  - (A^T)Ax = (A^T)b
  - (R^T)(Q^T)QRx = (R^T)(Q^T)b
  - (R^T)Rx = (R^T)(Q^T)b
  - (R[m]^T)R[m]x = (R[m]^T)Q[m]b
  - R[m]は正則なので、
  - - R[m]x = (Q[m]^T)b
  - 後退代入で解ける