Schemi riassuntivi di Analisi numerica

Introduzione all'analisi numerica

Classificazione dei problemi computazionali

• Problema diretto
• Problema inverso
• Problema di identificaz

Problema ben posto

1. la soluzione esiste
2. la soluzione è unica
3. la soluzione dipende in modo continuo dai dati del problema

se non vale 1) ∧ 2) ∧ 3) ⇒ mal posto

NUMERI DI MACCHINA E ARITMETICA DI MACCHINA

RAPPRESENTAZIONE IN VIRGOLA MOBILE NORMALIZZATA DEI NUMERI REALI

Sia x ∈ ℝ\{0} scelta una base β > 2

x = ± (d₀,d₁,d₂,...)_β β^p = ± β^p ∑_{i ≥ 1} (d_i)_ββ⁻ⁱ

p: esponente

{d_i}_{i = 1,2,...} con 0 ≤ d_i ≤ β - 1, d₁ ≠ 0: cifre della rappresentazione (o della mantissa)

m: = ∑_{i ≥ 1}d_iβ⁻ⁱ: mantissa (β⁻¹ ≤ m < 1)

INSIEME DEI NUMERI DI MACCHINA

F(β, t, L, U) := {x ∈ ℝ\{0} | x = ± ( ∑_i=1^td_iβ⁻ⁱβ^p) ∪ \{0\}

β: base t: cifre di mantissa

L, U ∈ ℤ | L < 0 \ U > 0: valori min. e max. dell’esponente p

dato x = ± 0.(d₁d₂d₃...) β^p

ℒ = fl(x) = ± 0.(d₁d₂d₃...d_t) β^p, L ≤ p ≤ U

numero di macchina corrispondente a x

ERRORI DI RAPPRESENTAZIONE:

• UNDERFLOW: |x| troppo piccolo per essere rappresentato in F
• OVERFLOW: |x| troppo grande per essere rappresentato in F
• APPROSSIMAZIONE: L < p < U ma il n° di cifre della mantissa è > t

NORME DI VETTORI E MATRICI

NORME VETTORIALI

• NORMA 1

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

• NORMA 2 O EUCLIDEA

  ||x|| = √(∑_i=1ⁿ x_i²)

• NORMA INFINITO O DEL MASSIMO

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

TEOREMA 2.1 (teorema di equivalenza)

||x||_∞ ≤ ||x||₂ ≤ ||x||₁

NORME MATRICIALI INDOTTE

• NORMA 1

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

• NORMA 2 O NORMA SPETTRALE

  ||A||₂ = √(ρ(A^TA))

  ρ: raggio spettrale

• NORMA INFINITO O DEL MASSIMO

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

CRITERI DI ARRESTO

• ASSOLUTO (poco falzivi) |x_i+1 - x_i| < toll_x
• RELATIVO |x_i+1 - x_i| < toll_r |x_i+1|
• CONTROLLO DEL RESIDUO |f(x_i)| < toll_f se :
  • |f'(α)| << 1 → test inaffidabile
  • |f'(α)| >> 1 → test restrittivo
  • |f'(α)| ≈ 1 → indicazione soddisfacente

Conclusioni:

• Quando non si ha la certezza della bontà dei test di arresto su x_i e su f(x_i), conviene includerli entrambi
• In pratica, se il criterio di arresto funziona, non si ha la soluzione esatta α, ma solo una sua approssimazione.

METODO DI BISEZIONE

4.1 TEOREMA DEGLI ZERI

1. f(x) ∈ C([a,b])
2. f(a)f(b) < 0

⇒ ∃ almeno una soluzione α di f(α)=0 in ]a,b[

METODI ITERATIVI DI PUNTO FISSO

• Metodo delle CORDE (m ≠ 0)
  • g(x) = x - f(x)/m
• Metodo di NEWTON (f'(x) ≠ 0 ∀ x ∈ [a,b])
  • g(x) = x - f(x)/f'(x)

4.6 TEOREMA DI CONVERGENZA GLOBALE

X_i+1 = g(X_i) con X₀ assegnato

1. g: [a,b] → [a,b]
2. g ∈ C¹ [a,b]
3. ∃ C < 1 | g'(x) | ≤ C ∀ x ∈ [a,b]

⇒ g ha un punto fisso α ∈ [a,b], X_i converge ad α ∀ X₀ ∈ [a,b]

lim_i→∞ |X_i+1 - α| / |X_i - α| = |g'(α)|

4.7 TEOREMA DI CONVERGENZA LOCALE

1. α punto fisso di g ∈ C¹ [α-ρ, α+ρ], ρ>0
2. |g'(x)| < 1 ∀ x ∈ [α-ρ, α+ρ]

⇒ ∀ X₀ ∈ [α-ρ, α+ρ] la succ. X_i è t.c.:

• X_i ∈ [α-ρ, α+ρ] ∀ i > 1
• lim_i→∞ X_i = α unico punto fisso di g

Procedimento

A_x = b → U_x = y

Applicare _di matrici elementari _di Gauss:

A → U, A|b → U|y

n_(k) a_k,k^(k) PIVOT

y_k^(k)

m_i,k^(k) = ^a_i,k(k)/_ak,k^(k) MOLTIPLICATORI

M^(k) = I_d + m^(k) e_k^T MATRICE ELEMENTARE DI GAUSS

M^(k) = ¹/_-mk-1

(M^(k))^-1 = ¹/_-m^-k 1 1

U = A⁽ⁿ⁾(M^(n-1))^-1 A

→ A = (M⁽⁴⁾)^-1(M⁽²⁾)^-1...(M^(n-1))^-1 A⁽ⁿ⁾

L U

Osservazioni

• si arresta se a_k,k^(k) = 0 → i minori principali di ordine 1,...,n-1 devono essere ≠ 0
• ha _a buon fine se:
  • - A strettamente diagonali dominanti per righe/colonne
  • - A simmetrica def. pos.
• se i pivot a_k,k^(k) sono molto piccoli → metodo instabile

→ Strategie Pivotali

Approssimazione ai minimi quadrati

Sistemi lineari sovradeterminati

Ax = b

• rank(A) ≠ rank(A|b) ⇒ S = ∅
• rank(A) = rank(A|b) ⇒
  • rank(A) = h soluzione unica
  • rank(A) < h infinito^n-rank(A) soluzioni

Trovare una soluzione nel senso dei minimi quadrati

‖b - Ax‖₂² ≤ ‖b - Ax‖₂² ∀ x ∈ ℝⁿ

x̄ = argmin_x∈ℝⁿ ‖b - Ax‖₂² = argmin_x∈ℝⁿ ‖r(x)‖₂² con r(x) = b - Ax

Teorema 6.1

• A ∈ ℝ^m×n (m > n) e b ∈ ℝ^m

x̄ = argmin_x∈ℝⁿ ‖b - Ax‖₂² ⇔ x̄ è soluzione di A^TAx = A^Tb

Se rank(A) = n, la soluzione è unica

Sistema delle equazioni normali

Mx = d (A^TAx = A^Tb) con M def. pos. e simmetrica quando rank(A) = n

Condizionamento del problema di interpolazione

Funzione di Lebesgue

λ_n(x) = ∑_i=0ⁿ |L_i(x)|

Relazione tra gli errori assoluti sui risultati e sui dati:

||ĥ(x) - P_n(x)||_∞ ≤ ||λ_n(x)||_∞ ||Ŷ - Y||_∞ = Λ_n ||Ŷ - Y||_∞

Costante di Lebesgue

Λ_n = ||λ_n(x)||_∞ = max_x∈(a,b) ∑_i=0ⁿ |L_i(x)|

⇒ ||ĥ(x) - P_n(x)||_∞ / ||P_n(x)||_∞ ≤ Λ_n ||Ŷ - Y||_∞ / ||Y||_∞