1 Tracce di calcolo numerico

1 Tracce di calcolo numerico

Lauree tecnologiche (Informatica, Ingegneria)

Prof. Marco Vianello - Dipartimento di Matematica aggiornamento: 5 giugno 2014

testo di riferimento: A. Quarteroni, F. Saleri, Calcolo Scientifico, Springer, 2008

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) (α

. . . α

α

.α

. . . α

. . .)

= sign(x)

m

X

j=0

α

β

+

∞

X

j=1

α

β

!

dove α

, α

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

j=0

α

β

parte intera del numero e P

j=1

α

β

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 si pu`o anche scrivere (rappresentazione normalizzata a virgola mobile) come

x = sign(x)β

(0.d

. . . d

. . .)

= sign(x)β

∞

X

j=1

d

β

d

∈ {0, 1, . . . β − 1}, d

6= 0, dove chiamiamo P

j=1

d

β

mantissa e p ∈ Z esponente della rappresentazione normalizzata a virgola mobile in base β; a cosa serve la normalizzazione d

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

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

1

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

8. si dia un’interpretazione geometrica (con un disegno) del fatto che il massimo errore di arrotondamento ad n cifre `e la met`a del massimo errore di troncamento 9. si studi l’insieme dei numeri floating-point F(β, t, L, U) = {µ ∈ Q : µ =

±(0.µ

µ

. . . µ

)β

, µ

∈ {0, 1, . . . , β − 1} , p ∈ [L, U] ⊂ Z}

(traccia: determinare cardinalit`a, estremi, variazione di densit`a, intorni di ap- prossimazione 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, ε

= β

/2, non `e il pi` u piccolo numero floating- point positivo; che cos’`e 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´e? (si osservi che questo `e un esempio di non unicit`a dell’elemento neutro)

15. ∗ si pu`o dimostrare che vale anche ε

= min {µ ∈ F

: 1 + µ > 1}

16. detti ε

= |x− ˜x|/|x| e ε

= |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| ≤ w

(x, y)ε

+ w

(x, y)ε

, , x ⋆ y 6= 0 ,

calcolando w

, w

nei 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 facciano esempi

17. detto ε

l’errore relativo su una funzione (derivabile) con variabile approssimata, ε

= |x − ˜x|/|x|, x 6= 0, utilizzando la formula di Taylor si ricavi la “formula degli errori”

ε

≈ cond(f(x)) ε

, cond(f (x)) = |xf

(x)/f (x)| , f(x) 6= 0

18. si consideri f (x) = ((1 + x) − 1)/x, x 6= 0; in Matlab si ha che f(10

) = 1.110223024625157, invece ((1+2

)−1)/2

= 1, dove 2

≈ 10

; perch´e?

19. si consideri f (x) = 1 − √

1 − x

, |x| ≤ 1, e si calcoli cond(f(x)); in Matlab si ha che f (10

) =5.000000080634948e-09 ma il valore esatto (alla precisione di macchina) `e 5.000000012500000e-09; la perdita di precisione (quantificarla) `e compatibile con la formula degli errori? in caso contrario, qual’`e il problema e come si pu`o superarlo?

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 cor- rispondente e si ricavi una formula “stabilizzata” (traccia: per la stabilizzazione, si osservi ad esempio che per b > 0, √

∆−b = ( √

∆−b)( √

∆+b)/( √

∆+b) = ...) 22. si riscrivano, se necessario, le seguenti espressioni per ovviare a possibili insta-

bilit`a in aritmetica di macchina:

E

(x) = x

/(2 + x

+ 0.1|x|) − x + 100(x

+ 5)

E

(x) = √

x

+ 1 − |x| + 100x E

(x) = 3 √

x

+ 2 − (10x

+ 1)/(x

+ 1) + 10x

23. la successione definita da x

= 2, x

= 2

q

1 − p1 − 4

x

, n = 2, 3, . . ., soddisfa lim

x

= π, ma se usata per approssimare π diventa insta- bile 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?

24. ∗ la formula di ricorrenza in avanti I

= 1 − nI

, n = 1, 2, . . ., I

= 1 − e

, soddisfatta da I

= e

R

0

x

e

dx, `e fortemente instabile in aritmetica di macchina (perch´e?), ma pu`o essere stabilizzata usandola all’indietro

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

= a

= Q a

, dove {c

} sono

le cifre della codifica binaria di n ∈ N; qual’`e il costo computazionale (come

numero di operazioni aritmetiche floating-point) in funzione di n? qual’`e il

costo nel caso l’algoritmo venga applicato al calcolo di una potenza di matrice?

3. ∗ perch´e il calcolo di exp (x) (per x > 1) usando la formula exp (x) = (exp (x/m))

, m > [x] e la formula di Taylor per exp (x/m), `e pi` u 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 x

, x

, . . . , x

, . . ., costruita col metodo di bisezione (utilizzando iterativamente il teorema degli zeri) soddisfa la stima a priori dell’

errore

e

= |ξ − 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 lim

x

= ξ, 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 x

∈ [c, d] almeno per n abbastanza grande, si utilizzi il teorema del valor medio, f (x

)−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)

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

e

= |ξ − x

| ≈ |f(x

)|

x

− x

f (x

) − f(x

)

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

x

= x

− f (x

)

f

(x

) , f

(x

) 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 x

tale che f (x

)f

(x

) < 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 {x

} `e monotona e limitata, ...)

6. detto e

= |ξ − x

| l’errore assoluto del metodo di Newton per f(x) = 0, in ipotesi di convergenza e per f ∈ C

(I), dove I ⊃ {x

} `e un intervallo chiuso e limitato in cui f

(x) 6= 0, si dimostri la disuguaglianza e

≤ Ce

con C costante opportuna

(traccia: utilizzare la formula di Taylor calcolata nella radice e centrata in x

, insieme alla definizione di {x

}, ...)

∗ approfondimento: partendo da tale disuguaglianza, perch`e ci si aspetta con- vergenza locale? (cio`e, partendo in un intorno opportuno della soluzione) 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, ρ

= e

/|ξ|; col metodo di Newton ρ

≤ C|ξ|ρ

, ...)

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

e

≤ Ce

e ordine esattamente p se vale

n→∞

lim e

e

= 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

9. si dimostri che in ipotesi di convergenza il numero di iterazioni che garantiscono un errore assoluto ≤ ε (dove ε `e una tolleranza) `e n ≥ c

log (ε

) + c

per il metodo di bisezione e n ≥ c

log (log (ε

)) + c

per il metodo di Newton, dove c

, c

, c

, c

sono opportune costanti

10. perch´e la quantit`a |x

− x

| (detta “step”) `e una buona stima dell’errore assoluto per il metodo di Newton (almeno per n abbastanza grande)?

11. si verifichi l’applicabilit`a dei metodi di bisezione e di Newton alle equazioni

x = e

(dare un’interpretazione geometrica come intersezione di grafici) e 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) 12. ∗ se si applica il metodo di Newton con x

6= 0 all’equazione sign(x)|x|

= 0

si ottiene una successione “stazionaria”, mentre per sign(x)|x|

= 0 la succes- sione `e addirittura divergente; dove sta il problema?

13. data una stima s

dell’errore di un metodo iterativo convergente, e

≤ s

oppure e

≈ s

, si discuta il significato di un test di arresto delle iterazioni del tipo s

≤ |x

|ε

+ ε

, dove ε

`e una tolleranza assoluta ed ε

una tolleranza relativa 14. un risultato di convergenza delle iterazioni di punto fisso: sia φ : I → R deriv- abile 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

= φ(x

), n = 0, 1, 2, . . ., converge all’unico punto fisso di φ in I (dimostrazione non richiesta, ma 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)

15. ∗ corollario (convergenza locale): sia ξ punto fisso di una funzione φ derivabile 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 θ?)

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

|x

− ξ| ≤ θ

|x

− ξ| (a priori)

|x

− ξ| = |x

− x

|

1 − φ

(z

) ≤ 1

1 − θ |x

− x

| (a posteriori)

dove z

∈ 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

) − φ(ξ)| = |φ

(z

)| |x

− ξ| ≤ . . .; per la seconda si osservi che x

− x

= x

− ξ + ξ − x

= φ

(z

)(x

− ξ) + ξ − x

, ...)

17. si studi la soluzione dell’equazione di Keplero con le iterazioni di punto fisso;

quante iterazioni occorrono per garantire un errore assoluto < 10

?

18. ordine di convergenza delle iterazioni di punti fisso: si dimostri che un’iterazione

di punto fisso x

= φ(x

), con φ ∈ C

in un intorno di ξ, ha ordine 1 se e

solo se φ

(ξ) 6= 0, e ha ordine p > 1 se e solo se φ

(ξ) 6= 0 e φ

(ξ) = 0,

j = 1, . . . , p − 1

19. 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 x

= φ(x

) con φ(x) = . . . )

1.4 Interpolazione e approssimazione di dati e funzioni

1. problema algebrico dell’interpolazione (costruzione): dati n+1 punti (x

, f (x

)), i = 0, . . . , n, sul grafico di una funzione f : [a, b] → R, determinare se esiste ed

`e unica una funzione φ

in una opportuna famiglia di funzioni F

, tale che φ

(x

) = f (x

) , i = 0, . . . , n

(nel caso di F

= P

, lo spazio vettoriale dei polinomi di grado ≤ n, si parla di interpolazione polinomiale, e chiameremo Π

(x) = φ

(x) il polinomio interpo- latore)

2. problema analitico dell’interpolazione (convergenza): per quali scelte dei nodi {x

} e in quali ipotesi su f si ha convergenza uniforme degli interpolatori, cio`e

x∈[a,b]

max |φ

(x) − f(x)| → 0 , n → ∞ ?

3. perch´e il polinomio interpolatore Π

(x) di grado ≤ n di una funzione f su n + 1 nodi distinti {x

, x

, . . . , x

} `e unico?

4. si mostri che

Π

(x) =

n

X

i=0

f (x

) ℓ

(x) , ℓ

(x) = Q

k6=i

(x − x

) Q

k6=i

(x

− x

)

`e il polinomio interpolatore su n + 1 nodi distinti {x

, x

, . . . , x

} (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

) = (x

), 0 ≤ i, j ≤ n `e detta “matrice di Vandermonde” dei nodi di interpolazione, a = (a

, . . . , a

)

e y = (y

, . . . , y

)

, y

= f (x

)

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

(traccia: il problema `e equivalente ad un sistema lineare con matrice V , l’unicit`a significa che l’applicazione lineare associata a V `e iniettiva cio`e il nucleo di V `e 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)

E

(x) = f (x) − Π

(x) = f

(η)

(n + 1)! (x − x

) . . . (x − x

)

dove η ∈ int(x, x

, . . . , x

)

(traccia: si utilizzi la funzione (di variabile z) G(z) = E

(z)−ω(z)(E

(x)/ω(x)), x 6∈ {x

, x

, . . . , x

} 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`o dimostrare (dim. non richiesta) che il massimo errore nel caso di nodi equispaziati `e ≤ max

{|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]) 9. interpolazione di Chebyshev: abbiamo visto che in generale i polinomi inter- polatori non convergono alla funzione campionata (controesempio di Runge su nodi equispaziati); scelte speciali dei nodi per`o assicurano tale convergenza, `e il caso ad esempio dell’interpolazione polinomiale su nodi di Chebyshev, del tipo

x

= b + a

2 − b − a

2 cos  iπ n



, 0 ≤ i ≤ n

si noti che tali nodi non sono equispaziati ma si accumulano pi` u rapidamente agli estremi dell’intervallo [a, b]; geometricamente corrispondono alla proiezione su [a, b] di punti equispaziati sulla semicirconferenza di centro (a + b)/2 e raggio (b − a)/2; per questo tipo di nodi si pu`o dimostrare (dim. non richiesta) che per ogni f ∈ C

[a, b], k ≥ 1, esiste una costante M

tale che

x∈[a,b]

max |f(x) − Π

(x)| ≤ M

log(n) n

,

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

10. ∗ si mostri che la “risposta alle perturbazioni” su f dell’interpolazione polino- miale `e legata alla quantit`a Λ

= max

P

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`o dimostrare (dim. non richiesta) che la crescita di Λ

`e esponenziale in n per i nodi equispaziati (instabilit`a), mentre `e logaritmica per i nodi di Chebyshev

(traccia: si utilizzi la forma di Lagrange del polinomio interpolatore, detto Π ˜

(x) = P

i=0

f (x ˜

)ℓ

(x) il polinomio interpolatore sui dati perturbati { ˜ f (x

)}

dove | ˜ f (x

) − f(x

)| ≤ ε, si ha | ˜ Π

(x) − Π(x)| ≤ ...)

11. si dimostri che l’interpolazione lineare a tratti (disegnarla) converge uniforme- mente per f ∈ C

[a, b] con un errore O(h

), dove x

= a < x

< . . . < x

= b, h = max

∆x

, ∆x

= x

− x

, i = 0, . . . , n − 1

12. ∗ si dimostri che l’interpolazione quadratica a tratti (disegnarla) converge uni-

formemente per f ∈ C

[a, b] con un errore O(h

), dove h = max

∆x

; 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)

13. nell’interpolazione spline di grado k su x

= a < x

< . . . < x

= b, si cerca S

∈ C

[a, b] tale che S

ristretta a [x

, x

] sia un polinomio di grado al pi` u k e S

(x

) = f (x

); chi sono le incognite in questo problema, quante sono le equazioni (vincoli)? nel caso cubico, come si ottiene un sistema quadrato?

14. dato un campionamento {(x

, y

)}

, nell’approssimazione ai minimi quadrati invece di interpolare si cerca un polinomio p di grado m < N tale che la somma degli scarti quadratici P

i=1

(y

− p(x

))

sia minima, ovvero si risolve il prob- lema di minimo in m + 1 variabili

a∈R

min

N

X

i=1

(y

− (a

+ a

x

+ . . . + a

x

))

Si pu`o dimostrare che questo problema ha soluzione unica, calcolabile risolvendo sistema lineare V

V a = V

y, dove V = (v

) = (x

), 1 ≤ i ≤ N, 0 ≤ j ≤ m

`e una matrice di Vandermonde rettangolare N × (m + 1) e V

V `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); si calcolino la matrice V

V e il termine noto V

y nel caso m = 1 (approssimazione lineare ai minimi qudrati o retta di regressione)

1.5 Integrazione e derivazione numerica

1. l’operazione funzionale di integrazione `e stabile; detta infatti ˜ f ≈ f un’approssimazione di f funzione integranda continua (ottenuta ad esempio per interpolazione)

Z

a

f (x) dx − Z

a

f (x) dx ˜   

 ≤ (b − a) max

x∈[a,b]

|f(x) − ˜ f (x)| , cio`e, controllando l’errore su f si controlla l’errore sul suo integrale

2. ∗ si dimostri che, per f ∈ C

[a, b], le formule di quadratura composte dei trapezi (s = 1) e delle parabole (s = 2) costruite su un campionamento {(x

, f (x

))}, i = 0, . . . , n, sono convergenti con un errore che `e almeno O(h

), dove h = max ∆x

(c’`e qualche vincolo sul numero di nodi?)

3. si verifichi che le formule interpolatorie (quelle ottenute integrando un unico polinomio interpolatore su tutti i nodi) sono somme pesate P

i=0

w

f (x

), 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 ot-

tenute integrando un singolo polinomio interpolatore di grado s in [x

, x

],

k = 0, . . . , (n : s) − 1) con n multiplo di s)

4. 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

5. data una formula di approssimazione φ(h) di una quantit`a φ

, con la struttura φ(h) = φ

+ ch

+ O(h

), q > p > 0, utilizzando opportune combinazioni lineari di φ(h) e φ(h/2) si ricavino:

• una stima a posteriori della parte principale dell’errore ch

• una nuova approssimazione con errore di ordine O(h

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

7. si rifletta sull’instabilit`a intrinseca dell’operazione funzionale di derivazione:

funzioni arbitrariamente vicine possono avere derivate arbitrariamente distanti, fare un esempio grafico; come viene ereditata tale instabilit`a dai rapporti incre- mentali? (traccia: usando ˜ f al posto di f nel calcolo dei rapporti incrementali ...)

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

9. perch`e l’effetto dell’instabilit`a viene mitigato usando formule di derivazione nu- merica con errore di ordine maggiore? ad es. con δ(h) invece di δ

(h), oppure applicando l’estrapolazione

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

) + O(ε/h), ...)

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

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) = 3 R

a

f (x) dx + O(h

), ...)

11. ∗ abbiamo visto che la “risposta alle perturbazioni” su f dell’interpolazione polinomiale `e legata alla quantit`a Λ

= max

P

i=0

|ℓ

(x)| (costante di Lebesgue), dove gli {ℓ

} sono i polinomi elementari di Lagrange; si mostri che la quantit`a P

i=0

|w

| svolge un ruolo analogo nel caso delle formule di quadratura interpolatorie e composte; perch´e in particolare le formule interpolatorie e com- poste 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



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

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

) flops

5. si pu`o 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 `e una matrice di permutazione corrispondente agli scambi di righe, L `e triangolare inferiore con 1 sulla diagonale e U `e triangolare superiore);

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

6. perch`e la fattorizzazione P A = LU calcolata in aritmetica di macchina `e es- tremamente accurata (cio`e, 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)?

7. ∗ (cenni facoltativi) la soluzione di sistemi lineari con matrici fortemente mal condizionate (nelle applicazioni non `e infrequente avere indici di condiziona- mento k(A) ≈ 10

, 10

o anche superiori) deve essere affrontata con metodi speciali; schematizzando e semplificando, si pu`o dire che molti metodi corrispon- dono a sostituire il sistema di partenza con una opportuna famiglia parametriz- zata di sistemi

A

x

= b

tali che ε(h) = kx − x

k → 0, k(A

) < k(A) e k(A

) → k(A) per h → 0; dati i sistemi con termine noto perturbato

A

(x

+ δx

) = b + δb si ha allora una stima

kx − (x

+ δx

)k

kxk ≤ kx − x

k

kxk + kδx

k

kxk ≤ ε(h)

kxk + kx

k

kxk k(A

) kδbk kbk

≈ ε(h)

kxk + k(A

) 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´e si `e distanti da x) e neppure troppo piccolo (perch´e il condizionamento di A

diventa troppo vicino a quello di A)

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

9. sia A ∈ R

, 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∈R

min

kAx − bk

= min

x∈Rⁿ m

X

i=1

b

−

n

X

j=1

a

x

!

`e equivalente a risolvere il sistema con matrice simmetrica definita positiva A

Ax = A

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?

(∗ traccia: si osservi che x minimizza il polinomio quadratico φ(x) = kAx − bk

se e solo se per ogni v ∈ R

si ha φ(x) ≤ φ(x + v) ovvero sviluppando i calcoli 2v

A

(Ax−b)+v

A

Av ≥ 0, e posto v = εu con kuk

= 1, per ε → 0 ...; nel caso polinomiale, si ricordi che una matrice quadrata di Vandermonde corrispondente a nodi distinti `e non singolare, quindi considerando una sottomatrice quadrata della matrice di Vandermonde rettangolare ...)

10. sia A ∈ R

, m ≥ n, una matrice di rango massimo: allora si pu`o di-

mostrare (dim. non richiesta) che A ammette una fattorizzazione A = QR,

dove Q ∈ R

`e una matrice ortogonale (ovvero le colonne di Q sono vettori

ortonormali, cio`e Q

Q = I) e R `e una matrice triangolare superiore non singo-

lare (si tratta in sostanza di un procedimento equivalente all’ortogonalizzazione

di Gram-Schmidt delle colonne di A: la matrice R

, che resta triangolare su-

periore, `e la matrice dei coefficienti dell’ortogonalizzazione)

11. come si pu`o applicare la fattorizzazione QR alla soluzione di sistemi sovrade- terminati? (traccia: utilizzando A = QR, non `e necessario calcolare la matrice A

A perch´e A

A = R

R, ...)

12. 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

} definita da

x

= Bx

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

(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

= B(x−x

) si ottiene la stima kx−x

k ≤ kBk kx − x

k, ...)

13. cond. nec. e suff. per la convergenza delle approssimazioni successive: il metodo delle approssimazioni successive x

= Bx

+ c, k ≥ 0, converge alla soluzione di x = Bx + c per qualsiasi scelta dei vettori x

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

14. 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; un esempio nell’ipotesi a

6= 0 ∀i `e il classico metodo di Jacobi, P = D (la parte diagonale di A), N = A−D; si scriva il metodo per componenti tali metodi, e si dimostri che `e convergente per matrici diagonalmente dominanti in senso stretto, ovvero |a

| > P

j6=i

|a

| ∀i (traccia: si calcoli la norma infinito della corrispondente matrice di iterazione B)

15. 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

k

kxk ≤ k(A) kb − Ax

k

kbk