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

.

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

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

Εναλλαγή προσήμου

Έστω ότι \( c_0, c_1, c_2, \ldots \) είναι μια πεπερασμένη ή άπειρη ακολουθία πραγματικών αριθμών. Υποθέστε ότι l < r και ότι ισχύουν οι ακόλουθες συνθήκες:

Αν r = l + 1, τότε οι αριθμοί \( c_l \) και \( c_r \) έχουν αντίθετα πρόσημα.
Αν ( c r \ge l + 2, τότε οι αριθμοί ( cc_{l+1}, \ldots, c_{r-1} \) είναι όλοι μηδέν και οι αριθμοί ( cc_l \) και ( cc_r \) έχουν αντίθετα πρόσημα.

Έτσι ορίζεται η εναλλαγή ή μεταβολή προσήμου μεταξύ των αριθμών \( c c_l \) και \( cc_r \) .
Ο αριθμός των εναλλαγών προσήμου ενός πολυωνύμου p(x) μιας μεταβλητής ορίζεται ως ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του.

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

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

Ορισμός του θεωρήματος του Μπουντάν

Δεδομένης μιας εξίσωσης του x, p(x) = 0 βαθμού n > 0, είναι δυνατόν να πραγματοποιηθούν δύο αντικαταστάσεις της μορφής \( c x \leftarrow x + l \) και \( cx \leftarrow x + r \) όπου l και r δύο πραγματικοί αριθμοί τέτοιοι ώστε l < r. Αν v_l και v_r είναι οι εναλλαγές προσήμου στις ακολουθίες των συντελεστών των p(x+l) και p(x+r) αντίστοιχα, τότε, υπό την προϋπόθεση ότι \( c p(r) \ne 0, ισχύουν τα ακόλουθα:

Οι εναλλαγές προσήμου στο πολυώνυμο p(x+l) δεν μπορεί να είναι λιγότερες από αυτές στο p(x+r). Εν συντομία, \( c v_l \ge v_r \)
Ο αριθμός \( \rho \) των πραγματικών ριζών της εξίσωσης p(x) = 0 που βρίσκονται στο ανοιχτό διάστημα (l,r) δεν μπορεί να είναι μεγαλύτερος από τον αριθμό των εναλλαγών προσήμου που χάνονται καθώς περνάμε από το μετασχηματισμένο πολυώνυμο p(x+l) στο μετασχηματισμένο πολυώνυμο p(x+r). Εν συντομία, \( c\rho \le v_l - v_r \)
Όταν ο αριθμός \( c rho \) των πραγματικών ριζών της εξίσωσης p(x) = 0 που βρίσκονται στο ανοιχτό διάστημα (l,r) είναι αυστηρά μικρότερος από τον αριθμό των εναλλαγών προσήμου που χάνονται καθώς περνάμε από το μετασχηματισμένο πολυώνυμο p(x+l) στο μετασχηματισμένο πολυώνυμο p(x+r), τότε η διαφορά είναι πάντα ένας άρτιος αριθμός. Εν συντομία, \( c\rho = v_l - v_r -2\lambda \) όπου \( c\lambda ∈ \mathbb{Z}_+ \) .

Κάνοντας χρήση των αντικαταστάσεων \( x \leftarrow x + l \) και \( x \leftarrow x + r \) , ο ακριβής αριθμός των πραγματικών ριζών στο διάστημα (l,r) μπορεί να βρεθεί μόνο σε δύο περιπτώσεις:

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

Παραδείγματα του θεωρήματος του Μπουντάν

1. Δεδομένου ενός πολυωνύμου \( cp(x)=x^3 -7x + 7 \) και του ανοιχτού διαστήματος (0,2), οι αντικαταστάσεις \( c x \leftarrow x + 0 \) και \( x \leftarrow x + 2 \) δίνουν:

\( c ( c p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2 \)

\( c p(x+2)=(x+2)^3 -7(x+2) + 7\Rightarrow p(x+2)=x^3+6x+5x+1, v_2=0 \)

Οπότε, από το θεώρημα του Μπουντάν, \(\rho \le v_0 - v_2 = 2 \) . Επομένως, το πολυώνυμο p(x) έχει είτε δύο ρίζες είτε καμία ρίζα στο ανοιχτό διάστημα (0,2), μια περίπτωση που πρέπει να διερευνηθεί περαιτέρω.

2. Δεδομένου του ίδιου πολυωνύμου \(p(x)=x^3 -7x + 7 \) και του ανοιχτού διαστήματος (0,1) οι αντικαταστάσεις \(x \leftarrow x + 0 \) και \( x \leftarrow x + 1 \) δίνουν:

\( p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2 \)

\( p(x+1)=(x+1)^3 -7(x+1) + 7\Rightarrow p(x+1)=x^3+3x-4x+1, v_2=2 \)

Οπότε, από το θεώρημα του Μπουντάν, \(\rho = v_0 - v_2 = 0 \) , δηλαδή δεν υπάρχουν ρίζες στο ανοιχτό διάστημα (0,1).

Το παραπάνω παράδειγμα υποδεικνύει την κύρια χρήση του θεωρήματος του Μπουντάν σαν ένα "τεστ μη ύπαρξης ριζών".

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

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

Δεδομένης μιας εξίσωσης του x, p(x) = 0 βαθμού n > 0 , η ακολουθία Φουριέ του \( p(x), F_\text{seq}(x) \) , ορίζεται ως η ακολουθία των n + 1 συναρτήσεων \(p(x), p^{(1)}(x),\ldots,p^{(n)}(x) όπου p^{(i)} είναι η ι-οστή παράγωγος του p(x). Οπότε, \(F_\text{seq}(x)=\big\{ p(x), p^{(1)}(x),\ldots,p^{(n)}(x)\big\} \) .
Παράδειγμα της ακολουθίας Φουριέ

Η ακολουθία Φουριέ του πολυωνύμου \(p(x)=x^3 -7x + 7 \) είναι η \(F_\text{seq}(x)=\big\{x^3 -7x + 7,3x^2-7,6x,6\big\} \) .

Ορισμός του θεωρήματος του Φουριέ

Δεδομένης μιας πολυωνυμικής εξίσωσης του x, p(x) = 0 βαθμού n > 0 με πραγματικούς συντελεστές και την αντίστοιχη ακολουθία Φουριέ \(F_\text{seq}(x)=\big\{ p(x), p^{(1)}(x),\ldots,p^{(n)}(x)\big\} \) , το x μπορεί να αντικατασταθεί από δύο οποιουσδήποτε πραγματικούς αριθμούς l,r (l<r). Αν οι δύο προκύπτουσες αριθμητικές ακολουθίες αναπαριστώνται από\( F_\text{seq}(l) και F_\text{seq}(r) αντίστοιχα και οι εναλλαγές προσήμου τους από \( v_l, v_r \) αντίστοιχα, τότε, υπό την προϋπόθεση ότ ι\( p(r) \ne 0 \) , ισχύουν τα ακόλουθα:

Η ακολουθία \(F_\text{seq}(l) \) δεν μπορεί να παρουσιάζει εναλλαγές προσήμου λιγότερες από την ακολουθία \(F_\text{seq}(r) \) . Εν συντομία, \(v_l \ge v_r \)
Ο αριθμός \( \rho των πραγματικών ριζών της εξίσωσης p(x) = 0 που βρίσκονται στο ανοιχτό διάστημα (l,r) δεν μπορεί να είναι μεγαλύτερος από τον αριθμό των εναλλαγών προσήμου που χάνονται καθώς περνάμε από την ακολουθία \(F_\text{seq}(l) \) στην ακολουθία \(F_\text{seq}(r) \) . Εν συντομία,\( \rho \le v_l - v_r
Όταν ο αριθμός \rho των πραγματικών ριζών της εξίσωσης p(x) = 0 που βρίσκονται στο ανοιχτό διάστημα (l,r) είναι αυστηρά μικρότερος από τον αριθμό των εναλλαγών προσήμου που χάνονται καθώς περνάμε από την ακολουθία \(F_\text{seq}(l) \) στην ακολουθία F_\text{seq}(r), τότε η διαφορά είναι πάντα ένας άρτιος αριθμός. Εν συντομία, \(\rho = v_l - v_r -2\lambda \) όπου \( \lambda \in \mathbb{Z}_+ \)

Παράδειγμα του θεωρήματος του Φουριέ

Δεδομένου του πολυωνύμου που αναφέρθηκε προηγουμένως \(p(x)=x^3 -7x + 7 \) και του ανοιχτού διαστήματος (0,2), οι ακόλουθες πεπερασμένες ακολουθίες και οι αντίστοιχες εναλλαγές προσήμου τους μπορούν να υπολογιστούν:

\(F_\text{seq}(0)=\big\{7,-7,0,6\big\},v_0=2 \)

\(F_\text{seq}(2)=\big\{1,5,12,6\big\},v_2=0 \)

Οπότε, από το θεώρημα του Φουριέ, \(\rho \le v_0 - v_2 = 2 \) . Επομένως, το πολυώνυμο p(x) έχει είτε δύο ρίζες είτε καμία ρίζα στο ανοιχτό διάστημα (0,2), μια περίπτωση που πρέπει να διερευνηθεί περαιτέρω.

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

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

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

Στη "Νέα μέθοδο για την επίλυση αριθμητικών εξισώσεων",[1] ο ίδιος ο Μπουντάν χρησιμοποίησε το θεώρημά του για να υπολογίσει τις ρίζες οποιασδήποτε πολυωνυμικής εξίσωσης υπολογίζοντας τα δεκαδικά ψηφία των ριζών. Πιο συγκεκριμένα, ο Μπουντάν χρησιμοποίησε το θεώρημά του ως ένα "τεστ μη ύπαρξης ριζών", το οποίο μπορεί να οριστεί ως εξής: εάν τα πολυώνυμα p(x+a) και p(x +a+ 1) έχουν (στην ακολουθία των συντελεστών τους) τον ίδιο αριθμό εναλλαγών προσήμου, τότε το θεώρημα του Μπουντάν δηλώνει ότι το p(x) δεν έχει πραγματικές ρίζες στο διάστημα (a,a+1).

Επιπλέον, στο βιβλίο του,[1] σελ. 37, ο Μπουντάν παρουσιάζει ανεξάρτητα από το θεώρημά του ένα "τεστ ύπαρξης ριζών στο 0_1", το οποίο αποτελεί ένα κριτήριο για να καθορίσουμε αν ένα πολυώνυμο έχει ρίζες στο διάστημα (0,1). Το τεστ αυτό μπορεί να οριστεί ως εξής:

Εκτέλεσε στο πολυώνυμο p(x) την αντικατάσταση \(x \longleftarrow \frac{1}{x +1} \) και υπολόγισε τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών του μετασχηματισμένου πολυωνύμου. Αυτός ο αριθμός δίνει ένα άνω όριο στον αριθμό των πραγματικών ριζών που έχει το πολυώνυμο p(x) μέσα στο ανοιχτό διάστημα (0,1). Πιο συγκεκριμένα, ο αριθμός \( \rho_{01}(p) \) των πραγματικών ριζών στο ανοιχτό διάστημα (0,1) — λαμβάνοντας υπ’ όψιν και τις πολλαπλότητες — του πολυωνύμου \( p(x) \in \mathbb{R}[x] \) , βαθμού deg(p), έχει σαν πάνω φράγμα τον αριθμό των εναλλαγών προσήμου \( var_{01}(p) \) , όπου

\( var_{01}(p) = var((x+1)^{deg(p)}p(\frac{1}{x+1})) \)

και \(var_{01}(p) \ge \rho_{01}(p) \) . Όπως και στην περίπτωση του κανόνα προσήμων του Ντεκάρτ αν \(var_{01}(p)=0 τότε \rho_{01}(p)=0 \) και αν \(var_{01}(p)=1 \) τότε \(\rho_{01}(p)=1 \) .

Το τεστ αυτό (το οποίο είναι μια ειδική περίπτωση του γενικότερου "τεστ ύπαρξης ριζών στο \( a_b \) " των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi)) χρησιμοποιήθηκε μεταγενέστερα από τον Ουσπένσκι (Uspensky) τον 20ο αιώνα.[6] Ο Ουσπένσκι ήταν αυτός που κράτησε ζωντανό το θεώρημα του Βίνσεντ (Vincent), "παίρνοντας την σκυτάλη" από τον Σερέ (Serret).[7][8]

Το 1831 ο Μπουρντόν (Bourdon)[9] συνδύασε το θεώρημα του Μπουντάν με τη μέθοδο συνεχών κλασμάτων του Λαγκράνζ (Lagrange) για την προσέγγιση πραγματικών ριζών πολυωνύμων και, έτσι, προσέφερε μια προεπισκόπηση της μεθόδου του Βίνσεντ, χωρίς να του δώσει τα εύσημα. Όπως αναφέρει ο Βίνσεντ στην πρώτη κιόλας πρόταση των άρθρων του το 1834[10] και 1836[11], ο Μπουρντόν χρησιμοποίησε στο βιβλίο του μια κοινή τους παρουσίαση.

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

Το θεώρημα του Μπουντάν αποτελεί τη βάση για το θεώρημα του Βίνσεντ (Vincent) και την (εκθετική) μέθοδό του για την απομόνωση των πραγματικών ριζών πολυωνύμων. Επομένως, δεν είναι παράξενο ότι ο Βίνσεντ αναφέρει το θεώρημα του Μπουντάν και στα δύο άρθρα του το 1834[10] και 1836[11], το οποίο και συγκρίνει με αυτό του Φουριέ. Ο Βίνσεντ ήταν ο τελευταίος συγγραφέας του 19ου αιώνα που διατύπωσε το θεώρημα του Μπουντάν στην πρωτότυπή του μορφή.

Παρά το γεγονός ότι το θεώρημα του Μπουντάν ήταν τόσο μεγάλης σημασίας, η εμφάνιση του θεωρήματος του Στουρμ (Sturm) το 1827 του έδωσε το θανατηφόρο χτύπημα (το ίδιο συνέβη και με το θεώρημα του Βίνσεντ). Το θεώρημα του Στουρμ έλυσε το πρόβλημα της απομόνωσης πραγματικών ριζών καθορίζοντας τον ακριβή αριθμό των πραγματικών ριζών ενός πολυωνύμου σε ένα πραγματικό ανοιχτό διάστημα (a, b). Επίσης, ο ίδιος ο Στουρμ,[12] σελ. 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).[13]

Συνεπώς, το θεώρημα του Μπουντάν (αλλά όχι το όνομά του) οδηγήθηκε στη λήθη. Στο βιβλίο του Σερέ (Serret)[8] υπάρχει το τμήμα 121 (σελ. 266) που αναφέρεται στο θεώρημα του Μπουντάν, ωστόσο η διατύπωση είναι αυτή του Φουριέ, διότι, όπως αναφέρει ο συγγραφέας στην υποσημείωση της σελ. 267, τα δύο θεωρήματα είναι ισοδύναμα και αυτό του Μπουντάν είχε σαφή προτεραιότητα. Προς τιμήν του, ο Σερέ συμπεριέλαβε το 1877 στην άλγεβρά του,[8] σελ. 363–368, το θεώρημα του Βίνσεντ μαζί με την απόδειξή του, παραπέμποντας όλους τους ενδιαφερόμενους αναγνώστες στα άρθρα του Βίνσεντ για παραδείγματα χρήσης του θεωρήματός του. Ο Σερέ ήταν ο τελευταίος συγγραφέας που ανέφερε το θεώρημα του Βίνσεντ τον 19ο αιώνα.
Επανεμφάνιση του θεωρήματος του Μπουντάν

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

Το θεώρημα του Μπουντάν είναι ισοδύναμο με αυτό του Φουριέ. Η ισοδυναμία αυτή είναι προφανής από το γεγονός ότι, δεδομένου ενός πολυωνύμου p(x) βαθμού n > 0 , οι n+1 όροι της ακολουθίας Φουριέ \(F_\text{seq}(a) \) (που προκύπτει αντικαθιστώντα ς\( x \leftarrow a \) στην ακολουθία \(F_\text{seq}(x)) \) έχουν τα ίδια πρόσημα (και είναι ανάλογοι) με τους αντίστοιχους συντελεστές του πολυωνύμου \(p(x+a)=\sum_{i=0}^n \frac{p^{(i)}(a)}{i!}\ x^i \) , που προκύπτει από το θεώρημα επέκτασης του Τέιλορ (Taylor).

Όπως επισημαίνουν οι Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi) στην υποσημείωση 9, σελ. 222 της δημοσίευσή τους,[14] η διαμάχη για τα δικαιώματα προτεραιότητας των Μπουντάν και Φουριέ είναι από μια σύγχρονη σκοπιά μάλλον ανούσια. Οι δύο συγγραφείς θεωρούν ότι ο Μπουντάν έχει μία "καταπληκτικά σύγχρονη κατανόηση της σημασίας της αναγωγής σε απλές προθέσεις του αλγορίθμου (τα δικά του λόγια) για την μετάθεση ενός πολυωνύμου με την αντικατάσταση x \leftarrow x+p, όπου p είναι ένας ακέραιος αριθμός".

Παρόλη την ισοδυναμία τους, τα δύο θεωρήματα έπαιξαν ξεχωριστό ρόλο στην απομόνωση των πραγματικών ριζών πολυωνύμων με ρητούς συντελεστές. Δηλαδή:

Το θεώρημα του Φουριέ οδήγησε τον Στουρμ (Sturm) στα θεωρήματά του και τη μέθοδό του,[12] ενώ
Το θεώρημα του Μπουντάν αποτελεί τη βάση της μεθόδου Vincent–Akritas–Strzeboński (VAS).[13]

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

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

Εάν σε μια πολυωνυμική εξίσωση με ρητούς συντελεστές και χωρίς πολλαπλές ρίζες γίνουν διαδοχικοί μετασχηματισμοί της μορφής

\( x = a + \frac{1}{x'},\quad x' = b + \frac{1}{x''},\quad x'' = c + \frac{1}{x'''}, \ldots \)

όπου a, b και c είναι οποιοδήποτε θετικοί αριθμοί μεγαλύτεροι ή ίσοι της μονάδας, τότε μετά από έναν αριθμό τέτοιων μετασχηματισμών, η προκύπτουσα μετασχηματισμένη εξίσωση έχει είτε μηδενικές εναλλαγές προσήμου είτε μία και μοναδική. Στην πρώτη περίπτωση δεν υπάρχει ρίζα ενώ στη δεύτερη περίπτωση υπάρχει μία πραγματική θετική ρίζα. Επιπλέον, η αντίστοιχη ρίζα της προτεινόμενης εξίσωσης προσεγγίζεται από το πεπερασμένο συνεχές κλάσμα:[10][11][15]

\( a + \cfrac{1}{b + \cfrac{1}{c + \cfrac{1}{\ddots}}} \)

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

Η παραπάνω διατύπωση αποτελεί μια πιστή μετάφραση του θεωρήματος που βρέθηκε στα πρωτότυπα άρθρα του Βίνσεντ.[10][11][15] Για μια πιο σαφή κατανόηση του θεωρήματος του Βίνσεντ δείτε τις παρατηρήσεις στο αντίστοιχο λήμμα της Βικιπαίδεια Θεώρημα του Βίνσεντ.

Εφαρμογή του θεωρήματος του Βίνσεντ από τον ίδιο
Η αναζήτηση μιας ρίζας από τον Βίνσεντ (εφαρμόζοντας το θεώρημα του Μπουντάν).

Ο Βίνσεντ (Vincent) χρησιμοποιεί το θεώρημα του Μπουντάν αποκλειστικά ως ένα "τεστ μη ύπαρξης ριζών", για να εντοπίσει που εμφανίζονται οι ρίζες στον άξονα των x (ώστε να υπολογίσει τις τιμές a,b,c ,\ldots του θεωρήματός του). Με άλλα λόγια, για να βρει το ακέραιο μέρος μιας ρίζας, ο Βίνσεντ εφαρμόζει διαδοχικές αντικαταστάσεις της μορφής \( x \leftarrow x + 1 \) και σταματά μόνο όταν τα πολυώνυμα p(x) και p(x + 1) διαφέρουν ως προς τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών τους (δηλαδή όταν μειώνεται ο αριθμός των εναλλαγών προσήμου του p(x+1)).[10][11]

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

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

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

Η αναζήτηση μιας ρίζας από τον Ουσπένσκι (χωρίς την εφαρμογή του θεωρήματος του Μπουντάν).

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

Οι μετασχηματισμοί του Ουσπένσκι δεν είναι αυτοί που περιγράφονται στο θεώρημα του Βίνσεντ και, συνεπώς, οι μετασχηματισμοί του απαιτούν τον διπλάσιο υπολογιστικό χρόνο από αυτούς του θεωρήματος του Βίνσεντ.[6][16]

Δείτε επίσης

Μέθοδος Νιούτον

Παραπομπές

Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier.
Fourier, Jean Baptiste Joseph (1820). «Sur l'usage du théorème de Descartes dans la recherche des limites des racines». Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.
Akritas, Alkiviadis G. (1981). «On the Budan–Fourier Controversy». ACM-SIGSAM Bulletin 15 (1): 8–10. doi:10.1145/1089242.1089243.
Akritas, Alkiviadis G. (1982). «Reflections on a Pair of Theorems by Budan and Fourier». Mathematics Magazine 55 (5): 292–298. doi:10.2307/2690097.
Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation)
Akritas, Alkiviadis G. (1986). There is no "Uspensky's Method". In: Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86, Waterloo, Ontario, Canada), pp. 88–90.
Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company., pp. 298–303
Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars.
Bourdon, Louis Pierre Marie (1831). Éléments d'Algèbre. Paris: Bachelier Père et Fils (6th edition)., pp. 717–760
Vincent, Alexandre Joseph Hidulph (1834). «Mémoire sur la résolution des équations numériques». Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille: 1–34.
Vincent, Alexandre Joseph Hidulph (1836). «Sur la résolution des équations numériques». Journal de Mathématiques Pures et Appliquées 1: 341–372.
Hourya, Benis-Sinaceur (1988). «Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm». Revue d'histoire des sciences 41 (2): 99–132.
Akritas, Alkiviadis G.; A.W. Strzeboński, P.S. Vigklas (2008). «Improving the performance of the continued fractions method using new bounds of positive roots». Nonlinear Analysis: Modelling and Control 13: 265–279.
Alesina, Alberto; Massimo Galuzzi (1998). «A new proof of Vincent's theorem». L'Enseignement Mathématique 44 (3-4): 219–256.
Vincent, Alexandre Joseph Hidulph (1838). «Addition à une précédente note relative à la résolution des équations numériques». Journal de Mathématiques Pures et Appliquées 3: 235–243.

Akritas, Alkiviadis G. (2008). There is no "Descartes' method". In: M.J.Wester and M. Beaudin (Eds), Computer Algebra in Education, AullonaPress, USA, pp. 19–35.

Εξωτερικοί σύνδεσμοι

Budan, F.: Εκτεταμένη Βιογραφία http://www-history.mcs.st-andrews.ac.uk/Biographies/Budan_de_Boislaurent.html
Εγκυκλοπαίδεια των Μαθηματικών http://www.encyclopediaofmath.org/index.php/Budan-Fourier_theorem

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Budan's theorem της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License