Αριθμητική ανάλυση
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. |
Αριθμητική ανάλυση είναι η μελέτη των αλγορίθμων οι οποίοι χρησιμοποιούν μαθηματικές προσεγγίσεις (σε αντιδιαστολή με τους γενικούς συμβολικούς υπολογιστικούς) για την επίλυση προβλημάτων της μαθηματικής ανάλυσης (όπως διακρίνεται από διακριτά μαθηματικά).
Ένα από τα αρχαιότερα μαθηματικά κείμενα είναι μία βαβυλωνιακή πλάκα από τη βαβυλωνιακή συλλογή του Γέιλ (YBC 7289), η οποία δίνει την εξηνταδική προσέγγιση της , ως το μήκος της διαγωνίου σε ένα τετράγωνο με πλευρά μήκους 1. Το να είμαστε ικανοί να υπολογίσουμε τις πλευρές ενός τριγώνου (ως εκ τούτου το να είμαστε ικανοί να υπολογίσουμε τετραγωνικές ρίζες) είναι εξαιρετικά σημαντικό, για παράδειγμα, στην ξυλουργική και την κατασκευή.[2]
Η αριθμητική ανάλυση συνεχίζει τη μακρά αυτή παράδοση των πρακτικών μαθηματικών υπολογισμών. Όπως και με την προσέγγιση των Βαβυλωνίων της , η σύγχρονη αριθμητική ανάλυση δεν επιδιώκει ακριβείς απαντήσεις , επειδή τέτοιες λύσεις είναι συχνά αδύνατο να επιτευχθούν στην πράξη. Αντί για αυτό, ένα μεγάλο μέρος της αριθμητικής ανάλυσης ασχολείται με την απόκτηση προσεγγιστικών λύσεων διατηρώντας παράλληλα εύλογα όρια σχετικά με τα σφάλματα.
Η αριθμητική ανάλυση βρίσκει εφαρμογές σε όλα τα πεδία της μηχανικής και των φυσικών επιστημών, αλλά στον 21ο αιώνα, οι βιοεπιστήμες και ακόμη και οι τέχνες έχουν υιοθετήσει στοιχεία των επιστημονικών υπολογισμών. Οι συνήθεις διαφορικές εξισώσεις εμφανίζονται στην κίνηση των ουρανίων σωμάτων (πλανήτες, αστέρια και γαλαξίες), η αριθμητική γραμμική άλγεβρα είναι σημαντική για την ανάλυση δεδομένων, oι στοχαστικές διαφορικές εξισώσεις και οι αλυσίδες Μάρκοφ είναι απαραίτητες για την προσομοίωση ζωντανών κυττάρων στην ιατρική και στη βιολογία.
Πριν από την έλευση των σύγχρονων υπολογιστών η εφαρμογή των αριθμητικών μεθόδων συχνά εξαρτιόνταν από την παρεμβολή του ανθρώπου και γινόταν σε μεγάλους έντυπους πίνακες. Από τα μέσα του 20ού αιώνα, οι υπολογιστές υπολογίζουν τις απαιτούμενες λειτουργίες αντί των ανθρώπων. Αυτοί οι ίδιοι τύποι παρεμβολής συνεχίζουν να χρησιμοποιούνται ως μέρος του λογισμικού των αλγορίθμων για την επίλυση διαφορικών εξισώσεων.
Γενική εισαγωγή
ΕπεξεργασίαΟ γενικός στόχος του πεδίου της αριθμητικής ανάλυσης είναι ο σχεδιασμός και η ανάλυση τεχνικών που δίνουν σε προσέγγιση αλλά ακριβείς λύσεις σε δύσκολα προβλήματα, η ποικιλία των οποίων φαίνεται παρακάτω:
- Σύνθετες αριθμητικές μέθοδοι είναι απαραίτητοι για να είναι η αριθμητική πρόγνωση καιρού εφικτή.
- Ο υπολογισμός της τροχιάς ενός διαστημικού οχήματος απαιτεί την ακριβή αριθμητική επίλυση ενός συστήματος συνήθων διαφορικών εξισώσεων.
- Βιομηχανίες οχημάτων μπορούν να βελτιώσουν την ασφάλεια στις συγκρούσεις των οχημάτων τους, χρησιμοποιώντας προσομοιώσεις σε υπολογιστή των τροχαίων ατυχημάτων. Οι εν λόγω προσομοιώσεις αποτελούνται κυρίως από την επίλυση μερικών διαφορικών εξισώσεων αριθμητικά.
- Τα κεφάλαια Χεντζ (ιδιωτικά επενδυτικά κεφάλαια) χρησιμοποιούν εργαλεία από όλους τους τομείς της αριθμητικής ανάλυσης στην προσπάθεια να υπολογίσουν της αξίας των αποθεμάτων και των παραγώγων τους με μεγαλύτερη ακρίβεια από ότι οι άλλοι συμμετέχοντες στην αγορά.
- Οι αεροπορικές εταιρείες χρησιμοποιούν πολύπλοκους αλγόριθμους βελτιστοποίησης για να αποφασίσουν τις τιμές των εισιτηρίων, τις αναθέσεις πληρωμάτων σε αεροσκάφος και τις ανάγκες των καυσίμων. Ιστορικά τέτοιοι αλγόριθμοι αναπτύχθηκαν εντός του πεδίου της επιχειρησιακής έρευνας.
- Οι ασφαλιστικές εταιρείες χρησιμοποιούν αριθμητικές μεθόδους για την αναλογιστική ανάλυση.
Το υπόλοιπο αυτής της ενότητας περιγράφει διάφορα σημαντικά θέματα της αριθμητικής ανάλυσης.
Ιστορία
ΕπεξεργασίαΤο πεδίο της αριθμητικής ανάλυσης προηγείται της εφεύρεσης των σύγχρονων υπολογιστών κατά πολλούς αιώνες. Η γραμμική παρεμβολή ήταν ήδη σε χρήση πάνω από 2000 χρόνια πριν. Πολλοί μεγάλοι μαθηματικοί του παρελθόντος ήταν απορροφημένοι με την αριθμητική ανάλυση, όπως είναι προφανές από τα ονόματα των σημαντικών αλγορίθμων, όπως η μέθοδος του Νεύτωνα, η παρεμβολή Λαγκράνζ, η μέθοδος απαλοιφής Γκάους και η μέθοδος Όιλερ.
Για να διευκολυνθούν οι υπολογισμοί με το χέρι, μεγάλα βιβλία παρήχθησαν με τύπους και πίνακες των δεδομένων, όπως τα σημεία παρεμβολής και οι συντελεστές λειτουργίας. Χρησιμοποιώντας τους πίνακες αυτούς, υπολόγιζαν έως και 16 δεκαδικά ψηφία ή περισσότερα για ορισμένες λειτουργίες, θα μπορούσε κανείς να κοιτάζει προς τα πάνω τις τιμές για να συνδέσει σε δεδομένα τους τύπους και να επιτύχει πολύ καλές αριθμητικές εκτιμήσεις ορισμένων λειτουργιών. Η κανονικοποιημένη εργασία στον τομέα είναι η δημοσίευση NIST επιμελημένη από τους Αμπράμοβιτς και Στεγκούν, ένα 1000-και σελίδων βιβλίο ενός πολύ μεγάλου αριθμού τύπων που χρησιμοποιούμε συνήθως και τις λειτουργίες και τις αξίες τους σε πολλά σημεία. Οι τιμές λειτουργίας δεν είναι πλέον πολύ χρήσιμες όταν ένας υπολογιστής είναι διαθέσιμος, αλλά η μεγάλη λίστα των τύπων μπορεί ακόμα να είναι πολύ βολική.
Η μηχανική αριθμομηχανή επίσης αναπτύχθηκε ως ένα εργαλείο για υπολογισμό με το χέρι. Αυτοί οι υπολογιστές είχαν εξελιχθεί σε ηλεκτρονικούς υπολογιστές τη δεκαετία του 1940, και έπειτα ανακαλύφθηκε ότι αυτοί οι υπολογιστές ήταν επίσης χρήσιμοι για διοικητικούς σκοπούς. Όμως, η ανακάλυψη του υπολογιστή επηρέασε επίσης τον τομέα της αριθμητικής ανάλυσης, δεδομένου ότι τώρα πλέον θα μπορούσαν να γίνουν και πιο πολύ πολύπλοκοι υπολογισμοί.
Άμεσες και επαναληπτικές μέθοδοι
Επεξεργασία
Άμεσες εναντίον επαναληπτικών μεθόδων Εξετάστε την επίλυση του προβλήματος
για την άγνωστη ποσότητα x.
Για την επαναληπτική μέθοδο, εφάρμοσε την μέθοδο διχοτόμησης σε f(x) = 3x3 − 24. Οι αρχικές τιμές είναι a = 0, b = 3, f(a) = −24, f(b) = 57.
Καταλήγουμε στο αποτέλεσμα ότι λύση είναι ανάμεσα στο 1.875 και 2.0625. Ο αλγόριθμος μπορεί να επιστέψει οποιοδήποτε αριθμό μέσα σε αυτό το διάστημα με σφάλμα λιγότερο από 0.2. Διακριτοποίηση και αριθμητική ολοκλήρωσηΕπεξεργασίαΣε έναν δίωρο αγώνα, μετρήσαμε την ταχύτητα του αυτοκινήτου σε τρεις χρονικές στιγμές και τις καταγράψαμε στον παρακάτω πίνακα.
Ηδιακριτοποίηση θα μας έλεγε ότι η ταχύτητα του αυτοκινήτου ήταν σταθερή από 0:00 έως 0:40, μετά από 0:40 έως 1:20 και τέλος από 1:20 έως 2:00. Για παράδειγμα η συνολική απόσταση που ταξίδεψε στα πρώτα 40 λεπτά είναι περίπου (2/3h × 140 km/h) = 93.3 Χλμ. Αυτό θα μας επέτρεπε να εκτιμήσουμε την συνολική απόσταση ως εξής 93.3 χλμ + 100 kχλμ m + 120 χλμ = 313.3 χλμ , αυτό είναι παράδειγμα αριθμητικής ολοκλήρωσης χρησιμοποιώντας άθροισμα Ρήμαν. |
Οι άμεσες μέθοδοι υπολογίζουν τη λύση ενός προβλήματος σε πεπερασμένο αριθμό βημάτων. Αυτές οι μέθοδοι θα δώσουν σαφή απάντηση, εάν έχουν πραγματοποιηθεί με άπειρη αριθμητική ακρίβεια. Τα παραδείγματα περιλαμβάνουν την μέθοδος απαλοιφής του Γκάους, την παραγοντοποίηση QR για την επίλυση συστημάτων γραμμικών εξισώσεων, και τη μέθοδο simplex του γραμμικού προγραμματισμού. Στην πράξη, πεπερασμένη ακρίβεια χρησιμοποιείται και το αποτέλεσμα είναι μια προσέγγιση της πραγματική λύσης (με την παραδοχή της σταθερότητας).
Σε αντίθεση με τις άμεσους μεθόδους, οι επαναληπτικές μέθοδοι δεν αναμένεται να τελειώσουν σε ορισμένα βήματα. Ξεκινώντας από την αρχική υπόθεση, οι επαναληπτικές μέθοδοι αποτελούν διαδοχικές προσεγγίσεις που συγκλίνουν προς την ακριβή λύση μόνο στο όριο. Μια δοκιμή σύγκλισης προσδιορίζεται, προκειμένου να αποφασιστεί πότε μια αρκούντως ακριβή λύση (ευτυχώς) έχει βρεθεί. Ακόμη και χρησιμοποιώντας άπειρη αριθμητική ακρίβεια αυτές οι μέθοδοι δεν θα φθάσουν τη λύση μέσα σε ένα πεπερασμένο αριθμό βημάτων (γενικώς). Παραδείγματα αποτελούν η μέθοδος του Νεύτωνα, η μέθοδο διχοτόμησης, και η επανάληψη Γιακόμπι. Στην υπολογιστική άλγεβρα πινάκων, οι επαναληπτικές μέθοδοι είναι γενικά απαραίτητες για μεγάλα προβλήματα.
Οι επαναληπτικές μέθοδοι είναι πιο συχνές από τις άμεσες μεθόδους στην αριθμητική ανάλυση. Μερικές μέθοδοι είναι άμεσες, κατ 'αρχήν, αλλά συνήθως χρησιμοποιούνται σαν να μην ήταν, π.χ. GMRES και η μέθοδος συζυγούς κλίσης. Για τις μεθόδους αυτές, ο αριθμός των βημάτων που απαιτούνται για να ληφθεί η ακριβή λύση είναι τόσο μεγάλος, ώστε η προσέγγιση είναι αποδεκτή με τον ίδιο τρόπο όπως και για μια επαναληπτική μέθοδο.
Διακριτοποίηση
ΕπεξεργασίαΕπιπλέον, τα συνεχή προβλήματα πρέπει μερικές φορές να αντικατασταθούν από ένα διακριτό πρόβλημα του οποίου η λύση ειναι γνωστή το κατά προσέγγιση από το συνεχές πρόβλημα. Αυτή η πρόοδος λέγεται διακριτοποίηση. Για παράδειγμα, η λύση μιας διαφορικής εξίσωσης είναι μία μαθηματική λειτουργία. Αυτή η λειτουργία πρέπει να εκπροσωπείται από ένα πεπερασμένο σύνολο δεδομένων, για παράδειγμα από την αξία του σε ένα πεπερασμένο αριθμό σημείων του τομέα του , ακόμη και αν αυτός ο τομέας ανήκει στη Θεωρία συνόλων.
Παραγωγή και διάδωση των σφαλμάτων
ΕπεξεργασίαΗ μελέτη των σφαλμάτων αποτελεί ένα σημαντικό μέρος της αριθμητικής ανάλυσης. Υπάρχουν διάφοροι τρόποι με τους οποίους ένα σφάλμα μπορεί να εισαχθεί στην λύση του προβλήματος.
Στρογγυλοποίηση
ΕπεξεργασίαΗ στρογγυλοποίηση οφείλεται στο γεγονός ότι είναι αδύνατο να αναπαραστήσεις όλους τους πραγματικούς αριθμούς σε ένα μηχάνημα με πεπερασμένη μνήμη (πράγμα που ισχύει για όλους τους ψηφιακούς υπολογιστές).
Αποκοπή και σφάλμα διακριτοποίησης
ΕπεξεργασίαΤα σφάλματα αποκοπής διαπράττονται όταν μία επαναληπτική μέθοδος τερματίζεται ή όταν μια μαθηματική διαδικασία προσεγγίζεται, και η προσεγγιστική λύση διαφέρει από την ακριβή λύση. Ομοίως, η διακριτοποίηση προκαλεί ένα σφάλμα διακριτοποίησης γιατί η επίλυση του διακριτού προβλήματος δεν συμπίπτει με την επίλυση του συνεχούς προβλήματος. Για παράδειγμα, σε μια επανάληψη για να υπολογιστεί η λύση του x3 + 4 = 28, μετά από περίπου 10 επαναλήψεις, καταλήγουμε στο συμπέρασμα ότι η ρίζα είναι περίπου 1,99. Έχουμε, λοιπόν, ένα σφάλμα αποκοπής της τάξης του 0,01. Μόλις δημιουργείται σφάλμα, γενικά θα φανερώνεται μέσω του υπολογισμού. Για παράδειγμα, έχουμε ήδη επισημάνει ότι η λειτουργία + σε έναν υπολογιστή τσέπης (ή σε έναν ηλεκτρονικό υπολογιστή) είναι ανακριβής. Επομένως, ένας υπολογισμός του τύπου α + β + γ + δ + ε είναι ακόμη πιο ανακριβής. Τι σημαίνει όταν λέμε ότι το σφάλμα αποκοπής δημιουργείται όταν υπολογίζουμε κατά προσέγγιση μια μαθηματική διαδικασία; Γνωρίζουμε ότι για να ενσωματώσουμε μια λειτουργία ακριβώς απαιτείται κάποιος να βρει το άθροισμα άπειρων τραπεζίων. Αλλά αριθμητικά μπορεί κανείς να βρει το άθροισμα πεπερασμένων μόνο τραπεζίων. Ομοίως, για να διαφοροποιηθεί μια λειτουργία, το στοιχείο απόκλισης πλησιάζει στο μηδέν αλλά, αριθμητικά, μπορούμε μόνο να επιλέξουμε μία πεπερασμένη τιμή στοιχείου διαφοροποίησης.
Αριθμητική σταθερότητα και καλά δημιουργούμενα προβλήματα
ΕπεξεργασίαΗ αριθμητική σταθερότητα είναι μία σημαντική έννοια στην αριθμητική ανάλυση. Ένας αλγόριθμος ονομάζεται αριθμητικά σταθερός αν ένα λάθος, ανεξάρτητα απ' την αιτία του, δεν τείνει να γίνει πολύ μεγαλύτερο κατά τη διάρκεια του υπολογισμού. Αυτό συμβαίνει αν ένα πρόβλημα είναι καλά κατασκευασμένο αριθμητικά, πράγμα που σημαίνει ότι η λύση του αλλάζει μόνο κατά ένα μικρό ποσό, αν τα δεδομένα του προβλήματος αλλάξουν κατά ένα μικρό ποσό. Αντιθέτως αν ένα πρόβλημα ειναι άσχημα κατασκευασμένο, τότε κάθε μικρό λάθος στα δεδομένα θα τείνει να γίνει ένα μεγάλο λάθος.
Τόσο το αρχικό πρόβλημα όσο και ο αλγόριθμος που χρησιμοποιούνται για την επίλυση αυτού του προβλήματος μπορούν να είναι καλά κατασκευασμένα και/ή άσχημα κατασκευασμένα, και κάθε συνδιασμός είναι πιθανός.
Έτσι, ένας αλγόριθμος που λύνει ένα καλά κατασκευασμένο πρόβλημα μπορεί να είναι είτε αριθμητικά σταθερός είτε αριθμητικά ασταθής. Μια τέχνη της αριθμητικής ανάλυσης είναι η εύρεση ένας σταθερού αλγόριθμου για την επίλυση ενός καλά κατασκευασμένου μαθηματικού προβλήματος. Για παράδειγμα, ο υπολογισμός της τετραγωνικής ρίζας του 2, (η οποίο είναι περίπου 1,41421) είναι ένα καλά ορισμένο πρόβλημα. Πολλοί αλγόριθμοι λύνουν αυτό το πρόβλημα, ξεκινώντας με μια αρχική προσέγγιση του x1 ως , για παραράδειγμα x1=1.4, και υπολογίζοντας στη συνέχεια τις βελτιωτικές εικασίες x2, x3, κτλ... Μία τέτοια μέθοδος είναι η γνωστή ως Bαβυλώνια μέθοδος, η οποία δίνεται από τύπο xk+1 = xk/2 + 1/xk. Μία άλλη επανάληψη, την οποία θα ονομάζουμε μέθοδο Χ, δίνεται από τον τύπο xk + 1 = (xk2−2)2 + xk. Έχουμε υπολογίσει μερικές επαναλήψεις του κάθε συστήματος σε μορφή πίνακα, με τις αρχικές εικασίες x1 = 1.4 και x1 = 1.42.
Βαβυλώνια | Βαβυλώνια | Μέθοδος X | Μέθοδος X |
---|---|---|---|
x1 = 1,4 | x1 = 1,42 | x1 = 1,4 | x1 = 1,42 |
x2 = 1,4142857... | x2 = 1,41422535... | x2 = 1,4016 | x2 = 1,42026896 |
x3 = 1,414213564... | x3 = 1,41421356242... | x3 = 1,4028614... | x3 = 1,42056... |
... | ... | ||
x1000000 = 1,41421... | x28 = 7280,2284... |
Παρατηρήστε ότι η Βαβυλώνια μέθοδος συγκλίνει γρήγορα, ανεξάρτητα από την αρχική υπόθεση, ενώ η μέθοδος X συγκλίνει πολύ αργά με την αρχική εικασία 1,4 και αποκλίνει με την αρχική εικασία 1,42.
Ως εκ τούτου, η Βαβυλώνια μέθοδος είναι αριθμητικά σταθερή, ενώ η μέθοδος Χ είναι αριθμητικά ασταθής.
Η αριθμητική σταθερότητα επηρεάζεται απ΄τον αριθμό των σημαντικών ψηφίων που κρατάει η μηχανή, αν χρησιμοποιούμε μια μηχανή που κρατάει για τα τέσσερα πρώτα ψηφία κινητή υποδιαστολή. Ένα καλό παράδειγμα για την απώλεια της σταθερότητας δίνεται από αυτές τις δύο ισοδύναμες λειτουργίες:
- Αν συγκρίνουμε τα αποτελέσματα του
- και του
- Παρατηρώντας τα δύο παραπάνω αποτελέσματα, συνειδητοποιούμε ότι η απώλεια σταθερότητας, η οποία ονομάζεται επίσης αφαιρετική ακύρωση, έχει τεράστια επίδραση στα αποτελέσματα, ακόμη και αν και οι δύο λειτουργίες είναι ισοδύναμες. Για να δείξουμε ότι αυτές είναι ισοδύναμες πρέπει απλά να αρχίσουμε με την f(x) και να τελειώσουμε με την g(x), και έτσι:
- Η αληθινή τιμή του αποτελέσματος είναι 11,174755..., η οποία είναι ακριβώς g(500) = 11,1748 μετά τη στρογγυλοποίηση του αποτελέσματος σε 4 δεκαδικά ψηφία.
- Τώρα φανταστείτε ότι τα μέρη των όρων, όπως αυτές τις λειτουργίες που χρησιμοποιούνται στο πρόγραμμα. Το σφάλμα θα αυξηθεί καθώς προχωράει στο πρόγραμμα, εκτός αν κάποιος χρησιμοποιεί τον κατάλληλο τύπο από τις δύο λειτουργίες κάθε φορά και υπολογίζει είτε το f(x), είτε το g(x). Η επιλογή εξαρτάται από την ισοτιμία του x.
- Το παράδειγμα πάρθηκε από τον Mathew: Numerical methods using matlab, 3rd ed.
Τομείς της μελέτης
ΕπεξεργασίαΠαρεμβολή: Παρατηρείται η μεταβολή της θερμοκρασίας από 20 βαθμούς κελσίου έως τους 14 βαθμούς σε διάστημα 2 ωρών. Η γραμμική παρεμβολή των δεδομένων αυτών θα συμπέραινε πως ήταν 17 βαθμοί στο διάστημα της 1 ώρας, και 18.5 σε διάστημα 1.5 ώρας. Παρέκταση: Αν το ΑΕΠ μιας χώρας αυξάνονταν κατά μέσο όρο με ρυθμό 5% ανά έτος, και το προηγούμενο έτος ήταν 10 δισεκατομμύρια ευρώ, εκτιμάται πως με αυτόν τον ρυθμό πως το επόμενο έτος θα είναι 10.5 δισ. ευρώ.Παλινδρόμηση: Στην γραμμική παλινδρόμηση, εάν υπάρχουν ν σημεία, γίνεται ο υπολογισμός μιας γραμμής η οποία περνάει όσο το δυνατό πλησιέστερα από τα ν αυτά σημεία.Βελτιστοποίηση: Αν ένα ποτήρι λεμονάδας πωλείται για 1 ευρώ, και πωλούνται 197 ποτήρια ημερησίως, για κάθε αύξηση του ενός λεπτού (0.01) μπορεί να πωληθεί ένα ποτήρι λιγότερο την ημέρα. Αν το ποτήρι κόστιζε 1.48,5 ευρώ, θα γινόταν μεγιστοποίηση του κέρδους, ωστόσο καθώς δεν μπορεί να υπάρξει διαίρεση του λεπτού, γίνεται η πώληση με τιμή 1.48 ή 1.49 ώστε να επιτευχθεί το μέγιστο κέρδος τω 220.52 ευρώ τη μέρα.Διαφορική εξίσωση: Αν τοποθετηθούν 100 ανεμιστήρες στη μια άκρη του δωματίου και ενεργοποιηθούν, και αφεθεί ένα φτερό στη μέση του δωματίου, η κατεύθυνση που θα ακολουθήσει το φτερό από τα διάφορα ρεύματα είναι πολύ περίπλοκη. Μια τεχνική θα ήταν η μέτρηση της ταχύτητας με την οποία κινείται ο αέρας κοντά στο φτερό κάθε δευτερόλεπτο, και να θεωρηθεί πως το φτερό θα κινείται με την ταχύτητα αυτή σε ευθεία γραμμή για ένα δευτερόλεπτο. Μετά από 1 δευτερόλεπτο επαναλαμβάνεται η παραπάνω διαδικασία. Η τεχνική αυτή ονομάζεται μέθοδος του Όιλερ. |
Το πεδίο της αριθμητικής ανάλυσης περιλαμβάνει πολλές υπο-ειδικότητες. Μερικές από τα σημαντικότερες από αυτές είναι:
Τιμές των λειτουργιών της πληροφορικής
ΕπεξεργασίαΈνα από τα πιο απλά προβλήματα είναι η αξιολόγηση της συνάρτησης σε ένα δεδομένο σημείο. Η πιο απλή προσέγγιση, το να συνδέεις μόνο τον αριθμό στον τύπο είναι μερικές φορές όχι πολύ αποτελεσματική. Για τα πολυώνυμα, μια καλύτερη προσέγγιση χρησιμοποιεί το σύστημα/σχήμα Horner, δεδομένου ότι μειώνει τον αναγκαίο αριθμό των πολλαπλασιασμών και προσθηκών. Γενικά, είναι σημαντικό να εκτιμούμε και να ελέγχουμε αριθμητικά τις στρογγυλοποιήσεις σφαλμάτων που προκύπτουν από τη χρήση της κινητής υποδιαστολής.
Παρεμβολή, παρέκταση, και παλινδρόμηση
ΕπεξεργασίαΗ παρεμβολή επιλύει το ακόλουθο πρόβλημα: δεδομένης της τιμής κάποιας άγνωστης συνάρτησης σε ορισμένα σημεία, τι τιμή έχει η συνάρτηση αυτή σε κάποιο άλλο σημείο μεταξύ των δεδομένων σημείων?
Η παρέκταση είναι πολύ όμοια με την παρεμβολή, με εξαίρεση ότι τώρα θέλουμε να βρούμε την αξία της άγνωστης συνάρτησης σε ένα σημείο που είναι έξω από τα δεδομένα σημεία.
Η παλινδρόμηση είναι επίσης παρόμοια, αλλά λαμβάνει υπόψη το γεγονός ότι τα δεδομένα δεν είναι ακριβή. Λαμβάνοντας υπόψη ορισμένα σημεία, και μια μέτρηση της τιμής κάποιας συνάρτησης σε αυτά τα σημεία (με σφάλμα), θέλουμε να προσδιορίσουμε την άγνωστη συνάρτηση. Η μέθοδος ελαχίστων τετραγώνων είναι ένας δημοφιλής τρόπος για να επιτευχθεί αυτό.
Επίλυση εξισώσεων και συστημάτων εξισώσεων
ΕπεξεργασίαΈνα άλλο βασικό πρόβλημα είναι ο υπολογισμός της λύσης κάποιας δεδομένη εξίσωσης. Δύο περιπτώσεις διακρίνονται συνήθως, ανάλογα με το αν η εξίσωση είναι γραμμική ή όχι. Για παράδειγμα,η εξίσωση είναι γραμμική ενώ η δεν είναι.
Πολλή προσπάθεια έχει γίνει για την ανάπτυξη μεθόδων για την επίλυση συστημάτων γραμμικών εξισώσεων. Πρότυπες άμεσες μέθοδοι, i.e., μέθοδοι που χρησιμοποιούν κάποια αποσύνθεση μαθηματικών μοντέλων είναι οι ελλειπτικές του Gauss, οι αποσύνθεσης LU , οι αποσύνθεσης Cholesky για συμμετρικά μοντέλα (ή ερμιτιανά μοντέλα) και θετικά-οριστικά μοντέλα, και οι αποσύνθεσης QR για μη τετραγωνικούς πίνακες. Οι επαναληπτικές μέθοδοι όπως η μέθοδος Jacobi, η μέθοδος Gauss–Seidel, διαδοχικές υπερβολικής χαλάρωσης και κλίσης συζυγούς μεθόδους προτιμώνται για μεγάλα συστήματα. Γενικά οι επαναληπτικές μέθοδοι μπορούν να αναπτυχθούν χρησιμοποιώντας ε΄να μαθηματικό μοντέλο.
Οι αλγόριθμοι Root-finding χρησιμοποιούνται στην επίλυση μη γραμμικών εξισώσεων (ονομάστηκαν έτσι από μία ρίζα μιας συνάρτησης για την οποία η λειτουργία δίνει μηδέν). Εάν η λειτουργία είναι παραγωγίσιμη και η παράγωγος είναι γνωστή, τότε η μέθοδος του Νεύτωνα είναι μία δημοφιλής επιλογή. Η γραμμικοποίηση είναι άλλη μια τεχνική για την επίλυση μη γραμμικών εξισώσεων.
Επίλυση ιδιοτιμών ή ιδιόμορφα προβλήματα αξιών
ΕπεξεργασίαΑρκετά σημαντικά προβλήματα μπορούν να διατυπωθούν από την άποψη της αποσύνθεσης ιδιοτιμών ή αποσύνθεσης αξιών. Για παράδειγμα, η φασματική συμπίεσης της εικόνας ενός αλγορίθμου[3] βασίζεται στην αποσύνθεση ιδιαζουσών ιδιοτιμών. Το αντίστοιχο εργαλείο στη στατιστική ονομάζεται ανάλυση σε κύριες συνιστώσες.
Λογισμικό
ΕπεξεργασίαΑπό τα τέλη του εικοστού αιώνα, οι περισσότεροι αλγόριθμοι εφαρμόζονται σε μια ποικιλία γλωσσών προγραμματισμού. Η αποθήκη Netlib περιέχει διάφορες συλλογές από λογισμικά ρουτίνας για αριθμητικά προβλήματα, κυρίως σε Fortran και C. Διαφημιστικά προϊόντα που εφαρμόζουν πολλούς διαφορετικούς αριθμητικούς αλγορίθμους περιλαμβάνουν τις αριθμητικές βιβλιοθήκες IMSL και τις αριθμητικές βιβλιοθήκες αλγορίθμων του ομίλου NAG. Μια ελεύθερη εναλλακτική λύση είναι η επιστημονική βιβλιοθήκη GNU.
Υπάρχουν πολλές δημοφιλής αριθμητικές εφαρμογές πληροφορικής όπως η MATLAB, η S-PLUS, η LabVIEW, και η IDL καθώς επίσης και ελεύθερες και ανοιχτές εναλλακτικές πηγές όπως η FreeMat, η Scilab, η GNU Octave (παρόμοια με τη Matlab), η IT++ (μια C++ βιβλιοθήκη), η R (παρόμοια με τη S-PLUS) και ορισμένες παραλλαγές της Python. Η απόδοση ποικίλλει ευρέως: ενώ ο φορέας και το μαθηματικό μοντέλο πράξεων είναι συνήθως γρήγορα, οι βρόχοι διανυσμάτων μπορεί να διαφέρουν στην ταχύτητα κατά περισσότερο από μία τάξη μεγέθους.[4][5]
Πολλά αλγεβρικά συστήματα υπολογιστών όπως το Mathematica επίσης επωφελούνται από τη διαθεσιμότητα της αυθαίρετης αριθμητικής ακρίβειας η οποία μπορεί να προσφέρει πιο ακριβή αποτελέσματα.
Επίσης, οποιοδήποτε λογισμικό υπολογιστικών φύλλων μπορεί να χρησιμοποιηθεί για να λύσει απλά προβλήματα που αφορούν στην αριθμητική ανάλυση.
Παραπομπές
Επεξεργασία- ↑ «Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection». Αρχειοθετήθηκε από το πρωτότυπο στις 13 Αυγούστου 2012. Ανακτήθηκε στις 20 Φεβρουαρίου 2012.
- ↑ The New Zealand Qualification authority specifically mentions this skill in document 13004 version 2, dated 17 October 2003 titled CARPENTRY THEORY: Demonstrate knowledge of setting out a building
- ↑ «The Singular Value Decomposition and Its Applications in Image Compression». Αρχειοθετήθηκε από το πρωτότυπο στις 4 Οκτωβρίου 2006. Ανακτήθηκε στις 5 Ιουνίου 2013.
- ↑ «Speed comparison of various number crunching packages». Αρχειοθετήθηκε από το πρωτότυπο στις 5 Οκτωβρίου 2006. Ανακτήθηκε στις 6 Ιουνίου 2013.
- ↑ Comparison of mathematical programs for data analysis Αρχειοθετήθηκε 2016-05-18 στο Portugese Web Archive Stefan Steinhaus, ScientificWeb.com
Σχετική βιβλιογραφία
ΕπεξεργασίαΣτα ελληνικά
Επεξεργασία- Γ. Δ. Ακρίβης, Β. Α. Δουγαλής: Εισαγωγή στην Αριθμητική Ανάλυση. Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο, Τέταρτη έκδοση, 2010, πέμπτη ανατύπωση, 2017.
- Μ. Ν. Βραχάτης: Αριθμητική Ανάλυση: Εισαγωγή. Εκδόσεις Κλειδάριθμος, Αθήνα, 2011.
Ξενόγλωσση
Επεξεργασία- Golub, Gene H. και Charles F. Van Loan (1986). Matrix Computations, Third Edition (Johns Hopkins University Press, ISBN 0-8018-5413-X).
- Higham, Nicholas J. (1996). Accuracy and Stability of Numerical Algorithms (Society for Industrial and Applied Mathematics, ISBN 0-89871-355-2).
- Hildebrand, F. B. (1974). Introduction to Numerical Analysis (2nd έκδοση). McGraw-Hill. ISBN 0-07-028761-9.
- Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation. Addison Wesley. ISBN 0-201-73499-0.
- Wilkinson, J.H. (1965). The Algebraic Eigenvalue Problem (Clarendon Press).
- Kahan, W. (1972). "A survey of error-analysis," in Info. Processing 71 (Proc. IFIP Congress 71 in Ljubljana), vol. 2, pp. 1214–39, North-Holland Publishing, Amsterdam. (examples of the importance of accurate arithmetic).
- Trefethen, Lloyd N. (2006). "Numerical analysis", 20 pages. In: Timothy Gowers and June Barrow-Green (editors), Princeton Companion of Mathematics, Princeton University Press.
Εξωτερικοί σύνδεσμοι
ΕπεξεργασίαΣτα ελληνικά
ΕπεξεργασίαΣε άλλες γλώσσες
ΕπεξεργασίαΠεριοδικά
- Numerische Mathematik, volumes 1-66, Springer, 1959-1994 (searchable; pages are images). (Αγγλικά) (Γερμανικά)
- Numerische Mathematik at SpringerLink, volumes 1-112, Springer, 1959–2009
- SIAM Journal on Numerical Analysis[νεκρός σύνδεσμος], volumes 1-47, SIAM, 1964–2009
Κείμενα
- Hazewinkel, Michiel, επιμ.. (2001), «Numerical analysis», Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://www.encyclopediaofmath.org/index.php?title=p/n120130
- Numerical Recipes, William H. Press
- First Steps in Numerical Analysis, R.J.Hosking, S.Joe, D.C.Joyce, and J.C.Turner
- CSEP (Computational Science Education Project) Αρχειοθετήθηκε 2017-08-01 στο Wayback Machine., U.S. Department of Energy
Εκπαιδευτικό υλικό
- Numerical Methods, Stuart Dalziel University of Cambridge
- Lectures on Numerical Analysis, Dennis Deturck and Herbert S. Wilf, University of Pennsylvania
- Numerical methods, John D. Fenton, University of Karlsruhe
- Numerical Methods for Science, Technology, Engineering and Mathematics, Autar Kaw University of South Florida
- Numerical Analysis Project, John H. Mathews, California State University, Fullerton
- Numerical Methods - Online Course, Aaron Naiman Jerusalem College of Technology
- Numerical Methods for Physicists, Anthony O’Hare, Oxford University
- Lectures in Numerical Analysis, R. Radok, Mahidol University
- Introduction to Numerical Analysis for Engineering, Henrik Schmidt, Massachusetts Institute of Technology
- Numerical Methods for time-dependent Partial Differential Equations Αρχειοθετήθηκε 2014-10-26 στο Wayback Machine., J.W. Haverkort, based on a course by P.A. Zegeling, Utrecht University
- Numerical Analysis for Engineering, D. W. Harder, University of Waterloo