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

Θεώρημα του Βίνσεντ
αγγλικά : Vincent's theorem
γαλλικά :
γερμανικά :

Στα μαθηματικά, το θεώρημα του Βίνσεντ — το οποίο πήρε το όνομά του από τον Αλεξάντρ Ζοζέφ Ιντούλφ Βενσάν — είναι ένα θεώρημα το οποίο απομονώνει τις πραγματικές ρίζες πολυωνύμων με ρητούς συντελεστές.

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

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

Έστω ότι c0, c1, c2, ... είναι μια πεπερασμένη ή άπειρη ακολουθία πραγματικών αριθμών. Υποθέστε ότι l < r και ότι ισχύουν οι ακόλουθες συνθήκες:

Αν r = l+1, τότε οι αριθμοί cl και cr έχουν αντίθετα πρόσημα.
Αν r ≥ l+2, τότε οι αριθμοί cl+1, ..., cr−1 είναι όλοι μηδέν και οι αριθμοί cl και cr έχουν αντίθετα πρόσημα.

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

Στη συνέχεια παρουσιάζονται δύο εκδοχές του θεωρήματος του Βίνσεντ: αυτή των συνεχών κλασμάτων από τον ίδιο τον Βίνσεντ[1][2] και αυτή της διχοτόμησης από τους Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi).[3][4]

Η εκδοχή των συνεχών κλασμάτων μπορεί να βρεθεί επίσης στο άρθρο της Βικιπαίδεια Θεώρημα του Μπουντάν.
Θεώρημα του Βίνσεντ: Η παραλλαγή των συνεχών κλασμάτων (1834 και 1836)

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

\( {\displaystyle x=a_{1}+{\frac {1}{x'}},\quad x'=a_{2}+{\frac {1}{x''}},\quad x''=a_{3}+{\frac {1}{x'''}},\ldots } \)

όπου \( a_{1},a_{2},a_{3},\ldots \) είναι οποιοδήποτε θετικοί αριθμοί μεγαλύτεροι ή ίσοι της μονάδας, τότε μετά από έναν αριθμό τέτοιων μετασχηματισμών, η προκύπτουσα μετασχηματισμένη εξίσωση έχει είτε μηδενικές εναλλαγές προσήμου είτε μία και μοναδική. Στην πρώτη περίπτωση δεν υπάρχει ρίζα ενώ στη δεύτερη περίπτωση υπάρχει μία πραγματική θετική ρίζα. Επιπλέον, η αντίστοιχη ρίζα της προτεινόμενης εξίσωσης προσεγγίζεται από το πεπερασμένο συνεχές κλάσμα:[1][2][5]

\( a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}\)

Επίσης, εάν μπορούν να βρεθούν άπειρα πολλοί αριθμοί \( a_{1},a_{2},a_{3},\ldots \) που ικανοποιούν αυτή την ιδιότητα, τότε η ρίζα αναπαριστάται από το αντίστοιχο (άπειρο) συνεχές κλάσμα.

Η παραπάνω διατύπωση αποτελεί μια πιστή μετάφραση του θεωρήματος που βρέθηκε στα πρωτότυπα άρθρα του Βίνσεντ.[1][2][5] Ωστόσο, οι παρακάτω παρατηρήσεις είναι απαραίτητες για την πλήρη κατανόηση του θεωρήματος:

Αν η \( f_{n}(x) \) δηλώνει το πολυώνυμο που λαμβάνεται μετά από n αντικαταστάσεις (και αφού αφαιρεθεί ο παρονομαστής), τότε υπάρχει N τέτοιο ώστε για κάθε \( n\geq N \) είτε η \( f_{n}(x) \) να μην εμφανίζει εναλλαγή προσήμου είτε να εμφανίζει μία ακριβώς. Στη δεύτερη περίπτωση, η \( f_{n}(x) \) έχει μία πραγματική θετική ρίζα για κάθε \( n\geq N \) .
Το συνεχές κλάσμα αναπαριστά μια θετική ρίζα της αρχικής εξίσωσης, αν και η αρχική εξίσωση μπορεί να έχει παραπάνω από μία ρίζες. Επιπλέον, υποθέτοντας ότι \( a_{1}\geq 1 \), μπορούμε να λάβουμε από την αρχική εξίσωση μόνο ρίζες που είναι μεγαλύτερες του ένα. Για να λάβουμε μία τυχαία θετική ρίζα πρέπει να θεωρήσουμε ότι \( a_{1}\geq 0 \).
Αρνητικές ρίζες λαμβάνονται αντικαθιστώντας το x με το −x, στην οποία περίπτωση οι αρνητικές ρίζες γίνονται θετικές.

Θεώρημα του Βίνσεντ: Η παραλλαγή της διχοτόμησης των Αλεσίνα και Γκαλούτσι (2000)

Έστω ότι p(x) ένα πραγματικό πολυώνυμο βαθμού deg(p) το οποίο έχει μόνο απλές ρίζες. Είναι δυνατό να καθορίσουμε μια θετική ποσότητα δ, τέτοια ώστε για κάθε ζεύγος θετικών πραγματικών αριθμών a, b με \( |b-a|<\delta \), κάθε μετασχηματισμένο πολυώνυμο της μορφής

\( f(x)=(1+x)^{{\deg(p)}}p\left({\frac {a+bx}{1+x}}\right) \) (1)

να έχει ακριβώς 0 ή 1 εναλλαγές προσήμου. Η δεύτερη περίπτωση είναι δυνατή εάν και μόνον εάν το πολυώνυμο p(x) έχει μία μοναδική ρίζα στο διάστημα (a, b).

Το "τεστ ύπαρξης ριζών στο a_b" των Αλεσίνα και Γκαλούτσι

Από την εξίσωση (1) λαμβάνουμε το ακόλουθο κριτήριο για να καθορίσουμε εάν ένα πολυώνυμο έχει ρίζες στο διάστημα (a, b):

Εφάρμοσε στο πολυώνυμο p(x) την αντικατάσταση

\( x\leftarrow {\frac {a+bx}{1+x}}\)

και υπολόγισε τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών του μετασχηματισμένου πολυωνύμου. Αυτός ο αριθμός δίνει ένα άνω όριο στον αριθμό των πραγματικών ριζών που έχει το πολυώνυμο p(x) μέσα στο ανοιχτό διάστημα (a, b). Πιο συγκεκριμένα, ο αριθμός ρab(p) των πραγματικών ριζών στο ανοιχτό διάστημα (a, b) — λαμβάνοντας υπ’ όψιν και τις πολλαπλότητες — του πολυωνύμου p(x) στο R[x], βαθμού deg(p), έχει σαν άνω όριο τον αριθμό των εναλλαγών προσήμου varab(p), όπου

\( var_{{ab}}(p)=var\left((1+x)^{{\deg(p)}}p\left({\frac {a+bx}{1+x}}\right)\right), \)
\( var_{{ab}}(p)=var_{{ba}}(p)\geq \rho _{{ab}}(p). \)

Όπως και στην περίπτωση του κανόνα προσήμων του Ντεκάρτ αν varab(p) = 0 τότε ρab(p) = 0 και αν varab(p) = 1 τότε ρab(p) = 1.

Μια ειδική περίπτωση του "τεστ ύπαρξης ριζών στο a_b" των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi) είναι το "τεστ ύπαρξης ριζών στο 0_1" του Μπουντάν (Budan).

Σκίτσο μιας απόδειξης

Μια λεπτομερής περιγραφή του θεωρήματος του Βίνσεντ, των επεκτάσεών του, της γεωμετρικής ερμηνείας των μετασχηματισμών που περιλαμβάνει και τρεις διαφορετικές αποδείξεις του μπορούν να βρεθούν στο έργο των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi).[3][4] Μια τέταρτη απόδειξη οφείλεται στον Οστρόφσκι (Ostrowski),[6] ο οποίος το 1950 (ξανά) ανακάλυψε μια ειδική περίπτωση ενός θεωρήματος που είχε διατυπωθεί πρώτη φορά το 1920-1923 από τον Ομπρέσκοφ (Obreschkoff)[7] (σελ. 81).

Για να αποδείξουν και τις δύο παραλλαγές του θεωρήματος του Βίνσεντ οι Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi) έδειξαν ότι μετά από μια σειρά μετασχηματισμών, οι οποίοι αναφέρονται στο θεώρημα, ένα πολυώνυμο με μια θετική ρίζα έχει τελικά μία εναλλαγή προσήμου. Για να το δείξουν αυτό, χρησιμοποιούν το ακόλουθο πόρισμα του θεωρήματος που αναφέρθηκε προηγουμένως (Ομπρέσκοφ, 1920-1923). Δηλαδή, το ακόλουθο πόρισμα δίνει τις απαραίτητες προϋποθέσεις κάτω από τις οποίες ένα πολυώνυμο με μια θετική ρίζα έχει ακριβώς μία εναλλαγή προσήμου στην ακολουθία των συντελεστών του. Δείτε επίσης την αντίστοιχη εικόνα.

Πόρισμα. (το θεώρημα του κώνου ή τομέα του Ομπρέσκοφ, 1920-1923[7] σελ. 81): Αν ένα πραγματικό πολυώνυμο έχει μία απλή ρίζα x0 και όλες οι άλλες (πιθανόν πολλαπλές) ρίζες βρίσκονται στον τομέα

\( S_{{{\sqrt {3}}}}=\left\{x=-\alpha +i\beta \ :\ |\beta |\leq {\sqrt {3}}|\alpha |,\alpha >0\right\} \)

τότε η ακολουθία των συντελεστών του έχει ακριβώς μία εναλλαγή προσήμου.

Ο \( S_{{{\sqrt {3}}}} \) τομέας του Ομπρέσκοφ (Obreschkoff) και το γνωστό του οκτω-μορφικό σχήμα (των κύκλων)

Θεωρήστε τώρα τον μετασχηματισμό Μέμπιους (Möbius)

\( M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in {\mathbb {Z}}_{{>0}} \)

και τους τρεις κύκλους της παραπάνω εικόνας. Υποθέστε ότι ac < bd.

Ο (κίτρινος) κύκλος

\( \left|x-{\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\right|={\tfrac {1}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right) \)

που η διάμετρός του βρίσκεται στον πραγματικό άξονα, με τελικά σημεία τα ac και bd, προβάλλεται από τον αντίστροφο μετασχηματισμό Μέμπιους (Möbius)

\( M^{{-1}}(x)={\frac {dx-b}{-cx+a}} \)

πάνω στο φανταστικό άξονα. Για παράδειγμα το σημείο

\( {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)+{\tfrac {i}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)\)

προβάλλεται πάνω στο σημείο −i dc. Τα εξωτερικά σημεία προβάλλονται επάνω στο ημιεπίπεδο με Re(x) < 0.

Οι δύο κύκλοι (φαίνονται μόνο τα μπλε μισοφέγγαρά τους) με κέντρο

\( {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\pm {\tfrac {i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right) \)

και ακτίνα

\( {\tfrac {1}{{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right) \)

προβάλλονται από τον αντίστροφο μετασχηματισμό Μέμπιους (Möbius)

\( M^{{-1}}(x)={\frac {dx-b}{-cx+a}} \)

επάνω στις γραμμές Im(x) = ±√3 Re(x). Για παράδειγμα το σημείο

\( {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)-{\tfrac {3i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right) \)

προβάλλεται στο σημείο

\( {\tfrac {-d}{2c}}\left(1-i{\sqrt {3}}\right). \)

Τα εξωτερικά σημεία (αυτά που είναι έξω από το οχτω-μορφικό σχήμα) προβάλλονται πάνω στον τομέα \( S_{{{\sqrt {3}}}} . \)

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

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

Και στα δύο άρθρα του[1][2], ο Βίνσεντ παρουσιάζει παραδείγματα που δείχνουν επακριβώς τη χρήση του θεωρήματός του για την απομόνωση των πραγματικών ριζών πολυωνύμων με συνεχή κλάσματα. Ωστόσο, η μέθοδος αυτή απαιτεί εκθετικό υπολογιστικό χρόνο, γεγονός το οποίο είχαν αντιληφθεί οι μαθηματικοί της εποχής εκείνης, όπως το αντιλήφθηκε επίσης και ο Ουσπένσκι (Uspensky)[8] (σελ. 136) έναν αιώνα αργότερα.

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

Η εκθετική φύση του αλγορίθμου του Βίνσεντ οφείλεται στον τρόπο με τον οποίο υπολογίζονται (στο θεώρημα του Βίνσεντ) τα μερικά πηλίκα ai. Δηλαδή, για να υπολογίσει το κάθε μερικό πηλίκο ai, που σημαίνει για να εντοπίσει την θέση των ριζών πάνω στον άξονα των x, ο Βίνσεντ χρησιμοποιεί το θεώρημα του Μπουντάν (Budan) ως ένα "τεστ μη ύπαρξης ριζών". Με άλλα λόγια, με σκοπό να βρει το ακέραιο μέρος μιας ρίζας, ο Βίνσεντ εφαρμόζει διαδοχικές αντικαταστάσεις της μορφής x ← x+1 και σταματά μόνο όταν τα πολυώνυμα p(x) και p(x+1) διαφέρουν ως προς τον αριθμό των εναλλαγών προσήμου στην ακολουθία των συντελεστών τους (δηλαδή όταν μειώνεται ο αριθμός των εναλλαγών προσήμου του p(x+1)).[1][2]

Δείτε το αντίστοιχο διάγραμμα όπου η ρίζα βρίσκεται στο διάστημα (5, 6). Εύκολα συνεπάγεται ότι, με τον τρόπο αυτό, εάν η ρίζα βρίσκεται μακριά από το αρχικό σημείο μηδέν, απαιτείται όλο και περισσότερος χρόνος για να βρεθεί το ακέραιο τμήμα της. Σε αυτό οφείλεται και η εκθετική φύση του αλγορίθμου του Βίνσεντ. Παρακάτω εξηγείται ο τρόπος με τον οποίο λύνεται το μειονέκτημα αυτό.
Εξαφάνιση του θεωρήματος του Βίνσεντ

Ο Βίνσεντ ήταν ο τελευταίος συγγραφέας του 19ου αιώνα που χρησιμοποίησε το θεώρημά του για την απομόνωση των πραγματικών ριζών ενός πολυωνύμου.

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

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

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

Τον 20ο αιώνα το θεώρημα του Βίνσεντ δεν εμφανίζεται σε κανένα βιβλίο θεωρίας εξισώσεων, με εξαίρεση τα βιβλία των Ουσπένσκι (Uspensky)[8] και Ομπρέσκοφ (Obreschkoff),[7] όπου στο βιβλίο του δεύτερου δίνεται απλά η διατύπωση του θεωρήματος.

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

Η απομόνωση των πραγματικών ριζών ενός πολυωνύμου είναι η διαδικασία της εύρεσης ανοιχτών ξένων (disjoint) διαστημάτων τέτοιων ώστε κάθε ένα να περιέχει ακριβώς μία πραγματική ρίζα και κάθε πραγματική ρίζα να περιέχεται σε κάποιο διάστημα. Σύμφωνα με τη γαλλική σχολή μαθηματικών του 19ου αιώνα, αυτό είναι το πρώτο βήμα για την εύρεση των πραγματικών ριζών, ενώ το δεύτερο βήμα είναι η προσέγγισή τους σε οποιοδήποτε βαθμό ακρίβειας. Επίσης, συγκεντρωνόμαστε μόνο στις θετικές ρίζες, καθώς η απομόνωση των αρνητικών ριζών ενός πολυωνύμου p(x) πραγματοποιείται με την αντικατάσταση του x με −x (x ← −x) και την επανάληψη της διαδικασίας.

Η παραλλαγή των συνεχών κλασμάτων του θεωρήματος του Βίνσεντ μπορεί να χρησιμοποιηθεί για την απομόνωση των πραγματικών ριζών ενός πολυωνύμου p(x) βαθμού deg(p). Για να το δούμε αυτό, αναπαραστήστε με τον μετασχηματισμό Μέμπιους (Möbius)

\( M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in {\mathbb {N}} \)

το συνεχές κλάσμα που οδηγεί στο μετασχηματισμένο πολυώνυμο

\( } f(x)=(cx+d)^{{\deg(p)}}p\left({\frac {ax+b}{cx+d}}\right) (2) \)

με μία εναλλαγή προσήμου στην ακολουθία των συντελεστών του. Τότε, η μοναδική θετική ρίζα του f(x) (στο διάστημα (0, ∞)) αντιστοιχεί σε εκείνη τη θετική ρίζα του p(x) που βρίσκεται στο ανοιχτό διάστημα με τελικά σημεία \( {\frac {b}{d}} \) και \( {\frac {a}{c}} \). Τα τελικά αυτά σημεία δεν είναι ταξινομημένα και αντιστοιχούν στο M(0) και M(∞) αντίστοιχα.

Επομένως, για την απομόνωση των θετικών ριζών ενός πολυωνύμου, αυτό που πρέπει να γίνει είναι ο υπολογισμός, για κάθε ρίζα, των μεταβλητών a, b, c, d του αντίστοιχου μετασχηματισμού Μέμπιους (Möbius)

\( M(x)={\frac {ax+b}{cx+d}}\)

που οδηγεί σε ένα μετασχηματισμένο πολυώνυμο όπως αυτό της εξίσωσης (2), με μία μόνο εναλλαγή προσήμου στην ακολουθία των συντελεστών του.

Σημαντική παρατήρηση: Οι μεταβλητές a, b, c, d του μετασχηματισμού Μέμπιους (Möbius)

\( M(x)={\frac {ax+b}{cx+d}}\)

(στο θεώρημα του Βίνσεντ) που οδηγούν σε ένα μετασχηματισμένο πολυώνυμο όπως αυτό της εξίσωσης (2) με μία εναλλαγή προσήμου στην ακολουθία των συντελεστών του μπορούν να υπολογιστούν:

Είτε με συνεχή κλάσματα, οδηγώντας στη μέθοδο συνεχών κλασμάτων VAS (Vincent–Akritas–Strzeboński)[9]
Είτε με διχοτόμηση, οδηγώντας στη μέθοδο διχοτόμησης VCA (Vincent-Collins-Akritas)[11]

Το δεύτερο μέρος (με την διχοτόμηση) της σημαντικής αυτής παρατήρησης εμφανίζεται ως ειδικό θεώρημα στα άρθρα των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi).[3][4]

Όλες οι μέθοδοι που περιγράφονται παρακάτω (δείτε το άρθρο Θεώρημα του Μπουντάν για μια ιστορική αναδρομή), απαιτούν αρχικά τον υπολογισμό (μία φορά) ενός άνω ορίου ub (ub = upper bound) στις τιμές των θετικών ριζών του πολυωνύμου όπου εφαρμόζονται. Εξαίρεση αποτελεί η μέθοδος VAS, όπου απαιτείται επιπλέον ο υπολογισμός κάτω ορίων lb (lb = lower bounds) σχεδόν σε κάθε κύκλο του κύριου βρόχου. Για τον υπολογισμό του κάτω ορίου lb ενός πολυωνύμου p(x) υπολογίζεται το άνω όριο ub του πολυωνύμου \( x^{{\deg(p)}}p\left({\frac {1}{x}}\right) \) και στη συνέχεια τίθεται l \( lb={\frac {1}{ub}} \).

Άριστα (άνω και κάτω) όρια στις τιμές των θετικών ριζών πολυωνύμων έχουν αναπτυχθεί από τους Ακρίτα, Σεμπόνσκι (Strzeboński) και Βίγκλα βασιζόμενοι σε προηγούμενη εργασία του Ντόρου Στεφανέσκου (Doru Stefanescu). Αυτά τα όρια περιγράφονται στην διδακτορική διατριβή του Π. Βίγκλα[12] και αλλού,[13] και έχουν ήδη ενσωματωθεί σε διάφορα συστήματα υπολογιστικής άλγεβρας όπως το Mathematica, Sage, SymPy, Xcas κ.α.

Και οι τρεις μέθοδοι που περιγράφονται παρακάτω ακολουθούν την εξαιρετική παρουσίαση του Φρανσουά Μπουλιέ (François Boulier),[14] σελ. 24.

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

Μόνο μία μέθοδος συνεχών κλασμάτων προέρχεται από το θεώρημα του Βίνσεντ. Όπως αναφέρθηκε παραπάνω, η ιστορία αυτής της μεθόδου ξεκίνησε τη δεκαετία του 1830, όταν ο Βίνσεντ παρουσίασε και στα δύο άρθρα του[1][2] πολλά παραδείγματα που δείχνουν επακριβώς πως χρησιμοποιείται το θεώρημά του για την απομόνωση των πραγματικών ριζών πολυωνύμων με συνεχή κλάσματα. Ωστόσο, η προκύπτουσα μέθοδος είχε εκθετικό χρόνο εκτέλεσης. Παρακάτω ακολουθεί μία ανάλυση για το πώς εξελίχθηκε η μέθοδος αυτή.
Vincent-Akritas-Strzeboński (VAS, 2005)

Πρόκειται για την δεύτερη κατά σειρά μέθοδο (μετά την μέθοδο VCA) που αναπτύχθηκε με σκοπό να αντιμετωπίσει την εκθετική συμπεριφορά της μεθόδου του Βίνσεντ.

Η μέθοδος VAS των συνεχών κλασμάτων αποτελεί μία απ’ ευθείας υλοποίηση του θεωρήματος του Βίνσεντ. Αρχικά παρουσιάστηκε από τον ίδιο τον Βίνσεντ στα άρθρα του το 1834[1] και 1836[2] στην εκθετική της μορφή. Συγκεκριμένα, ο Βίνσεντ υπολόγιζε κάθε μερικό πηλίκο ai με μια σειρά από μοναδιαίων αυξήσεων ai ← ai + 1, οι οποίες είναι ισοδύναμες με αντικαταστάσεις της μορφής x ← x + 1.

Η μέθοδος του Βίνσεντ μετατράπηκε σε μέθοδο πολυωνυμικής πολυπλοκότητας από τον Α. Ακρίτα το 1978, ο οποίος υπολόγισε κάθε μερικό πηλίκο ai ως ένα κάτω όριο, lb, στις τιμές των θετικών ριζών ενός πολυωνύμου. Αυτό ονομάστηκε το ιδανικό θετικό κάτω όριο που υπολογίζει το ακέραιο μέρος της μικρότερης θετικής ρίζας (βλέπε την αντίστοιχη εικόνα). Δηλαδή, τώρα θέτουμε ai ← lb ή, ισοδύναμα, εφαρμόζουμε την αντικατάσταση x ← x + lb, για την οποία απαιτείται περίπου ο ίδιος χρόνος με την αντικατάσταση x ← x + 1.

Η αναζήτηση μιας ρίζας με τη μέθοδο VAS. Το ιδανικό κάτω όριο είναι 5, οπότε x ← x + 5.

Τέλος, επειδή το ιδανικό θετικό κάτω όριο μιας ρίζας δεν υπάρχει, ο Σεμπόνσκι (Strzeboński)[15] εισήγαγε το 2005 την αντικατάσταση \( x\leftarrow lb_{{computed}}*x \) , οποτεδήποτε \( lb_{{computed}}>16 \). Γενικότερα, ισχύει \( lb>lb_{{computed}} \) και η τιμή 16 καθορίστηκε μέσω πειραματικών αποτελεσμάτων. Επιπλέον, έχει αποδειχτεί[15] και ανεξάρτητα επιβεβαιωθεί ότι η μέθοδος (συνεχών κλασμάτων) VAS είναι ταχύτερη ακόμα και από την πιο γρήγορη υλοποίηση της μεθόδου διχοτόμησης VCA.[16][17] Συγκεκριμένα, για τα πολυώνυμα Mignotte υψηλού βαθμού η εκτέλεση της μεθόδου VAS είναι περίπου 50,000 φορές ταχύτερη από την ταχύτερη εκτέλεση της μεθόδου VCA.

Το 2007 ο Σάρμα (Sharma)[18] στην διδακτορική του διατριβή απέδειξε ότι ακόμα και αν αφαιρεθεί η υπόθεση του ιδανικού κάτω ορίου η μέθοδος VAS παραμένει πολυωνυμική ως προς την πολυπλοκότητά της.

Ο αλγόριθμος VAS αποτελεί τον προεπιλεγμένο αλγόριθμο απομόνωσης ριζών στο Mathematica, Sage, SymPy, Xcas.

Για μια σύγκριση της μεθόδου του Στουρμ (Sturm) και της μεθόδου VAS χρησιμοποιείστε τις συναρτήσεις realroot( poly ) και time( realroot( poly ) ) του Xcas. Προεπιλεγμένα, για την απομόνωση των πραγματικών ριζών ενός πολυωνύμου poly η realroot χρησιμοποιεί τη μέθοδο VAS. Για να χρησιμοποιήσετε τη μέθοδο του Στουρμ (Sturm) γράψτε realroot( sturm, poly ). Δείτε επίσης τους εξωτερικούς συνδέσμους για μια εφαρμογή του Α. Μπερκάκη για συσκευές Android που κάνει το ίδιο πράγμα.

Παρακάτω παρουσιάζεται ο αλγόριθμος VAS(p, M), όπου για λόγους απλότητας δεν περιλαμβάνεται η συνεισφορά του Σεμπόνσκι (Strzeboński):

Έστω ότι p(x) είναι ένα πολυώνυμο βαθμού deg(p) τέτοιο ώστε p(0) ≠ 0. Για την απομόνωση των θετικών ριζών του, αντιστοίχισε το πολυώνυμο p(x) με τον μετασχηματισμό Μέμπιους (Möbius) M(x) = x και επανέλαβε τα ακόλουθα βήματα όσο υπάρχουν ζεύγη {p(x), M(x)} προς επεξεργασία.
Χρησιμοποίησε τον κανόνα προσήμων του Ντεκάρτ στο πολυώνυμο p(x) για τον υπολογισμό, εάν είναι δυνατόν, του αριθμού των ριζών του πολυωνύμου μέσα στο διάστημα (0, ∞), χρησιμοποιώντας τον αριθμό (var) των εναλλαγών προσήμου στην ακολουθία των συντελεστών του. Αν δεν υπάρχουν ρίζες επέστρεψε το κενό σύνολο, ∅ ενώ αν υπάρχει μία ρίζα επέστρεψε το διάστημα (a, b), όπου a = min(M(0), M(∞)) και b = max(M(0), M(∞)). Αν b = ∞ τότε θέσε b = ub, όπου ub είναι ένα άνω όριο στις τιμές των θετικών ριζών του p(x).[12][13]
Αν υπάρχουν δύο ή περισσότερες εναλλαγές προσήμου από τον κανόνα προσήμων του Ντεκάρτ συνεπάγεται ότι ίσως υπάρχουν 0, 1, ή περισσότερες πραγματικές ρίζες μέσα στο διάστημα (0, ∞). Στην περίπτωση αυτή εξέτασε ξεχωριστά τις ρίζες του πολυωνύμου p(x) που υπάρχουν μέσα στο διάστημα (0, 1) από αυτές που υπάρχουν μέσα στο διάστημα (1, ∞). Ο αριθμός 1 εξετάζεται ξεχωριστά.
Για να υπάρχουν με βεβαιότητα ρίζες στο διάστημα (0, 1), χρησιμοποίησε το ιδανικό κάτω όριο ''lb''. Ουσιαστικά αυτό είναι το ακέραιο μέρος της μικρότερης θετικής ρίζας και υπολογίζεται με τη βοήθεια του κάτω ορίου,[12][13] \( lb_{{computed}} \), για τις τιμές των θετικών ριζών του πολυωνύμου p(x). Αν \( lb_{{computed}}>1 \), τότε στο p(x) και M(x) εκτελείται η αντικατάσταση \( x\leftarrow x+lb_{{computed}} \), ενώ αν \( lb_{{computed}}\leq 1 \) για την εύρεση του ακέραιου μέρους των ριζών γίνονται μία ή περισσότερες αντικαταστάσεις της μορφής x ← x+1.
Για τον υπολογισμό των ριζών μέσα στο διάστημα (0, 1), εκτέλεσε στο p(x) και M(x) την αντικατάσταση \( x\leftarrow {\frac {1}{1+x}} \) και επεξεργάσου το ζευγάρι

\( \left\{(1+x)^{{\deg(p)}}p\left({\tfrac {1}{1+x}}\right),M({\tfrac {1}{1+x}})\right\},\)

ενώ για τον υπολογισμό των ριζών στο διάστημα (1, ∞) εκτέλεσε στο p(x) και M(x) την αντικατάσταση x ← x + 1 και επεξεργάσου το ζευγάρι {p(1 + x), M(1 + x)}. Αν διαπιστωθεί ότι ο αριθμός 1 είναι μια ρίζα του πολυωνύμου p(x), τότε, στην περίπτωση αυτή, M(1) είναι μία ρίζα του αρχικού πολυωνύμου και το διάστημα απομόνωσης ανάγεται σε ένα σημείο.

Παρακάτω βλέπουμε μια αναδρομική παρουσίαση του αλγορίθμου VAS(p, M).

VAS(p, M):

Είσοδος: Ένα πολυώνυμο μιας μεταβλητής χωρίς πολλαπλές ρίζες \( p(x)\in {\mathbb {Z}}[x],p(0)\neq 0, βαθμού deg(p) \) και ο μετασχηματισμός Μέμπιους (Möbius)

\( M(x)={\frac {ax+b}{cx+d}}=x,\qquad a,b,c,d\in {\mathbb {N}}.\)

Έξοδος: Μια λίστα με τα διαστήματα απομόνωσης των θετικών ριζών του p(x).

1 var ← ο αριθμός των εναλλαγών προσήμου του p(x) // κανόνας προσήμων του Ντεκάρτ; 2 if var = 0 then RETURN ∅; 3 if var = 1 then RETURN {(a, b)} // a = min(M(0), M(∞)), b = max(M(0), M(∞)), αλλά αν b = ∞ τότε θέσε b = ub, όπου ub ένα άνω όριο στις τιμές των θετικών ριζών του p(x); 4 lb ← το ιδανικό κάτω όριο των θετικών ριζών του p(x); 5 if lb ≥ 1 then p ← p(x + lb), M ← M(x + lb); 6 p₀₁ ← (x + 1)^deg(p) p(1x + 1), M₀₁ ← M(1x + 1) // Ψάξε για πραγματικές ρίζες στο διάστημα (0, 1); 7 m ← M(1) // Είναι ρίζα ο αριθμός 1?; 8 p_1∞ ← p(x + 1), M_1∞ ← M(x + 1) // Ψάξε για πραγματικές ρίζες στο διάστημα (1, ∞); 9 if p(1) ≠ 0 then 10 RETURN VAS(p₀₁, M₀₁) ∪ VAS(p_1∞, M_1∞) 11 else 12 RETURN VAS(p₀₁, M₀₁) ∪ {[m, m]} ∪ VAS(p_1∞, M_1∞) 13 end

Παρατηρήσεις

Η συνεισφορά του Σεμπόνσκι (Strzeboński) δεν περιλαμβάνεται για λόγους απλότητας.
Στον παραπάνω αλγόριθμο κάθε πολυώνυμο σχετίζεται με έναν μετασχηματισμό Μέμπιους (Möbius) M(x).
Στη γραμμή 1 εφαρμόζεται ο κανόνας προσήμων του Ντεκάρτ.
Αν διαγραφούν οι γραμμές 4 και 5 από τον VAS(p, M) τότε καταλήγουμε στον αρχικό εκθετικό αλγόριθμο του Βίνσεντ.
Κάθε αντικατάσταση που εφαρμόζεται στο πολυώνυμο p(x) εφαρμόζεται επίσης στον αντίστοιχο μετασχηματισμό Μέμπιους (Möbius) M(x) (γραμμές 5, 6 και 8).
Τα διαστήματα απομόνωσης υπολογίζονται από τον μετασχηματισμό Μέμπιους (Möbius) στη γραμμή 3, με εξαίρεση τις ακέραιες ρίζες οι οποίες υπολογίζονται στη γραμμή 7 (και 12).

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

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

VAS(x³ − 7x + 7, x) 1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του πολυωνύμου p(x) = x³ − 7x + 7 4 lb ← 1 // το ιδανικό κάτω όριο — βρίσκεται χρησιμοποιώντας lb_computed και αντικαταστάσεις x ← x + 1 5 p ← x³ + 3x² − 4x + 1, M ← x + 1 6 p₀₁ ← x³ − x² − 2x + 1, M₀₁ ← x + 2x + 1 7 m ← 1 8 p_1∞ ← x³ + 6x² + 5x + 1, M_1∞ ← x + 2 10 RETURN VAS(x³ − x² − 2x + 1, x + 2x + 1) ∪ VAS(x³ + 6x² + 5x + 1, x + 2)

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, M} προς επεξεργασία:

\( \left\{\left\{x^{3}-x^{2}-2x+1,{\tfrac {x+2}{x+1}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}. \)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
2η επανάληψη

VAS(x³ − x² − 2x + 1, x + 2x + 1) 1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του πολυωνύμου p(x) = x³ − x² − 2x + 1 4 lb ← 0 // το ιδανικό κάτω όριο — βρίσκεται χρησιμοποιώντας lb_computed και αντικαταστάσεις x ← x + 1 6 p₀₁ ← x³ + x² − 2x − 1, M₀₁ ← 2x + 3x + 1 7 m ← 32 8 p_1∞ ← x³ + 2x² − x − 1, M_1∞ ← x + 3x + 2 10 RETURN VAS(x³ + x² − 2x − 1, 2x + 3x + 2) ∪ VAS(x³ + 2x² − x − 1, x + 3x + 2)

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, M} προς επεξεργασία:

\( \left\{\left\{x^{3}+x^{2}-2x-1,{\tfrac {2x+3}{x+2}}\right\},\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}. \)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
3η επανάληψη

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

Λίστα διαστημάτων απομόνωσης: {(32, 2)}.

Λίστα ζευγαριών {p, M} προς επεξεργασία:

\( \left\{\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}. \)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
4η επανάληψη

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

Λίστα διαστημάτων απομόνωσης: {(1, 32), (32, 2)}.

Λίστα ζευγαριών {p, M} προς επεξεργασία:

\( \left\{\left\{x^{3}+6x^{2}+5x+1,x+2\right\}\right\}. \)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
5η επανάληψη

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

Λίστα διαστημάτων απομόνωσης: {(1, 32), (32, 2)}.

Λίστα ζευγαριών {p, M} προς επεξεργασία: ∅.

Τέλος.
Συμπέρασμα

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

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

Υπάρχουν διάφορες μέθοδοι διχοτόμησης που προέρχονται από το θεώρημα του Βίνσεντ.[19] Εδώ παρουσιάζονται οι δύο πιο σημαντικές από αυτές, η μέθοδος Vincent-Collins-Akritas (VCA) και η μέθοδος Vincent-Alesina-Galuzzi (VAG).

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

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

Vincent-Collins-Akritas (VCA, 1976)

Πρόκειται για την πρώτη μέθοδο που αναπτύχθηκε με σκοπό να ξεπεράσει την εκθετική φύση της αρχικής προσέγγισης του Βίνσεντ και παρουσιάζει μια αρκετά ενδιαφέρουσα ιστορία όσον αφορά το όνομά της. Η μέθοδος αυτή, η οποία απομονώνει τις πραγματικές ρίζες χρησιμοποιώντας τον κανόνα προσήμων του Ντεκάρτ και το θεώρημα του Βίνσεντ, αρχικά ονομάστηκε ως τροποποιημένος αλγόριθμος του Ουσπένσκι (Uspensky) από τους δημιουργούς της Κόλινς (Collins) και Ακρίτα.[11] Αφού πέρασε από τα ονόματα "μέθοδος των Collins-Akritas" και "μέθοδος του Ντεκάρτ" (κάτι που δημιουργεί σύγχυση δεδομένου του άρθρου του Φουριέ[20]), έλαβε τελικά το σημερινό της όνομα από τον Φρανσουά Μπουλιέ (François Boulier),[14] (σελ. 24), του Πανεπιστημίου της Λιλ (Lille), ο οποίος βασίστηκε στο γεγονός ότι δεν υπάρχει ούτε "μέθοδος του Ουσπένσκι (Uspensky)"[21] ούτε "μέθοδος του Ντεκάρτ".[22] Η καλύτερη υλοποίηση της μεθόδου αυτής πραγματοποιήθηκε από τους Ρουλιέ (Roullier) και Ζίμερμαν (Zimmerman)[16] και μέχρι σήμερα αποτελεί την ταχύτερη μέθοδο διχοτόμησης. Στη χειρότερη περίπτωση έχει την ίδια πολυπλοκότητα με τον αλγόριθμο του Στουρμ (Sturm), αλλά σχεδόν πάντα είναι αρκετά πιο γρήγορη. Τέλος, η μέθοδος VCA έχει συμπεριληφθεί στον πακέτο RootFinding του συστήματος υπολογιστικής άλγεβρας Maple.

Παρακάτω παρουσιάζεται ο αλγόριθμος VCA(p, (a, b)):

Δεδομένου ενός πολυωνύμου porig(x) βαθμού deg(p), τέτοιο ώστε porig(0) ≠ 0, του οποίου οι θετικές ρίζες πρέπει να απομονωθούν, αρχικά υπολόγισε ένα άνω όριο,[12][13] ub στις τιμές αυτών των θετικών ριζών και θέσε p(x) = porig(ub * x) και (a, b) = (0, ub). Οι θετικές ρίζες του p(x) βρίσκονται στο διάστημα (0, 1). Επίσης, υπάρχει μία αμφιμονοσήμαντη αντιστοιχία (ένα προς ένα και επί) μεταξύ αυτών και των ριζών του porig(x), οι οποίες βρίσκονται στο διάστημα (a, b) = (0, ub) (βλέπε την αντίστοιχη εικόνα). Αυτή η αμφιμονοσήμαντη αντιστοιχία εκφράζεται με την εξίσωση α(a,b) = a +α(0,1)(b − a). Παρομοίως, υπάρχει μία αμφιμονοσήμαντη αντιστοιχία μεταξύ των διαστημάτων (0, 1) και (0, ub).

Αμφιμονοσήμαντη αντιστοιχία μεταξύ των ριζών του porig(x) και p(x).

Επανέλαβε τα επόμενα βήματα όσο υπάρχουν ζεύγη {p(x), (a, b)} προς επεξεργασία.
Χρησιμοποίησε το "τεστ ύπαρξης ριζών στο 0_1" του Μπουντάν (Budan) στο p(x) ώστε να υπολογιστεί, χρησιμοποιώντας τον αριθμό (var) των εναλλαγών προσήμου στην ακολουθία των συντελεστών του, ο αριθμός των ριζών του πολυωνύμου στο διάστημα (0, 1). Αν δεν υπάρχουν ρίζες επέστρεψε το κενό σύνολο, ∅ ενώ εάν υπάρχει μία ρίζα επέστρεψε το διάστημα (a, b).
Αν υπάρχουν δύο ή περισσότερες εναλλαγές προσήμου, το "τεστ ύπαρξης ριζών στο 0_1" του Μπουντάν (Budan) υποδεικνύει ότι ίσως υπάρχουν 0, 1, 2 ή περισσότερες πραγματικές ρίζες μέσα στο διάστημα (0, 1). Στην περίπτωση αυτή κόψε το διάστημα στη μέση και θεώρησε ξεχωριστά τις ρίζες του p(x) μέσα στο διάστημα (0, 12), το οποίο αντιστοιχεί στις ρίζες του porig(x) μέσα στο διάστημα (a, 12(a + b)), από αυτές μέσα στο διάστημα (12, 1), το οποίο αντιστοιχεί στις ρίζες του porig(x) μέσα στο διάστημα (12(a + b), b). Επεξεργάσου αντίστοιχα, δηλαδή, τα ζεύγη

\( \left\{2^{{\deg(p)}}p({\tfrac {x}{2}}),(a,{\tfrac {1}{2}}(a+b))\right\},\quad \left\{2^{{\deg(p)}}p({\tfrac {1}{2}}(x+1)),({\tfrac {1}{2}}(a+b),b)\right\} \)

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

Αμφιμονοσήμαντη αντιστοιχία μεταξύ των ριζών του p(x) και αυτών του p(x2) και p(x + 12).

Παρακάτω βλεπουμε μια αναδρομική παρουσίαση του αλγορίθμου VCA(p, (a, b)).

VCA(p, (a, b))

Είσοδος: Ένα πολυώνυμο μιας μεταβλητής χωρίς πολλαπλές ρίζες p(ub * x) ∈ Z[x], p(0) ≠ 0, βαθμού deg(p) και το ανοιχτό διάστημα (a, b) = (0, ub), όπου ub είναι ένα άνω όριο στις τιμές των θετικών ριζών του p(x). (Οι θετικές ρίζες του p(ub * x) είναι όλες μέσα στο ανοιχτό διάστημα (0, 1)).
Έξοδος: Μια λίστα με τα διαστήματα απομόνωσης των θετικών ριζών του p(x)

1 var ← ο αριθμός των εναλλαγών προσήμου του (x + 1)^deg(p)p(1x + 1) // "0_1 εξέταση ριζών" του Μπουντάν; 2 if var = 0 then RETURN ∅; 3 if var = 1 then RETURN {(a, b)}; 4 p₀₁₂ ← 2^deg(p)p(x2) // Ψάξε για πραγματικές ρίζες στο διάστημα (0, 12); 5 m ← 12(a + b) // Είναι ρίζα ο αριθμός 12? 6 p₁₂₁ ← 2^deg(p)p(x + 12) // Ψάξε για πραγματικές ρίζες στο διάστημα (12, 1); 7 if p(12) ≠ 0 then 8 RETURN VCA (p₀₁₂, (a, m)) ∪ VCA (p₁₂₁, (m, b)) 9 else 10 RETURN VCA (p₀₁₂, (a, m)) ∪ {[m, m]} ∪ VCA (p₁₂₁, (m, b)) 11 end

Παρατηρήσεις

Στον παραπάνω αλγόριθμο κάθε πολυώνυμο σχετίζεται με ένα διάστημα (a, b). Επίσης, όπως έχει αποδειχθεί,[22] (σελ. 11), κάθε πολυώνυμο μπορεί να αντιστοιχιστεί με έναν μετασχηματισμό Μέμπιους (Möbius), στην οποία περίπτωση η μέθοδος VCA μοιάζει περισσότερο με τη μέθοδο VAS.
Στη γραμμή 1 εφαρμόζεται το "τεστ ύπαξης ριζών στο 0_1" του Μπουντάν (Budan).

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

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

1η επανάληψη

1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(1x + 1) = 7x³ − 7x² − 35x + 43 4 p₀₁₂ ← 64x³ − 112x + 56 5 m ← 2 6 p₁₂₁ ← 64x³ + 192x² + 80x + 8 7 p(12) = 1 8 RETURN VCA(64x³ − 112x + 56, (0, 2)) ∪ VCA(64x³ + 192x² + 80x + 8, (2, 4))

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}-112x+56,(0,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.\)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
2η επανάληψη

VCA(64x³ − 112x + 56, (0, 2)) 1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(1x + 1) = 56x³ + 56x² − 56x + 8 4 p₀₁₂ ← 64x³ − 448x + 448 5 m ← 1 6 p₁₂₁ ← 64x³ + 192x² − 256x + 64 7 p(12) = 8 8 RETURN VCA(64x³ − 448x + 448, (0, 1)) ∪ VCA(64x³ + 192x² − 256x + 64, (1, 2))

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}-448x+448,(0,1)\right\},\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.\)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
3η επανάληψη

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

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.\)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
4η επανάληψη VCA(64x3 + 192x2 − 256x + 64, (1, 2))
1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)3p(1x + 1) = 64x3 − 64x2 − 128x + 64
4 p012 ← 64x3 + 384x2 − 1024x + 512
5 m ← 32
6 p121 ← 64x3 + 576x2 − 64x + 64
7 p(12) = −8
8 RETURN VCA(64x3 + 384x2 − 1024x + 512, (1, 32)) ∪ VCA(64x3 + 576x2 − 64x −

VCA(64x³ + 192x² − 256x + 64, (1, 2)) 1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(1x + 1) = 64x³ − 64x² − 128x + 64 4 p₀₁₂ ← 64x³ + 384x² − 1024x + 512 5 m ← 32 6 p₁₂₁ ← 64x³ + 576x² − 64x + 64 7 p(12) = −8 8 RETURN VCA(64x³ + 384x² − 1024x + 512, (1, 32)) ∪ VCA(64x³ + 576x² − 64x − 64, (32, 2))

))

Λίστα διαστημάτων απομόνωσης: { }.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}+384x^{2}-1024x+512,\left(1,{\tfrac {3}{2}}\right)\right\},\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.\)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
5η επανάληψη

VCA(64x³ + 384x² − 1024x + 512, (1, 32)) 1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(1x + 1) = 512x³ + 512x² − 128x − 64 3 RETURN {(1, 32)}

Λίστα διαστημάτων απομόνωσης: {(1, 32)}.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.

6η επανάληψη

VCA(64x³ + 576x² − 64x − 64, (32, 2)) 1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(1x + 1) = −64x³ − 256x² + 256x + 512 3 RETURN {(32, 2)}

Λίστα διαστημάτων απομόνωσης: {(1, 32), (32, 2)}.

Λίστα ζευγαριών {p, I} προς επεξεργασία:

\( \left\{\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.\)

Αφαίρεσε το πρώτο ζευγάρι και προχώρα στην επεξεργασία του.
7η επανάληψη

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

Λίστα διαστημάτων απομόνωσης: {(1, 32), (32, 2)}.

Λίστα ζευγαριών {p, I} προς επεξεργασία: ∅.

Τέλος.
Συμπέρασμα

Vincent-Alesina-Galuzzi (VAG, 2000)

Πρόκειται για την πιο πρόσφατη και πιο απλή μέθοδο απομόνωσης πραγματικών ριζών που προέκυψε από το θεώρημα του Βίνσεντ.

Παρακάτω παρουσιάζεται ο αλγόριθμος VAG(p, (a, b)):

Δεδομένου ενός πολυωνύμου p(x) βαθμού deg(p), τέτοιο ώστε p(0) ≠ 0, του οποίου οι θετικές ρίζες πρέπει να απομονωθούν, αρχικά υπολόγισε ένα άνω όριο,^[12]^[13] ub στις τιμές αυτών των θετικών ριζών και θέσε (a, b) = (0, ub). Οι θετικές ρίζες του p(x) βρίσκονται στο διάστημα (a, b).
Επανέλαβε τα ακόλουθα βήματα όσο υπάρχουν διαστήματα (a, b) προς επεξεργασία. Στην περίπτωση αυτή το πολυώνυμο p(x) παραμένει ίδιο.
Χρησιμοποίησε το "τεστ ύπαρξης ριζών στο a_b" των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi) στο p(x) ώστε να υπολογιστεί, χρησιμοποιώντας τον αριθμό (var) των εναλλαγών προσήμου στην ακολουθία των συντελεστών του, ο αριθμός των ριζών του πολυωνύμου στο διάστημα (a, b). Αν δεν υπάρχουν ρίζες επέστρεψε το κενό σύνολο, ∅ ενώ αν υπάρχει μία ρίζα επέστρεψε το διάστημα (a, b).
Αν υπάρχουν δύο ή περισσότερες εναλλαγές προσήμου, το "τεστ ύπαρξης ριζών στο a_b" των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi) υποδεικνύει ότι ίσως υπάρχουν 0, 1, 2 ή περισσότερες πραγματικές ρίζες μέσα στο διάστημα (a, b). Στην περίπτωση αυτή κόψε το διάστημα στη μέση και θεώρησε ξεχωριστά τις ρίζες του p(x) μέσα στο διάστημα (a, 12(a + b)) από αυτές μέσα στο διάστημα (12(a + b), b). Επεξεργάσου αντίστοιχα, δηλαδή, τα διαστήματα (a, 12(a + b)) και (12(a + b), b). Αν διαπιστωθεί ότι ο αριθμός 12(a + b) είναι μια ρίζα του p(x), τότε, στην οποία περίπτωση, το διάστημα απομόνωσης ανάγεται σε ένα σημείο.

Παρακάτω βλέπουμε μια αναδρομική παρουσίαση του αλγορίθμου VAG(p, (a, b)).

VAG(p, (a, b))

Είσοδος: Ένα πολυώνυμο μιας μεταβλητής χωρίς πολλαπλές ρίζες p(x) ∈ Z[x], p(0) ≠ 0, βαθμού deg(p) και το ανοιχτό διάστημα (a, b) = (0, ub), όπου ub είναι ένα άνω όριο στις τιμές των θετικών ριζών του p(x).
Έξοδος: Μια λίστα με τα διαστήματα απομόνωσης των θετικών ριζών του p(x).

1 var ← ο αριθμός των εναλλαγών προσήμου του (x + 1)^deg(p) p(a + bx1 + x) // το "τεστ ύπαρξης ριζών στο a_b" των Αλεσίνα και Γκαλούτσι; 2 if var = 0 then RETURN ∅; 3 if var = 1 then RETURN {(a, b)}; 4 m ← 12(a + b) // Διαίρεσε το διάστημα (a, b) σε δύο ίσα μέρη; 5 if p(m) ≠ 0 then 6 RETURN VAG(p, (a, m)) ∪ VAG(p, (m, b)) 7 else 8 RETURN VAG(p, (a, m)) ∪ {[m, m]} ∪ VAG(p, (m, b)) 9 end

Παρατηρήσεις

Σε σύγκριση με τη μέθοδο VCA ο παραπάνω αλγόριθμος είναι εξαιρετικά απλός. Αντίθετα, η μέθοδος VAG χρησιμοποιεί το χρονικά απαιτητική "τεστ ύπαρξης ριζών στο a_b". Το γεγονός αυτό την κάνει πολύ πιο αργή από τη μέθοδο VCA.[19]
Όπως υπέδειξαν οι Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi),[4] (σελ. 189), υπάρχει μια διαφορά σε αυτόν τον αλγόριθμο σε σχέση με τον αλγόριθμο του Ντονάτο Σαέλι (Donato Saeli). Ο Σαέλι πρότεινε να χρησιμοποιηθεί ο ενδιάμεσος (median) των καταληκτικών σημείων (endpoints) σε σύγκριση με το μέσο σημείο 12(a + b) των Αλεσίνα (Alesina) και Γκαλούτσι (Galuzzi). Ωστόσο, έχει αποδειχτεί[19] ότι χρησιμοποιώντας τον ενδιάμεσο των καταληκτικών σημείων η διαδικασία γίνεται γενικότερα πολύ πιο αργή σε σχέση με την εκδοχή του "μέσου σημείου".

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

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

1η επανάληψη

1 var ← 2 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του (x + 1)³p(4xx + 1) = 43x³ − 35x² − 7x + 7 4 m ← 12(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)}.