라그랑주 보간법(Lagrange Interpolation) 개념부터 C++ 구현까지

라그랑주 보간법이란?

보간(Interpolation)은 주어진 이산적인 데이터 포인트들 사이에서 새로운 데이터 값을 추정하는 수학적 기법입니다. 그중 라그랑주 보간법(Lagrange Interpolation)은 다항식을 이용해 보간을 수행하는 대표적인 방법으로, 특히 데이터 포인트가 균등하게 분포되어 있지 않은 경우에도 정확한 결과를 얻을 수 있다는 큰 장점이 있습니다.

라그랑주 보간법은 다음과 같은 공식을 따릅니다.

동작 원리

라그랑주 보간법은 각 데이터 포인트마다 하나의 기저 다항식(basis polynomial)을 생성하고, 이들을 함수값과 함께 가중합하여 전체 보간 다항식을 구성합니다. i번째 항은 x가 x_i일 때만 1이 되고 나머지 데이터 점에서는 0이 되는 성질을 가지므로, 최종적으로 만들어진 다항식은 모든 주어진 데이터 점을 정확히 통과하게 됩니다. 계산량은 이중 반복문 구조로 인해 시간 복잡도 O(n²)입니다.

입력 및 출력

Input:
x 값과 f(x) 값 목록, 그리고 구하려는 f(3.25)
x: {0,1,2,3,4,5,6}
f(x): {0,1,8,27,64,125,216}

Output:
라그랑주 보간 결과 f(3.25) = 34.3281

알고리즘

lagrangeInterpolation(x: 배열, fx: 배열, x1)

입력 − 이미 알려진 데이터를 담고 있는 x 배열과 fx 배열, 그리고 값을 구하고자 하는 점 x1

출력: f(x1)의 계산된 값

Begin
    res := 0, tempSum := 0
    for i := 1 to n, do
        tempProd := 1
        for j := 1 to n, do
            if i ≠ j, then
                tempProd := tempProd * (x1 – x[j]) / (x[i] – x[j])
        done
        tempProd := tempProd * fx[i]
        res := res + tempProd
    done
    return res
End

여기서 i = j인 경우를 제외하는 이유는 분모가 0이 되어 나눗셈이 불가능해지기 때문입니다.

C++ 구현 예제

#include<iostream>
#define N 6
using namespace std;

double lagrange(double x[], double fx[], double x1) {
    double res = 0, tempSum = 0;

    for(int i = 1; i<=N; i++) {
        double tempProd = 1;  // 각 반복마다 곱셈 변수 초기화
        for(int j = 1; j<=N; j++) {
            if(i != j) {  // i = j이면 분모가 0이 되므로 제외
                tempProd *= (x1 - x[j])/(x[i] - x[j]);  // 공식에 따라 각 항을 곱함
            }
        }
        tempProd *= fx[i];  // f(xi)를 곱함
        res += tempProd;
    }
    return res;
}

main() {
    double x[N+1] = {0,1,2,3,4,5,6};
    double y[N+1] = {0,1,8,27,64,125,216};
    double x1 = 3.25;
    cout << "Result after lagrange interpolation f("<<x1<<") = " << lagrange(x, y, x1);
}

위 예제에서 사용된 데이터는 f(x) = x³ 함수의 값들이며, 이 범위 안의 임의의 점 x1 = 3.25에서의 함수값을 보간으로 추정합니다.

실행 결과

Result after lagrange interpolation f(3.25) = 34.3281

실제 f(3.25) = 3.25³ ≈ 34.3281이므로, 라그랑주 보간법이 매우 정확한 근사값을 계산해냈음을 확인할 수 있습니다.