Θεώρημα του Βίνσεντ

Στα μαθηματικά, το θεώρημα του Βίνσεντ — το οποίο πήρε το όνομά του από τον Αλεξάντρ Ζοζέφ Ιντούλφ Βενσάν — είναι ένα θεώρημα το οποίο απομονώνει τις πραγματικές ρίζες πολυωνύμων με ρητούς συντελεστές.
Παρ’ όλο που το θεώρημα αυτό αποτελεί τη βάση για την ταχύτερη μέθοδο απομόνωσης των πραγματικών ριζών πολυωνύμων, είχε σχεδόν τελείως ξεχαστεί επειδή επισκιάστηκε  από το θεώρημα του Στουρμ (Sturm). Το αποτέλεσμα είναι ότι δεν εμφανίζεται σε κανένα από τα κλασσικά βιβλία του 20ου αιώνα τα σχετικά με τη θεωρία εξισώσεων, εκτός από το βιβλίο του Ουσπένσκι (Uspensky). Παρουσιάζονται δύο παραλλαγές του θεωρήματος αυτού (συνεχών κλασμάτων και διχοτόμησης), μαζί με διάφορες μεθόδους απομόνωσης πραγματικών ριζών που προέρχονται από τις παραλλαγές αυτές.

Πρώιμες εφαρμογές του θεωρήματος του Βίνσεντ

Και στα δύο άρθρα του, ο Βίνσεντ παρουσιάζει παραδείγματα που δείχνουν επακριβώς τη χρήση του θεωρήματός του για την απομόνωση των πραγματικών ριζών πολυωνύμων με συνεχή κλάσματα. Ωστόσο, η μέθοδος αυτή απαιτεί εκθετικό υπολογιστικό χρόνο, γεγονός το οποίο είχαν αντιληφθεί οι μαθηματικοί της εποχής εκείνης, όπως το αντιλήφθηκε επίσης και ο Ουσπένσκι (Uspensky) (σελ. 136) έναν αιώνα αργότερα.
Η εκθετική φύση του αλγορίθμου του Βίνσεντ οφείλεται στον τρόπο με τον οποίο υπολογίζονται (στο θεώρημα του Βίνσεντ) τα μερικά πηλίκα aᵢ. Δηλαδή, για να υπολογίσει το κάθε μερικό πηλίκο aᵢ, που σημαίνει για να εντοπίσει την θέση των ριζών πάνω στον άξονα των x, ο Βίνσεντ χρησιμοποιεί το θεώρημα του Μπουντάν (Budan) ως ένα "τεστ μη ύπαρξης ριζών". Με άλλα λόγια, με σκοπό να βρει το ακέραιο μέρος μιας ρίζας, ο Βίνσεντ εφαρμόζει διαδοχικές αντικαταστάσεις της μορφής x ← x+1 και σταματά μόνο όταν τα πολυώνυμα p(x) και p(x+1) διαφέρουν ως προς τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών τους (δηλαδή όταν μειώνεται ο αριθμός των εναλλαγών προσήμου του p(x+1)).
Δείτε το αντίστοιχο διάγραμμα όπου η ρίζα βρίσκεται στο διάστημα (5, 6). Εύκολα συνεπάγεται ότι, με τον τρόπο αυτό, εάν η ρίζα βρίσκεται μακριά από το αρχικό σημείο μηδέν, απαιτείται όλο και περισσότερος χρόνος για να βρεθεί το ακέραιο τμήμα της. Σε αυτό οφείλεται και η εκθετική φύση του αλγορίθμου του Βίνσεντ. Παρακάτω εξηγείται ο τρόπος με τον οποίο λύνεται το μειονέκτημα αυτό.

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

Ο Βίνσεντ ήταν ο τελευταίος συγγραφέας του 19ου αιώνα που χρησιμοποίησε το θεώρημά του για την απομόνωση των πραγματικών ριζών ενός πολυωνύμου.
Ο λόγος ήταν η εμφάνιση το 1827 του θεωρήματος του Στουρμ (Sturm), το οποίο έλυσε το πρόβλημα της απομόνωσης των πραγματικών ριζών σε πολυωνυμικό χρόνο, καθορίζοντας τον ακριβή αριθμό των πραγματικών ριζών ενός πολυωνύμου σε ένα πραγματικό ανοιχτό διάστημα (a, b). Η μέθοδος του Στουρμ ήταν η μόνη διαδεδομένη μέθοδος για τον υπολογισμό των πραγματικών ριζών πολυωνύμων μέχρι περίπου το 1980, όταν και αντικαταστάθηκε (σχεδόν σε όλα τα συστήματα υπολογιστικής άλγεβρας) από μεθόδους που προέρχονται από το θεώρημα του Βίνσεντ, με τον καλύτερο  χρόνο να επιτυγχάνεται από τη μέθοδο VAS (Vincent–Akritas–Strzeboński).
Ο Σερέ (Serret) συμπεριέλαβε το 1877 στην άλγεβρά του, σελ. 363–368, το θεώρημα του Βίνσεντ μαζί με την απόδειξή του. Όμως, για  παραδείγματα χρήσης του θεωρήματος αυτού, παραπέμπει τους ενδιαφερόμενους αναγνώστες στα άρθρα του Βίνσεντ. Ο Σερέ ήταν ο τελευταίος συγγραφέας που ανέφερε το θεώρημα του Βίνσεντ τον 19ο αιώνα.

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

Τον 20ο αιώνα το θεώρημα του Βίνσεντ δεν εμφανίζεται σε κανένα βιβλίο θεωρίας εξισώσεων, με εξαίρεση τα βιβλία των Ουσπένσκι (Uspensky) και Ομπρέσκοφ (Obreschkoff), όπου στο βιβλίο του δεύτερου δίνεται απλά η διατύπωση του θεωρήματος.
Ήταν το βιβλίο του Ουσπένσκι αυτό στο οποίο βρήκε ο Α. Ακρίτας το θεώρημα του Βίνσεντ, το οποίο και αποτέλεσε το  θέμα της διδακτορικής του διατριβής με τίτλο "Η αλγεβρική χρήση του θεωρήματος του Βίνσεντ" ("Vincent's Theorem in Algebraic Manipulation"), Πανεπιστήμιο της Βόρειας Καρολίνας των ΗΠΑ (North Carolina State University, USA), το 1978. Μία από τις μεγαλύτερες επιτυχίες για την εποχή εκείνη ήταν η απόκτηση του πρωτότυπου άρθρου του Βίνσεντ του 1836, κάτι που είχε διαφύγει από τον Ουσπένσκι — γεγονός που οδήγησε σε μια μεγάλη παρεξήγηση. Το πρωτότυπο άρθρο του Βίνσεντ έγινε διαθέσιμο στον Α. Ακρίτα χάρη στις αξιέπαινες προσπάθειες (δανεισμός από άλλη βιβλιοθήκη) μιας βιβλιοθηκάριου της Βιβλιοθήκης του Πανεπιστημίου του Ουισκόνσιν-Μάντισον, ΗΠΑ (University of Wisconsin–Madison, USA).

Μέθοδος συνεχών κλασμάτων

Μόνο μία μέθοδος συνεχών κλασμάτων προέρχεται από το θεώρημα του Βίνσεντ. Όπως αναφέρθηκε παραπάνω, η ιστορία αυτής της μεθόδου ξεκίνησε τη δεκαετία του 1830, όταν ο Βίνσεντ παρουσίασε και στα δύο άρθρα του πολλά παραδείγματα που δείχνουν επακριβώς πως χρησιμοποιείται το θεώρημά του για την απομόνωση των πραγματικών ριζών πολυωνύμων με συνεχή κλάσματα. Ωστόσο, η προκύπτουσα μέθοδος είχε εκθετικό χρόνο εκτέλεσης. Παρακάτω ακολουθεί μία ανάλυση για το πώς εξελίχθηκε η μέθοδος αυτή.

Παράδειγμα της VAS(p, M)

Εφαρμογή της μεθόδου VAS στο πολυώνυμο p(x) = x³ − 7x + 7 (σημειώστε ότι M(x) = x).

5η επανάληψη

VAS(x³ + 6x² + 5x + 1, x + 2) 

1 var ← 0 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του πολυωνύμου p(x) = x³ + 6x² + 5x + 1

2          RETURN ∅
Λίστα διαστημάτων απομόνωσης: {(1, ), (, 2)}.
Λίστα ζευγαριών {p, M} προς επεξεργασία: ∅. 
Τέλος.

Συμπέρασμα

Επομένως, οι δύο θετικές ρίζες του πολυωνύμου p(x) = x³ − 7x + 7 βρίσκονται μέσα στα διαστήματα απομόνωσης (1, ) και (, 2). Κάθε ρίζα μπορεί να προσεγγιστεί (για παράδειγμα) διχοτομώντας το αντίστοιχο διάστημα απομόνωσης έως ότου η διαφορά των καταληκτικών σημείων (endpoints) να είναι μικρότερη του 10⁻⁶. Με αυτή την προσέγγιση οι ρίζες του πολυωνύμου είναι οι ρ₁ = 1.3569 και ρ₂ = 1.69202.

Μέθοδοι διχοτόμησης

Υπάρχουν διάφορες μέθοδοι διχοτόμησης που προέρχονται από το θεώρημα του Βίνσεντ. Εδώ παρουσιάζονται οι δύο πιο σημαντικές από αυτές, η μέθοδος Vincent-Collins-Akritas (VCA) και η μέθοδος Vincent-Alesina-Galuzzi (VAG).
Η μέθοδος Vincent-Alesina-Galuzzi (VAG) είναι η απλούστερη από όλες τις μεθόδους που προέρχονται από το θεώρημα του Βίνσεντ αλλά περιλαμβάνει το πιο χρονοβόρο τεστ (στην γραμμή 1 του αλγορίθμου) για να καθορίσει εάν ένα πολυώνυμο έχει ρίζες στο διάστημα που μας ενδιαφέρει. Το γεγονός αυτό καθιστά την μέθοδο αυτή την πιο αργή από όλες τις μεθόδους που περιγράφονται στο παρόν άρθρο. 
Αντίθετα, η μέθοδος Vincent-Collins-Akritas (VCA) είναι περισσότερο περίπλοκη αλλά χρησιμοποιεί ένα πιο απλό τεστ ((στην γραμμή 1 του αλγορίθμου) από ότι η μέθοδος VAG. Το γεγονός αυτό σε συνδυασμό με ορισμένες βελτιώσεις καθιστά τη μέθοδο VCA την ταχύτερη μέθοδο διχοτόμησης.

Παράδειγμα της VCA(p, (a,b))

Δεδομένου του πολυωνύμου porig(x) = x³ − 7x + 7 και θεωρώντας ub = 4 ως ένα άνω όριο στις τιμές των θετικών ριζών, τα ορίσματα της VCA μεθόδου είναι: p(x) = 64x³ − 28x + 7 και (a, b) = (0, 4).

7η επανάληψη

VCA(64x³ + 192x² + 80x + 8, (2, 4)) 
 
1 var ← 0 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = 8x³ + 104x² + 376x + 344 

2 RETURN ∅
Λίστα διαστημάτων απομόνωσης: {(1, ), (, 2)}.
Λίστα ζευγαριών {p, I} προς επεξεργασία: ∅. 
Τέλος.

Συμπέρασμα

Επομένως, οι δύο θετικές ρίζες του πολυωνύμου p(x) = x³ − 7x + 7 βρίσκονται μέσα στα διαστήματα απομόνωσης (1, ) και (, 2). Κάθε ρίζα μπορεί να προσεγγιστεί (για παράδειγμα) διχοτομώντας το αντίστοιχο διάστημα απομόνωσης έως ότου η διαφορά των καταληκτικών σημείων (endpoints) να είναι μικρότερη του 10⁻⁶. Με αυτή την προσέγγιση οι ρίζες του πολυωνύμου είναι οι ρ₁ = 1.3569 και ρ₂ = 1.69202.

Παράδειγμα της VAG(p, (a, b))

Δεδομένου του πολυωνύμου p(x) = x³ − 7x + 7 και θεωρώντας ub = 4 ως ένα άνω όριο στις τιμές των θετικών ριζών, τα ορίσματα της VAG μεθόδου είναι: p(x) = x³ − 7x + 7 και (a, b) = (0, 4).

1η επανάληψη

1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = 43x³ − 35x² − 7x + 7

4 m ← (0 + 4) = 2

5 p(m) = 1

8          RETURN VAG(x³ − 7x + 7, (0, 2)) ∪ VAG(x³ − 7x + 7, (2, 4)
Λίστα διαστημάτων απομόνωσης: {}. 
Λίστα διαστημάτων προς επεξεργασία: {(0, 2), (2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

2η επανάληψη

VAG(x³ − 7x + 7, (0, 2)) 

1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = x³ − 7x² + 7x + 7

4 m ← (0 + 2) = 1

5 p(m) = 1

8          RETURN VAG(x³ − 7x + 7, (0, 1)) ∪ VAG(x³ − 7x + 7, (1, 2)
Λίστα διαστημάτων απομόνωσης: {}. 
Λίστα διαστημάτων προς επεξεργασία: {(0, 1), (1, 2), (2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

3η επανάληψη

VAG(x³ − 7x + 7, (0, 1)) 

1 var ← 0 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = x³ + 7x² + 14x + 7

2          RETURN ∅
Λίστα διαστημάτων απομόνωσης: {}. 
Λίστα διαστημάτων προς επεξεργασία: {(1, 2), (2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

4η επανάληψη

VAG(x³ − 7x + 7, (1, 2)) 

1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = x³ − 2x² − x + 1

4 m ← (1 + 2) = 

5 p(m) = −

8          RETURN VAG(x³ − 7x + 7, (1, )) ∪ VAG(x³ − 7x + 7, (, 2))
Λίστα διαστημάτων απομόνωσης: {}. 
Λίστα διαστημάτων προς επεξεργασία: {(1, ), (, 2), (2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

5η επανάληψη

VAG(x³ − 7x + 7, (1, )) 

1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του 2³(x + 1)³p() = x³ + 2x² − 8x − 8

3          RETURN (1, ) 
Λίστα απομονωμένων διαστημάτων: {(1, )}. 
Λίστα διαστημάτων προς επεξεργασία: {(, 2), (2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

6η επανάληψη

VAG(x³ − 7x + 7, (, 2)) 

1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του 2³(x + 1)³p() = 8x³ + 4x² − 4x − 1

3          RETURN (, 2) 
Λίστα απομονωμένων διαστημάτων: {(1, ), (, 2)}. 
Λίστα διαστημάτων προς επεξεργασία: {(2, 4)}. 
Αφαίρεσε το πρώτο διάστημα και προχώρα στην επεξεργασία του.

7η επανάληψη

VAG(x³ − 7x + 7, (2, 4)) 

1 var ← 0 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p() = 344x³ + 376x² + 104x + 8

2          RETURN ∅ 
Λίστα απομονωμένων διαστημάτων: {(1, ), (, 2)}. 
Λίστα διαστημάτων προς επεξεργασία: ∅.  
Τέλος.

Συμπέρασμα

Επομένως, οι δύο θετικές ρίζες του πολυωνύμου p(x) = x³ − 7x + 7 βρίσκονται μέσα στα διαστήματα απομόνωσης (1, ) και (, 2). Κάθε ρίζα μπορεί να προσεγγιστεί (για παράδειγμα) διχοτομώντας το αντίστοιχο διάστημα απομόνωσης έως ότου η διαφορά των καταληκτικών σημείων (endpoints) να είναι μικρότερη του 10⁻⁶. Με αυτή την προσέγγιση οι ρίζες του πολυωνύμου είναι οι ρ₁ = 1.3569 και ρ₂ = 1.69202.