Calcolo

Calcolo numerico 3 - Sistemi lineari

Norme di un vettore e di una matrice

x = (x₁, ..., x_n)^T ∈ ℝⁿ una colonna

‖x‖₁ = Σ |x_i|, i = 1..n

‖x‖₂ = √Σ x_i² = √x^Tx

‖x‖_∞ = max |x_i|

A_i,j = (a_i,j) i = 1, ..., m; j = 1, ..., n ∈ ℝ^m×n

‖A‖₁ = max Σ |a_i,j| 1 ≤ j ≤ n

‖A‖_∞ = max Σ |a_i,j| 1 ≤ i ≤ m

Date una norma di un vettore e una di una matrice, si dice che le norme sono compatibili se:

‖Ax‖ ≤ ‖A‖ ‖x‖ ∀ A ∈ ℝ^m×n e ∀ x ∈ ℝⁿ

Matrici

D: permutazione: si ottiene permutando le righe della matrice identità

Diagonale dominante per righe: se |a_i,i| > Σ |a_i,j| per i = 1, ..., n

Diagonale dominante per colonne: se |a_i,i| > Σ |a_j,i| per i = 1, ..., n

Simmetrica definita positiva: se x^TAx > 0 ∀x ≠ 0

Condizionamento di un sistema lineare

( ... A ... )_m×n ( ... x ... )_n×1 = ( ... b ... )_m×1 ⟷ Ax = b

Se il sistema ha una e una sola soluzione ⟹ la matrice A è non singolare.

A, b dati perturbati x soluzione in aritmetica esatta del sistema perturbato Āx̃ = b̃.

È necessario studiare le relazioni tra gli errori relativi:

‖x-x̃‖_∞/‖x‖_∞, ‖A-Ā‖_∞/‖A‖_∞, ‖b-b̃‖_∞/b̃

Teorema

Se ‖A-Ā‖ 1/_2‖Ā‖ il sistema Āx̃ = b̃ ammette una e una sola soluzione e

‖x-x̃‖_∞ ≤ 2 κ(A) [‖A-Ā‖/‖A‖ + ‖b-b̃‖_∞/b̃]

con κ(A) = ‖A‖ ‖Ā^-1‖ numero di condizionamento

Calcolo numerico 3 - Sistemi lineari

Norme di un vettore e di una matrice

x = (x₁, ..., x_n)^T ∈ ℝⁿ

||x||₁ = ∑_i=1ⁿ|x_i|

||x||₂ = √∑_i=1ⁿx_i² = √x^Tx

||x||_∞ = max|x_i|

A_i,j = (a_i,j) i = 1, ..., m j = 1, ..., n ∈ ℝ^m*n

||A||₁ = max_j=1,...,n ∑_i=1^m |a_i,j|

||A||_∞ = max_i=1,...,m ∑_j=1ⁿ |a_i,j|

Dato una norma di un vettore e una di una matrice, si dice che le norme sono compatibili se

||Ax|| ≤ ||A|| ||x|| ∀ A ∈ ℝ^m*n e ∀ x ∈ ℝⁿ

Matrici

D: permutazione: si ottiene permutando le righe della matrice identità

Diagonali dominante per righe: se |a_i,i| > ∑_j≠i |a_i,j| per i = 1, ..., n

Diagonale dominante per colonne: se |a_i,i| > ∑_i≠j |a_i,j| per a = 1, ..., n

Simmetrica definita positiva: se x^TAx > 0 ∀x≠0

Condizionamento di un sistema lineare

a₁₁ a₁₂ ... a_1n x₁ b₁

a₂₁ a₂₂ ... a_2n x₂ b₂

...

a_m1 a_m2 ... a_mn x_n b_m

Ax = b

Se il sistema ha una e una sola soluzione => la matrice A è non singolare.

A, b dati perturbati x soluzione in aritmetica esatta del sistema perturbato Ãx = b.

È necessario studiare le relazioni tra gli errori relativi:

||x-x‾||/||x||

||A-Ã||/||A||

||b-b‾||/||b||

Teorema

Se ||A-Ã|| -1|| il sistema Ãx = b ammette una e una sola soluzione e

||x-x‾||/||x|| ≤ 2 K(A) ||A-Ã||/||A|| + ||b-b‾||/||b||

con K(A) = ||A|| ||A^-1|| numero di condizionamento

se K(A) ≈ 1 sistema ben condizionato

se K(A) ≫ 1 sistema molto condizionato CN≫1

Costi computazionali

• Metodo di Gauss: O(n³)
• Metodo di Cramer: (n+1)!

Metodi matematici

Matrice dei coefficienti A è diagonale

a_ii ≠ 0   i = 1, ..., n

x₁

x₂

x₃

...

x_n

Matrice dei coefficienti A è triangolare superiore a_ii ≠ 0   i = 1, ..., n

a₂₂x₂ + a₂₃x₃ + ... = b₂

a_nnx_n = b_n

x_n = b_nn/a_nn   x_n-1 = [b_n-1 - a_n-1n x_n]/a_n-1n-1 ...

x₁ = [b₁ - ∑_i=2ⁿ a_1ix_i]/a₁₁

Metodo di sostituzione all'indietro

x_n = b