forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 23 Σεπ 2017, 22:11

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Προσέγγιση του π με τετραγωνικά συγκλίνοντες αλγόριθμους
ΔημοσίευσηΔημοσιεύτηκε: 11 Μαρ 2017, 10:42 
Χωρίς σύνδεση

Εγγραφη: 24 Φεβ 2016, 13:15
Δημοσ.: 4
Προσέγγιση του π με τετραγωνικά συγκλίνοντες αλγόριθμους

Ξεκινάμε από τη σχέση:

{\mathrm{(}}{1}{\mathrm{)}}\hspace{0.33em}\hspace{0.33em}{\mathrm{\pi}}_{\mathrm{\nu}}\mathrm{{=}}{2}^
{\mathit{\nu}}\mathrm{\sqrt{{2}_{1}{-}\sqrt{{2}_{2}{+}\sqrt{{2}_{3}{+}{...}{+}\sqrt{{2}_{\mathrm{\nu}}}}}}}

όπου {\mathit{\pi}}_{\mathit{\nu}} τείνει στο π καθως ν τείνει στο ∞. Μεταφέροντας τους όρους της (1) στο αριστερό σκέλος, παίρνουμε

{\mathrm{(}}{2}{\mathrm{)}}\hspace{0.33em}\hspace{0.33em}{\mathrm{[}}{\mathit{\pi}}_{\mathit{\nu}}{\mathrm{/}}{2}^{\mathit{\nu}}{\mathrm{)}}^{2}\mathrm{{-}}{2}_{1}{\mathrm{)}}^{2}\mathrm{{-}}{2}_{2
}{\mathrm{)}}^{2}\mathrm{{-}}{\mathrm{...}}{2}_{\mathit{\nu}\mathrm{{-}}{1}}{\mathrm{)}}^{2}\mathrm{{-}}
{2}_{\mathit{\nu}}\mathrm{{=}}{0}

Αν αντικαταστήσουμε τώρα το {\mathit{\pi}}_{\mathit{\nu}} μ' έναν μικρότερο θετικό αριθμό p τότε η (2) θα είναι ίση μ' έναν αριθμό r για τον οποίο θα ισχύει

{p}\mathrm{\leq}{p}\mathrm{{+}}{r}\mathrm{\leq}{\mathrm{\pi}}_{\mathrm{\nu}}

οπότε αποδίδοντας στο p την τιμή p+r και επαναλαμβάνοντας τη διαδικασία θα καταλήξουμε οριακά στην ισότητα p={\mathit{\pi}}_{\mathit{\nu}}.

Το π προσεγγίζεται ταχύτερα άν μετά την εκτέλεση της διεργασίας p=p+r πολλαπλασιάσουμε το ν μ' εναν θετικό ακέραιο >1. Τα παραπάνω υλοποιούνται από τον αλγόριθμο:

ΑΛΓ. π1

1. Εισάγουμε \mathit{\nu}\mathrm{\geq}{2}{\mathrm{,}}\hspace{0.33em}{p}\mathrm{\leq}{\mathit{\pi}}_{\mathit{\nu}}
2. r=p+r
3. Εκτελούμε ν φορές την αναδρομική σχέση {r}\mathrm{{=}}{r}^{2}\mathrm{{-}}{2}
4. p=p+r (το p τείνει στο {\mathit{\pi}}_{\mathit{\nu}})
5. ν=2ν
6. Πήγαινε στο βήμα 2

Αυτός κληρονομεί από την (1) ένα ελάττωμα το οποίο απορρέει απ' τη μορφή του όρου που ακολουθεί το αρνητικό πρόσημο. Συγκεκριμένα, η τιμή του όρου αυτού αρχίζει με 1.999... πριν καταλήξει στα ψηφία που διαμορφώνουν ουσιαστικά την τιμή του {\mathit{\pi}}_{\mathit{\nu}}, περιορίζοντας έτσι τη μέγιστη δυνατή ακρίβεια που μπορεί να επιτευχθεί στα μισά περίπου ψηφία του υπολογιστή.

Το πρόβλημα μπορεί να εξαλειφθεί εντελώς εφόσον ο υπλογιστής είναι τύπου scientific (επιστημονικός). Δεν θα εξηγήσουμε εδώ τις λεπτομέρειες αυτής της διαδικασίας αλλά θα περάσουμε κατευθείαν στη βελτιωμένη εκδοχή του
αλγόριθμου:

ΑΛΓ. π2

1. Εισάγουμε \mathit{\nu}\mathrm{\geq}{2}{\mathrm{,}}\hspace{0.33em}{p}\mathrm{\leq}{\mathit{\pi}}_{\mathit{\nu}}
2. {r}\mathrm{{=}}{\mathrm{(}}{p}{\mathrm{/}}{2}^{\mathit{\nu}}{\mathrm{)}}^{2}
3. εκτελούμε ν–1 φορές την αναδρομική σχέση {r}\mathrm{{=}}{r}^{2}\mathrm{{-}}{2} (δεν πρέπει να την γράψουμε στη μορφή r=r(4–r) καθώς αυτό μπορεί ν' αποβεί σε βάρος της επιδιωκόμενης
ακρίβειας)
4. Αν {r}\mathrm{\geq}{2} πήγαινε στο βήμα 8
5. p=p–r+2
6. ν=2ν
7. Πήγαινε στο βήμα 2
8. Τύπωσε p (p≈π)

Αυτός αξιοποιεί όλα τα ψηφία του υπολογιστή για την προσέγγιση του π. Ο αριθμός των σχετικών ψηφίων
διπλασιάζεται σε κάθε νέο κύκλο διεργασιών ενώ για σταθερή τιμή του ν το r τείνει ταλαντευόμενο προς το 2. Η διαδικασία προσέγγισης διακόπτεται μόλις το r υπερβεί το 2 (λόγω εξάντλησης των ψηφίων).

Σε αυτούς τους αλγόριθμους είναι χρήσιμο να γνωρίζουμε τα φράγματα του π. Προς αυτό δίνονται οι σχέσεις

\begin{array}{l}
{{\mathit{\Pi}}_{\mathit{\nu}}\mathrm{{=}}{\mathit{\pi}}_{\mathrm{\nu}}^{2}{\mathrm{/}}{\mathit{\pi}}_{\mathit{\nu}\mathrm{{-}}{1}}}\\
{{\mathit{\pi}}_{\mathit{\nu}}\mathrm{\leq}\mathit{\pi}\mathrm{\leq}{\mathit{\Pi}}_{\mathit{\nu}}}\\
{{\mathrm{(}}{2}{\mathit{\pi}}_{\mathit{\nu}}\mathrm{{+}}{\mathit{\Pi}}_{\mathit{\nu}}{\mathrm{)/}}{3}\mathrm{\approx}\mathit{\pi}}\end{array}

Οι παραπάνω αλγόριθμοι είναι κατάλληλοι για υπολογιστές με απεριόριστο αριθμό ψηφίων για τον υπολογισμό χιλιάδων ή εκατομμυρίων ψηφίων του π, περιπτώσεις για τις οποίες έχει νόημα ν' απαλλαγούμε από τα ριζικά καθώς έτσι γλυτώνουμε πολύτιμο υπολογιστικό χρόνο. Διαφορετικά, μπορούμε να προσεγγίσουμε το π εύκολα, γρήγορα και με την μέγιστη δυνατή ακρίβεια ενός συμβατικού υπολογιστή με τον παρακάτω απλούστερο αλγόριθμο:

ΑΛΓ. π3

1. Θέτουμε ν=r=0, m=1
2. {r}\mathrm{{=}}\sqrt{{2}\mathrm{{+}}{r}}
3. m=rm
4. ν=ν+1
5. Τύπωσε {\mathit{\pi}}_{\mathit{\nu}}\mathrm{{=}}{2}^{\mathit{\nu}\mathrm{{+}}{1}}{\mathrm{/}}{m}
6. Πήγαινε στο βήμα 2

Παρατηρήστε ότι στη βάση 2 του αριθμητικού συστήματος ο πρώτος όρος του γινομένου στην (1) μετακινεί απλώς την
υποδιαστολή της τιμής που δίνει ο ριζικός όρος αφήνοντας αμετάβλητη την δυαδική παράσταση του π. Υπάρχει μια θεμελιώδης σχέση μεταξύ της τριγωνομετρίας και των δυαδικών αριθμών η οποία προκύπτει από μια ενδιαφέρουσα
γενίκευση της (1). Περισσότερα πάνω σ' αυτό το θέμα θα βρείτε στο "Πολλά & Διάφορα" αυτού του forum με τίτλο "Δυαδική οδός στην τριγωνομετρία".


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group