In questa sezione introduciamo le definizioni e propriet`a delle norme vettoriali e matriciali, basilari nella risoluzione numerica dei sistemi algebrici.
5.9. Norme vettoriali. Per norma vettoriale in Rn (o in Cn) si intende la funzione k · k soddisfacente le seguenti proppriet`a:
(a) kxk ≥ 0, qualunque sia x con kxk = 0 se e solo se x = 0; (b) kαxk = |α| kxk, per ogni vettore x e ogni scalare α;
(c) kx + yk ≤ kxk + kyk, qualunque siano x e y.
Le tre norme pi`u frequentemente utilizzate nelle applicazioni sono le seguenti: kxk2 = n X i=1 |xi|2 !1/2
, norma Euclidea (norma 2); kxk1 = n X i=1 |xi|, norma in `1 (norma 1); kxk∞ = max
i=1,...,n|xi|, norma in `∞ (norma infinito).
Ciascuna di esse appartiene alla famiglia delle norme p essendo, per 1 ≤ p < ∞, kxkp = n X i=1 |xi|p !1/p .
La norma ∞ `e cos`ı denominata, in quanto limite delle k · kp per p → ∞. Per cerchio unitario in k · kp si intende l’insieme dei vettori x ∈ Rn con kxkp ≤ 1. `E facile dimostrare che, relativamente alla norma 2, 1 e ∞ abbiamo le rappresentazioni geometriche riportate nella Fig. 5.1: Osserviamo che il terzo cerchio contiene il primo, che a sua volta contiene il secondo. `E facile altres`ı dimostrare che k · kp `e una funzione decrescente di p, da cui segue, in particolare, che
kxk∞ ≤ kxk2 ≤ kxk1, per ogni x ∈ Rn.
Tutte le precedenti considerazioni sono immediatamente estendibili al campo complesso Cn.
5.10. Prodotto interno. Per prodotto interno in Rn si intende un’appli-cazione da Rn a Rn che soddisfa le seguenti propriet`a:
Figura 5.1: Nella prima riga: I cerchi unitari tipici delle norme 2, 1 e ∞, rispettativamente. Nella seconda riga: i tre cerchi unitari in una singola figura.
(a) (x, x) ≥ 0, per ogni x, con (x, x) = 0 se e solo se x = 0;
(b) (αx, y) = α(x, y) per ogni coppia di vettori in Rn e ogni numero reale α;
(c) (x, y) = (y, x), qualunque siano x, y ∈ Rn;
(d) (x, y + z) = (x, y) + (x, z), qualunque siano i vettori x, y e z.
Le stesse propriet`a valgono per vettori in Cn a condizione di sostituire la (c) con la seguente:
(c0) (x, y) = (y, x), qualunque siano x, y ∈ Cn.
Ad ogni prodotto interno si pu`o associare una norma cos`ı definita
kxk = p(x, x) . (5.5) La verifica delle propriet`a (a) e (b) `e immediata. La verifica della (c) [o della (c0)] richiede il ricorso alla seguente
Disuguaglianza di Cauchy-Schwartz:
|(x, y)| ≤ kxk kyk, qualunque siano x, y ∈ Rn.
Per la sua dimostrazione basta osservare che, per le propriet`a (a) e (b) del prodotto interno, il polinomio
`
e non negativo per ogni valore α ∈ R. Di conseguenza, il suo discriminante ∆(P ) = 4|(x, y)|2− (x, x)(y, y) ≤ 0
`
e non positivo e questo equivale a dire che la disuguaglianza `e valida.
Per dimostrare la disuguaglianza triangolare basta infine osservare che (per ogni coppia x, y)
kx + yk2 = (x + y, x + y) = (x, x) + 2(x, y) + (y, y) ≤ (x, x) + 2kxk kyk + (y, y) = (kxk + kyk)2
=⇒ kx + yk ≤ kxk + kyk e dunque la (5.5) definisce una norma.
Implicazione della disuguaglianza triangolare. Nella disuguaglianza triangolare sulla norma segue immediatamente che, qualunque siano x, y,
|kxk − kyk| ≤ kx − yk. (5.6) Per verificare ls (5.6), basta osservare che (per la disuguaglianza triangolare)
kxk = k(x + y) − yk ≤ kx + yk + kyk =⇒ kxk − kyk ≤ kx + yk. kyk = k(y + x) − xk ≤ kx + yk + kxk =⇒ kyk − kxk ≤ kx + yk, dalle quali segue immediatamente la (5.6).
Matrice di Gram. Il seguente risultato `e molto utile nello stabilire la non singolarit`a delle matrici provenienti dalla risoluzione numerica delle equazioni differenziali e di altri problemi applicativi.
Teorema 5.3 Gli n vettori a1, a2, . . . , anin Rnsono linearmente indipendenti se e solo se la corrispondente matrice di Gram
G = {gij}n
i,j=1, gij = (ai, aj), `
e non singolare.
Dimostrazione. E facile verificare che` kc1a1 + . . . + cnank2 = n X i,j=1 cicj(ai, aj) = c1 . . . cn G c1 .. . cn , qualunque siano le costanti reali c1, . . . , cn. Di conseguenza, esistono tali co-stanti ci non tutte nulle tali che c1a1 + . . . + cnan = 0 se e solo se il vettore colonna c1 . . . cn
T
`e autovettore di G corrispondente all’autovalore 0, cio`e gli n vettori a1, a2, . . . , an sono linearmente dipendenti se e solo se la matrice di Gram G `e singolare. 2
Un risultato simile vale per n vettori in Cn.
5.11. Norme matriciali (indotte, naturali). Ad ogni norma vettoriale k · k in Rn si pu`o associare una norma matriciale, per tale motivo, definita indotta o anche naturale.
Definizione. Per ogni A ∈ L(Rn) si ha: kAk = sup
x6=0
kAxk
kxk . (5.7a) Ponendo y = kxkx , la (5.7a), osservato che kAxk = kA(kxk)yk = kxk kAyk e che kyk = 1, diventa
kAk = max
kyk=1kAyk. (5.7b) La sostituzione del sup con il max discende dal fatto che la k · k `e una funzione continua e l’insieme dei vettori y ∈ Rn con kyk = 1 `e chiuso.
Le norme matriciali sono caratterizzate dalla validit`a delle seguenti pro-priet`a:
(a) kAk ≥ 0 con kAk = 0 se e solo se A = O;
(b) kαAk = |α| kAk, qualunque sia il numero α ∈ R (α ∈ C); (c) kA + Bk ≤ kAk + kBk, qualunque siano le matrici A e B; (d) kABk ≤ kAk kBk, qualunque siano le matrici A e B.
Le prime tre seguono immediatamente dalle (5.7). Per la (d) si deve prima osservare che per la (5.7a)
kAxk
kxk ≤ kAk, x 6= 0,
dato che kAk (per definizione) `e il pi`u piccolo maggiorante di kAxkkxk , kxk 6= 0, da cui
kAxk ≤ kAk kxk. Conseguentemente, per ogni x 6= 0,
kA(Bx)k ≤ kAk kBxk ≤ kAk kBk kxk =⇒ =⇒ k(AB)xk
kxk ≤ kAk kBk per ogni x 6= 0 e dunque vale la (c), dato che kABk = sup
x6=0
k(AB)xk
Matrice identit`a. `E evidente che, indicata con I la matrice identit`a in L(Cn), qualunque sia la norma matriciale indotta, kIk = 1.
5.12. Relazione tra norma matriciale e raggio spettrale. Qualunque sia la k · k matriciale indotta e qualunque sia la matrice A ∈ L(Cn),
ρ(A) ≤ kAk. (5.8) Verifica. Dalla definizione
Ax = λx, x 6= 0
deriva infatti che, qualunque sia l’autovalore λ e il corrispondente autovettore x,
kAxk = |λ| kxk =⇒ |λ| = kAxk
kxk ≤ kAk = supx6=0
kAxk kxk .
Anche se, in generale vale il <, in casi particolari pu`o valere l’uguale. Per A = I, vale l’uguale dato che, per ogni norma, kAk = 1 e λ1 = λ2 = . . . = λn = 1 =⇒ ρ(I) = 1.
Calcolo delle kAk2, kAk∞ e kAk1. (a) Se A ∈ L(Rn), kAk2 =pρ(ATA).
Per la sua dimostrazione, indicati con (λ, u) una coppia autovalore-auto-vettore di ATA, possiamo affermare che
ATAu = λu, u 6= 0. Da essa segue che
uTATAu = kAuk22 = λkuk22 =⇒ λ ≥ 0 e conseguentemente ρ(ATA) = kAuk2 2 kuk2 2 ≤ sup x6=0 kAxk2 2 kxk2 2 = kAk22, ossia ρ(ATA) ≤ kAk2
2.
Per dimostrare che vale l’uguale, posto µ = ρ(ATA) e indicato con v l’autovettore corrispondente, osserviamo che
kAvk2 2 kvk2 2 = v TATAv vTv = vT(µv) vTv = µ = ρ(A T A). Resta cos`ı dimostrato che kAk2 =pρ(ATA).
Se la matrice A `e simmetrica, essendo ρ(ATA) = ρ(A2) = ρ(A)2, kAk2 = ρ(A).
Se A `e ortogonale, kAk2 = 1, dato che ATA = I e ρ(I) = 1.
Anche se esistono vari metodi per il calcolo del raggio spettrale di una matrice, il calcolo della kAk2 `e, in generale, piuttosto complicato. Per questo motivo nei metodi iterativi, in particolare, si utilizzano pi`u frequentemente la k · k1 e la k · k∞, molto pi`u semplici da calcolare.
(b) Se A ∈ L(Rn), kAk∞= max i=1,...,n n X j=1 |aij|.
5.13. Iniziamo con l’osservazione che, per ogni x ∈ Rn con kxk∞ = max i=1,...,n |xi| = 1, si ha: kAxk∞ = max i=1,...,n n X j=1 aijxj ≤ max i=1,...,n n X j=1 |aij| |xj| ≤ max i=1,...,n n X j=1 |aij|.
Per dimostrare che vale l’uguale, basta trovare un vettore x con kxk∞ = 1 per cui vale l’uguale. A tale scopo, indicata con r la riga della matrice con
n X j=1 |arj| = max i=1,...,n n X j=1 |aij|, definiamo x ponendo per j = 1, 2, . . . , n
xj = ( arj
|arj|, se arj 6= 0 0, se arj = 0. La dimostrazione risulta pertanto completa, dato che
kAxk∞ = n X j=1 arjxj = n X j=1 |arj|.
Calcolare la k · k∞ di una matrice `e molto semplice, a differenza di quanto avviene per il calcolo della k · k2. Come risulta dalla propriet`a seguente, il costo computazionale della kAk∞ e kAk1 `e lo stesso, per ogni A ∈ L(Cn).
5.14. Per ogni A ∈ L(Rn), kAk1 = max
j=1,...,n n
X
i=1
Dimostrazione. kAxk1 = n X i=1 n X j=1 aijxj ≤ n X i=1 n X j=1 |aij| |xj| = n X j=1 |xj| n X i=1 |aij| ≤ max j=1,...,n n X i=1 |aij| ! kxk1.
Si tratta ora di dimostrare che esiste un vettore x 6= 0 per cui vale l’uguale. A tale scopo, supponendo che il massimo della sommatoria valga per j = r, basta prendere x = ek (versore con 1 nella k-esima posizione e zero altrove). Con tale scelta risulta infatti Aek = ak, colonna k-esima di A, e la dimostrazione `
e completa (essendo kekk = 1).
La (5.8) evidenzia che ρ(A) `e minore di una qualsiasi norma indotta. In realt`a si pu`o affermare che ρ(A) `e l’estremo inferiore delle norme indotte in quanto, alla (5.8) pu`o essere aggiunta la seguente propriet`a (di cui si tralascia la dimostrazione): prefissato ad arbitrario ε > 0, esiste una norma kAk per la quale
ρ(A) ≤ kAk < ρ(A) + ε. (5.9) In una matrice simmetrica ρ(A) = kAk2, dato che kAk2 = pρ(ATA) = pρ(A)2 = ρ(A), dato che AT = A e ρ(A2) = ρ(A)2.
Nella seguente matrice simmetrica A = 1 1 01 −1 1 0 1 1
, ρ(A) =√
3 e, conseguen-temente kAk2 = ρ(A), mentre:
kAk∞ = max i=1,2,3 3 X j=1 |aij| = 3 X j=1 |a2j| = 3, kAk1 = max j=1,2,3 3 X i=1 |aij| = 3 X i=1 |ai2| = 3. `
E importante osservare, per la rilevanza del risultato nella risoluzione dei sistemi lineari, che ρ(A) pu`o essere < 1, anche se kAk1 > 1 e kAk∞ > 1. Per evidenziarlo consideriamo il seguente esempio riportato in [20, pag. 55]
A = 0.1 0 1.0 0.2 0.2 0.3 0.1 0.3 0.1 0.1 0.1 0.2 0.1 0.2 0.2 0.1 ,
per la quale kAk∞ = 1.3 e kAk1 = 1.4. Il suo raggio spettrale ρ(A) < 1. Per verificarlo, indicata con D la matrice diagonale D = diag(6, 6, 10, 6),
consideriamo la matrice simile alla A DAD−1 = 0.1 0 0.6 0.2 0.2 0.3 0.06 0.3 1 6 1 6 0.1 13 0.1 0.2 0.12 0.1 .
Applicando ad essa il teorema di localizzazione di Gershgorin si ha: |λ − 0.1| ≤ 0.8 =⇒ −0.7 ≤ λ ≤ 0.9 |λ − 0.3| ≤ 0.56 =⇒ −0.26 ≤ λ ≤ 0.86 |λ − 0.1| ≤ 2 3 =⇒ −1730 ≤ λ ≤ 23 30 |λ − 0.1| ≤ 0.42 =⇒ −0.32 ≤ λ ≤ 0.52.
Di conseguenza, ρ(A) < 1, dato che |λ| < 1 in ciascuno dei cerchi di Gershgorin. Alla stessa conclusione si pu`o arrivare applicando il teorema di localizzazione di Gershgorin alle colonne di A.
Convergenza di una successione. Una successione {xk}∞
k=1 in Rn `e convergente a x ∈ Rn, secondo una prefissata k · k, se lim
k→∞ kxk− xk = 0. Ana-logamente, la successione {xk}∞
k=1`e di Cauchy (per la norma in considerazione) se, prefissato ε > 0, esiste un N (ε) tale che, per ogni coppia k, l > N (ε),
kxk− xlk < ε.
Per la completezza dello spazio Rn, rispetto a una sua qualunque norma, ogni successione di Cauchy `e anche convergente. Pertanto, essendo l’inverso ovvio, le due definizioni sono equivalenti.
Nei processi iterativi studiare la convergenza rispetto a una norma pu`o essere molto pi`u complicato che rispetto a un’altra norma. Per fortuna, come evidenziato nel seguente teorema, la convergenza secondo una norma (la pi`u semplice da utilizzare) implica la convergenza con un’altra norma (quella di maggior interesse).
Teorema 5.4 (Equivalenza delle norme) Prefissata due qualsiasi norme k · k0 e k · k00, esistono due costanti c2 ≥ c1 > 0, tali che
c1kxk0 ≤ kxk00 ≤ c2kxk0, qualunque sia il vettore x
Dimostrazione. Per rendersi conto dell’equivalenza basta osservare che se una successione {xk}∞
k=1converge a x secondo la k · k0, essendo c2 indipendente dai vettori in considerazione,
Se, viceversa {xk}∞
k=1 converge e se secondo la k · k00, per l’indipendenza di e1 dei vettori in considerazione,
c1kxk− xk0 ≤ kxk− xk00=⇒ kxk− xk0 → 0. `
E questo il motivo per il quale, nei metodi iterativi, in virt`u della facilit`a del loro calcolo, le norme pi`u usate sono k · k∞ e la k · k1. La convergenza secondo una delle due implica, in particolare, la convergenza secondo la k · k2. 2 Prima di discutere della risoluzione numerica dei sistemi lineari, `e bene sof-fermarsi sulla rappresentazione spettrale della soluzione di un sistema lineare. La sua rilevanza trascende il settore specifico, in quanto una analoga rap-presentazione viene utilizzata nella risoluzione analitica dei sistemi di ODEs lineari. Iniziamo con il supporre che la matrice A ∈ L(Rn) del sistema Ax = b sia non singolare e simmetrica. In tal caso gli autovalori λ1, . . . , λn sono reali e gli autovettori u1, . . . , un possono essere scelti mutuamente ortonormali. Di conseguenza, si pu`o scrivere
(
Aui = λiui, i = 1, . . . , n con |λ1| ≥ |λ2| ≥ . . . ≥ |λn| > 0
uTi uj = δij, i, j = 1, 2, . . . , n. (5.10) Tale propriet`a, in forma matriciale, pu`o essere cos`ı rappresentata
AU = U D, U = u1 u2 . . . un , D = diag(λ1, λ2, . . . , λn). Da quest’ultima, tenendo conto della ortonormalit`a delle colonne di U , segue che
A = U DUT =⇒ U DUTx = b, (5.11a) e conseguentemente, essendo D non singolare
x = U D−1UTb = u1 u2 . . . un D−1 (u1, b) (u2, b) .. . (un, b) ,
che, in forma scalare diventa x = n X j=1 (uj, b) λj uj. (5.11b) La (5.11) fornisce la rappresentazione spettrale della soluzione. Il risultato, pi`u che numericamente, `e importante teoricamente per la propriet`a da essa desumibile e per le analogie che ispira in altri settori della matematica.
Decomposizione a valori singolari (Singular Value Decomposition, SVD). Se A `e non singolare, le matrici ATA e AAT sono simmetriche e definite positive. Di conseguenza, indicati con {λi = σ2
i, i = 1, . . . , n} gli autovalori di ATA e con {u1, . . . , un} i relativi autovettori ortonormali, possiamo scrivere
ATAui = σi2ui, i = 1, 2, . . . , n. (5.12) Da essa, ponendo (per definizione)
Aui = σivi, i = 1, 2, . . . , n, otteniamo i due sistemi
ATvi = σiui Aui = σivi
i = 1, 2, . . . , n. (5.13) Dalla (5.12) segue immediatamente che i σ2
1, . . . , σ2
n sono gli autovalori di AAT
(oltre che di ATA), i cui autovettori relativi sono i v1, . . . , vn. Per verificarlo basta osservare che, molteplicando la prima delle (5.13) per A
AATvi = σiAui, i = 1, . . . , n, (5.14) dalla quale, ricordando la seconda, segue che
ATAvi = σ2ivi, i = 1, . . . , n.
Di conseguenza, ATA e AAT hanno gli stessi autovalori, mentre gli autovet-tori sono diversi. Anche gli autovetautovet-tori v1, . . . , vn sono ortonormali, dato che (indicato con δij =
(
1, i = j,
0, i 6= j, il simbolo di Kronecker) per la seconda delle (5.13) vTjvi = 1 σj uTjAT 1 σi Aui = σi σj uTjui = σi σj δij, i, j = 1, . . . , n, e dunque anche i v1, . . . , vn sono ortonormali.
Ponendo
V = v1 v2 . . . vn , U = u1 u2 . . . un , Σ = diag(σ1, . . . , σn), dalla prima delle (5.13) segue che
e da questa, ricordando che U−1 = UT e che V−1 = VT, segue la SVD di A A = V ΣUT =⇒ A−1 = U Σ−1VT.
I σ1, . . . , σnsono definiti i valori singolari di A e i vettori {ui, vi}n
i=1 i suoi vet-tori singolari. Di conseguenza, la soluzione x = A−1b pu`o essere rappresentata nella forma vettoriale
x = U Σ−1VTb = u1 u2 . . . un Σ−1 (v1, b) (v2, b) .. . (vn, b) (5.15a)
o, nella forma scalare
x = n X j=1 (vj, b) σj uj. (5.15b) La (5.15) fornisce la rappresentazione singolare della soluzione di un sistema con matrice non singolare. La (5.12) implica che, ordinati i valori singolari per valori decrescenti (σ1 ≥ σ2 ≥ . . . ≥ σn),
kAk2 =pρ(ATA) = σ1, kA−1k2 =pρ((ATA)−1) = 1 σn, da cui segue immediatamente che (relativamente alla stessa norma)
cond(A) ≡ kAk2kA−1k2 = σ1 σn.
Esistono nella letteratura molti metodi per il calcolo della SVD di A e del cond(A). Algoritmi molto efficienti per il calcolo dei valori singolari e dei vettori singolari e conseguentemente anche del cond(A), rispetto alla k · k2, si trovano in MATLAB.