Metodi numerici per l'ingegneria

Risoluzione di sistemi lineari

Dati un vettore b ∈ ℝ^m e una matrice A ∈ ℝ^n×m, si cerca x ∈ ℝ^m tale che Ax = b.

Condizione necessaria e sufficiente per un'unica soluzione

A non singolare, cioè det A ≠ 0, quindi A invertibile.

Soluzione

x = A^-1b → Costoso

Non si calcola x se non è necessario A^-1, ma si cerca di risolvere il sistema. Questo è molto costoso. Nel caso di alcune matrici si hanno però dei costi contenuti. Nel seguito sono mostrate le soluzioni di tali matrici.

Matrice A diagonale

A = ➠    ^{0     d₂₂   …  …     d_mm}

Condizione necessaria e sufficiente → d_ii ≠ 0 ∀i

Sistema costituito da n equazioni indipendenti tra di loro:

• x₁ = b₁ ⁄ d₁₁
• …
• x_m = b_m ⁄ d_mm

Costo: m ops

A triangolare superiore

A = ^{u₁₁ u₁₂ u₁₃ …  u_1m0  u₂₂ u₂₃ …0      u₃₃ ……       u_mm}

Condizione necessaria e sufficiente → u_ii ≠ 0 ∀i

Sistema:

• x₁ = b₁ ⁄ u₁₁
• …
• x_n = b_m ⁄ u_mm

A inferiore

A = ^{l₁₁ 0      …l₂₁ l₂₂    0l₃₁ l₃₂ l₃₃ ……       l_m1 l_m2 l_m3 … l_mm}

Condizione necessaria e sufficiente → l_ii ≠ 0 ∀i

Sistema:

• x₁ = b₁ ⁄ l₁₁
• x₂ = (b₂ - l₂₁x₁) ⁄ l₂₂
• …
• x_m = (b_m - ∑ l_ijx_j) ⁄ l_mm

Risoluzione di sistemi lineari Ax = b con A ∈ ℝ^n×n

Dati un vettore b ∈ ℝ^m e una matrice A ∈ ℝ^n×m, si cerca x ∈ ℝ^m tale che: Ax = b.

Condizione necessaria e sufficiente per un'unica soluzione

A non singolare, cioè det A ≠ 0, quindi A invertibile.

Soluzione

x = A^-1b → COSTOSO.

Non si calcola A^-1 se non è necessario, ma si cerca di risolvere il sistema. Questo è molto costoso. Nel caso di alcune matrici si hanno però dei costi contenuti. Nel seguito sono mostrate le soluzioni di tali matrici.

Matrice A diagonale

A = [d₁₁ 0 ... 0] [0 d₂₂ ... 0] [...] [0 0 ... d_mm]

Condizione necessaria e sufficiente ⇒ d_ii ≠ 0 ∀ i

Sistema costituito da m equazioni indipendenti tra di loro:

• x₁ = b₁ / d₁₁
• [...]
• x_m = b_m / d_mm

Costo: m ops

A triangolare superiore

A = [u₁₁ u₁₂ u₁₃ ... u_1m] [0 u₂₂ u₂₃ ... u_2m] [0 0 u₃₃ ... u_3m] [...] [0 0 ... u_mm]

Condizione necessaria e sufficiente ⇒ u_ii ≠ 0 ∀ i

Sistema:

• x_m = b_m / u_mm
• [...]
• x₁ = (b₁ - Σ_j=i+1^m u_ij x_j) / u₁₁

Inversione

A = [ℓ₁₁ 0 ... 0] [ℓ₂₁ ℓ₂₂ 0 ...] [ℓ₃₁ ℓ₃₂ ℓ₃₃ ...] [...] [ℓ_m1 ... ℓ_mm]

Condizione necessaria e sufficiente ⇒ ℓ_ii ≠ 0 ∀ i

Sistema:

• x₁ = b₁ / ℓ₁₁
• x₂ = (b₂ - ℓ₂₁ x₁) / ℓ₂₂
• [...]
• x_m = (b_m - Σ_j=1^m-1 ℓ_ij x_j) / ℓ_mm

Si parte dall'ultima equazione, si parte dalla prima equazione.

Geometrico termine

Il costo per il calcolo del generico termine k è dato da m operazioni. In totale COSTO = m(m+1)/2 ⇒ O(m²).

Metodo di Cramer

Nel caso di una generica matrice A, si potrebbe usare il METODO di CRAMER che permette di trovare la soluzione esatta data da:

dove A_i è ottenuta sostituendo alla colonna i il vettore dei termini noti. Il costo per il calcolo di un determinante è O(m!).