1) ∗∗ Si dimostri, usando le serie, che l’errore di arrotondamento ad m cifre dopo la virgola in base β `e ≤ β −m /2.

Calcolo numerico: esercizi facoltativi di ripasso e approfondimento per astronomi e matematici (gli esercizi contrassegnati da ^∗ e ^∗∗ sono pi` u im- pegnativi).

1) ^∗∗ Si dimostri, usando le serie, che l’errore di arrotondamento ad m cifre dopo la virgola in base β `e ≤ β ^{− m} /2.

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, precisione di macchina, ...).

3) Quali numeri floating-point si comportano come elemento neutro nell’addizione con un dato numero floating-point µ?

4) Si dimostri che se un reale y approssima il reale x con un errore relativo < β ^{− m} , allora i due numeri hanno almeno m cifre significative coincidenti in base β (traccia: si ragioni sulle mantisse).

5) ^∗ Detto ε f l’errore relativo su una funzione (differenziabile) con variabili approssi- mate, si dia una veste pi` u rigorosa alla “formula degli errori”

ε 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 e si applichi la formula alla stima dell’errore nelle operazioni aritmetiche (traccia: si utilizzi il teorema del valor medio).

6) In Matlab si ha che ((1 + 10 ⁻¹⁵ ) − 1)/10 ⁻¹⁵ = 1.110223024625157, ma invece ((1 + 2 ^{− 50} ) − 1)/2 ^{− 50} = 1, dove 2 ^{− 50} ≈ 10 ^{− 15} . Perch´e?

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

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

9) Riscrivere, se necessario, le seguenti espressioni per ovviare a possibili instabilit`a in aritmetica di macchina:

E 1 (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 ²

1

10) ^∗ La formula di ricorrenza in avanti I n = 1−nI ⁿ⁻¹ , n = 1, 2, . . ., I 0 = 1−e ^{− 1} , sod- disfatta da I n = e ^{− 1 R} ₀ ¹ 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.

11) Si dimostri che la complessit`a asintotica del metodo di eliminazione gaussiana

`e 2n <sup>3</sup> /3 flops (traccia: si incastri la complessit`a tra due integrali).

12) 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 ⁿ⁺¹ ≤ Ke ² n con K costante opportuna. Approfondimento ^∗ : partendo da tale disuguaglianza, si arrivi ad enunciare e dimostrare un risultato di convergenza locale.

13) 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, vedi es. 4).

14) Si dimostri che in ipotesi di convergenza il numero di iterazioni che garantiscono un errore assoluto ≤ ε (dove ε `e una tolleranza) `e n ≥ c ¹ log (ε ^{− 1} ) + c 2 per il metodo di bisezione e n ≥ c 3 log (log (ε ⁻¹ )) + c ₄ per il metodo di Newton, dove c 1 , c 2 , c 3 , c 4 sono opportune costanti.

15) Perch´e la quantit`a |x <sup>n+1</sup> − x <sup>n</sup> | `e una buona stima dell’errore assoluto |x ⁿ − ξ|

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

16) 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, ...).

17) Se si applica il metodo di Newton con x 0 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?

18) ^∗∗ 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 ₁ ? ...)

2

19) ^∗ 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 ⁰ , . . . , x n ) (traccia: si utilizzi la funzione ausiliaria G(u) = E n (u) − ω(u)(E n (x)/ω(x)) e si applichi il teorema di Rolle).

20) ^∗ 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]).

21) ^∗ 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 ^{− 8} (traccia: si utilizzi localmente la stima dell’es.20).

22) ^∗ Si dimostri che, per f ∈ C ^s+1 [a, b], le formule di quadratura “composte” ot- tenute 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 <sub>i</sub> (c’`e qualche vincolo sul numero di nodi?).

23) ^∗ 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 i } 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).

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

25) Data una formula di approssimazione φ(h) di una quantit`a φ 0 , con la struttura φ(h) = φ 0 + ch ^p + O(h ^q ), q > p, 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) = φ 0 + c 1 h ^p

+ c 2 h ^p

+ . . . c m h ^p

+ O(h ^q ), p 1 < p 2 < . . . < p m < q?

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

26) 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’es.25 per f abbastanza regolare (traccia: si utilizzi la formula di Taylor;

3

in particolare, chi `e q per δ(h) con f ∈ C ⁵ )? Si applichino poi i risultati dell’es.25 a vari esempi di calcolo della derivata, controllando l’accuratezza delle approssimazioni e delle stime dell’errore.

27) Detta T (h) la formula di quadratura composta dei trapezi a passo costante e sapendo che T (h) = ^R _a ^b f (x) dx + ch ² + O(h ⁴ ) per f ∈ C ⁴ [a, b], si applichino i risultati dell’es.25 a vari esempi di calcolo di integrali di funzioni integrabili anche elementarmente, confrontando con l’errore effettivo.

28) ^∗∗ Abbiamo visto che la “risposta alle perturbazioni” su f dell’interpolazione poli- nomiale `e legata alla quantit`a Λ n = max x∈[a,b] P _n

i=0 |` <sup>i</sup> (x)| (costante di Lebesgue), dove gli {` i } sono i polinomi elementari di Lagrange. Quale quantit`a potrebbe svolgere un ruolo analogo nel caso delle formule di quadratura interpolatorie e composte, e perch´e in particolare le formule con pesi positivi sono sicuramente stabili? (traccia: si veda l’es.23 e si utilizzi il fatto che le formule interpolatorie e composte danno risultato esatto sulle funzioni costanti).

4