Theoretical Concepts and Simulations
S. Denisov MNTF, Uni Augsburg
Random walks: an example of stochastic simulations
The process
A walker (sometime called
’drunkard’) performes sequential steps on the x−y plane with the direction of each step independent of the direction of the previous step.
The walker makesN steps
(4x1,4y1),(4x2,4y2), ...,(4xN,4yN)
The radial distance from the starting point (0,0) afterN steps is R2 = (4x1+4x2+...+4xN)2+ (4y1+4y2+...+4yN)2
2 / 20
Random walks: an example of stochastic simulations
Radial distance
R2=4x12+4x22+...+4xN2 + 24x14x2 +24x14x3+...+ 24xN−14xN+ (x→y)
Random walks: an example of stochastic simulations
Radial distance
IfN is large and steps are independent (as it was assumed at the beggining) then all terms4xi4xj,i 6=j self-average out, i. e.
they summ up to zero and
R2 =4x12+4x22+...+4xN2 +4y12+4y22+...+4yN2 =
= (4x12+4y12) + (4x22+4y22) +...+ (4xN2 +4yN2) = Nhr2i=Nrrms2 ⇒
R=
√ Nrrms, whererrms is theroot-mean-square step size.
4 / 20
Random walks: an example of stochastic simulations
How to simulate
I start at timet= 0 at (x(0) = 0,y(0) = 0);
I independently choose random values forx0 andy0 in the range [−1; 1];
I normalize them so that each step is of unit length:
L=p
x02+y02, 4x = 1
Lx0, 4y= 1 Ly0;
I incrementx →x+4x,y →y+4y, andt →t+ 1;
I start again from the first step and continue antilt=N
Random walks: an example of stochastic simulations
Results of stochastic simulations
(left) Three samples of random-walk trajectories with N= 2000 steps and rrms = 1;
(right) DependenceR(N) vs the square root of the number of stepsN.
6 / 20
Random walks: an example of stochastic simulations
Results of stochastic simulations
The probability distribution function (pdf) P(x,y,t) for t= 200 (left) and t = 400 (right). Number of realizationsNrez = 106.
Numerical integration
The problem
Riemann definition
Z b a
f(x)dx = lim
h→0[h
b−a h
X
i=1
f(xi)]
8 / 20
Numerical integration
Approximation algorithm
Z b a
f(x)dx '
N
X
i=1
f(xi)·wi
It is the standard form for all integration algorithms; the function f(x) is evaluated at N points in the interval [a,b], and the function valuesfi ≡f(xi) are summed with each term in the sum weighted bywi.
While in general the sum gives the exact integral only when N→ ∞, it may be exact for finiteN if the integrand is a polynomial.
Numerical integration
Simplest algorithm: Trapezoid rule
The trapezoid rule uses values off(x) at evenly spaced values of x. It usesN pointsxi,i = 1, ..,N evenly spaced at a distance h apart throughout the integration region [a,b], including the endpoints,x =a andx=b. This means that there areN−1 intervals of lengthh:
The trapezoid rule takes each integration intervali and constructs a trapezoid of widthh in it. This approximatesf(x) by a straight line in each intervali and uses the average height (fi+fi+1)/2 as the value forfi.
10 / 20
Numerical integration
Simplest algorithm: Trapezoid rule
The area of each such trapezoid is
Numerical integration
Simplest algorithm: Trapezoid rule
In order to apply the trapezoid rule to the entire region [a,b], we add the contributions from each subinterval:
Because the internal points are counted twice (as the end of one interval and as the beginning of the next), they have weights h/2 +h/2 =h, whereas the endpoints are counted just once and on that account have weights of onlyh/2. Thus, in terms of our standard integration rule, we have
wi ={h
2,h,h, ...,h,h 2}
12 / 20
Numerical integration
Simpson’s rule
For each interval, Simpsonˆas rule approximates the integrand f(x) by a parabola
f(x)'αx2+βx+γ
with all intervalsequally spaced(again). The area under the parabola for each interval is
In order to relate the parametersα,β, andγ to the function, we consider an interval [−1,1], in which case
Numerical integration
Simpson’s rule
Notice that
we can express the integral as the weighted sum over the values of the function at three points
14 / 20
Numerical integration
Simpson’s rule
Because three values of the function are needed, we generalize this result to our problem by evaluating the integral over two adjacent intervals, in which case we evaluate the function at the two endpoints and in the middle
Numerical integration
Simpson’s rule
Simpson’s rule requires the elementary integration to be over pairs of intervals, which in turn requires that the total number of intervals be even or that the number of pointsN be odd. In order to apply Simpson’s rule to the entire interval, we add up the contributions from each pair of subintervals, counting all but the first and last endpoints twice:
Thus, in terms of our standard integration rule, we have wi ={h
3,4h 3 ,2h
3 ,4h 3 , ...,4h
3 ,h 3}
16 / 20
Numerical integration
Simpson’s rule
Comparison of the trapezoid rule (left) with Simpson’s rule (right).
Numerical integration
Error analysis
Absolute,E and relative errors,, and scaling
See on the blackboard (and hand-written notes to this lecture)
18 / 20
Numerical integration
Higher-order equidistant schemes: Newton - Cotes formulae