Soluz v1
Soluz v1
Soluz v1
TEST – 15 pt
1 — 1 pt
Sia dato l’insieme dei numeri floating point F(2, 3, −2, U ) dipendente dal parametro
U ∈ N. Sapendo che il numero massimo rappresentabile (in base 10) con tale
insieme è xmax = 14, si determini il valore assunto da U .
4
2 — 1 pt (***) No Multichance
Si consideri il seguente algoritmo: dati a0 ∈ R, positivo, e b0 = 1, si pongano
an + bn √ π a0
an+1 = e bn+1 = an bn per n = 0, 1, 2, . . .. Il valore Sn = fornisce
2 2 bn
un’approssimazione di log(4 a0 ) per n “grande”. Posto a0 = 2500, si riporti il
valore approssimato S4 ottenuto applicando l’algoritmo precedente.
9.2173
3 — 2 pt
Il metodo della fattorizzazione QR può essere utilizzato per risolvere il sistema lin-
eare Ax = b con A matrice quadrata non singolare. Esso consiste dei seguenti
passaggi: i) determinazione della fattorizzazione QR di A, ovvero A = Q R,
con R triangolare superiore; ii) determinazione del vettore ausiliario y = QT b;
iii) soluzione
di R x =
y tramite l’algoritmo delle sostituzioni
all’indietro.
Posti
0 3 −1 0 1 0
A= 0 0 2 , b = (1 4 5)T e sapendo che Q = 0 0 1 , si deter-
7 −1 2 1 0 0
minino e si riportino: (R)33 , (y)1 = y1 e (x)1 = x1 .
2, 5, 2/7
1
4 — 2 pt (***) No Multichance
5 −1 −1
Sia data una matrice A = 0 4 −2 dipendente da un parametro γ ∈ R
0 γ 3
con γ 6= −6. Si determinino i valori di tale parametro γ ∈ R tali per cui il metodo
di Gauss–Seidel applicato alla soluzione di un sistema lineare A x = b converge
per ogni scelta dell’iterata iniziale.
−6 < γ < 6
5 — 2 pt
3 −γ 0
Si consideri la matrice A = γ 1 0 dipendente da un parametro γ ∈ R.
1 2 6
Per quali valori di γ è possibile applicare il metodo delle iterazioni QR per il calcolo
degli autovalori di A?
−1 < γ < 1
6 — 2 pt
8
Si consideri la funzione f (x) = − x e l’uso sequenziale dei metodi di
1 + x2
bisezione e Newton per l’approssimazione del suo zero α, come implementato nella
funzione Matlabr biseznewton.m. Si riporti il valore approssimato dello zero
di f (x) ottenuto applicando prima 2 iterazioni del metodo di bisezione a partire
dall’intervallo [−10, 10] e poi 2 iterazioni del metodo di Newton.
1.8281
7 — 1 pt
x−5
Si consideri la funzione f (x) = ex log (7 − x) e il metodo di Newton per
2
l’approssimazione dello zero α = 7. Scelto x(0) “sufficientemente” vicino ad α,
qual è l’ordine di convergenza p atteso per il metodo?
1
8 — 1 pt
Si consideri il metodo di Newton per l’approssimazione dello zero α = 0 della
funzione f (x) = ex/8 − 1. Sapendo che all’iterata x(k) del metodo, comunque già
“sufficientemente” vicina ad α, l’algoritmo si arresta con il residuo
|f (x(k) )| = 10−4 ,
(k) (k)
si riporti il valore stimato dell’errore corrispondente e = x − α.
8 · 10−4
2
9 — 1 pt
Si consideri la funzione di iterazione φ(x) = x (x2 − 3x + 3). Si applichi il metodo
delle iterazioni di punto fisso partendo dall’iterata iniziale x(0) = 1.90. Si riporti
il valore dell’iterata x(3) cosı̀ ottenuta.
1.0581
10 — 2 pt (***) No Multichance
1
Si consideri la funzione di iterazione φ(x) = (x − γ)2 dipendente dal parametro
2
1 p
γ ∈ R tale che γ > − e dotata di due punti fissi, tra cui α1 = γ + 1 − 1 + 2γ .
2
Per quali valori di γ il metodo delle iterazioni di punto fisso converge ad α1 ,
scegliendo l’iterata iniziale “sufficientemente” vicina a α1 ?
1 3
− <γ<
2 2
ESERCIZIO – 17 pt
Si consideri il sistema lineare A x = b, dove A ∈ Rn×n è una matrice simmetrica
e definita positiva, e x, b ∈ Rn per n ≥ 1.
Punto 1) — 3 pt
• Si scriva il problema di minimo associato alla funzione Φ : Rn → R equiva-
lente alla soluzione del sistema lineare A x = b di cui sopra.
• Si riporti l’espressione di Φ nel punto di minimo in termini di A e b.
• Si riporti l’espressione della direzione di discesa della funzione Φ in un gener-
ico punto y ∈ Rn .
• Posto y = 0, si riporti l’espressione della direzione di discesa della funzione
Φ(0) corrispondente.
Punto 2) — 2 pt
Posto n = 100, la matrice A è la matrice pentadiagonale seguente:
3
Punto 3) — 2 pt (***) No Multichance
Si consideri il metodo del gradiente per la soluzione del sistema lineare, con
la matrice A indicata al Punto 2). Senza applicare esplicitamente l’algoritmo,
si stimi il numero di iterazioni kmin necessarie tale metodo iterativo affinché
l’errore in norma A si riduca di un fattore inferiore a tol = 10−3 , ovvero tale che
kx(kmin ) − xkA
< tol. Si giustifichi la risposta data definendo tutta la notazione
kx(0) − xkA
utilizzata.
Spazio per risposta lunga (kmin = 28311)
Punto 4) — 2 pt
Per la matrice A di cui al Punto 2) e il vettore b = (1, 1, . . . , 1)T ∈ R100 si applichi
il metodo del gradiente implementato nella funzione Matlabr richardson.m us-
ando la tolleranza sul criterio d’arresto basato sul residuo normalizzato tol = 10−3 ,
il numero massimo di iterazioni pari a 105 e l’iterata iniziale x(0) = b. Si riportino:
il numero N di iterazioni effettuate, la prima componente della soluzione approssi-
kr(N ) k
mata x1 = x(N ) e il valore del residuo normalizzato rnorm (N )
= .
1 kbk
Spazio per risposta breve
(N = 28200, x1 = 10.3053, (N )
rnorm = 9.9952 · 10−4 )
Punto 5) — 2 pt
Si consideri ora il metodo del gradiente precondizionato per risolvere un sistema
lineare associato alla matrice A di cui al Punto 2). In particolare si considerino le
seguenti matrici di precondizionamento simmetriche e definite positive:
P1 = tridiag ( −1, 2, −1 ) ∈ R100×100 , P2 = tridiag ( −2, 5, −2 ) ∈ R100×100 .
Per quale delle due matrici di precondizionamento precedenti il metodo del gra-
diente precondizionato converge più rapidamente alla soluzione per ogni scelta
dell’iterata iniziale? Si motivi dettagliatamente la risposta data.
Spazio per risposta lunga (P1 , K(P1−1 A) = 1.9979, K(P2−1 A) = 912.7022)
4
Punto 7) — 3 pt
Date due generiche matrici A ∈ Rn×n e P ∈ Rn×n non singolare, gli autovalori
della matrice P −1 A risultano equivalenti al problema agli autovalori generalizzato
A v = λ P v. Sotto opportune ipotesi, λmax (P −1 A) può essere approssimato con
il seguente algoritmo: