DifiTsi.com

Rezolvați ecuațiile de recurență

În încercarea de a găsi o formulă pentru anumite secvențe matematice, un pas intermediar comun este de a determina termenul n nu ca o funcție de n, ci ca o funcție a termenilor de ordine anteriori. De exemplu, ar fi frumos să aibă o formulă în formă închisă pentru termenul nth secvenței Fibonacci, dar uneori ai una ecuație doar recurență și anume că fiecare termen al secvenței Fibonacci este suma celor doi termeni precedente. În acest articol, sunt prezentate diferite metode de derivare a unei formule în formă închisă dintr-o ecuație de recurență.

metodă

Metoda 1
Consecințe aritmetice

Imaginea intitulată Rezolvați relațiile de recurență Pasul 1
1
Să avem o secvență aritmetică ca 5, 8, 11, 14, 17, 20, .... ia în considerare.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 2
    2
    Deoarece fiecare termen este mai mare decât cel precedent cu 3, poate fi scris ca o recurență după cum urmează.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 3
    3
    Fiecare ecuație de recurență a formei an = an-1 + d este o secvență aritmetică.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 4
    4
    Scrieți forma închisă a formulei pentru o secvență aritmetică, eventual cu necunoscute, după cum se arată.
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 5
    5
    Determinați necunoscuții cu ajutorul valorilor inițiale. În acest caz, deoarece 5 este al optulea termen, formula este an = 5 + 3n. Dacă în schimb am avut 5 ca primul termen, atunci formula noastră ar fi an = 2 + 3n.

    • Metoda 2
    Consecințe geometrice

    Imaginea intitulată Rezolvați relațiile de recurență Pasul 6
    1
    Să avem o secvență aritmetică cum ar fi 3, 6, 12, 24, 48, .... ia în considerare.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 7
    2
    Deoarece fiecare termen este de două ori cel precedent, acesta poate fi scris ca o recurență după cum urmează.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 8
    3
    Fiecare ecuație de recurență a formei an = r * an-1 este o secvență geometrică.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 9
    4
    Scrieți forma închisă a formulei pentru o secvență geometrică, eventual cu necunoscute, după cum se arată.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 10
    5
    Determinați necunoscuții cu ajutorul valorilor inițiale. În acest caz, deoarece 3 este al optulea termen, formula este an = 3 * 2n. Dacă, în schimb, am avut 3 ca prim termen, atunci formula noastră ar fi an = 3 * 2(N-1).

    • Metoda 3
    Consecințe polinomiale

    Imaginea intitulată Rezolvați relațiile de recurență Pasul 11
    1
    Să urmăm episodul 5, 0, -8, -17, -25, -30, ..., dat de recursiunea an = an-1 + n2 - Uită-te la 6n.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 12
    2
    Fiecare recursiune având forma prezentată, unde p (n) este un polinom în n, are o formulă polinomială închisă cu un grad mai mare decât gradul p.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 13
    3
    Scrieți forma generală a unui polinom de gradul dorit. În acest exemplu, p este patrat, deci avem nevoie de un polinom cubic pentru a obține termenii secvenței secvenței an afișare.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 14
    4
    Deoarece un polinom cubic general are patru coeficienți necunoscuți, avem nevoie de patru valori pentru a rezolva sistemul de ecuații rezultat. Nu contează care patru, deci să luăm termenii 0, 1, 2 și 3. Dacă conducem recursiunea înapoi pentru a determina termenul -1, probabil că unele calcule vor fi mai ușor, dar nu este necesar.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 15
    5


    Fie rezolvați sistemul de ecuații rezultat cu ecuațiile deg (p) + 2 și deg (p) = 2 necunoscute sau potriviți un polinom Lagrangian cu punctele cunoscute la deg (p) +2.
    • Dacă termenul 0 este unul dintre termenii pe care i-am luat pentru a determina coeficienții, atunci avem termenul constant al polinomului și putem readuce imediat sistemul la ecuațiile deg (p) +1 cu deg (p) + Reduceți 1 necunoscut după cum se arată.
      Imaginea intitulată Rezolvați relațiile de recurență Pasul 16
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 16
    6
    Scrieți formula închisă pentru an ca polinom cu coeficienți cunoscuți.

    • Metoda 4
    Cu algebră liniară

    Imaginea intitulată Rezolvați relațiile de recurență Pasul 17
    1
    Aceasta este prima metodă care poate rezolva secvența Fibonacci în introducere, dar metoda rezolvă fiecare ecuație de recurență în care termenul n este o combinație liniară a termenilor k anteriori. Să încercăm exemplul arătat, al cărui prim termen este 1, 4, 13, 46, 157, ....
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 18
    2
    Notați polinomul caracteristic al recurenței. Am obținut-o dându-i pe fiecare an în re-concurs de xn înlocui și cu x(N-k) unde obținem un polinom de grad k, cu un termen constant constant.
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 19
    3
    Rezolvați polinomul caracteristic. În acest caz, polinomul caracteristic are gradul 2 și putem folosi formula patratică pentru a determina zerourile.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 20
    4
    Fiecare expresie care are forma prezentată rezolvă ecuația de recurență. Ceu sunt constante, iar bazele termenilor exponențiali sunt soluțiile polinomului caracteristic de mai sus. Acest lucru se poate dovedi prin inducție.
    • Dacă polinomul caracteristic are un număr multiplu de zero, această etapă poate fi ușor modificată. Dacă r este zero față de multiplicitatea m, luați (c1rn + c2nrn + c3n2rn + ... + cmnm-1rn) în loc de (c1rn). De exemplu, secvența care începe cu 5, 0, -4, 16, 144, 640, 2240, ... satisface ecuația de recurență an = 6an-1 - 12aN-2 + 8an-3. Polinomul caracteristic are un triple zero la 2 și formula în formă închisă este an = 5 * 2n - 7 * n * 2n + 2 * n2* 2n.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 21
    5
    Determinați ceu, care satisfac condițiile inițiale date. La fel ca în exemplul polinomial, o facem prin stabilirea unui sistem liniar de ecuații cu termenii de început. Deoarece acest exemplu are două necunoscute, avem nevoie de doi termeni. Nu contează care dintre noi luăm, așa că luăm a cincea și prima, pentru a evita să faci o putere mare de un număr irațional.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 22
    6
    Rezolvați sistemul de ecuații rezultat.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 23
    7
    Puneți constantele rezultate în formula generală pentru a obține soluția.

    • Metoda 5
    Funcțiile generatoare

    Imaginea intitulată Rezolvați relațiile de recurență Pasul 24
    1
    Să urmăm episodul 2, 5, 14, 41, 122, ... , Luați în considerare recursiunea de mai sus. Această sarcină nu poate fi rezolvată prin metodele de mai sus, dar putem găsi o formulă care utilizează funcții de generare.
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 25
    2
    Notați funcția de generare a secvenței. O funcție de generare este pur și simplu o serie formală de putere în care coeficientul xn al n-lea termen al secvenței.
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 26
    3
    Conversia funcției de generare așa cum este prezentat. Scopul acestei etape este de a găsi o ecuație care ne permite să calculam funcția generatoare A (x). Eliminați termenul de început. Aplicați ecuația de recurență la termenii rămași. Împărțiți suma. Eliminați termenii constanți. Utilizați definiția lui A (x). Utilizați formula pentru suma unei serii geometrice.
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 27
    4
    Determinați funcția de generare A (x).
  • Imaginea intitulată Rezolvarea relațiilor de recurență Pasul 28
    5
    Determinați coeficienții termenilor xn în A (x). Metodele de a face acest lucru depind de forma exactă a lui A (x), dar metoda descompunerii parțiale parțiale, combinată cu cunoașterea funcției de generare a unei secvențe geometrice, funcționează aici așa cum se arată.
  • Imaginea intitulată Rezolvați relațiile de recurență Pasul 29
    6
    Scrieți formula pentru an prin luarea coeficientului de xn în A (x).

    • Sfaturi

    • Inducția este, de asemenea, o tehnică populară. Este adesea ușor să se demonstreze prin inducție că o anumită formulă satisface o anumită recurență, dar problema este că trebuie să ghicim formula în prealabil.
    • Unele dintre aceste metode sunt computațional intensive, cu multe moduri de a face o greșeală proastă. Este bine să verificați formula cu câteva valori cunoscute.
    • "În matematică, numerele Fibonacci sau secvența Fibonacci sunt numerele din următoarele serii întregi: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
      • Spirala lui Fibonacci: o aproximare a raportului de aur, care este format prin arce de cerc care colțurile opuse Sună de pătrate cu dale Fibonacci aici sunt pătratele dimensiunile de 1, 1, 2, 3, 5, 8, 13, 21 și 34 utilizate.
      • Prin definiție, primele două numere din secvența Fibonacci sunt fie 1, fie 1 sau 0 și 1, în funcție de punctul de pornire ales al secvenței, iar fiecare număr consecutiv este suma celor două precedente.
      • Exprimată matematic, secvența Fn din numerele Fibonacci definite de următoarea recursiune
      • Fn= Fn-1 + FN-2 cu valori inițiale F1 = 1, F2 = 1 sau F0 = 0, F1 = 1.
      • Raportul Fn/ Fn-1 se numește "intersecție de aur" sau Phi (Φ), și același lucru se aplică și Fn-1/ Fn.1
    Distribuiți pe rețelele sociale:

    înrudit