12 Ordinary Differential Equations: Initial-Value Problems 자연어처리 연구실 김혜겸 윤도상 최성원.

Presentation on theme: "12 Ordinary Differential Equations: Initial-Value Problems 자연어처리 연구실 김혜겸 윤도상 최성원."— Presentation transcript:

1 12 Ordinary Differential Equations: Initial-Value Problems 2005. 06. 01 자연어처리 연구실 김혜겸 윤도상 최성원

2 2 Introduction Techniques for solving first-order ordinary differential equations are the subject of this chapter –the differential equation is written in the form with the value of function given at,i.e.,. –Basic idea is to divide the internal of interest into discrete steps and find approximations to the function y at those values of. Taylor Method Runge-Kutta Method Multistep Method

3 3 12.1 TAYLOR METHODS Consider two methods that are based on the Taylor series representation of unknown function. –Euler’s method Uses only the first term in the Taylor series –Higher order Taylor method

4 4 12.1 TAYLOR METHODS 12.1.1 Euler’s Method The simplest method of approximating the solution of the differential equation –Start by treating the function as a constant,, and replace the derivative by the forward difference quotient. This gives or ( where ) Geometrically, this corresponds to using the line tangent to the true solution curve to find the value of.

5 5 12.1 TAYLOR METHODS 12.1.1 Euler’s Method Euler Method gives, for For example,

6 6 Example 12.1 Solving a Simple ODE with Euler’s Method(1/2), (i.e., a=0, b=1),. First, find the approximate solution for h =0.5 (n =2) Approximation at is Second, find the approximate solution at :

7 7 Example 12.1 Solving a Simple ODE with Euler’s Method(2/2) To find a better approximate solution(use n=10 intervals)

8 8 MATLAB Function For Euler’s Method

9 9 Example 12.2 Another Example of the Use of Euler’s Method Consider the differential equation –Interval with initial value –With intervals, the step size –Exact solution is

10 10 Discussion How well a numerical technique for solving an initial- value ordinary differential equation works –Total truncation error for Euler’s method is –Related to the truncation error of the method is Result of basic Euler’s method can be improved by using it with Richardson extrapolation Step size Extrapolation level Computed directly from Euler’s method

11 11 12.1 TAYLOR METHODS 12.1.2 Higher Order Taylor Method Use more terms in the Taylor series for y, in order to obtain a higher order truncation error –However do not have a formula for –If is not too complicated Differentiate with respect to to find a representation for

12 12 Example 12.3 Solving a Simple ODE with Taylor’s Method Consider the differential equation with initial condition To apply the second order Taylor method This gives the approximation formula or For, we find

13 13 MATLAB Function For Taylor’s Method

14 14 12.2 RUNGE-KUTTA METHOD 배경 –Talyor 해법은 Euler 해법에 비해서 정확하지만, f(x,y) 의 고계도함수를 구해야 함 – 임의의 f(x,y) 가 주어 졌을 때, 고계 미분계수를 계산하는 프로그램을 작성하는 것은 어려움 –Runge-kutta 해법은 talyor 해법의 장점이 되는 계산 정밀도는 유지하되, 단점을 보완한 방법

15 15 12.2 RUNGE-KUTTA METHOD 12.2.1 Midpoint Method –Runge-kutta 의 해법 중 가장 간단함 – 공식 Runge-kutta 해법은 더 쉬운 계산법을 사용하여 Tailer 방법을 근사시키는 전략을 사용함

16 16 12.2 RUNGE-KUTTA METHOD 12.2.1 Midpoint Method Example 12.4 Solving a Simple ODE with the Midpoint Method 에서 미분 방정식은, y(0) = 2 1) h = 0.5 (n=2)  x 1 = 0.5 2) x 2 = 0.0 + 2h = 1.0

17 17 12.2 RUNGE-KUTTA METHOD 12.2.1 Midpoint Method MATLAB Function for the Midpoint Method Function [x, y] = RK2 (f, tspan, y0, n) % function [x, y] = RK2 (f, y0, a, b, n) % solve y’ = f(x, y) % with initial condition y(a) = y0 % using n steps of the midpoint (RK2) method; a = trans(1); b = trans(2); h = (b - a) / n x = (a+h: h : b); k1 = h * feval (f, a, y0); k2 = h * feval (f, a + h / 2, y0 + k1 / 2); y(1) = y0 + k2; for i = 1 : n-1 k1 = h * feval (f, x(i), y(i) ); k2 = h * feval (f, x(i) + h / 2, y(i) + k1 / 2); y(i+1) = y(i) + k2; end x = [ a x ]; y = [ y0 y];

18 18 12.2 RUNGE-KUTTA METHOD 12.2.2 Other Second-Order Runge-Kutta Mehods 2 차 runge-kutta 해법의 일반적인 형태 –Modified Euler’s method –Heun’s method –Midpoint Method c2c2 a 21 w1w1 w2w2 11 1/2 2/3 1/43/4 1/2 01

19 19 12.2 RUNGE-KUTTA METHOD 12.2.3 Third-Order Runge-Kutta Mehods N=3 이며, 식은 2 차 방법과 유사하게 기술 됨 c3c3 a 31 w1w1 w2w2 c2c2 a 21 a 32 w3w3 2/30 2/83/8 2/3 3/8 1 1/64/6 1/2 2 1/6 - Nystrom - Classical 3/40 2/93/9 1/2 3/4 4/9 2/30 1/40 1/3 2/3 3/4 - Nearly Optimal - Heun

20 20 12.2 RUNGE-KUTTA METHOD 12.2.4 Classic Runge-Kutta Method 2 차나 3 차보다 더 정확한 해를 구해 줌 다른 Runge-Kutta 방법들 중에서 가장 널리 사용됨

21 21 12.2 RUNGE-KUTTA METHOD 12.2.4 Classic Runge-Kutta Method MATLAB Function for Classic Runge-Kutta Method Function [x, y] = RK4 (f, tspan, y0, n) % solve y’ = f(x, y) with initial condition y(a) = 0 % using n steps of the classic 4 th order Runge-Kutta method; a = trans(1); b = trans(2); h = (b - a) / n x = (a+h: h : b); k1 = h * feval (f, a, y0); k2 = h * feval (f, a + h / 2, y0 + k1 / 2); k3 = h * feval (f, a + h / 2, y0 + k2 / 2); k4 = h * feval (f, a + h, y0 + k3); y(1) = y0 + k1/6 + k2/3 + k3/3 + k4/6; for i = 1 : n-1 k1 = h * feval (f, x(i), y(i) ); k2 = h * feval (f, x(i) + h/2, y(i) + k1 / 2); k3 = h * feval (f, x(i) + h/2, y(i) + k2 / 2); k4 = h * feval (f, x(i) + h, y(i) + k3); y(i+1) = y(i) + k1/6 + k2/3 + k3/3 + k4/6; end x = [ a x ]; y = [ y0 y];

22 22 12.2 RUNGE-KUTTA METHOD 12.2.4 Classic Runge-Kutta Method Example 12.6 Solving a Simple ODE with the Classic Runge-Kutta Method xExact solution Approximate Solution Absolute error 0.22.4642 8.2745e-06 0.43.0755 2.0213e-05 0.63.86643.86633.7032e-05 0.84.8766 6.0308e-05 1.06.1548 9.2076e-05

23 23 12.2 RUNGE-KUTTA METHOD 12.2.5 Other Runge-Kutta Methods General Runge-Kutta Mothod (1/2) c3c3 a 31 w1w1 w2w2 c2c2 a 21 a 32 w3w3 c4c4 a 41 a 42 a 43 w4w4

24 24 12.2 RUNGE-KUTTA METHOD 12.2.5 Other Runge-Kutta Methods General Runge-Kutta Mothod (2/2) - Classic fourth-order Runge-Kutta - Lawson’s fifth-order Runge-Kutta Method - Kutta’s method - Butcher’s sixth-order Runge-Kutta method 1/20 1/62/6 1/2 2/6 1001 1/6 1/20 1/62/6 1/2 2/6 1001 1/6 1/43/16 7/900 1/2 1/16 32/90 1/200 12/90 3/40-3/166/16 11/74/76/7 9/16 -12/78/7 32/90 7/90 2/30 11/1200 1/3 2/3 27/40 1/31/121/3-1/12 27/40 1/2-1/169/8-3/16 1/209/8-3/8 -3/41/2 -4/15 19/44-9/1163/44 18/110 -16/11 11/120

25 25 12.3 Multistep methods Multistep methods – 앞에서의 방법론들은 단일점 x = x i 에서의 정보를 이용하여, x = x i+1 의 해 y i+1 의 값을 계산했다. – one step methods –General form of two-step methods a 1,a 2,b 0,b 1 등은 methods 에 따라 달라진다. 앞으로는 다음과 같은 notation 으로 표현하겠다.

26 26 12.3 Multistep methods Multi-step methods (cont’) –Multi-step methods 는 f i+1 의 계수 b 의 값에 따라 b = 0 인 경우 명시적 (explicit) 또는 개식 (open) methods 라 부르고, b ≠0 인 경우에는 암묵적 (implicit) 또는 폐식 (closed) method 라 부른다. –Multi-step methods 는 시작 값을 필요로 하므로, 보통 Runge-Kutta 와 같 은 기존의 method 를 이용해서 초기값 y 1 을 구한다.

27 27 12.3 Multistep methods 12.3.1 Adams-Bashforth Methods Most popular explicit multistep methods Two-step method formula –Local truncation error O(h 3 ) Three-step method formula –y 0 는 주어져 있고, y 1 &y 2 는 one-step method 에서 얻는다. –Local truncation error O(h 4 ) Step 이 올라가면 그만큼 truncation error 가 줄어든다.

28 28 12.3 Multistep methods 12.3.1 Adams-Bashforth Methods Mathlab code

29 29 12.3 Multistep methods 12.3.1 Adams-Bashforth Methods Example 12.8 –Y’ = x+y, y(0) = 2 x00.20.40.60.81 y22.463.06523.85094.85466.1241 (real)y22.46423.07553.86644.87666.1548

30 30 12.3 Multistep methods 12.3.2 Adams-Moultion Methods Most popular implicit method Two-step method formula –y 0 is given, y 1 is found from a one step methods –Local truncation error : O(h 4 ) Adams-Bashforth Methods 의 local truncation error : O(h 3 ) Adams-Bashforth Methods 에 비해서 error 가 작다

31 31 12.3 Multistep methods 12.3.2 Adams-Moultion Methods Matlab code

32 32 12.3 Multistep methods 12.3.2 Predictor-Corrector Methods 경우에 따라서, 앞의 두 다단계 공식을 한 쌍의 공식으로 조합해서 사용하 는 것을 Predictor-Corrector Methods 라 한다. Procedure – 각 구간에서 predictor step 으로 implicit method 를 사용한다 –Corrector step 으로 explicit method 를 사용한다. (predictor 가 새 점에서 문제를 예측 하고 corrector 가 그 정확도를 개선하는 것을 의미한다.) Adams Third-Order Predictor-Corrector Method –y 0 는 초기값으로 주어지고, y 1, y 2 는 one-step method 로 구한다. –Predictor –Corrector

33 33 12.4 Stability Definition –Root condition : characteristic polynomial 의 근을 λ 1, λ 2,… λ m 로 나타낼때, | λ i | ≤ 1, i = 1,2,…,m 이고, 절대값이 1 인 모 든 근이 simple root 이면, root condition 을 만족한다 라고 한다. –Strongly stable : root condition 을 만족하고 크기가 1 인 특성방정식의 유 일한 근으로 λ = 1 인 방법 –Weakly stable : root condition 을 만족하고 크기가 1 인 근을 두개 이상 갖는 방법 –Unstable : root condition 을 만족하지 않는 방법

34 34 12.4 Stability Example 12.11 – Weakly Stable method –Simple two step method y i+1 = y i-1 +2hf i –Differential equation y’ = -4y, y(0) = 1 : exact solution is y = e -4x

35 35 12.4 Stability Example 12.11(cont’)

36 36 12.5 MATLAB ’s Method MATLAB includes three functions for solving non-stiff ODEs –ode 23, ode45 Implement a pair of explicit Runge-Kutta methods second and third order and forth and fifth order –ode113 Fully variable step-size ODE solver based on the Adams-Bashforth-Moulton family of formulas of orders 1-12 –syntax for function [t, y] = ode23 (‘F’, tspan, y0),where tspan=[t0 t_final] ‘F’: string contatining the name of an ODE file F(t, y): must return a column vector of values each row of solution array y corresponds to a time returned in column vector t y0: initial conditions are given in the vector y0