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 ...