|
== Generacija i propagacija grešaka ==
Izučavanje grešaka sačinjava važan deo numeričke analize. Postoji nekoliko načina na koji se može uneti greška u rešenje problema.
The study of errors forms an important part of numerical analysis. There are several ways in which error can be introduced in the solution of the problem.
=== Zaokruživanje ===
[[Greška zaokruživanja|Greške zaokruživanja]] nastaju zato što je nemoguće precizno predstaviti sve [[realni broj|realne brojeve]] na mašini sa konačnom memorijom (što je slučaj sa praktično svim [[računar|digitalnim računarima]]).
[[Round-off error]]s arise because it is impossible to represent all [[real number]]s exactly on a machine with finite memory (which is what all practical [[digital computer]]s are).
=== Skraćivanje i greške diskretizacije ===
Greške [[Skraćivanje|skraćivanja]] nastaju kad se iterativni metod završi ili kad se matematička procedura aproksimira, i približno rešenje se razlikuje od tačnog rešenja. Slično tome, diskretizacija unosi [[Greška diskretizacije|grešku diskretizacije]] zato što se rešenje diskretnog problema ne poklapa sa rešenjem kontinualnog problema. Na primer, u iteraciji prikazanoj na desnoj strani da bi se izračunalo rešenje jednačine <math>''3x^3+4=28''</math>, nakon 10 ili više iteracija, zaključuje se (na primer) da je koren oko 1,99. Stoga imamo grešku skraćivanja od 0,01.
[[Truncation]] errors are committed when an iterative method is terminated or a mathematical procedure is approximated, and the approximate solution differs from the exact solution. Similarly, discretization induces a [[discretization error]] because the solution of the discrete problem does not coincide with the solution of the continuous problem. For instance, in the iteration in the sidebar to compute the solution of <math>''3x^3+4=28''</math>, after 10 or so iterations, we conclude that the root is roughly 1.99 (for example). We therefore have a truncation error of 0.01.
Nakon generisanja greške, ona se generalno uvećava tokom proračuna. Na primer, već smo napomenuli da operacija + na kalkulatoru (ili računaru) nije precizna. Iz toga sledi da je sabiranje tipa a+b+c+d+e još nepreciznije.
Once an error is generated, it will generally propagate through the calculation. For instance, we have already noted that the operation + on a calculator (or a computer) is inexact. It follows that a calculation of the type a+b+c+d+e is even more inexact.
Gore je pomenuto da dolazi do greške skraćivanja, kad se aproksimira matematička procedura. Poznato je da je za preciznu integraciju funkcije neophodno naći zbir beskonačno velikog broja trapezoida. U praksi se međutim može odrediti jedino zbir konačnog broja trapezoida, i stoga dolazi do aproksimacije matematičke procedure. Slično tome, da bi se diferencirala funkcija, diferencijalni element treba da teži nuli, dok je numerički moguće jedino izabrati konačnu vrednost diferencijalnog elementa.
What does it mean when we say that the truncation error is created when we approximate a mathematical procedure? We know that to integrate a function exactly requires one to find the sum of infinite trapezoids. But numerically one can find the sum of only finite trapezoids, and hence the approximation of the mathematical procedure. Similarly, to differentiate a function, the differential element approaches to zero but numerically we can only choose a finite value of the differential element.
=== Numerička stabilnost i dobro postulirani problemi ===
[[Numerička stabilnost]] je važan pojam u numeričkoj analizi. Algoritam se smatra ''numerički stabilnim'' ako se greška, nezavisno od izvora, znatno ne uvećava tokom proračuna. Do toga dolazi ako je problem ''stabilan'', što znači da se rešenje malo menja sa malom promenom ulaznih podataka. U kontrastu s tim, ako je problem ''nestabilan'', onda svaka mala greška u ulaznim podacima narasta u veliku grešku u rešenju.
[[Numerical stability]] is an important notion in numerical analysis. An algorithm is called ''numerically stable'' if an error, whatever its cause, does not grow to be much larger during the calculation. This happens if the problem is ''[[condition number|well-conditioned]]'', meaning that the solution changes by only a small amount if the problem data are changed by a small amount. To the contrary, if a problem is ''ill-conditioned'', then any small error in the data will grow to be a large error.
SoOriginalni anproblem algorithmi thatalgoritam solveskoji ase well-conditionedkoriste problemza mayrešavanje beproblema eithermogu numericallyda stablebudu or''stabilni'' i/ili ''nestabilni'', ili bilo numericallykoja unstablekombinacija. AnStoga artalgoritam ofkoji numericalrešava analysisstabilni isproblem tomože findda abude stablebilo algorithmnumerički forstabilan solvingili anumerički well-posednestabilan. mathematicalUmetnost problemnumeričke analize je da se nađe stabilan algoritam za rešavanje dobro postavljenog matematičkog problema. ForNa instanceprimer, computingizračunavanje the squarekvadratnog rootkorena ofiz 2 ( whichkoji isje roughlyoko 1 .,41421) isje a well-posedstabilan problem. ManyMnogi algorithmsalgoritmi solverešavaju thistaj problem bypočevši startingod withinicijalne an initial approximationaproksimacije ''x''<sub>1</sub> tood <math>\sqrt{2}</math>, forna instanceprimer ''x''<sub>1</sub>=1 .,4, andi thenzatim computingizračunavaju improvedpoboljšanje guessespretpostavke ''x''<sub>2</sub>, ''x''<sub>3</sub>, etc.. OneJedan suchtakav methodmetod isje the famouspoznati [[ BabylonianMetode methodizračunavanja kvadratnih korena|Vavilonski metod]], whichkoji isje givendat bysa ''x''<sub>''k''+1</sub> = ''x<sub>k</sub>''/2 + 1/''x<sub>k</sub>''. AnotherJoš iterationjedan iterativni pristup, whichkoji wećemo willzvati call MethodMetod X, isje givendat bysa ''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> WeIzračunali havesmo calculatednekoliko a few iterations of eachiteracija schemeovog inalgoritma tableu formdonjoj belowtabeli, withsa initialinicijalnim guessespretpostavkama ''x''<sub>1</sub> = 1 .,4 andi ''x''<sub>1</sub> = 1 .,42. ▼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"
|-
! Vavilonski metod
! Babylonian
! Vavilonski metod
! Babylonian
! MethodMetod X
! MethodMetod X
|-
| ''x''<sub>1</sub> = 1.4
|}
Može se uočiti da Vaviloniski metod brzo konvergira nezavisno od inicijalne pretpostavke, dok Metod X konvergira ekstremno sporo sa inicijalnom pretpostavkom od 1,4 i divergira počevši od inicijalne pretpostavke 1,42. Stoga je Vavilonski metod numerički stabilan, dok je Metod X numerički nestabilan.
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.
:'''Numerička stabilnost''' je zavisna od broja značajnih cifara koje data mašina podržava, ako se koristi mašina koja radi sa prve četiri cifre pokretnog zareza dolazi do znatnog gubitka preciznosti
:'''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>
:Ako se uporede rezultati od
:If we compare the results of
:: <math> f(500)=500 \left(\sqrt{501}-\sqrt{500} \right)=500 \left(22.3830-22.3607 \right)=500(0.0223)=11.1500</math>
:andi
:<math>
\begin{alignat}{3}g(500)&=\frac{500}{\sqrt{501}+\sqrt{500}}\\
\end{alignat}
</math>
: uočava se da '''[[gubitak značaja]]''', koji se takođe naziva '''poništavanja oduzimanjem''', ima ogromni efekat na rezultate, mada su funkcije ekvivalentne; da bi se pokazalo da su ekvivalentne jednostavno se polazi od f(x) i završava sa g(x), tako da je
: by looking to the two results above, 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 \left(\sqrt{x+1}-\sqrt{x} \right)\\
\end{alignat}</math>
:TheIstinska truevrednost valuerezultata for the result isje 11.,174755..., whichšto isje exactlytačno ''g''(500) = 11.,1748 after roundingnakon thezaokruživanja resultrezultata tona 4 decimaldecimalna digitsmesta.
:NowSad imaginezamislimo thatda lotsse ofkoristi termsmnoštvo likečlanova thesekao functionsšto aresu usedove infunkcije theu programprogramu; thegreške errorće willse increaseuvećavati astokom onerada proceeds in the programprograma, unlessosim oneako usesse thekoristi suitablepodesna formula ofza theove twodve functionsfunkcije eachsvaki timeput onekad evaluatesse eitherizračunavaju ''f''(''x''), orili ''g''(''x''); the choice isizbor dependentje onzavistan theod paritypariteta of ''x''.
*ThePrimer exampleje isuzet taken fromiz: Mathew; Numerical methods using matlab, 3rd ed.
== Oblasti izučavanja ==
| 