Jacobi Iterative Method

• 행렬 Ax=b를 풀 때
  • 초기 가정 $x^0$을 가정하고, $x^k$에 대해 k의 극한 계산
• Jacobi Iterative method
  • $x_i=\sum_{j=1,j\not ={i}}(-\frac{a_{ij}x_j}{a_{ii}})+\frac{b_i}{a_{ii}}$
  • 2x2 행렬에 대해, $\\a_{11}x_1+a_{12}x_2=b_1\\a_{21}x_1+a_{22}x_2=b_2$
  • 위 식에서 $\\x_1=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2\\x_2=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1$
  • $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^n$
  • 계산된 해에 대해 $\frac{||x^k-x^{k-1}||_\infty}{||x^k||_\infty}$가 일정 오차 이하가 될 때까지 반복
• More general representation
  • 행렬 A를 $A=D-L-U$로 분리
    • D : 대각행렬 / L : Lower Triangle / U : Upper Triangle
  • $Ax=b$를 계산하면 $x=D^{-1}(L+U)x+D^{-1}b$, 즉 $x=Tx+c$꼴로 변환
  • $\rho(T)<1$ 혹은 $||T||_\infty$임을 증명하면 $x^k=Tx^{k-1}+c$가 수렴함을 증명할 수 있다.

Gauss-Seidel Method

• $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^{n+1}$

• $x^n=x$로 수렴하기 위한 조건

  • $T^nx^0$가 0으로 수렴
  • $S^nc$는 x로 수렴
  • 즉 $\rho(T)<1,\ ||T||_2<1,\ ||T||_\infty<1$중 하나를 만족
    • 앞으로 갈수록 sharp한 수렴, 계산은 복잡
  • 한 열에서 사용한 결과값을 바로 다음 열에 사용하므로 계산 시간이 줄어듬
  • $\begin{bmatrix} b1\\ b2 \end{bmatrix}=\begin{bmatrix} a_{11}\ 0\\ a_{21}\ a_{22} \end{bmatrix}+\begin{bmatrix} 0\ a_{12}\\ 0\ 0 \end{bmatrix}$

• $Dx^{n+1}=Lx^{n+1}+Ux^n+b$

  • D : A행렬의 대각선 원소 / L : L행렬 대각원소의 아랫부분 / U : L행렬 대각행렬의 윗부분

• $\rho(T)<1$일 때, $(I-T)^{-1}$을 만족

  • $S_n=(I-T)^{-1}=I+T+T^n+...+T^n$
  • $(I-T)S_n=I-T^{n+1}$
  • n이 발산하면 S는 I로 수렴

• fixed-point iteration 형태의 표현
  • $x^k=Tx^{k-1}+c$
  • jacobi iteration : $T_j=D^{-1}(L+U)$
  • gauss-seidel : $T_g=(D-L)^{-1}U$

Successive Over Relatxation(SOR)

• $x^{n+1}=(1-w)x^n+wx_g^{n+1}$
  • w : relaxation parameger
  • $w_g$ : gauss-seidel로 계산한 값
• Residual Vector
  • gauss-seidel method에서 $x^{n+1}=\frac{1}{a_{11}}[-a_{12}x_2^n+b_1]$
  • 즉 $a_{11}x_1=a_{11}x_1^{n+1}-a_{11}x_1^n\\=-a_{11}x_1^n-a_{12}x_2^n+b_1=r_1^n$으로 정의
  • residual form : $x^{n+1}=x^n+D^{-1}r^n$
  • SOR residual form : $x^{n+1}=x^n+wD^{-1}r^n\\x^{n+1}=(1-w)x^n+wD^{-1}(Lx^{n+1}+Ux^n)$

• norm : data 간의 거리 / 판정의 기준

Vector norm

• $\R^n$은 n차원 공간 내의 함수$\{(x_1, x_2, ..., x_n|x \in R\}$를 의미
• vector norm의 성질
  • $||\bold{x}||\geq0\ for\ all\ x\in\R^n$
  • x가 영벡터일 때만 $||\bold{x}||=0$
  • 모든 실수 $\alpha$에 대해 $||\alpha\bold{x}||=|\alpha|||\bold{x}||$
  • triangle inequality : $||\bold{x+y}||\leq||\bold{x}||+||\bold{y}||$
• Cauchy-Bunyakovsky-Schwarz Inequality
  • 벡터 x, y에 대해서
  • $x^ty=\sum^n_{i=1}x_iy_i\leq\{\sum x_i^2\}^{1/2}\{\sum y_i^2\}^{1/2}=||x||_2||y||_2$

• $l_2$ norm과 $l_\infty$ norm
  • 전자는 square norm, 후자는 max norm이라고 칭함
  • 선형대수에서 가장 보편적으로 사용되는 norm
  • $l_2$ norm : $||\bold{x}||_2=\{\sum_{i=1}^nx^2_i\}^{1/2}$
    

    

    • 2차원 실수 공간의 $l_2$ < 1 norm
  • $l_\infty$ norm : $||\bold{x}||_\infty=max|x_i|$
    

    

    • 2차원 실수 공간의 $l_\infty$ < 1 norm
• ex. 벡터 x = (-1, 1, -2)인 경우
  • $l_2$ norm = $\sqrt{6}$
  • $l_\infty$ norm = 2

• Cauchy-Bunyakovsky-Schwarz Inequality의 증명
  • 임의 벡터 x, y가 영벡터가 아닐 때
  • $0\leq||x-\lambda y||_2^2=\sum(x_i-\lambda y_i)^2$
  • 즉 $2\lambda\sum x_iy_i\leq\sum x_i^2 + \sum y_i^2=||x||_2^2+\lambda^2||y||_2^2$
  • $||x||_2>0,\ ||y||_2>0$이므로 $\lambda=||x||_2/||y||_2$로 가정하면 $2\sum x_iy_i\leq2||x||_2||y||_2$

• norm 간의 비교
  • $||x||_\infty\leq||x||_2\leq\sqrt{n}||x||_\infty$ ( n : 차원 )
  • 증명 : $||x||_\infty=|x_j|^2\leq\sum x_i^2=||x||_2^2 \\ ||x||_2^2\leq nx_j^2=n||x||_\infty^2$

Matrix norm

• vector 계산에서 행렬은 변환을 담당(X 공간에서 Y공간으로의 이동)
  • function : 벡터 or 실수 > 실수
  • operator : 벡터 > 벡터
• Matrix norm은 vector norm과 유사한 특성을 보유
  • $||\bold{A}||\geq0$
  • A가 영행렬일 때만 $||\bold{A}||=0$
  • 모든 실수 $\alpha$에 대해 $||\alpha\bold{A}||=|\alpha|||\bold{A}||$
  • triangle inequality : $||\bold{A+B}||\leq||\bold{A}||+||\bold{B}||$
  • $||\bold{AB}||\leq||\bold{A}||||\bold{B}||$

• Matrix Norm : $||A||=max_{||x||=1}||Ax||$
• Natural(Mmatrix) Norm
  • 영벡터가 아닌 임의 벡터 z가 있을 때, unit vector $x=z/||z||$로 정의
  • 즉 $||A||=max_{z\not ={0}}\frac{||Az||}{||z||}=max_{||x||=1}||Ax||$
• Matrix norm은 vector norm에 종속되어 결정

• A가 n x n크기의 행렬일 때, $||A||_\infty = max\sum|a_{ij}|$
  • $||A||$는 행렬 A와 unit vector 사이의 곱이므로, 무한 차원의 norm은 행의 절댓값 합 중 최댓값으로 나타나게 된다.

LU decomposition

• $2x_1+x_2=1,\ x_1+2x_2=3$의 방정식 가정
  • $\begin{bmatrix} 2\ 1:1\\ 1\ 2:3 \end{bmatrix}$ : augmented matrix
  • x계수 행렬을 system matrix라고 함
• Gauss Elimination : 계수 소거
  • $\begin{bmatrix} 2\ 1:1\\ 0\ \frac{3}{2}:\frac{5}{2} \end{bmatrix}$
  • 2열에 1열 / 2한 것을 빼서 계산
  • $x_2=5/3$, $x_1=-1/3$
• $Ax=b$를 Gaussian Elimination을 통해 $Ux=b'$으로 변환
  • $U=\begin{bmatrix} a\ b\\ 0\ d \end{bmatrix}$꼴의 행렬

• $Ax=b_1,\ Ax=b_2,\ Ax=b_3, ...$의 행렬식을 푼다고 하면 각 행렬마다 Gauss Elimination이 적용되어야 함

  • Lower - Triangle Matrix L : $L=\begin{bmatrix} a\ 0\\ c\ d \end{bmatrix}$
  • Gauss-Elimitation 연산을 기억하는 효과
  • $A=LU$

• LU Decomposition

  • $A = \begin{bmatrix} 2\ 1\\ 1\ 2 \end{bmatrix} = LU$
    • $U = \begin{bmatrix} 2\ 1\\ 0\ \frac{3}{2} \end{bmatrix}$
    • $L = \begin{bmatrix} 1\ 0\\ k\ 1 \end{bmatrix}$
      • k = 상수항 제거를 위해 Gauss Elimination에 적용한 계수
  • $Ax=b\rarr LUx=b$

• Gauss Elimitnation은 계수 행렬 A에서 항 하나가 제거된 Lower Matrix L로 변환하는 과정을 거침

• LU-Decomposition은 계수행렬 A를 L과 U의 곱으로 변환

  • 우항이 바뀌어도 LU식은 변화 없음

• m x n 행렬의 LU decomposition
  • i행 j열 위치의 값을 $a_ji$라고 할 때,
  • j번째 행의 원소 $E_j$의 값을 $E_j-m_{j1}E_1$로 바꿔준다 ($m_j1=\frac{a_j1}{a_11}$)
  • j번째 행의 원소 $E_j$의 값을 $E_j-m_{j2}E_1$로 바꿔준다
  • 1열의 모든 행에 대해 위 계산을 반복한 결과 행렬이 U행렬
  • 위 식에서 계산한 계수 m으로 이루어진 행렬이 L행렬이다.
• Permutation
  • Gauss Elimination 연산이 불가능한 경우 계수 행렬의 열을 맞바꿈
  • P = (a, b) : 바꿀 두 행 a, b를 지정
    • ex. P = (1, 2) (2, 4)의 경우, 1 - 2행을 바꾼 후 2 - 4행을 바꿈
    • $P \begin{bmatrix} 0\ 1\ 0\ 0\\ 0\ 0\ 0\ 1\\ 0\ 0\ 1\ 0\\ 1\ 0\ 0\ 0 \end{bmatrix}$
  • PA = LU의 관계식을 만족
  • $A = P^{-1}LU = P^tLU$

Positive definitive

• n x n 행렬 A가 있을 때,
  • $|a_{ii}|\geq\sum^n_{j=1, j\not ={i}}|a_{ij}|$이면 diagonally dominant 하다고 표현
  • $|a_{ii}|>\sum^n_{j=1, j\not ={i}}|a_{ij}|$ 이면 strictly digonally dominant
• $det(A)\not ={0}\lrArr A^{-1}\ exist$
  • determinant가 0이 아님을 증명하는 계산 과정은 복잡
  • 그 대신 (strictly) diagnally dominant이면 $A^{-1}$이 존재하다는 것을 이용
  • $diag.\ dominant A\larr A^{-1}\ exist$
  • $strictly\ diag.\ dominant A\lrarr A^{-1}\ exist$ : non-singluar

• 0이 아닌 벡터 x에 대해
  • $x^tAx>0$이면 A는 positive definitive하다고 정의
• positive definitive할 경우
  • 역행렬이 존재
  • 모든 대각 성분은 양수
  • 행렬 내 임의 값의 최대값보다 대각 성분의 최대값이 더 큼
  • i행 j열에서 $(a_{ij})^2<a_{ii}a_{jj}$

• n x n 행렬 내에는 n개의 leading submatrix가 존재
  • leading submetrix : 행렬의 1,1 원소를 공통으로 갖는 1 x 1, ..., n x n 크기의 대칭행렬
  • 대칭행렬 A의 leading submatrix가 모두 행렬식이 양수인 경우, A는 positive definitive

Euler's method

• 가장 단순한 미분법
• Initial value problem
  • $\frac{dy}{dt}=f(t,y),\ a\leq t\leq b, y(a)=\alpha$
  • [a,b] 범위를 n등분 : $t_i=a+ih,\ i=0,1,2,...,n$
  • $h=(b-a)/n=t_{i+1}-t_i$를 step size라고 정의
• euler's method 유도를 위한 taylor's theorem
  • $y(t_{i+1})=y(t_i)+(t_{i+1}-t_i)y'(t_i)+\frac{(t_{i+1}-t)^2}{2}y''(\zeta_i)\ (t_i\leq\zeta\leq t_{i+1})$
  • step size 공식에 의해 $y(t_{i+1})=y(t_i)+hf(t_i, y(t_i)) + \frac{h^2}{2}y''(\zeta_i)$

• Euler's method
  • $w_i\simeq y(t_i)$로 정으
  • $w_0 = \alpha$
  • $w_{i+1}=w_i+hf(t_i, w_i)$
• ex. h = 0.5, y(0)=0.5, $y'=y-t^2+1$
  • $w_0=y(0)=0.5$
  • $w_1=w_0+0.5(w_0-0^2+1)$
  • $w_2=w_1+0.5(w_1-(0.5)^2+1$
• $w_{j+1}=w_j+hf(t_j, w_j)$ : worward euler method
  • h가 커지면 발산할 위험이 있음
• $w_{j+1}\simeq w_j + hf(t_{j+1}, y_{j+1})$ : backward euler method
  • $w_{j+1}$을 풀어야 하나, stable한 장점이 있음

• Runge-Katta method (order 2)
  • $\int^{t_{j+1}}_{t_j}y'dt=\int^{t_{j+1}}_{t_j}f(t, y(t))dt\\\rarr y_{j+1}-y_j\simeq \frac{h}{2}[f(t_j, y_j) + f(t_{j+1}, y_{j+1})]$ : Implicit
  • Explicit : $y_{j+1}-y_j\simeq \frac{h}{2}[f(t_j, y_j) + f(t_{j+1}, \hat{y_{j+1})}]$
    • $y_{j+1}\simeq\hat{y_{j+1}}=y_j+hf(t_j, y_j)$
• Runge-Katta method (order 4)
  • Implicit : $y_{j+1}-y_j = \frac{h}{6}[f(t_j, y_j) + 4f(t_{j+1/2}, y_{j+1/2})+f(t_{j+1}, y_{j+1})]$
  • Explicit : $y_{j+1}-y_j = \frac{h}{6}[f(t_j, y_j) + 2f(t_{j+1/2}, \hat{y_{j+1/2}})+2f(t_{j+1/2}, \hat{\hat{y_{j+1/2}}})+f(t_{j+1}, \hat{y_{j+1}})]$
    • $\hat{y_{j+1/2}}=y_j+\frac{h}{2}f(t_j, y_j)$
    • $\hat{\hat{y_{j+1/2}}}=y_j+\frac{h}{2}f(t_j, \hat{y_j})$
    • $\hat{y_{j+1}}=y_j+hf(t_j+\hat{\hat{y_{j+1/2}}})$

Numerical Integration

• 수치적 적분은 $\int$대신 $\sum$을 쓰는 원리

Trapezoidal Rule

• 적분 구간의 일부인 [a, b]구간의 적분을 가정 (구분구적법과 유사)
  • $\int_{x_0}^{x_2}f(x)dx\simeq (x_2-x_0)\frac{[f(x_0)+f(x_2)]}{2}$
• 해당 구간의 Linear Lagrange Polynomial $P_1(x)=\frac{x-x_1}{x_0-x_1}f(x_0)+\frac{x-x_0}{x_1-x_0}f(x_1)$
• Lagrange Method $x_1,\ x_2$를 shifting
  • $L_0=\frac{h-x}{h},\ L_1=\frac{x}{h}$
  • $\int_{x_0}^{x_2}f(x)dx\simeq (2h)\frac{[f(x_0)+f(x_2)]}{2}$
• three-point rule 적용(x-h, 0, x+h)
  • taylor polynomial : $f(x)=f(x_1)+f'(x_1)(x-x_1)+\frac{f''(\zeta)}{2}(x-x_1)^2$
  • a : $\int_{x_0}^{x_2}f(x)=f(x_1)\cdot 2h+\frac{f''(\zeta_x)}{2}(x-x_1)^2$
  • b : $[f(x_0)+f(x_2)]h=2hf(x_1)+[f''(\zeta_1)+f''(\zeta_2)]\frac{h^3}{2}$
  • error = a-b = $\int_{x_0}^{x_1}\frac{f''(\zeta)}{2}(x-x_1)^2-\frac{[f''(\zeta_1)+f''(\zeta_2)]}{2}h^3$
    $=h^3[\frac{f''(\eta)}{3}-\frac{[f''(\zeta_1)+f''(\zeta_2)]}{2}]$
• Error 발생 $\int^h_{-h} f(x)dx\simeq h\frac{[f(h)+f(-h)]}{2}$
  • f(x)=1인 경우 : a=2h, b=2h
  • f(x)=x인 경우 : a=b=0
  • f(x)=$x^2$인 경우 : $\frac{2}{3}h^3\not ={h^3}$(error 발생)

Simpson's Rule

• [a, b]구간을 세 점 (x0, x1, x2)로 가정
• shifting : $x_0=-h,\ x_1=0,\ x_2=h$
  • $\int_{-h}^hf(x)\simeq h\frac{f(-h)+4f(0)+f(h)}{3}$
  • 혹은 $\int_{x_0}^{x_2}f(x)dx=2hf(x_1)+\frac{h^3}{3}f''(x_1)+\frac{f''''(\zeta)}{60}h^5$
• Trapizoidal Rule의 degree of precesion은 1이지만, simpson은 4(전자는 2차식, 후자는 5차식부터 오차 발생)
• Composite Simpson's rule
  

  

  • 함수를 일정 구간으로 나누어 Simpson's Rule을 여러번 적용
  • $I(f)=\int^b_af(x)dx,$
  • $T_n(f)=h[\frac{f(x_0)+f(x_1)}{2}+\frac{f(x_1)+f(x_2)}{2}+...+\frac{f(x_{n-2})+f(x_{n-1})}{2}+\frac{f(x_{n-1})+f(x_n)}{2}$
    $=h[\frac{f(x_0)}{2}+f(x_1)+...+f(x_{n-1})+\frac{f(x_n)}{2}]$
  • 오차 = $nO(h^3)$ - 간격이 줄어 h가 감소하므로 오차가 대폭 줄어듦

Gaussian Quadratic

• $\int f(x)dx\simeq c_1f(x_1)+c_2f(x_2)$
• Simpson's rule의 변형으로, 양 끝점을 구분부적 하는 대신 구간 내 임의 두개의 점으로 구분구적을 진행
• 미지수 $c_1,\ c_2,\ x_1,\ x_2$를 알기 위한 4개 방정식 필요
• 5개 점(a, x1, 0, x2, b)이 대칭형이라 가정
  • x1 = -x2
  • c1 = c2

Numeriacal Differenctiation

• $f(x)=P_n(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Pi(x-x_n)=P_n(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Phi(x)$
• 미분 근사
  • $f'(x)=lim_{h\rarr0}\frac{f(x+h)-f(x)}{h}\simeq\frac{f(x+h)-f(x)}{h}$
  • 계산이 단순함
  • 수렴이 느림 = 근사 정확도가 낮음
  • h에 정비례로 오차도 작아짐 (1차 수렴)
• Higher Order method : Lagrange method
  • $f(x)=\Sigma f(x_k)L_k(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Pi(x-x_n)$
  • 앞의 항은 $P_n(x)$, 뒤의 항은 Error
  • 미분값 $f'(x)=\sum^n_{k=0}f(x_k)L'_k(x)+D_x[\Phi(x)]f^{n+1}(\zeta(x))+\Phi(x)D_x[f^{n+1}(\zeta(x))]$
    • j번째 미분항 $f'(x_j)=\sum^n_{k=0}f(x_k)L'_k(x_j)+\frac{f^{n+1}(\zeta(x_j))}{(n+1)!}\Pi^n_{k=0, k\not ={j}}(x_j-x_k)$
    • 오차를 특정하기보다는 Error Bound를 계산한다.
  • n이 중가할수록 error는 감소

Three-Point Formula

• Lagrange Polynomial (3 basis) : 3개 점을 이용한 근사식
  • $L_0=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$
  • $L_1=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}$
  • $L_2=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
• 3-point method : 3개 점이 일정 간격이라 가정 $x_1 = x_0+h,\ x_2=x_0+2h$
  • Lagrange method의 분모항은 모두 $2h^2$으로 통일됨
  • shifting : 3개 점 중 하나를 0으로 치환
• 3-point method를 적용한 미분식
  • $f'(x_0)=\frac{1}{h}[-\frac{3}{2}f(x_0)+2f(x_0+h)-\frac{1}{2}f(x_0+2h)]+\frac{h^2}{3}f'''(\zeta_0)$
  • $f'(x_0+h)=\frac{1}{h}[-\frac{1}{2}f(x_0)+\frac{1}{2}f(x_0+2h)]+\frac{h^2}{6}f'''(\zeta_1)$
  • $f'(x_0+2h)=\frac{1}{h}[\frac{1}{2}f(x_0)-2f(x_0+h)+\frac{3}{2}f(x_0+2h)]+\frac{h^2}{3}f'''(\zeta_2)$
  • h가 절반 >> error항은 2차식이므로 오차는 1/4로 감소
• 미분식 간소화
  • $f'(x_0)\simeq\frac{-3f(x_0)+4f(x_1)-f(x_2)}{2h}$ (back-order form)
  • $f'(x_1)\simeq\frac{-f(x_0)+f(x_2)}{2h}$ (central form)
  • $f'(x_2)\simeq\frac{f(x_0)-4f(x_1)+3f(x_2)}{2h}$ (forward-order form)
  • 세 식이 대칭 구조를 이룸
  • 분자의 계수 합이 0이어야 함

• $\tilde{x}=x-x_1\ (x_1=x+h)$로 정의
  • Largrange Polynomial $f(x)\simeq f(x_0)L_0(x)+f(x_1)L_1(x)+f(x_2)L_2(x)$를
  • $f(x)\simeq f(x_0)L_0(\tilde{x})+f(x_1)L_1(\tilde{x})+f(x_2)L_2(\tilde{x})$로 치환
  • $L_0(\tilde{x})=\frac{\tilde{x}(\tilde{x}-h)}{2h^2}$
• five point formula
  • $f'(x_0)=\frac{1}{12h}(f(x_0-2h)-8f(x_0-h)+8f(x_0+h)-f(x_0+2h))+\frac{h^4}{30}f^{(5)}(\zeta)$
    • midpoint formula - 가운데 점의 미분
    • $\zeta=[x_0-2h, x_0+2h]$
  • $f'(x_0)=\frac{1}{12h}[-25f(x_0)+48f(x_0+h)-36f(x_0+2h)+16f(x_0+3h)-3f(x_0+4h)]+\frac{h^4}{5}f^{(5)}(\zeta)$
    • endpoint formula - 왼쪽 끝점에서 미분
    • $\zeta=[x_0, x_0+4h]$
  • Error식이 4차 - Order of Convergence = 4
• Order of Convergence 계산
  • Error $E_h=Ch^\alpha$라고 할 때 Order of convergence = $O(h^2)$
  • h값이 1/2로 감소한다고 할때 이전 값은 2h이므로 $E_2h=C(2h)^\alpha$
  • error의 감소분은 $\frac{E_2h}{E_h}=2^\alpha$
  • $\alpha$의 계산은 $log\frac{E_2h}{E_h}/log2$로 구할 수 있음 (Error Of Convergence)

Application of the Formula

• ex. $f(x)=xe^x$
  • f(1.8) = 10.889365, f(1.9) = 12.703199, f(2.0) = 14.778112, f(2.1) = 17.148957, f(2.2) = 19.855030
  • h=0.1, x=1.9 기준으로 한 3-point endpoint formila
    $f(x)=\frac{1}{0.2}[-3f(1.9)+4f(2.0)-f(2.1)]$

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)|$