1 Tracce di calcolo numerico

(1)

Lauree scientifiche (Astronomia, Matematica)

Prof. Marco Vianello - Dipartimento di Matematica, Universit`a di Padova aggiornamento: 13 aprile 2015 (sulle costanti di Lebesgue)

testo di approfondimento: G. Rodriguez, Algoritmi numerici, Pitagora, Bologna, 2008 argomenti e quesiti contrassegnati da ^∗ sono pi`u impegnativi, se non si `e in grado di fare la dimostrazione bisogna comunque sapere (e saper usare) gli enunciati e capire di cosa si sta parlando; quelli contrassegnati da ^∗∗ sono approfondimenti difficili e facoltativi

1.1 Sistema floating-point e propagazione degli errori

1. 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); chiamiamoPn

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

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

2. perch´e la serie che rappresenta la parte frazionaria converge? si osservi che la parte frazionaria sta in [0, 1]

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

4. si mostri (con qualche esempio) che ogni numero reale diverso da zero si pu`o anche scrivere (rappresentazione normalizzata a virgola mobile) come

x = sign(x)β^p(0.d₁. . . d_t. . .)_β = sign(x)β^p

∞

X

j=1

d_jβ^−j

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

j=1djβ^−j mantissa e p ∈ Z esponentedella rappresentazione normalizzata a virgola mobile in base β; a cosa serve la normalizzazione d1 6= 0?

5. la mantissa di un numero reale sta in [0, 1], ma non `e la sua parte frazionaria 6. i numeri irrazionali hanno parte frazionaria (e mantissa) infinita

(2)

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

8. si dia un’interpretazione geometrica (con un disegno) del fatto che il massimo errore di arrotondamento ad n cifre è la metà del massimo errore di troncamento (∗∗ è possibile dare una dimostrazione rigorosa di questo fatto utilizzando la serie che rappresenta la parte frazionaria)

9. 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: determinare 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?

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

11. 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)

12. la precisione di macchina, εM = β^1−t/2, non è il più piccolo numero floating- point positivo; che cos’è invece?

13. si discuta un modello di codifica dei reali in base 2 con una sequenza di 64 bit, la cosiddetta “precisione doppia” (traccia: riservando un bit per i segno, 52 (+1) bit per la mantissa che `e come avere 53 bit perch´e la prima cifra di mantissa deve essere 1, e 11 bit per l’esponente, ...)

14. in un’aritmetica a base 10 con 16 cifre di mantissa, 1 + 10⁻¹⁵ viene calcolato correttamente ma 1 + 10⁻¹⁶ = 1; perché? (si osservi che questo è un esempio di non unicità dell’elemento neutro)

15. ∗∗ 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 µ?

16. detti εx= |x− ˜x|/|x| e ε^y = |y− ˜y|/|y|, x, y 6= 0, gli errori relativi sui dati si studi la stabilit`a delle operazioni aritmetiche con numeri approssimati, mostrando che per ciascuna operazione aritmetica ⋆ si ha una stima del tipo “somma pesata degli errori”

ε_x⋆y = |(x ⋆ y) − (˜x ⋆ ˜y)|

|x ⋆ y| ≤ w1(x, y)ε_x+ w₂(x, y)ε_y, , x ⋆ y 6= 0 ,

calcolando w1, w2nei vari casi (moltiplicazione, divisione, addizione, sottrazione;

traccia: si utilizzi la disuguaglianza triangolare); quali operazioni si possono considerare “stabili”? in quali situazioni la sottrazione fa perdere precisione? si

(3)

17. detto εf l’errore relativo su una funzione (differenziabile) con variabili approssi- mate, si ricavi la “formula degli errori”

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

εf (x,y)≈ |(xfx^′(x, y)/f (x, y)) ∆x/x + (yf_y^′(x, y)/f (x, y)) ∆y/y|

≤ |xfx^′(x, y)/f (x, y)| ε^x+ |yfy^′(x, y)/f (x, y)| ε^y

partendo dal caso di funzioni di una variabile (traccia: si utilizzi la formula di Taylor; ∗∗ per dare una veste pi`u rigorosa alla stima si utilizzi il teorema del valor medio e nel caso di due variabili si assuma f di classe C¹ in un aperto convesso)

18. utilizzando la formula degli errori, si studi la stabilit`a (risposta agli errori sui dati) delle operazioni aritmetiche

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

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

21. la formula risolutiva classica per le equazioni di secondo grado ax²+ bx + c = 0, a 6= 0, ∆ = b² − 4ac > 0, perde precisione in aritmetica di macchina se b² ≫ 4|ac|; si quantifichi la perdita di precisione calcolando i pesi della sottrazione corrispondente e si ricavi una formula “stabilizzata” (traccia: per la stabilizzazione, si osservi ad esempio che per b > 0,√

∆−b = (√

∆−b)(√

∆+b)/(√

∆+b) = ...) 22. ∗ si trovino esempi di funzioni “instabili”, cio`e tali che per certi punti x si ha ε_{f (x)} ≫ ε^x qualunque sia la rappresentazione di f , e di funzioni “stabili” per cui l’instabilit`a nel calcolo dipende dalla rappresentazione

23. si riscrivano, se necessario, le seguenti espressioni per ovviare a possibili instabilit`a in aritmetica di macchina:

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

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

x⁴ + 2 − (10x⁷ + 1)/(x⁵+ 1) + 10x² 24. la successione definita da x₂ = 2, x_n+1 = 2^n−1/2q

1 −p1 − 4¹⁻ⁿx²_n, n = 2, 3, . . ., soddisfa lim_n→∞x_n= π, ma se usata per approssimare π diventa instabile in aritmetica di macchina (qual’`e la sottrazione che fa perdere precisione?

si calcolino i fattori di amplificazione dell’errore in funzione di n); come pu`o essere stabilizzata?

25. ∗ la formula di ricorrenza in avanti Iⁿ = 1 − nIⁿ⁻¹, n = 1, 2, . . ., I0 = 1 − e⁻¹, soddisfatta da In = e⁻¹R1

0 xⁿe^xdx, è fortemente instabile in aritmetica di macchina (perché?), ma può essere stabilizzata usandola all’indietro; ∗∗ si dimostrino convergenza e stabilità della formula all’indietro analizzando l’errore relativo

(4)

1.2 Costo computazionale degli algoritmi numerici

1. si discuta l’algoritmo di H¨orner per il calcolo dei valori di un polinomio

2. esiste un algoritmo veloce per il calcolo di una potenza tramite codifica binaria dell’esponente, basato sulla proprietà aⁿ = a^P^c^j²^j = Q a^c^j²^j, dove {c^j} sono le cifre della codifica binaria di n ∈ N; qual’è il costo computazionale (come numero di operazioni aritmetiche floating-point) in funzione di n? qual’è il costo nel caso l’algoritmo venga applicato al calcolo di una potenza di matrice?

3. ∗ perché 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), è più efficiente dell’utilizzo diretto della formula di Taylor?

(traccia: si stimi il modulo del resto della formula di Taylor di exp (x) per

|x| ≤ 1 e per |x| > 1; qual’ `e il comportamento per n → ∞?)

4. il metodo di eliminazione gaussiana pu`o essere usato per calcolare il determi- nante di una matrice quadrata (come?), con costo computazionale O(n³) flops (da confrontare con il costo O(n!) flops della regola di Laplace, che la rende inutilizzabile gi`a per valori relativamente piccoli di n)

5. ∗ si dimostri che il costo computazionale asintotico del metodo di eliminazione gaussiana `e 2n³/3 flops (traccia: si incastri il costo tra due integrali)

1.3 Soluzione numerica di equazioni non lineari

1. data una funzione f ∈ C[a, b] (ovvero, f `e continua in [a, b]), tale che f(a)f(b) <

0, si dimostri che la successione x0, x1, . . . , xn, . . ., costruita col metodo di bisezione (utilizzando iterativamente il teorema degli zeri) soddisfa la stima a priori dell’

errore

en= |ξ − xⁿ| ≤ b − a

2ⁿ⁺¹ , n = 0, 1, 2, . . .

dove ξ `e uno zero di f in (a, b); si diano ipotesi su f che garantiscono l’unicit`a dello zero

2. data una funzione continua f tale che f (ξ) = 0 e successione {xⁿ} tale che limn→∞xn = ξ, 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 con derivata continua e non nulla in [c, d], dove xn ∈ [c, d] almeno per n abbastanza grande, si utilizzi il teorema del valor medio, f (xn)−f(ξ) = . . . ; si osservi che per la permanenza del segno la derivata

`e sicuramente non nulla in un intorno [c, d] di uno zero semplice, ovvero ξ tale che f^′(ξ) 6= 0)

(5)

3. utilizzando i risultati dell’esercizio precedente, si discuta la seguente stima a posterioridell’errore (con correzione del residuo)

en= |ξ − xⁿ| ≈ |f(xⁿ)|

xn− xⁿ⁻¹ f (xn) − f(xⁿ⁻¹)

4. si dia un’interpretazione geometrica del metodo di Newton

xn+1 = xn− f (xn)

f^′(xn) , f^′(xn) 6= 0 , n = 0, 1, 2, . . .

5. un risultato di convergenza globale del metodo di Newton: sia f ∈ C²[a, b], f (a)f (b) < 0, f^′′ di segno costante in (a, b); scelto x0 tale che f (x0)f^′′(x0) < 0, il metodo di Newton `e ben definito e convergente all’unico zero di f in [a, b]

(traccia: le tangenti alla curva grafico stanno sempre sopra o sotto la curva, quindi la successione {xn} `e monotona e limitata, ...)

6. detto en = |ξ − xⁿ| l’errore assoluto del metodo di Newton per f(x) = 0, in ipotesi di convergenza e per f ∈ C²(I), dove I ⊃ {xn} `e un intervallo chiuso e limitato 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 di {xⁿ}, ...)

approfondimento∗: partendo da tale disuguaglianza, perch`e ci si aspetta convergenza locale? ∗∗ si enunci e dimostri rigorosamente un risultato di convergenza locale

7. 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, ρn = en/|ξ|; col metodo di Newton ρ_n+1 ≤ C|ξ|ρ²n, ...)

8. si mostri che il metodo di Newton per il calcolo di a^1/k, a > 0, assume la forma xn+1 = k − 1

k xn+ a

kx^k−1_n , n = 0, 1, 2, . . .

(gi`a nota in antichit`a come metodo di Erone nel caso della radice quadrata), dove x0 va scelto tale che x^k₀ > a

9. un metodo convergente ha ordine di convergenza almeno p ≥ 1 se esiste C > 0 tale che

en+1≤ Ce^pn

(6)

e ordine esattamente p se vale

n→∞lim en+1

e^pn = L 6= 0 ;

quindi il metodo di Newton nel caso di uno zero semplice ha ordine almeno 2;

quando ha ordine esattamente 2, e quando maggiore di 2?

∗ per p = 1 si osservi in generale che necessariamente L ≤ 1 e che L < 1 oppure C < 1 sono condizioni sufficienti per la convergenza

10. ∗ si dimostri che se un metodo ha ordine di convergenza almeno p > 1 vale la stima

C^p−1¹ eν+k≤

C^p−1¹ eν

p^k

, ν ≥ 0 , k ≥ 0 (traccia: si dimostri che eν+k ≤ C C^pC^p². . . C^p^k−1e^p_ν^k = . . . )

11. si dimostri che in ipotesi di convergenza il numero di iterazioni che garantiscono un errore assoluto ≤ ε (dove ε `e una tolleranza) `e n ≥ c¹log (ε⁻¹) + c2 per il metodo di bisezione e n ≥ c³log (log (ε⁻¹)) + c4 per il metodo di Newton, dove c1, c2, c3, c4 sono opportune costanti

12. perché la quantità |xⁿ⁺¹ − xⁿ| (detta “step”) è una buona stima dell’errore assoluto per il metodo di Newton (almeno per n abbastanza grande)?

13. data una stima sndell’errore di un metodo iterativo convergente, en≤ sⁿoppure e_n ≈ sn, si discuta il significato di un test di arresto delle iterazioni del tipo sn ≤ |xⁿ|ε^r+ εa, dove εa`e una tolleranza assoluta ed εr una tolleranza relativa 14. si verifichi l’applicabilit`a dei metodi di bisezione e di Newton all’equazione

x − e^−x/5 = 0

15. 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, x l’anomalia eccentrica; 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, ...)

16. 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 successione `e addirittura divergente; dove sta il problema?

(7)

17. un risultato di convergenza delle iterazioni di punto fisso: sia φ : I → R derivabile nell’intervallo chiuso I ⊆ R, con (i): φ(I) ⊆ I, e (ii): |φ^′(x)| ≤ θ < 1 per ogni x ∈ I; scelto un qualsiasi x⁰ ∈ I, la successione xⁿ⁺¹ = φ(xn), n = 0, 1, 2, . . ., converge all’unico punto fisso di φ in I (si faccia vedere usando (ii) e il teorema del valor medio che φ “contrae le distanze” e che il punto fisso `e unico in I; si osservi anche che I pu`o essere non limitato, ovvero una semiretta chiusa o anche tutta la retta)

(∗∗ traccia della dimostrazione: si provi che valgono le disuguaglianze |x^n+p− xn| ≤ (1 + θ + θ²+ . . . + θ^p−1)|xⁿ⁺¹− xⁿ| ≤ (θⁿ/(1 − θ))|x¹− x⁰|, da cui si vede che la successione {xⁿ} `e di Cauchy, ...)

18. corollario (convergenza locale): sia ξ punto fisso di una funzione φ di classe C¹ in un intorno di ξ, con |φ^′(ξ)| < 1; allora la successione delle iterazioni di punto fisso converge a ξ a partire da qualsiasi x₀ in un intorno opportuno di ξ

(∗ traccia: detto I = [ξ − δ, ξ + δ] un intorno chiuso di ξ in cui |φ^′(x)| < 1, che esiste per la permanenza del segno, si applichi il risultato precedente mostrando che φ(I) ⊆ I; chi `e θ?)

19. in ipotesi di convergenza, per le iterazioni di punto fisso valgono le stime di errore

|xⁿ− ξ| ≤ θⁿ|x⁰− ξ| (a priori)

|xⁿ− ξ| = |xⁿ⁺¹− xⁿ|

1 − φ^′(zn) ≤ 1

1 − θ|xⁿ⁺¹− xⁿ| (a posteriori)

dove zn ∈ int(xⁿ, ξ); quando ha senso usare il solo step |xⁿ⁺¹− xⁿ| come stima a posteriori dell’errore?

(traccia: per la prima si osservi che |xⁿ⁺¹− ξ| = |φ(xⁿ) − φ(ξ)| = |φ^′(zn)| |xⁿ− ξ| ≤ . . .; per la seconda si osservi che xⁿ⁺¹ − xⁿ = xn+1 − ξ + ξ − xⁿ = φ^′(zn)(xn− ξ) + ξ − xⁿ, ...)

20. si studi la soluzione delle equazioni x = e^−x/5 e x = e^−x con le iterazioni di punto fisso (∗∗ per la seconda si isoli la soluzione col teorema degli zeri per applicare un risultato di convergenza locale); con la prima equazione, quante iterazioni occorrono per garantire un errore assoluto < 10⁻⁸?

21. ordine di convergenza delle iterazioni di punto fisso: si dimostri che un’iterazione di punto fisso xn+1 = φ(xn), con φ ∈ C^p in un intorno di ξ, ha ordine 1 se e solo se φ^′(ξ) 6= 0, e ha ordine p > 1 se e solo se φ^(p)(ξ) 6= 0 e φ^(j)(ξ) = 0, j = 1, . . . , p − 1

22. 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 osservi che il metodo di Newton corrisponde a xn+1 = φ(xn) con φ(x) = . . . )

23. ∗ dato il sistema non lineare f(x) = 0, dove f : (Ω ⊆ R^m) → R^m `e un campo vettoriale differenziabile definito su un aperto Ω contenente ξ tale che f (ξ) = 0,

(8)

il metodo di Newton corrisponde alla linearizzazione iterativa f (xn) + Jn(x − xⁿ) = 0 , n ≥ 0

a partire da un opportuno vettore iniziale x0, dove Jn = Jf (xn) `e la matrice Jacobiana (purch´e x_n∈ Ω e Jn sia invertibile ad ogni iterazione), ovvero

xn+1 = xn− Jn⁻¹f (xn) , n ≥ 0 ;

in pratica, il metodo viene implementato risolvendo un sistema lineare ad ogni iterazione, J_nv_n = −f(xn), x_n+1 = x_n+ v_n; si dimostra (non richiesto) che vale un risultato di convergenza locale

1.4 Interpolazione e approssimazione di dati e funzioni

1. problema algebrico dell’interpolazione (costruzione): dati n+1 punti (xi, f (xi)), i = 0, . . . , n, sul grafico di una funzione f : [a, b] → R, determinare se esiste ed

`e unica una funzione f_n in una opportuna famiglia di funzioni Fn, tale che fn(xi) = f (xi) , i = 0, . . . , n

(nel caso di Fⁿ= Pn, lo spazio vettoriale dei polinomi di grado ≤ n, si parla di interpolazione polinomiale, e chiameremo Π_n(x) = f_n(x) il polinomio interpolatore)

2. problema analitico dell’interpolazione (convergenza): per quali scelte dei nodi {xi} e in quali ipotesi su f si ha convergenza uniforme degli interpolatori, cio`e

x∈[a,b]max |fⁿ(x) − f(x)| → 0 , n → ∞ ?

3. perch´e il polinomio interpolatore Πn(x) di grado ≤ n di una funzione f su n + 1 nodi distinti {x⁰, x1, . . . , xn} `e unico?

4. si mostri che

Πn(x) =

n

X

i=0

f (xi) ℓi(x) , ℓi(x) = Q

k6=i(x − x^k) Q

k6=i(x_i− xk)

`e il polinomio interpolatore su n + 1 nodi distinti {x⁰, x1, . . . , xn} (si tratta della coiddetta “forma di Lagrange” del polinomio interpolatore)

5. il problema di interpolazione polinomiale di grado n su n+1 nodi `e equivalente al sistema lineare V a = y, dove V = (v_ij) = (x^j_i), 0 ≤ i, j ≤ n `e detta “matrice di Vandermonde” dei nodi di interpolazione, a = (a0, . . . , an)^t e y = (y0, . . . , yn)^t, yi= f (xi)

(9)

6. ∗ perch´e nell’interpolazione polinomiale esistenza per ogni vettore di valori cam- pionati nei nodi ed unicit`a sono equivalenti?

(traccia: il problema è equivalente ad un sistema lineare con matrice V , l’unicità significa che l’applicazione lineare associata a V è iniettiva cioè il nucleo di V è il vettore nullo, ...)

7. ∗ 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)

En(x) = f (x) − Πⁿ(x) = f⁽ⁿ⁺¹⁾(η)

(n + 1)! (x − x⁰) . . . (x − xⁿ) dove η ∈ int(x, x⁰, . . . , xn)

(traccia: si utilizzi la funzione (di variabile z) G(z) = E_n(z)−ω(z)(En(x)/ω(x)), x 6∈ {x⁰, x1, . . . , xn} fissato, e si applichi ripetutamente il teorema di Rolle) 8. ∗ partendo dalla forma di Lagrange dell’errore di interpolazione polinomiale di

grado n per f ∈ Cⁿ⁺¹[a, b], si può dimostrare (dim. non richiesta) che il massimo errore nel caso di nodi equispaziati è ≤ max^x∈[a,b]{|f⁽ⁿ⁺¹⁾(x)|} hⁿ⁺¹/(4(n + 1)) dove h = (b − a)/n; perché da questa stima non si può dedurre la convergenza per f ∈ C^∞[a, b]? (vedi controesempio di Runge, f (x) = 1/(1+x²), x ∈ [−5, 5]) 9. interpolazione di Chebyshev: abbiamo visto che in generale i polinomi interpolatori non convergono alla funzione campionata (controesempio di Runge su nodi equispaziati); scelte speciali dei nodi però assicurano tale convergenza, è il caso ad esempio dell’interpolazione polinomiale su nodi di Chebyshev, del tipo

xi = b + a

2 − b − a

2 cos iπ n

, 0 ≤ i ≤ n oppure

xi = b + a

2 − b − a

2 cos (2i + 1)π 2n + 2

, 0 ≤ i ≤ n ;

si noti che tali nodi non sono equispaziati ma si accumulano più rapidamente agli estremi dell’intervallo [a, b]; la prima famiglia corrisponde alla proiezione su [a, b] di punti equispaziati sulla semicirconferenza di centro (a + b)/2 e raggio (b − a)/2, la seconda agli n + 1 zeri (opportunamente traslati e scalati) della funzione Tn+1(t) = cos((n + 1) arccos(t)), t ∈ (−1, 1), che è un polinomio (∗∗), il cosiddetto polinomio di Chebyshev di grado n + 1. Per questo tipo di nodi si può dimostrare (dim. non richiesta) che per ogni f ∈ C^k[a, b], k ≥ 1, esiste una costante M_k tale che

x∈[a,b]max |f(x) − Πⁿ(x)| ≤ M^klog(n) n^k ,

e quindi si ha convergenza uniforme per n → ∞ (in particolare per la funzione del controesempio di Runge)

(10)

10. ∗ si mostri che la “risposta alle perturbazioni” su f dell’interpolazione polinomiale `e legata alla quantit`a Λn = max_x∈[a,b]Pn

i=0|ℓⁱ(x)| (costante di Lebesgue), dove gli {ℓⁱ} sono i polinomi elementari di Lagrange; si osservi che Λⁿ dipende solo dai nodi di interpolazione; si può dimostrare (dim. non richiesta) che la crescita di Λnè esponenziale in n per i nodi equispaziati (instabilità), mentre è logaritmica per i nodi di Chebyshev

(traccia: si utilizzi la forma di Lagrange del polinomio interpolatore, detto Π˜n(x) =Pn

i=0f (x˜ i)ℓi(x) il polinomio interpolatore sui dati perturbati { ˜f (xi)}

dove | ˜f (xi) − f(xⁱ)| ≤ ε, si ha | ˜Πn(x) − Π(x)| ≤ ...)

11. `e noto che per qualsiasi distribuzione di nodi la costante di Lebesgue ha crescita almeno logaritmica, Λn≥ c¹log n, che per i nodi equispaziati Λn ∼ c²n log n²ⁿ (instabilit`a), mentre per i nodi di Chebyshev Λn= O(log n) (c¹e c2sono opportune costanti)

12. si dimostri che l’interpolazione lineare a tratti (disegnarla) converge uniforme- mente per f ∈ C²[a, b] con un errore O(h²), dove x0 = a < x1 < . . . < xn = b, h = maxi∆xi, ∆xi = xi+1− xⁱ, i = 0, . . . , n − 1

13. ∗ si dimostri che l’interpolazione quadratica a tratti (disegnarla) converge uni- formemente per f ∈ C³[a, b] con un errore O(h³), dove h = maxi∆xi; 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)

14. nell’interpolazione spline di grado k su x0 = a < x1 < . . . < xn = b, si cerca Sk∈ C^k−1[a, b] tale che Sk ristretta a [xi, xi+1] sia un polinomio di grado al pi`u k e Sk(xi) = f (xi); chi sono le incognite in questo problema, quante sono le equazioni (vincoli)? nel caso cubico, come si ottiene un sistema quadrato?

15. dato un campionamento {(xⁱ, yi)}^1≤i≤N, nell’approssimazione ai minimi quadrati invece di interpolare si cerca un polinomio p di grado m < N tale che la somma degli scarti quadratici PN

i=1(yi− p(xⁱ))² sia minima, ovvero si risolve il problema di minimo in m + 1 variabili

a∈Rmin^m+1

N

X

i=1

(yi− (a⁰+ a1xi+ . . . + amx^m_i ))²

Si pu`o dimostrare che questo problema ha soluzione unica, calcolabile risolvendo sistema lineare V^tV a = V^ty, dove V = (vij) = (x^j_i), 1 ≤ i ≤ N, 0 ≤ j ≤ m

`e una matrice di Vandermonde rettangolare N × (m + 1) e V^tV `e una matrice (m+1)×(m+1) simmetrica e definita positiva (traccia: si tratta della soluzione ai minimi quadrati del sistema sovradeterminato V a = y, vedi la sezione 1.6)

(11)

1.5 Integrazione e derivazione numerica

16. ∗ 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 (xi))}, i = 0, . . . , n, sono convergenti con un errore che `e almeno O(h^s+1), dove h = max ∆xi (c’`e qualche vincolo sul numero di nodi?)

17. ∗ si verifichi che le formule di quadratura interpolatorie (quelle ottenute integrando un unico polinomio interpolatore su tutti i nodi) hanno la forma di somma pesata Pn

i=0wif (xi), dove i {wⁱ} sono opportuni pesi

(traccia: si utilizzi la formula di interpolazione di Lagrange; ∗∗ lo stesso vale anche per le formule composte, che sono localmente “interpolatorie”, cio`e ottenute integrando un singolo polinomio interpolatore di grado s in [xks, x(k+1)s], k = 0, . . . , (n : s) − 1) con n multiplo di s)

18. si ricavino la formula di quadratura composta di grado 1, detta dei trapezi, e

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

19. l’interpolazione spline cubica pu`o essere usate per approssimare integrali e derivate di una funzione campionata?

(traccia.: si ricordi la stima dell’errore in norma infinito per f ∈ C⁴[a, b]

x∈[a,b]max|f^(j)(x) − S3^(j)(x)| ≤ cjh^4−j , 0 ≤ j ≤ 3

dove cj sono costanti (in h = max ∆xi) dipendenti da f ; si osservi che le derivate di S3 approssimano le derivate di f ma non sono in generale interpolanti) 20. 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 ch^p

• una nuova approssimazione con errore di ordine O(h^q) (estrapolazione) approfondimento ∗∗: come si potrebbe iterare il procedimento di estrapolazione per φ(h) = φ0+c1h^p¹+c2h^p²+. . .+cmh^p^m+O(h^q), 0 < p1 < p2 < . . . < pm < q?

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

21. 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 sono p e q per δ(h) con f ∈ C⁵)? si applichi l’esercizio precedente a vari esempi, controllando l’accuratezza delle approssimazioni e delle stime dell’errore

(12)

22. 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)?

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

(∗ traccia: detto ε l’errore su f, l’errore effettivo delle formule ha una stima del tipo E(h) = O(h^p) + O(ε/h), ...)

24. detta T (h) la formula di quadratura composta dei trapezi a passo costante e sapendo che T (h) =Rb

a f (x) dx + ch²+ O(h⁴) per f ∈ C⁴[a, b], si calcolino stima a posteriori dell’errore e formula di estrapolazione (detta formula di Romberg) su vari esempi di funzioni integrabili elementarmente, confrontando con l’errore effettivo

(traccia: per l’errore T (h) − T (h/2) = ³₄ch²+ O(h⁴), ...; per l’estrapolazione 4T (h/2) − T (h) = 3Rb

a f (x) dx + O(h⁴), ...)

25. ∗ abbiamo visto che la “risposta alle perturbazioni” su f dell’interpolazione polinomiale `e legata alla quantit`a Λn = maxx∈[a,b]Pn

i=0|ℓⁱ(x)| (costante di Lebesgue), dove gli {ℓⁱ} sono i polinomi elementari di Lagrange; si mostri che la quantit`a Pn

i=0|wi| svolge un ruolo analogo nel caso delle formule di quadratura interpolatorie e composte; perch´e in particolare le formule interpolatorie e composte con pesi positivi sono sicuramente stabili?

(traccia: tali formule sono esatte sui polinomi costanti, ...)

1.6 Algebra lineare numerica

1. ∗ stime di condizionamento (risposta della soluzione di un sistema lineare agli errori sul vettore termine noto): dato il sistema quadrato Ax = b con det(A) 6=

0, b 6= 0 e il sistema perturbato A(x + δx) = b + δb, si mostri che vale la stima kδxk

kxk ≤ k(A) kδbk kbk

dove k(A) = kAk kA⁻¹k `e l’indice di condizionamento di una matrice invertibile nella norma matriciale indotta dalla norma vettoriale (traccia: si utilizzi la disuguaglianza fondamentale valida per ogni norma matriciale indotta kAxk ≤ kAk kxk)

2. si pu`o dimostrare (dim. non richiesta) che per un sistema in cui anche la matrice sia affetta da errori, (A + δA)(x + δx) = b + δb, se kk(A)k kδAk < kAk, vale la stima

kδxk

kxk ≤ k(A)

1 − k(A)kδAk/kAk

kδAk

kAk +kδbk kbk

(13)

3. ∗∗ teorema fondamentale di invertibilit`a: data una norma matriciale in C^m×m tale che kABk ≤ kAk kBk (come sono tutte le norme indotte da norme vettoriali, ovvero kAk = supx6=0kAxk/kxk = supkxk=1kAxk), 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.: kPn

j=mA^jk ≤ Pn

j=mkAk^j e la serie geometrica P kAk^j è convergente e quindi di Cauchy, ... ; nel caso kAk sia indotta da una norma vettoriale, la dimostrazione di invertibilità e la stima si possono fare in modo più diretto osservando che k(I − A)xk ≥ kxk − kAxk > 0, e se x è autovettore di I − A ...;

detta poi S = (I − A)⁻¹ si ha 1 = kS(I − A)k ≥ kSk − kSAk ≥ ...).

(applicazione: si utilizzi il teorema fondamentale di invertibilit`a per dimostrare la stima generale di condizionamento del punto precedente; sugg: partendo da (A + δA)δx = δb − δAx e osservando che (A + δA) = A(I + A⁻¹δA) con kA⁻¹δAk ≤ kA⁻¹k kδAk < 1, ...).

4. si dimostri che k(A) ≥ |λ^max|/|λ^min| ≥ 1 con qualsiasi norma matriciale indotta, dove λmax e λmin sono gli autovalori di modulo massimo e minimo della matrice invertibile A; per le matrici simmetriche k2(A) = kAk²kA⁻¹k² = |λ^max|/|λ^min| (traccia: se λ `e autovalore di A e v 6= 0 autovettore corrispondente, da Av = λv, si ricava immediatamente |λ| = kAvk/kvk ≤ kAk; si ricordi poi che gli autovalori dell’inversa sono i reciproci degli autovalori di A, ...; si ricordi che in generale gli autovalori di A² sono i quadrati degli autovalori di A, per A simmetrica A^tA = A², ...)

5. ∗∗ la soluzione di sistemi lineari con matrici fortemente mal condizionate (nelle applicazioni non `e infrequente avere indici di condizionamento k(A) ≈ 10¹⁰, 10²⁰ o anche superiori) deve essere affrontata con metodi speciali; schematizzando e semplificando, si pu`o dire che molti metodi corrispondono a sostituire il sistema di partenza con una opportuna famiglia parametrizzata di sistemi

Ahxh = b

tali che ε(h) = kx − x^hk → 0, k(A^h) < k(A) e k(Ah) → k(A) per h → 0; dati i sistemi con termine noto perturbato

Ah(xh+ δxh) = b + δb si ha allora una stima

kx − (x^h+ δxh)k

kxk ≤ kx − x^hk

kxk + kδx^hk

kxk ≤ ε(h)

kxk + (1 + ε(h)) k(Ah)kδbk kbk da cui si vede che conviene minimizzare in h: come nella derivazione numerica con formule alle differenze, non conviene prendere il parametro h troppo grande (perché si è distanti da x) e neppure troppo piccolo (perché il condizionamento di Ah diventa troppo vicino a quello di A)

(14)

6. 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)

7. si mostri che il costo computazionale della soluzione di un sistema con matrice triangolare `e O(n²) flops

8. si può dimostrare (dim. non richiesta) che il metodo di eliminazione gaussiana con pivoting per righe produce per matrici non singolari una fattorizzazione P A = LU (dove P è una matrice di permutazione corrispondente agli scambi di righe, L è triangolare inferiore con 1 sulla diagonale e U è triangolare superiore);

come si risolve in sistema Ax = b utilizzando la fattorizzazione P A = LU?

9. perchè la fattorizzazione P A = LU calcolata in aritmetica di macchina è es- tremamente accurata (cioè, gli elementi di LU coincidono alla precisione di macchina con quelli di P A), ma per certe matrici (vedi matrice di Hilbert) la soluzione di sistemi ottenuta con tale fattorizzazione risulta molto poco accurata (se non addirittura completamente sbagliata)?

10. come si pu`o utilizzare la fattorizzazione P A = LU fornita dal metodo di eliminazione con pivoting per righe, per calcolare l’inversa di una matrice? si osservi che il costo computazionale complessivo `e O(n³) flops

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

11. 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 (che in generale non ha soluzione classica, perch´e?)

x∈RminⁿkAx − bk²2 = min

x∈Rⁿ m

X

i=1

bi−

n

X

j=1

aijxj

!2

`e equivalente a risolvere il sistema con matrice simmetrica definita positiva A^tAx = A^tb (detto “sistema delle equazioni normali”)

(traccia: ∗ 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 sviluppando i calcoli 2v^tA^t(Ax − b) + v^tA^tAv ≥ 0, e posto v = εu con kuk² = 1, per ε → 0 ...; per provare che A^tA `e definita positiva, si osservi che (A^tAv, v) = (Av, Av) ≥ 0 per ogni v ∈ Rⁿ, ...)

12. si ottenga il sistema delle equazioni normali come condizione necessaria di es- tremalit`a, annullando il gradiente di φ (chi `e la matrice Hessiana di φ?)

13. si reinterpreti l’approssimazione polinomiale ai minimi quadrati come soluzione ai minimi quadrati di un sistema sovradeterminato

(15)

matrice quadrata di Vandermonde corrispondente a nodi distinti `e non singolare, quindi considerando una sottomatrice quadrata della matrice di Vandermonde rettangolare ...)

14. sia A ∈ R^m×n, m ≥ n, una matrice di rango massimo: allora si può dimostrare (dim. non richiesta) che A ammette una fattorizzazione A = QR, dove Q ∈ R^m×n è una matrice ortogonale (ovvero le colonne di Q sono vettori ortonormali, cioè Q^tQ = I) e R è 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⁻¹, che resta triangolare superiore, è la matrice dei coefficienti dell’ortogonalizzazione)

15. come si può applicare la fattorizzazione QR alla soluzione di sistemi sovrade- terminati? (traccia: utilizzando A = QR, non è necessario calcolare la matrice A^tA perché A^tA = R^tR, ...)

16. cond. suff. per la convergenza delle approssimazioni successive: un sistema quadrato della forma x = Bx + c con kBk < 1 (in una norma matriciale indotta da una norma vettoriale) ha soluzione unica che si pu`o ottenere come limite della successione di approssimazioni successive vettoriali {x^k} definita da

xk+1 = Bxk+ c , k = 0, 1, 2, . . . a partire da un qualsiasi vettore iniziale x0

(traccia: il sistema ha soluzione unica se e solo se I − B `e invertibile, e gli autovalori di I − B sono del tipo µ = 1 − λ con λ autovalore di B e quindi

|λ| ≤ kBk < 1, ...; scrivendo x−x^k+1 = B(x−x^k) si ottiene la stima kx−x^k+1k ≤ kBk kx − x^kk, ...)

17. cond. nec. e suff. per la convergenza delle approssimazioni successive: il metodo delle approssimazioni successive xk+1 = Bxk+ c, k ≥ 0, converge alla soluzione di x = Bx + c per qualsiasi scelta dei vettori x0 e c se e solo se ρ(B) < 1 (dove ρ(B) `e il “raggio spettrale” della matrice quadrata B, ovvero il max dei moduli degli autovalori); dimostrazione non richiesta

18. dato uno splitting di una matrice quadrata, A = P − N, con det(P ) 6= 0, il sistema Ax = b si pu`o scrivere nella forma x = Bx + c dove B = P⁻¹N e c = P⁻¹b. Esempi di corrispondenti metodi delle approssimazioni successive nell’ipotesi aii6= 0 ∀i sono (posto A = D − (E + F ), dove D `e la parte diagonale di A ed −E, −F le parti triangolare inferiore e superiore di A − D)

• il metodo di Jacobi: P = D, N = E + F

• il metodo di Gauss-Seidel: P = D − E, N = F

Si scrivano per componenti tali metodi, e si dimostri che il metodo di Jacobi

`e convergente per matrici diagonalmente dominanti in senso stretto; si pu`o dimostrare (dim. non richiesta) che anche il metodo di Gauss-Seidel converge in

(16)

tale ipotesi nonch´e per matrici simmetriche definite positive (traccia: si consideri la norma infinito della matrice di iterazione B del metodo di Jacobi, ...)

19. ∗∗ il metodo delle approssimazioni successive si pu`o riscrivere come xk+1 = (I − P⁻¹A)xk+ P⁻¹b = xk+ P⁻¹r(xk)

(dove r(x_k) = b − Axk è il vettore “residuo” al passo k-esimo); il ruolo della matrice P⁻¹ può essere visto come quello di “precondizionatore”: l’azione di P⁻¹ è efficace quando P⁻¹ ≈ A⁻¹, nel senso che gli autovalori di P⁻¹A si accumulano intorno ad 1 (e nel contempo dato un vettore v, il calcolo di z = P⁻¹v, ovvero la soluzione del sistema P z = v, ha basso costo computazionale); vari metodi introducono un parametro di rilassamento α, xk+1 = xk+ αP⁻¹r(xk), che aumenti l’efficacia del precondizionatore (cercando di diminuire o addirittura minimizzare il raggio spettrale di B(α) = I − αP⁻¹A)

20. test di arresto del residuo: dato un qualsiasi metodo iterativo convergente per la soluzione di un sistema lineare non singolare Ax = b con b 6= 0, si mostri che vale la seguente stima dell’errore relativo

kx − x^kk

kxk ≤ k(A)kr(x^k)k kbk

21. ∗ metodo delle potenze per il calcolo degli autovalori estremali: data una matrice diagonalizzabile A ∈ R^m×m, con un unico autovalore di modulo massimo (di qualsiasi molteplicità), e la successione di vettori xn+1 = Axn, n ≥ 0 dove x₀ abbia componente non nulla nell’autospazio corrispondente, i quozienti di Rayleigh R(xn) = (Axn, xn)/(xn, xn) (dove (x, y) è il prodotto scalare euclideo di x, y ∈ R^m) convergono a tale autovalore e xn/kxⁿk² tende ad un autovettore (normalizzato) corrispondente; come si può modificare il metodo per calcolare l’autovalore di modulo minimo quando A è non singolare? (sugg.: si scriva x0

nella base di autovettori, ...; per l’autovalore di modulo minimo, si osservi che gli autovalori di A⁻¹ sono ...).

1.7 Differenze finite per equazioni differenziali

1. dato un problema ai valori iniziali y^′ = f (t, y), t ∈ [t⁰, tf]; y(t0) = a, con f di classe C¹ tale che |∂f/∂y| ≤ L, si dimostri che la “legge di propagazione”

dell’errore en= |yⁿ− y(tⁿ)| dei metodi di Eulero esplicito yn+1= yn+ hf (tn, yn) , 0 ≤ n ≤ N − 1 ed Eulero implicito

yn+1 = yn+ hf (tn+1, yn+1) , 0 ≤ n ≤ N − 1

su una discretizzazione a passo costante h = (tf − t⁰)/N, tn = t0 + nh, `e del tipo