[수치해석] 6. Lagrange Interpolation

Lagrange Interpolation

Weierstrass Approximation Theorem

• Algebric Polynomial
  • 임의의 f(x)에 대한 근사식
  • $P_n(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$
    

    

  • 함수 f가 [a, b]에서 연속할 경우, $|f(x)-P(x)|<\epsilon$인 P가 존재
  • 오차 $\epsilon$이 작아질수록 차수 n은 증가

Taylor Polynomial

• 함수 f가 x=a에서 (n+1)번 미분 가능할 경우
  • $f(x)=f(0)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+...+\frac{f^n(a)}{n!}(x-a)^n+\frac{f^{n+1}(\psi_x)}{(n+1)!}(x-a)^{n+1}$
  • n+1차항 : Taylor 급수의 error
  • $f(x)=P(x)=f(0)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+...+\frac{f^n(a)}{n!}(x-a)^n$으로 근사할 수 있다
  • $\psi_x$ : x ~ a 사이의 임의 값
• ex. x=0에서의 $f(x)=e^x$
  • f는 미분해도 모두 동일한 함수
  • x=0 대입시 f=1
  • $\therefore e^x\simeq1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}$
  • error : $\frac{e^{\psi_x}}{(n+1)!}x^{n+1}$
• Taylor Polynomal의 수렴 반경
  • ex. 1/x의 taylor polynomal : 전개할수록 오차가 커짐
  • 1/x를 x=1에서 전개 시 x는 0 ~ 2를 벗어날 수 없음(대칭성)
  • 수렴 범위를 벗어날 경우 taylor polynomal은 발산
• Weierstrass theorem : P가 taylor 급수 ≠ P(x)가 수렴한다

Lagrange Polynomial

• Polynomal Interpolation(1차 식으로 근사)
  • 점 [x0, y0], [x1, y1]의 경우 $P_1(x)=\frac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0$
• Lagrange Polynomial : Polynomial Interpolation을 구조화
  • $L_0(x)=\frac{x-x_1}{x_0-x_1},\ L_1(x)=\frac{x-x)0}{x_1-x_0}$로 정의
  • $P_1(x)=f(x_0)L_0(x)+f(x_1)L_1(x)$
• 2차 Lagrange Pilynomial : 점 [x0, y0], [x1, y1], [x2, y2]
  • $L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)},\ L_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)},\ L_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
  • $P_2(x)=f(x_0)L_0(x)+f(x_1)L_1(x)+f(x_2)L_2(x)$
• 자기 자신을 제외한 나머지 점으로 규칙성을 갖는 식 수립 가능
  • n+1개 점 > n차 Lagrange Polynomial
  • general case : n차 다항식의 k번째 점의 lagrange basis $L_{n,k}(x)$
    $=\Pi\frac{x-x_n}{x_k-x_n}=\frac{(x-x_0)...(x-x_{k-1})(x-x_{k+1})...(x-x_n)}{(x_k-x_0)...(x_k-x_{k-1})(x_k-x_{k+1})...(x_k-x_n)}$
    

    

InterPolating Error bound

• Lagrange Polynomial로 구한 근사식
  • $f(x)=P(x)+\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
    • $\zeta(x)$는 a~b 사이의 임의의 점
  • $P(x)=f(x_0)L_{n,0}(x)+...+f(x_n)L_{n,n}(x)=\sum^{n}_{k=0}f(x_k)L_{n,k}(x)$
  • Error : $\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
• 증명 과정
  • $x\not ={x_k}$라고 할 때, $g(t)$함수를 다음과 같이 정의
    • $g(t)=f(t)-P(t) - [f(x)-P(x)]\frac{(t-x_0)(t-x_1)...(t-x_n)}{(x-x_0)(x-x_1)...(x-x_n)}=f(t)-P(t) - [f(x)-P(x)]\Pi^n_{i=0}\frac{(t-x_i)}{(x-x_i)}$
  • P는 f의 interpolation이므로 모든 x값에 대해
    $g(x_n)=f(x_n)-P(x_n)=0$ ($Pi$항은 분자 식에 의해 0)
  • Rolle's Theorem : n개 점에서 함수가 0이면, n-1차 미분의 값이 0인 점이 존재
    • g(t)는 $x, x_0, x_1, ..., x_n$의 구간으로 n+2개의 함수가 0인 점이 존재하므로, n+1차 미분이 0인 점 $\zeta$가 존재
    • $f^{n+1}(\zeta)-P^{n+1}(\zeta)-[f(x)-P(x)]\frac{d^{n+1}}{dt^{n+1}}[\Pi^n_{i=0}\frac{t-x_i}{x-x_i}]_{t=\zeta}$
    • P는 최대 n차식이므로 $P^{n+1}=0$
  • $g^{n+1}(\zeta)=0= f^{n+1}(\zeta)-0-[f(x)-P(x)](n+1)!\Pi^n_{i=0}\frac{1}{x-x_i}$
    • $(t-x_i)$는 n+1차항이므로 n+1번 미분하면 (n+1)!
  • 위 식을 f(x)에 대해 정리하면
    $f(x)=P(x)+\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
  • 즉 원래 식과 근사식의 차 $f(x)-P(x)=\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$가 Error값이 됨
    • 최대 오차는 $max|\frac{f^{n+1}(\zeta(x))}{(n+1)!}|\cdot max|(x-x_0)(x-x_1)...(x-x_n)|$