2020년 9월 28일 월요일

다항 함수 보간(Polynomial Interpolation)

[경고] 아래 글을 읽지 않고 "다항 함수 보간"을 보면 바보로 느껴질 수 있습니다.


[그림 1] 이산적인 자료점을 통과하는 다함 함수 보간의 예(출처: wikipedia.org)

임의의 함수를 간단한 다항 함수(polynomial)로 근사하는 효과적인 기법은 다항 함수 보간(polynomial interpolation)이다. 다항 함수 보간의 기반이 되는 바이어슈트라스 근사 정리(Weierstrass approximation theorem)는 대(大)수학자 바이어슈트라스Karl Weierstrass(1815–1897)가 70세 되던 해인 1885년바이어슈트라스 70세, 조선 고종 시절에 발표했다[1]. 해석학(解析學, analysis)은 코쉬Augustin-Louis Cauchy(1789–1857)를 선두로 하여 여러 수학자가 시작했지만, 현대 해석학으로 발전시킨 두드러진 수학자는 바이어슈트라스이다. 보통의 천재 수학자라고 하면 가우스Carl Friedrich Gauss(1777–1855)처럼 어릴 때부터 두각을 나타내어 죽을 때까지 천재성을 유지한다고 상상한다. 하지만 바이어슈트라스는 천재 수학자의 전형에서 많이 벗어나 있다. 1834년바이어슈트라스 19세, 조선 순조 시절에 아버지의 기대를 따라 공공 재무와 행정을 배울 수 있는 본 대학교(University of Bonn)에 입학했지만, 자신의 내면에 있는 수학 사랑으로 인해 방황했고 많이 아파했다. 대학 시절 동안에는 독학으로 틈틈이 수학을 공부하면서 자신의 수학적 재능도 확신했다. 하지만 마음에 잠재된 순종과 열망 사이의 압박이 계속 있었다. 결국 1838년에 수학자가 되기로 확실히 결심한 후, 여러 시험들을 치르지도 않고 홀연히 본 대학교를 떠나버렸다. 자식을 이기는 부모가 없다고, 아버지는 고등학교 교사라도 되라고 바이어슈트라스를 뮌스터 아카데미(Akademie Münster, Münster Academy)로 보냈다. 독일 학제에서 아카데미는 대학교보다 수준이 낮지만 고등 교육을 제공하는 비인증 교육 기관이다. 아카데미 뮌스터는 평범한 학교였지만 비범한 구더만Christoph Gudermann(1798–1852)이 있었다. 짧은 기간이었지만 구더만으로부터 바이어슈트라스는 제대로 된 고등 수학 교육을 받았다.

[그림 2] 예전 아카데미 뮌스터였던 뮌스터 대학교의 전경(출처: wikipedia.org)

교사 시험을 통과한 바이어슈트라스는 여러 김나지움(Gymnasium)을 돌면서 수학 외에도 다양한 과목들을 가르쳤다.[독일 학제에서 김나지움은 대학 진학을 준비하는 고등학교이다.] 교사 업무가 끝나면 모든 시간을 수학 연구에 쏟아부었다. 바이어슈트라스의 노력은 1854년바이어슈트라스 39세, 조선 철종 시절에 발표한 초타원 적분(hyperelliptic integral)에 대한 논문으로 빛을 발했다. 예나 지금이나 논문 한 편으로 명성을 얻기는 매우 어렵지만, 늦깎이 천재인 바이어슈트라스는 달랐다. 같은 해에 쾨니히스베르크 대학교(University of Königsberg)에서 명예 박사(Doktor honoris causa, honorary doctorate) 학위도 받았다. 조금은 늦었지만 꿈에도 그리던 프리드리히 빌헬름 대학교(Friedrich-Wilhelms-Universität, Friedrich Wilhelm University, 흔히 베를린 대학교라 부름)에서 1856년부터 수학 강의와 연구를 할 수 있었다.[여러 계약 문제로 정식 교수 임용은 1864년에 된다.] 베를린 대학교에는 바이어슈트라스 외에 뛰어난 수학자인 쿠머Ernst Kummer(1810–1893)와 크로네커Leopold Kronecker(1823–1891)도 있었다. 연구 능력과 더불어 바이어슈트라스의 수학 강의는 명강의로 소문나서 베를린 대학교를 수학의 중심으로 만들었다. 하지만 바이어슈트라스는 특이하게도 논문 발표를 거의 하지 않았다. 바이어슈트라스의 수학적 결과물은 강의로 전달되거나 제자가 간접적으로 발표했다. 바이어슈트라스보다 먼저 해석학을 시작한 코쉬는 성향이 매우 달랐다. 코쉬는 수학사에서 가장 많은 논문을 발표한 두번째 인물이다.[수학 논문 발표의 일등은 당연히 오일러이다. 오일러는 약 900편, 코쉬는 약 800편의 논문을 발표했다.] 코쉬가 발표한 논문만 모은 책이 27권 분량이나 된다. 어쨌건 논문 발표 성향은 정반대인 코쉬와 바이어슈트라스가 해석학이란 새로운 세상을 만들었다.
논문에 관심 없던 바이어슈트라스가 70세에 몸소 논문으로 발표한 재미있는 바이어슈트라스 근사 정리를 직접 증명해보자[1], [2].

[바이어슈트라스 근사 정리] [2]
구간 $[a, b]$에서 연속인 $f(x)$에 균등 수렴하는 다항 함수 $P(x)$가 존재한다.

[증명]
구간 $[a, b]$에서는 $f(x)$와 같으면서 전체 실수 영역에서 균등 연속인 함수(uniformly continuous function) $g(x)$를 다음처럼 정의한다.

                  (1)

함수 $g(x)$는 구간 $[a-1, b+1]$에서 연속이므로 균등 연속 함수가 된다. 다음 단계로 $g(x)$를 바이어슈트라스 변환(Weierstrass transform)한다.

                  (2)

여기서 $|x| > R$이면 $g(x)$는 항상 $0$이라 가정한다. 가우스 함수(Gaussian function)를 구성하는 $e^{-x^2}$은 테일러 급수에 대해 균등 수렴(uniform convergence)하므로, 임의의 작은 양의 $\epsilon$에 대해 $n \ge N$이 성립하면, 다음 부등식이 항상 성립한다.

                  (3)

여기서 모든 $x$에 대해 $|g(x)| \le M$이 성립한다. 식 (2)처럼 바이어슈트라스 변환이 되도록, 식 (3)에 $|g(x)|$를 곱해서 적분해서 정리한다.

                  (4)

여기서 다항 함수를 다음처럼 새롭게 정의한다.

                  (5)


                  (6)

여기서 $|x - s| < \delta$, $0 < h \le h_0$, $h_0 < \sqrt{\pi} \epsilon \delta / (4M)$을 만족한다. 따라서 다음 부등식이 성립해서 $P(x)$는 $g(x)$에 균등 수렴한다.

                  (7)
______________________________

식 (5)에서 유한 합을 결정하는 $N$이 정해지면, $P(x)$의 차수는 최대 $2N$이 될 수 있다.
바이어슈트라스 근사 정리가 보장하는 다항 함수는 식 (5)처럼 구할 수 있다. 하지만 [그림 1]처럼 자료점(data point)에서만 함수값을 정확히 알 경우는 어떻게 해야 할까? 이때는 다항 함수의 근(root) 특성을 이용해서 쉽게 다항 함수의 계수를 정할 수 있다.

[그림 3] 서로 다른 실근을 갖는 4차 함수의 예(출처: wikipedia.org)

[그림 3]은 서로 다른 실근(real root)을 갖는 4차 함수를 보여준다. 여기서 실근은 $f(x)$ = $0$을 만드는 실수인 $x$이다. 대수학의 기본 정리(代數學 基本定理, fundamental theorem of algebra)에 의해 4차 함수는 4개의 근을 가질 수 있다. 그러면 실근 위치 $x_k$의 함수값을 0이 아니고 새롭게 $y_k$라 가정해서 다음과 같은 3차 함수를 손쉽게 만들 수 있다.

             (8)

식 (8)의 개념을 더 확장해서 일반화하면 제$n$차 라그랑주 보간(Lagrange interpolation) $L_n(x)$를 얻을 수 있다.

                  (9)

여기서 $L_n(x)$는 $n+1$개 근으로 정의한 제$n$차 다항식, $L_n(x)$를 구성하는 $l_k (x)$는 라그랑주 다항식(Lagrange polynomial)이라 부른다. 예를 들어, 식 (8)은 자료점 4개로 만든 제3차 라그랑주 보간이며, [그림 1]에는 자료점 7개를 가진 제6차 라그랑주 보간을 쓸 수 있다. 그래서 식 (9)에 정의한 라그랑주 보간은 $n+1$개 자료점인 $(x_0, y_0)$, $(x_1, y_1)$, $\cdots$, $(x_n, y_n)$의 중간값을 매끈하게[혹은 미분 불연속 없이] 채울 수 있다. 이러한 성질은 라그랑주 다항식이 항상 만족하는 $l_k(x_m)$ = $\delta_{km}$에 기인한다. 여기서 $\delta_{km}$은 크로네커 델타(Kronecker delta)이다. 다음 단계로 라그랑주 보간의 최대 오차를 다음처럼 증명한다.

[라그랑주 보간의 최대 오차]

                  (10)

여기서 자료점의 개수는 $n+1$, $f(x)$가 정의된 구간은 $[a, b]$, $a \le \xi \le b$, $R_n (x)$는 라그랑주 보간의 잉여항(remainder term of Lagrange interpolation), $f^{(n)}(x)$는 $f(x)$의 $n$번 미분, $f(x)$ = $L_n(x) + R_n (x)$이다.

[증명]
원래 함수 $f(x)$와 라그랑주 보간 $L_n (x)$의 차이를 표현하는 잉여항을 $R_n(x)$라 한다. 이 함수들을 이용해 새로운 함수 $F(x)$를 정의한다.

                  (11)

여기서 $L_n (x)$는 $n$차 다항식, $R_n (x)$는 $n+1$차 다항식, $C$는 결정해야 할 상수이다. 함수 $F(x)$는 $x_k$ 외에도 $\chi$에서 $0$이어서, $x$ = $\chi$에서 라그랑주 보간의 잉여항까지 포함한 오차 추정은 $0$이라 생각한다. 그러면 $x$ = $\chi$에서 $f(\chi)$ = $L_n(\chi) + R_n(\chi)$가 성립한다. 결국 $F(x)$는 $n+2$개의 근 혹은 영점(zero)을 가지게 된다. 롤의 정리(Rolle's theorem)에 의해 두 근 사이에는 미분이 $0$인 점이 하나 이상 존재하므로, $F(x)$의 $n+1$번 미분은 다음 관계를 만족한다.

                  (12)

여기서 $\xi$는 구간 $[a, b]$ 사이에 있으며 $F^{(n+1)}(\xi)$ = $0$이 되게 하는 점이다. 따라서 라그랑주 보간의 잉여항은 다음과 같다.

                  (13)

식 (13)을 이용해 잉여항의 최대값을 구하면 다음 부등식을 얻을 수 있다.

                  (14)
______________________________

라그랑주 보간의 잉여항은 테일러 급수의 라그랑주 잉여항과 완전 동일하다. 이런 특성은 우연이 아니다. 테일러 급수는 완비성이 있기 때문에 함수 $f(x)$를 무한 급수로 정확히 전개할 수 있다. 라그랑주 보간은 다항 함수 보간이므로, 바이어슈트라스 근사 정리에 의해 균등 수렴이 보장된다. 따라서 오차에 해당하는 잉여항은 다를 수가 없다.
식 (9)에 있는 라그랑주 보간을 $x$에 대한 다항식으로 다음처럼 간단히 표현할 수 있다.

                  (15)

여기서 $a_i$는 식 (9)에 있는 다항식을 정리해서 얻는 $x^i$에 대한 계수이다. 라그랑주 보간의 특성으로 인해 식 (15)는 $(x_0, y_0)$, $(x_1, y_1)$, $\cdots$, $(x_n, y_n)$을 항상 만족한다. 이런 성질을 이용해 연립 방정식(simultaneous equations)을 구성한다.

                  (16)

보기 편하도록 식 (16)을 행렬 방정식으로 구성한다.

                  (17)

식 (17)에 등장한 $(n+1)\times(n+1)$ 차원을 가진 정방 행렬(square matrix)방데르몽드 행렬(Vandermonde matrix)이다. 만약 $x_i$[$i$ = $0, 1, \cdots, n$]의 위치가 모두 다르다면, 이 방데르몽드 행렬은 행렬식이 $0$이 아니어서 역행렬이 반드시 존재한다. 따라서 라그랑주 보간에 의해 $a_i$는 정확히 단 하나로만 결정된다.
다항 함수 보간의 또 다른 유명한 예는 뉴턴Isaac Newton(1643–1727)이 1687년뉴턴 44세, 조선 숙종 시절에 공개한 뉴턴 보간(Newton interpolation)이다. 뉴턴 보간은 다항식의 근을 바탕으로 함수값을 간단하게 보간한다.

[뉴턴 보간]
자료점 $(x_0, y_0)$, $(x_0, y_0)$, $\cdots$, $(x_n, y_n)$은 $n$차 다항식 $p_n(x)$로 모든 점에서 정확히 보간된다.

                  (18)

여기서 $p_0(x)$ = $y_0$, $x$ = $x_0, x_1, \cdots, x_{n-1}$에서 $w_n(x)$ = $0$ 및 $p_n(x)$ = $p_{n-1}(x)$, $k$ = $1,2,\cdots,n$에 대해 $a_k$는 $(x_k, y_k)$로 결정하는 분할 차분(divided difference)이다.

[증명]
1차부터 시작하는 다항식의 재귀 관계로부터 증명한다.

             (19)
______________________________

뉴턴 보간의 핵심인 분할 차분 $a_n$의 특성을 이해하기 위해 $a_2$를 풀어쓴다.

                  (20a)

                  (20b)

식 (20)에서 유추해서 분할 차분을 정의하고 재귀 관계를 밝힌다.

[분할 차분의 재귀 관계] [4]

                  (21)

여기서 $a_0$ = $[y_0]$ = $y_0$이다.

[증명]
수학적 귀납법(數學的歸納法, mathematical induction)에 따라 $n$에 대해 식 (21)이 성립한다고 가정해 새로운 다항 함수 $r(x)$를 정의한다.

                  (22a)

                  (22b)

함수 $r(x)$에 $x$ = $x_0, x_1, \cdots, x_n, x_{n+1}$을 차례로 넣으면, $r(x_k)$ = $y_k$가 항상 성립한다. 따라서 식 (22a)에 정의한 $r(x)$는 $p_{n+1}(x)$와 동일하다. 이 $p_{n+1}(x)$의 최고차 항인 $x^{n+1}$에 곱한 계수가 분할 차분 $a_{n+1}$이다. 식 (22a)에서 $x^{n+1}$의 계수를 찾아서 $a_{n+1}$을 유도한다.

                  (23)

여기서 $w_{n+1}(x)$ = $(x-x_n) w_n(x)$ = $(x-x_0) v_n(x)$이다.
______________________________

뉴턴 보간의 놀라운 점 중 하나는 미분(differentiation)과의 관계이다. 자료점의 $x$ 간격이 $\Delta x$로 동일해 $x_n$ = $n\Delta x$인 경우만 고려해 분할 차분 $a_k$를 각각 계산한다.

                  (24)

여기서 $p_1'(x)$는 $p_1(x)$의 미분이다. 식 (24)가 암시하는 추측에 따르면 $a_n$은 미분 계수와 분명 연결된다. 평균값의 정리(mean value theorem)를 다시 적용해서 $a_n$과 미분 계수를 등식 관계로 만들 수 있다.

[분할 차분의 평균값 정리]

                  (25)

여기서 $f^{(n)}(x)$는 $f(x)$의 $n$계 미분이다.

[증명]
함수 $f(x)$와 뉴턴 보간 $p_n(x)$의 차이를 $g(x)$ = $f(x) - p_n(x)$로 나타낸다. 함수 $f(x)$와 $p_n(x)$는 $x$ = $x_0, x_1, \cdots, x_n$에서 같아서 $g(x)$는 최소 $n+1$개의 영점(zero)을 가진다. 롤의 정리(Rolle's theorem)에 따라 $g(x)$를 $n$번 미분해도 영점 하나는 남게 된다.

                  (26)

여기서 $\xi$는 영점이다.
______________________________

식 (25)는 분명히 분할 차분으로 고계 미분 계수를 근사화하는 방법을 보여준다. 1계 미분을 $a_1$로 근사화하고, 이 값을 다시 써서 $a_2$를 만들어 2계 미분도 어림한다. 이 과정을 계속 반복하면 어떤 고계 미분이든 분할 차분으로 대략 계산할 수 있다. 분할 차분으로 미분 계수를 근사화해서 미분 방정식을 차분 형태로 푸는 방법은 유한 차분법(finite difference method, FDM)으로 부른다.
식 (24)를 더 간단하게 얻기 위해, $p_n(x)$를 $n$번 미분해서 $a_n$ = $p_n^{(n)} (x)\mathbin{/} n!$로 표현할 수 있다. 이 결과를 도입해서 식 (18)을 미분으로 바꾼다.

                  (27)

식 (27)은 왠지 낯익은 공식으로 보인다. 맞다. 바로 테일러 급수(Taylor series)의 초기 형태이다. 간격 $\Delta x$를 $0$으로 보고 차수 $n$을 계속 높이면, 식 (27)의 유한 곱(finite product)은 $(x-x_0)^k$로 바뀌고 식 (25)에 의해 $p_k^{(k)}(x_0)$ = $f^{(k)}(x_0)$이 되어서 테일러 급수와 동일한 공식이 된다. 따라서 뉴턴이 만든 뉴턴 보간은 함수값을 세밀히 보간하는 동시에 간격을 줄이면 그대로 테일러 급수가 되어 정확한 함수값도 얻을 수 있다. 뉴턴 보간과 테일러 급수의 연결성을 통해 뉴턴은 뉴턴임을 다시 확인할 수 있다.  

[참고문헌]
[1] K. Weierstrass, "Über die analytische Darstellbarkeit sogenannter willkürlicher Funktionen einer reellen Veränderlichen (About the analytical representability of so-called arbitrary functions of a real variable)," Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin (Session Reports of the Royal Prussian Academy of Sciences at Berlin), pp. 633–639 & 789–805, 1885.
[2] A. R. Schep, "Weierstrass' proof of the Weierstrass approximation theorem," University of South Carolina, May 2007. (방문일 2020-09-27)
[3] V. K. Dzyadyk and I. A. Shevchuk, Theory of Uniform Approximation of Functions by Polynomials, Göttingen: Walter de Gruyter, 2008.
[4] Cambridge Numerical Analysis Group, "1.2 Divided differences: a definition," Numerical Analysis, 2010. (방문일 2024-01-14)

[다음 읽을거리]

댓글 없음 :

댓글 쓰기

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.