From veky@student.math.hr Thu Nov 20 17:57:37 2003
Subject: Re: Binetova formula
Lines: 209
Message-ID: <slrnbrpsip.cv0.veky@student.math.hr>
References: <bpgu4h$rrt$1@ls219.htnet.hr>

>Formula koja omogucuje izracunavanje 
>n-tog clana Fibonaccijevog niza glasi:
>
><LATEX>
>\[a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-
>\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\]
></LATEX>
>
>Taj zadatak (dokazati formulu za proizvoljan n) 
>smo imali u testu u skoli i
>nasao sam jedan dokaz koji mi se cini elegentan,
> pa me zanima moze li netko
>naci jos ljepsi i jednostavniji.

Well... ima ih zaista dosta, vjerujem da je najjednostavniji 
simply uvrstit stvar u rekurziju i vidjet da se dobiva tocna
jednakost... :-)

A sto se ljepote tice... tim vise sto sam u prethodnom lessonu napomenuo
neke stvari vezane uz sustave rekurzija (pa rekao da sam prelijen
raspisivati ih - eto kako mi se Svemir osvecuje;), sad bih prezentirao 
jedan pristup koji se temelji na linearnoj algebri i meni se cini
prilicno zanimljivim... idemo.

[lesson title="linearne rekurzije, linearni operatori i ostale banane"
	title-comment="hi ofca;-)"]

Dakle, svi znamo da je F_i jednak i za i@2 , a F_{i-1}+F_{i-2} za ostale
prirodne i . Krenimo od toga, i pogledajmo kako bismo izracunali neki,
npr. F_5 . Za njega nam trebaju F_4 i F_3 , dok nam za F_4 trebaju
F_3 i F_2 , i tako dalje... vidimo da cemo bar F_3 racunati bar dvaput.
Buduci da za F_3 trebaju i svi ispod njega, sve njih cemo takoder
racunati bar dvaput 
(inFact, i puno vise puta, za vece pocetne indekse).
Ideja je, naravno, spremiti vrijednosti prethodno izracunatih F-ova.
Za to nam na prvi pogled treba polje od ~~n integera. No na drugi pogled,
zapravo ne, jer vidimo da jednom kad izracunamo sve do F_n , za
racunanje sljedeceg - F_{n+1} trebaju nam samo
 dva zadnja koja smo izracunali - F_n i F_{n-1} .
 Konkretno, za F_5 bi izgledalo ovako:
0 1 ? ? ? ?                                    0 1 ? ? ? ?    0 1
0 1 1 ? ? ?                      "zaboravimo"->? 1 1 ? ? ?    1 1
0 1 1 2 ? ?                                    ? ? 1 2 ? ? -> 1 2
0 1 1 2 3 ? , no to mozemo zamijeniti s        ? ? ? 2 3 ?    2 3
0 1 1 2 3 5                 ovakvom shemom :   ? ? ? ? 3 5    3 5

Dakle, dovoljne su nam samo dvije varijable, za spremanje dviju zadnjih
vrijednosti. Pocetno je (0,1), a korak je (x,y)|->(y,x+y) . 
Nakon n-1 koraka, druga komponenta (y) je ono sto trazimo.
(Moze i nakon n koraka, tad ce ono sto trazimo biti u x - jedan korak
vise, ali sto to znaci mathu...;) Naravno, ako
bismo to htjeli racunati kompjuterski, npr. u C-u, trebamo voditi racuna
da prvo izracunamo drugu komponentu, jer inace cemo dobiti [y,y] kao
medurezultat i necemo imati nacina da rekonstruiramo x - ali
math-zapisano, za to nas ne mora biti 
briga - obje transformacije x|->y i y|->x+y se odvijaju simultano.

Drugim rijecima, mozemo na (x,y) gledati kao na ureden par - ie,
tocku u ravnini; a na gornje preslikavanje kao na neko 
preslikavanje ravnine. Ono nazalost nije ni translacija ni rotacija ni
simetrija, ali jest nesto sto se zove _linearni operator_. Nama naziv
nece biti toliko bitan, bitnija ce nam biti matricna reprezentacija.

Da, matricna. (y,x+y) se moze shvatiti kao vektor stupac, [ y // x+y ]
( "//" oznacava prelazak u novi red), i on je funkcija
 od vektora [ x // y ] .
Lako se vidi da se prijelaz dobiva 
mnozenjem (slijeva) s matricom A=[ 0 1 // 1 1 ] .
Dakle, pocinjemo od vektora [ 0 // 1 ] ,
 i mnozimo ga n puta s matricom A .
Ono sto dobijemo, u prvom retku ima trazeni F_n (naravno, u drugom ce
biti F_{n+1} , ali za njega nas nije toliko briga). To mozemo zapisati
kao [ 0 1 ]^n . [ 0 ] = [ F_n     ]
    [ 1 1 ]     [ 1 ]   [ F_{n+1} ]

Dakle, stvar se svodi na: kako lukavo potencirati matricu A nekim
prirodnim brojem? Hm. Kao prvo, kad bi se matrice mnozile "po tockama",
( [ a b // c d ] . [ e f // g h ] = [ ae bf // cg dh ] :), to bi bilo
trivijalno - samo dignemo svaki broj u matrici na n-tu potenciju, i to
je to (Da ne govorim o tome da su brojevi u matrici samo 0 i 1 ;). 
No kakva nam korist od toga, 
kad se matrice _ne_ mnoze po tockama? Welll...
zapravo postoje matrice koje se upravo tako mnoze. Naravno, mislim na
dijagonalne matrice. Probaj mnozit dvije dijagonalne matrice "obicnim"
matricnim mnozenjem, i vidjet ces da se zapravo mnoze samo odgovarajuci
dijagonalni elementi - svi ostali se takoder mnoze, ali s nulama:-).

ok, sve je to lijepo i krasno, ali sto nam to vrijedi kad matrica A
_nije_ dijagonalna?? (Welll)_2... nemoj me previse cudno gledati, ali
jest. Na neki nacin. :-)
U cem je fora? Gore sam rekao da se A moze shvatiti kao linearni 
operator - transformacija ravnine. Opcenito, linearnom
operatoru odgovara neka matrica koja se dobiva tako da se izvode neki
masakri s bazama, koji nama nisu previse bitni. 
Ono sto mi zelimo je samo ovo: 
Neka su i i j jedinicni vektori u ravnini (oni sa strelicama umjesto
tockica gore:). Tada se lako vidi (sjetimo se kako je A dobiven) da je
Ai=j & Aj=i+j . Dakle, jednostavno citamo stupce (ili retke - A je 
simetricna:) i stavljamo te brojeve kao koeficijente. 
Ai=0i+1j,Aj=1i+1j .
Sto bi znacilo da je A dijagonalna? Znacilo bi da za neke (druge)
vektore i' i j' vrijedi ( A' = [ e 0 // 0 f ] <- dijagonalno)
Ai'=e*i' , te Aj'=f*j' . Uhvatimo se zasad za ovu prvu jednakost, 
drugu cemo analogno zamjenom "i'" s "j'" i "e" s "f" .

Dakle, Ai'=ei' . Ai' je mnozenje i' s nekom matricom (slijeva).
ei' na prvi pogled nije (s matricom),
 ali takoder jest ako se sjetimo i'=Ii'
( I je jedinicna matrica 2x2 , I = [ 1 0 // 0 1 ] ):
Ai'=ei'=eIi'=(eI)i' ( eI = [ e 0 // 0 e ] ). Dakle,
(A-eI)i'=0_2 <- oznaka za 2D-nulvektor. Naravno, ako je i' nulvektor, 
tada trivijalno vrijedi Ai'=ei'=0_2 , ali iz toga ne mozemo odrediti e
( e moze biti bilo sto), pa nam od toga i nema neke koristi.
Ako dakle i' ne smije biti nulvekter, tad A-eI mora biti ono sto se zove
_singularan operator_. Opet, nije bitno kako se stvar zove, bitno je
da mu determinanta mora biti 0 .

Kakve sad veze determinanta ima s tim? Pa, ovo gore ( (A-eI)i'=0_2 )
se moze shvatiti kao sustav dvije jednadbe s dvije nepoznanice, cija
je determinanta upravo det(A-eI) . Po Cramerovom pravilu, rjesenje je
jedinstveno akko je determinanta razlicita od 0 (nis strasno... samo
rijesis opcenit sustav 2x2 , i vidis sto se nalazi u nazivniku).
No rjesenje ovog cuda ocito nije jedinstveno, jer jedno rjesenje _jest_
(0,0) (a rekli smo da postoji jos jedno, jer i' nije nulvektor).
Dakle, 
	0=det(A-eI)=det([ 0 1 // 1 1 ]-[ e 0 // 0 e ])=
	=det[ -e 1 // 1 1-e ]=-e*(1-e)-1*1=-e+e^2-1=e^2-e-1 ,
pa je e nultocka polinoma k(x)=x^2-x-1 . (Inace, taj polinom,
det(A-xI) , se zove _karakteristicni polinom_, e se zove _svojstvena
vrijednost_ , a i' _svojstveni vektor_ matrice A - ali sve to nije
toliko bitno.:)

Primijetimo da je u meduvremenu i' prilicno ispao iz price, pa ona 
zamjena navedena gore mijenja samo e s f . Dakle, f je nultocka
tog istog polinoma (odnosno, f je takoder svojstvena vrijednost,
za svojstveni vektor j' ). 
Dakle, e i f dobivamo rjesavanjem kvadratne jednadbe:
	/e,f/=(1/+,-/sqrt(1+4))/2 , odnosno (npr.) 
	e=(1+sqrt(5))/2 & f=(1-sqrt(5))/2 .
Sto smo napravili? Matricu A shvatili smo kao matricu nekog linearnog
operatora, i kasnije napisali 
drugu matricu tog istog linearnog operatora
(samo u drugoj bazi, rekli bi ljudi 
koji dobro poznaju linearnu algebru),
koja je dijagonalna i prema tome se moze lako potencirati
( A'^n = [ e 0 // 0 f ]^n = [ e^n 0 // 0 f^n ] ).

No kakve to veze ima s potenciranjem same matrice A ? Prilicno velike, 
it turns out. Naime, ako s T oznacimo matricu u kojoj su zapisani
koeficijenti kojima se i' i j' izrazavaju pomocu i i j (ta matrica 
se inace zove _matrica prijelaza_), tad je to zapravo matrica identitete
(operatora v|->v ), samo u razlicitim bazama. Iz tog se dobivaju dvije
stvari:
+ obrnuti prijelaz ostvaruje se inverzom tog ("jedinicnog" operatora),
cija je matrica T^{-1} (jer komponiranju linearnih operatora odgovara
mnozenje matrica - tako je namjesteno, i uostalom zato je mnozenje
matrica tako ocajno komplicirano:).
+ A' se dobije tako da se A s jedne i s druge strane komponira s 
jedinicnim operatorom, i onda se ovaj prvi intepretira kao onaj koji
ima matricu T , a ovaj drugi kao njegov inverz. I to zaista stima - sto
radimo s vektorom v da bismo na njega djelovali s A ? Prvo promijenimo
bazu u (i',j') (ie, mnozimo s T - v|->Tv ), zatim djelujemo (u '-bazi)
s A' ( Tv|->A'Tv ), i nakon toga vratimo stvar natrag u (i,j) - kao
sto gore pise, mnozenjem s T^{-1} ( A'Tv|->T^{-1}A'Tv ). Sveukupno,
preslikavanje A preslikava v|->T^{-1}A'Tv , dakle Av=T^{-1}A'Tv .
To mora vrijediti za svaki v , pa je najjednostavnije staviti
A=T^{-1}A'T (odnosno A'=TAT^{-1} ).

Okej, kakve _to_ veze ima s potenciranjem:-? Pa gle...
	A^2=AA=(T^{-1}A'T)(T^{-1}A'T)=
	(*vidividi cuda velikoga, ovi u sredini se pokrate:-)*)
	=T^{-1}A'^2 T
	A^3=AAA=...T^{-1}A'^3 T .  I opcenito A^n=T^{-1}A'^n T .
	A A'^n znamo izracunati. Divota. :-)
Dakle, nas F_n ce biti prvi broj u matrici 
    T^{-1} [ ((1+sqrt 5)/2)^n 0 // 0 ((1-sqrt 5)/2)^n ] T [ 0 // 1 ] .
Samo jos treba odrediti matricu T 
(odnosno jedan njen dio...) i njen inverz.

T je neka matrica 2x2 , dakle oznacimo njene komponente slovima a do d .
T=[ a b // c d ] ((sad je jasno zasto su svojstvene vrijednosti bile
oznacene s e i f ;)) Inverz matrice je opcenito ruzna stvar, ali jedna
dosjetka nam ovdje moze pomoci.
Naime, potpuno je svejedno je li T pomnozena s nekim brojem 
r^{+-1} razlicitim od 0 . Time cemo samo umjesto i' i j' dobiti vektore
ri' i rj' , za koje se lako vidi da su takoder svojstveni
( Ari'=rAi'=rei'=eri' & analogno za j' i f ). Naravno, mnozenjem T s r 
mnozimo njenu determinantu s r^2 (provjeri ako ne vjerujes), pa je
jasno da namjestanjem r mozemo postici da det(rT) bude 1 (zapravo,
lazem. Mnozenjem/dijeljenjem s 
pozitivnim brojem r^2 ne mozemo promijeniti
predznak, pa je pravo rjesenje +-1 ; ali determinanta mijenja predznak 
zamjenom redaka (illi stupaca), pa -1 mozemo pretvoriti u 1 
zamjenom i' i j' - doduse, tada i e i f mijenjaju uloge, ali i tako nam
je bilo svejedno koji je koji).

Dakle, BSOMP det T=1 , odnosno ad-bc=1 . Sad se lako vidi da je u tom
slucaju T^{-1}=[ d -b // -c a ] 
( pomnozi s T ... dobijes [ ad-bc 0 // 0 ad-bc ] , 
sto je jedinicna matrica zbog gornje jednakosti).
Super. Dakle, trazi se prva komponenta od 
	[ d -b ] . [ ((1+sqrt 5)/2)^n 0 ] . [ a b ] . [ 0 ]
	[ -c a ]   [ 0 ((1-sqrt 5)/2)^n ]   [ c d ]   [ 1 ] .

Lak racun s matricama pokazuje da je to 
	F_n=bd*(((1+sqrt 5)/2)^n-((1-sqrt 5)/2)^n) .
Dakle, samo nam jos fali bd . No to lako dobijemo iz F_1=1 ...
	1=F_1=bd*((1+sqrt 5)/2-(1-sqrt 5)/2)=
	=bd*(1-1+sqrt 5+sqrt 5)/2=bd*2*(sqrt 5)/2=bd*sqrt 5 .
Iz tog odmah bd=1/sqrt 5 , pa je to broj s kojim treba pomnoziti
ono cudoviste ( e^n-f^n ) da se dobije F_n . QED. :-)

[/lesson]

Eto. Znam da nije najelegantnije, naravno, ali vjerujem da se iz
tog pristupa moze puno nauciti. 

Za domacu zadacu - rijesiti onu rekurziju iz lessona "Pell demistified"
na ovaj nacin. ;-)
Bye,

-- 
Veky        ... what if the lights go out maybe ...