Rij van fibonnaci,expliciet voorschrift.

[arie]

Met lineaire algebra bedoel je met matrices enzo kunnen rekenen?

ja

Kan je me nog uitleggen waarom dit ookalweer geld:


waarschijnlijk weet ik dit wel,aangezien ik matrices al ken, maar het is al een tijdje geleden dat ik dat nog heb gedaan. Ik weet dat je de labda en eenheidsmatrix nodig hebt om de eigenwaarden te bereken, is dat gewoon wat je eigenlijk de eerste keer deed?
Waarvoor staat die vi ? Want deze wordt een v, dus waarvoor staat de i? iets met de eenheidsmatrix?

Netter was geweest:

dus vector v onderlijnd.
Omdat F een 2x2 matrix is, zijn er maximaal 2 verschillende eigenwaarden, en , elk met hun eigen eigenvector resp.
De i is dus de index van de eigenwaarde en bijbehorende eigenvector.
Omdat we weten dat er 2 oplossingen zijn, heb ik daarna die index weggelaten.
Dit komt op hetzelfde neer als het oplossen van:

die je naar x oplost en die 2 oplossingen geeft:



Let wel dat we de eigenwaarden hier juist zoeken, en nog niet gevonden hebben.
We moeten dus nog oplossen:

waarbij lambda een reeel getal.

We willen dit hebben om

snel uit te kunnen rekenen.

Immers: als

dan is

(je kan dit zo nodig nog bewijzen met volledige inductie)
Noem nu de 2 oplossingen hiervan en . Als we vervolgens kunnen uitdrukken in de eigenvectoren:



(met a en b reele getallen) dan krijgen we:









dus ook:



Merk op dat we nu helemaal niet meer nodig hebben, maar fib(n) snel kunnen bepalen uit a, b en de eigenwaarden en eigenvectoren.
De macht van een reeel getal is veel sneller te bepalen dan de macht van een matrix, vergelijk bv:

met



De eenheidsmatrix hebben we gebruikt om

op te kunnen lossen, want anders zouden we krijgen

en een matrix min een reeel getal is niet gedefineerd.

Je kan wsch zelf wel aantonen dat:



(let op dat en hier de coordinaten van zijn, dus geen vectoren maar reele getallen)
en hiermee kunnen we



wel oplossen.

En: onze eerste matrix is toch opgebouwd uit de fibonacci getallen (want ik moet natuurlijk alles kunnen verklaren)
A^n=

met fib(0)=0 en fib (1)= 1 en dus geldt dat voor iedere n 1 ?

Lukt het je om dit te bewijzen met volledige inductie?
(merk overigens op dat we niet nodig hebben, zoals hierboven beschreven).

En deze heb ik ook nog gevonden: iemand die vanaf de lambda via de euclidische deling (d*q+r) verder gaat. Moet je maar eens bekijken als je geïnteresseerd bent: http://www.uhasselt.be/documents/uhasse ... RijenA.pdf

Leuke link!

[fibonnaci]

neen, dat bewijzen met volledige inductie kan ik niet.
Ik begrijp het concept, namelijk dat als het geldt voor het getal n, en voor n+1, het voor ieder getal geldt, maar ik kan het niet bewijzen.
Het is eigenlijk ook nog steeds niet vermeld hoe we aan onze waarden van de matrix bekomen:
0 1
1 1

Hoe komen we hieraan, volgens mij komt dit uit de matrix van:

voor iedere n 1 en fib(0)=0 en fib(1)=1
voor n=1 geeft dat dan:

of liever:

en om f(n) en f(n+1) (die van kolom 2)te weten, moeten we dit natuurlijk met de ?vector? v vermenigvuldigen(logisch nadenken met vermenigvuldigen met matrices, zo getallen 2de kolom matrix uitkomen:
v=

Hoe is dan iemand ooit op de eerste matrix gekomen (deze matrix:)


Ik doe hier zo moeilijk over omdat ik moet beginnen met in mijn berekening alles uit te leggen, dus ook van waar ieder getal komt. Wil je in je uitleg ook zeggen wat de voorwaarden zijn voor n? (n 1 ofzo...)

[arie]

We willen de rij van Fibonacci bepalen.
Hiervoor geldt:
fib(0)=0
fib(1)=1
en
fib(n+1)=fib(n) + fib(n-1)
voor n>=1.
Uitgaande van de huidige waarde en de vorige waarde kunnen we dus de volgende waarde bepalen.

Geef nu de huidige en de vorige waarde weer in een vector:



We zoeken dan een afbeelding F zodanig dat v afgebeeld wordt op w waarvoor geldt:



De vector w bevat dus de huidige en de volgende waarde, en die zijn beide uit v af te leiden.
Omdat we door die afbeelding F de waarden in deze vectoren in feite 1 fibonacci-waarde doorschuiven, kunnen we w straks opnieuw gebruiken om via F*w fib(n+1) en fib(n+2) te bepalen. En dit proces kunnen we blijven herhalen.

Nu de afbeelding F die v op w afbeeldt.
Noem



Je zoekt de waarden van a, b, c en d, zodanig dat



ofwel



Werk hiertoe het product uit volgens de definitie van het product van een matrix en een vector:



En die laatste 2 vectoren moeten gelijk zijn aan elkaar:



Het is nu vrij triviaal in te zien dat a=0 en b=1: fib(n) = 0*fib(n-1) + 1*fib(n)
en c=1 en d=1: fib(n+1) = 1*fib(n-1) + 1*fib(n),
waarmee we F bepaald hebben.

Er geldt dus voor alle n>=1 :




Vervolgens hebben we dit verder herleid naar :



Ook dit is inductief te bewijzen:
- basisstap: voor n=1 gaat direct over in .
- inductiestap:
Stel voor n=k geldt:



Dan geldt voor n=(k+1):







gebruik nu de inductie-hypothese:



gebruik nu :



hetgeen te bewijzen was.

BELANGRIJK: we hebben F bepaald, en kunnen met F^n vanuit [fib(0), fib(1)] de vector [fib(n), fib(n+1)] bepalen, maar we hoeven niet te weten hoe F^n er precies uit ziet!!!
Dankzij de eigenwaarden hebben we F^n uit de formule ge-elimineerd, en kunnen we volstaan met de machten van de eigenwaarden (= reele getallen ipv een matrix).


Maar wil je (terwijl het hier niet nodig is) toch aantonen dat



kan dit ook weer met volledige inductie:
- basisstap: neem n=1, wat staat er dan?
- inductiestap:
Neem aan dat het geldt voor F^k, dan geldt voor F^(k+1):



wat krijg je als je dit laatste matrixproduct uitwerkt?

[fibonnaci]

=
en aangezien n= k+1
=

vragen:
Moet dat van n=k+1 op einde van dat van jouw eerste er ook nietmeer bij?
Wat is de inductie-hypothese ookalweer?
Wat je in het begin zegt, over hoe de matrix bekomen, elimineert voor mij de nood voor de laatste inductiehypothese.

Vervolgens hebben we dit verder herleid naar :

Is dat in de post van 07 Mei 2011, 17:42 ??

Je zat knal op mijn vraag en hebt hem heerlijk uitgelegd. Dank je!
Hopelijk vermoei ik je niet te hard met al mijn vragen, deze zijn uit nieuwsgierigheid en gebrek aan logisch nadenken.
Dank je nogmaals!

[arie]

Een bewijs met volledige inductie van een stelling of formule bestaat uit 2 stappen:
[1] de basisstap: hierin bewijs je dat die stelling of formule waar is voor een bepaalde waarde van n, meestal n=0 of n=1.
[2] de inductiestap: hierin neem je aan (=de inductie-hypothese) dat de stelling of formule waar is voor n=k, en toon je vervolgens aan dat als dit zo is, dat de stelling/formule dan ook waar is voor n=k+1.
(ook hierop bestaan varianten, bv: "stel waarheid voor n=1 t/m k", maar dit hebben we hier niet nodig).

Bijvoorbeeld:
Door de basisstap bewijs je de juistheid voor het geval n=1, uit de inductie stap volgt dan de juistheid voor n=1+1=2, daaruit volgt weer de juistheid voor n=2+1=3, etc.

Dit zien we ook in het voorgaande bewijs van:



[1] basisstap: voor n=1 geldt:



Dit klopt volgens onze definitie van F.

[2] inductiestap:
Neem aan dat de formule geldt voor k:



deze aanname is de inductie-hypothese.

Nu geldt:



macht van een matrix:



gebruik nu de inductiehypothese voor k (we hebben aangenomen dat die waar is) en vervang F^k:



vermenigvuldig deze twee matrices volgens de definitie van het matrixproduct:



en herschrijf dit in termen van (k+1):



waarmee is aangetoond: ALS de formule geldt voor n=k, DAN geldt deze ook voor n=(k+1).


mbt je vraag over : dat klopt.
In die post hebben we dat wat losjes beredeneerd, later bewezen via volledige inductie.

Het idee is dat als je een fibonacci-vector v vermenigvuldigt met F, je de volgende fibonacci-vector krijgt.
Je kan dit lezen als:



schrijf de macht uit:



plaats haakjes:



werk vervolgens alle haakjes weg:











Je ziet: elke keer dat we met F vermenigvuldigen deze vector 1 fib-waarde doorschuift.

Dus als we n keer met F vermenigvuldigen, ofwel: levert dit

[fibonnaci]

mijn vraag van inductie-hypothese was eigenlijk een slechte, aangezien ik dacht dat je iets speciaal had gedaan in die stap, maar je had gewoon de matrices tussen de haken vervangen door de ene matrix, wat we in het begin hadden aangenomen. Ik was gewoon even verstrooid.

Ik denk dat ik nu alles weet dat ik moet weten, en dat het nu tijd wordt om hem echt helemaal uit te schrijven. Helaas ben ik vanaf woensdag weg voor een paar daagjes, en zal ik hem waarschijnlijk niet op tijd opgeschreven hebben.
Mag ik hem als ik klaar ben eens doorsturen via een privé-bericht, dan kan je als je wilt nog opmerkingen geven?

Tenslotte:
Hier is nog een bewijs dat de verhouding van twee opeenvolgende fibonacci getallen phi benaderd. Zou je er eens naar willen kijken en eventueel opmerkingen bij geven?
linkje:http://www.phys.tue.nl/TULO/guldensnede/index5.html

Nogmaals bedankt voor al je hulp!

[fibonnaci]

helaas nog op een kleine onzekerheid gestuit:
vanwaar komt volgende formule:



je gebruikt hem in je laatste post vorige pagina en eerste post deze pagina.

[arie]

We hadden de formule:



ofwel:



We zouden fib(n) dus kunnen bepalen uit het product van de n-de macht van een matrix met de vector [0,1].
De n-de macht van een matrix berekenen is in het algemeen veel werk, fib(n) zou dan nog eenvoudiger en sneller te bepalen zijn door gebruik te maken van de recursieve definitie: f(n)=f(n-1)+f(n-2).

Daarom maken we hier gebruik van de eigenwaarden en eigenvectoren, waarvoor geldt:

en waarvoor ook:

Voor deze vectoren v geldt dat we het product van F met v kunnen vervangen door het product van een reeel getal (=lambda) met v, en evenzo de macht F^n door lambda^n.
En de macht van een reeel getal kunnen we wel snel uitrekenen voor elke n.

Nu hebben we voor de eigenwaarden en eigenvectoren 2 oplossingen gevonden: en .
Omdat geen eigenvector is lukt het voor deze vector niet direct om matrix F te vervangen door een getal lambda.

Maar omdat en niet op dezelfde lijn liggen (=onafhankelijk zijn), kunnen we wel elke andere vector in het vlak, dus ook [0,1], uitdrukken in deze 2 vectoren:



met a en b reele getallen die we kunnen bepalen (en die je ook bepaald hebt).

En dit hebben we gebruikt voor de afleiding (in het kort weergegeven):



Hiermee kunnen we fib(n) direct bepalen uit het product van reele getallen en machten van reele getallen.