Inhomogene recurrente betrekkingen

Moderators: ArcherBarry, Fuzzwood

Berichten: 19

Inhomogene recurrente betrekkingen

Gegeven een inhomogene recurrente betrekking, probeer een expliciete formule te vinden voor de volgende recurrente betrekkingen:
\( a_{i+1} = a_i + i \)
met
\( a_0 = 0 \)
\( a_{i+1} = 2 \cdot a_i + 2^i \)
met
\( a_0 = 0\)
Het oplossen van homogene recurrente betrekkingen snap ik best goed. Met behulp van de karakteristieke vergelijking is dat redelijk eenvoudig te doen, maar ik snap niet echt hoe je inhomogene recurrente betrekkingen moet oplossen.

Op internet worden vaak al aannames gemaakt over hoe de oplossing eruit moet komen zien bijvoorbeeld
\(a_i = c_i \cdot 2^n \)
en soms wordt het weggedeeld uit de betrekking, maar hoe het nu precies zit kan ik nergens duidelijk vinden.

Wie kan mij op weg helpen met bovenstaande recurrente betekkingen of me wijzen op een goede uitleg?

Alvast bedankt! ;)

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Eider, heb je al misschien iets gehad over tweede orde differentiaalvergelijkingen met constante coëfficiënten? Zo ja, dan is het uitleggen een stuk makkelijker ;) .

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Flamey, bedankt voor je snelle antwoord! Ik heb vorig jaar volgens mij heel kort iets over twee orde differentiaalvergelijkingen gehad, maar te weinig om het echt goed te begrijpen.

Je mag het anders wel uitleggen met twee orde differentiaalvergelijkingen. Ik kan dan wel zoeken naar achtergrondinformatie.

Alvast bedankt! ;)

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Door het met differentiaalvergelijkingen te doen hoef ik niet telkens na te denken over de indices en subscripts ed. Het typt wat sneller. Je kunt een recurrente betrekking zien als een 'discrete differentiaalvergelijking', dus daarom gelden ~de volgende stappen ook voor jouw probleem.

We beschouwen de differentiaalvergelijking

ay''+by'+cy = f(t).

We willen de oplossing y=y(t) zoeken met a,b,c constanten. Stel we hebben een oplossing voor bovenstaande vergelijking: yp(t) (zoals ze dat noemen een particuliere oplossing), maar niet de algemene.

m.a.w. ayp(t)''+byp(t)'+cyp(t) = f(t).

Dit aftrekken van de oorspronkelijke vergelijking geeft

a(y-yp(t))''+b(y-yp(t))'+c(y-yp(t)) = 0.

Dan is yhom(t):=y(t)-yp(t) een oplossing van de homogene vergelijking.

Dus de algemene oplossing is: y(t)=yhom(t)+yp(t).

Als je de homogene oplossing hebt, moet je dus nog een particuliere oplossing vinden om je probleem op te lossen.

Hetzelfde verhaal geldt voor recurrente betrekkingen (je kan bovenstaande ook eens proberen voor dergelijke vergelijkingen). Er bestaan algemene methoden om particuliere oplossingen te vinden, maar die kunnen aardig complex zijn. Wat vaak sneller is, is de vorm van de particuliere oplossing te 'gokken', zoals jij deed:
\( a_i = c_i \cdot 2^i \)
(zie ook dat je een typo had, de n hoorde er niet)

Je hoeft dan alleen maar de constanten ci te bepalen. Dit kan je doen door je gok terug in je recurrente betrekking in te vullen.

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Hmm, ik heb nog niet helemaal door hoe het zit maar ik ga morgen even wat informatie zoeken over tweede orde differentiaalvergelijkingen.

Maar als je dus geen gok weet dan is zo'n inhomogene recurrente betrekking ook niet eenvoudig op te lossen?

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Klopt, als je geen gok weet moet je meer moeite doen. Maar dat is bij de opgaven uit je post niet nodig. Je kunt de particuliere oplossingen daar prima gokken.

Wat ik met mijn differentiaalvergelijking wilde laten zien is dat de algemene oplossing gelijk is aan een homogene oplossing + een particuliere oplossing. Ik zal het anders even voor een recurrente betrekking doen voor jouw vorm.

Je bent geinteresseerd in
\(a_i\)
, in recurrente betrekkingen van de vorm:
\(Aa_{i+1}+Ba_i=f[i]\)
,

met f een algemene uitdrukking als functie van i, A en B getallen.

Stel je weet een oplossing
\(a_i^{part}\)
, de zogenaamde particuliere oplossing. Dan,
\(Aa_i^{part}+Ba_i^{part}=f[i]\)
.

Deze kun je van de oorspronkelijke vergelijking aftrekken:
\(A(a_{i+1}-a_{i+1}^{part})+B(a_i-a_i^{part})=0\)


Dan lost
\(a_i^{hom}=a_i-a_i^{part}\)
de homogene vergelijking op.

Kortom:
\(a_i=a_i^{hom}+a_i^{part}\)
.

Dus weet je de homogene en een andere oplossing (de particuliere), dan heb je de algemene oplossing.

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Voor de eerste heb ik inmiddels wel een gok gevonden, alleen zijn alle waarden eentje verschoven.

Ik heb nu
\(\dfrac{n(n+1)}{2} + (n+1)\)
omdat het eerste deel een simpele somrij is en bij het tweede deel tel je de index op, maar alle termen zijn een waarde verschoven en ik zie zo snel niet hoe ik dat kan aanpassen.

De homogene oplossing van de tweede is
\(2^n\)
, maar ik kom niet veel verder met die inhomogene term
\(2^i\)

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Hoe heb je de homogene oplossing gekregen voor je eerste vraag? Ik krijg namelijk a=0 voor alle i uit. Dit is makkelijk in te zien omdat de homogene vergelijk a[i+1]=a is. a[0]=0. Dus alles is nul ;) . Ook voor de tweede vergelijking. Je hebt in beide gevallen dus alleen een particuliere oplossing!

Dus gok bij de eerste eens: a=A*i^2+B*i (A en B getallen). Kun je uitleggen waarom a=C*i niet werkt?

De tweede is moeilijker: je gokte zelf iets van de vorm 2^i (niet 2^n, wat is n bijvoorbeeld?). Deze werkt inderdaad niet. Dan moet je gewoon een orde hoger proberen, zoals: D*i*2^i en bepaal D. Ik weet het, het is een hoop trial en error.

Berichten: 19

Re: Inhomogene recurrente betrekkingen

De homogene oplossing is inderdaad nul, dat had ik even niet goed gezien.

Maar ik snap even niet hoe je aan de gok komt bij de eerste.

Als je 'm invult dan krijg je
\(a_{i+1} = i \cdot (A \cdot i + B + 1)\)
, maar ik zie niet hoe je 'm dan kunt oplossen?

a=C*i werkt niet omdat je de som moet nemen van een aantal termen dus dan heb je al een kwadraat.

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Weer trial en error. Ik probeerde eerst lineair, maar dit werkte niet. Deed ik er een kwadratische term bij, dan werkte het wel.

Je kunt bij het invullen ook a[i+1] invullen.

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Als je a[i+1] invult dan krijg je toch gewoon twee keer hetzelfde
\( i \cdot (A \cdot i + B + 1) = i \cdot (A \cdot i + B + 1) \)
?

Berichten: 244

Re: Inhomogene recurrente betrekkingen

a[i+1]=A(i+1)^2+B(i+1)...

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Oké ;) , dus dan krijg je
\(A = \dfrac{i-B}{2i+1}\)
\(B = i - A \cdot (2 \cdot i +1)\)
Hoe kun je die dan vervolgens oplossen ;) ?

Berichten: 244

Re: Inhomogene recurrente betrekkingen

Ziet er goed uit! Eerste vergelijking in de tweede vullen, B oplossen. En als je B hebt, kun je A bepalen.

Ter controle (want ik moet weg): Je moet vinden A=1/2, B=-1/2. Succes en fijne jaarwisseling :-).

Berichten: 19

Re: Inhomogene recurrente betrekkingen

Bedankt voor je uitleg!

Ik snap alleen niet hoe je nu A en B kunt oplossen, waarschijnlijk doe ik hetzelfde fout als het vorige want ik kom nu steeds op A = A of B = B uit.

Jij ook een fijne jaarwisseling ;)

Reageer