2分法やニュートン法を使って以下のrf_horner.eq1.gif次の代数方程式を解くときの演算回数を考える.

rf_horner.eq2.gif

rf_horner.eq3.gifの値を計算する際の乗算回数はrf_horner.eq4.gif回で 加算がrf_horner.eq1.gif回である. 乗算回数がrf_horner.eq1.gifの2乗で増えるため,たとえば,rf_horner.eq5.gifでは55回だが,rf_horner.eq6.gifだと5050回にもなる.

乗算回数を少なくするために代数方程式を以下のように変形する.

rf_horner.eq7.gif

この場合,一番内側の括弧内から計算していくと,

rf_horner.eq8.gif

となり,最終的にrf_horner.eq9.gifとなる. このときの乗算回数はrf_horner.eq1.gif回,加算もrf_horner.eq1.gif回である. 特にrf_horner.eq1.gifが大きな時に計算回数を大幅に減らすことができる. たとえば,乗算回数はrf_horner.eq5.gifで10回,rf_horner.eq6.gifでも100回で済む. この計算方法はホーナー(Horner)法と呼ばれる.

ホーナー法で代数方程式の値とその導関数を求めるコード例を以下に示す.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
/*!
 * ホーナー法で代数方程式の値を計算
 * @param[in] x 変数
 * @param[in] b 係数
 * @param[in] n 方程式の次数
 * @return 代数方程式の値
 */
template<class T>
inline T func_h(double x, const vector<T> &b, int n)
{
    T f = b[0];
    for(int i = 1; i <= n; ++i){
        f = b[i]+f*x;
    }
    return f;
}
/*!
 * ホーナー法で代数方程式の導関数値を計算
 * @param[in] x 変数
 * @param[in] b 係数
 * @param[in] n 方程式の次数
 * @return 代数方程式の導関数値
 */
template<class T>
inline T dfunc_h(double x, const vector<T> &b, int n)
{
    T df = n*b[0];
    for(int i = 1; i <= n-1; ++i){
        df = (n-i)*b[i]+df*x;
    }
    return df;
}

テンプレート関数にしているのはDKA法で複素数を扱う関係上,様々な型に対応できるようにしたいためである.


添付ファイル: filerf_horner.eq4.gif 484件 [詳細] filerf_horner.eq5.gif 462件 [詳細] filerf_horner.eq7.gif 464件 [詳細] filerf_horner.eq2.gif 464件 [詳細] filerf_horner.eq3.gif 440件 [詳細] filerf_horner.eq1.gif 451件 [詳細] filerf_horner.eq9.gif 452件 [詳細] filerf_horner.eq8.gif 424件 [詳細] filerf_horner.eq6.gif 410件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-06-27 (水) 11:57:11 (3010d)