Probability theory

Author: Michal Wardzynski
Supervisor : Igor Ohirko
Facility: Kazimierz Pułaski University of Technology and Humanities in Radom

Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set of axioms. Typically these axioms formalise probability in terms of a probability space, which assigns a measure taking values between 0 and 1, termed the probability measure, to a set of outcomes called the sample space. Any specified subset of these outcomes is called an event.

Central subjects in probability theory include discrete and continuous random variables, probability distributions, and stochastic processes, which provide mathematical abstractions of non-deterministic or uncertain processes or measured quantities that may either be single occurrences or evolve over time in a random fashion.

Although it is not possible to perfectly predict random events, much can be said about their behaviour. Two major results in probability theory describing such behaviour are the law of large numbers and the central limit theorem.

As a mathematical foundation for statistics, probability theory is essential to many human activities that involve quantitative analysis of data. Methods of probability theory also apply to descriptions of complex systems given only partial knowledge of their state, as in statistical mechanics. A great discovery of twentieth century physics was the probabilistic nature of physical phenomena at atomic scales, described in quantum mechanics.

History

The mathematical theory of probability has its roots in attempts to analyze games of chance by Gerolamo Cardano in the sixteenth century, and by Pierre de Fermat and Blaise Pascal in the seventeenth century (for example the „problem of points”). Christiaan Huygens published a book on the subject in 1657 and in the 19th century, Pierre Laplace completed what is today considered the classic interpretation.

Initially, probability theory mainly considered discrete events, and its methods were mainly combinatorial. Eventually, analytical considerations compelled the incorporation of continuous variables into the theory.

This culminated in modern probability theory, on foundations laid by Andrey Nikolaevich Kolmogorov. Kolmogorov combined the notion of sample space, introduced by Richard von Mises, and measure theory and presented his axiom system for probability theory in 1933. This became the mostly undisputed axiomatic basis for modern probability theory; but, alternatives exist, such as the adoption of finite rather than countable additivity by Bruno de Finetti.

Treatment

Most introductions to probability theory treat discrete probability distributions and continuous probability distributions separately. The more mathematically advanced measure theory-based treatment of probability covers the discrete, continuous, a mix of the two, and more.

Motivation

Consider an experiment that can produce a number of outcomes. The set of all outcomes is called the sample space of the experiment. The power set of the sample space (or equivalently, the event space) is formed by considering all different collections of possible results. For example, rolling an honest die produces one of six possible results. One collection of possible results corresponds to getting an odd number. Thus, the subset {1,3,5} is an element of the power set of the sample space of die rolls. These collections are called events. In this case, {1,3,5} is the event that the die falls on some odd number. If the results that actually occur fall in a given event, that event is said to have occurred.

Probability is a way of assigning every „event” a value between zero and one, with the requirement that the event made up of all possible results (in our example, the event {1,2,3,4,5,6}) be assigned a value of one. To qualify as a probability distribution, the assignment of values must satisfy the requirement that if you look at a collection of mutually exclusive events (events that contain no common results, e.g., the events {1,6}, {3}, and {2,4} are all mutually exclusive), the probability that any of these events occurs is given by the sum of the probabilities of the events.

The probability that any one of the events {1,6}, {3}, or {2,4} will occur is 5/6. This is the same as saying that the probability of event {1,2,3,4,6} is 5/6. This event encompasses the possibility of any number except five being rolled. The mutually exclusive event {5} has a probability of 1/6, and the event {1,2,3,4,5,6} has a probability of 1, that is, absolute certainty.

Discrete probability distributions

The Poisson distribution, a discrete probability distribution.

Discrete probability theory deals with events that occur in countablesample spaces.

Examples: Throwing dice, experiments with decks of cards, random walk, and tossing coins

Classical definition: Initially the probability of an event to occur was defined as number of cases favorable for the event, over the number of total outcomes possible in an equiprobable sample space: see Classical definition of probability.

For example, if the event is „occurrence of an even number when a die is rolled”, the probability is given by {\tfrac {3}{6}}={\tfrac {1}{2}}, since 3 faces out of the 6 have even numbers and each face has the same probability of appearing.

Modern definition: The modern definition starts with a finite or countable set called the sample space, which relates to the set of all possible outcomes in classical sense, denoted by \Omega . It is then assumed that for each element x\in \Omega \,, an intrinsic „probability” value f(x)\, is attached, which satisfies the following properties:

  1. {f(x)\in [0,1]{\mbox{ for all }}x\in \Omega \,;
  2. \sum _{x\in \Omega }f(x)=1\,.

That is, the probability function f(x) lies between zero and one for every value of x in the sample space Ω, and the sum of f(x) over all values x in the sample space Ω is equal to 1. An event is defined as any subset E\, of the sample space \Omega \,. The probability of the event E\, is defined as

P(E)=\sum _{x\in E}f(x)\,.

So, the probability of the entire sample space is 1, and the probability of the null event is 0.

The function f(x)\, mapping a point in the sample space to the „probability” value is called a probability mass functionabbreviated as pmf. The modern definition does not try to answer how probability mass functions are obtained; instead it builds a theory that assumes their existence

Continuous probability distributions

The normal distribution, a continuous probability distribution.

Continuous probability theory deals with events that occur in a continuous sample space.

Classical definition: The classical definition breaks down when confronted with the continuous case. See Bertrand’s paradox.

Modern definition: If the outcome space of a random variable X is the set of real numbers (\mathbb {R} ) or a subset thereof, then a function called the cumulative distribution function (or cdfF\, exists, defined by F(x)=P(X\leq x)\,. That is, F(x) returns the probability that X will be less than or equal to x.

The cdf necessarily satisfies the following properties.

  1. F\, is a monotonically non-decreasing, right-continuous function;
  2. \lim _{x\rightarrow -\infty }F(x)=0\,;
  3. \lim _{x\rightarrow \infty }F(x)=1\,.

If F\, is absolutely continuous, i.e., its derivative exists and integrating the derivative gives us the cdf back again, then the random variable X is said to have a probability density function or pdf or simply density f(x)={\frac {dF(x)}{dx}}\,.

For a set E\subseteq \mathbb {R} , the probability of the random variable X being in E\, is

P(X\in E)=\int _{x\in E}dF(x)\,.

In case the probability density function exists, this can be written as

P(X\in E)=\int _{x\in E}f(x)\,dx\,.

Whereas the pdf exists only for continuous random variables, the cdf exists for all random variables (including discrete random variables) that take values in \mathbb {R} \,.

These concepts can be generalized for multidimensional cases on \mathbb {R} ^{n} and other continuous sample spaces.

Measure-theoretic probability theory

The raison d’être of the measure-theoretic treatment of probability is that it unifies the discrete and the continuous cases, and makes the difference a question of which measure is used. Furthermore, it covers distributions that are neither discrete nor continuous nor mixtures of the two.

An example of such distributions could be a mix of discrete and continuous distributions—for example, a random variable that is 0 with probability 1/2, and takes a random value from a normal distribution with probability 1/2. It can still be studied to some extent by considering it to have a pdf of (\delta [x]+\varphi (x))/2, where \delta [x] is the Dirac delta function.

Other distributions may not even be a mix, for example, the Cantor distribution has no positive probability for any single point, neither does it have a density. The modern approach to probability theory solves these problems using measure theory to define the probability space:

Given any set \Omega \, (also called sample space) and a σ-algebra {\mathcal {F}}\, on it, a measure P\, defined on {\mathcal {F}}\, is called a probability measure if P(\Omega )=1.\,

If {\mathcal {F}}\, is the Borel σ-algebra on the set of real numbers, then there is a unique probability measure on {\mathcal {F}}\, for any cdf, and vice versa. The measure corresponding to a cdf is said to be induced by the cdf. This measure coincides with the pmf for discrete variables and pdf for continuous variables, making the measure-theoretic approach free of fallacies.

The probability of a set E\, in the σ-algebra {\mathcal {F}}\, is defined as

P(E)=\int _{\omega \in E}\mu _{F}(d\omega )\,

where the integration is with respect to the measure \mu _{F}\, induced by F\,.

Along with providing better understanding and unification of discrete and continuous probabilities, measure-theoretic treatment also allows us to work on probabilities outside \mathbb {R} ^{n}, as in the theory of stochastic processes. For example, to study Brownian motion, probability is defined on a space of functions.

When it’s convenient to work with a dominating measure, the Radon-Nikodym theorem is used to define a density as the Radon-Nikodym derivative of the probability distribution of interest with respect to this dominating measure. Discrete densities are usually defined as this derivative with respect to a counting measure over the set of all possible outcomes. Densities for absolutely continuous distributions are usually defined as this derivative with respect to the Lebesgue measure. If a theorem can be proved in this general setting, it holds for both discrete and continuous distributions as well as others; separate proofs are not required for discrete and continuous distributions.

 

Reklamy

WYBRANE ASPEKTY ZASTOSOWANIA SYMULACJI KOMPUTEROWYCH W NANOTECHNOLOGII

Michał Wardzyński , Ihor Ohirko

Uniwersytet Technologiczno-Humanistyczny im. Kazimierza Pułaskiego w Radomiu

Modelowanie numeryczne jest dziś jedną z najbardziej obiecujących i rozwijających się dziedzin inżynierii. Główną jego zaletą jest możliwość uzyskania rozwiązania danego problemu, który inaczej należałoby rozwiązać za pomocą metod doświadczalnych. W ostatnich latach obserwuje się gwałtowny rozwój nanotechnologii. Nanotechnologia jest dziedziną nauki zajmującą się materiałami i układami, których struktury i elementy wykazują osobliwe właściwości doskonale rozwinięte fizycznie, chemicznie i biologicznie, a zachodzące w nich procesy spowodowane są ich nanorozmiarami. Celem nanotechnologii jest wykorzystanie tych właściwości poprzez osiągnięcie kontroli na poziomie atomowym i molekularnym cząsteczek oraz opracowanie skutecznego sposobu ich wytwarzania i wykorzystania. Zachowanie cząsteczek w ”nanoskali” jest nie do przewidzenia w porównaniu z tym obserwowanym w większych cząsteczkach. Możliwość zmniejszenia wymiarów cząsteczki do nanoskali prowadzi do uzyskania wyjątkowych własności. Projektowanie takich urządzeń i materiałów wymaga jednak rozwoju adekwatnych narzędzi obliczeniowych. W odniesieniu do zagadnień klasycznych (w skali makro) modelowanie i symulacje numeryczne są szeroko stosowane w praktycznych badaniach naukowych, projektach inżynieryjno – technicznych oraz przemysłowych w skali globalnej. Prototypy modeli fi- zycznych są obecnie ulepszane i czasami zastępowane modelami komputerowymi, które mają swoją ekonomiczną przewagę. Do obliczeń wielkości fizycznych układów służą komercyjne solvery działające w oparciu o dyskretyzację klasycznych równań zachowania, opisujących ośrodek jako ciągły. W zagadnieniach związanych z nanotechnologią model ośrodka ciągłego nie może być stosowany, jak również metody obliczeniowe oparte na tym modelu. Symulacje komputerowe stały się tu doskonałym narzędziem umożliwiającym rozwią- zanie wielu problemów związanych z fizyką statyczną, chemią materiałową oraz biofizyką. Ponadto symulacja komputerowa bywa jedyną rozsądną alternatywą analizy zjawiska tam, gdzie budowa wiarygodnego modelu analitycznego oraz wykonanie eksperymentu jest niemożliwe lub bardzo trudne

W porównaniu z obserwowanymi cząsteczkami w skali makro zachowanie nanocząsteczek jest nie do przewidzenia. Modelowanie i symulacje numeryczne są powszechnie stosowane do zagadnień klasycznych (w skali makro). Model ośrodka oraz obliczenia oparte na tym modelu nie mogą być stosowane w zagadnieniach związanych z nanotechnologią. Zastosowanie tu znalazły symulacje komputerowe, które znakomicie umożliwiają znalezienie rozwiązania dla problemów związanych z biofizyką, fizyką statyczną oraz chemią materiałową. Symulacja komputerowa doskonale zastępuję analizę zjawiska tam gdzie jest ona niemożliwa lub bardzo trudna do wykonania, najczęściej przy budowie wiarygodnego modelu analitycznego czy wykonaniu eksperymentu. Czasami jedynie przy zastosowaniu symulacji komputerowej można zbadać dokładnie aspekty złożonych systemów pomimo tego, że techniki eksperymentalne dotyczące szczegółowych informacji są zadowalające. W celu przeprowadzenia symulacji komputerowej należy wprowadzić parametry wejściowe, które są charakterystyczne dla modelowanego systemu. Takie parametry uzyskujemy z teoretycznych rozwiązań lub z danych eksperymentalnych.

Wyróżniamy dwie klasy metod symulacji: deterministyczne oraz stochastyczne. Podstawą metod deterministycznych jest wykorzystanie dynamiki wewnętrznej modelu do przemieszczania układu w przestrzeni fazowej. Aby przemieszczać układ poprzez przestrzeń fazową należy sformułować równania ruchu i całkować je po czasie. Metoda stochastyczna opiera się ono na fakcie, że
w istocie konieczne jest wyznaczenie wartości jedynie konfiguracyjnej części zagadnienia. Część pędową można zawsze scałkować i wyłączyć. Przejście z jednej konfiguracji do następnej, która w ujęciu deterministycznym była określona przez wartości pędów, w metodach stochastycznych jest realizowane w wyniku ewolucji probabilistycznej za pośrednictwem procesu Markowa.

Dynamika molekularna

Metoda numerycznego całkowania równań ruchu układów wielocząsteczkowych nazywana jest dynamiką molekularną. Układy składające się z cząstek podlegają klasycznym prawom ruchu, natomiast mikroskopowe parametry opisujące stan układu obliczane są jako średnie po trajektorii w przestrzeni fazowej.

Opis działania dynamiki molekularnej:
– dla każdej cząstki należy obliczyć siłę na nią działającą, pochodzącą od pozostałych cząstek ;
– korzystając z obliczonych sił, przy znajomości położenia cząstek, obliczamy nowe położenia i pędy każdej cząstki stosując numeryczne równanie ruchu Newtona;
– wyznaczając parametry mikroskopowe (prędkości i położenia), obliczamy wielkości makroskopowe (temperaturę, energię całkowitą i kinetyczną, współczynnik dyfuzji, ciepło właściwe, lepkość, itp.).

Dynamika molekularna wymaga szczegółowego opisu molekuł oraz oddziałujących między nimi sił. Łączenie równań ruchu złożonych systemów cząstek i i kroków czasowych (od kilku do kilku milionów) jest efektem symulacji dynamiki molekularnej. Trajektorie podążających cząsteczek podczas obliczeń obrazują rzeczywiste molekularne trajektorie. Dynamika molekularna opisuje tempo rozwoju zbioru oddziałujących atomów.

W dynamice molekularnej stosujemy prawa mechaniki klasycznej :

Fi(t) = miai(t)

Ponieważ każdy atom i w systemie został utworzony przez N atomów, mi jest masą atomu,

ai = d2 ri/dt2

jest przyspieszeniem Fi siłą oddziaływującą dzięki oddziaływaniu z innymi atomami.

Dynamika molekularna jest techniką deterministyczną: podanie początkowych pozycji i prędkości oraz czasu późniejszej ewolucji są dokładnie określone. Atomy poruszają się oddziaływując wzajemnie na siebie, wędrują dookoła (jeśli system jest płynem), drgają i prawdopodobnie omijają system w przypadku wolnej przestrzeni. Zatem w pewnym sensie oddziaływają tak jak zrobiłyby to atomy w rzeczywistej substancji.

Chcąc wyrazić siłę pochodzącą od atomu α z molekuły i na atom β z molekuły j jako fiαjβ , wtedy cała siła oddziałująca na molekułę i to :

Fi = ∑j ∑αfiα jẞ 

 Natomiast moment obrotowy jest wyrażany jako:

Ni = ∑α (r – Ri)× f

gdzie:

Ri = 1/Mi  ∑α mr

jest środkiem masy molekuły i.

Ruch jest określony (wyrażony) przez równania Newtona-Eulera:

Mi Ȑi = F,

Ii · ωi − ω× I· ω= Ni,

gdzie ωjest prędkością kątową molekuły.

Powszechnie stosowane jest przedstawianie położenia molekuł za pomocą kwaternionów, które są bardziej preferowane od kątów Eulera.

Dynamika molekularna- algorytmy 

Motorem programu Dynamiki Molekularnej jest jego algorytm integrujący wymagany do łączenia równań ruchu oddziałujących wzajemnie cząstek i podążania za ich trajektorią. Algorytmy łączące bazują na określonych różnych metodach dyskretyzujących czas i krok czasowy równy Δt. Znając położenia poszczególnych cząstek i ich niektóre pochodne po czasie t (szczegóły zależą od typu algorytmu), schemat łączenia daje te same wielkości w późniejszym czasie (t + Δt).

Najprostszym przypadkiem algorytmu dynamiki molekularnej jest zastosowanie do obliczania sił równania ruchu Newtona:

Fi(t) = miai(t)

gdzie  -oznacza siłę, -jest masą,  – przyspieszeniem atomu i.

Siła działająca na atom i może zostać obliczona bezpośrednio poprzez zróżniczkowanie funkcji energii potencjalnej po położeniu :

∂V/∂ri = m(∂2ri/∂ti2)

Powyższe równania są klasycznymi równaniami deterministycznymi. Oznacza to, że jeśli znane są warunki początkowe, dla dowolnej chwili czasowej t znane są położenia i prędkości atomów. Współrzędne i prędkości atomów całego przebiegu symulacji noszą nazwę trajektorii (ang. trajecory).

Metoda rozwiązywania takiego równania jest zawsze taka sama: znając położenia i prędkości atomów w chwili t, oblicza się położenia i prędkości w chwili t+Δt. Najczęściej stosowaną metodą całkowania równań ruchu jest algorytm Verleta.

Podstawowym założeniem algorytmu jest to, aby wyprowadzić dwa rozwinięcia Taylora trzeciego rzędu dla położeń r(t), jednego wstecz a drugiego w przód, w czasie.

Oznaczając prędkość jako v, przyśpieszenie jako a i b jest trzecią pochodną r po czasie t, otrzymujemy:

r (t + ∆t) = r(t) +v(t)∆t + 1/2a(t)∆t2 + (1/6) b(t)∆t3 + O (∆t)

r (t – ∆t) = r(t) – v(t)∆t – 1/2a(t)∆t2 – (1/6) b(t)∆t3 + 0 (∆t)

Zsumowanie obu wyrażeń daje:

r(t + Δt)=2r(t) − r(t − Δt) + a(t)Δ+ O(Δ )

To jest podstawowa forma algorytmu Verleta. Ponieważ łączymy równania Newtona, a(t) jest tylko siłą podzieloną przez masę, jak również siła jest funkcją odwrotną położenia r(t):

a(t) = – (1/m)∆v(r(t))

Prędkości nie są potrzebne, aby policzyć trajektorie, ale są pomocne do oszacowania energii kinetycznej (całkowitej energii). Prędkości te mogą być otrzymane z wzoru:

v(t) = [r(t+∆t) – r(t-∆t)]/ 2∆t

Ten algorytm jest jednocześnie na tyle prosty, dokładny i stabilny, aby wyjaśnić jego dużą popularność wśród symulatorów dynamiki molekularnej.

Ważnym parametrem każdej symulacji dynamiki molekularnej jest krok czasowy. Aby jak najlepiej wykorzystać czas procesora należałoby użyć dużego kroku czasowego. Jednakże takie postępowanie może prowadzić do niedokładności, a nawet niestabilności algorytmu.

Przedstawiony referat w dużym skrócie opisuje zasadę działania symulacji komputerowej, dotyczącej badania przepływu wody w nanokanałach, wykorzystującej metodę Dynamiki Molekularnej. Na podstawie przedstawionych wyników można wywnioskować, że prezentowana metoda jest dobrze dostosowana dla nanoprzepływów, w wyniku czego jest bardzo przydatna w nano-fizyce i nanotechnologii

Źródło : http://www.pwszchelm.pl/kis/publikacje/VII/Kucaba.pdf
Heermann W.D., Computer Simulation Method in Theoretical Physics, Springer Verlag, Berlin 1990.

Grotendorst J., Marx D., Muramatsu A., Quantum Simulations of Complex Many-Body Systems: From Theory to Algorithms, John von Neumann Institute for Computing, Jlich, NIC Series, Vol. 10,ISBN 3-00-009057-6, pp. 211-254, 2002.

Metody numeryczne dla informatyków

2016

Witam wszystkich uczestników naszych zajęć i zapraszam na wspaniałą przygodę na pograniczu matematyki stosowanej i informatyki! W zadaniach obliczeniowych wykorzystujących methody numeryczne musimy zmierzyć się nie tylko z oczywistymi restrykcjami narzucanymi nam przez reguły matematyczne, ale także z ograniczeniami używanych komputerów oraz niedogodnościami i wymaganiami stawianymi przez praktykę.

Nasz przedmiot, rzecz jasna, będzie koncentrować się na matematycznych aspektach zadań obliczeniowych i algorytmów numerycznych. Namiastką prawdziwych zastosowań będą zajęcia laboratoryjne, gdzie będziemy mogli zmierzyć się z implementacją metod i zobaczyć je w działaniu.

Zaliczenie ćwiczeń

Szczegółowe zasady zaliczenia i oceny końcowej z przedmiotu znajdują się na stronie wykładowcy. Należy pamiętać, że warunkiem przystąpienia do egzaminu jest zaliczenie ćwiczeń. Łącznie można z ćwiczeń uzyskać 50 punktów, które razem z 50 punktami z egzaminu będą stanowiły podstawę dla oceny końcowej z przedmiotu. Do wyniku z ćwiczeń będą brane pod uwagę:

Prace domowe (30 punktów)
Będzie 5 serii po mniej więcej 6 zadań. Prace będą sprawdzone przez 3 zapowiedziane kartkówki (max. 20 min), po 2 zadania za 5 pkt każde. Terminy kartkówek: 2016-11-25, 2016-12-09, 2017-01-20.
Zadania programistyczne (15 punktów)
Będą 3 projekty (zadania), za 5 punktów każdy. Projekty (źródła) należy nadesłać mailem w terminie zgodnie z treścią zadania. Każdy dzień nieusprawiedliwionego spóźnienia zmniejsza przyznaną liczbę punktów za projekt o 2. Projekty mogą być dodatkowo sprawdzane w trakcie labu wypadającego bezpośrednio po terminie.
Obecności (5 pkt)
Na dobry początek każdy dostaje 5 pkt z LABu. Każda nieusprawiedliwiona nieobecność na LABie zmniejsza liczbę punktów o 1.

Nie istnieje możliwość pisania kartkówki i oddawania zadania programistycznego po terminie, z wyjątkiem przypadków usprawiedliwionej nieobecności.

Stosowanie metod numerycznych

Metody numeryczne

Metody numeryczne są to sposoby rozwiązywania złożonych problemów matematycznych za pomocą narzędzi obliczeniowych udostępnianych przez popularne języki programowania.

Metody numeryczne są jedną z tych dziedzin matematyki stosowanej, których zastosowanie w praktyce jest powszechne. Wykorzystywane są wówczas, gdy badany problem nie ma w ogóle rozwiązania analitycznego (danego wzorami), lub korzystanie z takich rozwiązań jest uciążliwe ze względu na ich złożoność lub z innych powodów (np. stosowanie eliminacji Gaussa zamiast wyliczania rozwiązań układu równań metodą wyznaczników jest stosowana dlatego, że jest lepiej uwarunkowana numerycznie, a nie dlatego, że brak jest wzoru). Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb.

Inaczej mówiąc: metody numeryczne polegają na uzyskiwaniu wyniku poprzez sekwencję kolejnych przybliżeń. W efekcie otrzymany wynik będzie cechował się prawie zawsze pewnym błędem, chociaż ten błąd może być dowolnie mały.

Metody numeryczne znalazły zastosowanie wszędzie tam, gdzie dojście do wyniku innymi sposobami jest niemożliwe lub bardzo trudne.
Takim przykładem z życia szkolnego może być np. obliczenie powierzchni jakiejś nieregularnej figury lub pola pod krzywą.

Z metodami numerycznymi związane są takie pojęcia jak: konwergencja i dywergencja oraz dokładność.

Konwergencja określa zdolność danej metody numerycznej do „zmierzania” w kierunku wyniku. Użytkownik jest zainteresowany, aby zastosowana metoda cechowała się maksymalną konwergencją. Niestety czasami dla pewnych specyficznych danych zastosowana metoda numeryczna może zachowywać się co najmniej dziwnie – zamiast prowadzić do wyniku, daje rezultaty coraz bardziej od wyniku odległe. Tę niepożądaną cechę nazywa się dywergencją. Czasem dywergencja dla pewnego małego zakresu danych jest ceną, jaką płacimy za korzyści wynikające z zastosowanej metody.

Dokładność – ważna cecha metod numerycznych, jest zwykle określana przed rozpoczęciem obliczeń. Im dokładniejszy wynik chce się otrzymać, tym więcej czasu trzeba poświęcić na obliczenia.
Dla niektórych metod wynik może być uzyskany z dowolnie dużą dokładnością, lecz niektóre metody dają wynik obarczony pewnym stałym błędem, zatem zwiększanie precyzji obliczeń nic tu nie pomoże. Czemu stosuje się takie metody – ponieważ są bardzo szybkie i proste w implementacji.
W metodach numerycznych ważny jest kompromis pomiędzy czasem obliczeń, ich dokładnością oraz uniwersalnością metody.

Uwaga, w większości zagadnień numerycznych operuje się na liczbach rzeczywistych.
Programista, który zamierza napisać program rozwiązujący zagadnienia numeryczne musi wybrać odpowiadający mu typ rzeczywisty. Najlepiej gdyby to był typ dający największą dokładność obliczeń (np. long double w języku C++). Niestety, konsekwencją takiego wyboru jest wydłużenie czasu obliczeń i zwiększenie wymaganej przez program pamięci operacyjnej. Gdy problem numeryczny jest bardzo złożony (np. w trakcie obliczeń trzeba jeszcze przydzielić dodatkową pamięć), użycie liczb o dużej precyzji może doprowadzić do szybkiego wyczerpania zasobów maszyny obliczeniowej i w konsekwencji uniemożliwić wykonanie obliczeń.

Szukanie miejsc zerowych funkcji metodami numerycznymi

Aby poznać i zrealizować wybrane metody numeryczne wybrałam jako przykłady szukanie miejsca zerowego konkretnej funkcji z określoną dokładnością. Zastosowane implementacje mają poważne zalety – są proste w zrozumieniu, nie wymagają wyższej matematyki, a co najważniejsze dobrze ilustrują problem.
Funkcja f(x) = x3 – 3x – 20, ma jedno miejsce zerowe, którego położenie można określić, jednak jest ono liczbą niewymierną. Szukanie miejsca zerowego tej funkcji z dokładnością 0,0001 posłuży do zaprezentowania, zilustrowania i porównania kilku wybranych metod numerycznych.