[수치해석 12] 보간법

보간법

데이터가 정확하게 알려져 있는 경우에 각 점을 직접 통과하는 곡선이나 일련의 곡선을 구해 사이 값을 추정하는 방법.

다항식 보간법(polynomial interpolation) 은 n+1개의 점으로부터 n차 다항식의 계수를 추정한다.

데이터 개수보다 1차원 작은 다항식을 추정하게 된다.

 

Newton divided-difference(제차분) 보간 다항식

우리는 흔히 다항식을 아래와 같이 표현한다.

현실에서 손으로 계산하는 경우 위 식에 직접 값을 대입하여 근을 구하더라도 문제는 없다. 그러나 해당 계산을 컴퓨터를 통해 하면, 필연적으로 반올림 오차가 발생하기 때문에 이런 방식은 부적절하다.

이런 이유로 우리는 다항식을 아래와 같은 방식으로 표현한다.

위 다항식에 대해 몇몇 식을 구해보자.

선형 보간법

삼각형의 닮음 관계를 이용하여 1차 다항식을 얻을 수 있다.

2차 이상의 다항식으로 확장되는 경우, 해당 인자들은 기존의 값을 대입하는 방식으로 찾을 수 있다. 이를 일반화하면,

제차분을 뜻하는 f[x, y] 는 아래와 같이 정의된다. 각 고저차분은 저저차분을 기반으로 계산된다.

 

계산 방식

 

파이썬 알고리즘

from math import log # 파이썬에서는 log 함수의 밑을 따로 안주면 자연로그로 취급

def Newdd(x: list[float], y: list[float]):
    '''
    Newton divided-difference. 실제 값을 계산한다.

    @param x,y : 실제 좌표 데이터.
                    x의 크기와 y의 크기는 같아야 함.
    @return (args, func) : args 는 a_0 ~ a_n
                            func는 실제 함수
    '''
    length = len(x)
    if length != len(y):
        print("size of x and y aren't same.")
        return
    
    '''
    fdd :    계산되는 제차분이 저장되는 공간. 
            각 차원은 각각의 배열로 구성된다.
            개수는 리스트 크기 - 1이다.(기본 값은 계산이 필요 없음)
    '''
    fdd = [[] for x in range(length)]
    fdd[0].extend(y) # y로 fdd[0] 을 초기화한다.

    for i in range(1,length): # 1,n
        for j in range(length - i): # 0, n-i 
            '''
                i = 1 : range(3), 0, 1, 2에 대해 가능
                fdd[i-1]은 이전 단계에서 구한 제차분을 가리킴.

                j + i 인 이유? : 1단계 : 1간격 차이, 2단계 2간격 차이...
                0!  [1,0] 1-0=1   [2,1,0] 2-0=2   [3,2,1,0] 3-0=3
                1   [2,1] 2-1=1   [3,2,1] 3-1=2
                2   [3,2] 3-2=1
                3
                diff          1               2                 3
                value는 위 규칙에 따라 생성된다.
            '''
            value = (fdd[i-1][j+1] - fdd[i-1][j]) / (x[j+i] - x[j])
            fdd[i].append(value)
    
    args = [fdd[i][0] for i in range(length)]
    #최종적으로 얻게되는 계수

    def innerFunc(val : float):
        '''
        Newton divided-difference 방법으로 생성된 보간 다항식

        @param val : 생성된 보간 다항식에 대입하는 값
        @return result : 보간 다항식에 의한 계산 값
        '''
        result : float = 0
        mulval: float = 1

        for i in range(length):
            temp = args[i] # 계수를 가져온다
            temp = temp * mulval # 계수 * x에 대한 식

            result = result + temp # 값 더하기
            mulval = mulval * (val - x[i]) 
            # x에 대한 식에 다음에 쓸 값 곱
            # 1 -> 1 * (x - 1) -> (x - 1) * (x - 6) 이런식으로.

        return result

    return (args, innerFunc)


if __name__ == "__main__":
    x = [1, 4, 6, 5]
    y = [log(v) for v in x]
    # x 와 y 의 값 생성
    print(Newdd(x, y)[1](2))
    # 위 예제의 답과 비교!
    # 결과 : 0.6287685789084135

Lagrange 보간 다항식

다항식을 표기할 수 있는 방법 중 하나이다. 주어진 점 x을 식에 대입할 때 대응되는 f(x)만 남도록 다항식을 구성한다.

위 식에 x₀, x₁, x₂ 를 대입하면  f(x₀), f(x₁), f(x₂)를 얻을 수 있다.

이를 일반화하면 다음과 같다.