Appunti del corso completo di Calcolo numerico

CALCOLO NUMERICO

ALGORITMI

Definizione qualitativa: un algoritmo è una sequenza finita di istruzioni che date n variabili di partenza permette di fornire una soluzione a un calcolo risolvibile in un tempo finito.

L’algoritmo quindi, oltre a restituire la soluzione si deve assicurare che darà il messaggio giusto dove quest’ultima dèboreva per permettere al calcolatore di capire.

I METODI sono algoritmi con tempi di risoluzione infiniti.

Gli algoritmi sono scritti nel METALINGUAGGIO, ovvero in una lingua non ambigua.

Un tipo di istruzione che apre l’algoritmo è allo stesso tempo chi lo chiude è quello di assegnazione: N := E, dove E è un’espressione matematica e N è una variabile numerica. Prima si calcola E e poi si memorizza il risultato con il nome della variabile N.

Algoritmo della somma di m numeri:

Dati a₁, a₂, ..., a_n, calcoliamo Σ a_i = S

S := 0 (inizializzazione della variabile somma)

• Per i = 1, ..., mS := S + a_i

Quando i = 1, S = 0 e S = 0 + a₁

Quando i = 2, S = a₁ S := a₁ + a₂

Quando i = m S := a₁ + ... + a_m, S = a₁ + ... + a_m

Per il prodotto di m numeri:P = a₁, a₂...a_m

P := 1 (elemento neutro)

• P := P · a_i per i := 1, ..., m

Per calcolare il massimo tra n numeri:

Algoritmo - dati a₁, a₂, ..., a_n, calcolo M := max a_i

Poi si confrontano gli elementi due a due M := a₁

Per i := 1, ..., m (il primo confronto è tra M e A₂)

Se M < a_i allora M := a_i (aggiorna il valore del massimo)

Quando arriva a n ha trovato il massimo.

Queste algoritmi è applicabile a ogni problema simile. Gli algoritmi devono risolvere problemi con dimensione aritmetica.

Entrambi gli errori sono considerati senza segno, ma l'errore assoluto si rifà ad un ordine di grandezza di X, e l’errore relativo normalizza l'errore con la grandezza di X a cui si sta guardando. Quindi, l’errore relativo ci dà l’accuratezza dell’approssimazione.

es: X₁ = 10

X₂ = 1000

X’₁ = 11 X’₂ = 10001

L’errore assoluto E_a è 1 in entrambi i casi, ma

E_r1 = ¹/₁₀ = 10^-1

E_r2 = ¹/₁₀₀₀ = 10^-4

RAPPRESENTAZIONE IN VIRGOLA MOBILE NORMALIZZATA (floating point)

Un qualunque numero in forma normalizzata è del tipo:

X = ±a₁a₂ ... a_s · 10^E

L’ipotesi fondamentale per questo standard è che sia:

0 < a_i ≤ 9 e a₁ ≠ 0

Grazie a questo standard posso scrivere i numeri in modo univoco.

es: 27,43 in forma normalizzata è 0,2743 · 10²

0,00833 in forma normalizzata è 0,833 · 10^-3

La sequenza delle cifre dopo la virgola si chiama MANTISSA, e viene moltiplicata per la caratteristica, che nella rappresentazione normalizzata è unica.

esempio: prendo i due numeri X₁ = 583,54 e X₂ = 0,0058354, tali che X₂ = 0,000058350

I due rappresenti in virgola mobile normalizzata:

X₁ = 0,58350 · 10⁵ X’₁ = 0,58350 · 10⁵

X₂ = 0,5835 · 10^-2 X’₂ = 0,58350 · 10^-2

X̄ e X̂ hanno stessa caratteristica e mantissa uguale tranne l’ultima cifra.

E_a1 = E_a2 = 4 · 10^-5 —> l’errore assoluto è molto diverso

E_r1 = E_r2 = 7 · 10^-5 —> l’errore relativo è uguale.

La grandezza dell’errore relativo ci dice quante cifre sono accurate nel numero.

Nelle situazioni reali conosciamo X̄ e non X, quindi X̄ deve essere più accurate possibile.

CIFRE SIGNIFICATIVE

Sono le cifre sicuramente attendibili in X̄. Se X e X̄ sono espressi in virgola mobile normalizzata e :

^{|X - X̄|}/_|X| ≤ 10^-k

allora X̄ approssima X̄ con k cifre significative (certe, esatte, attendibili).

Queste cifre significative possono essere non esatte rispetto a X ma sicuramente attendibili.

La tolleranza negli strumenti è la precisione con cui lo strumento effettua misure.

-54-

Epsilon di macchina

È il piú piccolo numero positivo che sommato a 1 rende un numero diverso da 1.

1⊕εps=1

Se: 0<ε≤εps 1⊕ε≠1

Es: 0,1000₁₀⊕0,500₁₀≠0,3₁₀; 0,1001₁₀⊕0₁₀^-4 per la regola dell'errore

0,00005₁₀ ⬅ EPS

Proprietà della macchina

• ⎜(a⊙b)-(a⊗b)⎟≤εm ⎜a⊙b⎟⎜a⊙b⎟
• ⎜(a/b)-(a⊗b)⎟≤εm (a≠0 b≠0)⎜a/b⎟

valgono solo per i numeri in macchina

• si esegue il prodotto o la divisione tra le mantisse e si somma (per il prodotto) o si sottraggono (per la divisione) le caratteristiche
• si ricava il floating del risultato

Esempio: β=10, m=3, metodo del troncamento, εm=10^-2

1. 0,32₁₀ ⊙ 0,302⋅10 ¹₁₀ ⊙ 0,459⋅10 ^-10,0580₁₀⋅10^-2
2. 0,152₁₀⋅10^-1 ⊙ 0,2₁₀⋅10^-1 = 0,2₁₀⋅10^-10,165⋅10^-1₁₀ ⬅ 0,1652173⋅10^-3

In macchina a causa delle approssimazioni piú succedere che:

• a⊗b = a   onde se b≠0

La proprietá associativa non é garantita.(a⊙b)⊙c ≠ a⊙(b⊙c)

Stabilità di un algoritmo

Un algoritmo si dice stabile se restituisce risultati accurati nei limiti della precisione di macchina, altrimenti instabile.

Per esempio: per un ε=10^-16 un algoritmo é stabile se restituisce un risultato con inaccuratezza comparabile con 10^-16 indipendentemente da come si sono propagati gli errori.

La norma che propaga meno l'errore di arrotondamenti é quella infinita.

1. |g(X_k)| ≪ 1 con ε_m ≪ γ ≪ 1 con γ tolleranza ≅ 10^-3
2. |X_k+1 + X_k| ≤ |1 - μ|^k ⇒ non vale se g'(X_k) è abbastanza vicino a zero: distanza tra due iterate troppo piccola.

ALGORITMO: dati X₀, k_max e ε

Per k = 0, 1, ..., k_max

• Calcola g(X_k) e g'(X_k). Se g'(X_k) = 0 stop
• Definisci X_k+1 = X_k + g(X_k)/g'(X_k)
• Se |g(X_k+1)| ≤ ε stop oppure se |X_k+1 - X_k| ≤ ε|X_k| + γ stop

APPROSSIMAZIONI DI DATI E DI FUNZIONI

Ci approcciamo al problema di avere un insieme discreto di punti e di cercare una funzione che li approssima.

INTERPOLAZIONE:

vuol dire passare per i nodi (punti). Questo problema fu conosciuto già ai tempi di Newton. Se abbiamo da i = 0, ..., m (quindi m + 1 punti) tali che X_i, X_j se i ≠ j.

I nodi (le ascisse) sono due a due distinti.

Bisogna trovare una funzione tale che g(X_i) = Y_i ∀i tra 0 e m, per tutti i punti.

Posso applicare l'interpolazione per due situazioni:

• Y_i = g(X_i) ma la funzione g(x) è incognita, non ho la sua forma esplicita.
• Se è l'inverso: dai nodi e mi serve g(x) approssimo il valore di g(x) con g(x) dove g(x) è costruita.

g(x) ≅ g(X_i) (g è noto solo per i punti)

Conosco la forma analitica di g ma non riesco a fare un'operazione per il tipo di interesse. Sostituisco g e la approssimazione che riesco a integrare.

∫g(x)dx ≅ ∫g(X_i)dx

INTERPOLAZIONE POLINOMIALE:

sostituisco alla funzione un polinomio. Se ho m + 1 punti sui quali passa la funzione, mi cerco il polinomio di grado al più m che passa per tutti.

Trovare il polinomio di grado al più m (potrebbe essere più piccolo) tale che P_m(X_i) = Y_i con i = 0, ..., m.

Se ho due punti cerco una retta, se ne ho tre una parabola.

P_m(x) = a₀ + a₁x + a₂x² + ... + a_mx^m con:

• P_m(X₀) = Y₀
• P_m(X₁) = Y₁
• P_m(X_m) = Y_m

n + 1 condizioni e n + 1 incognite.

-15