본문 바로가기

(비정기) Mr.K's Post/Weekly paper

Interpolation : Part 1


안녕하십니까 Mr. K입니다

2주 전까지 쓴 소재는 적당히 접기로 결정을 내린 터라, 다른 소재를 찾아야 하는데

소재가 없어서 늦게 찾았다기보단 그저 학교일이 바쁘네요 -_-;


그리고, 이전 소재에서 제목 앞에 붙여놓았던 R.A.M. 이 별로 의미가 없는 것 같아서

(R.A.M. = Realizable Abstract Matter or Material 이었으나, 이런걸 달아놓지 않더라도 수학적인 것에 대해 얘기를 하다보면 무의식중에 무한대나 무리수 등등, 컴퓨터에서 똑같이 따라하지만 실수에서 되는 계산이 깔끔하게 떨어지지 않는(예외는 있습니다, Maple이라는 프로그램은 √2를 입력하고 엔터를 치면 결과값에 그대로 √2가 출력이 됩니다) 경우가 많기 때문에 그냥 그때그때 해당하는 주제가 나오면 언급하기로 했습니다)

다시 마음이 바뀌기 전까지는 아마 '제목 : 연재회수' 꼴로 계속 적을 듯 합니다 ㅋ


그럼 시작해보지요



우리가 수학을 하다보면 종종 주어진 명제에 대해 '그 역도 성립하는가?' 를 따지게 되곤 합니다

아마 이 보간법(interpolation)이라는 것도 그렇게 출발해서 나온 것이 아닐까 생각해봅니다

어떤 함수 f(x)가 주어져 있을 때, 우리는 그 함수 위에 있는 몇 개의 점을 정확하게 집어낼 수 있습니다

그러면 반대로,
몇 개의 점이 주어져 있을 때, 그 점들을 완벽하게 지나는 함수를 찾아낼 수 있을까?

-라는 것이 이번 소재의 핵심 내용입니다


아래의 그림을 보시죠


좌표평면 위에 3개의 점이 있습니다

각각은 (1, 2), (2, 3), (3, 6)이라는 좌표를 가지고 있지요

3개의 점을 지나는 2차 다항식은 유일하게 존재합니다
(실제로 N+1개의 점을 지나는 N차 다항식은 유일하게 존재합니다, 이유가 궁금하다면 생각해보세요 :D)


그래서 함수 f(x)를 f(x) = a + bx + cx² 이라 놓고 아래와 같이 풀면



원하는 f(x) = 3 - 2x + x² 를 얻어낼 수 있습니다


그런데 사실,
고등학교과정까지만 잘 마치면 N+1개의 점을 지나는 N차 다항식도 연립방정식 풀듯이 풀어내서 구할 수 있습니다

다만 시간이 오래걸리고 계산 오차가 발생할 확률이 클 뿐.. -_-;

그래서 그 시간과 오차를 줄여주기 위해 새로운(?) 개념을 도입합니다



이 때, 위의 그림에서 다음과 같은 행렬을 Vandermonde matrix라고 합니다
(검색좀 때려보니 Vandermonde는 '밴더몽드'라고 읽는 것 같더군요)

n×n Vandermonde matrix, 책에 따라서는 이것의 transpose를 이것으로 칭하기도


이 행렬의 역행렬이 존재한다면, 다음과 같이 다항식의 계수를 구할 수도 있습니다



만약 주어진 N+1개의 점들의 x좌표들이 단 한 개도 중복되지 않는다면, N×N 밴더몽드 행렬은 행렬식이 0이 아니게 되고,
(이유가 궁금하다면 생각해보세요 :D 선형대수학을 배웠다면 금방 답이 나올겁니다)

역행렬을 구해서 위의 식처럼 계산하면 우리는 원하는 N차 다항식을 구할 수 있습니다


역행렬을 구하는 과정은 가우스-조르단의 소거법(Gauss-Jordan elimination)을 사용하였습니다
이것은 수식으로 보이지 않고 넘어가겠습니다 -_-;


이것을 코드로 쓰면 다음과 같습니다


그러나 이 방법의 단점은 구하고자 하는 다항식의 차수가 커지면 커질 수록 시간이 오래걸린다는 단점이 존재합니다

학술제 준비로 다음주 포스트는 쉬고, 다다음주에 올리게 될 포스트에서는
차수에 큰 영향을 받지 않고 빠르게 계산이 될 것 같은 Newton Forward Differences에 대해 얘기하겠습니다



덧. 크롬에서 그림파일 업로드하는 속도가 전에 비해 훨씬 빨라졌군요 -_-b

(포스팅 소요시간 : 약 110분)