Teoria completa Numerical Methods in Engineering Sciences, prof.Sangalli

Numerical methods

Reminders on matrices

A ∈ R^n×n:

• A simmetrica se A=A^T.
• Matrice A definita positiva se x^TAx > 0 ∀x ∈ Rⁿ con x≠∅.
• A non singolare = ATA simmetrica e positiva definita.

Natural norm

|||A||| = supy≠∅ ||Ay|| / ||y|| verifica → ||Ay|| ≤ ||A|| ||y|| ||A + B|| ≤ ||A|| + ||B||

Solving linear systems

The problem: given b ∈ C bⁿ, A ∈ C^n×n, R ∈ R, we look X ∈ Cⁿ solution of AX = b soli: X = A^-1b.

soluzione unica se e solo se A e’ non singolare (o invertible) condizione abastanza e sufficiente e’che a abbia det(A)≠0

Simplest systems are diagonal systems

Dχ=b con 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 j=1

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,j; bj;   endend

for k = 1, ..., n - 1   for i = k + 1, ..., n     b_i; b_i + I_i,k; bk;   endend

Upper triangular matrices

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

x_n = b_n / u_nnx_n-1 = b_n-1 - u_n-1,n x_n / u_n-1,n-1x₁ = 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 simmetrica se A = A^T. Autovalori di una simmetrica sono reali.
• Matrice A definita positiva se:
  • x^TAx > 0 ∀ x ∈ Rⁿ con x ≠
  • x^TAx = 0 se x =
• A non singolare = ATA simmetrica e positiva definita.

Natural norm:

‖A‖ = sup ‖A‖ / ‖‖ ≠

Verifica → ‖A‖ ≤ ‖A‖ ‖‖

‖A + B‖ ≤ ‖A‖ + ‖B‖

Solving linear systems:

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

Simplest systems are diagonal systems

Dx = b con D = d₁₁ d₂₂ n operations

x_i = _bi/_dii i = 1,2,...,n

Lower triangular matrices →

L = [I₁₁ I₂₁ I₂₂ I_n1 I_n2 I_nn]

System can be solved “forward”

{x₁ = _b1/_I11x₂ = b₂ - I₂₁x₁

x_n = b_n - Σ_j=1^n-1 I_njx_j}_Inn

n² operations

A special lower triangular matrix

(L has only 1 on the diagonal) → L = [1 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,...,nfor j = 1,..,i-1b_i = b_i - I_i,jb_jendend

for k = 1,...,n - 1for i = k+1,...,nb_i = b_i - I_i,kb_kendend

Upper triangular matrices → U =

[U₁₁ U₂₂ U₂₁ U₃₃ U_n2 ... ]

{x_n = _bn/_Unn}

x_n-1 = b_n-1 - _Un-1,n/_Un-1,n-1

x₁ = b₁ - Σ_j=2ⁿ U_i,jx_j