Αριθμητική ανάλυση: Διαφορά μεταξύ των αναθεωρήσεων

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Gerrard ael (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Gerrard ael (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 180: Γραμμή 180:
:Τώαρα φανταστείτε ότι τα μέρη των όρων, όπως αυτές τις λειτουργίες που χρησιμοποιούνται στο πρόγραμμαthat. Το σφάλμα θα αυξηθεί καθώς προχωράει στο πρόγραμμα, εκτός αν κάποιος χρησιμοποιεί τον κατάλληλο τύπο από τις δύο λειτουργίες κάθε φορά και ένας υπολογίζει, είτε ο ''f''(''x''), είτε ο ''g''(''x'').Η επιλογή εξαρτάται από την ισοτιμία του ''x''.
:Τώαρα φανταστείτε ότι τα μέρη των όρων, όπως αυτές τις λειτουργίες που χρησιμοποιούνται στο πρόγραμμαthat. Το σφάλμα θα αυξηθεί καθώς προχωράει στο πρόγραμμα, εκτός αν κάποιος χρησιμοποιεί τον κατάλληλο τύπο από τις δύο λειτουργίες κάθε φορά και ένας υπολογίζει, είτε ο ''f''(''x''), είτε ο ''g''(''x'').Η επιλογή εξαρτάται από την ισοτιμία του ''x''.
*Το παράδειγμα πάρθηκε από τον Mathew: Numerical methods using matlab, 3rd ed.
*Το παράδειγμα πάρθηκε από τον Mathew: Numerical methods using matlab, 3rd ed.


==Τομείς της μελέτης==

Το πεδίο της αριθμητικής ανάλυσης περιλαμβάνει πολλές υπο-ειδικότητες. Μερικές από τα σημαντικότερες από αυτές είναι:

===Τιμές των λειτουργιών της πληροφορικής===

One of the simplest problems is the evaluation of a function at a given point. The most straightforward approach, of just plugging in the number in the formula is sometimes not very efficient. For polynomials, a better approach is using the [[Horner scheme]], since it reduces the necessary number of multiplications and additions. Generally, it is important to estimate and control [[round-off error]]s arising from the use of [[floating point]] arithmetic.

===Interpolation, extrapolation, and regression===

[[Interpolation]] solves the following problem: given the value of some unknown function at a number of points, what value does that function have at some other point between the given points?

[[Extrapolation]] is very similar to interpolation, except that now we want to find the value of the unknown function at a point which is outside the given points.

[[Regression analysis|Regression]] is also similar, but it takes into account that the data is imprecise. Given some points, and a measurement of the value of some function at these points (with an error), we want to determine the unknown function. The [[least squares]]-method is one popular way to achieve this.

===Solving equations and systems of equations===

Another fundamental problem is computing the solution of some given equation. Two cases are commonly distinguished, depending on whether the equation is linear or not. For instance, the equation <math>2x+5=3</math> is linear while <math>2x^2+5=3</math> is not.

Much effort has been put in the development of methods for solving [[systems of linear equations]]. Standard direct methods, i.e., methods that use some [[matrix decomposition]] are [[Gaussian elimination]], [[LU decomposition]], [[Cholesky decomposition]] for [[symmetric matrix|symmetric]] (or [[hermitian matrix|hermitian]]) and [[positive-definite matrix]], and [[QR decomposition]] for non-square matrices. [[Iterative method]]s such as the [[Jacobi method]], [[Gauss–Seidel method]], [[successive over-relaxation]] and [[conjugate gradient method]] are usually preferred for large systems. General iterative methods can be developed using a [[matrix splitting]].

[[Root-finding algorithm]]s are used to solve nonlinear equations (they are so named since a root of a function is an argument for which the function yields zero). If the function is [[derivative|differentiable]] and the derivative is known, then [[Newton's method]] is a popular choice. [[Linearization]] is another technique for solving nonlinear equations.

===Solving eigenvalue or singular value problems===
Several important problems can be phrased in terms of [[eigenvalue decomposition]]s or [[singular value decomposition]]s. For instance, the [[image compression|spectral image compression]] algorithm<ref>[http://online.redwoods.cc.ca.us/instruct/darnold/maw/single.htm The Singular Value Decomposition and Its Applications in Image Compression]</ref> is based on the singular value decomposition. The corresponding tool in statistics is called [[principal component analysis]].

===Optimization===
{{Main|Mathematical optimization}}

Optimization problems ask for the point at which a given function is maximized (or minimized). Often, the point also has to satisfy some [[Constraint (mathematics)|constraint]]s.

The field of optimization is further split in several subfields, depending on the form of the objective function and the constraint. For instance, [[linear programming]] deals with the case that both the objective function and the constraints are linear. A famous method in linear programming is the [[simplex method]].

The method of [[Lagrange multipliers]] can be used to reduce optimization problems with constraints to unconstrained optimization problems.

===Evaluating integrals===
{{Main|Numerical integration}}

Numerical integration, in some instances also known as numerical [[quadrature (mathematics)|quadrature]], asks for the value of a definite [[integral]]. Popular methods use one of the [[Newton–Cotes formulas]] (like the midpoint rule or [[Simpson's rule]]) or [[Gaussian quadrature]]. These methods rely on a "divide and conquer" strategy, whereby an integral on a relatively large set is broken down into integrals on smaller sets. In higher dimensions, where these methods become prohibitively expensive in terms of computational effort, one may use [[Monte Carlo method|Monte Carlo]] or [[quasi-Monte Carlo method]]s (see [[Monte Carlo integration]]), or, in modestly large dimensions, the method of [[sparse grid]]s.

===Differential equations===
{{main|Numerical ordinary differential equations|Numerical partial differential equations}}

Numerical analysis is also concerned with computing (in an approximate way) the solution of [[differential equation]]s, both ordinary differential equations and [[partial differential equation]]s.

Partial differential equations are solved by first discretizing the equation, bringing it into a finite-dimensional subspace. This can be done by a [[finite element method]], a [[finite difference]] method, or (particularly in engineering) a [[finite volume method]]. The theoretical justification of these methods often involves theorems from [[functional analysis]]. This reduces the problem to the solution of an algebraic equation.







==Παραπομπές==
==Παραπομπές==

Έκδοση από την 22:53, 5 Ιουνίου 2013

Βαβυλωνιακή πλάκα από 7289 π.Χ. (περ. 1800-1600 π.Χ.) με σχολιασμούς. Η προσέγγιση της τετραγωνικής ρίζας του 2 είναι τέσσερα εξηνταδικά στοιχεία, που είναι περίπου έξι δεκαδικά ψηφία. 1 + 24/60 + 51/602 + 10/603 = 1,41421296 .[1]

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

Ένα από τα αρχαιότερα μαθηματικά κείμενα είναι μία Βαβυλωνιακή πλάκα από τη Βαβυλωνιακή συλλογή Yale του 7289 π.Χ, η οποία δίνει την εξηνταδική προσέγγιση της , ως το μήκος της διαγωνίου σε ένα τετράγωνο με πλευρά μήκους 1. Το να είμαστε ικανοί να υπολογίσουμε τις πλευρές ενός τριγώνου (ως εκ τούτου το να είμαστε ικανοί να υπολογίσουμε τετραγωνικές ρίζες) είναι εξαιρετικά σημαντικό, για παράδειγμα, στην ξυλουργική και την κατασκευή.[2]

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

Η αριθμητική ανάλυση βρίσκει εφαρμογές σε όλα τα πεδία της μηχανικής και των φυσικών επιστημών, αλλά στον 21ο αιώνα, οι βιοεπιστήμες και ακόμη και οι τέχνες έχουν υιοθετήσει στοιχεία των επιστημονικών υπολογισμών. Οι συνήθεις διαφορικές εξισώσεις εμφανίζονται στην κίνηση των ουρανίων σωμάτων (πλανήτες, αστέρια και γαλαξίες), η αριθμητική γραμμική άλγεβρα είναι σημαντική για την ανάλυση δεδομένων, oι στοχαστικές διαφορικές εξισώσεις και οι αλυσίδες Markov είναι απαραίτητες για την προσομοίωση ζωντανών κυττάρων στην ιατρική και στη βιολογία.

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

Γενική εισαγωγή

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

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

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

Ιστορία

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

Για να διευκολυνθούν οι υπολογισμοί με το χέρι, μεγάλα βιβλία παρήχθησαν με τύπους και πίνακες των δεδομένων, όπως τα σημεία παρεμβολής και οι συντελεστές λειτουργίας. Χρησιμοποιώντας τους πίνακες αυτούς, υπολόγιζαν έως και 16 δεκαδικά ψηφία ή περισσότερα για ορισμένες λειτουργίες, θα μπορούσε κανείς να κοιτάζει προς τα πάνω τις τιμές για να συνδέσει σε δεδομένα τους τύπους και να επιτύχει πολύ καλές αριθμητικές εκτιμήσεις ορισμένων λειτουργιών. Η κανονική εργασία στον τομέα είναι η δημοσίευση NIST επιμελημένη από Abramowitz και Stegun, ένα 1000-και σελίδων βιβλίο ενός πολύ μεγάλου αριθμού τύπων που χρησιμοποιούμε συνήθως και τις λειτουργίες και τις αξίες τους σε πολλά σημεία. Οι τιμές λειτουργίας δεν είναι πλέον πολύ χρήσιμες όταν ένας υπολογιστής είναι διαθέσιμος, αλλά η μεγάλη λίστα των τύπων μπορεί ακόμα να είναι πολύ βολική.

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

Άμεσες και επαναληπτικές μέθοδοι

Άμεσες εναντίον επαναληπτικών μεθόδων

Εξετάστε την επίλυση του προβλήματος

3x3 + 4 = 28

για την άγνωστη ποσότητα x.

Άμεση μέθοδος
3x3 + 4 = 28.
Αφαίρεσε 4 3x3 = 24.
Διαίρεσε με το 3 x3 = 8.
Πάρε κυβική ρίζα x = 2.

Για την επαναληπτική μέθοδο, εφάρμοσε την μέθοδο διχοτόμησης σε f(x) = 3x3 − 24. Οι αρχικές τιμές είναι a = 0, b = 3, f(a) = −24, f(b) = 57.

Επαναληπτική μέθοδος
a b μέση f(μέση)
0 3 1.5 −13.875
1.5 3 2.25 10.17...
1.5 2.25 1.875 −4.22...
1.875 2.25 2.0625 2.32...

Καταλήγουμε στο αποτέλεσμα ότι λύση είναι ανάμεσα στο 1.875 και 2.0625. Ο αλγόριθμος μπορεί να επιστέψει οποιοδήποτε αριθμό μέσα σε αυτό το διάστημα με σφάλμα λιγότερο από 0.2.

Διακριτοποίηση και αριθμητική ολοκλήρωση

Σε έναν δίωρο αγώνα, μετρήσαμε την ταχύτητα του αυτοκινήτου σε τρις χρονικές στιγμές και τις καταγράψαμε στον παρακάτω πίνακα.

Χρόνος 0:20 1:00 1:40
Χλμ/ω 140 150 180

Ηδιακριτοποίηση θα μας έλεγε ότι η ταχύτητα του αυτοκινήτου ήταν σταθερή από 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 του γραμμικού προγραμματισμού. Στην πράξη, πεπερασμένη ακρίβεια χρησιμοποιείται και το αποτέλεσμα είναι μια προσέγγιση της πραγματική λύσης (με την παραδοχή της σταθερότητας).

Σε αντίθεση με τις άμεσους μεθόδους, οι επαναληπτικές μέθοδοι δεν αναμένεται να τελειώσουν σε ορισμένα βήματα. Ξεκινώντας από την αρχική υπόθεση, οι επαναληπτικές μέθοδοι αποτελούν διαδοχικές προσεγγίσεις που συγκλίνουν προς την ακριβή λύση μόνο στο όριο. Μια δοκιμή σύγκλισης προσδιορίζεται, προκειμένου να αποφασιστεί πότε μια αρκούντως ακριβή λύση (ευτυχώς) έχει βρεθεί. Ακόμη και χρησιμοποιώντας άπειρη αριθμητική ακρίβεια αυτές οι μέθοδοι δεν θα φθάσουν τη λύση μέσα σε ένα πεπερασμένο αριθμό βημάτων (γενικώς). Παραδείγματα αποτελούν η μέθοδος του Νεύτωνα, η μέθοδο διχοτόμησης, και η επανάληψη Jacobi. Στην υπολογιστική άλγεβρα πινάκων, οι επαναληπτικές μέθοδοι είναι γενικά απαραίτητες για μεγάλα προβλήματα.

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

Διακριτοποίηση

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

Παραγωγή και διάδωση των σφαλμάτων

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

Στρογγυλοποίηση

Η στρογγυλοποίηση Οφείλεται στο γεγονός ότι είναι αδύνατο να αναπαραστήσεις όλους τους πραγματικούς αριθμούς σε ένα μηχάνημα με πεπερασμένη μνήμη (το οποίο είναι ότι είναι όλοι οι πρακτικοί ψηφιακοί υπολογιστές ψηφιακοί υπολογιστές).

Αποκοπή και σφάλμα διακριτοποίησης

Τα σφάλματα αποκοπής διαπράττονται όταν μία επαναληπτική μέθοδος τερματίζεται ή όταν μια μαθηματική διαδικασία προσεγγίζεται, και η προσεγγιστική λύση διαφέρει από την ακριβή λύση. Ομοίως, η διακριτοποίηση προκαλεί ένα σφάλμα διακριτοποίησης γιατί η επίλυση του διακριτού προβλήματος δεν συμπίπτει με την επίλυση του συνεχούς προβλήματος. Για παράδειγμα, σε μια επανάληψη για να υπολογιστεί η λύση του , μετά από περίπου 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.[3] Έχουμε υπολογίσει μερικές επαναλήψεις του κάθε συστήματος σε μορφή πίνακα, με τις αρχικές εικασίες x1 = 1.4 και x1 = 1.42.


Babylonian Babylonian Method X Method 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 δεκαδικά ψηφία.
Τώαρα φανταστείτε ότι τα μέρη των όρων, όπως αυτές τις λειτουργίες που χρησιμοποιούνται στο πρόγραμμαthat. Το σφάλμα θα αυξηθεί καθώς προχωράει στο πρόγραμμα, εκτός αν κάποιος χρησιμοποιεί τον κατάλληλο τύπο από τις δύο λειτουργίες κάθε φορά και ένας υπολογίζει, είτε ο f(x), είτε ο g(x).Η επιλογή εξαρτάται από την ισοτιμία του x.
  • Το παράδειγμα πάρθηκε από τον Mathew: Numerical methods using matlab, 3rd ed.


Τομείς της μελέτης

Το πεδίο της αριθμητικής ανάλυσης περιλαμβάνει πολλές υπο-ειδικότητες. Μερικές από τα σημαντικότερες από αυτές είναι:

Τιμές των λειτουργιών της πληροφορικής

One of the simplest problems is the evaluation of a function at a given point. The most straightforward approach, of just plugging in the number in the formula is sometimes not very efficient. For polynomials, a better approach is using the Horner scheme, since it reduces the necessary number of multiplications and additions. Generally, it is important to estimate and control round-off errors arising from the use of floating point arithmetic.

Interpolation, extrapolation, and regression

Interpolation solves the following problem: given the value of some unknown function at a number of points, what value does that function have at some other point between the given points?

Extrapolation is very similar to interpolation, except that now we want to find the value of the unknown function at a point which is outside the given points.

Regression is also similar, but it takes into account that the data is imprecise. Given some points, and a measurement of the value of some function at these points (with an error), we want to determine the unknown function. The least squares-method is one popular way to achieve this.

Solving equations and systems of equations

Another fundamental problem is computing the solution of some given equation. Two cases are commonly distinguished, depending on whether the equation is linear or not. For instance, the equation is linear while is not.

Much effort has been put in the development of methods for solving systems of linear equations. Standard direct methods, i.e., methods that use some matrix decomposition are Gaussian elimination, LU decomposition, Cholesky decomposition for symmetric (or hermitian) and positive-definite matrix, and QR decomposition for non-square matrices. Iterative methods such as the Jacobi method, Gauss–Seidel method, successive over-relaxation and conjugate gradient method are usually preferred for large systems. General iterative methods can be developed using a matrix splitting.

Root-finding algorithms are used to solve nonlinear equations (they are so named since a root of a function is an argument for which the function yields zero). If the function is differentiable and the derivative is known, then Newton's method is a popular choice. Linearization is another technique for solving nonlinear equations.

Solving eigenvalue or singular value problems

Several important problems can be phrased in terms of eigenvalue decompositions or singular value decompositions. For instance, the spectral image compression algorithm[4] is based on the singular value decomposition. The corresponding tool in statistics is called principal component analysis.

Optimization

Κύριο λήμμα: Mathematical optimization

Optimization problems ask for the point at which a given function is maximized (or minimized). Often, the point also has to satisfy some constraints.

The field of optimization is further split in several subfields, depending on the form of the objective function and the constraint. For instance, linear programming deals with the case that both the objective function and the constraints are linear. A famous method in linear programming is the simplex method.

The method of Lagrange multipliers can be used to reduce optimization problems with constraints to unconstrained optimization problems.

Evaluating integrals

Κύριο λήμμα: Numerical integration

Numerical integration, in some instances also known as numerical quadrature, asks for the value of a definite integral. Popular methods use one of the Newton–Cotes formulas (like the midpoint rule or Simpson's rule) or Gaussian quadrature. These methods rely on a "divide and conquer" strategy, whereby an integral on a relatively large set is broken down into integrals on smaller sets. In higher dimensions, where these methods become prohibitively expensive in terms of computational effort, one may use Monte Carlo or quasi-Monte Carlo methods (see Monte Carlo integration), or, in modestly large dimensions, the method of sparse grids.

Differential equations

Numerical analysis is also concerned with computing (in an approximate way) the solution of differential equations, both ordinary differential equations and partial differential equations.

Partial differential equations are solved by first discretizing the equation, bringing it into a finite-dimensional subspace. This can be done by a finite element method, a finite difference method, or (particularly in engineering) a finite volume method. The theoretical justification of these methods often involves theorems from functional analysis. This reduces the problem to the solution of an algebraic equation.




Παραπομπές

  1. Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection
  2. 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
  3. This is a fixed point iteration for the equation , whose solutions include . The iterates always move to the right since . Hence converges and diverges.
  4. The Singular Value Decomposition and Its Applications in Image Compression
CC-BY-SA
Μετάφραση
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Numerical analysis της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 4.0. (ιστορικό/συντάκτες).