From veky@student.math.hr Tue Nov 18 13:44:37 2003
Subject: Re: pomoc?!?
Lines: 208
Message-ID: <slrnbrjt66.q21.veky@student.math.hr>
References: <bobifb$aij$1@bagan.srce.hr>
<slrnbql0el.9ua.veky@student.math.hr> <bovs4d$var$1@bagan.srce.hr>
<slrnbr71js.m4.veky@student.math.hr> <bp6k19$hf6$1@bagan.srce.hr>
>> Jesam li lijepo rekao da je to (jedino) zabranjeno pitanje;-? [:-)]
> ali zanima me odgovor.
Curiosity killed the cat, nisi nikad za to cuo;-? :-p
>> Ak si u Zagrebu, mozemo na kavu jednom...
> nisam.
Istra?
>nema smisla da to sad pisem
>> po Usenetu.
>
>daj napisi onda na mail.
Biser. :-p
No dobro, evo kad si tvrdoglav.
[lesson type=heuristic title="Pell demistified"]
Trazim rjesenja od 2a^2=c^2+2 . Kvadrat broja jednak je kvadratu njemu
suprotnog broja, pa jednom rjesenju (a,c) u prirodnim brojevima
odgovaraju maksimalno 4 rjesenja u cijelim brojevima (+-a,+-c) .
Dakle, ekvivalentno je dokazati da jednadba ima beskonacno mnogo
_prirodnih_ rjesenja (nulu smatram prirodnom). (U daljem tekstu
a i c su nenegativni, odnosno prirodni).
Ta beskonacnost je ocito prebrojiva (uredenih parova prirodnih
brojeva ima prebrojivo mnogo), a buduci da ocito strogo
vecem a-u odgovara strogo veci c i obrnuto,
moze se poredati po velicini istog tipa kao i
prirodni brojevi (tj. postoji najmanje (ie, ono s najmanjim a , npr.)
rjesenje, onda postoji najmanje od preostalih, itd.). Dakle,
sva rjesenja se mogu prirodno poredati kao
(a_0,c_0)<(a_1,c_1)<(a_2,c_2)<....
To sugerira da idemo traziti dva niza,
a_0<a_1<a_2<.... i c_0<c_1<c_2<.... ,
takva da je za svaki prirodni n , 2a_n^2=c_n^2+2 .
Buduci da a_n (a tako i c_n ) strogo raste s n , a nalazimo se u
prirodnim brojevima gdje je svaki strogi porast, porast za bar 1 ,
za svaki prirodni M su skoro svi (ie, svi osim konacno mnogo)
a_n i c_n veci od M . Dakle, zanima nas ponasanje gornje jednadbe
za po volji velike a i c . Tada onaj 2 postaje zanemarivo malen,
pa dobijemo 2a^2 ~=~ c^2 , odnosno c/a ~=~ sqrt(2) ,
odnosno c/a predstavlja
(jako dobru) racionalnu aproksimaciju iracionalnog broja sqrt(2) .
Kako znati koje su aproksimacije dovoljno dobre (tako da razlika
izmedu 2a^2 i c^2 iznosi samo 2 )? Prvi korak je doci sto blize toj
idealnoj situaciji - 2 nije najmanja moguca (apsolutna) razlika.
0 naravno ne mozemo postici - to bi znacilo racionalnost od sqrt(2) ;
ali zato mozda mozemo postici 1 . Za takvo nesto trebali bismo ocito
jednadbu podijeliti s 2 , no za to nam na prvi pogled smeta c^2 .
Naravno, na drugi pogled, c zapravo mora biti paran , c=2d , pa
jednadba postaje a^2=2d^2+1 - upravo ono sto smo zeljeli. Sad je
dakle a/d najbolja (u smislu najmanje apsolutne razlike a^2 i 2d^2 )
racionalna aproksimacija za sqrt(2) .
Naravno, za ocekivati je, kako se a i d povecavaju, da ce aproksimacija
biti sve bolja u smislu apsolutne razlike sqrt(2) i a/d
(inFact, lako se vidi da je a/d slightly veci od sqrt(2) , pa je
razlika zapravo a/d-sqrt(2) ), no mozemo
reci da je to zato sto imamo sve vise ( ~~ d ) mogucnosti za odabir
nazivnika (brojnik je time odreden iz gornje jednadbe). No greska
se smanjuje cak brze nego sto d raste, u smislu da se njihov produkt
smanjuje:
d*(a/d-sqrt(2))=a-d*sqrt(2)=1/(a+d*sqrt(2)) (*razlika kvadrata*)
Ofcourse, kako a i d rastu, raste i a+d*sqrt(2) , pa je njegova
reciprocna vrijednost sve manja.
No gornje raspisivanje nam daje jos nesto.
(Za pratiti sljedecu ideju potrebno je znanje o kompleksnim brojevima.)
(a+d*sqrt(2))(a-d*sqrt(2))=1
donekle podsjeca na z*z^~=|z|^2 (sa ^~ je oznaceno konjugiranje)
u kompleksnim brojevima (inFact, analogija je i veca nego na prvi
pogled - samo pod korijenom zamijeni 2 s -1 ;). U |C , dakle, postoji
preslikavanje || (modul), koje ima gore navedeno
svojstvo, i osim toga |z|=|z^~| . U |C bi gornja jednadba
dakle povlacila da je |a+d*i|=|a-d*i|=1 , odnosno da su
a+d*i i njegov konjugat "jedinicni" brojevi (na jedinicnoj kruznici).
Mozemo li nesto slicno zakljuciti u nasem slucaju, kad umjesto
i imamo sqrt(2) ? Da. Kao prvo, ako imamo broj a+d*sqrt(2) , njemu
su jednoznacno odredeni njegov "racionalni" i "iracionalni" dio,
Ra(a+d*sqrt(2))=a i Ir(a+d*sqrt(2))=d
(po uzoru na Re i Im ), jer se svaki takav broj
moze samo na jedan nacin tako zapisati (za cijele a i d ) - naime,
a1+d1*sqrt(2)=a2+d2*sqrt(2) i d1 != d2
povlaci sqrt(2)=(a1-a2)/(d2-d1) , sto je racionalno,
dakle kontradikcija. So, mora biti d1=d2 , a po tome odmah i a1=a2 .
Sad mozemo definirati i "konjugiranje" na takvim brojevima,
w^~~:=Ra(w)-Ir(w)*sqrt(2) . Modul bas i ne mozemo
(dolje ce postati jasno zasto), ali mozemo
kvadrat modula (koji ce biti dovoljno dobar, jer bit ce nam
bitno samo mnozenje, i broj 1 kao njegova vrijednost; a
kvadrat umnoska je umnozak kvadrata i kvadrat jedinice je jedinica),
q(w):=w*w^~=(Ra(w)+sqrt(2)*Ir(w))(Ra(w)-sqrt(2)*Ir(w))=
(Ra w)^2-2*(Ir w)^2 .
To je cijeli broj za w gornjeg oblika, ali teoretski moze biti
negativan (npr. q(1+3*sqrt(2))=1^2-2*3^2=-17 ), pa bi onda modul
kao korijen iz toga
mogao biti nerealan, sto ne zelimo. Zato necemo komplicirati i
zadrzat cemo se na q kao kvadratu modula.
Jedinicni kompleksni brojevi imaju jedno lijepo svojstvo, a to je
da su zatvoreni na mnozenje - produkt dva jedinicna je opet jedinican,
odnosno apsolutna vrijednost cuva mnozenje:
|z1*z2|=|z1|*|z2| . To je zapravo direktna posljedica toga da vec
komplement cuva mnozenje: (z1*z2)^~=z1^~*z2^~ .
To potpuno jednako vrijedi i u sqrt(2)-slucaju:
(a+b*sqrt(2))^~*(c+d*sqrt(2))^~=(a-b*sqrt(2))(c-d*sqrt(2))=
=(a*c+2*b*d)-(a*d+b*c)*sqrt(2)=((a*c+2*b*d)+(a*d+b*c)*sqrt(2))^~=
=((a+b*sqrt(2))*(c+d*sqrt(2)))^~ . So,
q(w1*w2)=(w1*w2)*(w1*w2)^~=w1*w2*w1^~*w2^~=
=w1*w1^~*w2*w2^~=q(w1)*q(w2) ,
odnosno umnozak dvaju brojeva oblika a+d*sqrt(2) q-a jednakog
1 opet je takav.
Kako dobiti beskonacno mnogo brojeva q-a jednakog 1 ? Pa, ocito
nam trebaju dva takva, i onda jednog uzastopce mnozimo ovim drugim,
ostajuci uvijek na "jedinicnoj kruznici". Stovise,
q(1)=(Ra(1))^2-2*(Ir(1))^2=1-2*0=1 , odnosno onaj pocetni
broj moze biti 1 (ne onaj kojim mnozimo, jer zelimo dobivati
razlicite brojeve:). Dakle, osim trivijalnog w_0=1 , treba nam
jos jedan takav, w_1 , a onda ce svi ostali biti njegove potencije,
w_n=w_1^n za svaki prirodni n .
(Kasnije cemo vidjeti, zapravo vidjeli smo u prethodnom
postu, da njima Ra-ovi i Ir-ovi
strogo rastu, dakle svi ce biti razliciti.)
Dakle, sveli smo problem na nalazenje jednog netrivijalnog
rjesenja, odnosno jedne jako dobre (u odnosu na velicinu nazivnika)
aproksimacije sqrt(2) . S nazivnikom 1 imali bismo a^2=2*1^2+1=3 ,
sto nema rjesenja u cijelim brojevima. Prvi sljedeci na redu je
2 , i a^2=2*2^2+1=9 daje a=3 (i zaista, 3/2=1.5 je prilicno dobra
aproksimacija za sqrt(2) , uzevsi u obzir da joj je nazivnik samo 2 :).
So, w_1=3+2*sqrt(2) , odnosno a_1=Ra w_1=3 & d_1=Ir w_1=2 .
Sad znamo da je za svaki prirodni n , a_n=Ra w_1^n i d_n=Ir w_1^n ,
odnosno potencirajuci simbolicki 3+2*sqrt(2) mozemo dobiti
a-ove i d-ove (Naravno, sjetimo se otkud nam d , c_n=2d_n ).
No to jos uvijek ukljucuje racunanje sa sqrt(2) .
Mozemo li se nekako njega osloboditi, i dobiti
racun sa samo cijelim brojevima? Mozemo. Kljuc je u rekurzivnom
shvacanju potenciranja.
a_{n+1}+d_{n+1}*sqrt(2)=w_{n+1}=w_1^{n+1}=w_1^n*w_1=w_n*w_1=
=(a_n+d_n*sqrt(2))*(3+2sqrt(2))=(3a_n+4d_n)+(2a_n+3d_n)sqrt(2) ,
so, a_{n+1}=3a_n+4d_n & d_{n+1}=2a_n+3d_n .
To bi bio sustav rekurzija za a_n i d_n , koji vec moze posluziti
za racunanje ta dva niza (a time i c=2d ) samo pomocu cijelih brojeva,
no mozemo li dobiti rekurziju sa samim a-ovima (ili d-ovima)?
Mozemo i to, i jedan vrlo elegantan nacin
da se to ucini ukljucuje elementarnu
linearnu algebru (matrice i problem svojstvenih vrijednosti), no to
ipak ne bih trenutno raspisivao. Idemo radije drugim putom.
Rekli smo da je a_n "racionalni dio" od w_1^n . Gore smo indirektno
vidjeli da imaju smisla funkcije Ra i Ir , pa smo pomocu njih
egzaktno definirali fonkciju ^~ ("konjugiranje"). Mogli smo i
obrnuto - ako imamo ^~ , tad Ra i Ir mozemo definirati (jednako
kao u |C-slucaju) s Ra(w):=(w+w^~)/2 & Ir(w):=(w-w^~)/(2*sqrt(2)) .
Dakle, a_n=((3+2sqrt(2))^n+(3-2sqrt(2))^n)/2 , odnosno a_n je
aritmeticka sredina n-tih potencija brojeva 3+-2sqrt(2) . Kad bi te
n-te potencije zadovoljavale neku (jednu te istu) linearnu rekurziju,
tad bi je ocito zadovoljavao i niz a
(opcenito, linearna kombinacija tih n-tih potencija je
takoder rjesenje; a aritmeticka sredina je linearna kombinacija
s koeficijentima 1/2,1/2 ). Pokusajmo naci tu rekurziju.
Dakle, neki w^n je linearno izrazen pomocu nekoliko ( k ) prethodnih:
w^n=r_1*w^{n-1}+r_2*w^{n-2}+...+r_k*w^{n-k} .
q(w^{n-k})=1^{n-k}=1 a q(0)=0^2-2*0^2=0 , pa w^{n-k} != 0 , dakle
njime smijemo podijeliti gornju rekurziju. Dobijemo
w^k=r_1*w^{k-1}+r_2*w^{k-2}+...+r_{k-1}*w+r_k ,
sto ne ovisi o n i zapravo kazuje da je w nultocka polinoma
p(x)=x^k-r_1*x^{k-1}-...-r_k .
Buduci da rekurzija mora biti ista i za (3+2sqrt(2))^n
i za (2-2sqrt(2))^n , obje su baze nultocke od p .
Stvar se svela na nalazenje polinoma cije su nultocke
3+-2sqrt(2) . Naravno, prvi guess je
p(x)=(x-(3+2sqrt(2))(x-(3-2sqrt(2)))=
=((x-3)-2sqrt(2))((x-3)+2sqrt(2))=(x-3)^2-(2sqrt(2))^2=
=x^2-6x+9-4*2=x^2-6x+1 , i to je sasvim ok.
Dakle, k=2 & r_1=6 & r_2=-1 , odnosno rekurzija glasi
w_{n+2}=6w_{n+1}-w_n .
To je rekurzija za a-ove , no lako se vidi da i d-ovi moraju
zadovoljavati tu istu rekurziju (takoder su izrazeni kao
linearna kombinacija n-tih potencija - s koeficijentima
1/(2sqrt(2)),-1/(2sqrt(2)) ). Takoder i c-ovi (inFact, i oni
su linearna kombinacija gornjih - s koeficijentima 0,2 ;).
Jos je samo ostalo odrediti pocetne uvjete. S obzirom na to da
je dubina rekurzije 2 , dovoljno je odrediti prva dva clana.
w_0=1 & w_1=3+2sqrt(2) , dakle
a_0=Ra(1)=1
c_0=2d_0=2Ir(1)=2*0=0
a_1=Ra(3+2sqrt(2))=2
c_1=2d_1=2Ir(3+2sqrt(2))=2*2=4 .
[/lesson]
Sad zadovoljan:-?
I jel sad jasno zasto mi se nije dalo pisati:-? :-)
--
Veky ... da vidim kako puca ova noc ...