MTH307 Formula Sheet PDF

Preview

Summary

Download MTH307 Formula Sheet PDF

Description

MTH307 Formula Sheet Note: the formulae presented here are often abbreviated for concerns of space and you need to be familiar with them before using this sheet.

For 1st order hyperbolic PDE Proposition 4. The Fourier sine series for a function f (x) is: X

Finite Differences

Name

yi′ yi′ yi′ yi′ yi′′ yi′′ yi′′

C2 F2 F1 B1 C2

2 bn = L

Proposition 1 (Shooting method for BVP). For a linear DE, in order to solve a BVP with conditions u(t0 ) = u0 and u(t1 ) = u1 , then pick two independent IVPs with u(t0 ) = u0 and ut (t0 ) chosen arbitrarily. Then uBV P = auIV P 1 + buIV P 2 . Sub in t = t0 and t = t1 to find a and b and hence determine uBV P .

Fourier Series Proposition 2. The Fourier series for a periodic function f (x) with period 2L is: X an cos(nπx) + b n sin(nπx) a0 /2 + n≥1

where 1 L

L

1 bn = L

Z

L

an = and

f (x) cos(nπx/L)dx

f (x) sin(nπx/L)dx

0

The type of a 2nd order PDE: Auxx + 2Buxy + C uyy + f (u, x, y, ux , uy ) = 0 • AC − B 2 = 0: parabolic • AC − B 2 > 0: elliptic • AC − B 2 < 0: hyperbolic Proposition 5 (Separation of variables to solve PDEs). One way to try to solve a PDE for u(x, t) is to try a solution of the form u(x, t) = F (x)G(t). Sub this expression into the PDE. Put all the functions of x on one side and all function of t on the other (ie something like p(x) = q(t)). Then both sides must be constant, k say. Then solve each half (p(x) = k and q(t) = k) separately to find F (x) and G(t) (use the boundary conditions to simplify). For simpler problems, using the initial condition will fully solve the problem. A variant of this is to try u(x, t) = F (x) + G(t) (it otherwise works the same).

n≥1

where

Proposition 10 (Dirichlet problem for Laplace equation). The solution to uxx + uyy = 0, u(x, 0) = f (x), u(x, b) = g(x), u(0, y ) = u(a, y) = 0 is  sin(nπx/a) X  f g bn sinh(nπ (b − y)/a) + bn sinh(nπy/a) sinh(nπb/a) n≥1 g

Proposition 6 (Von Neumann Stability Analysis (constant coefficients)). For a finite difference scheme, sub in the expression ǫ ij = Gj eIωi (into the homogeneous part). Then solve for G. If |G| ≤ 1 for all ω then the error is bounded and the method is stable. If |G| > 1 for some ω then the error is unbounded and the method is unstable.

Parabolic equations (the heat equation) Proposition 7 (Dirichlet Heat Equation with zero boundary). The solution to ut = c2 uxx,

u(x, 0) = f (x),

is u(x, t) =

0

Elliptic PDE

f where b n and bn are the coefficients of the Fourier sine series of f and g with period 2a.

Data Modelling SSE =

n X (yi − f (xi ))2

RMSE =

i=1

r

SSE n

Methods to minimise SSE f (x) sin(nπx/L)dx

−L

Z

Proposition 9 (Wave equation). The solution to utt = c2 uxx is (d’Alembert’s solution): u(x, t) = φ(x + ct) + ψ(x − ct). If we have initial and Dirichlet boundary conditions, u(x, 0) = f (x), ut (x, 0) = g(x) (for 0 ≤ x ≤ L) and u(0, t) = u(L, t) = 0 then the solution is Z x+ct 1 1 g ∗ (s)ds u(x, t) = (f ∗ (x + ct) + f ∗ (x − ct)) + 2 2c x−ct where f ∗ and g ∗ are the odd periodic extensions of f and g with period 2L (eg they are the Fourier sine series).

−L

Proposition 3. The Fourier cosine series for a function f (x) is X an cos(nπx) a0 /2 +

2 an = L

using the initial condition t = t0 , x = x0 , u = f (x0 ) (where x0 is arbitrary). Eliminate x0 to get the general solution. The equation for x and t (also involving x0 ) are the characteristic curves. Solution is unique on all characteristic curves passing through the initial condition. Hence characteristic curves for boundary of initial condition, give boundary of solution.

L

Partial Differential Equations

Shooting Method For a linear DE, if u1 and u2 are solutions, then u3 = au1 + bu2 is also a solution. In order to determine u3 then sub in key values to find a and b. For example:

Z

This is the 2L-periodic odd continuation of f (x).

Two variables: xi = x0 + ih, ti = t0 + ik, ui = u(xi , ti ).

Z

Proposition 8 (Method of characteristics). To solve aux + but = c given u(x, t0 ) = f (x), solve the ODEs: dt du dx = = c a b

where

Equation y i+1 −y i h y i −y i−1 h y i+1 −y i−1 2h −y i+2 +4y i+1 −3y i 2h y i+2 −2y i+1 +y i h2 y i −2y i−1 +y i−2 h2 y i+1 −2y i +y i−1 h2

F1 B1

b n sin(nπx)

n≥1

Single variable: xi = x0 + ih, yi = y(xi ). F = forward, B = backward, C = centred. The number after the name indicated the order. For example C2 indicates centred difference with truncation error of O(h2 ). Exp

Hyperbolic PDE

This is the 2L-periodic even continuation of f (x).

L

f (x) cos(nπx/L)dx

X

n≥1

b n sin

u(0, t) = 0,

 nπx  L

2

e−c

u(L, t) = 0

n2 π2 t/L2

where b n are the coefficients of the Fourier sine series.

Theorem 11 (Linear regression). The least squares linear regression for the model y = bT x fitted to this data is given by the following values for the parameters: b = (XXT )−1 Xy, where y is the n × 1 vector (yi ), X be the m × n matrix (xi ). If not linear, transform to linear or try ...

Pn 2 i=1 (fi (b)) . (Commonly fi = yi − g(b, xi ).) Then given an initial guess bold for the parameters an improved guess is:

Proposition 12 (Grid Search). To minimise F (b). Adjust one variable at a time(b i , say). Repeatedly increment b i (by h) and calculate F to determine (local) min for F . Repeat for all variables. Then repeat entire process until the decrease in F is small

= bold − (JT J)−1 JT f,

Proposition 14 (Gauss-Newton Method). To minimise

RK4

ut = c2 uxx + s(x, t)

Ex Forward FD

ut = c2 uxx + s(x, t)

(heat) Im Backward FD (heat)

ut = c2 uxx + s(x, t)

Crank-Nicholson

aux + but = c

FTFS

aux + but = c

FTBS

aux + but = c

Lax-Wendroff

aux + but = c

BTBS

aux + but = c

Wendroff

aux + but = c

Characteristics

utt =

c2 u

xx

utt = c2 uxx

uxx + uyy = f (x, y)

2

Implicit (Poisson) with Gauss-Seidel (w = relaxation)

where r = kc h2 + (1 + 2r)ui,j+1 − rui+1,j+1 = ui,j + ksi,j+1 2

where r = kc h2 (2 + 2r)ui,j+1 −r(ui+1,j+1 + ui−1,j+1 ) = (2 − 2r)ui,j + r(ui+1,j + ui−1,j ) + k(si,j+1 + sij ) 2 where r = kc  h2  ak ak u + 1 uij + kb cij + ui,j+1 = − bh i+1,j  bh  ak ak ui,j+1 = bh ui−1,j + 1 − bh uij + kb cij

ui,j+1 = uij

Explicit (wave) Implicit (wave)

Formula xi+1 = xi + hf(xi , ti ) xi+1 = xi + hk2 k1 = f (xi , ti ) hk k2 = f (xi + 2 1 , ti + 2h ) (k + 2k2 + 2k3 + k4 ) xi+1 = xi + h 1 6 k1 = f (xi , ti ) hk1 k2 = f (xi + 2 , ti + 2h ) hk k3 = f (xi + 2 2 , ti + 2h ) k4 = f (xi + hk3 , ti + h) ui,j+1 = (1 − 2r)uij + r(ui−1,j + ui+1,j ) + ksij

−rui−1,j +1

j

Model Selection

where f is the  n × 1 vector (fi ), J is the Jacobian, the n × m ∂fi matrix ∂b : j   ∂f1 ∂f1 ... ∂b ∂b2  ∂f12  ∂f2 . . .   J =  ∂b1 ∂b2  . . . .. . .. .

where k is chosen to make F (bnew ) a (local) minimum (ie increment by a fixed amount then use parabolic interpolation to get better estimate of the min).

x′ = f(x, t)

Note: In previous two methods, if derivatives are difficult to determine, replace derivatives with forward finite differences.

bnew = bold + ∆b

Proposition 13 (Gradient Search Method). To minimise F (b). bnew = bold − k∇F

Summary of numerical method based on finite differences Im/Ex means implicit or explicit. DE Method x′ = f(x, t) (Forward) Euler x′ = f(x, t) RK2

Do several iterations to get better value.

Forward selection: start with no variables and then add variables which impact on the fit, until virtually no further impact on fit can be achieved.

Diffs used all F C at ti + h/2

Im/Ex Ex Ex

Error O(h) O(h2 )

Ex

O(h4 )

F in t,

Ex

O(h2 + k)

r ≤ 21

C in space B in t,

Im

O(h2 + k)

always

Im

O(h2 + k2 )

always

F at ti

stable

C in space C about ti + h/2, C in x, av at ti and ti+1 F in t, F in x

Ex

O(h + k)

F in t, B in x

Ex

O(h + k)

rewrite DE, then C

Ex

O(h2 + k2 )

B in t, B in x

Im

O(h + k)

2 2

ak − 2bh (ui+1,j − ui−1,j ) + 2ba2 hk2 (ui−1,j − 2uij + ui+1,j ) k2 (bc − ac ) + kb cij + 2b t x ij 2

akui,j +1 +bhui+1,j +khci+1,j +1 ui+1,j+1 = ak+bh a (u + u i+1,j+1 i+1,j − ui,j+1 − uij ) 2h b (ui+1,j+1 − ui+1,j + ui,j+1 − uij ) = c(xi + h/2, tj + k/2) + 2k = ba and du = c numerically (eg RK4). Solve the system dx dt dt b 2 2 j > 0 : ui,j+1 = −ui,j−1 + 2uij + ch2k (ui−1,j − 2uij + ui+1,j ) c2 k2 j =0: ui,1 = k(ut )i0 + ui0 + 2h2 (ui−1,0 − 2ui0 + ui+1,0 )   2 2 2 2 >0: 2 1 + ch2k ui,j+1 − c hk2 (ui−1,j+1 + ui+1,j +1 )



c2 k2 (u i−1,j −1 + ui+1,j −1 ) + 4uij h2 c2 k2 j = 0 : ui,1 = k(ut )i0 + ui0 + 2h2 (ui−1,0 − 2ui0 + ui+1,0 ) h2y ui−1,j + hx2ui,j−1 + hy2 ui+1,j + hx2 ui,j+1 − 2(hx2 + h2y )uij = hx2h2y fij 2 2 2 2 2u +h2 x ui,j−1 +hy ui+1,j +h x ui,j+1 −hx h y fij new = hy i−1,j uij 2 +h2 ) 2(hx y old new uij = wuij + (1 − w)uij

 = −2 1 +

Backwards Elimination: start with the full model and then remove variables which have virtually no impact on the fit, until all remaining variables impact fit.

c2 k2 h2

ui,j−1 +

Av of C

Im

2

O(h + k2 )

Ex 2

   ak    ≤ 1, ab ≤ 0  bh   ak   bh  ≤ 1, ab ≥ 0    ak   bh  ≤ 1 a b

≥0

a b

≥0

always    ck   h≤1

all C

Ex

O(h2

C; av of tj−1 and tj+1

Im

O(h2 + k2 )

always

all C

Im

O(h2 + k2 )

always

+k )...