C++로 구현하는 라그랑주 보간법(Lagrange Interpolation)

라그랑주 보간법(Lagrange Interpolation)이란?

라그랑주 보간법은 서로 다른 n개의 데이터 포인트 (x₀, y₀), (x₁, y₁), …, (x_n-1, y_n-1)가 주어졌을 때, 이 점들을 모두 통과하는 다항식을 구성하여 임의의 x 값에 대응하는 y 값을 추정하는 고전적인 수치 해석 기법입니다.

보간 공식은 다음과 같습니다.

P(x) = Σ y_i · Π (x − x_j) / (x_i − x_j) (단, j ≠ i)

각 항은 하나의 데이터 포인트에 대응하며, 자신이 담당하는 점에서는 1, 나머지 점들에서는 0이 되는 성질을 갖습니다. 따라서 모든 항을 더하면 주어진 점들을 정확히 지나는 다항식이 완성됩니다.

알고리즘 단계

결과값을 저장할 변수를 0으로 초기화합니다.
각 데이터 포인트 i마다 y_i로 시작하는 항(term)을 생성합니다.
i가 아닌 모든 j에 대해 항에 (x − x_j) / (x_i − x_j)를 곱합니다.
완성된 항을 결과값에 누적합니다.
모든 항의 합을 최종 결과로 반환합니다.

복잡한 로직 없이 공식을 코드로 옮기기만 하면 되므로 구현이 매우 간단합니다. 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n²)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int x, y;
};

double interpolate(Data function[], int xi, int n) {
    double result = 0;
    for (int i = 0; i < n; i++) {
        double term = function[i].y;
        for (int j = 0; j < n; j++) {
            if (j != i) {
                term = term * (xi - function[j].x)
                     / double(function[i].x - function[j].x);
            }
        }
        result += term;
    }
    return result;
}

int main() {
    Data function[] = {{0, 3}, {1, 2}, {6, 9}, {10, 17}};
    // 데이터 포인트는 4개이므로 n에는 반드시 4를 전달해야 합니다.
    cout << interpolate(function, 3, 4) << endl;
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

x = 3인 지점에서 네 개의 데이터 포인트 {(0,3), (1,2), (6,9), (10,17)}를 지나는 보간 다항식의 값은 3입니다.

코드 설명

Data 구조체: 각 데이터 포인트의 x, y 좌표를 함께 저장합니다.
interpolate 함수: 바깥쪽 반복문은 각 항을 순회하고, 안쪽 반복문은 해당 항의 곱셈 부분을 계산합니다.
double() 형 변환: 분모를 실수형으로 변환하여 정수 나눗셈으로 인한 계산 오차를 방지합니다.
n 전달 시 주의: n은 배열에 저장된 실제 데이터 포인트 개수와 일치해야 합니다. 배열 크기를 초과하는 값을 전달하면 정의되지 않은 동작(undefined behavior)이 발생할 수 있습니다.

마무리

이 튜토리얼에서는 라그랑주 보간 공식을 C++ 코드로 구현하는 방법을 살펴보았습니다. 공식을 그대로 코드로 옮기는 것만으로 주어진 데이터 포인트 사이의 임의의 지점에서 함수값을 손쉽게 계산할 수 있습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.