반감기법
이진법은 수치해석에서 방정식의 근을 찾는 알고리즘 중 하나입니다. 이 알고리즘은 주어진 간격에서 함수 값의 부호가 다른 두 점을 찾고 함수 값이 0에 가장 가까운 중간점에서 근을 찾는 방식으로 작동합니다.
알고리즘 순서
알고리즘의 동작 순서는 다음과 같습니다.
- 주어진 간격(a, b)에서 함수 f(x)의 값이 다른 두 점을 찾습니다. 이렇게 하려면 구간의 중앙값 c를 찾고 f(a)와 f(c)의 부호가 다르면 구간을 (a, c)로 좁히고 f(c)와 f(b)의 부호가 )는 서로 다르며, (c, b)는 간격을 좁히기 위한 것입니다.
- 간격을 좁힌 후 새 중앙값을 찾습니다. c. 이 경우 c = (a + b) / 2를 얻을 수 있다.
- 새 중앙값 c가 주어졌을 때 함수 값 f(c)를 계산합니다. f(c)가 0이거나 0에 충분히 가까우면 c를 제곱근으로 반환하고 알고리즘을 중지합니다.
- f(c)가 0에 가깝지 않으면 f(c)의 부호가 f(a)이면 (c, b)로 간격을 좁히고 f(c)의 부호가 f(b)이면 (a, c ) 간격을 좁힙니다.
- 2~4단계를 반복하여 근을 찾을 수 있을 만큼 간격을 좁힙니다.
이분법은 간격의 길이가 점점 더 작아지기 때문에 수렴을 보장합니다. 그러나 초기 간격을 잘못 지정하면 수렴이 느리고 잘못된 결과를 얻을 수 있습니다. 함수 f(x)가 미분 가능하지 않거나 0이 여러 개인 경우에도 다른 알고리즘을 사용해야 합니다.
클래스 구현
다음은 이분법을 구현하는 클래스입니다.
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 클래스는 이분법 알고리즘을 사용하여 특정 함수의 근을 찾는 방법을 제공합니다. 클래스를 초기화할 때 왼쪽 극한(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