Appunti di calcolo numerico

Errore assoluto E_a = |x - X| dipende dall'ordine di grandezza

Errore relativo E_r = |x - X| / |x| non dipende dall'ordine di grandezza

X = ± 0.a₁a₂a₃ ... .A_nm^b β^e A_n ≠ 0 β = base

• numero in virgola mobile normalizzato
• a₁a₂a₃ ... A_nm^b MANTISSA A_n ≠ 0
• base di numerazione
• e = CARATTERISTICA (esponente della base)

Dati x e x' in V.M.N. (virgola mobile normalizzata)

|x - X| / |x| ≤ 10^-n, x ≠ 0

X approssima x con K cifre significative. (attendibili: non esatte)

NORME VETTORI

• P = 1   ||X||₁ = ∑ |x_i| Norma 1
• P = 2   ||X||₂ = ( ∑ |x_i|^p )^1/p Norma 2
• P = ∞   ||X||_∞ = max |x_i| Norma inf.

L'errore relativo e assoluto tra vettori si calcola usando la stessa norma

NORME MATRICI

• P = 1   ||A||₁ = sup_x∈ℝᵐ ||Ax||₁ / ||x||₁ = max_j∈{1...n} ∑ |a_ij| = Il massimo delle somme dei valori assoluti degli elementi pesi per colonna
• P = 2   ||A||₂ = sup_x∈ℝᵐ ||Ax||₂ / ||x||₂ = √(max_i∈ℜ λ_i(A^TA))
• P = ∞   ||A||_∞ = sup_x∈ℝᵐ ||Ax||_∞ / ||x||_∞ = max_i∈{1...m} ∑ |a_ij| = Il massimo delle somme dei valori assoluti degli elementi pesi per righe

Norma Frobenius   ||A||_F = √( ∑_i=1^m ∑_j=1ⁿ a_ij² )

Def (Norma vettore)

Una norma vettoriale è una funzione V→ℝ che associa ad un vettore x∈ℝⁿ un numero reale ‖x‖ t.c.

• ‖x‖≥0
• ‖x‖=0 sse x=0
• ‖λx‖=|λ|‖x‖ ∀λ∈ℝ
• ‖x+y‖≤‖x‖+‖y‖

Def (Norma Matrice)

Una norma matriciale è una funzione ∧:A→ℝ che associa ad una matrice A∈ℝⁿˣᵐ uno scalare ‖A‖ t.c.

• ‖A‖≥0 e ‖A‖=0 sse A=0
• ‖λA‖=|λ| ‖A‖ ∀λ∈ℝ
• ‖A+B‖≤‖A‖+‖B‖ ∀A,B∈ℝⁿˣᵐ
• ‖λ·B‖≤‖λ‖‖B‖

x ± 0̥,a₁a₂a₃... con β⁰ a₀ →

p → numero di macchine

t → numero di cifre punto per rappresentare la mantissa, segno escluso

m → numero di cifre finito per rappresentare la caratteristica, escluso

L’insieme dei numeri di macchina è rappresentato da quei numeri la cui rappresentazione fl(x) floating point in base β=2 riduce al più n cifre per la mantissa e m cifre per la caratteristica.

Standard IEEE

• Precisione finita/semplice β=2 32 bit
  • 1 bit per il segno
  • m=23 bit
  • b=8 bit
    • 1 bit per il segno
    • n=7 bit
• Precisione doppia β=2 64 bit
  • 1 bit per il segno
  • m=52 bit
  • b=11 bit
    • 1 bit per il segno
    • m=10 bit

Metodo delle Secanti

Dati x₀ e x₁.

Retta secante per (x₀, f(x₀)) e (x₁, f(x₁)) f(x₀) ≠ f(x₁).

y - f(x₀) = (f(x₁)-f(x₀)) / (x₁-x₀) (x-x₀)

y = f(x₁) + (x-x₁) (f(x₁)-f(x₀)) / (x₁-x₀)

Trovata l'intersezione con asse x → x₂

Calcola secante tra x₁ e x₂ ... ecc.

x₀, x₁ dati,

x_n+1 = x_n - f(x_n)(x_n-x_n-1)/(f(x_n-f(x_n-1))

f(x_n) ≠ f(x_n-1)

Condizionamento Problemi

Bene condizionato → piccole variazioni sui dati → piccole perturbazioni

Mal condizionato → piccole variazioni sui dati → grandi perturbazioni

Numero di condizionamento di una matrice

A x = b, A ∈ R^n×n, b ∈ Rⁿ, det(A) ≠ 0 b ≠ 0

A(x+Sx) = b+Sb

‖Ax+Sx‖ ≤ ‖AΔ‖‖x‖

Let α = sup_{x ∈ Ω} ‖Ax‖/‖x‖

Ax + ASx = b +Sb → ASx =Sb → Sx = A^-1Sb

‖Sx‖ ≤ ‖A^-1‖ ‖S‖ ‖b‖

α‖Sx‖ ≤ ‖A‖ ‖Δx‖

1/‖Δx‖ ≤ ‖A‖ ‖Δx‖

K(A) = ‖A‖‖A^-1‖ → numero di condizionamento di A

K(A) ≥ 1

Errore di interpolazione

p_m(x) t.c. p_m(x_i) = y_i, i = 0:m

f t.c. y_i = f(x_i), i = 0:m

E_m(x) = f(x) - p_m(x)

Errore di interpolazione -> E_m(x) = f(x) - p_m(x), x ∈ [a,b] I

Supponiamo f ∈ C^m+1 [a,b]

E_m(x,n) = f^(m+1)(ζ)/(m+1)! ∏_{i = 0:m}(x-x_i)

Per controllare l'errore si diminuisce l'intervallo o si aumenta il grado.

Funzioni Spline

Dati x = z₀ < z₁ < z₂ < ... < z_m = b, poniamo I_j = [z_j, z_j+1], j = 0:m-1

Definizione

Una funzione r(x) è una polinomiale a tratti di grado p se r(x) è un polinomio di grado p in ciascun intervallo I₀, I₁, ..., I_m

Sp_k è una Spline di grado p se:

• Sp_k è un polinomio di grado p in I₀, I₁, ..., I_m

• DⁱSp_k-1(x) = DⁱSp_k(x), i = 1:m

• S_pk(x) è una spline di grado k se:
  • lim_x→z0 S_pk(x) = lim_x→z1 S_pk(x), k = 0:p-1

  • p

    p(p+1 )(m+1) = mp + m + p + 1