Metodi Analitici e Numerici / Calcolo Numerico - teoria parte 1

METODI ANALITICI E NUMERICI

PARTE II → CALCOLO NUMERICO

1. INTRO ANALISI NUMERICA

1. Rappresentazione macchina dei num. reali

def.: IF = insieme dei numeri FL_OATING-POINT (numeri reali rappresentabili al calcolatore)

x ∉ F

fl(x) =: rappresentare floating point di x (se x ∉ IF)

F = F₀ ∪ {∞}

oss. dim {F₀?} ⊂ +∞

x ∈ F₀ → x = (-1)^s m β^e-t

    = (-1)^s (a₁, a₂, ..., a_t) β^e-t

β = BASE (decimale → β = 10, binario β: 2)

m = MANTISSA

a_i ∈ cifre

e = esponente, e ∈ N, e ∈ [L, U] (L < 0, U > 0)

λ = segno =: → 0 → n^o positivo [(-1)-1] 0 ^o

      1 → n^o negativo

[primo cifra (si assume diversa da 0)]

0 ≤ a_i ≤ β-1

0 ≤ i₂, i = 2, ..., t

oss X_min = β^-1 e n^o min + piccolo rappresentabile (accetto lo 0)

X_max = β^t(1-β^-t) → n^o grande rappresent.

Numero elementi F₀ = 2(β-1) β^t-1(-L+U+1)

2) EPSILON MACCHINA ε_M = β^1-t

è il piú piccolo numero tale che fl(1+ε_M) > 1

DEF. ERRORE DI ARROTONDAMENTO

|X - fl(X)| ≤ 1^/2 ε_M |X|

dist. relativa tra numero reale e n^ro rapp^to macch^ina

ESEMPIO

F₀(2, 2, -1, 2)

β = t = L = U

ε_M = β^1-t = 2^-t = 1^/2

X_MIN = β^L-1 = 2^-2 = 1^/4 < ε_M

(!) Il calcolatore conta ordine delle operazioni!

1+1/4+1/4 → 1/2 → 1/= 1 → 1/

1+(1/4+1/4) → 1/2 → 1/2+1 → 3/2

OSS fl(1+fl(X)) è rappr. di 1+X

→ ordine è importante perché il calcolatore approssima i numeri

MANTISSA

t = 2 → M = q = a₂

0 ≤ α = β^-1 = 2^-1 = 1

0 ≤ e^-1 < 1

c = 1

es e [1, U] = [1, 2]

c = -1 0 1 2

m = 1/4 1/2 1 2

in: 3^/8 3^/4 3^/2 3

In pratica sono n "cifre" che si ottengono facendo (−1)^L (cioè β^−L)

(conv. daremmo 1→∞ numeri positivi)

A =

X =

b =

Scrittura in forma algebrica

CRAMER:

X_i = ^det(A_i')/_det(A)

(3ⁿ⁺¹ - 1)!

CALC:

OSS → AX = B → X = A^-1B

METODI:

• Metodi diretti → Risolvono sist. lineare in n° finito di passaggi
• Metodi iterativi → Ottengono soluz. X in n° infinito

Calcolo matrice inversa inefficiente → NON SI FA!

OSS AX = b₁. Con b₂ ≠ b₁ stessa matrice A!

• ← è solo di teoria, tutto deve fare solo con avanti e all'indietro

L₁y₁ = b₁ e poi Ux₁ = y₁

[Le matrici L e U le ho già in MATLAB e immagino in memoria]

OSS det(A) = ?

A = L・U → det(A) = det(L)・det(U) =

   ∏_i=1ⁿ u_ii

• tutti ell^a (già triangolare)
• stima = O(²/₃n³)

A = L・U →

sulla diagonale primi di somma di elementi di U

del A ε R^nxn E:

• simmetrica ↔ A = A^T TRASPOSTA
• definita positiva ↔ x^TA^{x> 0} ∀ x ε Rⁿ
• a dominanza diagonale per righe ↔   |a_ii| ≥ ∑_j≠i|a_ij|   ∀ i = 1,...,n

↻ &arr; se ↻ IN MODULO

a dominanza diagonale per colonne ↔  |a_jj|≥ ∑_i≠j|a_ij|   ∀ j = 1,...,n

• a dominanza stretta se

↻ e simmetrica

A =^|5   _{-1   3}⁴   _{6   2}⁰   _{-5   1}

• 5 > |-4| + 3 = 4
• 6 > 9 + 12 = 6
• |0| + |-1| + 5

↔ Dominanza diagonale

lim K→∞ ||B^K|| = 0 ⇔ lim N→∞ B^K = O ⇔ ρ(B) < 1

matrice nulla

Prop Condiz. necessaria e sufficiente :

Metodo iterativo converge alla sol. esatta x̄ di Ax̄ = b̄ per ogni scelta del vettore iniziale x⁽⁰⁾∈ℝⁿ ⇔ ρ(B) < 1

inoltre la convergenza è tanto + rapida tanto minore è il valore ρ(B)

(matrice di iterazione)

Come scelgo B ? → Metodi di splitting

Per ℝ^n×n, non singolare → Matrice di precondizionamento (o precondizionatore)

A = P - P^-1B

A x̄ = b̄ → P x̄ = (P - A)x̄ + b̄ → x̄ = P^-1(P - A)x̄ + ρ^-1b̄

Splitting = Scomposizione additiva della matrice A

B = I - P^-1A ; ỹ = P^-1b

p^(k+1) = (P-A)^(k) + p , k = 0,1, ...

p^(k+1) + ^(k) = p^(k) - A^(k) ⟺ ^(k) = P^-1(b̄ - A^(k)) = ρ^-1(k)

^(k) ∈ ℝⁿ

residuo precondizionato

OSS ̅^(k+1) = b̄ - A̅^(k+1) = b̄ - A[I - ρ^-1A]^(k) + ρ^-1b̄ =

= [b̄ - A^(k)] + Aρ^-1AX^{(k) - Aρ-1b =}

= [b̄ - A^(k)] + ρ^-1AX^(k)

p^(k+1) = p - (p - (p_Ax^(k) - b̄)) =

= - A [ p^-1(b̄ - A^(k))]

sist. lineare "facile"      sist. lineare "difficile"

_K(A^-1) ≈ 1         _K(P^-1A) ≈ 1

_K(A) + 1          _K(P^-1A) + 1 ≈ 0

↓ convergenza lenta       ↓ convergenza in 1 iterazione

↓ molto conv. veloci

Devo scegliere loro compromesso quando il C condizionamento K sa piccolo

Metodo del gradiente →

solo se A^T simmetrica e def. positive

Metodo gradiente → P = I e α_k = ( r^(k)T r^(k) ) / ( r^(k)T A r^(k) )

(Metodo di Richardson direzione —    k non varia con k)

Metodo gradiente precondizionato, P ∈ Rⁿ simm. e def.

via the α_k = ( z^(k)T r^(k) ) / ( z^(k)T A z^(k) )

Metodo di Richardson direzione di precondiz.

k = 0, 1, 2, ...

→ USO RESIDUO PRECONCILIO ζ^(k)

Algoritmo (Gradiente)

• Dato x⁽⁰⁾,   r⁽⁰⁾ = b - Ax⁽⁰⁾
• Per k = 1, 2, ... (fino a un certo errore)

→ α_k = ( r^(k) r^(k) ) / ( r^(k) A r^(k) )

x^(k+1) = x^(k) + α_k r^(k)

r^(k+1) = r^(k) - α_k A r^(k)

Algoritmo (Gradiente precondiz.)

• Dato x⁽⁰⁾ e scelto P

  z⁽⁰⁾ = calo.

Per k = 0, 1, ...

→ Risolvo P z^(k) = r^(k)

α_k con k 2 (v. sopra punto in rosso)