Κεφάλαιο 2





2. Πολυώνυμα και ρητές συναρτήσεις

2.1 Πολυώνυμα σε μία και περισσότερες μεταβλητές

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

2.1.1 Τα πολυώνυμα ως συμβολικές εκφράσεις

Με απλά λόγια ένα πολυώνυμο p μιας μεταβλητής x είναι ένα άθροισμα όρων, όπου κάθε όρος έχει έναν συντελεστή $a_k$, που πολλαπλασιάζεται με ένα μονώνυμο, όπου το κάθε μονώνυμο είναι η μεταβλητή x υψωμένη σε κάποια δύναμη k, όπου k μη-αρνητικός ακέραιος, δηλαδή $$ p = a_k\, x^k + a_{k-1} \, x^{k-1} + \cdots + a_1 \, x +a_0\,.$$ Για παράδειγμα,

In [1]:
p = x^4 - 4*x^2 -  7*x + 9
print p; print type(p)
print 'degree of p :' , p.degree(x)
x^4 - 4*x^2 - 7*x + 9
<type 'sage.symbolic.expression.Expression'>
degree of p : 4

Στο Sage, o βαθμός ενός πολυωνύμου μας δίνεται με την συνάρτηση degree η οποία δέχεται ως όρισμα την μεταβλητή του πολυωνύμου. Μπορούμε να συλλέξουμε τους συντελεστές των δυνάμεων της μεταβλητής x του πολυωνύμου p, με την εντολή coefficient(), ως εξής:

In [2]:
print 'the coefficient of x^2 :', p.coefficient(x,2)
print 'all coefficients :', [p.coefficient(x,k) for k in range(p.degree(x)+1)]
print 'the leading coefficient :', p.leading_coefficient(x)
the coefficient of x^2 : -4
all coefficients : [9, -7, -4, 0, 1]
the leading coefficient : 1

Επίσης, έχουμε την δυνατότητα να καταχωρούμε σε μια λίστα από λίστες όλους τους συντελεστές και τις αντίστοιχες δυνάμεις του x:

In [3]:
print 'all coefficients :', p.coefficients()
print 'all coefficients in x :', p.coefficients(x)
all coefficients : [[9, 0], [-7, 1], [-4, 2], [1, 4]]
all coefficients in x : [[9, 0], [-7, 1], [-4, 2], [1, 4]]

Αν θέλουμε να δούμε τους όρους του πολυωνύμου συμβολικά τότε χρησιμοποιούμε την συνάρτηση operands

In [4]:
print 'the operands of p :', p.operands()
the operands of p : [x^4, -4*x^2, -7*x, 9]

που μας εμφανίζει μια λίστα με τους όρους που απαρτίζουν το άθροισμα του πολυωνύμου. Ας ρωτήσουμε το Sage για τις ρίζες του πολυωνύμου p

In [5]:
print p.roots()
[(-1/6*sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) - 1/2*sqrt(-(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 124/9/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 42/sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 16/3), 1), (-1/6*sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 1/2*sqrt(-(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 124/9/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 42/sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 16/3), 1), (1/6*sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) - 1/2*sqrt(-(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 124/9/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 42/sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 16/3), 1), (1/6*sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 1/2*sqrt(-(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) - 124/9/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 42/sqrt((9*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(2/3) + 24*(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3) + 124)/(1/18*sqrt(248699)*sqrt(3) + 3787/54)^(1/3)) + 16/3), 1)]

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

In [6]:
print 'the real roots :', p.roots(ring=RR)
print 'the complex roots :', p.roots(ring=CC)
the real roots : [(0.910297335360486, 1), (2.31169382618360, 1)]
the complex roots : [(0.910297335360486, 1), (2.31169382618360, 1), (-1.61099558077204 - 1.29676194949457*I, 1), (-1.61099558077204 + 1.29676194949457*I, 1)]

απ' όπου διαπιστώνουμε ότι το πολυώνυμό μας έχει δυο διαφορετικές πραγματικές ρίζες και δυο συζυγείς μιγαδικές.

2.1.2 Πολυώνυμα μιας μεταβλητής

Μπορούμε να δηλώσουμε ρητά σε ποιο σώμα ανήκουν οι συντελεστές του πολυωνύμου p, και να περιορίσουμε την έκφραση του p σε αυτό το σώμα. Ας σημειώσουμε με q τον περιορισμό του p στους ρητούς αριθμούς

In [7]:
P.<x> = PolynomialRing(QQ)
q = P(p)
print q; print type(q)
x^4 - 4*x^2 - 7*x + 9
<type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>

Ένας εναλλακτικός πιο γρήγορος τρόπος, κι ίσως πιο φυσικός, για τον περιορισμό του πολυωνύμου p είναι

In [8]:
R = QQ[x]
r = R(p)
print r; print type(r)
x^4 - 4*x^2 - 7*x + 9
<type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>

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

In [9]:
print QQ[x].random_element(degree=4)
5*x^4 - 1/2*x^3 + 1/2*x + 8/7

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

In [10]:
print q.degree();
print 'coefficients of nonzero terms :', q.coefficients()
print 'all coefficients :', q.coefficients(sparse=False)
print 'the list of all coefficients :', q.list()
print 'a dictionary representation :', q.dict()
4
coefficients of nonzero terms : [9, -7, -4, 1]
all coefficients : [9, -7, -4, 0, 1]
the list of all coefficients : [9, -7, -4, 0, 1]
a dictionary representation : {0: 9, 1: -7, 2: -4, 4: 1}

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


Ας δούμε αν το πολυώνυμο q είναι ανάγωγο στους ρητούς

In [11]:
print q.is_irreducible()
print factor(q)
True
x^4 - 4*x^2 - 7*x + 9

Αφού είναι ανάγωγο ας επεκτείνουμε το σώμα ώστε αυτό να περιλαμβάνει μια ρίζα του πολυωνύμου q στο QQ, την οποία ας την ονομάζουμε a

In [12]:
K.<a> = QQ.extension(q)
print K
Number Field in a with defining polynomial x^4 - 4*x^2 - 7*x + 9

κι ας δούμε την μορφή του p στο νέο σώμα Κ, την οποία ας το ονομάσουμε q2

In [13]:
q2 = K[x](q)
print q2; print type(q2)
x^4 - 4*x^2 - 7*x + 9
<class 'sage.rings.polynomial.polynomial_number_field.PolynomialRing_field_with_category.element_class'>

Είναι άραγε ανάγωγο το q2 στο K;

In [14]:
print q2.is_irreducible()
print factor(q2)
False
(x - a) * (x^3 + a*x^2 + (a^2 - 4)*x + a^3 - 4*a - 7)

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

In [15]:
f2 = q2/(x-a); print f2; print type(f2); print type(K[x](f2))
L.<b> = K.extension(K[x](f2))
print L
x^3 + a*x^2 + (a^2 - 4)*x + a^3 - 4*a - 7
<class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'>
<class 'sage.rings.polynomial.polynomial_number_field.PolynomialRing_field_with_category.element_class'>
Number Field in b with defining polynomial x^3 + a*x^2 + (a^2 - 4)*x + a^3 - 4*a - 7 over its base field

Τώρα μπορούμε να πάρουμε το αρχικό μας πολυώνυμο q και να το παραγοντοποιήσουμε στη νέα επέκταση L.

In [16]:
q3 = L[x](q)
print factor(q3)
(x - b) * (x - a) * (x^2 + (b + a)*x + b^2 + a*b + a^2 - 4)

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

In [17]:
lf = list(factor(q3))
print lf
[(x - b, 1), (x - a, 1), (x^2 + (b + a)*x + b^2 + a*b + a^2 - 4, 1)]

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

In [18]:
f3t = lf[2]; print f3t, type(f3t)
f3 = L[x](f3t[0]); print f3; print type(f3)
(x^2 + (b + a)*x + b^2 + a*b + a^2 - 4, 1) <type 'tuple'>
x^2 + (b + a)*x + b^2 + a*b + a^2 - 4
<class 'sage.rings.polynomial.polynomial_number_field.PolynomialRing_field_with_category.element_class'>

Τώρα είμαστε σε θέση να εκτελέσουμε την τελευταία επέκταση του σώματος ώστε να παραγοντοποιηθεί επιτέλους το πολυώνυμο q

In [19]:
M.<c> = L.extension(f3);
print M
Number Field in c with defining polynomial x^2 + (b + a)*x + b^2 + a*b + a^2 - 4 over its base field

Αφού το q στο σώμα M μπορεί να παραγοντοποιηθεί ως γινόμενο γραμμικών παραγόντων, έχουμε βρει συμβολικά τις ρίζες του q, εκφράζοντάς τις ως προς τους αλγεβρικούς αριθμούς a,b και c. Πραγματικά:

In [20]:
q4 = M[x](q)
print factor(q4)
(x - b) * (x + c + b + a) * (x - c) * (x - a)

το q παραγοντοποιείται σε γραμμικούς παράγοντες στην επέκταση M. Παρατηρήστε την σύνδεση μεταξύ της διαδικασίας παραγοντοποίησης και εύρεσης ριζών

In [21]:
print q4.roots()
[(b, 1), (-c - b - a, 1), (c, 1), (a, 1)]

Φυσικά τώρα μπορούμε να βρούμε και αριθμητικά τις ρίζες του q στο Μ (δηλαδή του q4) αλλάζοντας δακτύλιο

In [22]:
rizes = q4.roots(ring=CC)
print rizes
[(0.910297335360486, 1), (2.31169382618360, 1), (-1.61099558077204 - 1.29676194949457*I, 1), (-1.61099558077204 + 1.29676194949457*I, 1)]

Επειδή ο συντελεστής του όρου $x^3$ είναι μηδέν, το άθροισμα των ριζών του πολυωνύμου μας, και στην συμβολική και στην αριθμητική του μορφή, οφείλει να είναι μηδέν. Στην συμβολική μορφή των ριζών το γεγονός αυτό προκύπτει άμεσα. Οπότε ας το ελέγξουμε για την αριθμητική μορφή των ριζών.

In [23]:
print sum( list(rizes[i])[0] for i in range(4))
0.000000000000000

Συνοψίζοντας, διακρίνουμε δυο κύριους τρόπους εύρεσης των ριζών ενός πολυωνύμου, τον συμβολικό και τον αριθμητικό. Το προεπιλεγμένο σώμα για τα αριθμητικά αποτελέσματα είναι οι μιγαδικοί αριθμοί. Με τον συμβολικό τρόπο επεκτείνουμε το σώμα των ρητών αριθμών εισαγάγοντας ικανό αριθμό συμβόλων ώστε να μπορούν να αναπαραστούν όλες τις ρίζες ενός πολυωνύμου, και συνεπώς να μπορεί το πολυώνυμο να παραγοντοποιηθεί σε γραμμικούς παράγοντες.

2.1.3 Πολυώνυμα πολλών μεταβλητών

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

In [24]:
R.<x,y> = QQ[]
p = R.random_element(degree=4,terms=10)
print p; print type(p)
-1/2*x^4 + x^3*y - 3/4*y^4 + 1/3*x^3 + 4/5*x^2*y + 1/3*x*y^2 + 2*y - 1/2
<type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'>

Μπορούμε να πληροφορηθούμε για τα μονώνυμα που απαρτίζουν το πολυώνυμο, τις μεταβλητές του, τους συντελεστές του πολυωνύμου, καθώς τόσο για τον ολικό βαθμό του πολυωνύμου όσο και για τους επιμέρους βαθμούς ως προς τις μεταβλητές x και y, όπως παρακάτω

In [25]:
print 'the monomials :', p.monomials()
print 'corresponding coefficients :', p.coefficients()
print 'the variables :', p.variables()
print 'the degree in x :', p.degree(x)
print 'the degree in y :', p.degree(y)
print 'the degree of p :', p.degree()
the monomials : [x^4, x^3*y, y^4, x^3, x^2*y, x*y^2, y, 1]
corresponding coefficients : [-1/2, 1, -3/4, 1/3, 4/5, 1/3, 2, -1/2]
the variables : (x, y)
the degree in x : 4
the degree in y : 4
the degree of p : 4

Η διάταξη που εμφανίζονται τα μονώνυμα είναι πολύ σημαντική

In [26]:
print R.term_order()
Degree reverse lexicographic term order

Προεπιλεγμένα, στο Sage η διάταξη των μονωνύμων είναι Degree reverse lexicographic term order. Για να αλλάξουμε την διάταξη των μονωνύμων, περιορίζουμε το πολυώνυμο στο σώμα των ρητών και θέτουμε λεξικογραφική διάταξη. Στην λεξικογραφική διάταξη όλα τα μονώνυμα που περιέχουν την μεταβλητή x έρχονται πρώτα, από την μεγαλύτερη δύναμη του x προς την μικρότερη.

In [27]:
Rlex.<x,y> = PolynomialRing(QQ,order = 'lex')
print Rlex; print Rlex.term_order()
print Rlex(p)
Multivariate Polynomial Ring in x, y over Rational Field
Lexicographic term order
-1/2*x^4 + x^3*y + 1/3*x^3 + 4/5*x^2*y + 1/3*x*y^2 - 3/4*y^4 + 2*y - 1/2

Τέλος, μπορούμε να θεωρήσουμε ένα πολυώνυμο με πολλές μεταβλητές ως ένα πολυώνυμο μιας μεταβλητής (της x, ή της y κοκ) επιλέγοντας τους αντίστοιχους όρους. Λόγω του τύπου του ορίσματος p.variables() το οποίο δέχεται η συνάρτηση polynomial() στο Sage, είναι απαραίτητο να επιλέξουμε από την ν-ιάδα (tuple) του p.variables(), την πρώτη, την δεύτερη συνιστώσα κοκ. Για παράδειγμα

In [28]:
print p.variables(); print type(p.variables())
(x, y)
<type 'tuple'>
In [29]:
print 'as polynomial in x :', p.polynomial(p.variables()[0])
print 'as polynomial in y :', p.polynomial(p.variables()[1])
as polynomial in x : -1/2*x^4 + (y + 1/3)*x^3 + 4/5*y*x^2 + 1/3*y^2*x - 3/4*y^4 + 2*y - 1/2
as polynomial in y : -3/4*y^4 + 1/3*x*y^2 + (x^3 + 4/5*x^2 + 2)*y - 1/2*x^4 + 1/3*x^3 - 1/2

2.2 Ρητές συναρτήσεις

Στο Sage ένας ρητός αριθμός απλοποιείται αυτόματα. Όμως, όταν έχουμε ρητές εκφράσεις, όπου ο αριθμητής και ο παρονομαστής είναι πολυώνυμα, τότε απλοποιώντας με τον μέγιστο κοινό διαιρέτη τους δεν σημαίνει ότι η έκφραση που θα πάρουμε ως το αποτέλεσμα της απλοποίησης θα είναι απλή. Για παράδειγμα, αν θεωρήσουμε την ρητή συνάρτηση $$ \frac{x^d-1}{x-1}$$ για οποιονδήποτε μεγάλο θετικό ακέραιο $d$, για παράδειγμα d=1000, το αποτέλεσμα της απλοποίησης θα είναι ένα πολυώνυμο βαθμού $d-1=999$, το οποίο απαρτίζεται από 1000 όρους!!!

2.2.1 Ρητές εκφράσεις

Στο Sage ο τύπος των ρητών εκφράσεων αναφέρεται ως fraction_field_element, στο πεδίο sage.rings

In [30]:
x = polygen(QQ)
p = x^3 - 1; q = x^2 - 1; r = p/q
print r; print type(r)
(x^2 + x + 1)/(x + 1)
<class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'>

Είναι ενδιαφέρον ότι το Sage φέρνει αυτόματα το πολυώνυμο σε κανονική μορφή, δηλαδή απλοποιεί με τον μέγιστο κοινό διαιρέτη του αριθμητή και του παρονομαστή. Στο συγκεκριμένο παράδειγμα βλέπουμε ότι έχει απλοποιηθεί ο κοινός παράγοντας $x-1$.

In [31]:
print factor(p); print factor(q)
(x - 1) * (x^2 + x + 1)
(x - 1) * (x + 1)

Η αυτόματη απλοποίηση μπορεί να οδηγήσει σε προβλήματα αφού, αν για παράδειγμα αν πάρουμε

In [32]:
f = (x^23 - 1)/(x-1); print f
x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

το αποτέλεσμα είναι ένα πολυώνυμο με τόσους όρους όσους είναι η δύναμη του αριθμητή!!! Φανταστείτε το αποτέλεσμα αν ο βαθμός του αριθμητή ήταν 1000. Αντί να ζητήσουμε από το Sage να μας δώσει το αποτέλεσμα μπορούμε να του ζητήσουμε να μας δώσει το πλήθος των όρων του f. Όμως, το θέμα είναι ότι για το Sage το f δεν είναι πολυώνυμο, αλλά ρητή έκφραση, και θα πρέπει να πάρουμε τον τετριμμένο αριθμητή του πριν ζητήσουμε το πλήθος των όρων του.

In [33]:
print type(f)
fn = f.numerator()
print type(fn)
print len(fn.coefficients())
<class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'>
<type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>
23

Μπορούμε να σταθεροποιήσουμε μια ρητή έκφραση, δηλαδή να μην γίνει αυτόματη απλοποίηση, περιορίζοντας τον συμβολικό δακτύλιο (symbolic ring SR)

In [34]:
g = SR(p)/q; print g;
(x^3 - 1)/(x^2 - 1)

και να ζητήσουμε από το Sage τον αριθμητή και τον παρονομαστή του g, πριν και μετά από την απλοποίηση

In [35]:
print g.numerator(normalize=False)
print g.numerator(normalize=True)
(x^3 - 1)
x^2 + x + 1
In [36]:
print g.denominator(normalize=False)
print g.denominator(normalize=True)
x^2 - 1
x + 1

Επιπλέον, μπορούμε να δούμε τον αριθμητή και τον παρονομαστή μιας ρητής έκφρασης σε παραγοντοποιημένη μορφή (αν είναι εφικτή) ή όχι

In [37]:
fn = g.numerator(normalize=False).factor()
fd = g.denominator(normalize=False).factor()
print SR(fn)/g.denominator(normalize=False)
print g.numerator(normalize=False)/SR(fd)
(x^2 + x + 1)*(x - 1)/(x^2 - 1)
(x^3 - 1)/((x + 1)*(x - 1))

2.2.2 Σχήμα Horner και διάσπαση σε απλά κλάσματα

Ο περιορισμός ενός πολυωνύμου σε ένα συμβολικό δακτύλιο με την εντολή SR μας δίνει το λεγόμενο σχήμα Horner του πολυωνύμου

In [38]:
x = SR.var('x')
p = x^4 + 2*x^3 + 3*x^2 + 4*x + 5
print p.horner(x)
(((x + 2)*x + 3)*x + 4)*x + 5

Το σχήμα Horner είναι ένας εύχρηστος τρόπος για να βρίσκουμε τις τιμές ενός πολυωνύμου σε ένα συγκεκριμένο $x_0$.
Επίσης μπορούμε να αναλύσουμε μια ρητή έκφραση σε απλά κλάσματα με την partial_fraction_decomposition(). Ας κατασκευάσουμε δυο τυχαία πολυώνυμα βαθμού 4 με συντελεστές στου ρητούς και με βάση αυτά κατασκευάζουμε μια ρητή έκφραση, όπως παρακάτω

In [39]:
P.<x> = PolynomialRing(QQ);
rn = P.random_element(degree = 4);
rd = P.random_element(degree = 4);
f = rn/rd;
print f; print type(f)
(1/2*x^4 + 14*x^3 + x^2 - 3*x - 4)/(-1/2*x^4 - 1/2*x^3 - x - 3/2)
<class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'>
In [40]:
print f.partial_fraction_decomposition()
(-1, [(-27*x^3 - 2*x^2 + 8*x + 11)/(x^4 + x^3 + 2*x + 3)])
In [41]:
whole, parts = f.partial_fraction_decomposition()
In [42]:
print whole; print parts
-1
[(-27*x^3 - 2*x^2 + 8*x + 11)/(x^4 + x^3 + 2*x + 3)]
In [43]:
print whole + sum(parts) == f
True

2.3 Αντικατάσταση, αναπτύγματα και παραγοντοποίηση

2.3.1 Αντικαταστάσεις

Στο Sage έχουμε την δυνατότητα να αντικαταστήσουμε μια σύνθετη συμβολική έκφραση από μια συμβολική μεταβλητή, έτσι ώστε να αποφύγουμε τυχόν αναπτύγματα της σύνθετης έκφρασης. Για παράδειγμα, ας υποθέσουμε ότι θέλουμε οι δυο όροι στην ρητή έκφραση $$ (x+y)^2 + \frac{1}{(x+y)^2}$$ να έχουν κοινό παρονομαστή. Ας επιχειρήσουμε να παραγοντοποιήσουμε την έκφραση

In [44]:
var('x y')
p = (x+y)^2 + 1/(x+y)^2
print p; print type(p)
(x + y)^2 + 1/(x + y)^2
<type 'sage.symbolic.expression.Expression'>
In [45]:
print p.factor()
(x^4 + 4*x^3*y + 6*x^2*y^2 + 4*x*y^3 + y^4 + 1)/(x + y)^2

Η εντολή factor αναπτύσσει τον αριθμητή, το οποίο δεν το επιθυμούμε. Για να διατηρήσουμε την μεταβλητή $(x+y)^2$ ως έχει, την αντικαθιστούμε από μια άλλη μεταβλητή $z$. Στην συνέχεια παραγοντοποιούμε την έκφραση στην μεταβλητή $z$, και στο τέλος αντικαθιστούμε την $z$ aπό την αρχική έκφραση $x+y$.

In [46]:
var('z')
q = p.subs({(x+y): z})
print 'after substitution of x+y into z :', q
fq = q.factor()
print 'after factoring :', fq
qq = fq.subs(z=x+y)
print 'after substitution of z into x+y :', qq
after substitution of x+y into z : z^2 + 1/z^2
after factoring : (z^4 + 1)/z^2
after substitution of z into x+y : ((x + y)^4 + 1)/(x + y)^2

Για να δούμε την τελική έκφραση σε μια κομψή μαθηματική μορφή, τρέχουμε

In [47]:
qq.show()

Οι αντικαταστάσεις με την μέθοδο subs() που είδαμε σε προηγούμενο εδάφιο συμβαίνουν με διαδοχική σειρά, και όχι ταυτόχρονα. Ας υποθέσουμε ότι θέλουμε να μεταθέσουμε κυκλικά τις μεταβλητές $a \rightarrow b \rightarrow c \rightarrow a $ στην συμβολική έκφραση $a+2 \ast b+3\ast c$. Με άλλα λόγια, θέλουμε να πάρουμε την έκφραση $b+2\ast c+ 3\ast a$, από την έκφραση $a+2 \ast b+3\ast c$, με ταυτόχρονη κυκλική μετάθεση των μεταβλητών της. Τότε το αποτέλεσμα με την μέθοδο subs() δεν θα μας έδινε το επιθυμητό αποτέλεσμα, αφού οι αντικαταστάσεις θα συνέβαιναν διαδοχικά. Όμως ο υπολογισμός της τιμής μιας έκφρασης με την μέθοδο της παραγράφου 1.7.2, δηλαδή (a = b, b = c, c = a) μας δίνει το επιθυμητό αποτέλεσμα.

In [48]:
var('a,b,c')
e = a + 2*b + 3*c
print 'the expression :', e
print 'substitution with dictionary argument :', e.subs({a:b, b:c, a:c})
print 'evaluation by keyword arguments :', e(a=b,b=c,c=a)
the expression : a + 2*b + 3*c
substitution with dictionary argument : 6*c
evaluation by keyword arguments : 3*a + b + 2*c

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

In [49]:
print p;
print p.operands()
(x + y)^2 + 1/(x + y)^2
[(x + y)^2, (x + y)^(-2)]

Θεωρώντας ότι η έκφραση αποτελείται, καθαρά συντακτικά από strings, μπορούμε να αντικαταστήσουμε όλον το όρο (x+y)^2 με τον όρο z

In [50]:
s = str(p)
print s
t = s.replace('(x + y)^2', 'z')
print t, type(t)
(x + y)^2 + 1/(x + y)^2
z + 1/z <type 'str'>

Τέλος, γνωρίζοντας την λίστα των όρων που απαρτίζουν την έκφρασή μας με την εντολή operands(), αποκτούμε το πλεονέκτημα να μπορούμε να εκμεταλλευτούμε την εντολή subs(). Έτσι μπορούμε να αντικαταστήσουμε τον όρο (x+y)^2 με τον όρο z, και τον όρο (x+y)^(-2) με τον όρο 1/z, δίχως να χάσουμε τον τύπο της συμβολικής μας έκφρασης, ως εξής

In [51]:
pz = p.subs({(x+y)^2:z, (x+y)^(-2):z^(-1)}) ; print pz, type(pz)
z + 1/z <type 'sage.symbolic.expression.Expression'>
In [52]:
factor(pz).subs({z:(x+y)^2, z^(-1):(x+y)^(-2)}).show()

2.3.2 Αναπτύγματα

Όταν δώσουμε στο Sage μια έκφραση σε μορφή παραγόντων όπως για παράδειγμα $$(a+b+c)(x^2+y^2+x\,y+3)\,,$$ τότε το Sage δεν αναπτύσσει αυτόματα την συμβολική έκφραση. Ο λόγος είναι ότι γενικά υπάρχει περίπτωση το ανάπτυγμα να έχει πάρα πολλούς όρους, και ουσιαστικά χάνεται οποιαδήποτε πληροφορία.

In [53]:
var('x y a b c')
p = (a+b+c)*(x^2+y^2+x*y+3)
print p
(x^2 + x*y + y^2 + 3)*(a + b + c)

Αν πραγματικά θέλουμε να αναπτύξουμε την έκφρασή μας τότε εφαρμόζουμε την εντολή expand()

In [54]:
print p.expand()
a*x^2 + b*x^2 + c*x^2 + a*x*y + b*x*y + c*x*y + a*y^2 + b*y^2 + c*y^2 + 3*a + 3*b + 3*c

Η εντολή expand() πραγματικά "εκτέλεσε" τα πάντα, ανέπτυξε όλους τους όρους με αποτέλεσμα να χάσουμε κάθε πληροφορία για την δομή της συμβολικής έκφρασης p. Ας υποθέσουμε ότι θέλουμε να κρατήσουμε τον παράγοντα (a+b+c) όπως είναι. Τότε ορίζουμε μια νέα μεταβλητή d και αντικαθιστούμε σε αυτή τον παράγοντα (a+b+c), πριν καλέσουμε την εντολή expand()

In [55]:
var('d')
dp = p.subs({a+b+c:d})
print dp
(x^2 + x*y + y^2 + 3)*d

Τώρα μπορούμε να αναπτύξουμε την έκφρασή μας με την εντολή expand() και να αντικαταστήσουμε στην μεταβλητή d τον αρχικό παράγοντα (a+b+c).

In [56]:
edp = dp.expand()
print edp
d*x^2 + d*x*y + d*y^2 + 3*d
In [57]:
pp = edp.subs({d:(a+b+c)})
print pp
(a + b + c)*x^2 + (a + b + c)*x*y + (a + b + c)*y^2 + 3*a + 3*b + 3*c

2.3.3 Παραγοντοποίηση

Η αντίστροφη διαδικασία των αναπτυγμάτων είναι η παραγοντοποίηση. Υπάρχει διάκριση μεταξύ της ακριβούς, της συμβολικής και της αριθμητικής παραγοντοποίησης.

In [58]:
print factor(pp)
(x^2 + x*y + y^2 + 3)*(a + b + c)

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

In [59]:
f = factor(x^2 - 1)
print f; print type(f)
(x + 1)*(x - 1)
<type 'sage.symbolic.expression.Expression'>

Για την συμβολική παραγοντοποίηση, προσθέτουμε φορμαλιστικά τις ρίζες του πολυωνύμου, που ονομάζονται αλγεβρικοί αριθμοί. Για παράδειγμα, επαναλαμβάνουμε την διαδικασία αυτή για το πολυώνυμο $y^2+2$

In [60]:
y = polygen(QQ)
q = y^2 + 2
print factor(q)
print q.is_irreducible()
K.<a> = QQ.extension(q)
kq = (K[y])(q)
print factor(kq)
x^2 + 2
True
(x - a) * (x + a)

Τέλος, η αριθμητική παραγοντοποίηση συμβαίνει πάντα στο σώμα των μιγαδικών

In [61]:
z = polygen(CC)
print factor(z^2 + 2)
(x - 1.41421356237310*I) * (x + 1.41421356237310*I)

2.4 Κανονική μορφή συμβολικών εκφράσεων

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

In [62]:
var('x,y')
e1 = x*(1+y)
e2 = x + x*y
print 'e1 = ', e1
print 'e2 = ', e2
print 'e1 == e1 : ', e1 == e2
e1 =  x*(y + 1)
e2 =  x*y + x
e1 == e1 :  x*(y + 1) == x*y + x

Όπως παρατηρούμε η τελευταία λογική ισότητα == δεν μας δίνει ως αποτέλεσμα ούτε True που αναμέναμε, ούτε False. Ίσως αν συγκρίναμε τους operands() και τους operator() αφού πρόκειται για συμβολικές εκφράσεις;

In [63]:
print e1.operands(), e1.operator()
print e2.operands(), e2.operator()
[x, y + 1] <function mul_vararg at 0x7f31d65a1aa0>
[x*y, x] <function add_vararg at 0x7f31d65a1a28>

Και πάλι στο Sage οι δυο αυτές εκφράσεις έχουν διαφορετικές λίστες ακόμα και στο επίπεδο των δεδομένων στο οποίο εκτελούνται οι υπολογισμοί για να βρούμε τις τιμές τους.
Για να δούμε τι θα συμβεί αν πάρουμε την διαφορά των δυο εκφράσεων.

In [64]:
print 'e1 - e2 :', e1 - e2
e1 - e2 : x*(y + 1) - x*y - x

Πάλι το Sage δεν απλοποιεί αυτόματα!! Για να ελέγξουμε την ισότητα είμαστε υποχρεωμένοι να αναπτύξουμε.

In [65]:
ee1 = e1.expand()
print 'e1 expanded :', ee1
print 'e2 :', e2
print 'e1 expanded - e2 :', ee1 - e2
e1 expanded : x*y + x
e2 : x*y + x
e1 expanded - e2 : 0

Παρατηρούμε ότι αναπτύσσοντας την διαφορά των δυο συμβολικών εκφράσεων οδηγούμαστε στο συμπέρασμα ότι οι δυο εκφράσεις είναι ταυτόσημες.

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


ΠΡΟΣΟΧΗ!! Η διαδικασία της κανονικοποίησης πρέπει να εφαρμόζεται με πάρα πολύ μεγάλη προσοχή, γιατί συνήθως χάνεται σημαντική πληροφορία. Επιπλέον, η κανονική μορφή μιας έκφρασης συνήθως δεν είναι μοναδική.

Ένας γρήγορος, αποτελεσματικός τρόπος, που συνήθως μας γλυτώνει από πολύ χαμένο χρόνο, για να αποφανθούμε αν δυο συμβολικές εκφράσεις είναι ταυτόσημες είναι να υπολογίσουμε τις τιμές των εκφράσεων δίνοντας τυχαίες τιμές στις μεταβλητές τους. Για παράδειγμα βρίσκουμε δυο τυχαίες μιγαδικές τιμές για τις μεταβλητές (x,y), που τις ονομάζουμε (rx,ry), ως εξής

In [66]:
rx = CC.random_element()
ry = CC.random_element()
print 'a random point :', (rx, ry)
a random point : (0.360996673346349 + 0.222156747209340*I, -0.446525900104420 - 0.947681290553240*I)

Στην συνέχεια υπολογίζουμε τις τιμές των εκφράσεων στο τυχαίο σημείο (rx, ry) και συγκρίνουμε την διαφορά τους,

In [67]:
v1 = e1(x=rx, y=ry)
v2 = e2(x=rx, y=ry)
print v1 - v2
0.000000000000000

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

In [68]:
rx = CC.random_element()
ry = CC.random_element()
print 'a random point :', (rx, ry)
a random point : (-0.793654299877551 + 0.562877141881479*I, 0.688568147657858 + 0.266600464949728*I)
In [69]:
v1 = e1(x=rx, y=ry)
v2 = e2(x=rx, y=ry)
print v1 - v2
0.000000000000000