Θεώρημα του Βίνσεντ: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε

Ενδογραμμικά

Έκδοση από την 06:33, 18 Δεκεμβρίου 2014

Στα μαθηματικά, το θεώρημα του Βίνσεντ — το οποίο πήρε το όνομά του από τον Alexandre Joseph Hidulphe Vincent — είναι ένα θεώρημα το οποίο απομονώνει τις πραγματικές ρίζες πολυωνύμων με λογικούς συντελεστές.

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

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

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

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

Έτσι ορίζεται η εναλλαγή προσήμου μεταξύ των αριθμών c_l και c_r.

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

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

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

Θεώρημα (συνεχών κλασμάτων) του Βίνσεντ (1834 και 1836)

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

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), οριοθετείται από τον αριθμό των εναλλαγών προσήμου var_ab(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).

Όπως και στην περίπτωση του κανόνα προσήμων του Ντεκάρτ αν var_ab(p) = 0 τότε ρ_ab(p) = 0 και αν var_ab(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): Αν ένα πραγματικό πολυώνυμο έχει μία απλή ρίζα

x 0

και όλες οι άλλες (πιθανόν πολλαπλές) ρίζες βρίσκονται στον τομέα

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

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

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

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

και τους τρεις κύκλους της παραπάνω εικόνας. Θεωρείστε ότι $a / c < b / d .$

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

\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)

που η διάμετρός του βρίσκεται στον πραγματικό άξονα, με τελικά σημεία τα

a / c

και

b / d,

σχεδιάζεται από τον αντίστροφο του Μέμπιους (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 d / c .

Τα εξωτερικά σημεία σχεδιάζονται επάνω στο ημιεπίπεδο, όπου

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) = \pm \sqrt 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}}

τομέα.

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

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

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

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

Η εκθετική φύση του αλγορίθμου του Βίνσεντ οφείλεται στον τρόπο με τον οποίο υπολογίζονται (στο θεώρημα του Βίνσεντ) τα επιμέρους πηλίκα a_i. Αυτό συμβαίνει διότι, για να υπολογιστεί το κάθε επιμέρους πηλίκο a_i, άρα να εντοπιστεί που εμφανίζονται οι ρίζες στον άξονα των 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).

Μέθοδοι απομόνωσης πραγματικών ριζών που προέρχονται από το θεώρημα του Βίνσεντ

Η απομόνωση των πραγματικών ριζών ενός πολυωνύμου είναι η διαδικασία της εύρεσης ανοιχτών ασυνεχών διαστημάτων τέτοιων ώστε κάθε ένα να περιέχει ακριβώς μία πραγματική ρίζα και κάθε πραγματική ρίζα να περιέχεται σε κάποιο διάστημα. Σύμφωνα με τη γαλλική σχολή μαθηματικών του 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 = upper bounds) σχεδόν σε κάθε κύκλο του κύριου βρόγχου. Για τον υπολογισμό του κάτω ορίου lb ενός πολυωνύμου p(x) υπολογίζεται το άνω όριο ub του πολυωνύμου $x^{\deg(p)}p\left({\frac {1}{x}}\right)$ και στη συνέχεια τίθεται $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] στην εκθετική του μορφή. Συγκεκριμένα, ο Βίνσεντ υπολόγισε κάθε επιμέρους πηλίκο a_i με μια σειρά από αυξήσεις a_i ← a_i + 1, οι οποίες είναι ισοδύναμες με αντικαταστάσεις της μορφής x ← x + 1.

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

Τέλος, επειδή το ιδανικό θετικό κάτω όριο μιας ρίζας δεν υπάρχει, ο Σεμπόνσκι (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, ∞). Στην περίπτωση αυτή εξέτασε ξεχωριστά τις ρίζες του πολυωνύμου 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):

Είσοδος: Ένα square-free πολυώνυμο μιας μεταβλητής $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(1/x + 1), M₀₁ ← M(1/x + 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) = x 3 - 7 x + 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 + 2/x + 1 7 m ← 1 8 p_1∞ ← x³ + 6x² + 5x + 1, M_1∞ ← x + 2 10 RETURN VAS(x³ − x² − 2x + 1, x + 2/x + 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 + 2/x + 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 + 3/x + 1 7 m ← 3/2 8 p_1∞ ← x³ + 2x² − x − 1, M_1∞ ← x + 3/x + 2 10 RETURN VAS(x³ + x² − 2x − 1, 2x + 3/x + 2) ∪ VAS(x³ + 2x² − x − 1, x + 3/x + 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 + 3/x + 2) 1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του πολυωνύμου p(x) = x³ + x² − 2x − 1 3 RETURN {(3/2, 2)}

Λίστα απομονωμένων διαστημάτων: ${(3 / 2, 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 + 3/x + 2) 1 var ← 1 // ο αριθμός των εναλλαγών προσήμου στην ακολουθία των συντελεστών του πολυωνύμου p(x) = x³ + 2x² − x − 1 3 RETURN {(1, 3/2)}

Λίστα απομονωμένων διαστημάτων: ${(1, 3 / 2), (3 / 2, 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, 3 / 2), (3 / 2, 2)}.$

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

Τέλος.

Συμπέρασμα

Επομένως, οι δύο θετικές ρίζες του πολυωνύμου $p (x) = x 3 - 7 x + 7$ βρίσκονται μέσα στα διαστήματα απομόνωσης $(1, 3 / 2)$ και $(3 / 2, 2)$ . Κάθε ρίζα μπορεί να προσεγγιστεί (για παράδειγμα) διχοτομώντας το αντίστοιχο διάστημα απομόνωσης έως ότου η διαφορά των τελικών σημείων να είναι μικρότερη του $10 -6$ . Με αυτή την προσέγγιση οι ρίζες του πολυωνύμου είναι οι $ρ 1 = 1.3569$ και $ρ 2 = 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), αλλά συνήθως είναι αρκετά πιο γρήγορος. Τέλος, έχει συμπεριληφθεί στον πακέτο RootFinding του συστήματος υπολογιστικής άλγεβρας Maple.

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

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

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

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

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

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

VCA(p, (a, b))

Είσοδος: Ένα square-free πολυώνυμο μιας μεταβλητής 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(1/x + 1) // "0_1 εξέταση ριζών" του Μπουντάν; 2 if var = 0 then RETURN ∅; 3 if var = 1 then RETURN {(a, b)}; 4 p_01/2 ← 2^deg(p)p(x/2) // Ψάξε για πραγματικές ρίζες στο διάστημα (0, 1/2); 5 m ← 1/2(a + b) // Είναι ρίζα ο αριθμός 1/2? 6 p_1/21 ← 2^deg(p)p(x + 1/2) // Ψάξε για πραγματικές ρίζες στο διάστημα (1/2, 1); 7 if p(1/2) ≠ 0 then 8 RETURN VCA (p_01/2, (a, m)) ∪ VCA (p_1/21, (m, b)) 9 else 10 RETURN VCA (p_01/2, (a, m)) ∪ {[m, m]} ∪ VCA (p_1/21, (m, b)) 11 end

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

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

Example of VCA(p, (a,b))

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