Teoria completa Numerical Methods in Engineering Sciences, prof.Sangalli

Numerical methods

Reminders on matrices

A ∈ R^n×n: A is symmetric if A = A^T. A matrix A is positive definite if x^TAx > 0 ∀ x ∈ Rⁿ with x ≠ ∅. A is non-singular if A^TA is symmetric and positive definite.

Natural norm

|||A||| = sup_y≠∅ ||Ay|| / ||y||. Verify → ||Ay|| ≤ ||A|| ||y||, ||A + B|| ≤ ||A|| + ||B||.

Solving linear systems

The problem: given b ∈ Cⁿ, A ∈ C^n×n, R ∈ R, we look for X ∈ Cⁿ solution of AX = b. Solution is X = A^-1b. There is a unique solution if and only if A is non-singular (or invertible). A necessary and sufficient condition is that det(A) ≠ 0.

Simplest systems are diagonal systems

Dχ = b with D =
d₁₁ 0
0 d₂₂

x_i = b_i / d_jj, i=1,2,...,n
n operations

Lower triangular matrices

L =
l₁₁ 0
l₂₁ l₂₂
l_n1 l_n2 l_nn

System can be solved "forward":
x₁ = b₁ / l₁₁
x₂ = (b₂ - l₂₁x₁) / l₂₂
x_n = (b_n - ∑ l_njx_j) / l_nn

n² operations

A special lower triangular matrix

(L has only 1 on the diagonal) → L =
1 0
l₂₁ 1
l_n1 l_n2 1

Two equivalent algorithms:
for i = 2, ..., n
  for j = i - 1, ..., 1
    b_i = b_i - I_i,jb_j;
  end
end

for k = 1, ..., n - 1
  for i = k + 1, ..., n
    b_i = b_i - I_i,kb_k;
  end
end

Upper triangular matrices

U =
u₁₁ u₁₂ u_1n
0 u₂₂ u_2n
0 0 u₃₃

x_n = b_n / u_nn
x_n-1 = (b_n-1 - u_n-1,n x_n) / u_n-1,n-1
x₁ = (b₁ - ∑ u_1,jx_j) / u₁₁, j=2

n² operations

Execution time

t = # operations / # flops

Numerical methods

Reminders on matrices

A ∈ R^n×n: A is symmetric if A = A^T. Eigenvalues of a symmetric matrix are real. A matrix A is positive definite if x^TAx > 0 ∀ x ∈ Rⁿ with x ≠ x^TAx = 0 if x = A is non-singular = A^TA is symmetric and positive definite.

Natural norm

‖A‖ = sup ‖A‖ / ‖‖ ≠ Verify → ‖A‖ ≤ ‖A‖ ‖‖‖A + B‖ ≤ ‖A‖ + ‖B‖

Solving linear systems

The problem → given b ∈ Rⁿ, A: Rⁿ x Rⁿ we look for X ∈ Rⁿ solution of AX = b. Solution: x = A^-1b.

Simplest systems are diagonal systems

Dx = b with D =
d₁₁ 0
0 d₂₂

n operations
x_i = b_i / d_ii i = 1,2,...,n

Lower triangular matrices

L =
I₁₁ 0
I₂₁ I₂₂
I_n1 I_n2 I_nn

System can be solved "forward":
x₁ = b₁ / I₁₁
x₂ = b₂ - I₂₁x₁
x_n = b_n - Σ_j=1^n-1 I_njx_j / I_nn

n² operations

A special lower triangular matrix

(L has only 1 on the diagonal) → L =
1 0
I_n1 1
I_n1 I_n2 1

x₁ = b₁
x₂ = b₂ - I₂₁x₁
x_n = b_n - Σ_j=1^n-1 I_njx_j

Two equivalent algorithms:
for i = 2,...,n
for j = 1,..,i-1
b_i = b_i - I_i,jb_j
end
end

for k = 1,...,n - 1
for i = k+1,...,n
b_i = b_i - I_i,kb_k
end
end

Upper triangular matrices

U =
U₁₁ U₁₂ U_1n
0 U₂₂ U_2n
0 0 U₃₃

x_n = b_n / U_nn
x_n-1 = (b_n-1 - U_n-1,n x_n) / U_n-1,n-1
x₁ = (b₁ - Σ_j=2ⁿ U_1,jx_j) / U₁₁