C
数値計算
数学

反復法で2次方程式を解く

More than 1 year has passed since last update.

反復法の素晴らしさを示そう
2次方程式を解く場合、普通は解の公式に数値を代入して解くだろう。

ax^2 + bx + c = 0\\
\Leftrightarrow
x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}

他にも、ニュートン法で解く場合は微分をしなければならない。
微分も解の公式も覚えられない人にお薦めの方法がある
方程式の両辺にxを足し

ax^2 + bx + c = 0\\
\Leftrightarrow
x = ax^2 + (1+b)x + c

左辺のxをyに置き換える

x = ax^2 + (1+b)x + c\\
\Leftrightarrow
y = ax^2 + (1+b)x + c

x = yとなる数値を探せば良い
xに適当な数字を入れよう。
その結果を元に次のxを決めてやれば良い。

\begin{align}
y &= ax_{current}^2 + (1+b)x_{current} + c\\
x_{next} &= (1+w)x_{current} - wy
\end{align}

wは重み、この計算を適当な数回せば求める答えが手に入る

#include <stdio.h>

int main()
{
    int i;
    double a,b,c,v,w,x,y;
    a = 1.0;
    b = 2.0;
    c = 1.0;
    w = 0.1;

    x = 0;
    y = a*x*x + (b+1.0)*x + c;
    x = (1.0 + w) * x - w * y;
    v = (y - x)*(y - x);
    for(i=0;i<1000;i++) {
        y = a*x*x + (b+1.0)*x + c;
        if(v < (y - x)*(y - x)) {
            w = -w;
        }
        x = (1.0 + w) * x - w * y;
    }

    y = a*x*x + b*x + c;
    printf("答え:%f\n誤差:%f\n",x,y);

    return 0;
}

実数解が存在するなら誤差は小さな範囲で収まる
実数解が1つだけいるならこの方法が使える
wを大きくしすぎると発散する
そして反復回数を増やせば増やすほど精度が上がる

2次方程式の場合は解の公式が覚えられない人にしかメリットが無いが、
反復法には直接計算出来ない解の公式が無いものでも計算できるメリットがある