Formulario e teoria di Calcolo numerico

MISURE di ERRORI

errore ASSOLUTO e_a = |x - x̄|

errore RELATIVO e_r = |x - x̄| / |x|

x = valore esatto x̄ = approssimazione

NORME di VETTORI

• NORMA 1: ||X||₁ = ∑ |x_i|
• NORMA 2: ||X||₂ = √(∑ x_i²)
• NORMA ∞: ||X||_∞ = max |x_i|

NORME MATRICIALI

• NORMA 1: ||A||₁ = max ∑ |a_i,j|
• NORMA 2: ||A||₂ = √λ₁(At·A)
• NORMA ∞: ||A||_∞ = max ∑ |a_i,j|
• NORMA di FROBENIUS: ||A||_F = √∑ |a_i,j|²

ARITMETICA di PRECISIONE FINITA

Intervallo delle CARATTERISTICHE: (β-n) ≤ b ≤ (β-n) L ≤ b ≤ U

• UNDERFLOW: b < L
• OVERFLOW: b > U
• NUMERI di MACCHINA: F(β, m, L, U)

PRECISIONE di MACCHINA: (x - fl(x)) / |x| ≤ E_m

• calcolo col TRONCAMENTO: E_m = β^1-m
• calcolo dall’ARROTONDAMENTO: E_m = 1 / 2 β^1-m

MISURE di ERRORI

errore ASSOLUTO e_a = |x - x̅|

errore RELATIVO e_r = |x - x̅| / |x|

x = valore esatto

x̅ = approssimazione

NORME di VETTORI

• NORMA 1: ||X||₁ = Σ |x_i|
• NORMA 2: ||X||₂ = √Σ x_i²
• NORMA ∞: ||X||_∞ = max |x_i|

NORME MATRICIALI

• NORMA 1: ||A||₁ = max Σ |a_ij|
• NORMA 2: ||A||₂ = √max λ_i (A^TA)
• NORMA ∞: ||A||_∞ = max Σ |a_ij|
• NORMA di FROBENIUS: ||A||_F = √Σ |a_ij|²

ARITMETICA di PRECISIONE FINITA

Intervallo della caratteristica: (β^-n) ≤ b ≤ (β^-n)

L ≤ b ≤ U

• UNDERFLOW: b < L
• OVERFLOW: b > U

NUMERI di MACCHINA: ƒ (β, m, L, U)

PRECISIONE di MACCHINA: |(x - fl(x)) / x| ≤   E_m

• Arrotondamento _{(x - fl(x)) / x}
• Troncamento: E_m = β^1-m
• Arrotondamento: E_m = 1/2 β^1-m

La precisione di macchina limita superiormente l'errore

Equazioni Non Lineari

Metodo di Bisezione

continua e intervallo limitatoDati (a₀, b₀), (a₀)(b₀) < 0

Calcolo xₖ = (aₖ + bₖ) / 2

• Se (aₖ) (xₖ) < 0 {aₖ₊₁ = aₖ bₖ₊₁ = xₖ
• Se (bₖ) (xₖ) < 0 {aₖ₊₁ = xₖ bₖ₊₁ = bₖ
• Se (xₖ) = 0 ➔ xₖ = x* stop

Criteri di Arresto

1. |(xₖ)| ≤ T₂     Em < T₁ ≪ 1
2. |bₖ - aₖ| ≤ T₂, |xₖ₊₁ + xₖ-1| ≤ T₃     Em < T₂, T₃ ≪ 1
3. Criterio di Suppurazione (impone un numero max di iterazioni) |aₙ - bₙ| = b₀ - a₀ ≤ T₃ ➔ R ≿ log₂ ((b₀ - a₀) / T₃)

Proprietà di Convergenza|bₖ - aₖ| = b₀ - a₀ / 2^ₖ ➔ con k → ∞Lim xₖ = x*k → ∞

Metodo di Newton

x₀ datoxₖ₊₁ = xₖ - (xₖ) / '(xₖ)     con k > 0, '(xₖ) ≠ 0

Condizioni Sufficienti per la Convergenza

• ∈ C²([a,b])
• (a) (b) ≤ 0
• Se segno di '' è costante in [a,b]
• Se segno di ' è costante in [a,b]
• '(x₀) ''(x₀) > 0
• ➔ Allora la successione converge

Criteri di Arresto

1. |(xₖ)| ≤ T₂     Em < T₁ ≪ 1
2. |xₖ₊₁ - xₖ| ≤ T₂ |xₖ₊₁ + xₖ-1| ≤ T₃     Em < T₂, T₃ ≪ 1
3. Impone un numero max (k_max) di iterazioni

INTERPOLAZIONE

MATRICE DI VANDERMONDE

V * a = y

p_n(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ

| 1 x₀ x₀² ... x₀ⁿ | | a₀ | | y₀ |

| 1 x₁ x₁² ... x₁ⁿ | * | a₁ | = | y₁ |

| ... ... | | ... | | ... |

| 1 x_n x_n² ... x_nⁿ | | a_n | | y_n |

RAPPRESENTAZIONE DI LAGRANGE

p_n(x) = Σ l_i(x) y_i = l₀(x) y₀ + l₁(x) y₁ + ... + l_n(x) y_n

con l_i(x) = π_j!=i (x - x_j) / (x_i - x_j)

RAPPRESENTAZIONE DI NEWTON

p_n(x) = A₀ + A₁ (x - X₀) + A₂ (x - X₀) (x - X₁) + ... + A_n (x - X₀) (x - X₁) ... (x - X_n-1)

A₀, ..., A_n si possono calcolare con le differenze divise

SPLINE

1) S_p(x) è un polinomio di grado p in I_i, i = 0, ..., m-1

2) S_p^(k) ∈ C^p-1([0,1])

3) lim (x - z_i) S_p^(k)(x) = lim (x - z_i)^p S_p^(k)(x), i = 1, ..., m, k = 0,1, ..., p - 1

POTENZA TRONCATA

(x - z_i)^p₊ = { 0 se x < z_i

{(x - z_i)^p se x ≥ z_i

La potenza troncata viene fatta solo con nodi interni.

MINIMI QUADRATI

p(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ

nΣx_i⁰Σx_i¹Σx_i²...Σx_iⁿΣx_i¹Σx_i²...Σx_iⁿ⁺¹...Σx_iⁿ⁺¹Σx_iⁿ⁺²Σx_i²ⁿ

nΣx_i⁰y_iΣx_i¹y_iΣx_iⁿy_i

VETTORE DEVIAZIONE

d = (y₁-p(x₁), y₂-p(x₂), ..., y_m-p(x_m))

FORMULE DI QUADRATURA

formula del PUNTO MEDIO

I_ph[β] = (β−α) f(^α+b/₂)

formula dei TRAPEZI

I_t[β] ≈ ^b−α/₂ (f(α) + f(b))

formula di SIMPSON

I_s[β] ≈ ^b−α/₆ [f(α) + 4f(^α+b/₂) + f(b)]

GRADO DI PRECISIONE

Una formula di quadratura ha grado di precisione d se è esatta, quando f è un polinomio di grado minore o uguale a d (≤ d), ed esiste almeno un polinomio di grado d+1 per cui non è esatta.

• I_ph d = 1
• I_t d = 1
• I_s d = 3

FORMULE COMPOSTE

I_ph^(m)[β] = ^h/₂ Σ_i=1^m f(^{x_2i−1 + x_2i+1}/₂)

I_t^(m)[β] ≈ ^h/₂ (f(α) + Σ_i=1^m−1 f(x_i) + f(b))

I_s^(m)[β] = ^h/₃ (f(x₀) + 2Σ_i=1^m/2 f(x_2i) + 4Σ_i=1^m/2−1 f(x_2i−1) + f(x_m))

CONVERGENZA

lim_m→∞ I_ph^(m)[β] = I[β] = ∫_α^βf(x)dx

lim_m→∞ I_t^(m)[β] = I[β] = ∫_α^βf(x)dx

lim_m→∞ I_s^(m)[β] = I[β] = ∫_α^βf(x)dx

Misure di Errori

• Errore assoluto = dipende dall'accuratezza dei problemi dei dati.
• Errore relativo = non

Norma di Vettore

Norma = una norma nello spazio R^m è una funzione che si rappresenta con || ||, che associa ad un vettore x appartenente a R^m, uno scalare (numero) non negativo ed è tale che soddisfa le seguenti proprietà:

1. ||x|| >= 0 e ||x|| = 0 se e solo se x = 0
2. ||λx|| = |λ| ||x|| λ ∈ R
3. ||x + y|| = 1)
4. ||x||_p = [ⁿ∑_i=1|x_i|^p]^1/p

Norma di Matrice

Norma = una norma la R^n*n è una funzione che associa ad ogni matrice A in R^n*n uno scalare ||A|| ed è tale da soddisfare le seguenti proprietà:

1. ||A|| >= 0 e ||A|| = 0 se e solo se A = 0
2. ||λA|| = |λ| ||A|| ∀λ ∈ R
3. ||A + B||