I. Sistemi d ricorrenze lineari

(1)

I. Sistemi d ricorrenze lineari

Sia A ∈ M k,k (C) una matrice complessa. Il sistema lineare omogeneo di ricorrenze per la successione {X n } di vettori di C ^k

( X n+1 = AX n , n ≥ 0, X 0 assegnato

ha come unica soluzione X n := A ⁿ X 0 ∀n, come si verifica immediatamente per induzione.

Proposizione. Assegnata una successione {F n } di vettori di C ^k , il sistema lineare non omogeneo di ricorrenze per la successione {X n } di vettori di C ^k

( X n+1 = AX n + F n+1 , n ≥ 0, X 0 assegnato

ha come unica soluzione

X n := A ⁿ X 0 +

n

X

j=0

A ^n−j F j ∀n ≥ 0

dove si` e posto F 0 := 0 ∈ C ^k .

Dimostrazione. Infatti per ogni n ≥ 0,

X n+1 = A ⁿ⁺¹ X 0 +

n+1−j

X

j=0

A ⁿ⁺¹ F j = A ⁿ⁺¹ X 0 +

n

X

j=0

A ^n+1−j F j + F n+1

= A A ⁿ X 0 + A

n

X

j=0

A ^n−j F j + F n+1 = A

A ⁿ X 0 +

n

X

j=0

A ^n−j F j

+ F n+1

= AX n + F n+1 .

Potenze di una matrice

Resta il problema di calcolare le potenze successive della matrice A in modo efficiente.

Si osserva che

(2)

2 I. Sistemi d ricorrenze lineari

(i) se B `e una matrice simile ad A, A = S ⁻¹ BS per qualche matrice S con det S 6= 0, allora

A ² = S ⁻¹ BSS ⁻¹ BS = S ⁻¹ B ² S e, per induzione,

A ⁿ = S ⁻¹ B ⁿ S ∀n.

(ii) Se B `e una matrice a blocchi quadrati sulla diagonale principale

B =







B ₁ 0 . . . 0

0 B ₂ . . . 0

. . .

0 . . . 0 B _r







allora

B ⁿ =





 B ⁿ

1 0 . . . 0

0 B ⁿ ₂ . . . 0 . . .

0 . . . 0 B ⁿ _r







Siano λ 1 , λ 2 , . . . , λ k gli autovalori distinti di A e m 1 , m 2 , . . . , m k le relative molteplicit` a. Per ogni k sia p k la dimensione dell’autospazio relativo a λ k . Allora esiste un cambiamento di base S tale che J := S ⁻¹ AS abbia la forma di Jordan

J =







J _1,1 0 0 . . . 0

0 J _1,2 0 . . . 0 . . .

0 0 0 . . . J _k,p

k







dove i = 1, . . . , k, j = 1, . . . , p i e

9 giugno 2004 Versione preliminare

(3)

I. Sistemi d ricorrenze lineari 3

J _i,j =



 



 



λ i se J i,j ha dimensione 1,







λ i 1 0 0 . . . 0 0 λ i 1 0 . . . 0 . . .

. . .

0 0 0 . . . λ i 1 0 0 0 . . . 0 λ i







altrimenti.

Percio’ A ⁿ = SJ ⁿ S ⁻¹ , e

J ⁿ =







J ⁿ _1,1 0 0 . . . 0

0 J ⁿ _1,2 0 . . . 0 . . .

0 0 0 . . . J ⁿ

k,p

_k





 .

Resta da calcolare la potenza di ciascun blocco di Jordan. Se J ⁰ = J i,j = (λ) ha dimensione 1, allora evidentemente J ⁰ⁿ = λ ⁿ . Se invece J ⁰ = J i,j `e uno dei blocchi di dimensione q maggiore o uguale a 2,

J ⁰ =







λ 1 0 . . . 0 0 λ 1 . . . 0 . . .

0 . . . 0 λ 1 0 0 . . . 0 λ





 ,

allora

J ⁰ = λ Id + B, B = (B) i,j , B ij = δ i+1,j . Essendo ora

(B ^r ) ij =

( δ r+i,j se r < q, 0 se r ≥ q, si ha B ^q = 0 e dalla formula del binomio di Newton

J ⁰ⁿ = (λ Id + B) ⁿ =

n

X

j=0

n j

λ ^n−j B ^j =

q−1

X

j=0

n j

λ ^n−j B ^j = λ ⁿ

q−1

X

j=0

n j

1 λ ^j B ^j i.e.,

Versione Preliminare 9 giugno 2004

(4)

4 I. Sistemi d ricorrenze lineari

J ⁰ⁿ = λ ⁿ







1 n _λ ¹ ⁿ ₂ 1

λ

²

. . . _q−1 ⁿ 1 λ

^q−1

0 1 n ¹ _λ . . . _q−2 ⁿ 1 λ

^q−2

. . .

0 0 . . . 1 n ¹ _λ

0 0 . . . 0 1





 .

Si osservi che ciascun elemento di A ⁿ ha la forma

k

X

j=1

λ ⁿ _j p j (t)

dove λ 1 , λ 2 , . . . , λ n sono gli autovalori di A e p j (t) `e un polinomio di grado al piu’ p j −1 (p j `e la molteplicit` a algebrica di λ j ). Segue immediatamente che per ogni ρ > max i (|λ i |) esiste una costante C ρ tale che per ogni soluzione di X n+1 = AX n si ha

|X n | ≤ C ρ ρ ⁿ |X 0 | ∀n.

In particolare

Proposizione. Se tutti gli autovalori di A hanno modulo minore di 1, allora ogni soluzione di X n+1 = AX n tende a zero per n → +∞.

Dimostrazione. Infatti, si sceglie σ > 0 tale che max i=1,n |λ i | < σ < 1. Esiste allora una costante C σ tale che per ogni soluzione di X n+1 = AX n si ha

|X n | ≤ C σ σ ⁿ |X 0 |, ∀n.

Essendo 0 < σ < 1, σ ⁿ → 0 e la tesi `e provata.

9 giugno 2004 Versione preliminare

I. Sistemi d ricorrenze lineari