Numerical Methods - Esame base - Pseudocodici ed esercizi

1- GEM + LU factorization

Forward substitution Lx = b

Backward substitution Ux = b

GEM Ux = b

Pivoting PAx = Pb

LU factorization L(Ux) = b

2- Iterative solvers

Splitting methods

Jacobi method M = diag(A)

Gauss-Seidel method M = tril(A)

3- Eigenproblems

Power method Av = λv

Inverse power method

4- Pagerank algorithm

V1 dangling

V2 unique solution

V3 w^T = w^TA

5- Least squares

Linear regression A^TAq = A^Tb

6- Nonlinear equations

Bisection method c = (a+b)/2

Newton's method x_k+1 = x_k - f(x_k)/f'(x_k)

Solution of systems F(x) = 0

7- Interpolation

Lagrange interpolation Π f = g_L

8- Quadrature

Composite midpoint rule h Σ f(x_i)

Composite trapezoidal rule h/2 (Σ f(x₀) + f(x_n))

Composite Simpson rule h/6 (Σ f_i-1 + 4f_i + f_i+1)

9- ODE

Explicit Euler ∫_a g = g(c)(d-c)

Implicit Euler ∫_a g = g(d)(d-c)

Crank-Nicolson ∫_a g = g(c+d)/2 (d-c)

Heun method y^* = f(t)

Runge-Kutta methods

Forward substitution

Lx = b

X₁ = b₁ / l₁₁X₂ = [b₂ - l₂₁x₁] / l₂₂⋮x_n = [b_n - ∑_j=1^n-1 l_njx_j ] / l_nn

Pseudo:

Input: L∈ℝ^n×n, b∈ℝⁿb₁ = b₁/l₁₁for i = 2,...,n    for j = 1,...,i-1        b_i = b_i - l_ijb_j    end    b_i = b_i / l_iiendOutput: x = b

Backward substitution

Ux = b

X_n = b_n / u_nnX_n-1 = (b_n-1 - u_n-1nx_n) / u_n-1n-1⋮X₁ = [b₁ - ∑_j=2ⁿ u_1j x_j] / u₁₁

Pseudo:

Input: U∈ℝ^n×n, u∈ℝⁿb_n = b_n/u_nnfor i = n-1,...,1    for j = n,...,i+1        b_i = b_i - u_ijb_j    end    b_i = b_i / u_iiendOutput: x = b

Power method

Av = λv

Find the eigenvector λ₁, largest in absolute value

PSEUDO:

• Input: A∈R^nxn
• Choose v₀∈Cⁿ with ||v₀|| = 1
• for k = 1, 2, ...
•  W = Av_k-1
•  v_k = W / ||W||
•  M_k = (v_k)^TAv_k
• end (stop when ||Av_k - M_kv_k|| ≤ tol)

Inverse power method

Find the eigenvector closest to μ

PSEUDO:

• Input: A∈R^nxn, μ∈C
• Choose v₀∈Cⁿ with ||v₀|| = 1
• for k = 1, 2, ...
•  W = (A - I_nμ)^-1v_k
•  v_k = W / ||W||
•  M_k = (v_k)^TAv_k
• end (stop when ||Av_k - M_kv_k|| ≤ tol)

ODES

y'(t) = f(t, y(t)) y(t₀) = y₀ t ∈ [0, T]

Explicit Euler

y₀ given y_n+1 = y_n + Δt f(t_n, y_n) n = 0, 1, ..., N-1

Implicit Euler

y₀ given y_n+1 = y_n + Δt f(t_n+1, y_n+1)

Crank-Nicolson

y₀ given y_n+1 = y_n + Δt/2 [f(t_n+1, y_n+1) + f(t_n, y_n)] n = 0, 1, ..., N-1

Heun method

y₀ given y*_n+1 = y_n + Δt f(t_n, y_n) y_n+1 = y_n + Δt/2 [f(t_n, y_n) + f(t_n+1, y*_n+1)] n = 0, 1, ..., N-1

Compute one step of Newton

(x_y - 5x = 6y + 7.5 = 0

x²y₂ - 6y₂ + 5x² = -10x_y + 12y - 60 = 0

J_F = _{∂f1/∂x ∂f1/∂y ∂f2/∂x ∂f2/∂y}

[ y - 5 ] [ x - 6 ] [ 2xy² + 10x - 20xy ] [ 2x²y - 12y - 10x² + 12 ]

J_F(x⁽⁰⁾) δ = F(x⁽⁰⁾) → [-5 -6] [δ₁] = [ 7.5 ] [0 12] [δ₂] = [ -60 ] → δ = [-9] ________________________ [-5]

x⁽¹⁾ = x⁽⁰⁾ - δ = [9] ______________________________ [5]

Given f(x) = x³ - 2x² + x - 4 write T₂(x) for x₁ = -1, x₂ = 1, x₃ = 2

L₁(x) = └_{x - x2} │┬_{x1 - x2} × x - x₃ └_{x1 - x3} = └_{x - 1} + 2 │┬_{x - 2} + 3 = └_{x² - 3x + 2}│ / 6

L₂(x) = └_{x - x1} │┬_{x2 - x1} × x - x₃ └_{x2 - x3} = └_{x + 1} / 2 ▲ x + 2 └_{+ 1} = └_{x² + x + 2}│ / 2

L₃(x) = └_{x - x1} │┬_{x3 - x1} × x - x₂ └_{x3 - x2} = └_{x + 1} / 3 [ x - 1 ] │_{+ 1} = └_{x² - 1}] │ / 3

f(x₁) = -1 - 2 - 1 - 4 = -8

f(x₂) = 4 - 4 - 1 - 4 = -4

f(x₃) = 8 - 8 + 2 - 4 = -2

T₂(x) = f(x₁)L₁(x) + f(x₂)L₂(x) + f(x₃)L₂(x) =

= ₁/₃ ( └-4x⁴ + 12x - 8 + 6x² - 6x - 12 - 2x² + 2│ ) = 2x - 6

Pseudo for Composite midpoint quadrature

Lagrange interpolation of degree 2 through