LeLing15: Fibonacci, Autovalori e Autovettori.
A ¯ rgomenti svolti:
• Serie di numeri di Fibonacci.
• Potenza n-esima di matrici.
• Autovalori ed autovettori.
• Formula di Binet.
E ¯ sercizi consigliati: Geoling 16 .
I numeri sulla Mole Antonelliana.
Ecco i numeri sulla Mole:
1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , · · ·
dove ogni nuovo numero rappresenta la somma dei due che lo precedono. Ad esempio 233 = 89 + 144
Se si e’ capito tutto fin qui, il lettore non dovrebbe trovare difficolta’ a calcolare qual e’ il numero che segue 987. (Risposta: 1597).
Nota Storica :
Questa serie di numeri e’ nota come serie di numeri di Fibonacci in onore a Leonardo da Pisa, conosciuto col nome paterno di ”figlio Bonacci”, cioe’ Fibonacci (detto anche Bigollo), che verso il 1223 ha studiato questa succesione di numeri a proposito del seguente problema sulla riproduzione dei conigli:
Quante coppie di conigli si ottengono in un anno supponendo che ogni coppia dia alla luce un’altra coppia ogni mese e che le coppie piu’ giovani siano in grado di riprodursi gia’ al secondo mese di vita?
La soluzione al problema studiato da Fibonacci e’ 377, cioe’ dopo un anno ci sono 377 coppie di conigli. Infatti,
F
nF
0F
1F
2F
3F
4F
5F
6F
7F
8F
9F
10F
11F
12mese 0 1 2 3 4 5 6 7 8 9 10 11 12
coppie 1 2 3 5 8 13 21 34 55 89 144 233 377
Dove F
nsodisfa
F
n= F
n−1+ F
n−2se n ≥ 2
e (
F
0= 1 , F
1= 2 .
La formula di Binet.
Problem 0.1. Quanto grande e’ F
100?. Ad esempio, se ci chiediamo se F
100e’ minore o maggiore di 100000000 = 10
8, qual e’ la risposta giusta??
Per rispondere a questa domanda, ci servirebbe (forse) una ”formula” per calcolare l’n-esimo numero F
n. Certamente il lettore informato sa che questa formula esiste ed e’
conosciuta con il nome di formula di Binet (ca. 1843), ma era gia’ conosciuta da Eulero e Daniele Bernoulli. Eccola qui,
F
n= 5 + 3 √ 5 10
1 + √ 5 2
!
n+ 5 − 3 √ 5 10
1 − √ 5 2
!
nNotiamo che questa identita’ e’ ben lontana dall’essere evidente o banale. Ad esem- pio, come spiegare la radice di 5, che non e’ un numero intero? (Ricordate che F
ne’
un numero intero, in quanto rappresenta il numero di coppie di conigli...). Quindi, se la formula e’ giusta ci sono delle semplificazioni misteriose...
Esercizio : Verificare che, effettivamente, la formula di Binet funziona per n = 0 e n = 1.
Di solito, si dimostra la formula di Binet a partire dal principio di induzione, cioe’:
Esercizio : Dimostrare usando il principio di induzione che la formula di Binet fun- ziona per ogni n ≥ 0.
Ma la dimostrazione per induzione non ci aiuta a capire l’origine di questa bellissima formula; allora come e’ nata questa formula?. In seguito il lettore trovera’ una possibile risposta (tra altre possibili) tramite i concetti di Autovalori ed Autovettori.
Prima di lasciare questa parte risolviamo il Problema 0.1 usando il fatto che (grazie
alla Formula di Binet...):
F
n≈ 5 + 3 √ 5 10
1 + √ 5 2
!
n≥ 1, 1708 3 2
n.
dove
5+3√5
10
= 1, 1708 e ricordo che Eulero era nato in 1707...
Allora, F
100≥
32100= ((
32)
2)
50> 2
50> 2
48= 2
8.2
40> 2
8.5
8= 10
8. Dunque F
100e’ maggiore di 10
8. Con i logaritmi si vede che in realta’ F
100ne ha piu’ di venti cifre, cioe’ F
100= o(10
20).
Fibonacci e matrici
Osserviamo che l’equazione
F
n= F
n−1+ F
n−2equivale al sistema:
F
n= F
n−1+ G
n−1G
n= F
n−1Come gia’ sappiamo, possiamo scrivere questo sistema tramite matrici, vettori colonna e prodotti fra loro, cioe’
1 1 1 0
F
n−1G
n−1=
F
nG
nAllora la colonna C
n=
F
nG
nrisulta da quella C
n−1tramite la moltiplicazione per la matrice A = 1 1
1 0
. Quindi possiamo scrivere:
A C
n−1= C
nSiccome C
n−1= A C
n−2risulta:
A C
n−1= A A C
n−2= A
2C
n−2= C
nDunque applicando reiteratamente questa idea si ottiene:
A
n−1C
1= C
ndove C
1=
F
1G
1= 2 1
.
Quindi risulta che dobbiamo calcolare la potenza n − 1 di una matrice A, cioe’
dobbiamo calcolare 1 1 1 0
n−1Calcolo della potenza n-esima di una matrice
Se una matrice D e’ diagonale, ad esempio D = 2 0 0 3
e’ molto facile calcolare D
n. Infatti, D
n= 2
n0
0 3
ne non ci sono problemi.
Piu’ in generale se D = λ 0 0 β
allora D
n= λ
n0 0 β
nQuindi non ci sono problemi per calcolare D
nse D e’ diagonale.
Un altro caso dove e’ facile calcolare la potenza n-essima di A e’ quando possiamo scrivere la matrice A come:
A = M DM
−1dove la D e’ una matrice diagonale e la matrice M e’ arbitraria (ma ovviamente invertibile, visto che l’equazione contiene M
−1).
Nota 0.2. Se queste due matrici D e M esistono si dice che la matrice A e’ diago- nalizzabile
1. Osservare che questo e’ equivalente a:
M
−1AM = D
Vediamo perche’ e’ facile calcolare A
nquando A e’ diagonalizzabile. Infatti, A
n= M DM
−1M DM
−1M DM
−1· · · M DM
−1M DM
−1| {z }
n volte
= M DDD · · · DD
| {z }
n volte
M
−1= M D
nM
−11
Non e’ vero che esistono sempre M e D , ad esempio la matrice A =
0 1 0 0
non e’ diagonalizz-
abile.
poiche’ i fattori M M
−1si elidono, per definizione di inversa. Dunque, se conosciamo D
ne M possiamo calcolare A
nsenza problema.
Diagonalizzando Fibonacci
Allora per il calcolo di 1 1 1 0
n−1sarebbe ideale trovare una matrice diagonale D e una matrice invertibile M tale che:
1 1 1 0
= M DM
−1Come trovare M e D ? L’idea e’ assumere che M e D esistano e cercare di trovarli tramite qualche trucchetto... Notiamo che l’equazione precedente implica:
1 1 1 0
M = M D .
Se ricordiamo come si ricava il prodotto tra matrici notiamo che, poiche’ D e’ diag- onale, le colonne M
1ed M
2della M , soddisfano a:
1 1 1 0
M
1= λM
1e 1 1
1 0
M
2= βM
2dove D = λ 0 0 β
, che pero’ non conosciamo, cioe’ conoscendo D sarebbe facile calcolare M risolvendo i seguenti sistemi (equivalenti alle equazioni di sopra) per le colonne M
1e M
2della M :
1 − λ 1
1 −λ
M
1= 0 0
1 − β 1
1 −β
M
2= 0 0
Quest’ultimo sistema e’ molto interessante perche’ ci dice che le colonne M
1,M
2sono
soluzioni di un sistema omogeneo. Ricordo inoltre che vogliamo che M
1(la stessa cosa
per M
2) sia una colonna di una matrice invertibile, dunque M
16= 0.
Questo ci forza a prendere λ (e pure β ) uguale ad una radice del determinante della matrice 1 − λ 1
1 −λ
, cioe’ questo sistema omogeneo ha delle soluzioni non banali se, e solo se:
det( 1 − λ 1
1 −λ
) = λ
2− λ − 1 = 0 Da dove λ =
1±√ 5
2
, questi numeri sono i cosidetti numeri d’oro (vedere [Livio] per delle interessanti proprieta’ di questi numeri).
Nota 0.3. Nel linguaggio dell’Algebra lineare i numeri
1±√ 5
2
si chiamano autovalori della matrice 1 1
1 0
. Piu’ in generale, data una matrice A si calcola il polinomio P (λ) = det(A − λId) che si chiama polinomio caratteristico
2. Le radici di P (λ) si chiamano autovalori .
Dunque possiamo prendere D uguale a
"
1+√ 5
2
0
0
1−√5 2
# .
Adesso non e’ difficile trovare le colonne M
1e M
2della matrice M , cioe’ queste colonne sono soluzioni dei sistemi omogeni le cui matrici sono:
"
1 −
1+√5
2
1
1 −
1+√ 5 2
# "
1 −
1−√5
2
1
1 −
1−√ 5 2
#
Possiamo allora prendere M
1=
1+√52
1
e M
2=
1−√52
1
.
Nota 0.4. Nel linguaggio dell’Algebra lineare si dice che le colonne M
1e M
2sono due autovettori della matrice 1 1
1 0
.
Piu’ in generale, una soluzione x 6= 0 (cioe’, x non nullo) del sistema omogeneo la cui matrice e’ A − λId = 0, dove λ e’ un autovalore di A si chiama autovettore di A.
2
Storicamente il polinomio caratteristico nasce con il lavoro di Luigi Lagrange su le perturbazioni
secolari delle orbite planetarie vicine alle orbite di Keplero. Dunque, la equazione det(A − λId) = 0
era chiamata equazione secolare [Arnold, pag.45]. Ancora oggi in Astronomia, Fisica e Chimica questa
equazioni si la conosce come equazione secolare [McSi].
Quindi abbiamo ottenuto cio’ che volevamo, cioe’
1 1 1 0
=
1+√52
1−√ 5 2
1 1
"
1+√ 5
2
0
0
1−√5 2
#
1+√52
1−√ 5 2
1 1
−1L’inversa
1+√52
1−√ 5 2
1 1
−1e’
"
1√ 5
√5−1 2√
5
−1√ 5
1+√ 5 2√
5
#
. Dunque
1 1 1 0
=
1+√52
1−√ 5 2
1 1
"
1+√ 5
2
0
0
1−√ 5 2
# "
1√5
√5−1 2√
5
−1√ 5
1+√ 5 2√
5
#
Finalmente,
1 1 1 0
n−1= 1
√ 5
1+√52
1−√ 5 2
1 1
"
(
1+√ 5
2
)
n−10
0 (
1−√5 2
)
n−1# "
1
√ 5−1
2
−1
1+√5 2
#
Per trovare F
ndobbiamo quindi calcolare, ricordiamo, 1 1 1 0
n−12 1
=
F
nG
ncioe’
F
nG
n= 1
√ 5
1+√52
1−√ 5 2
1 1
"
(
1+√ 5
2
)
n−10
0 (
1−√5 2
)
n−1# "
1
√ 5−1
2
−1
1+√5 2
# 2 1
=
= 1
√ 5
1+√52
1−√ 5 2
1 1
"
(
1+√5
2
)
n−10
0 (
1−√ 5 2
)
n−1# "
3+√ 5 2
√ 5−3
2
#
= 1
√ 5
"
(
1+√5
2
)
n(
1−√5 2
)
n(
1+√ 5
2
)
n−1(
1−√ 5 2
)
n−1# "
3+√ 5 2
√ 5−3
2
#
L’ultima moltiplicazione fornisce,
F
nG
n=
"
3+√52√ 5
(
1+√ 5 2
)
n+
√ 5−3 2√
5
(
1−√ 5 2
)
n3+√ 5 2√
5
(
1+√ 5
2
)
n−1+
√ 5−3 2√
5
(
1−√ 5 2