συμβολικο ολοκληρωμα και αντιστροφη πινακας

[RFleming]

Καλησπέρα σας.

Θέλω να ρωτήσω κάτι τους καλούς προγραμματιστές.

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

Η τεχνική που χρησιμοποιώ συνοπτικά είναι

- ανάλυση των εκφράσεων,

- μετατροπή τους από in-fix σε post fix μορφή

- αποθήκευσή τους σε ένα δυαδικό δέντρο

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

Το δέντρο υλοποιείται με virtual functions.

Πρόσφατα έβαλα και συμβολική παραγώγιση.

Αυτό το έκανα ως εξής :

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

προσθέτω/αφαιρώ νέους κόμβους στο δέντρο καθώς διασχίζεται (δηλ. δυναμικά).

 

Το επόμενο βήμα είναι να βάλω συμβολική ολοκλήρωση.

Αλλά εδώ δεν μπορώ να σκεφτώ κάτι αποτελεσματικό και όσοι ρώτησα δεν ήξερα να μου πουν.

Έχετε καμιά ιδέα αν και πώς μπορεί να γίνει αυτό;

 

Επίσης, έχω φτιάξει μια κλάση πίνακα για να κάνω συμβολικά πράξεις πινάκων.

Με το δεδομένο ότι μπορώ να χειριστώ συμβολικά τα στοιχεία του ποιά είναι η

καταλληλότερη μέθοδος για τον υπολογισμό του αντιστρόφου του;

(Η gauss jordan και η LU δεν μου φαίνονται κατάλληλες.)

 

Προγραμματισμό C++ και αλγοριθμική ξέρω καλά και μπορώ νομίζω να φτιάξω ότι χρειαστεί,

μόνον την ιδέα θέλω για το πώς μπορούν να γίνουν τα παραπάνω....

[defacer]

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

[V.I.Smirnov]

Εγώ είμαι απλά ερασιτέχνης αλλά ξέρω να σου απαντήσω.

 

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

ο βολικότερος τρόπος που μπορώ να σκεφτώ είναι η μέθοδος Leverrier.

Με την τεχνική αυτή, μπορεί να υπολογιστεί ο αντίστροφος ενός πίνακα από τις δυνάμεις του,

τις ιδιοτιμές και τους συντελεστές του χαρακτηριστικού πολυωνύμου (θεώρημα Cayley-Hamilton κλπ).

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

δεν ξεπερνά τις 30 γραμμές (το είχα κάνει κάποτε).

 

 

Σε ότι αφορά το πρώτο ερώτημα, είναι για προγραμματιστές-επιστήμονες, όχι της σειράς.

Το ότι ξέρεις αλγοριθμική και C++ δεν σημαίνει τίποτε, αυτά τα ξέρει η σάρα κι η μάρα.

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

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

Μπορώ να σου πω αν θέλεις - όσο ξέρω τουλάχιστον - αλλά μάλλον δεν γίνω κατανοητός...

 

-

[RFleming]

@V.I.Smirnov

 

Mπoρείς να μου πεις την ιδέα και που έγκειται η δυσκολία ;

 

Links από την wikipedia τα βρίσκω και μόνος μου, θέλω κάτι άλλο αν ξέρεις.

(και προφανώς όπως είπα δεν είμαι αρχάριος ώστε να μου κάνουν τέτοια υπόδειξη..)

Επεξ/σία 13 Ιανουαρίου 2012 από RFleming

[V.I.Smirnov]

Βεβαίως, να σου πω δυο λόγια (αν και δεν είμαι μαθηματικός, ούτε προγραμματιστής.)

 

 

Η βασική ιδέα είναι ότι το πρόβλημα της ολοκλήρωσης λύνεται στα πλαίσια αλγεβρικών δομών

και ΟΧΙ με όρους της ανάλυσης. Απαιτούνται γνώσεις άλγεβρας.

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

συστήματος, άντε και να 'χει ακούσει και κάτι από θεωρία διαν. χώρων.

Η ολοκλήρωση από τους ανθρώπους - αλλά και βοηθητικά από το λογισμικό - γίνεται εφαρμόζοντας

κανόνες (αντικαταστάσεις και μετασχηματισμούς) που μοιάζουν τυχάρπαστοι και ενίοτε άσχετοι

μεταξύ τους. Η μόνη στάνταρ μέθοδος αφορά την ολοκλήρωση των ρητών συναρτήσεων.

Για ρητές συναρτήσεις μπορεί να αναπτυχθεί ένας αιτιοκρατικός αλγόριθμος που να δουλεύει πάντα

(εφόσον η παράγουσα είναι στοιχειώδης).

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

Η υλοποίηση της ανάλυσης σε κλάσματα έχει κάποια μειονεκτήματα,

π.χ. προκύπτουν πολυώνυμα με τεράστιους ακέραιους συντελεστές κλπ.

Παραλλαγές αυτής της τεχνικής όπως η αναγωγή Hermite, οι μέθοδοι Horowitz και

Rothstein-Trager δεν έχουν τέτοια προβλήματα και είναι προτιμότερες.

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

παραγοντοποίηση πολυωνύμων, εύρεση MΚΔ και επίλυση πολυωνυμικών εξισώσεων.

Αυτά είναι τα βασικά εργαλεία σε ότι αφορά τις ρητές συναρτήσεις.

 

Η επόμενη σκέψη είναι αν και πώς μπορούν οι παραπάνω τεχνικές να επεκταθούν

σε ολοκληρώματα με στοιχειώδεις υπερβατικές συναρτήσεις (sin, cos, atan κλπ).

Καταρχήν, δεν είναι προφανές ότι τα παραπάνω εργαλεία που αφορούν πολυώνυμα μπορούν να

χρησιμοποιηθούν. Ωστόσο, φαίνεται εύκολα ότι μπορούν, παρόλο που διαφεύγει σε σχεδόν σε όλους.

Π.χ. ρώτα μερικούς ποιό είναι το ολοκλήρωμα του 1/(1+x*x). Όλοι θα απαντήσουν arctan(x).

Κανείς δεν θα σου πει την εναλλακτική μορφή i(log(x+i)-log(x-i))/2 η οποία είναι

ταυτόσημη με την πρώτη. Δηλ. εδώ το ολοκλήρωμα μια ρητής συνάρτησης είναι πάλι ρητή

συνάρτηση αλλά επιπλέον έχει λογαρίθμους και εκθετικά.

 

Υπενθυμίζεται λοιπόν ότι οι στοιχειώδεις υπερβατικές συναρτήσεις μπορούν να γραφούν σε

εκθετική και λογαριθμική μορφή - κι ας το ξεχνούν (ή δεν το ξέρουν) οι περισσότεροι.

Με αυτό ως αφετηρία - μιλώντας απλοποιημένα - μπορεί να αποδειχτεί ότι για τον υπολογισμό

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

προεκταθεί κατάλληλα το διαφορικό πεδίο των ρητών συναρτήσεων με εκθετικούς και

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

Τα υπόλοιπα εργαλεία είναι (ας πούμε) ίδια όπως και στις ρητές συναρτήσεις.

 

Έτσι, ορίζεται μια αλγεβρική δομή (συγκεκριμένα ένα διαφορικό πεδίο) και το πρόβλημα μελετάται

καθαρώς αλγεβρικά, εντός αυτής. Απλοποιημένα μιλώντας πάντα, ζητούνται οι κατάλληλες εκθετικές

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

των στοιχείων της.

Το σπουδαιότερο θεώρημα που χρησιμοποιείται είναι το θεώρημα Liouville.

Αυτό και κάποια άλλα θεωρήματα (όπως το κριτήριο των υπολοίπων) χρησιμοποιούνται για

την διατύπωση ενός αλγόριθμου (αλγ. Risch) με τον οποίο μπορεί να εξεταστεί αν μια συνάρτηση

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

Όμοιο είναι και το πρόβλημα της συμβολικής άθροισης (σειρές κλπ).

 

Οι γνώσεις που χρειάζονται είναι γενική Άλγεβρα, Αλγεβρα, Πολυωνύμων και Διαφορική Άλγεβρα.

Πρέπει απαραιτήτως να εξοικοιωθείς με έννοιες όπως δακτύλιος, ακέραια περιοχή, διαφορικό πεδίο,

χαρακτηριστική πεδίου κλπ. Αλλιώς, η κατανόηση και εφαρμογή της τεχνικής είναι αδύνατη.

Αν έχεις το κουράγιο να διαβάσεις τέτοια πράγματα, στείλε μου pm να σου πω από πού να ξεκινήσεις -

και φυσικά όχι wikipedia, δεν έχει τίποτε που να βοηθά.

Είναι περίπου 300 σελίδες σημειώσεις (μαζί με αυτές που πραγματεύονται το πρόβλημα).

Aκούγονται πολλές και θέλουν προσπάθεια αλλά τέτοιες γνώσεις είναι που διαφοροποιούν

τον προγραμματιστή-επιστήμονα από τον κοινό προγραμματιστή που ξέρει μόνον C++ και αλγοριθμική...

 

-

Επεξ/σία 13 Ιανουαρίου 2012 από V.I.Smirnov

[RFleming]

Είσαι απίστευτος V.I.Smirnov !

 

Οι εξηγήσεις σου για μένα είναι αποκάλυψη σε ένα ΠΟΛΥ δυσνόητο θέμα.

Εδώ και καιρό έχω ρωτήσει τόσο κόσμο, μαθηματικούς, μηχανικούς Η/Υ και συναδέλφους προγραμματιστές

και η απάντηση ήταν είτε μπούρδες είτε κάτι ακατανόητα links σαν το παραπάνω.

Tώρα καταλαβαίνω τι είναι αυτά τα παράξενα που έβλεπα και γιατί εμφανίζονται

τα πολυώνυμα και η άλγεβρα στο όλο ζήτημα.

 

Φυσικά και θέλω να μου δώσεις ότι έχεις επί του θέματος.

Θα μελετήσω ότι χρειάζεται, εξάλλου ένας από τους λόγους που ξεκίνησα την ενασχόλησή μου με

τις συμβολικές πράξεις ήταν ακριβώς για να μάθω κάτι πέρα από τα τετριμμένα και βλέπω τελικά

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