平方根の値を二分法で求めてみる!

こんにちは、MSKです。
今回は平方根の値をニュートン法で求めてみたいと思います。

二分法とは

以前ニュートン法を紹介しましたが、二分法も方程式f(x) = 0の解xを近似的に求めるアルゴリズムです。

平方根の値をニュートン法で求めてみる!今回は平方根の値をニュートン法で求めてみたいと思います。...

二分法を紹介します。

要は解がある範囲を徐々に狭めていって、解の十分近い値まで、もしくは一致する点を探していくというアルゴリズムですね。

Pythonで計算してみる

前の記事と同じように\sqrt{19}を計算したいと思います。

# 19の平方根を計算するための式を定義
def polynomial(x: float) -> float:
    return x**2 - 19
    
# 範囲の中点での式の値を計算し、新しいaとbを返す
def calc_one_step(a: float, b: float) -> (float, float):
    if polynomial((a+b)/2) < 0:
        return (a+b)/2, b
    else:
        return a, (a+b)/2

# 二分法で計算する
def calc_dichotomy(a: float, b: float) -> float:
    x: float = a
    y: float = b
    loop_cnt: int = 0
    while loop_cnt <= 50:
        x, y = calc_one_step(x, y)
        loop_cnt += 1
    return (x+y)/2
    

if __name__ == '__main__':
    print("root 19 = ", calc_dichotomy(3.0, 5.0))

実行すると、root 17 = 4.358898943540673と表示されると思います。
ニュートン法とほぼ同じですね。

Rustで計算してみる

// 19の平方根を計算するための式を定義
fn polynomial(x: f64) -> f64 {
    x*x - 19.0
}

// 範囲の中点での式の値を計算し、新しいaとbを返す
fn calc_one_step(a: f64, b: f64) -> (f64, f64) {
    let c_pt = (a+b) / 2.0;
    if polynomial(c_pt) < 0.0 {
        return ( c_pt, b);
    } else {
        return (a, c_pt)
    }
}

// # 二分法で計算する
fn calc_dichotomy(a: f64, b: f64) -> f64 {
    let mut x: f64 = a;
    let mut y: f64 = b;
    let mut loop_cnt: u8 = 0;
    while loop_cnt <= 50 {
        (x,y) = calc_one_step(x, y);
        loop_cnt += 1;
    }
    (x + y) / 2.0
}

fn main() {
    println!("root 19 = {}", calc_dichotomy(3.0, 5.0));
}

pythonと同じように、root 19 = 4.358898943540673と表示されます。

最後に

今回は二分法を紹介しました。
式fの値の符号が違う2点から初めて、その２点の中点のfの値が正か負かで範囲の片方を置き換え、再度新しくなった２点で同じような手順を行う。
これを何度も繰り返すことでf(x)の近似的な解を求めるアルゴリズムでした。

最後までご覧いただき、ありがとうございます。
以上、「平方根の値を二分法で求めてみる!」でした。