ESERCIZIO 1
Dato il sistema lineare
G Y = F G =
1.1) individuare per quali valori dei parametri α e β la matrice G `e definita positiva;
1.2) posto α = 1 e β = 1/4 stabilire se i metodi di Jacobi e di Gauss-Seidel sono adatti ad approssimare la soluzione del sistema lineare;
1.3) in caso di convergenza, specificare per ciascun metodo la scelta dell’approssimazione iniziale.
Soluzione ESERCIZIO 1
1.1) La matrice G `e definita positiva se `e simmetrica e se XT G X ≥ 0 per ogni X ∈ IR3. Per la simmetria deve essere α = 1. Per verificare se G `e definita positiva si pu`o utilizzare il criterio di Sylvester:
det G1 = 3 det G2 = 5 det G3 = det G = 5 β − 3 4
I primi due determinanti principali di testa sono positivi. Il deter-minante di G `e positivo se e solo se
`e definita positiva, quindi il metodo di Gauss-Seidel converge si-curamente. Poich´e la matrice G non `e diagonalmente dominante n´e per righe n´e per colonne, non si pu`o trarre nessuna conclusione sulla convergenza del metodo di Jacobi analizzando le propriet`a della matrice dei coefficienti.
Per quanto riguarda la matrice di iterazione del metodo, data da
CJ = −D−1(L + U ) =
sia la norma 1 che la norma uniforme sono maggiori di 1. Per verificare la convergenza bisogna quindi calcolare il raggio spettrale, cio´e il massimo dei moduli degli autovalori di Cj:
ρ(CJ) = max( 0,
s2
3 ) =
s2
3 ≈ 0.8165 < 1 , quindi anche il metodo di Jacobi `e convergente.
1.3) La convergenza dei metodi `e indipendente dalla scelta dell’ appros-simazione iniziale X(0) ∈ IR3. Una buona scelta pu`o essere X(0) = 0 per il metodo di Gauss-Seidel, del quale non `e stata calcolata la matrice di iterazione, e X(0) = D−1F = QJ per il metodo di Jacobi.
Si suggerisce di fare qualche iterazione di entrambi i metodi per confrontare le differenti velocit`a di convergenza.
ESERCIZIO 2
Sia dato un sistema lineare con matrice
A =
2 α 2 1
−α 5 2
1 1 α
dipendente dal parametro reale α, e vettore dei termini noti b = [5 − 2 1]T:
2.1) stabilire per quali valori del parametro α il metodo di Jacobi con-verge per ogni scelta della approssimazione iniziale X(0);
2.2) scelti α = 52 e X(0) = [0 0 0]T, produrre una stima superiore del numero di iterazioni necessarie affinch`e il metodo fornisca una soluzione con almeno 5 decimali esatti.
Soluzione Esercizio 2
La matrice di iterazione del metodo di Jacobi `e C =
Affinch`e il metodo di Jacobi converga per ogni scelta del punto iniziale,
`e necessario che kCk∞ < 1.
Quindi,
Imponendo kCk∞ < 1 risulta
( |α| > 2 se |α| < √
11 − 1
|α| < 3 se |α| ≥ √
11 − 1
da cui si deduce che il metodo di Jacobi converge in norma infinito se 2 < |α| < 3.
Il numero di iterazioni k necessarie affinch`e la soluzione abbia la preci-sione `e maggiorabile come segue
k > log (1 − kCk∞)
kX(1) − X(0)k∞
! 1
log(kCk∞).
In questo caso, = 0.5 · 10−5, kCk∞ = 52+25 = 109 mentre X(1) = CX(0) + Q = Q = [1 − 2
5
2 5]T e quindi kX(1) − X(0)k∞ = kX(1)k∞ = 1. Ne risulta che
k > log((1 − 9/10) · 0.5 · 10−5)
log(9/10) = 137.70.
Quindi, il numero minimo di iterazioni per raggiungere la precisione richiesta `e k = 138.
ESERCIZIO 3
3.1) Valutare il numero di condizionamento di An al variare di n;
3.2) stabilire per quali n il numero di condizionamento risulta inferiore a 50;
3.3) sia ¯n il valore pi`u grande di n verificante la condizione al punto (2.2). Dare una maggiorazione in norma ∞ dell’errore relativo su
x nel caso in cui la soluzione del sistema sia x = [1, 1]T e il vettore b¯n subisca una perturbazione pari a
δb¯n =
"
5 · 10−2 10−3
#
.
Soluzione ESERCIZIO 3
3.1) La matrice An `e simmetrica e tutti i suoi elementi sono non nega-tivi. Ne segue che kAnk1 = kAnk∞ = max{n + 1, n + 3} = n + 3.
Inoltre, risulta
A−1n = 1 det(An)
"
n2 + 2 −n2 − 1
−n2 − 1 n2
#
e quindi
kA−1n k1 = kA−1n k∞
in quanto si verifica facilmente che det(An) = −1, ∀ n. Ne segue che il numero di condizionamento di An risulta
K(An) = (n + 3)2,
rispetto alle norme k · k1 e k · k∞, quindi il sistema diventa mal condizionato anche per piccoli valori di n.
3.2)
K(An) = (n + 3)2 < 50 ⇔ n < √
50 − 3.
Poich`e n ∈ N, risulta n ≤ 4.
3.3) Si osserva che ¯n = 4. Poich`e x = [1 1]T, risulta bn¯ = [¯n + 1 ¯n + 3]T.
Quindi, kδkbb¯nk∞
¯
nk∞ = 5·10¯n+3−2 e kδxk∞
kxk∞ ≤ K(A¯n)kδb¯nk∞
kbn¯k∞ = (¯n+3)25 · 10−2
¯
n + 3 = 5·10−2(¯n+3) = 3.5·10−1.
ESERCIZIO 4
Si consideri la matrice
A =
4.1) Dopo una opportuna permutazione delle righe, individuare i valori dei parametri γ e δ per i quali la matrice A risulti definita positiva;
4.2) Sia B la matrice definita positiva costruita al punto precedente.
Determinare per quali valori dei parametri il numero di condizion-amento della matrice B risulta minore di 7.
Soluzione ESERCIZIO 4
4.1) Con una permutazione delle righe della matrice A si ottiene la matrice
che risulta simmetrica per γ = −1 e δ = 0. Si verifica facilmente che per questi valori dei parametri la matrice B `e definita positiva.
4.2) Poich`e la matrice B `e simmetrica, il numero di condizionamento in norma 1 o infinito sono coincidenti:
K(B) = kBk · kB−1k ≈ 2.95.
Si suggerisce di calcolare il numero di condizionamento in norma 2.
ESERCIZIO 5 Dato il sistema Ax = b con A =
α 4 1/2
0 2α 1
−1 1 2
e α 6= 0,
5.1) stabilire per quali valori del parametro α i metodi iterativi di Jacobi e Gauss-Seidel convergono alla soluzione del sistema per qualsiasi scelta della approssimazione iniziale;
5.2) posto α = 8, in caso di convergenza dei metodi, stimare il numero minimo di iterazioni necessarie affinch´e l’errore relativo soddisfi
kx − xkk
kxk < 10−8
dove xk `e l’approssimazione prodotta alla k-esima iterazione.
ESERCIZIO 6
Dato il sistema lineare
H A = Y H =
6.1) individuare per i quali valori dei parametri γ e θ la matrice H `e definita positiva;
6.2) posto γ = −1/2 e θ = 2/3 stabilire se i metodi di Jacobi e di Gauss-Seidel sono adatti ad approssimare la soluzione del sistema lineare;
6.3) in caso di convergenza, specificare per ciascun metodo la scelta dell’approssimazione iniziale.
ESERCIZIO 7
7.1) Illustrare in dettaglio un metodo di stima dell’errore commesso sulla soluzione di un sistema lineare in presenza di errori sui dati.
Dare un esempio di matrice mal condizionata e uno di matrice ben condizionata.
7.2) Si consideri il sistema lineare di n equazioni in n incognite AX = B, con matrice dei coefficienti
A =
– Stabilire se esistono valori di n per cui il metodo di Jacobi si-curamente converge alla soluzione del sistema perturbato (A + δA)(X + δX) = B, con δA = diag (−1n, n1, 1n, . . . , 1n, −1n);
– scelto n pari all’intero per cui kδAk∞ = 12, dare una maggio-razione dell’errore relativo kδkXXkk∞
∞ .
ESERCIZIO 8
8.1 Illustrare i teoremi di convergenza dei metodi iterativi per la soluzione di sistemi lineari e descrivere un metodo di stima a priori del numero di iterazioni necessarie affinch`e l’approssimazione abbia un numero stabilito di decimali esatti.
8.2 Discutere la convergenza dei metodi di Jacobi e Gauss Seidel del seguente
si-stema lineare
2 1 00 1 2
8.3 Detto AX = b un sistema lineare equivalente al precedente per il quale il metodo di Jacobi converge per ogni scelta dell’approssimazione iniziale, stabilire se esi-stono valori del parametro β ∈ R per cui il metodo iterativo
Xk+1 = Xk − β(AX¯ k − b¯) converge pi`u velocemente del metodo di Jacobi.
Soluzione
Siano A la matrice del sistema, x il vettore della soluzione e b il vettore dei termini noti. La matrice A non soddisfa le condizioni sufficienti di convergenza dei metodi di Jacobi e di Gauss Seidel. In particolare, A non `e a diagonale dominante per righe o per colonne (una condizione sufficiente per la convergenza dei due metodi iterativi), e neanche simmetrica e definita positiva (condizione sufficiente per la convergenza del metodo di Gauss Seidel). Tuttavia, scambiando la seconda e la terza riga della matrice A, si ottiene la matrice
A¯ =
che risulta a diagonale dominante per righe e per colonne. Inoltre `e simmetrica e definita positiva; infatti il determinante dei minori di testa di A¯ `e positivo:
det(A¯1) = 2 > 0; det(A¯2) = 6 − 1 = 5 > 0; det(A¯) = 12 − 4 = 8 > 0.
Ne segue che i metodi di Jacobi e di Gauss-Seidel convergono alla soluzione del sistema AX¯ = ¯b, con
In questo caso, la matrice di iterazione del metodo di Jacobi `e CJ =
il cui raggio spettrale ρ(CJ) = max {|λi|}1≤i≤3 = 1/√
3. Infatti, gli autovalori λi di CJ sono le soluzioni dell’equazione caratteristica −λ3 + λ/3 = 0.
La matrice di iterazione del metodo iterativo
Xk+1 = Xk − β(AX¯ k − b¯)
`
e C(β) = I−βA¯, con I matrice identit`a . Affinch`e il metodo converga pi`u velocemente del metodo di Jacobi, deve esistere almeno un β per cui
ρ(C(β)) < ρ(CJ), (∗).
Gli autovalori della matrice C(β) sono le soluzioni dell’equazione caratteristica (1 − 2β − λ)2(1 − 3β − λ) − 2β2(1 − 2β − λ) = 0,
non esistono valori di β per cui il metodo iterativo considerato converge pi`u veloce-mente del metodo di Jacobi.
Oss: Alla stessa conclusione si giunge ragionando come segue.
Poich`e per una generica matrice M risulta ρ(M) ≤ kMk, con k · k norma di matrice compatibile, la (∗) `e sicuramente verificata per i valori di β tali che
kC(β)k∞ < ρ(CJ), cio`e
max |1 − 2β| + |β|, |1 − 3β| + 2|β| < 1/√ 3 ovvero
|1 − 3β| + 2|β| < 1/√ 3 che non `e mai soddisfatta.
Tuttavia, in questo caso non si pu`o concludere che non esiste alcun valore di β per cui il metodo iterativo considerato converge pi`u velocemente del metodo di Jacobi.
ESERCIZIO 9
9.1 Illustrare il problema della soluzione di sistemi di equazioni lineari con particolare riferimento ai metodi diretti.
9.2 Si considerino i seguenti sistemi lineari:
εx1 + x2 = 1 x1 + x2 = 2 ,
x1 + 3x2 + 5x3 + 3x4 = −1 2x2 + 4x3 + 3x4 = −1
2x3 + x4 = 1 2x4 = 2
,
3x1 − x2 + 2x3 = 1 9x1 − x2 − 4x3 = 0
−6x1 + 6x3 = 1
.
Stabilire per quali di essi il metodo di eliminazione di Gauss senza pivoting fornisce la soluzione esatta. Motivare la risposta.
ESERCIZIO 10
10.1 Illustrare il problema della soluzione di sistemi di equazioni lineari con particolare riferimento ai metodi diretti.
10.2 Dati i seguenti sistemi lineari dipendenti dal parametro k ∈ R:
stabilire per quali valori di k `e possibile calcolarne la soluzione in modo esatto
usando il metodo di Thomas.
ESERCIZIO 11
11.1 Illustrare dettagliatamente i metodi iterativi per la soluzione di sistemi lineari.
11.2 Stabilire se i seguenti metodi iterativi
X(k+1) = (I − αA)X(k) + βB, α, β ∈ R
X(k+1) = β((1 − α)I − A)X(k) + βB, α, β ∈ R
X(k+1) = D−1(D + A)X(k) + B, con D matrice diagonale: Dii = Aii, ∀ i
possono convergere alla soluzione del sistema lineare AX = B per ogni scelta dell’approssimazione iniziale X0. Motivare la risposta.
ESERCIZIO 12 Si consideri il seguente procedimento iterativo dipendente dal parametro reale ω:
X(k+1) = D(ω)X(k) + F(ω),
12.1 Stabilire se esiste almeno un valore di ω per cui il procedimento iterativo risulta adatto ad approssimare la soluzione del sistema lineare AX = B con A =
12.2 in caso di risposta affermativa, determinare il valore di ω per cui la velocit`a di convergenza al vettore X `e massima;
12.3 stabilire se il procedimento iterativo `e adatto ad approssimare la soluzione del sistema perturbato AX = B¯ con B¯ =
3.1 5.1
. Motivare la risposta.
Riferimenti bibliografici L. Gori, Calcolo Numerico:
Cap. 2 §§ 2.1-2.5, 2.8-2.11
Cap. 4 §§ 4.1-4.6, 4.8, 4.9 (escluso il pivoting totale) 4.10 (solo enunciati dei teoremi), 4.12
L. Gori, M.L. Lo Cascio, F. Pitolli, Esercizi di Calcolo Numerico:
2.1-2.5, 2.10-2.13, 2.17, 2.19 - 2.26, 2.30, 7.7, 7.15, 7.16, 7.19, 7.35, 7.41, 7.49, 7.52, 7.57, 7.58, 7.64