Θεώρημα του Μπουντάν

Στα μαθηματικά, το θεώρημα του Μπουντάν, το οποίο πήρε το όνομά του από τον François Budan de Boislaurent, είναι ένα από τα πρώιμα θεωρήματα που σχετίζονται με τον υπολογισμό ενός άνω ορίου στον αριθμό των πραγματικών ριζών που έχει ένα πολυώνυμο μέσα σε ένα ανοιχτό διάστημα, μετρώντας τον αριθμό των εναλλαγών ή μεταβολών προσήμου στην ακολουθία των συντελεστών του. 
Από το 1836, το θεώρημα του Μπουντάν έχει αντικατασταθεί στη βιβλιογραφία από ένα ισοδύναμο θεώρημα του Ζοζέφ Φουριέ. Το τελευταίο αναφέρεται με πολλά ονόματα, συμπεριλαμβανομένου και του Μπουντάν. Το πρωτότυπο θεώρημα του Μπουντάν αποτελεί τη βάση της πιο γρήγορης μέχρι σήμερα μεθόδου απομόνωσης πραγματικών ριζών πολυωνύμων.

Θεώρημα του Μπουντάν

Το θεώρημα του Μπουντάν είναι ισοδύναμο με αυτό του Φουριέ. Αν και η διατύπωση του Μπουντάν προηγήθηκε από αυτή του Φουριέ, το όνομα του Φουριέ συνδέεται συχνά με αυτή.

Θεώρημα του Φουριέ

Ο ορισμός του θεωρήματος του Φουριέ (για πολυώνυμα), το οποίο εμφανίζεται συχνά ως θεώρημα των Φουριέ-Μπουντάν ή ως θεώρημα των Μπουντάν-Φουριέ ή απλά ως θεώρημα του Μπουντάν, μπορεί να βρεθεί σχεδόν σε όλα τα σχετιζόμενα με το θέμα κείμενα και άρθρα.

Ακολουθία Φουριέ

Δεδομένης μιας εξίσωσης του ,  βαθμού  , η ακολουθία Φουριέ του , , ορίζεται ως η ακολουθία των  συναρτήσεων    όπου   είναι η ι-οστή παράγωγος του  . Οπότε, .

Παράδειγμα της ακολουθίας Φουριέ

Η ακολουθία Φουριέ του πολυωνύμου  είναι η .

Ιστορική ανασκόπηση

Στις αρχές του 19ου αιώνα, οι Μπουντάν και Φουριέ παρουσίασαν δύο διαφορετικά (αλλά ισοδύναμα) θεωρήματα τα οποία καθιστούν εφικτό τον καθορισμό του μέγιστου δυνατού αριθμού πραγματικών ριζών που έχει μια εξίσωση μέσα σε ένα δεδομένο διάστημα.
Η διατύπωση του Μπουντάν σπάνια αναφέρεται. Αντίθετα, η διατύπωση του Φουριέ χρησιμοποιείται συχνά και αναφέρεται ως θεώρημα του Φουριέ ή θεώρημα των Φουριέ-Μπουντάν ή θεώρημα των Μπουντάν-Φουριέ ή ακόμη και θεώρημα του Μπουντάν. Ο ορισμός ουσιαστικά του θεωρήματος του Μπουντάν εμφανίστηκε το 1807 στο υπόμνημα "Νέα μέθοδος για την επίλυση αριθμητικών εξισώσεων" ("Nouvelle méthode pour la résolution des équations numériques"), ενώ το θεώρημα του Φουριέ δημοσιεύτηκε για πρώτη φορά το 1820 στο "Δελτίο της επιστήμης, η Φιλομαθηματική κοινωνία του Παρισιού" ("Bulletin des Sciences, par la Société Philomatique de Paris"). Λόγω της σημασίας των δύο αυτών θεωρημάτων, υπήρξε μεγάλη διαμάχη όσον αφορά τα δικαιώματα προτεραιότητας (και στο Βιβλίο του Φρανσουά Αραγκό (François Arago) σελ. 383).

Εξαφάνιση του θεωρήματος του Μπουντάν

Το θεώρημα του Μπουντάν αποτελεί τη βάση για το θεώρημα του Βίνσεντ (Vincent) και την (εκθετική) μέθοδό του για την απομόνωση των πραγματικών ριζών πολυωνύμων. Επομένως, δεν είναι παράξενο ότι ο Βίνσεντ αναφέρει το θεώρημα του Μπουντάν και στα δύο άρθρα του το 1834 και 1836, το οποίο και συγκρίνει με αυτό του Φουριέ. Ο Βίνσεντ ήταν ο τελευταίος συγγραφέας του 19ου αιώνα που διατύπωσε το θεώρημα του Μπουντάν στην πρωτότυπή του μορφή.
Παρά το γεγονός ότι το θεώρημα του Μπουντάν ήταν τόσο μεγάλης σημασίας, η εμφάνιση του θεωρήματος του Στουρμ (Sturm) το 1827 του έδωσε το θανατηφόρο χτύπημα (το ίδιο συνέβη και με το θεώρημα του Βίνσεντ). Το θεώρημα του Στουρμ έλυσε το πρόβλημα της απομόνωσης πραγματικών ριζών καθορίζοντας τον ακριβή αριθμό των πραγματικών ριζών ενός πολυωνύμου σε ένα πραγματικό ανοιχτό διάστημα (a, b). Επίσης, ο ίδιος ο Στουρμ, σελ. 108, αναγνωρίζει τη μεγάλη επιρροή που άσκησε επάνω του το θεώρημα του Φουριέ: « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer.» το οποίο μεταφράζεται ως «Βασιζόμενος στις αρχές που καθόρισε και μιμούμενος τις αποδείξεις του βρήκα τα νέα θεωρήματα που πρόκειται να σας ανακοινώσω». Λόγω των παραπάνω, τα θεωρήματα των Φουριέ και Στουρμ εμφανίζονται σχεδόν σε όλα τα βιβλία θεωρίας εξισώσεων και η μόνη διαδεδομένη μέθοδος για τον υπολογισμό των πραγματικών ριζών πολυωνύμων ήταν αυτή του Στουρμ, η οποία και χρησιμοποιούνταν από τότε και στο εξής – έως περίπου το 1980, όταν και αντικαταστάθηκε (σχεδόν σε όλα τα συστήματα υπολογιστικής άλγεβρας) από μεθόδους που προέρχονται από το θεώρημα του Βίνσεντ, με τη μεγαλύτερη ταχύτητα να επιτυγχάνεται από τη μέθοδο VAS (Vincent–Akritas–Strzeboński).
Συνεπώς, το θεώρημα του Μπουντάν (αλλά όχι το όνομά του) οδηγήθηκε στη λήθη. Στο βιβλίο του Σερέ (Serret) υπάρχει το τμήμα 121  (σελ. 266) που αναφέρεται στο θεώρημα του Μπουντάν, ωστόσο η διατύπωση είναι αυτή του Φουριέ, διότι, όπως αναφέρει ο συγγραφέας στην υποσημείωση της σελ. 267, τα δύο θεωρήματα είναι ισοδύναμα και αυτό του Μπουντάν είχε σαφή προτεραιότητα. Προς τιμήν του, ο Σερέ συμπεριέλαβε το 1877 στην άλγεβρά του, σελ. 363–368, το θεώρημα του Βίνσεντ μαζί με την απόδειξή του, παραπέμποντας όλους τους ενδιαφερόμενους αναγνώστες στα άρθρα του Βίνσεντ για παραδείγματα χρήσης του θεωρήματός του. Ο Σερέ ήταν ο τελευταίος συγγραφέας που ανέφερε το θεώρημα του Βίνσεντ τον 19ο αιώνα.

Επανεμφάνιση του θεωρήματος του Μπουντάν

Το θεώρημα του Μπουντάν επανεμφανίστηκε, μετά από σχεδόν 150 χρόνια, στην διδακτορική διατριβή του Α. Ακρίτα με τίτλο "Η αλγεβρική χρήση του θεωρήματος του Βίνσεντ" ("Vincent's Theorem in Algebraic Manipulation"), Πανεπιστήμιο της Βόρειας Καρολίνας των ΗΠΑ (North Carolina State University, USA), το 1978 και σε διάφορες άλλες δημοσιεύσεις που προέκυψαν από την εν λόγω διατριβή.

Οι πιο σημαντικές εφαρμογές του θεωρήματος του Μπουντάν

Η (εκθετική) μέθοδος του Βίνσεντ (Vincent) για την απομόνωση των πραγματικών ριζών πολυωνύμων (η οποία βασίζεται στο θεώρημα του Βίνσεντ του 1834 και 1836) είναι η πιο σημαντική εφαρμογή του θεωρήματος του Μπουντάν. Επιπλέον, είναι το πιο αντιπροσωπευτικό παράδειγμα της σημασίας της διατύπωσης του θεωρήματος του Μπουντάν.  Όπως περιγράφεται παρακάτω, η διατύπωση του θεωρήματος του Φουριέ δεν βοήθησε τον Ουσπένσκι (Uspensky) να αντιληφθεί ότι δεν υπάρχουν ρίζες του  στο ανοιχτό διάστημα  αν  και  έχουν τον ίδιο αριθμό εναλλαγών προσήμου στην ακολουθία των συντελεστών τους (βλέπε σελ. 127–137).

Εφαρμογή του θεωρήματος του Βίνσεντ από τον ίδιο

Ο Βίνσεντ (Vincent) χρησιμοποιεί το θεώρημα του Μπουντάν αποκλειστικά ως ένα "τεστ μη ύπαρξης ριζών", για να εντοπίσει που εμφανίζονται οι ρίζες στον άξονα των x (ώστε να υπολογίσει τις τιμές  του θεωρήματός του). Με άλλα λόγια, για να βρει το ακέραιο μέρος μιας ρίζας, ο Βίνσεντ εφαρμόζει διαδοχικές αντικαταστάσεις της μορφής  και σταματά μόνο όταν τα πολυώνυμα  και  διαφέρουν ως προς τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών τους (δηλαδή όταν μειώνεται ο αριθμός των εναλλαγών προσήμου του p(x+1)).
Δείτε το αντίστοιχο διάγραμμα όπου η ρίζα βρίσκεται στο διάστημα . Εφόσον γενικά η τοποθεσία των ριζών δε γνωρίζεται εκ των προτέρων, η ρίζα μπορεί να βρεθεί (με τη βοήθεια του θεωρήματος του Μπουντάν) μόνο από αυτήν την μείωση στον αριθμό των εναλλαγών προσήμου. Το πολυώνυμο  ) δηλαδή, έχει λιγότερες εναλλαγές προσήμου από το πολυώνυμο . Έπειτα ο Βίνσεντ λαμβάνει εύκολα μια πρώτη προσέγγιση (συνεχών κλασμάτων) για τη ρίζα αυτή ως , όπως αναφέρεται και στο θεώρημά του. Ο Βίνσεντ εφαρμόζει αυτούς, και μόνο αυτούς, τους μετασχηματισμούς που περιγράφονται στο θεώρημά του.

Εφαρμογή του θεωρήματος του Βίνσεντ από τον Ουσπένσκι

Σύμφωνα με τον Αλεξέι Ουτέσεβ (Alexei Uteshev) του Πανεπιστημίου της Αγίας Πετρούπολης της Ρωσίας, ο Ουσπένσκι (Uspensky) βρήκε στον 20ο αιώνα την διατύπωση (και την απόδειξη) του θεωρήματος του Βίνσεντ (Vincent) στο βιβλίο της Άλγεβρας του Σερέ (Serret), σελ. 363–368, πράγμα που σημαίνει ότι δεν γνώριζε την διατύπωση του θεωρήματος του Μπουντάν (διότι ο Σερέ συμπεριέλαβε στο βιβλίο του το θεώρημα του Φουριέ). Επιπλέον, αυτό σημαίνει ότι ο Ουσπένσκι δεν είδε ποτέ τα άρθρα του Βίνσεντ (1834 και 1836), όπου αναφέρεται το θεώρημα του Μπουντάν και εξηγείται η μέθοδος του Βίνσεντ με διάφορα παραδείγματα (διότι ο Σερέ παραπέμπει όλους τους ενδιαφερόμενους αναγνώστες στα άρθρα του Βίνσεντ για παραδείγματα χρήσης του θεωρήματός του). Επομένως, στον πρόλογο του βιβλίου του που εκδόθηκε το 1949, ο Ουσπένσκι εσφαλμένα ισχυρίζεται ότι, βασιζόμενος στο θεώρημα του Βίνσεντ, ανακάλυψε μια μέθοδο για την απομόνωση πραγματικών ριζών "πολύ ανώτερη στην πράξη από τη μέθοδο που βασίζεται στο θεώρημα του Στουρμ". Η δήλωση του Ουσπένσκι είναι λανθασμένη διότι, εφόσον δεν χρησιμοποιεί το θεώρημα του Μπουντάν, απομονώνει τις πραγματικές ρίζες κάνοντας την διπλάσια εργασία από αυτήν που έκανε ο Βίνσεντ (βλέπε σελ. 127–137).

 
Ο Ουσπένσκι δεν γνωρίζει το θεώρημα του Μπουντάν, οπότε, δεν μπορεί να το χρησιμοποιήσει σαν "τεστ μη ύπαρξης ριζών". Επομένως, για αυτόν δεν αρκεί ότι το πολυώνυμο  έχει τον ίδιο αριθμό εναλλαγών προσήμου με το πολυώνυμο  ώστε να καταλήξει στο συμπέρασμα ότι το  δεν έχει ρίζες μέσα στο διάστημα . Για να βεβαιωθεί, εφαρμόζει επιπλέον την περιττή αντικατάσταση ("τεστ ύπαρξης ριζών στο 0_1" του Μπουντάν)  στο , η οποία οδηγεί ανελλιπώς σε ένα πολυώνυμο χωρίς εναλλαγές προσήμου, και συνεπώς χωρίς θετικές ρίζες.
Ο Ουσπένσκι χρησιμοποιεί την πληροφορία που έλαβε από την (απαραίτητη) αντικατάσταση  και από την (περιττή) αντικατάσταση  για να καταλήξει στο συμπέρασμα ότι το  δεν έχει ρίζες στο διάστημα . Με άλλα λόγια, αναζητώντας μία ρίζα, ο Ουσπένσκι ακολουθεί τη διαδικασία που απεικονίζεται στην αντίστοιχη εικόνα.
Οι μετασχηματισμοί του Ουσπένσκι δεν είναι αυτοί που περιγράφονται στο θεώρημα του Βίνσεντ και, συνεπώς, οι μετασχηματισμοί του απαιτούν τον διπλάσιο υπολογιστικό χρόνο από αυτούς του θεωρήματος του Βίνσεντ.