未分類
二分法; Bisection Method

概要

---

二分法は関数値が0を通る点を求める求根アルゴリズムの一つ。根を含む領域を半分ずつ狭めながら根を求める
他の求根アルゴリズムに比べ収束速度が遅いが最も確実な手法である。


アルゴリズム

---

\(f(x)=0\)となる\(x\)を求める。
・初期値
-根を含む領域\([a, b]\)を設定する。

・収束計算
-\(a, b\)およびその中点\(m\)における\(f(a), f(b), f(m)\)に対し、
\(\quad f(a), f(m)\)の符号が一致するなら\(m\)を新たな\(a\)と、\(f(m), f(b)\)の符号が一致するなら\(m\)を新たな\(b\)とする。

ソースコード

---

namespace RootFindingMethod {

    /// <summary>2分法</summary>
    /// <remarks>f(x)=0となるxを求める</remarks>
    public static class BisectionMethod {

        /// <summary>求根</summary>
        /// <param name="func">f(x)=0となる関数f(x)</param>
        /// <param name="xa">求根範囲</param>
        /// <param name="xb">求根範囲</param>
        /// <param name="precision_level">精度レベル</param>
        /// <remarks>f(xa), f(xb)は異符号である必要がある</remarks>
        public static double Execute(Func<double, double> func, double xa, double xb, int precision_level) {
            double a = func(xa), b = func(xb);

            if((a > 0 && b > 0) || (a < 0 && b < 0)) {
                throw new ArgumentException($"Invalid Range {nameof(xa)}, {nameof(xb)}");
            }

            while(precision_level > 0) {

                double xm = (xa + xb) / 2;
                double m = func(xm);
                precision_level--;

                if((a > 0 && m > 0) || (a < 0 && m < 0)) {
                    xa = xm;
                    a = m;
                    continue;
                }
                if((b > 0 && m > 0) || (b < 0 && m < 0)) {
                    xb = xm;
                    b = m;
                    continue;
                }
                break;
            }

            return (xa + xb) / 2;
        }
    }
}

単体テスト

---

namespace RootFindingMethod.Tests {
    [TestClass()]
    public class BisectionMethodTests {
        [TestMethod()]
        public void ExecuteTest1() {
            Func<double, double> func = (x) => x * x - 2;

            double v = BisectionMethod.Execute(func, 0, 2, 50);

            Assert.AreEqual(v, Math.Sqrt(2), 1e-14);
        }

        [TestMethod()]
        public void ExecuteTest2() {
            Func<double, double> func = (x) => x * x - 2;

            double v = BisectionMethod.Execute(func, 2, 0, 50);

            Assert.AreEqual(v, Math.Sqrt(2), 1e-14);
        }
    }
}

関連項目

---

ニュートンラフソン法
挟み撃ち法
割線法