添付ファイル '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)
        • 次の２つの式から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を足す）

  • 最小二乗法
    • プロットが与えられたとき、もっとも近い直線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で微分して＝０とする
      • -> 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
      • 後退代入で解ける

添付ファイル

添付ファイルを参照するには、(下のファイル一覧にあるように)attachment:filenameと記述します。 [get]リンクのURLは変更される可能性が高いので、利用しないでください。

ファイルを添付する権限がありません。