quote:
Op woensdag 28 november 2012 20:50 schreef Amoeba het volgende:Het wiskundeboek smijt weer eens met bewijzen. In het hoofdstuk 'Toepassing van complexe getallen' krijgen we nu te maken met complexe getallen i.c.m. recursieve formules. Bij het opstellen van een directe formule van een lineaire differentievergelijking van de tweede orde zijn blijkbaar complexe getallen heel nuttig. Goed, prima prima. Zij geven mij de aanpak om bij de formule
u
n=a*u
n-1+b*u
n-2de substitutie u
n = g
n door te voeren, dan te delen door g
n-2 en dan de tweedegraadsvergelijking op te lossen. Wanneer geldt D<0, dan wordt de aanpak gegeven dat:
u
n = (Acos(nφ)+Bsin(nφ))g
n met φ het argument van g
1 en g de modulus van g
1, waarbij g
1 een van de oplossingen van de genoemde tweedegraadsvergelijking is. Maar waarom geldt deze aanpak/formule, is mijn vraag.
Kijk eens aan, weer zo'n klassiek onderwerp. Ik heb net enige tijd geleden een
artikel van Daniel Bernoulli (uit 1728) over lineaire recursieve rijen bestudeerd waarin onder meer de uitdrukking voor de algemene term van de rij van Fibonacci wordt afgeleid. Die formule is vernoemd naar Jacques Binet (1786-1856), maar de formule én de afleiding ervan waren al veel eerder bekend. Typisch gevalletje Stigler's law dus. De studie van lineaire recurrente rijen was een
hot item in de eerste decennia van de 18e eeuw waar diverse wiskundigen zich mee bezig hielden, zoals verschillende leden van de familie Bernoulli, Pierre Rémond de Montmort (1678-1719), Christian Goldbach (1690-1764), en ook de welbekende Abraham de Moivre (1667-1754).
De oplossing van De Moivre werkte met wat we nu voortbrengende functies noemen, en splitsing daarvan in deelbreuken. Zo kan de algemene term van een lineaire recursieve rij worden geschreven als een lineaire combinatie van de algemene termen van een stel convergente meetkundige rijen waarvan de som gegeven is door elk van de lineaire partiële breuken van de voortbrengende functie. Maar deze methode om een gesloten uitdrukking te vinden voor de algemene term van een lineaire recursieve rij is betrekkelijk omslachtig, en is (anders dan thenxero suggereert) ook niet nodig om je vragen te beantwoorden. De methode met de zogeheten
karakteristieke vergelijking (zoals voor het eerst gepubliceerd door Daniel Bernoulli, die evenwel spreekt van een
aequatio primaria) is een stuk praktischer.
Laten we voor een goed begrip eerst eens kijken naar hét schoolvoorbeeld van een tweede orde lineaire recursieve rij, de rij van Fibonacci (eigenlijk: Leonardo van Pisa, c.1170 - c.1250):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
Deze rij wordt, zoals bekend, gedefinieerd door het volgende recursieve voorschrift:
u
0 = 0, u
1 = 1, u
n = u
n-1 + u
n-2Om nu een gesloten (niet recursieve) uitdrukking te vinden voor de algemene term u
n kun je beginnen met te bedenken dat op grond van het lineaire recursievoorschrift u
n = u
n-1 + u
n-2 elke lineaire combinatie van rijen die aan dit voorschrift voldoen ook weer aan dit voorschrift zal voldoen. Dus, als {a
n} en {b
n} twee rijen zijn die voldoen dan zal een rij {c
n} met c
n = α∙a
n + β∙b
n en met willekeurige constanten α en β ook voldoen aan het recursievoorschrift.
Goed, maar hoe vinden we nu een gesloten (niet recursieve) uitdrukking voor de termen van (alle) rijen die voldoen aan zo'n recursievoorschrift? Wel, om te beginnen is het duidelijk dat er geen rekenkundige rijen kunnen zijn die hier voldoen, want dan zou u
n - u
n-1 constant moeten zijn, en zou daarmee ook u
n-2 constant moeten zijn (i.e. onafhankelijk van n), en dat kan alleen als alle termen nul zijn. Maar dat is een triviale oplossing van het recursievoorschrift waar we niet naar op zoek zijn.
De volgende gedachte is om te proberen of er meetkundige rijen zijn die aan het recursievoorschrift voldoen. Laten we zeggen dat de reden van zo'n meetkundige rij λ is, dan moet voor de algemene term u
n dus gelden:
u
n = u
0∙λ
nOp grond van het recursievoorschrift u
n = u
n-1 + u
n-2 geldt dan:
u
0∙λ
n = u
0∙λ
n-1 + u
0∙λ
n-2Na herleiding van het rechterlid op nul en het buiten haakjes halen van de gemeenschappelijke factor u
0∙λ
n-2 geeft dit:
u
0∙λ
n-2∙(λ
2 - λ - 1) = 0
Nu kan deze voorwaarde alleen gelden ongeacht de waarde van u
0 en ongeacht de waarde van λ als de uitdrukking tussen haakjes nul is, dus:
λ
2 - λ - 1 = 0
Dit is een vierkantsvergelijking met als oplossingen λ
1 = (1 + √5)/2 en λ
2 = (1 - √5)/2. Er zijn dus in ieder geval
twee lineair onafhankelijke meetkundige rijen {a
n} en {b
n} met reden λ
1 resp. λ
2 die voldoen aan de recursie u
n = u
n-1 + u
n-2. En aangezien elke lineaire combinatie hiervan ook voldoet hebben we dus in het algemeen:
u
n = α∙((1 + √5)/2)
n + β∙((1 - √5)/2)
nMaar, hebben we hiermee nu wel
alle mogelijke oplossingen voor de recursie u
n = u
n-1 + u
n-2 gevonden? Het antwoord is
ja, want een rij die aan dit recursievoorschrift voldoet ligt volledig vast als twee opeenvolgende termen zijn gegeven, en door die in te vullen in bovenstaande uitdrukking voor de algemene term krijgen we twee lineaire vergelijkingen in α en β en daarmee ook de waarden van α en β die voldoen aan een gegeven specifieke rij.
Voor de rij van Fibonacci hebben we u
0 = 0 en u
1 = 1. Invullen hiervan in bovenstaande uitdrukking voor de algemene term levert:
α∙1 + β∙1 = 0, α∙((1 + √5)/2) + β∙((1 - √5)/2) = 1
Oplossen van dit stelsel geeft α = 1/√5 en β = -1/√5, zodat we dus als uitdrukking voor de algemene term u
n van de rij van Fibonacci krijgen:
Goed, we zien dat het oplossen van een tweede orde lineaire recursie (met constante en reële coëfficiënten in het recursievoorschrift) leidt tot een vierkantsvergelijking met reële coëfficiënten, en deze kan, zoals bekend, ook twee (toegevoegd) complexe wortels bezitten, namelijk als de discriminant van de vierkantsvergelijking negatief is. Nu begrijp je dus waarom het met deze methode kan gebeuren dat we als algemene term voor een tweede orde lineaire recursieve rij een uitdrukking krijgen waarin complexe getallen voorkomen, en dat terwijl de rij
zelf uitsluitend uit reële getallen bestaat.
Natuurlijk rijst nu de vraag of het niet toch mogelijk is het gebruik van complexe getallen in de uitdrukking voor de algemene term van een tweede orde lineaire recursieve rij te vermijden, omdat de termen van de rij zelf immers reëel zijn. Welnu, het antwoord op deze vraag luidt bevestigend, maar de manier waarop ligt niet zo voor de hand, en daarmee ben ik aangekomen bij je laatste vraag.
Het blijkt mogelijk om de uitdrukking voor de algemene term een tweede orde lineaire recursieve rij met complexe getallen om te schrijven naar een goniometrische vorm. Maar:
waarom is dat zo? Wat hebben goniometrische functies te maken met een eenvoudige rij die voldoet aan een lineair tweede orde recursievoorschrift?
Een tipje van de sluier wordt al opgelicht als je kijkt naar bepaalde goniometrische identiteiten voor de sinus of cosinus van een veelvoud van een hoek. Om deze af te leiden begin ik even met de volgende formules van Simpson voor de som van twee sinussen of cosinussen die je uiteraard kent:
cos θ + cos φ = 2∙cos ½(θ + φ)∙cos ½(θ - φ)
sin θ + sin φ = 2∙sin ½(θ + φ)∙cos ½(θ - φ)
Deze identiteiten kun je, althans voor 0 < | θ - φ | < π, begrijpen als een eenvoudige consequentie van een stelling uit de elementaire meetkunde, als we ze als volgt herschrijven:
½(cos θ + cos φ) = cos ½(θ - φ)∙cos ½(θ + φ)
½(sin θ + sin φ) = cos ½(θ - φ)∙sin ½(θ + φ)
In woorden: het gemiddelde van de cosinussen of sinussen van twee hoeken is gelijk aan de cosinus resp. sinus van het gemiddelde van de hoeken, maar dan wel vermenigvuldigd met een schaalfactor die gelijk is aan de cosinus van het halve verschil tussen de hoeken.
Dat dit zo moet zijn is evident omdat een lijn door het middelpunt van een cirkel die een koorde van de cirkel middendoor deelt loodrecht op de koorde staat. Omgekeerd deelt een lijn door het middelpunt van een cirkel die een koorde van de cirkel loodrecht snijdt de koorde middendoor (Euclides,
Elementen, boek III, stelling 3). Een equivalente formulering van deze stelling is dat een lijn door het middelpunt van een cirkel die een koorde van de cirkel middendoor deelt de bissectrice is van de middelpuntshoek die wordt omspannen door de koorde en dat omgekeerd de bissectrice van een middelpuntshoek in een cirkel de koorde die de middelpuntshoek omspant middendoor deelt. Hierbij is steeds te veronderstellen dat de koorde niet door het middelpunt van de cirkel gaat en dus zelf geen middellijn is.
Kies je (met 0 < | θ - φ | < π) twee punten op de eenheidscirkel met coördinaten A(cos θ ; sin θ) en B(cos φ ; sin φ) dan heeft het midden M van de koorde AB die deze twee punten verbindt uiteraard de coördinaten (½(cos θ + cos φ) ; ½(sin θ + sin φ)). Maar nu ligt M op de bissectrice van ∠AOB, en deze bissectrice snijdt de eenheidscirkel dus in het punt C(cos ½(θ + φ) ; sin ½(θ + φ)). En aangezien OM loodrecht staat op AB is OM : OC = OM : OA = cos ∠MOA = cos ½(θ - φ). Punt M is dus het beeld van punt C bij een meetkundige vermenigvuldiging ten opzichte van de oorsprong met een factor cos ½(θ - φ), zodat de coördinaten van punt M ook gelijk zijn aan (cos ½(θ - φ)∙cos ½(θ + φ) ; cos ½(θ - φ)∙sin ½(θ + φ)), en dus is ½(cos θ + cos φ) = cos ½(θ - φ)∙cos ½(θ + φ) en tevens ½(sin θ + sin φ) = cos ½(θ - φ)∙sin ½(θ + φ).
Substitueer je in bovenstaande formules van Simpson θ = nψ en φ = (n-2)ψ, dan krijg je:
cos nψ + cos (n-2)ψ = 2∙cos (n-1)ψ∙cos ψ
sin nψ + sin (n-2)ψ = 2∙sin (n-1)ψ∙cos ψ
En dit kun je ook schrijven als:
cos nψ = 2∙cos ψ∙cos (n-1)ψ - cos (n-2)ψ
sin nψ = 2∙cos ψ∙sin (n-1)ψ - sin (n-2)ψ
Dit zijn recursieve betrekkingen voor de cosinus en sinus van een veelvoud van een hoek. Maar dat niet alleen, je ziet dat dit tweede orde recursieve betrekkingen zijn. Als we een rij hebben gedefinieerd door u
n = cos nψ óf door u
n = sin nψ, dan voldoet deze rij op grond van bovenstaande recursieformules dus aan:
u
n = 2∙c∙u
n-1 - u
n-2met c = cos ψ. Oefening: leid nu zelf aan de hand van deze recursieve betrekking gesloten (niet recursieve) uitdrukkingen af voor de algemene term u
n van deze rijen, zowel voor u
n = cos nψ als voor u
n = sin nψ.
Nu we zien waarom goniometrische rijen met als termen sinussen of cosinussen van opeenvolgende gehele veelvouden van een hoek altijd voldoen aan een tweede orde lineaire recursieve betrekking wordt het al wat inzichtelijker waarom er überhaupt goniometrische functies opduiken in de gesloten (niet recursieve) uitdrukkingen voor bepaalde rijen die voldoen aan een tweede orde lineaire recursieve betrekking.
Twee voor de hand liggende vragen zijn nu: (a) is het
altijd mogelijk de uitdrukking voor de algemene term van een reële rij die voldoet aan een tweede orde lineaire recursie om te schrijven naar een goniometrische vorm wanneer de karakteristieke vergelijking twee (toegevoegd) complexe wortels heeft en (b) hoe kunnen we dat dan doen?
Het is inderdaad altijd mogelijk om de uitdrukking voor de algemene term u
n van een reële rij te herleiden tot een goniometrische vorm als de rij voldoet aan een tweede orde lineaire recursieve betrekking en de karakteristieke vergelijking twee (toegevoegd) complexe wortels heeft. Om dit te bewijzen gaan we uit van een reële rij met algemene term u
n die voldoet aan een tweede orde lineaire recursie en waarbij de karakteristieke vergelijking twee toegevoegd complexe wortels λ
1 en λ
2 heeft. De algemene oplossing voor de recursie is dan:
u
n = α∙λ
1n + β∙λ
2nwaarbij α en β constanten zijn, die
in principe zowel reëel als complex kunnen zijn. Nu weet je dat we complexe getallen ook in polaire vorm kunnen omzetten. Laten we zeggen dat:
λ
1 = r(cos φ + i∙sinφ)
dan is:
λ
2 = r(cos φ - i∙sinφ)
aangezien λ
1 en λ
2 elkaars geconjugeerde zijn. Nu weet je ook dat:
e
iφ = cos φ + i∙sin φ
e
-iφ = cos φ - i∙sin φ
zodat we hebben λ
1 = r∙e
iφ en λ
2 = r∙e
-iφ en we dus de uitdrukking voor de algemene term van onze rij kunnen schrijven als:
u
n = α∙r
n∙e
inφ + β∙r
n∙e
-inφIntroduceren we nu twee nieuwe parameters A en B als volgt:
A = α + β
Β = i(α - β)
dan hebben we dus:
α = ½(A - iB)
β = ½(A + iB)
en kunnen we de uitdrukking voor de algemene term van onze rij dus schrijven als:
u
n = ½(A - iB)∙r
n∙e
inφ + ½(A + iB)∙r
n∙e
-inφoftewel:
u
n = A∙r
n∙½∙(e
inφ + e
-inφ) - B∙r
n∙½∙i∙(e
inφ - e
-inφ)
En aangezien:
cos nφ = (e
inφ + e
-inφ)/2
sin nφ = (e
inφ - e
-inφ)/2i
kunnen we de uitdrukking voor voor de algemene term van onze rij dus inderdaad schrijven als:
u
n = r
n∙(A∙cos nφ + B∙sin nφ)
Maar hiermee zijn we er nog niet, want we hadden opgemerkt dat α en β, en dus ook A en B, in principe
complexe grootheden kunnen zijn. Het is wel duidelijk dat
als A en B reëel zijn dat dan ook bovenstaande uitdrukking voor u
n reëel is, maar nu moeten we het
omgekeerde laten zien, namelijk dat A en B reëel zijn
als de termen van de rij reëel zijn. Maar dit is niet moeilijk aan te tonen. Substitutie van n = 0 en n = 1 geeft:
u
0 = A, u
1 = A∙r∙cos φ + B∙r∙sin φ
Welnu, u
0 is reëel en dus is A ook reëel en daarmee is A∙r∙cos φ ook reëel. En aangezien u
1 reëel is en r∙sin φ reëel is en tevens
ongelijk aan nul omdat λ
1 ≠ λ
2 volgt dat B ook reëel is.
Hiermee is dus aangetoond dat de algemene term van elke tweede orde lineaire recursieve rij met reële termen waarvan de karakteristieke vergelijking twee toegevoegd complexe wortels heeft kan worden uitgedrukt in de goniometrische gedaante u
n = r
n∙(A∙cos nφ + B∙sin nφ) zonder gebruik van complexe getallen.
QED
[ Bericht 0% gewijzigd door Riparius op 01-12-2012 15:44:36 ]