Appunti Calcolo numerico

CALCOLO NUMERICO

(Adriano Festa)

MODALITÀ ESAME:

• Quiz: 14 domande.
• 10 Algebra lineare e geometria
• 4 Calcolo numerico

ARITMETICA, ERRORI

CALCOLO NUMERICO

disciplina della matematica che propone e analizza metodi che consentono di ottenere una soluzione numerica di problemi matematici per i quali metodi di risoluzione analitica non esistono

Verrà utilizzato il software MATLAB

Per ottenere la soluzione numerica si utilizzano ALGORITMI eseguibili da un calcolatore e dedotti dai metodi stessi.

I risultati numerici ottenuti dal calcolatore possono presentare errori.

RAPPRESENTAZIONE DEI NUMERI:

Def: Si definisce RAPPRESENTAZIONE FLOATING-POINT di un numero reale a la seguente espressione:

a = (-1)^s p N^q, s ∈ {0,1}, p ≥ 0 reale, q intero

dove N rappresenta la base del sistema di numerazione.

Def: La rappresentazione floating-point a = (-1)^s p N^q del numero reale a si dice NORMALIZZAZIONE se p soddisfa la condizione:

N^-1 ≤ p < 1

In tal caso, p e q sono univocamente determinabili.

• il numero reale non negativo p si definisce MANTISSA di a
• l'intero q si definisce ESPONENTE di a

Fissata la base N del sistema di numerazione, i valori s, p, q della rappresentazione floating-point normalizzato a = (-1)^s p N^q individuano univocamente il numero reale a

Il calcolatore può memorizzare solo mantisse con un numero finito di cifre ed esponenti appartenenti a un certo intervallo.

=> NON TUTTI I NUMERI REALI SONO ESATTAMENTE RAPPRESENTABILI su di un calcolatore

• La mantissa p possono raggiungere al massimo t+1 cifre
• L’esponente q deve soddisfare L ≤ q < U con L < 0 e U > 0

Def: Si definiscono NUMERI DI MACCHINA i numeri con mantissa ed esponente esattamente rappresentabili negli spazi a loro riservati dal calcolatore

L’insieme dei numeri macchina è costituito da un numero finito di elementi:

F = {0} ∪ {-1} * 0.q₁q₂...q_t * N^q, 0 ≤ a_i < N, q₁ ≠ 0, L ≤ q < U}

• N: base del sistema di numerazione
• q: vale 0 (segno +) o 1 (segno -)
• q₁, q_t sono interi minori uguali a N-1 e rappresentano le cifre della mantissa
• t: massimo numero di cifre della mantissa rappresentabili
• q: l'esponente

La limitazione inferiore L ≤ q sull'esponente q comporta che il più piccolo numero positivo rappresentabile come numero di macchina, sia:

m = 0.100...0 * N^L

Def: Si definisce REGIONE DI UNDERFLOW l'insieme dei numeri reali diversi da zero e appartenenti a (-m, m)

La limitazione superiore q ≤ U sull'esponente q comporta che il più grande numero positivo rappresentabile come numero di macchina sia:

M = 0.N-1N-1...N-1 * N^U

Def: Si definisce REGIONE DI OVERFLOW l'insieme dei numeri appartenenti a (-∞, -M) ∪ (M, +∞)

Condizionamento di un problema numerico:

Nella risoluzione di un problema, gli errori presenti nei dati possono influire cosi ma nei risultati.

Nello studio della propagazione degli errori, bisogna distinguere il ruolo del PROBLEMA dal ruolo dell'ALGORITMO utilizzato per risolvere tale problema.

A tale scopo si introducono le definizioni di problema numerico e algoritmo, assieme ai concetti di condizionamento di un problema e stabilità di un algoritmo.

Problema numerico.

Def.: Si definisce PROBLEMA NUMERICO una relazione funzionale φ

tra i dati x (input) e i risultati y (output).

I dati x e i risultati y devono essere rappresentabili da numeri, vettori o matrici di numeri di dimensione finita.

La connessione f tra x e y può essere:

• ESPLICITA: y = f(x)
• IMPLICITA: f(x, y) = 0

Sia y = f(x) un generico problema numerico.

Si denotino con

• x̅ una perturbazione dei dati x di input
• y̅ i risultati ottenuti dai dati x in PRECISIONE INFINITA DI CALCOLO

Def.: Un problema numerico si dice BEN CONDIZIONATO se accade che l'errore relativo associato a y̅ è dello stesso ordine di grandezza dell'errore relativo associato a x̅ o minore, altrimenti si dice MAL CONDIZIONATO

Quindi, un problema si dice ben condizionato quando le perturbazioni nei dati non influenzano eccessivamente i risultati.

Teorema:

Data una qualunque successione di nodi distinti, tutti situati in [a, b], esiste sempre una funzione continua f(x) in [a, b] che, interpolata su quei nodi, genera una successione di polinomi di interpolazione {p_n(x)} NON UNIFORMEMENTE CONVERGENTE a f(x) in [a, b].

Esempio.

Se si considerano i nodi equispaziati in [a, b]

• x_i = a + (i - 1) h , i = 1, ..., n+1 , h = (b - a)/n

come nodi di interpolazione, l'esempio che segue mostra che la successione dei polinomi interpolanti la funzione

f(x) = 1/(1 + x²)

infinitamente derivabile, detta funzione di Runge, non converge uniformemente a f(x) in [a, b] per certi intervalli [a, b].

Denotato con p_n il polinomio interpolante f(x) = 4/(4 + x²) nei nodi x_i, i = 1, ..., n+1 h equispaziati in [-5, 5] si ha

• lim_n→∞ ||E_n||_∞ = ∞

Errore di interpolazione (tende a ∞) nell'intervallo [-5, 5]

Esercizio sul calcolo dell'Errore di interpolazione:

Calcoliamo p₃(x) che interpola f(x) = sin(x) in

• x₃ = 0
• x₂ = π/2
• x₃ = π
• x₄ = 3/2 π

quindi p₃(x) possiede per (0,0) , (π/2 , 1) , (π,0) , (3/2 π , -1)

l₀(x) = {{x - (π/2)}{x - π}{x -(3/2π)}} / {π/2 (π - π)(3/2π)}

l₂(x) = (x - 0){x - π/2}{x - (3/2 π)} / π/2 ( π) (3/2 π)

p₃(x) = 0 ⋅ l₀(x) + 1 ⋅ l₁(x) + 0 ⋅ l₂(x) -1 ⋅ l₃(x) = - (x(x - 2/3) (x - π)(x - π))

(x - π )

Teorema

Sia S₃(x) la spline cubica interpolante i dati (x_i, f(x_i)) con a ≤ x_i ≤ b e soddisfacente le condizioni aggiuntive (1), (2) oppure (3).

Denotato con h_i = x_i+1 - x_i e h = max_{1 ≤ i ≤ n}h_i, se f ∈ C²[a,b] allora

‖f - S₃‖_∞ = Θ(h⁴) h→0

Inoltre, nel caso delle condizioni aggiuntive (2) oppure (3), se f ∈ C⁴[a,b] e se n*h_i ≤ y < ∞ per h → 0, si ha

‖f^(p) - S^(p)₃‖_∞ = Θ(h^4-p) h→0 p = 0, 2, 3

La condizione ⁿ/_hi ≤ y < ∞ per h → 0 impone che la partizione sia uniforme o quasi.

• Θ(h^k) è il massimo ordine di convergenza che si ottiene con le suddette spline cubiche, cioè Θ(n^k) vale anche quando f ∈ C^(k)([a,b]) con k > 4 (saturazione).
• Le derivate di S₃, fino a quelle di ordine 3, convergono uniformemente alle corrispondenti derivate di f (simultanea approssimazione).
• La convergenza uniforme delle spline interpolanti, a differenza dei polinomi interpolanti, è comunque garantita qualunque sia la funzione continua f e qualunque sia la scelta dei nodi x_i per h → 0.

Un'importante applicazione dell'approssimazione di funzione è il calcolo di integrali.

È noto che non sempre si riesce a calcolare un integrale. È questo il caso dell'integrale che definisce la FUNZIONE DEGLI ERRORI

erf(x) = ²/_√π ∫₀^x e^-t2 dt

che interviene spesso nel calcolo delle probabilità, nella statistica e nelle equazioni differenziali alle derivate parziali.

In questi casi, si può procedere approssimando l'integrale di f(x) mediante l'integrale della spline S₃(x) lineare e interpolante f in nodi equispaziati dell'intervallo ; il vantaggio è che quest'ultimo valore è analiticamente calcolabile.