Fotools
nl

Rationele benadering / Kettingbreukexpansie

Voer een reëel getal in

Snelle voorbeelden:

Berekeningsresultaat

Voer een getal in en klik op Start berekening

Algoritme beschrijving:

1. Kettingbreuk:
Elk reëel getal x kan worden uitgedrukt als een kettingbreuk:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Afgekort als: x = [a₀; a₁, a₂, a₃, ...]
  • a₀ = ⌊x⌋ (het gehele deel van x)
  • Als x geen geheel getal is, stel x₁ = 1/(x - a₀), ga door met a₁ = ⌊x₁⌋
  • Herhaal dit proces om a₂, a₃, ... te krijgen
  • De kettingbreukexpansie van een rationaal getal is eindig
  • De kettingbreukexpansie van een irrationaal getal is oneindig
2. Convergenten:
De breuk verkregen door de eerste n termen te nemen heet de n-de convergent, genoteerd als pn/qn:
  • p-1 = 1, q-1 = 0
  • p0 = a₀, q0 = 1
  • Recursieformule: pn = an·p(n-1) + p(n-2)
  • Recursieformule: qn = an·q(n-1) + q(n-2)
  • Convergenten zijn de beste rationele benaderingen van het oorspronkelijke getal
3. Beste rationele benadering:
  • Gegeven een reëel getal x en een bovengrens Q voor de noemer, zoek de breuk p/q (q ≤ Q) die |x - p/q| minimaliseert
  • Convergenten van kettingbreuken geven alle beste rationele benaderingen
  • Als p/q een convergent is van x, dan geldt voor alle q' < q: |x - p/q| < |x - p'/q'|
4. Kettingbreuken van bijzondere getallen:
  • Gulden snede φ:[1; 1, 1, 1, 1, ...] (Allemaal enen, langzaamste convergentie)
  • √2:[1; 2, 2, 2, 2, ...] (Periodieke kettingbreuk)
  • e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regelmatig patroon)
  • π:[3; 7, 15, 1, 292, 1, ...] (Geen duidelijk patroon)

Algoritmecomplexiteit:

  • Tijdcomplexiteit:O(n)，waarbij n het aantal te expanderen termen is
  • Ruimtecomplexiteit:O(n)，Alle coëfficiënten en convergenten moeten worden opgeslagen
  • Numerieke stabiliteit:Gebruik van hoge-precisie drijvende-kommagetallen of grote gehele getallen voorkomt precisieverlies

Toepassingsscenario's:

  • Numerieke berekening:Gebruik eenvoudige breuken om complexe irrationale getallen te benaderen (bijv. π ≈ 22/7, 355/113)
  • Muziektheorie:Intervalconsonantie is gerelateerd aan de eenvoud van kettingbreukexpansies
  • Astronomie:Rationele benaderingen voor het berekenen van planetaire omlooptijden
  • Getaltheorie:Diofantische benaderingen, oplossingen van de vergelijking van Pell
  • Computergraphics:Bresenham's lijnalgoritme en meer