Metodi numerici e modelli matematici - 50 di 139

1. Analisi dell'errore
2. Sistemi lineari
3. Ricerca degli autovalori
4. Approssimazione di funzioni per interpolazioni
5. Spline
6. B-Spline
7. Minimi quadrati
8. Approssimazione di funzioni nel continuo
9. Approssimazione trigonometriche
10. Integrazione numerica

2-13

INTRODUZIONE AI METODI MATEMATICI E NUMERICI

LA MODELLISTICA DI UN FENOMENO SI SUDDIVIDE IN QUATTRO FASI:

1. ANALISI DEL FENOMENO: ATTRAVERSO SEMPLIFICAZIONI, ANALOGIE ED ASTRAZIONI SI EFFETTUA UN’ANALISI QUANTITATIVA
2. ANALISI DEL MODELLO: SI RICERCA ESISTENZA, REGOLARITÀ E UNICITÀ E QUINDI SI EFFETTUA UN’ANALISI QUALITATIVA
3. INDIVIDUAZIONE DEL METODO
4. IMPLEMENTAZIONE

REALTÀ OSSERVAZIONE RAPPRESENTAZIONE SCHEMATICA

MODELLO MATEMATICO

Arrotondamento (Rounding)

\(\tilde{x} = \text{arr}(x) = \tilde{m} \beta^p\)

\(\tilde{m} = \begin{cases} \text{trun}(m) & \text{se } d_{t+1} < \beta / 2 \\ \text{trun}(m + 1) & \text{se } d_{t+1} \geq \beta / 2 \end{cases}\)

Esempio: \(\beta = 10\), \(t = 1\)

• \(m\)     \(\tilde{m}\)     \(|\tilde{m} - m|\)
• 0.11   0.1   0.01
• 0.12   0.1   0.02
• 0.15   0.2   0.05
• 0.16   0.2   0.04
• 0.19   0.2   0.01

• \(|\tilde{m} - m| \leq \frac{1}{2} \beta^{1-t}\)

\(|E_A| = |\tilde{x} - x| = |\tilde{m} \beta^p - m \beta^p| = |\tilde{m} - m| \beta^p \leq \frac{1}{2} \beta^{p-t}\)

\(|E_R| = \frac{|\tilde{x} - x|}{|x|} = \frac{|\tilde{m} \beta^p - m \beta^p|}{|m \beta^p|} = \frac{|\tilde{m} - m|}{|m|} \leq \frac{1}{2} \beta^{1-t}\)

Precisione di Macchina (\(\varepsilon\))

\(\varepsilon = \begin{cases} \beta^{1-t} & \text{nel troncamento} \\ \frac{1}{2} \beta^{1-t} & \text{nell'arrotondamento} \end{cases}\)

Il problema di rappresentazione dei numeri di macchina può anche essere legato all’esponente \(p\) che può non appartenere al range di valori \([L, U]\) generando quindi problemi di underflow o overflow.

Moltiplicazioni

f(x₁, x₂) = x₁ ⋅ x₂

Divisioni

f(x₁, x₂) = _x1/_x2

Esempio

1. x² - 2px + 1 = 0

con p >> 1 il problema è ben condizionato

x₁ = p - √(p² - 1)

x₂ = p + √(p² - 1)

Algoritmo 1

1. Δ = 4(p²-1)
2. x₁ = p - √(p² - 1)
3. x₂ = p + √(p² - 1)

Nonostante sia ben condizionato

da p >> 1 l'algoritmo è instabile

a causa della cancellazione

numerica al punto 2.

Algoritmo 2

1. Δ = 4(p²-1)
2. x₂ = p + √(p² - 1)
3. x₁ = 1/_x2

Poiché x₁ x₂ = c₁

In questo algoritmo si risolve

il problema della cancellazione

numerica

||x||_∞ ≤ ||x||₂ ≤ √m · ||x||_∞

||x||_∞ ≤ ||x||₁ ≤ √m · ||x||₂

||x||_∞ ≤ ||x||₁ ≤ m · ||x||_∞

se x ∈ ℝ²

C₂ = { x ∈ ℝ² | ||x||₂ ≤ 1 }

C_∞ = { x ∈ ℝ² | ||x||_∞ ≤ 1 }

C₁ = { x ∈ ℝ² | ||x||₁ ≤ 1 }

NORMA DI MATRICE

se A ∈ ℝ^m×m f : ℝ^m×m → ℝ⁺ ∪ {0} si dice norma se:

1. f(A) ≥ 0 e f(A) = 0 ⇔ A = O ⇔ f ≠ 0
2. f(dA) = |d| f(A) ∀ d ∈ ℝ
3. f(A+B) = f(A) + f(B) ∀ A, B ∈ ℝ^m×m

(ℝ^m×m, ||.||) si dice SPAZIO DELLE MATRICI NORMATO

||A||₁ = max_1≤j≤m ∑_i=1^m |a_ij| (SOMMA ELEMENTI COLONNE)

||A||_∞ = max_1≤i≤m ∑_j=1^m |a_ij| (SOMMA ELEMENTI RIGA)

||A||₂ = √ρ(A^TA) (RAGGIO SPETTRALE = MAGGIORE IN MODO DEGLI AUTOVALORI DI A^TA)

= γ₄ + ¹/_1+x2 γ₃ + ¹/_1+x2 γ₂ + ¹/_1+x2 γ₁ + ¹/_1+x2 (E_Rx + E_Ry - E_Rz)

+ ^x₂/_1+x2 (2 E_Rx + E_Ry) =

+ ¹/_1+x2 γ₃ + δ₁ + ^x₂/_1+x2 E_Rx + ( ¹/_1+x2 + ^x₂/_1+x2 ) E_Ry - ¹/_1+x2 E_Rz

+ γ₀ + ^x₂/_1+x2 γ₃ + ¹/_1+x2 γ₂ + ¹/_1+x2 γ₁ =

= ^1+x₂/_1+x2 E_Rx + ^1+x₂/_1+x2 E_Ry - ¹/_1+x2 E_Rz

+ γ₀ + ^x₂/_1+x2 γ₃ + ¹/_1+x2 γ₂ + ^1+x₂/_1+x2 γ₁ =

= ^1+2x₂/_1+x2 E_Rx + E_Ry - ¹/_1+x2 E_Rz + γ₀ + ^x₂/_1+x2 γ₃ + ¹/_1+x2 γ₂ + γ₁

E_IN              E_ALG

a₁₁⁽¹⁾x₁ + a₁₂⁽¹⁾x₂ + a₁₃⁽¹⁾x₃ = b₁⁽¹⁾

a₂₂⁽²⁾x₂ + (a₁₂⁽¹⁾ - m₂₁a₁₃⁽¹⁾)x₃ = b₂⁽¹⁾ - m₂₁b₁⁽¹⁾

x₁ + a₁₁⁽¹⁾x₂ + a₁₃⁽¹⁾x₃ = b₁⁽¹⁾

x₂ + a₂₃⁽²⁾x₃ = b₂⁽²⁾

a₃₂⁽²⁾x₂ + a₂₃⁽²⁾x₃ = b₃⁽²⁾

(a₃₃⁽²⁾ - m₃₂a₂₃⁽²⁾)x₃ = b₃⁽¹⁾ - m₃₂b₂⁽²⁾

m₃₂ = ^a₃₂(2)/_a22⁽²⁾

A⁽³⁾x = b⁽³⁾ → SISTEMA EQUIVALENTE A QUELLO DI PARTENZA MA TRIANGOLARE

GENERALIZZANDO k = 1, m + 1 SUPPONENDO a_kk^(k) ≠ 0

{

m_ik = ^a_ik(k)/_akk^(k)

a_ij^(k+1) = a_ij^(k) - m_ika_ij^(k)

b_i^(k+1) = b_i^(k) - m_ikb_k^(k)

}

per i = k + 1, m e j = k + 1, m

Fattorizzazione di A

Si trasforma la matrice di partenza nel prodotto di matrici opportunamente scelte.

A = B C → (BC) x = b →

Sx = y

By = b

Fattorizzazione LU

(Tecnica compatta di Doolittle)

A = L U   dove:

• L è triangolare bassa
• U è triangolare alta

• a₁₁, a₁₂, a₁₃, a₁₄
• a₂₁, a₂₂, a₂₃, a₂₄
• a₃₁, a₃₂, a₃₃, a₃₄
• a₄₁, a₄₂, a₄₃, a₄₄

• 1   0   0   0
• l₂₁   1   0   0
• l₃₁   l₃₂   1   0
• l₄₁   l₄₂   l₄₃   1

• u₁₁   u₁₂   u₁₃   u₁₄
•   0   u₂₂   u₂₃   u₂₄
•     0   u₃₃   u₃₄
•       0   u₄₄

Quindi:

a₁₁ = u₁₁

a₁₂ = u₁₂

a₁₃ = u₁₃

a₁₄ = u₁₄

• a₂₁ = l₂₁ u₁₁ → l₂₁ = a₂₁ / u₁₁
• a₂₂ = l₂₁ u₁₂ + u₂₂ → u₂₂ = a₂₂ - l₂₁ u₁₂
• a₂₃ = l₂₁ u₁₃ + u₂₃ → u₂₃ = a₂₃ - l₂₁ u₁₃
• a₂₄ = l₂₁ u₁₄ + u₂₄ → u₂₄ = a₂₄ - l₂₁ u₁₄