[수치 해석] Numerical analysis

1. 수치 해석

 

직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘

 

이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야로,

공학, 과학, 금융과학 등 다양한 범위에 널리 사용

 

2. 이분법(bisection method)

 

[lo, hi] 내에서 어떤 함수 f(x)의 값이 0이 되는 지점을 수치적으로 찾아내는 기법.

 

답이 여러 개 있는 함수라도 연속이기만 하다면 이분법을 사용해 근을 찾을 수 있음.

 

이분법을 사용하기 위해서는 우선 함수의 그래프 상에서 x축 윗부분에 위치한 점 하나와

 

아랫부분에 위치한 점 하나르 찾아야한다. (lo, hi)

 

그래프가 연속인 경우 중간값 정리에 의해 두 점 사이에서 그래프가 x축을 만나는 지점이 반드시 존재한다.

 

lo와 hi의 중간점에서 f(x)를 검사하고 만약 위 그림처럼

[lo, mid] 구간내에 답이 존재한다면 hi = mid

[mid, hi] 구간내에 답이 존재하면 lo = mid로 갱신한다.

 

이렇게 이분법은 매번 구간의 크기를 절반으로 줄여나가 굉장히 빨리 답의 근사값을 찾는다.

 

 

double f(double x);
 
double bisection(double lo, double hi)
{
    if(f(lo) > 0)
        swap(lo, hi);
    
    while(fabs(hi-lo) > 2e-7)
    {
        double mid = (lo+hi)/2;
        double fmid = f(mid);
        if(fmid <= 0) lo = mid;
        else hi = mid;
    }
    return (lo+hi)/2;
}

3. 절대 오차를 이용한 종료판정

 

while의 종료 조건은 절대 오차를 이용하였다.

 

이는 정확도와 수행 속도 사이에서 적절히 타협하는 종료 조건을 선택 한 것이다.

 

반복문 불변식을 강제하기 위해 lo > hi가 될경우를 대비하여 항상 절대값을 취하였다.

 

위와 같이 절대 오차를 사용하는 방법은 다루는 값의 크기가 작을 때는 잘 동작하지만

값의 크기가 커지면 문제가 생길 수 있다.

 

부동 소수점은 가수부라고 부르는 정수 부분과 이 변수에서 소수점의 위치를 나타내는 지수부의 조합으로

표현되기 때문에, 표현할 수 있는 수의 집합이 제한되어있다.

따라서 숫자의 절대 값이 커지면 커질수록 표현할 수 있는 수들이 듬성듬성해지게 된다.

 

 

#include <iostream>
#include <cmath>
int main()
{
    double lo = 123456123456.1234588623046875;
    double hi = 123456123456.1234741210937500;
    while(fabs(hi - lo) > 2e-7)
    {
        hi = (lo + hi) / 2.0;
    }
}

위와 같은 코드는 lo 와 hi 사이에 double변수가 표현할 수 있는 값이 하나도 없다.

따라서  lo와 hi의 평균은 항상 hi와 같게되어 절대 종료되지 않는다.

(지수 비트와 부호 비트가 완전히 같고, 가수비트는 최하위 비트를 제외하고 완전히 똑같다

123456123456.1234688623046875를 double에 집어넣을시 hi값이 나온다.

그 수가 유효자리비트로 표현할 수 있는 한계를 넘어가버리게 되면 근사치를 취하기 때문이다)

IEEE의 부동소수점 방식

IEEE의 부동소수점 방식

 

4. 상대 오차를 이용한 종료판정

 

반환 값의  오차가 10^-7보다 크더라도 정답 A에대해 [A*(1-10^-7), A*(1+10^-7)] 범위에 포함되는 답을 정답으로

인정하는 것이다.

 

즉 lo, hi가 양수일 때

 

(1-10^-7)*hi < mid <  (1+10^-7)*lo

 

이 조건이 참이야한다

 

만약 두 수가 음수거나 lo가 음수인 경우는 더 복잡하게 판정을 해야한다.

 

5. 정해진 횟수만큼 반복하기

 

복잡성을 줄이기위해 단순히 while문과 for문으로 정해진 횟수만큼 실행하도록하는 방법이다.

 

100번정도 실행하면 절대오차는 최대 |lo - hi|/2^101 이 되어 오차는 항상 10^-7보다 작아진다.

 

6. 삼분법

삼분법은 하나의 극대점을 기준으로 왼쪽에는 항상 순 증가하고,

오른쪽에는 항상 순감소하는 함수에서 적용할 수 있다.

(지역극대점, 유니모달 함수)(순증가, 순감소함수는 단조함수와 다르게 수평부분이 허용되지 x)

 

삼분법은 함수를 구간 [lo, hi]에서 다음과 같이 분리한다.

lo,.. a=(2*lo + hi)/3, .. b=(lo + 2*hi)/3,.. hi

 

만약 극대점을 기준으로 왼쪽이 순증가, 오른쪽인 함수일 경우

a < b 이면 lo ~ a 까지는 최대치가 있을 수 없음을 의미한다.

따라서 다음 부분 문제는 lo = a 인 [lo, hi] 구간이 된다.

 

이렇게 삼분법은 한 번 반복할 때마다 후보 구간의 크기를 2/3로 줄여나간다.

이것을 n번 반복하면 구간의 길이가 |hi - lo|*(2/3)^n가 된다.

double ternary(double lo, double hi) 
{
    for(int iter = 0; iter < 100; iter++)
    {
        double a = (2*lo + hi) / 3.0;
        double b = (lo + 2*hi) / 3.0;
 
        if(f(a) > f(b)) hi = b;
        else lo = a;
    }
    return (lo+hi)/2.0;
}

 

7. 삼분법의 장점

 

위와 같은 유니모달 함수는 국소 탐색 알고리즘이나 미분하여 도함수 값이 0 인것을 조사하는 등

여러 알고리즘으로 문제를 해결할 수 있다.

 

그러나 미분할 수 없는 함수에도 삼분법은 사용할 수 있고,

국소탐색에 비해 훨씬 빠르게 동작하고 수렴판정이 용이하기 때문에 자주 사용된다

 

(국소탐색 알고리즘: 임의의 답을 하나 만들어 놓고 이 값을 조금씩 갱신하면서 답이 더 좋아지는 쪽으로 움직이는 알고리즘, 최적해를 찾는다는 보장은 없다.)

 

 

8. 여러 수치 해석 알고리즘

 

수치 적분 알고리즘들

 

심슨 방법: 구간의 함수를 2차함수로 근사해서 적분, 적분하는 함수가 2차 이하의 함수면 항상 정확한 값을 반환

 

 

-알고리즘 문제해결전략 472p