添付ファイル '110�A���n�A���S���Y���m�[�g.html'
ダウンロード
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)
- 次の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)
- あとは自分で考える
- 応用(1)多項式の積
- p(x) * q(x) = r(x)
- r(x) はK-1次以下(となるようにKを設定)
- 次のようにして求める
- p(w^h), q(w^h)をFFTで求める.O(KlogK)
- r(w^h) = p(w^h) * q(w^h).O(K)
- 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
- みたいにかけるので、多倍長の掛け算とかにも使える
- 応用(2)巡回畳み込み
- p(x), q(x) をK-1次多項式とする
- 応用(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を足す)
- 最小二乗法
- プロットが与えられたとき、もっとも近い直線y = a + bxを求める
- S = Σ(a + bx[i] - v[i])^2
- を最小化する
- A = ((1, x1), (1, x2), ・・・, (1, x[n])), v= (v1, v2, ・・・, v[n]) (縦行列)
- Z = (a, b)
- 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で微分して=0とする
- -> 2(A^T)Ax - 2(A^T)b = 0
- -> (A^T)Ax - (A^T)b = 0
- (A^T)Aを作ってLU分解はあまりおすすめでない
- 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]は正則なので、
- 後退代入で解ける