Tracce di calcolo numerico

Tracce di calcolo numerico

Prof. Marco Vianello - Dipartimento di Matematica, Universit` a di Padova aggiornamento: 18 settembre 2015

1 Sistema floating-point e propagazione degli errori

1.1 Rappresentazione dei numeri reali, errore di troncamento e di arro- tondamento

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

. . . c

c

.c−1 . . . c

. . .)

= sign(x)





m

X

j=0

c

β

+

∞

X

j=1

c

β





dove c

, c

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

c

β

parte intera del numero e P

j=1

c

β

parte frazionaria del numero

2. si ricordino le principali propriet`a della somma geometrica e della serie geometrica di ragione a 6= 1, ovvero S

= P

j=0

a

e S = P

a

traccia: aS

− Sn = (a − 1)S

= a

− 1, ...

3. perch´e la serie che rappresenta la parte frazionaria converge?

traccia: si utilizzi il confronto con la serie geometrica di ragione a = 1/β, osservando che c

≤ β − 1 (si tratta del criterio di confronto tra serie a termini non negativi); si osservi che la parte frazionaria sta in [0, 1], controllando ad esempio che (0.999 . . .)

= (0.111 . . .)

= 1

4. la parte frazionaria di un numero irrazionale `e infinita (perch´e?); la parte frazionaria di un numero razionale pu` o essere finita o infinita a seconda della base: 1/3 = (0.333 . . .)

(verificarlo) ma 1/3 = (0.1)

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

traccia: l’errore di troncamento non `e altro che il resto della serie corrispondente alla parte frazionaria, ...

6. si dia un’interpretazione geometrica (con un disegno, ad esempio nel caso di 2 cifre decimali) del fatto che il massimo errore di arrotondamento ad n cifre `e la met` a del massimo errore di troncamento (con l’usuale regola di arrotondamento, base pari: si tiene la cifra com’`e se la prima trascurata `e minore di β/2, si aumenta la cifra di una unit` a se la prima trascurata `e maggiore o uguale di β/2)

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

1.2 Sistema floating-point

1. si mostri (con qualche esempio) che ogni numero reale si pu` o anche scrivere (rappre- sentazione normalizzata a virgola mobile in base β) 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; a cosa serve la normalizzazione d

6= 0?

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

4. si studi l’insieme dei numeri floating-point

F (β, t, L, U ) = {µ = ±(0.µ

µ

. . . µ

)β

, µ

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

6= 0 , p ∈ [L, U] ⊂ Z } traccia:

• card(F) = 1 + 2(β − 1)β

(U − L + 1) (sugg.: F `e simmetrico, F

= −F

; si contino le possibili mantisse e i possibili esponenti)

• min F

= β

(sugg.: chi `e la minima mantissa?)

• max F

= β

(1 − β

) (sugg.: utilizzare la somma geometrica per calcolare la massima mantissa)

• i numeri floating-point sono razionali

• si rifletta sul fatto che la densit`a `e variabile calcolando la distanza tra numeri macchina consecutivi; dove e come cambia tale densit`a?

• si rifletta sul concetto di raggio assoluto e relativo dell’intorno di approssimazione corrispondente ad ogni numero macchina, calcolando la precisione di macchina ε

che `e il massimo errore relativo di arrotondamento a t cifre di mantissa

• quando l’intorno associato ad un numero floating-point non `e simmetrico?

• quali sono i numeri reali rappresentabili (ovvero approssimabili per arrotonda- mento a t cifre di mantissa) tramite questi numeri floating-point?

5. si disegnino F(10, 1, −1, 1) e F(10, 2, −2, 2); perch´e i numeri floating-point contigui ad 1 sono (in notazione posizionale classica) nel primo caso 0.9 e 2 (non 1.1) e nel secondo caso 0.99 e 1.1 (non 1.01)?

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

7. la precisione di macchina, ε

= β

/2, non `e il pi` u piccolo numero floating-point

positivo (che invece `e ...)

8. 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 di cui 1 per il segno e 10 per il valore assoluto, si calcolino la precisione di macchina e gli estremi L ed U dell’intervallo degli esponenti; quali sono gli ordini di grandezza di ε

, max F

e min F

in base 10?)

1.3 Propagazione degli errori

1. in un’aritmetica a base 10 con 16 cifre di mantissa, 1 + 10

viene calcolato corret- tamente ma 1 + 10

= 1; perch´e? (si osservi che questo `e un esempio di non unicit` a dell’elemento neutro)

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

= min {µ ∈ F

: 1 + µ > 1}

3. 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; trac- cia: si utilizzi la disuguaglianza triangolare); quali operazioni si possono considerare

“stabili”? in quali situazioni la sottrazione fa perdere precisione? si facciano esempi 4. 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

5. 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?

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

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

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

9. si riscrivano, se necessario, le seguenti espressioni per ovviare a possibili instabilit`a in

aritmetica di macchina:

E

(x) = x

/(2 + x

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

+ 5)

E

(x) = √

x

+ 1 − |x| + 100x E

(x) = 3 √

x

+ 2 − (10x

+ 1)/(x

+ 1) + 10x

10. la successione definita da x

= 2, x

= 2

q

1 − p1 − 4

x

, n = 2, 3, . . . (“successione di Archimede”), soddisfa lim

x

= π, 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?

11. in figura gli errori relativi (in scala logaritmica) nell’approssimazione di π con la successione S

= q

6 P

j=1 1

j²

, n = 1, 2, 3, . . . (triangolini; stabile ma a convergenza lentissima, si stimi l’errore assoluto tramite il resto della serie P

j=1 1

j²

= π

/6), con la successione di Archimede del punto (10) (pallini, convergente ma instabile) e con la corrispondente versione stabilizzata (asterischi); perch`e con entrambe le versioni della successione di Archimede l’errore diventa ad un certo punto praticamente costante?

0 10 20 30 40 50 60 70 80 90 100

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

Tracce di calcolo numerico

Prof. Marco Vianello - Dipartimento di Matematica, Universit` a di Padova aggiornamento: 18 settembre 2015

2 Soluzione numerica di equazioni non lineari

2.1 Metodo di bisezione e metodo di Newton

1. data una funzione f ∈ C[a, b] (cio`e, f continua in [a, b]), tale che f (a)f (b) < 0, si dimostri che la successione x

, x

, . . . , x

, . . ., costruita col metodo di bisezione (uti- lizzando 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. utilizzando la stima del punto 1, si calcoli il minimo numero di iterazioni del metodo di bisezione che garantisce un errore minore di ε, dove ε > 0 `e una tolleranza prefissata 3. data una funzione continua f tale che f (ξ) = 0 ed una successione {x

} tale che lim

x

= ξ, perch´e in generale il “residuo” |f (x

)| non `e una buona stima dell’errore? (si disegni il possibile andamento locale di f , se il grafico `e “piatto”

...); come va corretto il residuo utilizzando la derivata di f ? (residuo pesato)

(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 (ξ) = f

(α

)(x

− ξ), α

∈ int(x

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

4. se |f

(x)| ≥ k > 0 in [c, d], come pu`o essere stimato l’errore tramite il residuo?

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

e

= |ξ − x

| ≈ |f (x

)|

x

− x

f (x

) − f (x

)     6. si dia un’interpretazione geometrica del metodo di Newton

x

= x

− f (x

)

f

(x

) , f

(x

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

7. un risultato di convergenza globale del metodo di Newton: data f ∈ C

[a, b], tale che f (a)f (b) < 0, con 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]

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

(traccia: ci sono 4 configurazioni possibili (disegnarle); le tangenti alla curva grafico stanno sempre sopra o sotto la curva, la successione {x

} `e monotona e limitata, quindi ha limite finito che `e ..., passando al limite nella definizione del metodo ...) 8. 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: utilizzando la formula di Taylor calcolata nella radice e centrata in x

, 0 = f (ξ) = f (x

) + f

(x

)(ξ − x

) +

( (ξ − x

)

, dove z

∈ int(x

, ξ), in- sieme alla definizione di {x

}, si ottiene ξ − x

=

n)

(ξ − x

)

, e ... C = max

|f

(x)|/(2 min

|f

(x)|)

∗ approfondimento: partendo da tale disuguaglianza, perch`e ci si aspetta conver- genza locale? (cio`e, partendo in un intorno opportuno della soluzione? si osservi che Ce

≤ (Ce

)

, da cui Ce

≤ (Ce

)

)

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

10. si mostri che il metodo di Newton per il calcolo della radice k-esima di un numero reale a > 0, assume la forma

x

= k − 1

k x

+ a kx

, n = 0, 1, 2, . . .

(gi` a nota in antichit` a come metodo di Erone nel caso della radice quadrata), dove x

va scelto tale che x

> a

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

(traccia: si ragioni sull’errore relativo, ρ

= e

/|ξ|; col metodo di bisezione “in media”

ρ

≈ ρ

/2, ...; col metodo di Newton ρ

≤ C|ξ|ρ

, quindi se C|ξ| ≤ 1 si ha che ρ

≤ ρ

...)

12. in figura gli errori relativi (in scala logaritmica) nell’approssimazione di √

2 con il metodo di bisezione (errore effettivo: pallini; stima a priori: puntini; stima del residuo pesato: asterischi) e con il metodo di Newton (errore effettivo: quadratini; stima dello “step”, e

≈ |x

− x

|: triangolini); si osservi che lo step |x

− x

| =

|f (x

)|/|f

(x

)| `e per costruzione un residuo “pesato”

0 10 20 30 40 50 60 70 10⁻²⁰

10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰

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

14. si studi la risolubilit`a dell’equazione x − e

= 0, α > 0, con i metodi di bisezione e di Newton (l’equazione pu` o anche essere interpretata come intersezione di grafici) 2.2 Iterazioni di punto fisso

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

= φ(x

), n = 0, 1, 2, . . ., converge all’unico punto fisso di φ in I, ovvero ξ ∈ I tale che ξ = φ(ξ) (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 (facoltativo): si provi che valgono le disuguaglianze

|x

− x

| ≤ (1 + θ + θ

+ . . . + θ

)|x

− x

| ≤ (θ

/(1 − θ))|x

− x

|, da cui si vede che la successione {x

} `e di Cauchy, quindi ha limite in I ...)

2. 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 θ?)

3. 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 per il teorema del valor medio |x

− ξ| =

|φ(x

) − φ(ξ)| = |φ

(z

)| |x

− ξ| ≤ θ |x

− ξ|; per la seconda si osservi che x

− x

= x

− ξ + ξ − x

= φ

(z

)(x

− ξ) + ξ − x

, ...)

4. si mostri che l’equazione x − e

= 0, 0 < α < 1, `e risolubile con le iterazioni di punto fisso; quante iterazioni occorrono per garantire un errore assoluto < 10

con α = 1/5 ?

5. ordine di convergenza delle iterazioni di punto 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 6. 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 un’iterazione di punto fisso

con φ(x) = x − f (x)/f

(x), quindi se f

(ξ) 6= 0 si ha che φ

(ξ) = 0 ...)

Tracce di calcolo numerico

Prof. Marco Vianello - Dipartimento di Matematica, Universit` a di Padova aggiornamento: 18 settembre 2015

3 Interpolazione e approssimazione

3.1 Interpolazione polinomiale

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 f

in una opportuna famiglia di funzioni F

, tale che

f

(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) = f

(x) il polinomio interpolatore) 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 dist(f

, f ) = max

x∈[a,b]

|f

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

(traccia: se esistessero due polinomi interpolatori distinti, la loro differenza si an- nullerebbe in tutti i nodi e per il teorema fondamentale dell’algebra ...)

4. si mostri che Π

(x) =

n

X

i=0

f (x

) ℓ

(x) , ℓ

(x) = (x − x

) . . . (x − x

)(x − x

) . . . (x − x

) (x

− x

) . . . (x

− x

)(x

− x

) . . . (x

− x

)

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

, x

, . . . , x

} (si tratta della cosiddetta “forma di Lagrange” del polinomio interpolatore; siccome ℓ

(x

) = δ

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

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

7. ∗ con la forma di Lagrange dell’errore di interpolazione polinomiale di grado n per f ∈ C

[a, b], si dimostra che dist(Π

, f ) ≤ max

{|f

(x)|} (b − a)

/(n + 1)!, e che nel caso di nodi equispaziati dist(Π

, f ) ≤ max

{|f

(x)|} h

/(4(n + 1)) dove h = (b − a)/n (dim. non richiesta); perch´e da questa stime non si pu` o dedurre la convergenza per f ∈ C

[a, b]? (si pensi al controesempio di Runge, f (x) = 1/(1+x

), x ∈ [−5, 5], in cui accade che dist(Π

, f ) → ∞, n → ∞; in figura i grafici della funzione di Runge e del polinomio interpolatore di grado 10 su 11 nodi equispaziati, si notino le oscillazioni dell’interpolatore verso gli estremi)

−5 −4 −3 −2 −1 0 1 2 3 4 5

−0.5 0 0.5 1 1.5 2

8. interpolazione di Chebyshev: abbiamo visto che in generale i polinomi interpolatori non convergono alla funzione campionata (controesempio di Runge su nodi equis- paziati); scelte speciali dei nodi per` o assicurano tale convergenza, `e il caso ad esempio dell’interpolazione polinomiale sui nodi di Chebyshev

x

= b − a

2 cos  iπ n



+ b + a

2 , 0 ≤ i ≤ n ,

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

non richiesta) che, detto Π

(x) il polinomio interpolatore sui nodi di Chebyshev, per ogni f ∈ C

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

tale che

dist(Π

, f ) = max

x∈[a,b]

|Π

(x) − f (x)| ≤ c

log(n) n

,

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

9. ∗ si mostri 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 osservi che Λ

dipende solo dai nodi di interpolazione

(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)| ≤ ...)

10. `e noto che per qualsiasi distribuzione di nodi la costante di Lebesgue ha crescita almeno logaritmica, Λ

≥ c

log n, che per i nodi equispaziati Λ

∼ c

(instabilit`a), mentre per i nodi di Chebyshev Λ

= O(log n) (c

e c

sono opportune costanti) 3.2 Interpolazione polinomiale a tratti

1. nell’interpolazione polinomiale a tratti di grado s su x

= a < x

< . . . < x

= b, dove n `e multiplo di s, si costruisce una funzione continua Π

(x) tale che Π

(x) sia il polinomio interpolatore di grado fissato s sui nodi x

, x

, . . . , x

, 0 ≤ k ≤

−1 (si osservi che Π

(x) si ottiene “incollando” per continuit` a pezzi polinomiali e che in generale i punti di raccordo x

sono punti angolosi della funzione interpolante) 2. si dimostri che l’interpolazione lineare a tratti (s = 1, 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

(traccia: si utilizzi su ogni intervallino [x

, x

] la stima dell’errore di interpolazione polinomiale di grado 1)

3. ∗ si dimostri che l’interpolazione quadratica a tratti (s = 2, disegnarla) converge uniformemente 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 di grado 2)

4. nell’interpolazione spline di grado s 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 s e S

(x

) = f (x

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

5. `e noto che se f ∈ C

[a, b], dist(S

, f

) = O(h

), 0 ≤ j ≤ 3 (le derivate di S

non sono per` o interpolanti)

6. nella prima figura i grafici della funzione di Runge e delle spline interpolanti lineare e cubica (tratteggiata) su 11 nodi equispaziati, nella seconda figura un particolare

−5 −4 −3 −2 −1 0 1 2 3 4 5

−0.5 0 0.5 1 1.5 2

−1.50 −1 −0.5 0 0.5 1 1.5 0.5

1 1.5

3.3 Approssimazione polinomiale ai minimi quadrati

1. dato un campionamento {(x

, y

)}, y

= f (x

), 1 ≤ i ≤ N , nell’approssimazione ai minimi quadrati invece di interpolare si cerca un polinomio p di grado m < N (tipicamente m ≪ N ) tale che la somma degli scarti quadratici P

i=1

(y

− p(x

))

sia minima, ovvero si risolve il problema di minimo in m + 1 variabili a = (a

, . . . , a

)

min

a∈R^m+1 N

X

i=1

(y

− (a

+ a

x

+ . . . + a

x

))

che ha soluzione unica, calcolabile risolvendo il 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, si veda la sezione di Algebra Lineare Numerica)

2. in figura il polinomio dei minimi quadrati di grado m = 8 (puntini) e di grado m = 10 (tratteggio), ottenuti da un campionamento con rumore su N = 200 punti (linea frastagliata) della funzione sin(10x) in [−1, 1] (linea continua)

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−2

−1.5

−1

−0.5 0 0.5 1 1.5

Tracce di calcolo numerico

Prof. Marco Vianello - Dipartimento di Matematica, Universit` a di Padova aggiornamento: 18 settembre 2015

4 Integrazione numerica e derivazione numerica

4.1 Integrazione numerica (formule di quadratura)

1. l’operazione funzionale di integrazione (nel continuo) `e “stabile”: si dimostri infatti che, data una funzione continua ˜ f che approssima una funzione continua f su [a, b], vale la seguente stima

Z

f (x) dx − ˜ Z

a

f (x) dx   

 ≤ (b − a) dist( ˜ f , f )

2. in particolare, detta {f

} una successione di funzioni continue che converge uniforme- mente alla funzione continua f su [a, b],

Z

a

f

(x) dx − Z

a

f (x) dx   

 ≤ (b − a) dist(f

, f ) , quindi la successione degli integrali delle f

converge all’integrale di f

3. l’idea alla base delle formule di integrazione approssimata (formule di quadratura) `e di sostituire ad f un’opportuna interpolante f

; si verifichi che le formule di quadratura algebriche (spesso dette anche “interpolatorie”, quelle ottenute integrando un unico polinomio interpolatore su tutti i nodi, ovvero con f

= Π

) 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

Z

Π

(x) dx = Z

a n

X

i=0

f (x

)ℓ

(x) dx =

n

X

i=0

. . .

4. ∗ lo stesso vale anche per le formule composte, quelle ottenute integrando un’interpolante polinomiale a tratti di grado locale fissato s (ovvero con f

= Π

), che sono localmente algebriche, cio`e ottenute integrando un singolo polinomio interpolatore di grado s in [x

, x

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

5. nel caso di campionamento a passo costante, facendo prima un disegno esplicativo con interpretazione geometrica, si ricavino la formula di quadratura composta di grado 1, detta dei trapezi,

Z

Π

(x) dx = h

2 (f (a) + f (b)) +

n−1

X

i=1

hf (x

)

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

e ∗ la formula di quadratura composta di grado 2, detta di Cavalieri-Simpson (o delle parabole, n pari)

Z

a

Π

(x) dx = h

3 (f (a) + f (b)) +

n−2

X

i=2,i pari

2h

3 f (x

) +

n−1

X

i=1,i dispari

4h 3 f (x

)

6. la convergenza delle formule algebriche dipende dalla distribuzione dei nodi: si mostri che le formule ottenute integrando il polinomio interpolatore sui nodi di Chebyshev sono convergenti (invece le formule algebriche di Newton-Cotes, ottenute integrando il polinomio interpolatore su nodi equispaziati, non sono convergenti; dim. non richiesta) 7. ∗ 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?)

8. ∗ abbiamo visto che la “risposta alle perturbazioni” su f dell’interpolazione polinomi- ale `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 S

= P

i=0

|w

| svolge un ruolo analogo nel caso delle formule di quadratura interpolatorie e composte

n

X

i=0

w

f (x

) −

n

X

i=0

w

f (x ˜

)     

≤ S

dist(f, ˜ f )

9. perch´e in particolare le formule interpolatorie e composte con pesi positivi sono sicu- ramente stabili?

traccia: tali formule sono esatte (cio`e fanno errore nullo) sui polinomi costanti, quindi S

=

n

X

i=0

|w

| =

n

X

i=0

w

=

n

X

i=0

w

· 1 = Z

a

1 dx = b − a

10. si pu` o dimostrare (dim. non richiesta) che le formule algebriche di Newton-Cotes (algebriche su nodi equispaziati) hanno pesi non tutti positivi per n > 7 e sono instabili perch`e S

diverge esponenzialmente per n → ∞; invece (dim. non richiesta) le formule algebriche sui nodi di Chebyshev hanno pesi positivi, quindi sono stabili (oltre che convergenti)

4.2 Derivazione numerica

1. l’operazione funzionale di derivazione (nel continuo) non `e stabile; infatti detta Df la derivata di f

dist(f

, f ) → 0 6=⇒ dist(Df

, Df ) → 0 , n → ∞

come si vede considerando ad esempio la successione di funzioni f

(x) =

sin(nx), x ∈ [0, 1], visto che dist(f

, 0) ≤ 1/n `e infinitesima per n → ∞ ma dist(Df

, 0) ≡ 1 2. l’instabilit`a dell’operazione funzionale di derivazione si pu` o parafrasare con “funzioni

arbitrariamente vicine possono avere derivate arbitrariamente distanti”, ad esempio

si pu` o stare arbitrariamente vicini ad una funzione oscillando con frequenza arbitrari-

amente elevata (per un esempio grafico si veda la figura dopo 3.3.2, confrontando la

linea continua con la linea frastagliata)

3. tale instabilit`a viene ereditata dalle formule di approssimazione della derivata: perch´e nella derivazione numerica con il rapporto incrementale

δ

(h) = f (x + h) − f (x)

h = Df (x) + O(h) , f ∈ C

,

conviene prendere un passo dell’ordine di √ ε, dove ε `e il massimo errore su f ? traccia: si utilizzi la formula di Taylor al primo ordine con resto del secondo ordine per mostrare che |Df (x)−δ

(h)| ≤ Ah con A costante opportuna; detto poi ε = dist(f, ˜ f ) il massimo errore su f e detto ˜ δ

(h) = ( ˜ f (x + h) − ˜ f (x))/h il rapporto incrementale

“perturbato”, l’errore effettivo nell’approssimazione della derivata ha una stima del tipo |Df (x) − ˜δ

(h)| ≤ |Df (x) − δ

(h)| + |δ

(h) − ˜δ

(h)| ≤ E(h) = Ah + 2ε/h, minimizzando in h ... si ottiene un passo ottimale h

proporzionale a ε

e un minimo E(h

) = O(ε

)

4. l’analisi precedente pu` o essere estesa all’approssimazione della derivata con il rapporto incrementale “simmetrico”

δ(h) = f (x + h) − f (x − h)

2h = Df (x) + O(h

) , f ∈ C

,

traccia: in questo caso si ha una stima del tipo |Df (x) − ˜δ(h)| ≤ E(h) = Bh

+ ε/h con B costante opportuna (utilizzare la formula di Taylor al secondo ordine con resto del terzo ordine, f (x + h) = . . . e f (x − h) = . . .), minimizzando in h ... si ottiene un passo ottimale h

proporzionale a ε

e un minimo E(h

) = O(ε

)

5. in figura i grafici (scala loglog) delle stime di errore E(h) nel calcolo della derivata di f (x) = sin(x) in x = 0 con δ

(h) (linea continua) e δ(h) (linea tratteggiata), per ε = 10

10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

10⁻⁴ 10⁻² 10⁰ 10² 10⁴ 10⁶

4.3 Estrapolazione

1. 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 φ(h) − φ(h/2)

2

− 1 = c  h 2



+ O(h

) , |φ(h/2) − α| ≈ |c|  h 2



≈ |φ(h) − φ(h/2)|

2

− 1

• una nuova approssimazione con errore di ordine O(h

) (estrapolazione) 2

φ(h/2) − φ(h)

2

− 1 = α + O(h

)

2. si verifichi che il rapporto incrementale standard δ

(h) e quello “simmetrico” δ(h) 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)

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

4. ∗ il procedimento di estrapolazione pu`o essere iterato per φ(h) = α + c

h

+ c

h

+ . . . + c

h

+ O(h

), 0 < p

< p

< . . . < p

< p

traccia: si utilizzi una sequenza di passi h = h

, h

/2, h

/4, h

/8, . . ., e la formula φ

(h) = φ(h) , φ

(h) = 2

φ

(h/2) − φ

(h)

2

− 1 , i = 1, . . . , m ,

ottenendo φ

(h) = α + O(h

); il procedimento viene implementato con la tabella di estrapolazione

i = 0 i = 1 i = 2 i = 3 i = 4

φ

(h

)

φ

(h

/2) φ

(h

)

φ

(h

/4) φ

(h

/2) φ

(h

)

φ

(h

/8) φ

(h

/4) φ

(h

/2) φ

(h

)

φ

(h

/16) φ

(h

/8) φ

(h

/4) φ

(h

/2) φ

(h

)

5. ∗ la tabella di estrapolazione si pu`o utilizzare per f ∈ C

con φ(h) = δ

(h), p

= i, oppure f ∈ C

con φ(h) = δ(h), p

= 2i, i = 1, . . . , m (chi sono i coeff. c

nei due casi? traccia: utilizzare la formula di Taylor)

6. gli errori |φ

(h) − Df (0)| (con una cifra significativa) nel calcolo della derivata di f (x) = e

in x = 0 con la tabella di estrapolazione a partire da φ

(h) = δ(h), h

= 1/2

i = 0 i = 1 i = 2 i = 3 i = 4

h = 1/2 4 · 10

h = 1/4 1 · 10

1 · 10

h = 1/8 3 · 10

8 · 10

5 · 10

h = 1/16 7 · 10

5 · 10

8 · 10

3 · 10

h = 1/32 2 · 10

3 · 10

1 · 10

1 · 10

7 · 10

Tracce di calcolo numerico

Prof. Marco Vianello - Dipartimento di Matematica, Universit` a di Padova aggiornamento: 27 novembre 2015

5 Elementi di algebra lineare numerica

5.1 Condizionamento di matrici e sistemi

1. partendo dalla definizione di norma matriciale indotta da una norma vettoriale, kAk = sup

kAxk/kxk, si dimostrino le disuguaglianze fondamentali per le norme matriciali indotte: (i) kAxk ≤ kAk kxk e (ii) kABk ≤ kAk kBk (dove A, B ∈ R

e x ∈ R

) 2. si ricordi che kAk

= max

{ P

j=1

|a

|} e kAk

= pρ(A

A), dove ρ(B) `e il

“raggio spettrale” di una matrice B, ρ(B) = max

{|λ

|, λ

autovalore di B}

(dimostrazioni non richieste)

3. stima 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 ≥ 1 `e l’indice di condizionamento di una matrice invertibile nella norma matriciale indotta dalla norma vettoriale

(traccia: si utilizzi la prima disuguaglianza fondamentale per mostrare che kδxk ≤ kA

k kδbk e kxk ≥ kbk/kAk, ...; per dimostrare che k(A) ≥ 1, si osservi che kIk = 1 = kA A

k ≤ kAk kA

k per la seconda disuguaglianza fondamentale)

4. ∗ si ha 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 (dimostrazione facoltativa): se λ `e autovalore di A e v 6= 0 autovettore cor- rispondente, 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

, ...)

5. si consideri il seguente esempio:

A

 x

x



=

 1 0.7

 , A

 x ˜

˜ x



=

 1.01 0.69



, A =

 7 10 5 7

 , dove

A

=

 −7 10

5 −7

 ,

 x

x



=

 0 0.1

 ,

 x ˜

˜ x



=

 −0.17 0.22



; si ha che kδbk

/kbk

= 10

ma kδxk

/kxk

> 1; in effetti, K

(A) = . . .

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

6. risposta della soluzione di un sistema lineare agli errori sulla matrice: dato il sistema quadrato Ax = b con det(A) 6= 0, b 6= 0 e il sistema perturbato (A + δA)(x + δx) = b, con det(A + δA) 6= 0, si mostri che vale la stima

kδxk

kx + δxk ≤ k(A) kδAk kAk ,

cio´e in sostanza il ruolo di k(A) `e analogo al caso della risposta agli errori sul vettore termine noto

(traccia: da (A + δA)(x + δx) = b si ricava δx = −A

δA(x + δx) e usando la prima disuguglianza fondamentale per una norma indotta ...)

7. un teorema fondamentale di invertibilit` a: se kAk < 1 in una norma matriciale indotta, allora I ± A `e invertibile e si ha k(I ± A)

k ≤

(dimostrazione non richiesta)

8. ∗ si pu` o dimostrare 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



(traccia (dimostrazione facoltativa): partendo da (A + δA)δx = δb − δAx e osser- vando che (A + δA) = A(I + B) con B = A

δA e kBk ≤ kA

k kδAk < 1, per il teorema fondamentale di invertibilit` a e le disuguaglianze fondamentali δx = (A + δA)

(δb−δAx) = (I +B)

A

(δb−δAx) e kδxk ≤ k(I +B)

k kA

k kδb−δAxk ≤

kA⁻¹k

1−kA⁻¹δAk

kδb − δAxk ≤

kδb − δAxk ≤

(kδbk + kδAk kxk), da cui

≤ · · · )

9. ∗ (cenni di approfondimento facoltativi): la soluzione di sistemi lineari con matrici fortemente mal condizionate (nelle applicazioni non `e infrequente avere indici di con- dizionamento 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 +



1 + ε(h) kxk



k(A

) kδbk kbk da cui si vede che conviene minimizzare in h: come nella derivazione numerica con formule alle differenze (si veda la figura alla fine della sezione 4.2), 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)

5.2 Metodo di eliminazione di Gauss e fattorizzazione LU

1. il metodo di eliminazione di Gauss realizza la sequenza di trasformazioni A

=

A → A

→ A

→ . . . → A

. . . → A

= U (triangolare superiore), dove

a

= 0 per j + 1 ≤ k ≤ n, 1 ≤ j ≤ i (si disegnino le matrici A

e A

con la struttura a trapezio di zeri sotto la diagonale), tramite le operazioni vettoriali sulle righe R

:= R

+



−

(i) ki

a⁽ⁱ⁾ii



R

, k = i + 1, . . . , n (purch´e a

6= 0)

2. cosa succede se al passo i-esimo del metodo di eliminazione a

= 0 e a

= 0 per i + 1 ≤ k ≤ n ?

3. quali sono gli scopi del pivoting nel metodo di eliminazione di Gauss? (si pensi al caso in cui un elemento diagonale diventa nullo, oppure molto piccolo in modulo; nel secondo caso, si vuole evitare la creazione di numeri approssimati grandi in modulo, che nelle sottrazioni portano a potenziale perdita di precisione)

4. si mostri che il costo computazionale del metodo di eliminazione di Gauss `e O(n

) flops (floating-point operations), scrivendo lo schema dell’algoritmo

facoltativo: si dimostri che il costo computazionale effettivo `e ∼

n

flops

5. si mostri che il costo computazionale della soluzione di un sistema con matrice tri- angolare superiore o inferiore `e O(n

) flops, scrivendo lo schema dell’algoritmo di sostituzione all’indietro (caso triangolare superiore) e di sostituzione in avanti (caso triangolare inferiore)

6. il metodo di eliminazione di Gauss pu` o essere usato per calcolare il determinante di una matrice quadrata (in effetti det(A) = (−1)

det(U ) = (−1)

Q

i=1

u

dove s `e il numero di scambi tra righe); il costo computazionale della formula ricorsiva di Laplace per il determinante `e ∼ 2n! flops: in tabella gli ordini di grandezza dei tempi di calcolo dei due metodi per diversi valori (relativamente piccoli) di n con un computer da 1Gigaflops (10

flops al secondo) e da 1Petaflops (10

flops al secondo)

1Gflops 1Pflops

n Laplace Gauss Laplace Gauss

10 10

sec 10

sec 10

sec 10

sec

15 40 min 3 · 10

sec 2 millisec 3 · 10

sec 20 10

anni 8 · 10

sec 80 min 8 · 10

sec

25 10

anni 10

sec 10

anni 10

sec

100 10

anni 10

sec 10

anni 10

sec

7. si pu` o dimostrare (dim. non richiesta) che il metodo di eliminazione di Gauss con piv- oting 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); la soluzione di un sistema Ax = b con il metodo di eliminazione `e equivalente alla fattorizzazione LU seguita dalla soluzione della coppia di sistemi triangolari Ly = P b, U x = y

8. 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 {e

}, quindi le colonne di A

, c

= A

e

, corrispondono alle soluzioni

degli n sistemi Ac

= e

, ...)

9. perch`e la fattorizzazione P A = LU calcolata in aritmetica di macchina, diciamola L ˜ ˜ U ≈ P A) `e estremamente accurata (cio`e, gli elementi di ˜ L ˜ U coincidono alla preci- sione di macchina con quelli di P A), ma per certe matrici (vedi matrice di Hilbert H = (h

), h

= 1/(i + j − 1), 1 ≤ i, j ≤ n) la soluzione di sistemi ottenuta con tale fattorizzazione risulta molto poco accurata (se non addirittura completamente sbagliata)?

(traccia: in sostanza `e come se si risolvesse il sistema perturbato ˜ L ˜ U (x + δx) = P b, ...; in figura l’errore relativo in k · k

nella soluzione in aritmetica a precisione doppia di Hx = Hu, u = (1, . . . , 1)

(pallini), le quantit` a K

(H) (quadratini) e K

(H) · eps (asterischi), per n = 2, . . . , 30)

0 5 10 15 20 25 30

10⁻²⁰ 10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰ 10⁵ 10¹⁰ 10¹⁵ 10²⁰

5.3 Sistemi sovradeterminati, minimi quadrati e fattorizzazione QR 1. sia A ∈ R

, m > n, una matrice di rango massimo n (ovvero, le colonne di A

sono n vettori linearmente indipendenti di R

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





2

`e equivalente a risolvere il sistema con matrice simmetrica non singolare (e definita positiva) A

Ax = A

b (detto “sistema delle equazioni normali”)

(∗ 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 u fissato, per ε → 0 si ottiene (A

(Ax − b), u) ≥ 0 ∀u ∈ R

, ma allora prendendo −u al posto di u si ottiene (A

(Ax − b), u) ≤ 0 ∀u, da cui ...; per dimostrare che A

A `e non singolare, si osservi che se A

Av = 0 allora (A

Av, v) = (Av, Av) = 0 da cui Av = 0, ma le colonne di A sono linearmente indipendenti quindi v = 0)

2. l’approssimazione polinomiale di grado k ai minimi quadrati pu` o essere reinterpretata

come soluzione ai minimi quadrati del sistema m × n (sovradeterminato) V a = y (si

veda la sezione 3.3), dove m = N e n = k + 1

(traccia: per provare che V ha rango massimo, 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 ...)

3. sia A ∈ R

, m ≥ n, una matrice di rango massimo: si pu` o dimostrare (dim. non richiesta) che A ammette una fattorizzazione A = QR, dove Q ∈ R

`e una ma- trice ortogonale (ovvero le colonne di Q sono vettori ortonormali, cio`e Q

Q = I ∈ R

) e R `e una matrice triangolare superiore non singolare (si tratta in sostanza di un procedimento equivalente all’ortogonalizzazione di Gram-Schmidt delle colonne di A: la matrice R

, che resta triangolare superiore, `e la matrice dei coefficienti dell’ortogonalizzazione: si controlli che il prodotto A R

corrisponde a costruire com- binazioni lineari ortonormalizzanti delle colonne di A utilizzando i coefficienti delle colonne di R

)

4. come si pu` o applicare la fattorizzazione QR alla soluzione di sistemi sovradeterminati?

(traccia: utilizzando A = QR, non `e necessario calcolare la matrice A

A perch´e A

A = R

R, quindi il sistema delle equazioni normali diventa R

Rx = R

Q

b che `e equivalente (perch´e?) al sistema triangolare Rx = Q

b)

5. dal punto di vista del condizionamento `e meglio risolvere Rx = Q

b invece di A

Ax = b, perch´e l’indice di condizionamento di R in norma 2 `e molto pi´ u piccolo dell’indice di condizionamento di A

A (dimostrazione non richiesta; si pu` o intuire osservando che se A `e quadrata e simmetrica, k

(A

A) = k

(A

) = (k

(A))

)

5.4 Metodi iterativi

1. 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, ma kBk < 1 e per il teorema fondamentale di invertibilit` a ...; scrivendo x − x

= B(x − x

) si ottiene la stima kx − x

k ≤ kBk kx − x

k, ...)

2. 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) (traccia della dim. (facoltativa) nel caso B sia diagonalizzabile: scrivendo x

, c in una base {v

} di autovettori di B, Bv

= λ

v

, 1 ≤ i ≤ n, x

= P α

v

, c = P γ

v

, si ottiene x

= P 

α

λ

+ γ

(1 + λ

+ . . . + λ

) 

v

, che ha limite ∀ x

, c se e solo se

|λ

| < 1, 1 ≤ i ≤ n, con vettore limite lim

x

= P

1−λi

v

= (I − B)

c )

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