1 Tracce di calcolo numerico

1 Tracce di calcolo numerico

Corsi di laurea triennale in Ingegneria aggiornamento: 7 giugno 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) (α

. . . α

α

.α

. . . α

. . .)

= 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

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

• 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 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?

• 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 (con un disegno) del fatto che il massimo errore di arrotondamento ad n cifre `e la met`a del massimo errore di troncamento (∗∗ `e possibile dare una dimostrazione rigorosa di questo fatto utilizzando la serie che rappresenta la parte frazionaria)

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;

quelli contrassegnati da

sono difficili e non sono considerati essenziali per una buona preparazione

• 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?

• 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, ε

= β

/2, non `e il pi` u piccolo numero floating- point positivo; che cos’`e invece?

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

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

• ∗∗ si dimostri che vale anche ε

= min {µ ∈ F

: 1 + µ > 1}; quali numeri floating-point si comportano come elemento neutro nell’addizione con un dato numero floating-point µ?

• 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

• 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”

ε

≈ |xf

(x)/f (x)| ε

, f (x) 6= 0

• 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 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) = ...)

• ∗ si trovino esempi di funzioni “instabili”, cio`e tali che per certi punti x si ha ε

≫ ε

qualunque sia la rappresentazione di f , e di funzioni “stabili” per cui l’instabilit`a nel calcolo dipende dalla rappresentazione

• 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

• 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?

• ∗ 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; ∗∗ si dimostrino convergenza e stabilit`a della formula all’indietro analizzando l’errore relativo

1.2 Costo computazionale degli algoritmi numerici

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

• 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?

• ∗ 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 → ∞?)

1.3 Soluzione numerica di equazioni non lineari

• 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

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

• 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

)    

• si dia un’interpretazione geometrica del metodo di Newton x

= x

− f (x

)

f

(x

) , f

(x

) 6= 0 , n = 0, 1, 2, . . .

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

• 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 conver-

genza locale ? ∗∗ si enunci e dimostri rigorosamente 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, ρ

= e

/|ξ|; col metodo di Newton ρ

≤ C|ξ|ρ

, ...)

• 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

• 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

• 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)?

• 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

• si verifichi l’applicabilit`a dei metodi di bisezione e di Newton all’equazione x − e

= 0

• 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|

= 0 si

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

= 0 la succes-

sione `e addirittura divergente; dove sta il problema?

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

• 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 θ?)

• 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

, ...)

• si studi la soluzione delle equazioni x = e

e x = e

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

?

• 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

• 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

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

• 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 → ∞ ?

• perch´e il polinomio interpolatore Π

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

, x

, . . . , x

} `e unico?

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

• 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

)

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

• ∗ 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 ausiliaria di variabile z G(z) = E

(z)−ω(z)(E

(x)/ω(x)),

x ∋ {x

, x

, . . . , x

} fissato, 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 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])

• 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 oppure

x

= 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` u 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 T

(t) = cos((n + 1) arccos(t)), t ∈ (−1, 1), che `e un polinomio (∗∗), il cosiddetto polinomio di Chebyshev di grado n + 1. 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)

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

• 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

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

• 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?

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

1.5 Integrazione e derivazione numerica

• 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

(x) − S

(x)| ≤ c

h

, 0 ≤ j ≤ 3 dove c

sono costanti (in h = max ∆x

) dipendenti da f )

• ∗ si dimostri che, per f ∈ C

[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 = 0, . . . , n, sono convergenti con un errore che `e almeno O(h

), dove h = max ∆x

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

• ∗ si verifichi che, come le formule interpolatorie (quelle ottenute integrando un unico polinomio interpolatore su tutti i nodi) hanno la forma di somma pesata 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)

• 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

• 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) approfondimento ∗∗: come si potrebbe iterare il procedimento di estrapolazione per φ(h) = φ

+c

h

+c

h

+. . .+c

h

+O(h

), 0 < p

< p

< . . . < p

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

• 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

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

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

• 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

), ...)

• ∗ 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

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

• 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



• si dimostri che k(A) ≥ |λ

|/|λ

| ≥ 1 con qualsiasi norma matriciale indotta, dove λ

e λ

sono gli autovalori di modulo massimo e minimo della matrice invertibile A; per le matrici simmetriche k

(A) = kAk

kA

k

= |λ

|/|λ

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

A = A

, ...)

• ∗∗ 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

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

• 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 dimostri che il costo computazionale asintotico del metodo di eliminazione gaussiana `e 2n

/3 flops (traccia: si incastri il costo tra due integrali)

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

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

) flops

• 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?

• 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)?

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

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

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

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

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

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

• 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

• 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 a

6= 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 tale ipotesi nonch´e per matrici simmetriche definite positive (traccia: si consideri la norma infinito della matrice di iterazione B del metodo di Jacobi, ...)

• ∗∗ il metodo delle approssimazioni successive si pu`o riscrivere come x

= (I − P

A)x

+ P

b = x

+ P

r(x

)

(dove r(x

) = b − Ax

`e il vettore “residuo” al passo k-esimo); il ruolo della matrice P

pu`o essere visto come quello di “precondizionatore”: l’azione di P

`e efficace quando P

≈ A

, nel senso che gli autovalori di P

A si accu- mulano 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 α, x

= x

+ αP

r(x

), che aumenti l’efficacia del precondizionatore (cercando di diminuire o addirit- tura minimizzare il raggio spettrale di B(α) = I − αP

A)

• 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) kr(x

)k

kbk