Οι δέκα σπουδαιότερες μαθηματικές/υπολογιστικές μέθοδοι του 20ου αιώνα

Στο επετειακό τέυχος του περιοδικού "Computing in Science & Engineering" του Ιανουαρίου/Φεβρουαρίου 2000 (που συνεκδίδεται από το Αμερικανικό Φυσικομαθηματικό Ινστιτούτο και την οργάνωση Ι.Ε.Ε.Ε. - Institute of Electrical and Electronic Engineers - ), οι J. Dongarra και F. Sullivan συνέγραψαν μια λίστα αναφορικά με τους δέκα κορυφαίους μαθηματικούς αλγορίθμους των τελευταίων εκατό ετών. Η λίστα αυτή αποτέλεσε το έναυσμα για το αναλυτικό άρθρο που εμπεριέχεται στο τελευταίο φθινοπωρινό τεύχος του περιοδικού I.A.C.M. Expressions, όπου I.A.C.M. είναι το ακρωνύμιο της Διεθνούς Ομοσπονδίας για θέματα Υπολογιστικής Μηχανικής (International Association for Computational Mechanics). Ακολουθεί μια συνοπτική περίληψη των δέκα αυτών σπουδαίων μεθόδων, που αποτέλεσαν το βασικό εργαλείο για τον υπερκερασμό ανυπέρβλητων μέχρι πρώτινως υπολογιστικών προβλημάτων, ανοίγοντας έτσι τον δρόμο για μεγάλες εφευρέσεις, ανακαλύψεις και εξελίξεις στον επιστημονικό τρόπο σκέψεις σε ένα ευρύ φάσμα επιστημών και τεχνικών ειδικοτήτων.

1) Mέθοδος των πεπερασμένων στοιχείων (Finite Element Method, F.E.M.)

R. Courant 

J. Argyris (Ιωάννης Χατζηαργύρης)

O. C. Zienkiewicz

Κατά πολλούς, η F.E.M. είναι ό,τι σημαντικότερο έχει συλληφθεί στον τομέα της υπολογιστικής μηχανικής. Η μέθοδος των  πεπερασμένων στοιχείων μπορεί να περιγραφεί ως μια γενική αρχή προσεγγιστικής επίλυσης διαφορικών εξισώσεων με μερικές παραγώγους (η αναλυτική επίλυση των οποίων είναι από δύσκολη έως αδύνατη) και βασίζεται στην λεγόμενη μεταβολική (ή ασθενή) διατύπωση. Η μέθοδος είχε συλληφθεί εξαρχής από τον φημισμένο εφαρμοσμένο μαθηματικό R. Courant το 1943 αλλά αγνοήθηκε πλήρως (ίσως και λόγω απουσίας υπολογιστών εκείνη την εποχή), μέχρις ότου επαναδιατυπώθηκε από τους μηχανικούς το 1956. Ένας από τους συνεχιστές ήταν ο R. W. Clough, στον οποίο ανήκει και η πατρότητα του όρου "πεπερασμένα στοιχεία", ενώ ανάμεσα στις άλλες προσωπικότητες που ανέπτυξαν περεταίρω την μέθοδο ήταν ο O. C. Zienkiewicz και φυσικά ο Έλληνας, γεννηθείς στον Βόλο, J. Argyris (Ιωάννης Χατζηαργύρης), ένας από τους μέγιστους παγκοσμίως μαθηματικούς/μηχανικούς όλων των εποχών, ο οποίος ασχολήθηκε, εκτός της F.E.M., με την ανάπτυξη των πρώτων υπολογιστών, την αεροναυτική και την μηχανική των ρευστών. Συνυφασμένη και σχετική με την F.E.M.  είναι η Μέθοδος των Οριακών Στοιχείων που αναπτύχθηκε αρκετά αργότερα και συνδύασε τεχνικές επίλυσης αναπόσπαστων αναλυτικών εξισώσεων και ιδέες των πεπερασμένων στοιχείων.
Η F.E.M. χρησιμοποιείται πλέον κατά κόρον από κάθε υπολογιστικό πρόγραμμα εύρεσης εντατικής κατάστασης (όπως τα στατικά προγράμματα για τις κατασκευές) και διδάσκεται εμβριθώς στα Πολυτεχνεία της Ελλάδας και του εξωτερικού.

2) Διαδραστικοί γραμμικοί αλγεβρικοί τελεστές (interactive linear algebraic solvers)

E. Stiefel

Σχεδόν όλες οι μέθοδοι υπολογισμού που χρησιμοποιούν τις προσεγγιστικές πρακτικές της αριθμητικής ανάλυσης περιλαμβάνουν την επίλυση ενός γραμμικού αλγεβρικού συστήματος που περιλαμβάνει συνθετότερες μορφές της απλοποιημένης έκφρασης [Α]x = [Β]. Είναι όμως κατανοητό ότι οι κλασικές μέθοδοι επίλυσης (όπως η μέθοδος της απαλοιφής του Gauss καθώς και κάθε άλλη μέθοδος μορφοποίησης συστημάτων τέτοιας μορφής) είναι χρησιμοποιήσιμες κι εφικτές για συστήματα μέσου ή μικρού μεγέθους. Απεναντίας, τα συστήματα που προκύπτουν και είναι διάστασης, ας πούμε, μεγαλύτερης των 10.000, πρέπει να λυθούν διαδραστικά. Από την στιγμή λοιπόν που οι σύγχρονες υπολογιστικές απαιτήσεις οδηγούν συχνά στην ανάγκη επίλυσης συστημάτων μερικών εκατοντάδων χιλιάδων εξισώσεων κατ'ελάχιστο, οι διαδραστικοί γραμμικοί αλγεβρικοί τελεστές προβάλλουν εξαιρετικά χρήσιμοι. Αποτελεσματικοί τέτοιοι τελεστές καταφέρουν να επιταχύνουν την επίλυση εκμεταλλευόμενοι τις ειδικές ιδιότητες του μητρώου [Α], όπως την συμμετρία, την αντιστρεψιμότητα και την αραιότητά του. Διαδραστικές μέθοδοι επίλυσης  της [Α]x = [B] πρωτοεμφανίστηκαν το 1950 με την ανάπτυξη του αλγορίθμου των διαστημάτων Krylov και της μεθόδου των συζευγμένων κλίσεων των Hestenes και Stiefel για συμμετρικά μητρώα. Έκτοτε υπήρξε μεγάλη ανάπτυξη στον τομέα αυτό κι εμφανίστηκε μια σωρεία διαδραστικών μεθόδων, όπως η G.M.R.E.S. των Saad και Schultz (1986) για μη συμμετρικά μητρώα που χρησιμοποιείται έως και σήμερα ευρέως και σε πλήθος εφαρμογών.

3) Τελεστές αλγεβρικών ιδιοτιμών (algebraic eigenvalue solvers)

C. Lanczos

Το κλασικό πρόβλημα ιδιοτιμών [K]d = I...d αλλά και η γενικευμένη του μορφή [K]d = J[M]d εμφανίζονται συχνά σε αναλύσεις ταλαντώσεων ή καταστάσεων λυγισμού και συνήθως τα μητρώα [Κ] και [Μ] είναι μεγάλα και αραιά.
Μια ισχυρή μέθοδος επίλυσης των προναφερθέντων προβλημάτων αναπτύχθηκε το 1950 από τον C. Lanczos. Μια δεκαετία ργότερα, ο J. G. F. Francis ανέπτυξε τον πασίγνωστο πλέον ανάμεσα στους μαθηματικούς αλγόριθμο QR. Ο αλγόριθμος QR κυριάρχησε το '60 και το '70, διότι σε αντίθεση με την μέθοδο του Lanczos με την οποία υπολογίζονταν μόνο ορισμένες ακραίες ιδιοτιμές που ανήκαν σε ανώτερες ιδιομορφές των (δύο κυρίως) πρώτων τάξεων (που παρ'όλ'αυτά ευθύνονται κατά βάση κατά 70% έως 90% για την μορφή ενός παραμορφωμένου λόγω λυγισμού ή ταλάντωσης φορέα), ο QR βρίσκει όλες τις ιδιοτιμές ενός λογικά μικρού μητρώου με σχετική ταχύτητα.
Εν τούτοις, όταν κατά την δεκαετία του '80 διαπιστώθηκε η κύρια συμβολή στο τελικό αποτέλεσμα μόνο των αρχικών ιδιομορφών, η μέθοδος του Lanczos έκανε ένα θριαμβευτικό come - back.

4) Μέθοδοι της αποσύνθεσης των μητρώων (matric decomposition methods)

A. Householder

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

Τα απλούστερα μητρώα μπορούν να είναι διαγώνια, τριγωνικά, συμμετρικά, λοξώς συμμετρικά, ορθογώνια κ.τ.λ. Στις εφαρμογές της στην υπολογιστική μηχανική, η αποσύνθεση παρουσιάζει και φυσική σημασία. Όσων αφορά την επιστήμη του Πολιτικού Μηχανικού, αναφέρεται ενδεικτικά η φασματική αποσύνθεση (κατά την ανάλυση της δυναμικής επιπόνησης μιας κατασκευής από την σεισμική επιτάχυνση του εδάφους, η οποία χρησιμοποιεί αποσυντεθιμένα/παραγοντοποιημένα σεισμικά φάσματα σχεδιασμού που δείχνουν την πορεία εξέλιξης ιδιοπεριόδων ανάλογα με τον χρόνο) και η πολική αποσύνθεση (ταχεία μεταλλαγή από καρτεσιανό σε πολικό σύστημα συντεταγμένων προκειμένου να οριστεί η στροφική αδράνεια π.χ. μιας πολυκατοικίας, αφού έχει πρώτα βρεθεί ότι το κέντρο ελαστικής στροφής της εμφανίζεται σε ευνοϊκό για την κάτοψη σημείο).
Ο πρώτος που έδωσε ώθηση σε αυτό το πεδίο ήταν ο A. Householder ο οποίος, σε μια σειρά συγγραμμάτων που δημοσίευσε από το 1951 και μετά, εξήγησε την χρησιμότητα της παραγοντοποίησης των μητρώων και ανέπτυξε σχετικούς αλγορίθμους.

5) Μέθοδοι πεπερασμένης διαφοροποίησης για προβλήματα κυμάτων (finite difference methods for wave problems)

S. K. Godunov

Στις απαρχές της υπολογιστικής μηχανικής, προβλήματα συστημάτων κοινών διαφοροποιημένων εξισώσεων προερχομένων από (υπερβολικά κυρίως) κύματα, λύνονταν κυρίως με τον αλγόριθμο της χρονικής (αριθμητικής) ολοκλήρωσης του Euler. Εν τούτοις, στα μέσα του '50, έγινε κοινός τόπος στους εφαρμοσμένους μαθηματικούς και τους φυσικούς να βρουν ειδικές μεθόδους επίλυσης αποκλειστικά για προβλήματα κυμάτων. Δύο πρώιμες μέθοδοι αριθμητικής ολοκλήρωσης που χρησιμοποιούνται συχνά ακόμα και στις μέρες μας είναι εκείνη του Newmark (1959) αναφορικά με την δυναμική των κατασκευών κι εκείνη των Lex και Wendroff (1960) για την επίλυση υπερβολικών συστημάτων 1ης τάξης. Αργότερα ακολούθησαν και άλλες πολλές μέθοδοι βελτιωμένες ανά σημεία, όπως αυτή των Hilber, Hughes και Taylor (1978), με μια πιο "σφιχτή" αριθμητική διάχυση των τιμών.
Ένα σημαντικό θέμα που εμφανίζεται στην υπολογιστική επίλυση των υπερβολικών, παραβολικών και υπερβολικών παραβολοειδών προβλημάτων κυμάτων είναι αυτό του ορισμού και της σύλληψης της ασυνέχειας, ιδίως των κρουστικών κυμάτων. Οι κλασικές μέθοδοι πεπερασμένης διαφοροποίησης δεν μπορούσαν να επιλύσουν ικανοποιητικά τις ασυνέχειες. Ο S. K. Godunov ήταν ο πρώτος που αναγνώρισε κι εξέτασε το πρόβλημα και το 1959 πρότεινε, για προβλήματα της μηχανικής των ρευστών, τον πλέον γνωστό αλγόριθμο του Godunov. Αυτό άνοιξε τον δρόμο για διάφορους αλγορίθμους επίλυσης προβλημάτων στροβιλισμού και διάσπασης της ροής, προτεινόμενους από τους van Leer (1974, 1982), Steger και Warming (1979), Roe (1980) και άλλους. Σχετικά στοιχεία παρουσιάζονται ακόμα και στην F.E.M.

6) Μη γραμμικοί αλγεβρικοί τελεστές (nonlinear algebraic solvers)

Από τα αριστερά: G. G. Broyden, P. Fletcher, D. Goldfarb και D. F. Shanno

Τα περισσότερα προβλήματα της υπολογιστικής μηχανικής είναι μη γραμμικά. Η διακριτοποίηση χώρου και χρόνου οδηγεί συνήθως σε μη γραμμικό σύστημα αλγεβρικών εξισώσεων. Όταν άρχισαν με τον καιρό να παρουσιάζονται προβλήματα μεγάλης κλίμακας, έγινε αντιληπτό ότι οι συνηθισμένοι μη γραμμικοί τελεστές, όπως της διχοτόμησης, της διατέμνουσας ή ακόμα και του Newton δεν ήταν πλέον επαρκείς.
Μια σημαντική οικογένεια βελτιωμένων τελεστών είναι η λεγομένη ομάδα Quasi Newton (Q.N.). Η πρώτη μέθοδος Q.N. γνωστοποιήθηκε από τον Davidon το 1959 και μετέπειτα βελτιώθηκε περεταίρω κι εκδόθηκε από τους Fletcher και Powell. Μια άλλη μέθοδος Q.N. η οποία έγινε αργότερα (και παρέμεινε στις μέρες μας) ιδιαίτερα γνωστή, είναι η λεγόμενη B.F.G.S. η οποία πρωτοαναπτύχθηκε το 1970 από τους Broyden, Fletcher, Goldfarb και Shanno.
Μια τελείως διαφορετική προσέγγιση των μη γραμμικών προβλημάτων με μη γραμμικότητα μη μονότονης φύσης προσφέρεται από τις μεθόδους μήκους του τόξου (που καλούνται από τους μαθηματικούς μέθοδοι συνέχειας). Οι πρώτοι τέτοιοι αλγόριθμοι προτάθηκαν από τους G. A. Wempner (1971) και E. Riks (1972).

7) Γρήγορος μετασχηματισμός Fourier (Fast Fourier Transform, F.F.T.)

J. W. Tukey

J. Cooley

Οι φασματικές μέθοδοι της υπολογιστικής μηχανικής συχνά στηρίζονται στον διακριτό μετασχηματισμό Fourier. Το σημαντικότερο βήμα εδώ είναι ο υπολογισμός των πρώτων Ν συντελεστών του Fourier μιας συνάρτησης, όταν οι πρώτες Ν τιμές της δίνονται.
Ένας απευθείας υπολογισμός των συντελεστών του Fourier απαιτεί τις λεγόμενες O(N^2) διαδικασίες του κυμαινόμενου σημείου. Ο F.F.T. είναι ένας αλγόριθμος για την περαίωση αυτού του υπολογισμού χρησιμοποιώντας μόνο διαδικασίες του τύπου O(N*logN).
Η μέθοδος F.F.T. αναπτύχθηκε το 1965 από τους J. Cooley της Ι.Β.Μ.  και J. W. Tukey του Πανεπιστημίου του Princeton. Η μέθοδος είχε, μεταξύ άλλων, μεγάλο αντίκτυπο στην επεξεργασία των σημάτων.

8) Μη γραμμικός προγραμματισμός (nonlinear programming)

G. Dantzig

Η μέθοδος Simplex είναι ένας πολύ γνωστός κι εύχρηστος αλγόριθμος για γραμμικό προγραμματισμό, δημιουργημένη από τον  G. Dantzig, κυρίως για προβλήματα βελτιστοποίησης με αντικειμενικώς γραμμικές συναρτήσεις και περιορισμούς στην γραμμική ανισότητα των ενδιάμεσων βημάτων επίλυσης. Παρ'όλ'αυτά, τα περισσότερα προβλήματα βελτιστοποίησης στην υπολογιστική μηχανική σχετίζονται με αντικειμενικώς μη γραμμικές συναρτήσεις.
Σε διακριτό επίπεδο, τα απλούστερα προβλήματα αυτού του τύπου είναι εκείνα του τετραγωνικού προγραμματισμού (quadratic programming, Q.P.), με αντικειμενικώς τετραγωνικές συναρτήσεις και γραμμικούς περιορισμούς. Τέτοιου είδους προβλήματα εμφανίζονται συχνά σε διάφορους τομείς της υπολογιστικής μηχανικής, κι εν προκειμένω όσων αφορά τους Πολιτικούς Μηχανικούς, στην θεωρία της ελαστοπλαστικότητας. Η σημαντικότητα αυτής της κλάσης των θεμάτων συνίσταται και στο ότι η επίλυση πιο περίπλοκων προβλημάτων μπορεί να προσεγγιστεί θεωρώντας μια σειρά από απλούστερα προβλήματα Q.P.
 Πρώιμη δουλειά στον μη γραμμικό προγραμματισμό έγινε από τους Goldfarb (1969), Murtagh και Sargent (1969), McCormick (1970), Fletcher (1971) και Murray (1971). Μέθοδοι βελτιστοποίησης μεγάλης κλίμακας αναπτύχθηκαν από τους Griffith και Stewart (1961) και Murtagh και Saunders (1978).

9) "Ελαφρές" υπολογιστικές μέθοδοι ("soft" computing methods)

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

Παραδοσιακά, η υπολογιστική μηχανική βασίστηκε σε αυστηρές μαθηματικές νόρμες που περιλαμβάνουν, μεταξύ άλλων, την θεωρητική μηχανική, την αριθμητική ανάλυση, την συναρτησιακή ανάλυση κ.τ.λ. Εν τούτοις, από τις αρχές του '80 άρχισαν να εφαρμόζονται νέου τύπου υπολογιστικές διαδικασίες, οι οποίες έχει επικρατήσει να αναφέρονται ως "ελαφρές" υπολογιστικές μέθοδοι. Τέτοιου είδους διαδικασίες βασίζονται σε μια πιο "ευρετική" αντιμετώπιση του προβλήματος παρά σε αυστηρά μαθηματικά κι εφαρμόζονται σε τομείς όπως η τεχνητή νοημοσύνη. Παρά την χλυαρή έως καχύποπτη αρχική αντιμετώπιση των μεθόδων αυτών, η εκπληκτική δυναμική τους σε ορισμένους τομείς τις έχουν προσδώσει ιδιαίτερη αξία σε αρκετά πεδία της υπολογιστικής μηχανικής. Τρεις κύριες τεχνικές είναι τα Νευρωνικά Δίκτυα, οι Γενετικοί Αλγόριθμοι και η λεγόμενη Ασαφής Λογική. Και οι τρεις μπορούν να θεωρηθούν ως τεχνικές βελτιστοποίησης, αλλά στηρίζονται σε εντελώς διαφορετικές μεθοδολογίες.
Στοιχεία "ελαφρής" υπολογιστικής λογικής είχαν εμφανιστεί ήδη από το '40. Πιονέροι σε αυτό το πεδίο θεωρούνται οι McCulloch και Pitts στα Νευρωνικά Δίκτυα, ο Holland στους Γενετικούς Αλγορίθμους και ο Zadeh στην Ασαφή Λογική - αν και αρκετοί μαθηματικοί υποστηρίζουν ότι η Ασαφής Λογική εφευρέθηκε από τον Βούδα! Στις δεκαετίες του '60 και του '70 το όλο αυτό πεδίο μελετήθηκε εμβριθώς από τους επιστήμονες των υπολογιστών, αλλά μόνο στις αρχές του '80 άρχισε η συστηματική χρησιμοποίηση των εν λόγω μεθόδων.

10) Μέθοδοι πολλαπλής κλίμακας (multiscale methods)

A. Brandt

Πολλά προβλήματα της υπολογιστικής μηχανικής περιλαμβάνουν περισσότερες από μία κλίμακες τιμών. Επιπροσθέτως, σε αρκετές περιπτώσεις οι διαφορετικές κλίμακες αλληλεπιδρούν με έναν ιδιαίτερα περίπλοκο και μπερδεμένο τρόπο. Αυτό μπορεί να συμβεί σε δύο επίπεδα: το φυσικό επίπεδο, όταν το υπό μελέτη φαινόμενο περιλαμβάνει ταυτόχρονα μικροκλίμακα και μακροκλίμακα (για παράδειγμα, στην αερακουστική και την θραυστομηχανική) και το αριθμητικό επίπεδο, όπου η φτωχή σε ακρίβεια ανάλυση της μίας κλίμακας μπορεί να αλλοιώσει την ακρίβεια της άλλης (νόμος μετάδοσης του σφάλματος σε κλίμακες). Οι μέθοδοι που αντιμετωπίζουν τέτοιου είδους προβλήματα είναι γνωστές ως μέθοδοι πολλαπλής κλίμακας.
Διάσημη τέτοια μέθοδος είναι η τεχνική του πολλαπλού πλέγματος, που πρωτοεφευρέθηκε το 1977 από τον A. Brandt και η οποία μπορεί να εννοηθεί ως μια επαναληπτική μέθοδος αλγεβρικής επίλυσης που απαιτεί μόνο διαδικασίες του τύπου Ο(Ν). Μια άλλη προσέγγιση είναι αυτή των κυματίων η οποία, σαν τα απλά ημίτονα και συνημίτονα, συνίσταται στο "χτίσιμο" ενός αριθμού blocks από γενικές συναρτήσεις που όμως είναι τοπικές κι έχουν ειδικές ιδιότητες μετάφρασης και διαστολής (για την εύρεση των ακροτάτων τους) που τους επιτρέπουν να επιλύουν διαφορετικές κλίμακες. Η μέθοδος των κυματίων εμφανίστηκε για πρώτη φορά στην διατριβή του A. Haar to 1909, αλλά μορφοποιήθηκε στην γνωστή σήμερα μορφή της από το 1985 και μετά από τους S. Mallat, Y. Meyer και I. Daubechies. Η έρευνα στο πεδίο αυτό είναι ακόμα δυναμική.
Νεότερες μέθοδοι πολλαπλής κλίμακας που συνδυάζονται και με την F.E.M. αλλά είναι ακόμα σε ερευνητικό στάδιο περιλαμβάνουν την μέθοδο της μεταβολικής πολλαπλής κλίμακας του T. J. R. Hughes, την μέθοδο του διαχωρισμού της ενότητας των J. M. Melenk και I. Babuoka και την προσέγγιση της ιεραρχικής μοντελοποίησης της ομάδας του J. T. Oden.