1 Tracce di calcolo numerico

1 Tracce di calcolo numerico

(riflessioni ed esercizi contrassegnati da ^∗ e ^∗∗ sono pi` u impegnativi) aggiornamento: 6 marzo 2013

1.1 Sistema floating-point e propagazione degli errori

• si ricordi che, fissata una base (un numero naturale β > 1), ogni numero x ∈ R si pu`o scrivere (rappresentazione a virgola fissa) come

x = sign(x) (α m . . . α 1 α 0 .α −1 . . . α −n . . .) β

= sign(x)

m

X

j=0

α j β ^j +

∞

X

j=1

α −j β ^−j

!

dove α j , α −j ∈ {0, 1, . . . , β − 1} sono le cifre della rappresentazione in base β (ad esempio {0, 1} in base 2, {0, . . . , 9} in base 10); chiamiamo P n

j=0 α j β ^j parte intera del numero e P ∞

j=1 α _−j β ^−j parte frazionaria del numero

• perch´e la serie che rappresenta la parte frazionaria converge?

• la parte frazionaria di un numero razionale pu`o essere finita o infinita a seconda della base

• si mostri (con qualche esempio) che ogni numero reale si pu`o anche scrivere (rappresentazione a virgola mobile) come

x = sign(x)β ^p (0.d 1 . . . d t . . .) β = sign(x)β ^p

∞

X

j=1

d j β ^−j

d j ∈ {0, 1, . . . β − 1}, d ¹ 6= 0, dove chiamiamo P ∞

j=1 d j β ^−j mantissa e p ∈ Z esponente della rappresentazione normalizzata a virgola mobile in base β

• la mantissa di un numero reale sta in [0, 1], ma non `e la sua parte frazionaria

• i numeri irrazionali hanno parte frazionaria (e mantissa) infinita

• ∗ si dimostri, usando le serie, che l’errore di troncamento ad n cifre della parte frazionaria in base β `e ≤ β ⁻ⁿ

• si dia un’interpretazione geometrica del fatto che il massimo errore di arroton- damento ad n cifre `e la met`a del massimo errore di troncamento

• ∗∗ si dimostri, usando le serie, che l’errore di arrotondamento ad n cifre della

parte frazionaria in base β `e ≤ β ⁻ⁿ /2

• si studi l’insieme dei numeri floating-point F(β, t, L, U) = {µ ∈ Q : µ =

±(0.µ ¹ µ 2 . . . µ t )β ^p , µ j ∈ {0, 1, . . . , β − 1} , p ∈ [L, U] ⊂ Z} (traccia: deter- minare cardinalit`a, estremi, variazione di densit`a, intorni di approssimazione assoluti e relativi, precisione di macchina, ...); quali sono i reali rappresentabili (ovvero approssimabili per arrotondamento a t cifre di mantissa) tramite questi numeri floating-point?

• si disegnino F(10, 1, −1, 1) e F(10, 2, −2, 2)

• i numeri floating-point “grandi” (in modulo) sono interi e hanno moltissime cifre nulle; in un sistema floating-point con t cifre di mantissa in base β, i numeri interi con pi` u di t cifre vengono arrotondati (se rappresentabili)

• la precisione di macchina, ε ^M = β ^1−t /2, non `e il pi` u piccolo numero floating- point positivo; che cos’`e invece?

• si dimostri che vale anche ε ^M = min {µ ∈ F ⁺ : 1 + µ > 1}; quali numeri floating- point si comportano come elemento neutro nell’addizione con un dato numero floating-point µ?

• si dimostri che se un reale y approssima il reale x con un errore relativo < 10 ^−m , allora i due numeri hanno almeno m cifre decimali significative coincidenti, a meno che ... (traccia: si ragioni sulle mantisse)

• ∗ detto ε f l’errore relativo su una funzione (differenziabile) con variabili ap- prossimate, si dia una veste pi` u rigorosa alla “formula degli errori”

ε f (x) ≈ |xf ^′ (x)/f (x)| ε ^x

ε _{f (x,y)} ≈ |xf x ^′ (x, y)/f (x, y)| ε ^x + |yf y ^′ (x, y)/f (x, y)| ε ^y

partendo dal caso di funzioni di una variabile (traccia: si utilizzi il teorema del valor medio; ∗ nel caso di due variabili si assuma f di classe C ¹ in un aperto convesso)

• utilizzando la formula degli errori, si studi la stabilit`a (risposta agli errori sui dati) delle operazioni aritmetiche; in che situazioni la sottrazione fa perdere precisione?

• in Matlab si ha che ((1 + 10 ⁻¹⁵ ) − 1)/10 ⁻¹⁵ = 1.110223024625157, ma invece ((1 + 2 ⁻⁵⁰ ) − 1)/2 ⁻⁵⁰ = 1, dove 2 ⁻⁵⁰ ≈ 10 ⁻¹⁵ ; perch´e?

• si facciano esempi in cui la propriet`a associativa non `e valida in aritmetica di macchina per overflow oppure per effetto dell’arrotondamento

• la formula risolutiva classica per le equazioni di secondo grado perde precisione

in aritmetica di macchina se b ² ≫ 4|ac| oppure b ² ≈ 4ac: perch´e? si quantifichi

la perdita di precisione nei due casi e si discutano possibili rimedi (traccia

nel secondo caso ∗∗: quanta precisione si perderebbe approssimando con la

soluzione doppia −b/(2a)? ...)

• ∗ si trovino esempi di funzioni “instabili”, cio`e tali che per certi punti (x, y) si ha ε _{f (x,y)} ≫ max {ε ^x , ε y } qualunque sia la rappresentazione di f, e di funzioni

“stabili” per cui l’instabilit`a nel calcolo dipende dalla rappresentazione (iniziare da una variabile)

• riscrivere, se necessario, le seguenti espressioni per ovviare a possibili instabilit`a in aritmetica di macchina:

E ₁ (x) = x ⁵ /(2 + x ⁴ + 0.1|x|) − x + 100(x ⁴ + 5) ^1/4 E 2 (x) = √

x ² + 1 − |x| + 100x E 3 (x) = 3 √

x ⁴ + 2 − (10x ⁷ + 1)/(x ⁵ + 1) + 10x ²

• ∗ la formula di ricorrenza in avanti I ⁿ = 1−nI ⁿ⁻¹ , n = 1, 2, . . ., I 0 = 1−e ⁻¹ , sod- disfatta da I n = e ⁻¹ R 1

0 x ⁿ e ^x dx, `e fortemente instabile in aritmetica di macchina (perch´e?), ma pu`o essere stabilizzata usandola all’indietro; si dimostrino con- vergenza e stabilit`a della formula all’indietro analizzando l’errore relativo

1.2 Complessit` a degli algoritmi numerici

• si dimostri che la complessit`a della formula di Laplace per il calcolo di un determinante `e almeno n! flops

• si dimostri che la complessit`a asintotica del metodo di eliminazione gaussiana `e 2n ³ /3 flops (traccia: si incastri la complessit`a tra due integrali)

• perch´e il calcolo di exp (x) (per x > 1) usando la formula exp (x) = (exp (x/m)) ^m , m > [x] e la formula di Taylor per exp (x/m), `e pi` u efficiente dell’utilizzo diretto della formula di Taylor? (si ricordi che esiste un algoritmo veloce per il calcolo di una potenza tramite codifica binaria dell’esponente, basato sulla propriet`a a ⁿ = a ^{P c}

²

= Q a ^c

²

, dove {c ^j } sono le cifre della codifica binaria di n ∈ N)

1.3 Soluzione numerica di equazioni non lineari

• data una successione {x ⁿ } tale che lim ^n→∞ x n = ξ dove f (ξ) = 0, perch´e in generale il “residuo” |f(x ⁿ )| non `e una buona stima dell’errore? (si faccia un disegno sul possibile andamento locale di f , se il grafico `e “piatto” ...) come va corretto il residuo? (traccia: assumendo f derivabile in un intorno di ξ, si utilizzi il teorema del valor medio, f (x n ) − f(ξ) = . . .)

• detto e n l’errore assoluto del metodo di Newton per f (x) = 0, in ipotesi di

convergenza e per f ∈ C ² (I), dove I `e un intervallo chiuso e limitato contenente

la radice in cui f ^′ (x) 6= 0, si dimostri la disuguaglianza e ⁿ⁺¹ ≤ Ce ² n con C

costante opportuna (traccia: utilizzare la formula di Taylor calcolata nella radice

e centrata in x n , insieme alla definizione della successione del metodo, ...)

approfondimento ∗: partendo da tale disuguaglianza, si arrivi ad enunciare e

dimostrare un risultato di convergenza locale

• si giustifichi il fatto che nel calcolo di √

2 risolvendo l’equazione x ² − 2 = 0 nell’intervallo (1, 2), il metodo di bisezione guadagna in media 1 cifra decimale significativa ogni 3-4 iterazioni, mentre il metodo di Newton raddoppia il numero di cifre significative ad ogni iterazione; questo comportamento vale in generale per entrambi i metodi? (traccia: si ragioni sull’errore relativo)

• si dimostri che in ipotesi di convergenza il numero di iterazioni che garantiscono un errore assoluto ≤ ε (dove ε `e una tolleranza) `e n ≥ c 1 log (ε ⁻¹ ) + c ₂ per il metodo di bisezione e n ≥ c ³ log (log (ε ⁻¹ )) + c 4 per il metodo di Newton, dove c 1 , c 2 , c 3 , c 4 sono opportune costanti

• perch´e la quantit`a |x n+1 − x n | `e una buona stima dell’errore assoluto |x n − ξ|

per il metodo di Newton (almeno per n abbastanza grande)?

• si studino numericamente le seguenti equazioni “storiche”:

• x ³ − 2x − 5 = 0 (su questa equazione Newton illustr`o il suo metodo)

• m = x−E sin x (equazione di Keplero: m `e l’anomalia media di un pianeta, E l’eccentricit`a della sua orbita; si assuma ad esempio m = 0.8, E = 0.2) (traccia: isolare gli zeri anche graficamente, verificare l’applicabilit`a dei metodi di bisezione e di Newton, ...)

• se si applica il metodo di Newton con x ⁰ 6= 0 all’equazione sign(x)|x| ^1/2 = 0 si ottiene una successione “stazionaria”, mentre per sign(x)|x| ^1/3 = 0 la succes- sione `e addirittura divergente; dove sta il problema?

• ∗∗ abbiamo visto che il metodo di Newton converge globalmente se f ∈ C ² [a, b], f (a)f (b) < 0, f ^′′ (x) > 0 oppure f ^′′ (x) < 0 in [a, b] e f (x 0 )f ^′′ (x 0 ) > 0. Si dimostri che il metodo converge anche nelle eseguenti ipotesi, per qualsiasi scelta di x 0 ∈ [a, b]: f ∈ C ² [a, b], f (a)f (b) < 0, f ^′ (x) 6= 0 e f ^′′ (x) ≥ 0 oppure f ^′′ (x) ≤ 0 in [a, b], |f(a)/f ^′ (a)| < b − a e |f(b)/f ^′ (b)| < b − a (traccia: ci sono quattro situazioni geometriche possibili, dove pu`o cadere la prima iterata x ₁ ? ...)

• si studi la soluzione delle equazioni x − e ^−x/5 = 0 e x − e ^−x = 0 con le iterazioni di punto fisso (∗∗ per la seconda si isoli la soluzione col teorema degli zeri per applicare un risultato di convergenza locale)

• perch´e il metodo di Newton si pu`o interpretare come iterazione di punto fisso?

quando ci si aspetta ordine di convergenza p > 2? (traccia: si ricordi che un’iterazione di punto fisso ha ordine di convergenza p se e solo se ...)

1.4 Interpolazione e approssimazione di dati e funzioni

• qual’`e la forma di Lagrange del polinomio interpolatore di grado n su n+1 nodi

distinti?

• ∗ perch´e nell’interpolazione polinomiale (e pi`u in generale nell’interpolazione in qualsiasi sottospazio funzionale di dimensione finita) esistenza per ogni vettore di valori campionati nei nodi ed unicit`a sono equivalenti?

• ∗ si ricavi la forma di Lagrange dell’errore di interpolazione di grado n per f ∈ C ⁿ⁺¹ [a, b] (si noti l’analogia con il resto della formula di Taylor), E n (x) = f (x) − Π ⁿ (x) = f ⁽ⁿ⁺¹⁾ (η) ω(x)/(n + 1)!, dove ω(x) = (x − x ⁰ ) . . . (x − x ⁿ ), η ∈ int(x, x 0 , . . . , x _n ) (traccia: si utilizzi la funzione ausiliaria G(u) = E _n (u) − ω(u)(E n (x)/ω(x)) e si applichi ripetutamente il teorema di Rolle)

• ∗ partendo dalla forma di Lagrange dell’errore di interpolazione polinomiale di grado n per f ∈ C ⁿ⁺¹ [a, b], si dimostri che il massimo errore nel caso di nodi equispaziati `e ≤ max x∈[a,b] {|f ⁽ⁿ⁺¹⁾ (x)|} h ⁿ⁺¹ /(4(n + 1)) dove h = (b − a)/n;

perch´e da questa stima non si pu`o dedurre la convergenza per f ∈ C ^∞ [a, b]?

(vedi controesempio di Runge, f (x) = 1/(1 + x ² ), x ∈ [−5, 5])

• si dimostri che l’interpolazione lineare a tratti converge uniformemente per f ∈ C ² [a, b] con un errore O(h ² ), dove h = max i ∆x i (∗∗ si provi che c’`e convergenza anche per f ∈ C[a, b], utilizzando l’uniforme continuit`a)

• si dimostri che l’interpolazione quadratica a tratti converge uniformemente per f ∈ C ³ [a, b] con un errore O(h ³ ), dove h = max i ∆x i ; c’`e qualche vincolo sul numero di nodi? si utilizzi poi la stima trovata per decidere a priori quanti nodi usare nell’interpolazione quadratica a passo costante di f (x) = sin x in [0, π]

per avere un errore < 10 ⁻⁸ (traccia: si utilizzi localmente la stima dell’errore di interpolazione polinomiale a passo costante)

• ∗ si mostri che la “risposta alle perturbazioni” su f dell’interpolazione polino- miale `e legata alla quantit`a Λ n = max x∈[a,b] P n

i=0 |ℓ ⁱ (x)| (costante di Lebesgue), dove gli {ℓ ⁱ } sono i polinomi elementari di Lagrange

• l’interpolazione spline cubica pu`o essere usate per approssimare integrali e derivate di una funzione campionata? (sugg.: si ricordi la stima dell’errore in norma infinito per f ∈ C ⁴ [a, b])

• si dimostri che le seguenti affermazioni riguardo una formula di quadratura P n

i=0 w i f (x i ) ≈ R b

a f (x) dx, {x ⁱ } nodi distinti in [a, b], sono equivalenti:

• la formula `e “interpolatoria” (cio`e ottenuta integrando il polinomio inter- polatore sui nodi)

• w ⁱ = R b

a ℓ i (x) dx, i = 0, . . . , n

• la formula `e esatta sui polinomi di grado ≤ n

• ∗ si dimostri che, per f ∈ C ^s+1 [a, b], le formule di quadratura “composte”

ottenute integrando un’interpolante polinomiale a tratti di grado locale fissato

s costruita su un campionamento {(x ⁱ , f (x i ))}, i = 0, . . . , n, sono convergenti

con un errore che `e almeno O(h <sup>s+1</sup> ), dove h = max ∆x i (c’`e qualche vincolo sul

numero di nodi?)

• ∗ si verifichi che, come le formule interpolatorie, le formule di quadratura com- poste hanno tutte la forma di somma pesata P n

i=0 w i f (x i ), dove i {w ⁱ } sono opportuni pesi (traccia: tali formule sono localmente “interpolatorie”, cio`e ot- tenute integrando un singolo polinomio interpolatore di grado s in [x ks , x (k+1)s ], k = 0, . . . , (n : s) − 1)

• si ricavi la formula di quadratura composta di grado 2, detta di Cavalieri- Simpson (o delle parabole), nel caso di campionamento a passo costante

• data una formula di approssimazione φ(h) di una quantit`a φ ⁰ , con la struttura φ(h) = φ 0 + ch ^p + O(h ^q ), q > p > 0, utilizzando opportune combinazioni lineari di φ(h) e φ(h/2) si ricavino:

• una stima a posteriori della parte principale dell’errore

• una nuova approssimazione con errore di ordine O(h ^q ) (estrapolazione) approfondimento ∗∗: come si potrebbe iterare il procedimento di estrapolazione per φ(h) = φ ₀ +c ₁ h ^p

+c ₂ h ^p

+. . .+c _m h ^p

+O(h ^q ), 0 < p ₁ < p ₂ < . . . < p _m < q?

(traccia: si utilizzi una sequenza di passi h, h/2, h/4, . . .)

• si verifichi che il rapporto incrementale standard δ ⁺ (h) = (f (x + h) − f(x))/h e quello “simmetrico” δ(h) = (f (x + h) − f(x − h))/(2h) hanno la struttura dell’esercizio precedente per f sufficientemente regolare (traccia: si utilizzi la formula di Taylor; in particolare, chi `e q per δ(h) con f ∈ C ⁵ )? si applichi l’esercizio precedente a vari esempi, controllando l’accuratezza delle approssi- mazioni e delle stime dell’errore

• perch´e nella derivazione numerica con δ ⁺ (h) conviene prendere un passo dell’ordine di √

ε, dove ε `e il massimo errore su f ? e nel caso si usi δ(h)?

• si rifletta sull’instabilit`a intrinseca dell’operazione funzionale di derivazione (fare un esempio) e sul fatto che l’operazione di integrazione invece `e stabile; perch`e l’effetto dell’instabilit`a viene mitigato usando formule di derivazione numerica con errore di ordine maggiore? ad es. con δ(h) invece di δ + (h), oppure appli- cando l’estrapolazione

• ∗ gli esercizi precedenti mostrano che, in presenza di rumore, per calcolare la derivata `e ragionevole non utilizzare tutti i dati di un campionamento fitto, ma campionare con un passo ottimale: individuare un criterio pratico per la determinazione di tale passo nel caso di δ + (h), utilizzando un’approssimazione ai minimi quadrati

• detta T (h) la formula di quadratura composta dei trapezi a passo costante e sapendo che T (h) = R b

a f (x) dx + ch ² + O(h ⁴ ) per f ∈ C ⁴ [a, b], si calcolino stima

a posteriori dell’errore e formula di estrapolazione su vari esempi di funzioni

integrabili elementarmente, confrontando con l’errore effettivo

• ∗∗ abbiamo visto che la “risposta alle perturbazioni” su f dell’interpolazione polinomiale `e legata alla quantit`a Λ n = max _x∈[a,b] P n

i=0 |ℓ ⁱ (x)| (costante di Lebesgue), dove gli {ℓ ⁱ } sono i polinomi elementari di Lagrange; quale quantit`a potrebbe svolgere un ruolo analogo nel caso delle formule di quadratura inter- polatorie e composte, e perch´e in particolare le formule con pesi positivi sono sicuramente stabili? (traccia: si utilizzi il fatto che le formule interpolatorie e composte danno risultato esatto sulle funzioni costanti)

1.5 Algebra lineare numerica

• ∗ teorema fondamentale di invertibilit`a: data una norma matriciale in C <sup>m×m</sup> tale che kABk ≤ kAk kBk (come sono tutte le norme indotte da norme vettoriali, ovvero kAk = sup x6=0 kAxk/kxk = sup kxk=1 kAxk), se kAk < 1 allora I − A `e invertibile e si ha

(I − A) ⁻¹ =

∞

X

j=0

A ^j , k(I − A) ⁻¹ k ≤ 1 1 − kAk (sugg.: k P n

j=m A ^j k ≤ P n

j=m kAk ^j e la serie geometrica P kAk ^j `e convergente e quindi di Cauchy, ... ; nel caso kAk sia indotta da una norma vettoriale, la dimostrazione di invertibilit`a e la stima si possono fare in modo pi` u diretto osservando che k(I − A)xk ≥ kxk − kAxk > 0, ..., e detta S = (I − A) ⁻¹ si ha 1 = kS(I − A)k ≥ kSk − kASk ≥ ...)

• ∗ si verifichi che kAk = max ^i,j |a ^ij | `e una norma matriciale in C ^m×m ma non soddisfa la disuguaglianza kABk ≤ kAk kBk per ogni coppia di matrici

• ∗ stime di condizionamento: dato il sistema quadrato Ax = b con det(A) 6= 0 e il sistema perturbato (A + δA)(x + δx) = b + δb, se kk(A)k kδAk < kAk (dove k(A) = kAk kA ⁻¹ k `e l’indice di condizionamento della matrice in una norma matriciale indotta da una norma vettoriale), vale la stima

kδxk

kxk ≤ k(A)

1 − k(A)kδAk/kAk

 kδAk

kAk + kδbk kbk



(sugg.: partendo da (A + δA)δx = δb − δAx e osservando che (A + δA) = A(I + A ⁻¹ δA) dove kA ⁻¹ δAk ≤ kA ⁻¹ k kδAk < 1, ...)

• localizzazione rozza degli autovalori: data una norma matriciale indotta, gli autovalori di A ∈ C ^m×m stanno in C[0, kAk] (il cerchio complesso chiuso di centro 0 e raggio kAk)

(sugg.: se λ ∈ C, |λ| > kAk, scrivendo (λI − A) = λ(I − A/λ), ...)

• si dimostri, utilizzando il risultato precedente, che k(A) ≥ |λ ^max |/|λ ^min | con

qualsiasi norma matriciale indotta, dove λ max e λ min sono gli autovalori di

modulo massimo e minimo della matrice invertibile A. Si mostri anche che

vale l’uguaglianza per k 2 (A) con A simmetrica

(sugg.: si ricordi che gli autovalori dell’inversa sono i reciproci degli autovalori di A, ...; nel caso simmetrico, si osservi che kAk ² = |λ ^max |, ...)

• quali sono gli scopi del pivoting nel metodo di eliminazione gaussiana? (si pensi al caso in cui un elemento diagonale diventa nullo, oppure molto piccolo in modulo)

• si calcoli la complessit`a computazionale della soluzione di un sistema con matrice triangolare

• come si pu`o utilizzare la fattorizzazione P A = LU fornita dal metodo di elimi- nazione con pivoting per righe, per calcolare l’inversa di una matrice?

(sugg.: le colonne di una matrice si ottengono moltiplicando la matrice per i vettori coordinati, quindi le colonne di A ⁻¹ corrispondono alle soluzioni dei sistemi ...)

• sia A ∈ R ^m×n , m > n, una matrice di rango massimo: si mostri che calcolare la soluzione ai minimi quadrati del sistema sovradeterminato Ax = b `e equivalente a risolvere il sistema con matrice simmetrica definita positiva A ^t Ax = A ^t b (detto

“sistema delle equazioni normali”); nel caso dell’approssimazione polinomiale ai minimi quadrati (in una variabile), chi `e la matrice A? e perch´e ha rango massimo?

(sugg.: si osservi che x minimizza il polinomio quadratico φ(x) = kAx−bk ² 2 se e solo se per ogni v ∈ R ⁿ si ha φ(x) ≤ φ(x+v) ovvero 2v ^t A ^t (Ax−b)+v ^t A ^t Av ≥ 0, ...; nel caso polinomiale, si ricordi che una matrice quadrata di Vandermonde corrispondente a nodi distinti `e non singolare, ...)

• sia A ∈ R ^m×n , m ≥ n, una matrice di rango massimo: allora si pu`o dimostrare (non richiesto) che A ammette una fattorizzazione A = QR, dove Q ∈ R <sup>m×n</sup> `e una matrice ortogonale (ovvero le colonne di Q sono vettori ortonormali, Q ^t Q = I) e R `e una matrice triangolare superiore non singolare (si tratta in sostanza di un procedimento equivalente all’ortogonalizzazione di Gram-Schmidt delle colonne di A: la matrice R <sup>−1</sup> , che resta triangolare superiore, `e la matrice dei coefficienti dell’ortogonalizzazione)

• come si pu`o applicare la fattorizzazione QR alla soluzione di sistemi sovrade- terminati?

(sugg.: utilizzando A = QR, non `e necessario calcolare la matrice A ^t A perch´e

A ^t A = R ^t R, ...)