[C# Numerical analysis Lib] Bisection Method

Bisection Method

 

이분법(Bisection Method)

 

이분법은 수치해석에서 방정식의 근을 찾는 알고리즘 중 하나입니다. 이 알고리즘은 주어진 구간에서 함수 값의 부호가 서로 다른 두 점을 찾아서 그 중간 지점에서 함수값이 0에 가장 가까워지는 근을 찾아가는 방식으로 동작합니다.

---

---

알고리즘 순서

알고리즘 동작 순서는 다음과 같습니다.

1. 주어진 구간 [a, b]에서 함수 f(x)의 값이 서로 다른 두 점을 찾습니다. 이를 위해 구간의 중앙값인 c를 구하고, f(a)와 f(c)의 부호가 다르면 [a, c]로 구간을 좁히고, f(c)와 f(b)의 부호가 다르면 [c, b]로 구간을 좁힙니다.
2. 구간을 좁힌 후, 새로운 중앙값 c를 구합니다. 이 때, c = (a + b) / 2로 구할 수 있습니다.
3. 새로운 중앙값 c에서 함수값 f(c)를 계산합니다. 만약 f(c)가 0이거나 충분히 0에 가까워졌다면, c를 근으로 반환하고 알고리즘을 종료합니다.
4. f(c)가 0에 가깝지 않다면, f(c)의 부호가 f(a)와 같으면 [c, b]로 구간을 좁히고, f(c)의 부호가 f(b)와 같으면 [a, c]로 구간을 좁힙니다.
5. 2~4단계를 반복하여 구간을 충분히 좁히면 근을 찾을 수 있습니다.

이분법은 구간의 길이가 점점 줄어들기 때문에 수렴성이 보장됩니다. 하지만, 수렴속도가 느리고, 초기 구간을 잘못 지정하면 잘못된 결과를 얻을 수 있습니다. 또한 함수 f(x)가 미분 가능하지 않거나, 근이 여러 개인 경우에는 다른 알고리즘을 사용해야 합니다.

 

클래스 구현

다음은 이분법을 구현한 클래스입니다.

---

using System;

public class BisectionMethod
{
    private double a; // 구간의 왼쪽 경계값
    private double b; // 구간의 오른쪽 경계값
    private double eps; // 계산의 정확도
    private int maxIterations; // 최대 반복 횟수

    private List<double> values = new List<double>(); // 매 반복마다 찾은 값을 저장할 리스트
    private List<double> errors = new List<double>(); // 매 반복마다 에러값을 저장할 리스트

    private Func<double, double> f; // 근을 찾을 함수

    /// <summary>
    /// 이분법 알고리즘을 초기화합니다.
    /// </summary>
    /// <param name="a">구간의 왼쪽 경계값</param>
    /// <param name="b">구간의 오른쪽 경계값</param>
    /// <param name="eps">계산의 정확도</param>
    /// <param name="f">근을 찾을 함수</param>
    /// <param name="maxIterations">최대 반복 횟수</param>
    public BisectionMethod(double a, double b, double eps, Func<double, double> f, int maxIterations = 100)
    {
        this.a = a;
        this.b = b;
        this.eps = eps;
        this.f = f;
        this.maxIterations = maxIterations;
    }

    /// <summary>
    /// 주어진 함수의 근을 이분법 알고리즘으로 찾습니다.
    /// </summary>
    /// <returns>근</returns>
    public double FindRoot()
    {
        double fa = f(a);
        double fb = f(b);

        // 구간 내에 근이 없는 경우 예외를 발생시킴
        if (fa * fb > 0)
        {
            throw new Exception("근이 없습니다.");
        }

        // 초기값 추가
        values.Add((a + b) / 2);
        errors.Add(0);

        int i = 0;
        while (i++ < maxIterations)
        {
            double c = (a + b) / 2;
            double fc = f(c);

            // 근을 찾았을 경우, 매 반복마다 찾은 값을 리스트에 저장하고 근을 반환함
            if (Math.Abs(b - a) < eps)
            {
                values.Add(c);
                errors.Add(Math.Abs(values[values.Count - 1] - values[values.Count - 2]));
                return c;
            }

            // 적절한 구간으로 이동함
            if (fa * fc < 0)
            {
                b = c;
                fb = fc;
            }
            else
            {
                a = c;
                fa = fc;
            }

            // 매 반복마다 찾은 값을 리스트에 저장하고 에러값을 계산하여 리스트에 저장함
            values.Add((a + b) / 2);
            errors.Add(Math.Abs(values[values.Count - 1] - values[values.Count - 2]));
        }
        throw new Exception("근을 찾는 도중에 최대 반복 횟수를 초과했습니다.");
    }

    /// <summary>
    /// 매 반복마다 찾은 값을 반환합니다.
    /// </summary>
    /// <returns>매 반복마다 찾은 값</returns>
    public List<double> GetValues()
    {
        return values;
    }

    /// <summary>
    /// 매 반복마다 찾은 값을 반환합니다.
    /// </summary>
    /// <returns>매 반복마다 찾은 에러값</returns>
    public List<double> GetErrors()
    {
        return errors;
    }
}

---

위 BisectionMethod 클래스는 이분법(Bisection Method) 알고리즘을 사용하여 주어진 함수의 근을 찾는 기능을 제공합니다. 클래스를 초기화할 때는 구간의 왼쪽 경계값(a), 오른쪽 경계값(b), 계산의 정확도(eps), 근을 찾을 함수(f), 최대 반복 횟수(maxIterations)를 인자로 전달합니다.

FindRoot 메서드를 호출하면, 이분법 알고리즘을 사용하여 주어진 함수의 근을 찾습니다. 이분법 알고리즘을 사용하여 근을 찾을 때는 계산의 정확도를 만족할 때까지 구간을 점점 좁혀나갑니다. 이 과정에서 매 반복마다 찾은 값을 리스트로 저장하며, 최대 반복 횟수를 초과하면 예외를 발생시킵니다.

GetValues 메서드와 GetErrors 메서드를 사용하여, 매 반복마다 찾은 값을 리스트로 반환할 수 있습니다. 이 리스트를 사용하면, 이분법 알고리즘의 수렴 과정과 수렴 속도를 자세히 확인할 수 있습니다.

BisectionMethod 클래스는 주어진 함수의 근을 찾는 것 외에도, 구간을 동적으로 조정하는 기능과 매 반복마다 찾은 값을 저장하여 출력하는 기능 등을 제공합니다. 이 클래스를 사용하면, 수치해석 분야에서 매우 유용하게 사용할 수 있습니다.

 

 

사용 예제

BisectionMethod 클래스를 사용한 예제는 다음과 같습니다.

---

static void Main(string[] args)
{
    BisectionMethod bisectionMethod = new BisectionMethod(1, 2, 0.0001, x => x * x - 2);
    double root = bisectionMethod.FindRoot();
    Console.WriteLine("근: {0}", root);
    List<double> values = bisectionMethod.GetValues();
    List<double> errors = bisectionMethod.GetErrors();
    Console.WriteLine("반복마다 찾은 값: ");

    for (int i = 0; i < values.Count; i++) 
    {
        Console.WriteLine("반복 {0}: {1}, 에러: {2}", i, values[i], errors[i]);
    }
}

---

[결과]

근: 1.414215087890625
반복마다 찾은 값:
반복 0: 1.5, 에러: 0
반복 1: 1.25, 에러: 0.25
반복 2: 1.375, 에러: 0.125
반복 3: 1.4375, 에러: 0.0625
반복 4: 1.40625, 에러: 0.03125
반복 5: 1.421875, 에러: 0.015625
반복 6: 1.4140625, 에러: 0.0078125
반복 7: 1.41796875, 에러: 0.00390625
반복 8: 1.416015625, 에러: 0.001953125
반복 9: 1.4150390625, 에러: 0.0009765625
반복 10: 1.41455078125, 에러: 0.00048828125
반복 11: 1.414306640625, 에러: 0.000244140625
반복 12: 1.4141845703125, 에러: 0.0001220703125
반복 13: 1.41424560546875, 에러: 6.103515625E-05
반복 14: 1.414215087890625, 에러: 3.0517578125E-05
반복 15: 1.414215087890625, 에러: 0

---