Cheat Sheet - Summary Numerical Analysis I PDF

Preview

Summary

Cheat sheet for MA2213...

Description

MA2213 Finals Cheatsheet

Newton Interpolation Formula



(0)

(0)

a1,2 (1) a 2,2

a1,1

1. Computer Arithmetic and Computational Errors

 

(n−1)

U=A

=

Number Systems To reduce the significant digits in number a by chopping and rounding, we signify: ∗ a = f l(a)

L=

(n−1)

• ±(0.a1 a2 a3 ...am ) - mantissa (fractional part) • e - exponent (characteristic) • N - base (radix)

x−fl(x) x x−fl(x) | x

•

. . .

.



f (x) = pn (x) + R n (x),

  

pn (x) = f (x0 ) + (x − x0 )f [x0 , x1 ]



+ ... + (x − x0 )(x − x1 )...(x − xn−1 )f [x0 , x1 , ..., xn ],

1 ... ... (1)

b2

R n (x) = ψ(x)f [x, x0 , x1 , ..., xn ], pn+1 (xn+1 ) = f (xn+1 )

 

..

. ln,n−1

f [x0 , x1 , ..., xn ] =

1

=

T (n−1)

...

bn

(n−1)

xn = b n

xk =

Examples • f l(f l(a + b) + c) 6= f l(a + f l(b + c)) √ √ • Changing terms to reduce errors: a − b =

• axn = a × xn

a−b √ √ a+ b

Propagation of Errors in Function Evaluations

∗

n X

|

δf (x∗ ) ∗ |δ(x i ) δxi

i=1

(n)!

(n−1)

f (x) − pn (x) =

f (n+1) (ξ) (n + 1)!

n Y

(x − xj ),

j=0

1

(k−1)

(k−1)

ak,k

(bk

−

n X

|f (x) − pn (x)| ≤

(k−1)

ak,j

xj )

M |ψ(x)|, (n + 1)!

M = max |f

(n+1)

a≤ξ≤b

j=k+1

(ξ)|

Stability of Gaussian Elimination and Pivoting Strategies

Cubic Spline Interpolation

Partial Pivoting

A cubic spline interpolant to f is a function S satisfying the following conditions:

Choose the maximum absolute value in the kth column of A, ai,k , and exchange its row position with the kth row for every kth step

Generalisation of error calculation:

δ(f (x )) ≈

xn − x0

f (n) (ξ)

/an,n

and for k = n − 1, ..., 1,

1−t in rounding mode | < 12 × 10 | < 101−t in chopping mode

f [x1 , x2 , ..., xn ] − f [x0 , x1 , ..., xn−1 ]

Truncation Error of Interpolating Polynomial

Step 2 - Back Substitution

For a t-digit machine, • |

 l2,1  ..

= b(0) 1

e

±(0.a1 a2 a3 ...am ) × N , with a1 6= 0

..

1



b

a 1,n (1) a 2,n

(n−1) an,n



. ln,1

Floating Point Computatition and Cancellation

(0)

... ...

Scaled Partial Pivoting Get the maximum absolute value for each column, si,k , and apply partial pivoting, this time choosing the maximum absolute value of ai,k /si,k .

• • • • •

S(x) = a + bx + cx2 + dx2 on subinterval [xj , xj+1 ] S(xj ) = f (xj ) S ′ j (xj+1 ) = S ′ j+1 (xj+1 ) S ′′ j (xj+1 ) = S ′′ j+1 (xj+1 ) One of the sets of boundary conditions: – S ′′ 0 (x0 ) = S ′′ n−1 (xn ) = 0 (Natural Boundary Conditions) – S ′ 0 (x0 ) = f ′ (x0 ) and S ′ n−1 (xn ) = f ′ (xn ) (Clamped Boundary Conditions)

**

2. Numerical Solutions of Linear Systems

Lagrange Interpolating Polynomial Formula

Gaussian Elimination for General Ax = b

For k = 0, 1, 2, ..., n, if

pn (x) = 6= 0,

li,k+1 = ai,k+1 /a k+1,k+1 (k+1) ai,j (k+1)

bi

=

(k) ai,j (k)

= bi

−

X

Z

li (x)fi

i=0

a

where

(k)

(k)

Quadrature Formula

n

Step 1 - LU Decomposition (0) ak+1,k+1

4. Numerical Integration

3. Polynomial Interpolation

(k) li,k+1 a k+1,j (k)

− li,k+1 b k+1

b

f (x) dx ≈

Z

a

i, j = k + 2, ..., n, i = k + 2, ..., n.

n

n

li (x) =

Y

j=0,j 6=i

x − xj

xi − xj

=

ψ(x) , ψ(x) = (x − xi )ψ ′ (xi )

Y i=0

(x − xi )

ai f (xi ),

i=0

ai =

i = k + 2, ..., n,

n X

E(f ) =

b

n Y

li (x) dx,

j=0,j 6=i

1 (n + 1)!

Z

a

b

f

(n+1)

(ξ(x))ψ(x) dx

Newton-Cotes Formulae

Fixed Point Method I(f ) = ISn (f ) + ESn (f )

n | In (f ) | En (f ) | Rule | Degree of Precision | 1| 2| 3| 4|

h h3 f ′′ (ξ) | Trapezoid | 1 | 2 (f0 + f1 ) | − 12 5 (4) h f (ξ) | Simpson’s | 3 | (f + 4f + f ) | −h 0 1 2 3 90 5 3h (f + 3f + 3f + f ) | − 3h f (4) (ξ) | 3 Rule | 3 | 0 1 2 3 8 8 80 2h 8h7 f (6) (ξ) | Boole’s (7h + 32f + 12f + 32f + 7f4 ) | − 945 0 1 2 3 45

h (f0 + 4f1 + 2f2 + ...+ 3 = 2fn−2 + 4fn−1 + fn )

ISn (f ) = h4 (b − a)

ESn (f ) = −

|5|

180

f

(4)

a ≤ g(x) ≤ b, ∀x ∈ [a, b]

(η)

then g has a fixed point ξ ∈ [a, b].

h = (b − a)/n, fi = f (xi ), x0 = a, xn = b, xi = a + ih, ξ ∈ [a, b] If n is even, degree of precision is n + 1.

ξ is a fixed point of g if g(ξ) = ξ. If g is continuous on [a, b] and

Also, if g ′ (x) exists in (a, b) and

Romberg Integration ′

Z

n

b

f (x) dx = a

X

ai f (xi ) +

hn+3 f (n+2) (ξ) (n + 2)!

i=0

Z

hk =

n 2

b−a 2k−1

|g (x)| ≤ α < 1, ∀x ∈ (a, b)

, nk = 2k−1 , k = 1, 2, ...

then g has a unique fixed point ξ ∈ [a, b].

t (t − 1) · · · (t − n) dt

0

Iteration: Choose x0 and let xn+1 = g(xn ) until it converges. 2k−1

If n is odd, degree of precision is n.

Reducing error:

R k,1 =

hk 2

R k,j =

4j−1 R k,j−1 − R k−1,j−1

X

[f (a + (i + 1)hk ) + f (a + ihk )]

i=1

Z

n

b

f (x) dx = a

X

ai f (xi ) +

hn+2 f (n+1) (ξ) (n + 1)!

i=0

Z

n

0

4j−1 − 1 j = 1, 2, ..., n, k = j, j + 1, ..., n

t(t − 1) · · · (t − n) dt

|xn − ξ| =

If g (i) = 0, i = 1, 2, ..., k − 1 and g (k) (ξ) 6= 0, then |xn+1 − ξ|

lim

Composite Trapezoidal Rule Let h =

b−a n

b−a 2

I(f ) = , n ≥ 1, xi = a + ih, fi = f (xi ), i = 0, 1, 2, ..., n, η ∈ [a, b] I(f ) = Tn (f ) + ETn (f ) Tn (f ) =

h (fi + 2 2

n→∞

Gaussian Quadrature

Composite Numerical Integration

n−1 X

fi + fn )

Z

1

−1

1 f ( ((b + a) + t(b − a))) dt 2

5. Solutions of Nonlinear Equations

Composite Simpson’s Rule n ≥ 2, even

(b − a) 2 ′′ h f (η) 12

(ak , bk ) =

where xk =

1 (a k−1 2

|xn − ξ|k

=

n

(xk , bk−1 ) (ak−1 , xk )

if f (xk )f (bk−1 ) < 0 if f (xk )f (ak1 ) < 0

Newton-Raphason method Used to solve f (x) = 0, assumes that f ′ (x) = 6 0.

ln (ǫ−1 (b0 −a0 )) ln 2

f (xn ) f ′ (xn )

Otherwise if f (ξ ) = f (i)( ξ) = 0, i = 1, 2, ..., m − 1 and f (m) (ξ) 6= 0, then ξ is a root of multiplicity m of f (x) = 0.

xn+1 = xn − m

+ bk−1 )

Number of bisections, k ≥ ⌈

|g (k) (ξ)| 6= 0 k!

i.e. the convergence xn → ξ is of order k.

xn+1 = xn −

Bisection Method

i=1

ETn (f ) = −

αn |x0 − x1 | 1−α

⌉, tolerance = ǫ

This is a second order method.

f (xn ) f ′ (xn )...