Soluz v1

Fazer download em pdf ou txt
Fazer download em pdf ou txt
Você está na página 1de 5

Prima Prova in Itinere

21/04/2021 — versione 1 — ♦♣♥♠♣♦♠♣♥♠

32 pt – durata 1h 30’ – MS Forms


Gli studenti aventi diritto a svolgere la prova ridotta del 30% secondo la L.170/2010
(indicazioni Multichance team) NON svolgono i quesiti contrassegnati con (***)

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.

Spazio per risposta lunga

Punto 2) — 2 pt
Posto n = 100, la matrice A è la matrice pentadiagonale seguente:

A = pentadiag ( 1, −8, 14, −8, 1 ) ∈ R100×100 .

Si assegni la matrice A in Matlabr e si verifichi che A è simmetrica e definita pos-


itiva; si giustifichi la risposta data riportando valori numerici laddove necessario.
Spazio per risposta lunga

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)

Punto 6) — 3 pt (***) No Multichance


Si consideri il metodo del gradiente precondizionato per generiche matrici A e
P ∈ Rn×n simmetriche e definite positive, con P in aggiunta tridiagonale.
• Quale metodo è computazionalmente conveniente usare per risolvere il sis-
tema lineare associato al residuo precondizionato ad ogni iterazione?
• Si fornisca una stima del numero di operazioni richiesto dall’algoritmo del
gradiente precondizionato impiegando il metodo precedente e sapendo che
le iterazioni effettuate sono pari a k.
• Quando tale algoritmo diventa computazionalmente conveniente rispetto al
metodo della fattorizzazione di Cholesky per risolvere il sistema lineare?

Spazio per risposta lunga (Thomas, O(2(k + 1)n2 ), k < n/6)

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:

Algorithm 1: Metodo delle potenze per problema agli autovalori


generalizzato
Dato x(0) ∈ Cn , con kx(0) k = 6 0;
(0)
x
y(0) = ;
kx(0) k
(y(0) )H A y(0)
λ(0) = (0) H ;
(y ) P y(0)
for k = 1, 2, . . ., fino a che un criterio d’arresto è soddisfatto do
risolvere P x(k) = A y(k−1) ;
x(k)
y(k) = ;
kx(k) k
(y(k) )H A y(k)
λ(k) = (k) H ;
(y ) P y(k)
end

Si implementi il precedente algoritmo modificando opportunamente la funzione


Matlabr eigpower.m. Lo si applichi poi alle matrici A del Punto 2) e P = P2 del
Punto 5) partendo dal vettore iniziale x(0) = 1 ∈ R100 . Si riportino le approssi-
mazioni λ(0) , λ(1) e λ(100) di λmax (P2−1 A). Infine, si usi opportunamente λ(100)
per determinare i valori del parametro α del metodo di Richardson stazionario
precondizionato che garantiscono la convergenza del metodo per ogni scelta del
dato iniziale.
Spazio per risposta breve
(λ(0) = 0.1154, λ(1) = 2.4046, λ(100) = 3.5293, 0 < α < 0.5667)

Você também pode gostar