Πολύεδρο του Νεύτωνα και πολυπλοκότητα του πολυωνύμου

Ν. Λυγερός




Με το ευρύ τους φάσμα εφαρμογής, τα πολυώνυμα αποτελούν σημαντικότατα στοιχεία όχι μόνο για την υπολογιστική γεωμετρία, αλλά και πιο γενικά για τη μαθηματική μοντελοποίηση πολύπλοκων αλγεβρικών συστημάτων. Έτσι, η ακριβή γνώση της πολυπλοκότητας του πολυωνύμου είναι βασική για την προσέγγιση των προβλημάτων. Το πολύεδρο του Νεύτωνα είναι ένα ισχυρό μέσον πληροφορίας όσον αφορά αυτή την πολυπλοκότητα του πολυωνύμου. Διότι δεν κοιτάζει μόνο το συνολικό βαθμό του αλλά όλο το σύνολο των εκθετών που εμφανίζονται. Όταν το πολυώνυμο έχει μόνο έναν άγνωστο, δεν βλέπουμε τα πλεονεκτήματα του πολυέδρου του Νεύτωνα. Ενώ αν έχουμε τουλάχιστον δυο εξισώσεις με δύο αγνώστους, οι οποίες έχουν το ίδιο πολύεδρο του Νεύτωνα, τότε το διπλάσιο του όγκου του πολυέδρου ισούται με το πλήθος των κοινών μιγαδικών ριζών του συστήματος. Συνεπώς υπάρχουν όρια στο πλήθος ριζών συστήματος πολυωνύμου σε συνάρτηση των αντίστοιχων πολυέδρων του Νεύτωνα με τη χρήση της έννοιας του μικτού όγκου, ακριβέστερα από τα κλασικά όρια του Bιzout τα οποία αποτελούν συνάρτηση του συνολικού βαθμού. Υπολογιστικά, το μοναδικό πρόβλημα είναι ο μικτός όγκος των πολυέδρων που γίνεται μέσω του αθροίσματος Minkowski. Με αυτή την προσέγγιση, καταλήγουμε λογικά στο θεώρημα των Bernstein, Khvanskii και Kushnivenko, το οποίο εκφράζεται ως εξής: Ένα σύστημα n εξισώσεων με n αγνώστους έχει το πολύ n!G μιγαδικές ρίζες, όπου G ο όγκος του πολυέδρου του Νεύτωνα. Το θεώρημα βέβαια γενικεύεται στην περίπτωση που τα πολύεδρα του Νεύτωνα είναι διαφορετικά, όπου το φράγμα δίνεται από το μικτό του όγκου. Βλέπουμε, λοιπόν, ότι ακόμα και αν η νοητική προσέγγιση είναι γραμμική, η αλλαγή των αρχικών δεδομένων επιτρέπει την επίτευξη σχηματικών αποτελεσμάτων μέσω ενός εργαλείου σχετικά απλού, μα ποτέ απλοϊκού. Οι βασικές τροποποιήσεις προσφέρουν ένα καινούργιο πλαίσιο για την ανάπτυξη μίας σκέψης ακόμα και αν αυτή ακολουθεί τα κλασικά κριτήρια. Η ολική πολυπλοκότητα δεν αλλάζει όσον αφορά στην αναλογία του πολυωνύμου, όμως το πολύεδρο του Νεύτωνα την προσεγγίζει με μεγαλύτερη ακρίβεια και δίνει τη δυνατότητα μίας νέας ερμηνείας και τελικά επιτρέπει την επανανακάλυψή της.







free counters


Opus