Cheat-sheet - numeric PDF

Preview

Summary

numeric...

Description

MthSc 365 – Numerical methods for engineers Cheat sheet – Final exam, December 12, 2011 This will be in your printed exam, so you do not have to bring a copy of this. LUP decomposition.    w⊤ 1 0 a11 A= v/a11 I 0 A′ − vw⊤ /a11    1 0 a11 w⊤ = 0 L′ U ′ v/a11 I    a11 w⊤ 1 0 = 0 U′ v/a11 L′ Norms. For a vector v ∈ Rn , Pn 1 ℓ ℓ ||v||ℓ = i=1 |vi | is a norm for any ℓ ≥ 1.

Pn – ℓ = 1: 1-norm, ||v||1 = i=1 |vi | pPn 2 – ℓ = 2: Euclidean or 2-norm, ||v||2 = i=1 (vi ) n |v | – ℓ = +∞: ∞-norm, ||v||∞ = maxi=1 i For a matrix M ∈ Rm×n Pm n ℓ=1 (1-norm) ||A||1 = maxj=1 i=1 |aij | P n m ℓ = +∞ (∞-norm) ||A||∞ = maxi=1 j=1 |aij | Diagonally dominant matrices. X |aii | > |aij | j∈{1,2...,n}\{i}

Eigenvalues, eigenvectors. If a scalar λ and an nvector u provide a solution to the equation Au = λu then λ is an eigenvalue of A and u is the eigenvector associated with eigenvalue λ. The quantity det(A− λI), i.e., the determinant of A − λI, is the characteristic polynomial of A.

Numerical derivation. f (xi+1 )−f (xi ) . f ′ (xi ) ≈ h f (xi )−f (xi−1 ) ′ . f (xi ) ≈ h f (xi+1 )−f (xi−1 ) f ′ (xi ) ≈ 2h −3f (xi )+4f (xi+1 )−f (xi+2 ) f ′ (xi ) ≈ 2h f (xi−1 )−2f (xi )+f (xi+1 ) f ′′ (xi ) ≈ h2

Numerical integration. Rb PN f (x)dx ≈ k=1 f (xk )(xk+1 − xk ). Rab PN f (x)dx ≈ k=1 f (x +1 − xk ). a  k+1 )(xk Rb PN xk+1 +xk f (x)dx ≈ k=1 f (xk+1 − xk ). a 2  Rb PN R xk+1  f (xk+1 )−f (xk ) ) + f (x f ( x ) dx ≈ (x − x ) dx. k k k=1 xk a  xk+1 −x k  Rb PN h  xi +xi+1 f (x)dx ≈ k=1 3 f (xi ) + 4f + f (xi+1 ) a 2 Gauss quadrature. (C1 , C2 ) = (1, 1); (x1 , x2 ) = (− √13 , √1 ) q   q3 5 8 5 (C1 , C2 , C3 ) = 9 , 9 , 9 ; (x1 , x2 , x3 ) = − 35 , 0, 53 Richardson’s formula.

I(f ) ≈

Ih1 (f ) −



1−

h1 h2



2

h1 h2

Ih2 (f ) 2

Romberg’s methods. Ii,j =

4j−1 Ii+1,j −1 − Ii,j−1 4j−1 − 1

Euler’s methods. yi+1 = yi + slope · h slope = f (xi , yi ) slope = f (xi+1 , yi+1 ) f (xi ,yi )+f (xi+1 ,yi+1 ) slope = 2 Runge-Kutta methods.

Householder matrices. For any n-vector v 6= 0, an Householder matrix has the form H =I−

2 vv⊤ . ||v||22

Normal Equations. A⊤ A(p, q)⊤ = A⊤ b Lagrange interpolating polynomials.   m X Y x − xj   yi y= x − xj i=1 j6=i i

slope = c1 K 1 + c2 K 2 + · · · + cp K p . slope = c1 K 1 + c2 K 2 ; Modified Euler’s: K1 = f (xi , yi ), K2 = f (xi + h, yi + K1 h); c1 = c2 = 21 a2 = 1, b21 = 1 Midpoint Euler’s: K1 = f (xi , yi ), K2 = f (xi + 12 h, yi + 12 K1 h) c1 = 0, c2 = 1, a2 = 21 , b21 = 12 slope = c1 K 1 + c2 K 2 + c2 K 2 K1 = f (xi , yi ) K2 = f (xi + a2 h, yi + b21 K1 h) K3 = f (xi + a3 h, yi +  b31 K1 h + b32 K2 h) (c1 , c2 , c3 ) = 61 , 64 , 16 a2 = 21 , a3 = 1; b21 = 21 , b31 = −1, b32 = 2...