1. Fracție continuă:
Orice număr real x poate fi exprimat ca fracție continuă:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Notat: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (partea întreagă a lui x)
- Dacă x nu este întreg, fie x₁ = 1/(x - a₀), continuați cu a₁ = ⌊x₁⌋
- Repetați procesul pentru a obține a₂, a₃, ...
- Expansiunea în fracție continuă a unui număr rațional este finită
- Expansiunea în fracție continuă a unui număr irațional este infinită
2. Convergente:
Fracția obținută prin luarea primilor n termeni se numește a n-a frație convergentă, notată pn/qn:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Formula de recurență: pn = an·p(n-1) + p(n-2)
- Formula de recurență: qn = an·q(n-1) + q(n-2)
- Convergentele sunt cea mai bună aproximare rațională a numărului original
3. Cea mai bună aproximare rațională:
- Dat un număr real x și limita superioară Q a numitorului, găsiți fracția p/q (q ≤ Q) care minimizează |x - p/q|
- Convergentele fracției continue dau toate cele mai bune aproximări raționale
- Dacă p/q este o convergentă a lui x, atunci pentru orice q' < q, |x - p/q| < |x - p'/q'|
4. Fracții continue ale numerelor speciale:
- Raportul de aur φ:[1; 1, 1, 1, 1, ...] (Toți unu, convergență cea mai lentă)
- √2:[1; 2, 2, 2, 2, ...] (Fracție continuă periodică)
- e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Model regulat)
- π:[3; 7, 15, 1, 292, 1, ...] (Fără model evident)
Complexitatea algoritmului:
- Complexitate temporală:O(n)，unde n este numărul de termeni extinși
- Complexitate spațială:O(n)，Necesită stocarea tuturor coeficienților și convergentelor
- Stabilitate numerică:Utilizarea numerelor în virgulă mobilă de precizie ridicată sau a numerelor întregi mari evită pierderea preciziei
Scenarii de utilizare:
- Calcul numeric:Aproximarea numerelor iraționale complexe cu fracții simple (ex. π ≈ 22/7, 355/113)
- Teoria muzicii:Consonanța intervalelor este legată de simplitatea expansiunilor în fracții continue
- Astronomie:Aproximări raționale pentru calcularea perioadelor orbitale planetare
- Teoria numerelor:Aproximări diofantice, soluții ale ecuației lui Pell
- Grafică pe calculator:Algoritmul liniei Bresenham și altele