Μερικά πολύ βασικά για τούς πραγματικούς

[lucinos]

Μού έκανε μεγάλη εντύπωση που κάποιος με απίστευτο «θράσος» χρησιμοποίησε συνθήκη ισότητας σε πραγματικούς. Επειδή αυτά τα πράγματα είναι πολύ στοιχειώδη και κάπως δεν μπορώ να αποδεχτώ ότι κάποιος μπορεί να κάνει ένα τέτοιο λάθος, να έχετε πάντα στον νου σας ότι οι πραγματικοί από την φύση τους είναι προσεγγιστικοί.

Για να το δείτε με τα μάτια σας (το συγκεκριμένο παράδειγμα το έχω από πολλά χρόνια και είναι ανεξάρτητο από την python)

Κώδικας: Επιλογή όλων

>>> 0.2 == 0.2
True
>>> 1.2 - 1.0 == 0.2
False
>>> 1.2 - 1.0
0.19999999999999996
>>> print 1.2 - 1.0
0.2
>>> print 1.0/3.0
0.333333333333
>>> (1.0 / 3.0) * 3.0
1.0
>>>


Παρατηρήσεις:
Το σφάλμα είναι απρόβλεπτο. Μην κάνετε υποθέσεις για το πότε θα εμφανιστεί και πώς, δεν αξίζει τον κόπο απλά αρκεστείτε ότι οι αριθμοί είναι προσεγγιστικοί.
Το σφάλμα δεν εξαρτάται από την Python. Η Python χρησιμοποιεί απλά την C. Επομένως η ευθύνη πέφτει στην C.
Το σφάλμα δεν οφείλεται σε κακό προγραμματισμό. Η φύση τού προβλήματος το δημιουργεί. Δεν θα μπορούσαμε να απαλλαγούμε.

Για να πάρετε πάντως μια ιδέα γιατί εμφανίζεται στο 1.2 - 1.0, σκεφτείτε πώς αναπαριστά τούς αριθμούς ο υπολογιστής. όταν κάνει την αφαίρεση 1.2 - 1.0 = 0.2 το αποτέλεσμα πρέπει να το εκφράσει σαν πραγματικό, δηλαδή σε μια μορφή κοντύτερα στην 2.0 * 10^(-1). Πάνω σε αυτήν την πράξη μάς λείπουν κάποια ψηφία. Λάβετε υπόψιν σας ότι 0.2 = 1/5. Το 5 όμως δεν είναι δύναμη τού 2 ούτε υποπολλαπλάσιό του, ούτε γινόμενο υποπολλαπλάσιών του. Η διαίρεση στο δυαδικό σύστημα δημιουργεί μια ατελείωτη σειρά ψηφίων όπως στο δεκαδικό έχουμε με τις διαιρέσεις 1/3, 1/7 κλπ.

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

Ερώτηση κρίσεως: τι είναι ταχύτερο για τον υπολογιστή, η πρόσθεση ή ο πολλαπλασιασμός πραγματικών;

Κάτι ακόμα για το σφάλμα. Ο τρόπος που συσσωρεύεται είναι χαοτικός, και θυμηθείτε ότι βασικό χαρακτηριστικό τού χάους είναι η εκθετική συνάρτηση. Εκθετική ανάπτυξη σημαίνει ότι θα κάνει κάμποση ώρα ίσως να γίνει αισθητό, αλλά από την στιγμή που θα συμβεί αυτό πολύ γρήγορα χάνεται ο έλεγχος.

Παράδειγμα: Ελκυστής τού Λόρεντζ.


Η φύση τού υπολογισμού αυτού τού χαοτικού σχήματος είναι... χαοτική. Αυτό σημαίνει ότι πέρα από έναν ορίζοντα προβλεψιμότητας, δεν υπάρχει καμμία ακρίβεια στον υπολογισμό τών σημείων. Επειδή όμως είναι ελκυστής, έστω και παράξενος, το σχήμα για το «ανθρώπινο μάτι» είναι σωστό!

[maenolis]

Μπορείς να εξηγήσεις λίγο περισσότερα για το σχήμα;

[lucinos]

Είναι ο ελκυστής τού Λόρεντζ. Τον ανέφερα μόνο ως παράδειγμα αριθμητικού υπολογισμού που το σφάλμα συσσωρεύεται και κάνει αδύνατο τον ακριβή υπολογισμό και δεν σκοπεύω να εξηγήσω περισσότερο εδώ. Δείτε για παράδειγμα στην βικιπαίδεια:
http://en.wikipedia.org/wiki/Lorenz_attractor
http://en.wikipedia.org/wiki/Attractor

[Dimitris]

@lucinos συγγνώμη αλλα τα μπέρδεψες λιγάκι τα πράγματα. Καμία σχέση ο ελκυστής του Lorenz με τους floating point αριθμούς. Δηλαδή έχει σχέση αλλα δεν μπορεί να αποτελέσει παράδειγμα για τα σφάλματα των floating points. Το ζήτημα είναι πιο μεγάλο από ότι το περιγράφεις. Καταρχήν, μιλάμε για floating point αριθμούς και όχι για πραγματικούς. Στους υπολογιστές δεν υπάρχουν πραγματικοί αριθμοί, γιατί απλά δε μπορεί να υπάρξουν εκτός ένος συστήματος συμβολικών μαθηματικών. Το "π" είναι πραγματικός αριμός, το "ρίζα 2" είναι πραγματικός αριθμόυς, το "2/3" είναι πραγματικός αριθμός. Οι floating points δε μπορούν να περιγράψουν ούτε καν τους ρητούς αριθμούς (μπορεί παρόλ'αυτά να υλοποιηθει με απόλυτη ακρίβεια ένα σύστημα ρητών αριθμών). Οι floating points δεν είναι ισοκατανεμημένοι όπως οι ακέραιοι.

Ο ελκυστής του Lorenz θα είχε την ίδια συμπεριφορά ακόμη κι αν δεν υπήρχε το θέμα των floating points. (Ωραίο τα βιβλία εκλαϊκευμένης επιστήμης αλλά ούτε τη μισή αλήθεια δε λένε). Απλώς με τους floating points επιτείνεται η συμπεριφορά αυτή. Ο ελκυστής του Lorenz δηλώνει την εξάρτηση από τις αρχικές συνθήκες. Δηλαδή ακόμη κι αν είχαμε τέλειες όλες τις πράξεις, λόγω της μη γραμμικότητας του συστήματος, η άγνοια στις αρχικές συνθήκες, λόγω μετρητικού, αριθμητικού ή όποιου άλλου σφάλματος, θα οδηγούσε σε απόκλιση δύο αρχικά γειτονικών λύσεων. Οι όροι απόκλιση και γειτονικές λύσεις ορίζονται με μαθηματικούς ορισμούς.

Ο τρόπος που συσσωρεύεται ένα σφάλμα είναι χαοτικός γιατί το σύστημα που διάλεξες είναι χαοτικό. Εχεις μπλέξει τα ήδη σφαλμάτων. To ζήτημα των floating points αναφέρεται στο round off error, ενώ στην αριθμητική ανάλυση υπάρχει επίσης το truncation error και το discretization error. Σε γραμμικά συστήματα ο τρόπος που συσσωρεύεται το σφάλμα είναι απόλυτα γνωστός. Αν δεν ήταν τότε καμία μαθηματική μέθοδος υλοποιήσιμη σε υπολογιστή δε θα ήταν αξιόπιστη (βλ. επίσης σύμβολο Landau).

Θα σου πρότεινα να μείνεις στους floating-point αριθμούς και να μην επεκταθείς σε παραδείγματα που μόνο μεγαλύτερη σύγχυση μπορούν να δημιουργήσουν.

Αν θες να μάθεις περισσότερα για το χάος δες αυτά τα βιβλία:
* http://www.amazon.com/Die-Erforschung-Chaos-Einführung-nichtlinearer/dp/354071071X/ref=sr_1_2?ie=UTF8&qid=1323678058&sr=8-2
* http://www.amazon.com/Introduction-Appl ... 134&sr=1-4
* http://www.amazon.com/Nonlinear-Oscilla ... pd_sim_b_1
* http://www.amazon.com/Differential-Equa ... pd_sim_b_4

[medigeek]

Πολύ ενδιαφέρον το θέμα!
Νομίζω λέει το ίδιο κι εδώ: http://docs.python.org/tutorial/floatingpoint.html
Αναφέρει πως υπάρχει λύση αν χρησιμοποιήσεις το decimal module με αριθμούς ως text strings:
http://docs.python.org/library/decimal.html

>>> from decimal import Decimal
>>> Decimal(1.0) - Decimal(1.2)
Decimal('-0.1999999999999999555910790150')
>>> Decimal('1.0') - Decimal('1.2')
Decimal('-0.2')

[lucinos]

@Dimitris

δεν ξέρω αν το πρόσεξες αλλά στην πρώτη ανάρτηση είχα γράψει

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

συνεπώς μάλλον ξέρω πολύ καλά την διαφορά τού πραγματικού π από τον «πραγματικό» 1.0
αριθμός κινητής υποδιαστολής στην δικιά μου γλώσσα === float
απλά μού αρέσει να μην ακριβολογώ αν δεν υπάρχει λόγος και να χρησιμοποιώ λέξεις με «ευρύτερη» έννοια.
Επίσης είμαι και οπαδός τού Χάμπτυ-Ντάμπτυ.

Ακόμα και με την μαθηματική έννοια οι πραγματικοί έχουν έννοια προσέγγισης, απλά η προσέγγιση αυτή είναι ιδανική. Δηλαδή οι πραγματικοί ορίζονται σαν όρια ακολουθιών. Δηλαδή έχεις την ακολουθία:
α0=3
α1=3.1
α2=3.14
α3=3.141
α5=3.1415
α6=3.14159
...
και λες για παράδειγμα ότι για κάθε ε υπάρχει Μ ώστε για κάθε Ν > Μ, |αΝ - αΜ| < ε
και λες δεν μπορεί κάπου πάει αυτή η ακολουθία, αλλά αυτός δεν είναι πάντα ρητός (λύση πρωτοβάθμιας εξίσωσης). Κάποιοι όπως η λύση τής χ*χ = 2 είναι ρίζες πολυωνυμικών εξισώσεων και τούς λες αλγεβρικούς, κάποιοι όπως ο π και ο e δεν είναι και τούς λέμε υπερβατικούς. Φυσικά αυτά τα ξέρεις και εσύ πολύ καλά αλλά απλά τα λέω για να θυμηθούμε ότι αν το σκεφτούμε καλά οι πραγματικοί ακόμα και σε έναν ιδεατό κόσμο κάπου είναι μια ιδεατή προσέγγιση και απλά προσωπικά μού αρέσει η ιδέα να αντιμετωπίζω τούς αριθμούς κινητής υποδιαστολής σαν πετσοκομμένους πραγματικούς. Έτσι και αλλιώς κάθε τι είναι αυτό που θέλουμε να είναι.

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

Έχεις δίκιο ότι στον υπολογισμό (ειδικά ενός παράξενου ελκυστή) υπεισέρχονται πολύ μεγαλύτερα σφάλματα από το round off error. Ας το δούμε όμως ως εξής: το round off error είναι το ελάχιστο δυνατό σφάλμα το οποίο δεν μπορείς να ελπίζεις ότι θα αποφύγεις και σε βεβαιώνω ότι είναι χαοτικό και δεν έχει σημασία ότι το παράδειγμα είναι παράξενο. Ίσως απλά ήθελα να γίνω πιο δραματικός. Γράφεις ότι σε γραμμικά συστήματα, ο τρόπος που συσσωρεύεται το σφάλμα, είναι απόλυτα γνωστός. Κάνεις λάθος! Γραμμικότητα με round off error απλά δεν υφίσταται. Αλλά συνήθως αυτό απλά δεν μάς νοιάζει (για διαφόρους λόγους, είτε επειδή μπορούμε απλά να το παρακάμψουμε χρησιμοποιώντας την αναλυτική λύση, είτε επειδή θα μάς έχουν καταβροχθίσει πολύ μεγαλύτερα σφάλματα κλπ.

@medigeek
όχι δεν είναι λύση αυτό, τουλάχιστον όχι στο γενικότερο πρόβλημα που αναφέρομαι. Συνήθως όταν θες μια «φυσιολογικότερη» συμπεριφορά, ξέρεις την ακρίβεια που επιβάλλεται. Ανάλογα με την περίπτωση το θεωρώ λογικότερο, είτε απλά να στρογγυλοποιείς τα περίσσια ψηφία, είτε να χρησιμοποιείς ακεραίους (και να τούς προσαρμόζεις στην σωστή κλίμακα). Στις πολύ ιδιαίτερες περιπτώσεις που πραγματικά έχεις ανάγκη για κάτι ιδιαίτερο, τότε δεν βλέπω άλλη «σωστή» λύση από το να ορίσεις ρητούς και πραγματικούς με τον τρόπο που το κάνει το Mathematica. Όταν όμως θέλεις αριθμητική επίλυση θέλεις αριθμό κινητής υποδιαστολής και η φύση τού προβλήματος έτσι και αλλιώς σού επιβάλλει πολύ πιο σοβαρά σφάλματα.

Ας δούμε ένα παράδειγμα:

Κώδικας: Επιλογή όλων

>>> (Decimal('1')/Decimal('3'))*Decimal('3')
Decimal('0.9999999999999999999999999999')
>>>


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

[Dimitris]

Off topic:
Μη παίρνεις τα σχόλιά μου ως επίθεση εναντίον σου. Εκτιμώ την προσπάθειά σου να εξηγήσεις ένα δύσκολο πρόβλημα. Απλά μπορεί σε κάποιον μη ειδικό να δημιουργηθούν λανθασμένες εντυπώσεις. Συνέχισε την πολύ καλή δουλειά! (αλλά άφησε τα χαοτικά συστήματα από έξω για το συγκεκριμένο παράδειγμα)
Σχετικά με τον ορίζοντα υπολογισιμότητας της εξίσωσης Lorenz για δεδομένη ακρίβεια μηχανής μπορείτε να διαβάσετε εδω:

Κώδικας: Επιλογή όλων

http://home.simula.no/~logg/pub/papers/KehletLogg2010a.pdf

Για τους υπολογισμούς έχει χρησιμοποιηθεί το dolfin, προγραμμα ΕΛΛΑΚ.

[lucinos]

Και όμως την ακολουθία Κωσύ (την έγραψα από μνήμης) την έγραψα λάθος!!! Ξεχνάω αγρίως. Τώρα κοίταγα ότι ορίζεται σαν για κάθε ε υπάρχει Κ ώστε για κάθε Ν και Μ μεγαλύτερα τού Κ να ισχύει.
λολ

Ο σύνδεσμός σου μού λέει ότι είναι απαγορευμένος.

Δεν καταλαβαίνω γιατί να αφήσει κάποιος το χάος από έξω όταν προκύπτει εντελώς φυσικά, ακόμα και χωρίς να το θέλουμε.

Ο μη ειδικός αυτό που πρέπει να κρατήσει είναι όταν έχει προσέγγιση να μην απαιτεί ισότητα.

[the_eye]

Αν θέλετε στο forum μπορείτε να γράψετε και μαθηματικούς τύπους με latex bbcode
Φτιάχνετε το latex code εδώ http://www.codecogs.com/latex/eqneditor.php
και μετά τον βάζετε σε bbcode που είναι χαμηλά στην λίστα στα Άλλα bbcode
πχ

Κώδικας: Επιλογή όλων

[z_tex]2e^{i\frac{4\pi }{3}}[/z_tex]

Αποτέλεσμα

[kalakouentin]

Ωραίο άρθρο lucinos!


Xωρίς να θέλω να πάρω κάτι από το τελικό μήνυμα του άρθρο σου, ο Dimitris είναι σωστός. Το παράδειγμα σου με τον Lorentz attractor είναι λίγο απρεπές. Συγχέεται, μερικώς τουλάχιστον, το γεγονός ότι ένα σύστημα μπορεί να έχει εγγενώς μη-γραμμική συμπεριφορά (λχ. Lorentz attractor), με το γεγονός ότι ένα σύστημα κατά την προγραμματιστική του υλοποίηση απλά "σωρεύει αριθμητικά σφάλματα" που τελικά οδηγούν σε ακανόνιστη συμπεριφορά.
Το γεγονός ότι "το χάος.. .. προκύπτει εντελώς φυσικά, ακόμα και χωρίς να το θέλουμε." (το οποίο δεν το δέχομαι και τόσο αψήφιστα αλλά ας το δεχτούμε για τη συζήτηση), δε σημαίνει ότι όταν κάποιο σύστημα παρουσιάζει ακανόνιστη συμπεριφορά (erratic behaviour) είναι συνήθως λόγω χαοτικής δυναμικής του συστήματος. Ειδικά στο θέμα με floating point precision είναι πολύ περισσότερο θέμα αδυναμίας του χρήστη να αναγνωρίσει τους περιορισμούς της υλοποίησης του.

Πολύ γνωστή γενική εισαγωγή για το χάος είναι το βιβλίο του Strogartz, Nonlinear Dynamics And Chaos, εύπεπτο για κάποιον που έχει κάνει μέχρι ένα μάθημα σε συνήθεις διαφορικές. Δεν έχω δει από κοντά αυτά που προτείνει ο Dimitris αλλά μου φαίνονται πιο τεχνικά. (Και του Strogatz δεν είναι βιβλίο για πέταμα, απλά είναι λίγο sloppy και αμερικανιά.) (Το Introduction to Applied Nonlinear Dynamical Systems and Chaos που βλέπω τώρα είναι "διαφορετικό" βιβλίο, πάει σε πολύ μεγαλύτερο βάθος· αν θες να μάθεις τα βασικά για ένα Hopf bifurcation δε χρειάζεται να χάσεις τα νιάτα σου μέχρι να φτάσεις στη σελίδα 380 . Το Differential Equations, Dynamical Systems, and an Introduction to Chaos δείχνει πιο accessible σίγουρα.. )