Αριθμητική ανάλυση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 110:
Μόλις δημιουργείται σφάλμα, γενικά θα φανερώνεται μέσω του υπολογισμού. Για παράδειγμα, έχουμε ήδη επισημάνει ότι η λειτουργία + σε έναν υπολογιστή τσέπης (ή σε έναν ηλεκτρονικό υπολογιστή) είναι ανακριβής.Επομένως, ένας υπολογισμός του τύπου α + β + γ + δ + ε είναι ακόμη πιο ανακριβής.
Τι σημαίνει όταν λέμε ότι το σφάλμα αποκοπής δημιουργείται όταν υπολογίζουμε κατά προσέγγιση μια μαθηματική διαδικασία? Γνωρίζουμε ότι για να ενσωματώσουμε μια λειτουργία ακριβώς απαιτείται κάποιος να βρει το άθροισμα άπειρων τραπεζίων.Αλλά αριθμητικά μπορεί κανείς να βρει το άθροισμα πεπερασμένων μόνο τραπεζίων. Ομοίως, για να διαφοροποιηθεί μια λειτουργία, το στοιχείο απόκλισης πλησιάζει στο μηδέν αλλά, αριθμητικά,μπορούμε μόνο να επιλέξουμε μία πεπερασμένη τιμή στοιχείου διαφοροποίησης.
===Αριθμητική σταθερότητα και καλά δημιουργούμενα προβλήματα===
Η αριθμητική σταθερότητα είναι μία σημαντική έννοια στην αριθμητική ανάλυση. Ένας αλγόριθμος ονομάζεται αριθμητικά σταθερός αν ένα λάθος, ανεξάρτητα απ' την αιτία του, δεν τείνει να γίνει πολύ μεγαλύτερο κατά τη διάρκεια του υπολογισμού. Αυτό συμβαίνει αν ένα πρόβλημα είναι καλά κατασκευασμένο αριθμητικά, πράγμα που σημαίνει ότι η λύση του αλλάζει μόνο κατά ένα μικρό ποσό, αν τα δεδομένα του προβλήματος αλλάξουν κατά ένα μικρό ποσό. Αντιθέτως αν ένα πρόβλημα ειναι άσχημα κατασκευασμένο, τότε κάθε μικρό λάθος στα δεδομένα θα τείνει να είναι ένα μεγάλο λάθος.
Both the original problem and the algorithm used to solve that problem can be ''well-conditioned'' and/or ''ill-conditioned'', and any combination is possible.
So an algorithm that solves a well-conditioned problem may be either numerically stable or numerically unstable. An art of numerical analysis is to find a stable algorithm for solving a well-posed mathematical problem. For instance, computing the square root of 2 (which is roughly 1.41421) is a well-posed problem. Many algorithms solve this problem by starting with an initial approximation ''x''<sub>1</sub> to <math>\sqrt{2}</math>, for instance ''x''<sub>1</sub>=1.4, and then computing improved guesses ''x''<sub>2</sub>, ''x''<sub>3</sub>, etc.. One such method is the famous [[Babylonian method]], which is given by ''x''<sub>''k''+1</sub> = ''x<sub>k</sub>''/2 + 1/''x<sub>k</sub>''. Another iteration, which we will call Method X, is given by ''x''<sub>''k'' + 1</sub> = (''x''<sub>''k''</sub><sup>2</sup>−2)<sup>2</sup> + ''x''<sub>''k''</sub>.<ref>This is a [[fixed point iteration]] for the equation <math>x=(x^2-2)^2+x=f(x)</math>, whose solutions include <math>\sqrt{2}</math>. The iterates always move to the right since <math>f(x)\geq x</math>. Hence <math>x_1=1.4<\sqrt{2}</math> converges and <math>x_1=1.42>\sqrt{2}</math> diverges.</ref> We have calculated a few iterations of each scheme in table form below, with initial guesses ''x''<sub>1</sub> = 1.4 and ''x''<sub>1</sub> = 1.42.
{| class="wikitable"
|-
! Babylonian
! Babylonian
! Method X
! Method X
|-
| ''x''<sub>1</sub> = 1.4
| ''x''<sub>1</sub> = 1.42
| ''x''<sub>1</sub> = 1.4
| ''x''<sub>1</sub> = 1.42
|-
| ''x''<sub>2</sub> = 1.4142857...
| ''x''<sub>2</sub> = 1.41422535...
| ''x''<sub>2</sub> = 1.4016
| ''x''<sub>2</sub> = 1.42026896
|-
| ''x''<sub>3</sub> = 1.414213564...
| ''x''<sub>3</sub> = 1.41421356242...
| ''x''<sub>3</sub> = 1.4028614...
| ''x''<sub>3</sub> = 1.42056...
|-
|
|
| ...
| ...
|-
|
|
| ''x''<sub>1000000</sub> = 1.41421...
| ''x''<sub>28</sub> = 7280.2284...
|}
Observe that the Babylonian method converges fast regardless of the initial guess, whereas Method X converges extremely slowly with initial guess 1.4 and diverges for initial guess 1.42. Hence, the Babylonian method is numerically stable, while Method X is numerically unstable.
:'''Numerical stability''' is affected by the number of the significant digits the machine keeps on, if we use a machine that keeps on the first four floating-point digits, a good example on loss of significance is given by these two equivalent functions
:<math>
f(x)=x\left(\sqrt{x+1}-\sqrt{x}\right)
\text{ and } g(x)=\frac{x}{\sqrt{x+1}+\sqrt{x}}.
</math>
:If we compare the results of
:: <math> f(500)=500(\sqrt{501}-\sqrt{500})=500(22.3830-22.3607)=500(0.0223)=11.1500</math>
:and
:<math>
\begin{alignat}{3}g(500)&=\frac{500}{\sqrt{501}+\sqrt{500}}\\
&=\frac{500}{22.3830+22.3607}\\
&=\frac{500}{44.7437}=11.1748
\end{alignat}
</math>
: by looking to the two above results, we realize that '''[[loss of significance]]''' which is also called '''Subtractive Cancelation''' has a huge effect on the results, even though both functions are equivalent; to show that they are equivalent simply we need to start by f(x) and end with g(x), and so
:: <math> \begin{alignat}{4}
f(x)&=x(\sqrt{x+1}-\sqrt{x})\\
& =x(\sqrt{x+1}-\sqrt{x})\frac{(\sqrt{x+1}+\sqrt{x})}{(\sqrt{x+1}+\sqrt{x})}\\
&=x\frac{((\sqrt{x+1})^2-(\sqrt{x})^2)}{(\sqrt{x+1}+\sqrt{x})}
&=\frac {x}{(\sqrt{x+1}+\sqrt{x})}
\end{alignat}</math>
:The true value for the result is 11.174755..., which is exactly ''g''(500) = 11.1748 after rounding the result to 4 decimal digits.
:Now imagine that lots of terms like these functions are used in the program; the error will increase as one proceeds in the program, unless one uses the suitable formula of the two functions each time one evaluates either ''f''(''x''), or ''g''(''x''); the choice is dependent on the parity of ''x''.
*The example is taken from Mathew; Numerical methods using matlab, 3rd ed.
| |||