Metodi analitici e numerici per l'ingegneria - Lezioni

Cristina.cerutti@gmail.com cristina.cerutti@polimi.it

Quaestiones - Saleri, Gervasio - Calcolo scientifico

Salas, Regim, Zoretich, Zumno - Invito alle es. e durata parziale

Soluzione di sistemi lineari n×n

Q₁₁X₁ + Q₁₂X₂ + ... + Q_2nX_n = b₁

Q₂₁X₁ + Q₂₂X₂ + ... + Q_2nX_n = b₂

...

Q_n1X₁ + Q_n2X₂ + ... + Q_nnX_n = b_n

A = Q₁₁ Q₁₂ ... Q_1n
Q₂₁ Q₂₂ ... Q_2n
... ... ... ...
Q_n1 Q_n2 ... Q_nn matrice dei coefficienti

x→ = X₁
X₂
...
X_n vettore delle incognite

Aurina.cerutti@gmail.com aurina.cerutti@polimi.it

Questioni Salev, Gesvavo - Calcolo scientifico

Selez. Regni Zoretti, Zummo - Invito alle eg. e durate parziali

Soluzione di sistemi lineari n x n

Q₁₁x₁ + Q₁₂x₂ + ... + Q_2nx_2n = b₁

Q₂₁x₁ + Q₂₂x₂ + ... + Q_2nx_2n = b₂

...

Q_n1x₁ + Q_n2x₂ + ... + Q_nx_n = b_n

A = [ Q₁₁ Q₁₂ ... Q_1n
Q₂₁ Q₂₂ ... Q_2n
...
Q_n1 Q_n2 ... Q_nn ]. matrice dei coefficienti

x̅ = [ x₁ x₂ ... x_n ]. vettore delle incognite

\[ \vec{b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix} \]

Vettore dei termini noti

\[ A \vec{x} = \vec{b} \]

Questa eq. equivale al sistema \( n \times n \)

Teorema e regole di Cramer

Teorema di Cramer: questo sistema ammette un'unica soluzione se A è invertibile cioè se il det A ≠ 0

Se sistema ammette 1 soluzione ↔ A è invertibile ⇒ det A ≠ 0

Regole di Cramer

\[ x_i = \frac{\text{det } A_i}{\text{det } A} \]

\[ A = \begin{bmatrix} | & | & | \\ a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ | & | & | \end{bmatrix} \]

Quindi devo calcolare n+1 determinanti

Numero di operazioni per sistema di ordine n ≈ 3(n!)

O(n) e ordine di grandezza

Metodi diretti e iterativi

Metodi diretti: prevedono una procedura come Gaussian e alla fine ho la risposta

Metodi iterativi: procedura in cui ad ogni passaggio mi avvicino alla risposta, con infiniti passaggi arrivo alla risposta

Matrice triangolare bassa o superiore

Quando A ha una forma particolare (matrice triangolare bassa/superiore) la risoluzione è semplice

A matrice triangolare bassa/superiore

\[ \begin{bmatrix} q_{11} & 0 & \ldots & 0 \\ q_{21} & q_{22} & 0 & \ldots \\ q_{31} & 0 & q_{33} & \ldots \\ \vdots & \vdots & \ddots & \ddots \\ q_{nn} \end{bmatrix} \]

Può succedere che gli sia pari a zero, tranne quelli della diagonale principale

\[ \text{det A} = \prod_{i=1}^{n} q_{ii} ≠ 0 \quad \text{↔} \quad q_{ii} ≠ 0 \quad \forall i = 1, \ldots, n \]

\[ A \vec{x} = \vec{b} \]

\[ a_{11} x_1 = b_1 \]

\[ a_{21} x_1 + a_{22} x_2 = b_2 \]

\[ a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n = b_n \]

x₁ = b₁/a₁₁ sostituisco poi nella seconda eg

x₂ = 1/a₂₂ (b₂ - a₂₁x₁)

Abbiamo calcolato tutte le x fino a K-1

x_k = 1/a_kk (b_k - K-1 ∑_i=1a_kix_i)

Generica formula valida per ogni K che va da 1 a n (∀K=1,...,n)

Metodo di sostituzione in avanti (forward substitution)

Numero di flops

#lops: numere di operazioni elementari.

Calcolo il numero di flops: per x_k (so un’unica operazione, per x_k ho 3k operazione {1+2}, per x_n ho...

Quando numero totale di flops: ∑ⁿ_k=1(1+2(K-1)) = 1 + ∑ⁿ_k=12(K-1) = 1 + 2 ∑ⁿ_k=1(K-1) = 1 + 2 | con K=1 n(n-1) | = n²+ 1 + 1 + n²(K-1) | n-1 3(n-1) | = n³ |+ ... | secondo 香港六合彩n = 2

Matrice triangolare alta o superiore

A matrice triangolare alta (o superiore)

A = a₁₁ | a₁₂ | a_1n / 0 | a₂₂ | a_2n / 0 | 0 | a_nn