Fotools
sv

Rationell approximation / Kedjebråksutveckling

Ange ett reellt tal

Snabbexempel:

Beräkningsresultat

Ange ett tal och klicka på Starta beräkning

Algoritmförklaring:

1. Kedjebråk:
Varje reellt tal x kan uttryckas som ett kedjebråk:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Förkortat: x = [a₀; a₁, a₂, a₃, ...]
  • a₀ = ⌊x⌋ (heltalsdelen av x)
  • Om x inte är ett heltal, låt x₁ = 1/(x - a₀), fortsätt med a₁ = ⌊x₁⌋
  • Upprepa processen för att få a₂, a₃, ...
  • Kedjebråksutvecklingen av ett rationellt tal är ändlig
  • Kedjebråksutvecklingen av ett irrationellt tal är oändlig
2. Konvergenter:
Bråket från de första n termerna kallas den n-te konvergenten, betecknad pn/qn:
  • p-1 = 1, q-1 = 0
  • p0 = a₀, q0 = 1
  • Rekursionsformel: pn = an·p(n-1) + p(n-2)
  • Rekursionsformel: qn = an·q(n-1) + q(n-2)
  • Konvergenter är de bästa rationella approximationerna av ursprungstalet
3. Bästa rationella approximation:
  • För ett givet reellt tal x och övre gräns Q för nämnaren, hitta bråket p/q (q ≤ Q) som minimerar |x - p/q|
  • Konvergenter av kedjebråk ger alla bästa rationella approximationer
  • Om p/q är en konvergent av x gäller för alla q' < q: |x - p/q| < |x - p'/q'|
4. Kedjebråk av speciella tal:
  • Gyllene snittet φ:[1; 1, 1, 1, 1, ...] (Alla ettor, långsammast konvergens)
  • √2:[1; 2, 2, 2, 2, ...] (Periodiskt kedjebråk)
  • e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regelbundet mönster)
  • π:[3; 7, 15, 1, 292, 1, ...] (Inget uppenbart mönster)

Algoritmkomplexitet:

  • Tidskomplexitet:O(n)，där n är antalet termer att utveckla
  • Rymkomplexitet:O(n)，Alla koefficienter och konvergenter behöver lagras
  • Numerisk stabilitet:Användning av flytpunktstal med hög precision eller stora heltal förhindrar precisionförlust

Tillämpningsscenarier:

  • Numerisk beräkning:Approximera komplexa irrationella tal med enkla bråk (t.ex. π ≈ 22/7, 355/113)
  • Musikteori:Intervalkonsonans är relaterad till enkelheten hos kedjebråksutvecklingar
  • Astronomi:Rationella approximationer för beräkning av planetariska omloppstider
  • Talteori:Diofantiska approximationer, lösningar till Pells ekvation
  • Datorgrafik:Bresenhams linjealgoritm med mera