Fotools
EN

Rationella approximationer / kedjebråksutvecklingar

Ange ett giltigt decimaltal

Snabbexempel:

)

Fel:

Algoritmbekrivning:

Antal expanderade termer
Termer
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Antal kedjebråk
  • Antal
  • Beräkningstid
  • Expansionstyp
  • Ändlig
  • Avkortad
    • Beräkning klar!
    Ange ett tal och klicka på "Starta beräkning"
    n/qnDölj
    • p-1 = 1, q-1 = 0
    • p0 = a₀, q0 = 1
    • Rekursionsformel: pn = an·pn-1 + pn-2
    • Rekursionsformel: qn = an·qn-1 + qn-2
    • Kedjebråk ger den bästa rationella approximationen av originaltalet
    3. Bästa rationella approximationer:
    • Givet ett reellt tal x och en övre gräns Q för nämnaren, hitta ett bråk p/q (q ≤ Q) som minimerar |x - p/q|
    • Konvergenterna i ett kedjebråk ger alla de bästa rationella approximationerna
    • Om p/q är en konvergent av x, då gäller för alla q' < q att |x - p/q| < |x - p'/q'|
    4. Kedjebråk för speciella tal:
    • Det 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, ...] (mönster)
    • π:[3; 7, 15, 1, 292, 1, ...] (inget tydligt mönster)

    Algoritmkomplexitet:

    • Tidskomplexitet:O(n), där n är antalet expanderade termer
    • Rymdkomplexitet:O(n), kräver lagring av alla koefficienter och konvergenter
    • Numerisk stabilitet:Användning av högprecisions flyttal eller stora heltal undviker precisionsförlust

    Användningsområden:

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