3.5. Parametric curves
. x(t), y(t)에 대해 각각 풀면 된다.
. Bezier curve : guide point 2개를 이용하여 cubic Hermite를 푼다.
. Hermite를 위한 x'(t), y'(t)는 guide point를 이용한 numerical difference formula를 이용한다.
. Guide point의 부호가 반대이므로 주의
. (x0, y0), guide point1, guide point2, (x1, y1)
4. Numerical Differentiation and Integration
4.1. Forward difference formula
f'(x) = 1/h * (f(x+h) - f(x))
. backward difference formula
f'(x) = 1/h * (f(x) - f(x-h))
. centered formula
f(x+h), f(x-h), f(x) 등이 symmetric(대칭적)으로 들어간다.
. n-th order : 에러 term이 h의 h-th order이면 된다.
. 1th order : h*f''(x) + 등..
. 2th order : h^2*f''(x) + 등..
. 식 유도 방법
방법1) Lagrange를 이용한 후 미분한다. - 책에 소개된 방법
x0 ~ xn의 점을 이용하여 n-th lagrange interpolation을 이용하면
(n+1)-point formula가 된다.
방법2) Taylor series를 이용한 후 error order를 잘 소거하는 방향으로 더하거나 뺀다.
- 수업시간과 시험에 나오는 방법
4.2. Richardson's Extrapolation(R.E)
. Low-order formula를 잘 이용해서 high-accuracy를 구하는 방법
. function evaluation보다 사칙연산의 cost가 훨씬 적다고 가정한다.
. h -> h/2 등으로 step size를 줄이면서 계산
(연습 문제에서는 h/3 씩 줄이기도 함.)
. M = N(h) + k1h + k2h^2 + k3h^3 + k4h^4 +
. M : 참값
. N(h) : 근사식
. N1(h), N1(h/2)을 이용하여 N2(h)를 만듬.
. N1(h/(2^n))이 있으면 Nn(h)까지 만들 수 있음.
. Simple averaging process
4.3. Numerical Integration
. Quadrature = Integration = Numerical Integration
. Quadrature은 integration의 옛날 이름이다.
. Deviation은 역사가 몇백년이지만 Integration은 역사가 수천년이다.
. Trapezoidal Rule(TR, T.R)
. first Lagrange Polymial로 유도가능
. h/2 * (f(a) + f(b))
. h = (b-a)
. error : h^3/12*f''(x)
. Simpson's Rule(SR, S.R)
. second Lagrange Polymial로 유도가능
. h/3 * (f(a) + f((a+b)/2) + f(b))
. h = (b-a)/2
. error : h^5/90*f(4)(x)
. Degree of accuracy = precision
. Undetermined coefficient와 관련있다.
. degree가 k이면 각 degree polynomial에서 formula가 정확하다.
. Trapezoidal Rule은 1, Simpson's Rule은 3이다.
. TR은 1차식, SR은 3차식에 대해 각각 exact solution을 준다.
. Undetermined coefficient
. 구간이 -1, 1처럼 숫자일때는 c0, c1이 1/2, 1/2 같은 수로 나오지만
x0, x1일 때는 c0 = c1 = (x1-x0)/2로 나온다. (test2에서 내가 실수한 문제)
. Newton-Cotes formulas
. TR, SR의 일반식, lagrange를 이용.
. Open Newton-Cotes formulas
. boundary a,b가 포함됨
. closed Newton-Cotes formulas
. boundary a,b가 포함 안됨
4.4 Composite Numerical Integration
. High-order는 oscillatory nature가 있으므로 piece-wise로 한다.
. Composite Trapezoidal Rule(CTR, C.T.R)
. error : (b-a)*h^2/12*f''(x)
. Composite Simpson's Rule(CSR, C.S.R)
. error : (b-a)*h^4/180*f(4)(x)
4.5 Romberg Integration
. Composite Trapezoidal Rule + Richardson's Extrapolation
. R1,1 = TR
. R2,1 = 1/2(R1,1 + h * 1개)
. R3,1 = 1/2(R1,1 + h/2 * 2개)
. R4,1 = 1/2(R1,1 + h/2 * 4개)
. R1,1, R1,2 => R2,2 (R2,1은 없으므로 주의 항상 k>=j)
. Rk,2 = Rk,1, Rk-1, 1을 이용해서 구한다.
. Rk,j = Rk,j-1 + (Rk,j-1 - Rk-1,j-1)/(4^(j-1)-1)
. Rk, j : k : h를 1/2씩 줄인다, j : RE의 항
. Rn, n : TR일때 h^(2*n)의 accuracy(order)를 가진다.
4.6 Adaptive Quadrature Methods
. 1/2, 1/4로 step을 줄여 계산하고 값의 오차가 큰 경우 그 구간은 다시 1/2로 나눈다.
. 오차가 만족스럽거나 구간이 충분이 좁을 때까지 반씩 나누면서 연산을 계속한다.
. 변화량이 큰 구간은 잘게 쪼개고, 변화가 없는 구간은 적게 쪼개는 계산법.
4.7 Gaussian Quadrature
. 구간을 잘 쪼게거나 하는 것이 아니라 구간의 boundary의 점이 아닌
가운데 있는 점들을 선택해보자. 어떤 것이 optimal point일까?
(choose the points for evaluation in an optimal)
. Gaussian Quadrature
. http://en.wikipedia.org/wiki/Gaussian_quadrature
. Newton-Cotes formulas의 error term은 n+1 derivative로 정의되므로
polynomial of degree n에 대해서는 exact하다.
. Newton-Cotes formulas : equally spaced points 사용
. composite시 편하지만 accuracy가 떨어진다.
. Optimal placement를 해보자.
. Undetermined Coefficient constant를 구하는 방법으로
c1, c2, ..., cn, x1, x2, ..., xn을 구한다.
. Legnedre polynomials
. P0(x) = 1
. P1(x) = x
. P2(x) = x^2 - 1/3
. P3(x) = x^3 - 3/5x
. Monic polynomial : have leading coefficient 1
. Orthogonal polynomials
. intgral(-1 to 1, P(x)Pn(x)dx) = 0 where P(x) is a polynomial of degree less than n.
. xi를 알면, xi를 lagrange interpolate한 후 -1 to 1으로 적분하면 ci를 구할 수 있다.
. Multiple Integrals
. Region이 rectangle일 때
x축에 대해서 한 번 계산하고 y축에 대해서 또 계산하면 된다.
. Improper Integral
. I = int(a..b, f(x))
. lim x->a, f(x) = inf
. a에서 diverge하지만 area는 converge한다고 가정하자.
. TR, SR 등 기존의 방법은 사용할 수 없다.
왜냐하면 f(a) = inf 이기 때문에 값이 inf(nan : not a number)로 나온다.
. Gaussian Quadrature는 가능할 수도 있다. (f(a)를 얻지 않으므로)
하지만 운이 좋을 때 뿐이고 값이 커지면 이상해 질 수 있다.
. int(a..b, 1/(x-a)^p) = (b-a)^(1-p)/(1-p) (0<p<1 iff converge)
. f(x) = g(x)/(x-a)^p로 쓸 수 있으면
. P4(x) = 4th taylor Polynomial of f(x)
. P4(x) = g(a) + (x-a)g'(a) + 1/2*(x-a)^2*g''(a) + 1/6*(x-a)^3*g'''(a)
+ 1/24*(x-a)^4*g''''(a)
. int(a..b, f(x))
= int(a..b, g(x)/(x-a)^p)
= int(a..b, (g(x)-P4(x))/(x-a)^p) + int(a..b, (P4(x))/(x-a)^p)
. G(x) = (g(x)-P4(x))/(x-a)^p (a<x<=b)
= 0 (x = a)
. int(a..b, (P4(x))/(x-a)^p) 부분은 CSR로 푼다.
. Why 4th taylor Polynomial?
. CSR과 P4(4)의 error term의 order를 같게 맞추기 위해서이다.
. 5th order로 같아진다.
댓글 없음:
댓글 쓰기