ホーナー法の変更点

追加された行はこの色です。
削除された行はこの色です。
ホーナー法へ行く。
ホーナー法の差分を削除



2分法やニュートン法を使って以下の&ref(rf_horner.eq1.gif,nolink,70%);次の代数方程式を解くときの演算回数を考える．
#ref(rf_horner.eq2.gif,nolink,70%)

&ref(rf_horner.eq3.gif,nolink,70%);の値を計算する際の乗算回数は&ref(rf_horner.eq4.gif,nolink,70%);回で
加算が&ref(rf_horner.eq1.gif,nolink,70%);回である．
乗算回数が&ref(rf_horner.eq1.gif,nolink,70%);の2乗で増えるため，たとえば，&ref(rf_horner.eq5.gif,nolink,70%);では55回だが，&ref(rf_horner.eq6.gif,nolink,70%);だと5050回にもなる．

乗算回数を少なくするために代数方程式を以下のように変形する．
#ref(rf_horner.eq7.gif,nolink,70%)

この場合，一番内側の括弧内から計算していくと，
#ref(rf_horner.eq8.gif,nolink,70%)

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

ホーナー法で代数方程式の値とその導関数を求めるコード例を以下に示す．
#code(C){{
/*!
 * ホーナー法で代数方程式の値を計算
 * @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法で複素数を扱う関係上，様々な型に対応できるようにしたいためである．
ホーナー法 の変更点
