MATH-04. 라그랑주 보간법: 제약 조건을 다항식으로 표현

라그랑주 보간법은 주어진 여러 개의 점을 모두 지나는 특정 차수의 다항 함수를 찾는 방법입니다. 이 방법은 데이터 포인트들 사이의 값을 추정하는 데 유용하게 사용됩니다.

라그랑주 보간법의 원리

라그랑주 보간법의 핵심 아이디어는 각 데이터 포인트를 지나는 개별적인 라그랑주 기저 다항식(Lagrange basis polynomials)을 만든 후, 이들을 선형 결합하여 최종 보간 다항식을 구하는 것입니다.

n+1개의 데이터 포인트 $(x_0, y_0), (x_1, y_1), …, (x_n, y_n)$가 주어졌을 때, 라그랑주 보간 다항식 $P(x)$는 다음과 같이 정의됩니다.

$$P(x) = \sum_{j=0}^{n} y_j L_j(x)$$

여기서 $L_j(x)$는 라그랑주 기저 다항식이며, 다음과 같은 형태를 가집니다.

$$L_j(x) = \prod_{i=0, i \neq j}^{n} \frac{x - x_i}{x_j - x_i} = \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_n)}{(x_j-x_n)}$$

기저 다항식$ L_j(x)$는 다음과 같은 중요한 특징을 가집니다.

• $x = x_j$일 때, $L_j(x_j) = 1$입니다.
• $x = x_i$이고 $i ≠ j$일 때, $L_j(x_i) = 0$입니다.

이러한 특징 덕분에, 전체 보간 다항식 $P(x)$는 각 데이터 포인트 $(x_j, y_j)$를 정확하게 지나가게 됩니다. 예를 들어, $P(x_j)$를 계산하면 $y_j L_j(x_j)$ 항만 남고 나머지는 모두 0이 되어 $P(x_j) = y_j$가 성립합니다.

라그랑주 보간법의 활용: 계산 과정을 다항식으로

영지식 증명의 목표는 "내가 이 계산을 올바르게 수행했다"는 사실을 계산의 입력값이나 중간 과정을 노출하지 않고 증명하는 것입니다. 컴퓨터 프로그램의 모든 계산은 근본적으로 덧셈과 곱셈 같은 간단한 산술 연산의 연속입니다.

이러한 산술 연산들의 관계를 다항식의 관계로 표현할 수 있다면, 복잡한 계산의 검증 문제를 "특정 다항식이 주어진 조건을 만족하는가?"라는 수학 문제로 바꿀 수 있습니다. 다항식은 간결하고 강력한 수학적 특성(예: 특정 점에서만 평가해도 높은 확률로 검증 가능)을 가지고 있어 검증 과정을 매우 효율적으로 만들어 줍니다. 이 변환 과정을 산술화(Arithmetization)라고 부릅니다.

라그랑주 보간법은 "산술화" 과정의 중심에 있습니다.

1. 계산의 실행 흔적(Execution Trace) 만들기

먼저, 증명하려는 계산의 각 단계별 변수 값들을 표로 만듭니다. 이를 실행 흔적(Execution Trace)이라고 합니다.

예를 들어, 피보나치수열의 10번째 항을 계산하는 과정을 증명한다고 가정해 봅시다. $(a_0=1, a_1=1, a_n = a_{n-1} + a_{n-2})$

• 단계(x) : 값(y)
• 0 : 1
• 1 : 1
• 2 : 2
• 3 : 3
• 4 : 5
• ... : ...

이 표는 (0, 1), (1, 1), (2, 2), (3, 3), (4, 5) ... 와 같은 점들의 집합으로 볼 수 있습니다.

2. 라그랑주 보간법으로 다항식 생성

라그랑주 보간법을 사용하면 이 모든 점들을 정확히 통과하는 유일한 최소 차수의 다항식 P(x)를 찾을 수 있습니다.

• P(0) = 1
• P(1) = 1
• P(2) = 2
• P(3) = 3
• ... 등등

이제 이 다항식 P(x)는 피보나치수열 계산의 전체 실행 흔적을 하나의 수학적 객체로 압축한 것과 같습니다.

3. 다항식을 이용한 제약 조건 검증

계산이 올바르게 수행되었는지 검증하는 것은 이제 다항식에 대한 제약 조건(Constraint)을 확인하는 문제로 바뀝니다. 피보나치수열의 제약 조건은 "$a_n = a_{n-1} + a_{n-2}$"입니다. 이를 다항식으로 표현하면 다음과 같습니다.

$$P(x+2) = P(x+1) + P(x)$$

이 등식이 계산이 수행된 모든 단계(예: x = 0, 1, 2, ...)에서 성립한다면, 계산이 올바르게 수행되었다고 할 수 있습니다.