From 4939582e49004859350e04a17a711e6c9bb12ed7 Mon Sep 17 00:00:00 2001 From: hackbard Date: Thu, 30 Jun 2005 01:12:14 +0000 Subject: [PATCH] nearly finished cp talk --- computational_physics/cp.tex | 371 +++++++++++++++++++++-------------- 1 file changed, 222 insertions(+), 149 deletions(-) diff --git a/computational_physics/cp.tex b/computational_physics/cp.tex index a320c48..f961215 100644 --- a/computational_physics/cp.tex +++ b/computational_physics/cp.tex @@ -33,7 +33,7 @@ \end{itemstep} \end{slide}} -\overlays{4}{ +\overlays{3}{ \begin{slide}{motivation} \FromSlide{1}{ \begin{center} @@ -44,14 +44,12 @@ } \FromSlide{2}{ challenge: -} -\FromSlide{3}{ \begin{itemize} \item precise mathematical theory \item often: solving theory's equations ab-initio is not realistic \item only a few models can be solved exactly \end{itemize}} -\FromSlide{4}{ +\FromSlide{3}{ $\Rightarrow$ study and implementation of numerical algorithms } \end{slide}} @@ -116,35 +114,26 @@ $\Rightarrow$ study and implementation of numerical algorithms \end{itemstep} \end{slide}} -\overlays{4}{ -\begin{slide}{warning - machine accuracy $\epsilon_m$} +\overlays{7}{ +\begin{slide}{warning - numerical errors} \begin{itemstep} - \item numerical precision of 64-bit floating point \\ - ieee floating point format: $v = -1^s 2^{-e} m$ - \[ - \begin{array}{lll} - s: & \textrm{signe} & \textrm{1 bit} \\ - m: & \textrm{mantissa} & \textrm{52 bit} \\ - e: & \textrm{exponent} & \textrm{11 bit} \\ - \end{array} - \] - \item $\epsilon_m$: smallest floating point with $1 + \epsilon_m \neq 1$ \\ - $\epsilon_m \approx 2 \times 10^{-18}$ \hspace{2pt} (roundoff error) - \item $N$ arithmetic operations $\Rightarrow$ error of order $N \epsilon_m$ - \item subtraction of very nearly equal numbers\\ - (difference in few significant low-order bits) - \end{itemstep} -\end{slide}} - -\overlays{6}{ -\begin{slide}{warning - truncation error} - \begin{itemstep} - \item discrete approximation of continuous quantity - \item truncation error $\equiv$ discrepancy between true answer and practical calculation - \item persists even on hypothetical perfect computer ($\epsilon_m = 0$) - \item machine independent, characteristic of used algorithm - \item numerical analysis: minimizing truncation error - \item unstable method: roundoff error interacting at early stage + \item machine accuracy $\epsilon_m$ + \begin{itemize} + \item ieee 64-bit floating point format: $v = -1^s 2^{-e} m$ \\ + \begin{tabular}{lll} + $s$: & signe & 1 bit \\ + $m$: & mantissa & 52 bit \\ + $e$: & exponent & 11 bit \\ + \end{tabular} + \item $\epsilon_m$: smallest floating point with $1 + \epsilon_m \neq 1$ \\ + $\epsilon_m \approx 2.22 \times 10^{-16}$ \hspace{2pt} (roundoff error) + \end{itemize} + \item truncation error $\epsilon_t$ + \begin{itemize} + \item discrete approximation of continuous quantity + \item persists even on hypothetical perfect computer ($\epsilon_m = 0$) + \item machine independent, characteristic of used algorithm + \end{itemize} \end{itemstep} \end{slide}} @@ -159,44 +148,32 @@ $\Rightarrow$ study and implementation of numerical algorithms \end{slide}} \begin{slide}{computational techniques} -techniques discussed in the talk: -\begin{itemize} - \item rough discretization - \item solution of linear algebraic equations - \item interpolation and extrapolation - \item integration of functions - %\item evaluation of (special) functions - \item monte carlo methods - \item eigensystems - \item spectral applications - %\item modeling of data - %\item ordinary differential equations - %\item two point boundary value problems - %\item partial differential equations -\end{itemize} -\end{slide} - -\begin{slide}{computational techniques} -techniques \textcolor{red}{not yet} discussed in the talk:\footnote{if time is available this will be completed. updates at:\\http://www.physik.uni-augsburg.de/\~{}zirkelfr/download/cp/cp.pdf\\read more at: http://www.nr.com} -\begin{itemize} - %\item rough discretization - %\item solution of linear algebraic equations - %\item interpolation and extrapolation - %\item integration of functions - \item evaluation of (special) functions - %\item monte carlo methods - %\item eigensystems - %\item spectral applications - \item modeling of data - \item ordinary differential equations - \item two point boundary value problems - \item partial differential equations -\end{itemize} -\hspace{6cm} + \begin{minipage}{5.5cm} + \begin{itemize} + \item rough discretization + \item solution of linear algebraic equations + \item interpolation and extrapolation + \item integration of functions + \item evaluation of (special) functions + \item monte carlo methods + \end{itemize} + \end{minipage} + \begin{minipage}{5.5cm} + \begin{itemize} + \item eigensystems + \item spectral applications + \item modeling of data + \item ordinary differential equations + \item two point boundary value problems + \item partial differential \\ + equations + \end{itemize} + \end{minipage} +\footnote{http://www.nr.com/} \end{slide} -\overlays{2}{ -\begin{slide}{rough discretization} +\overlays{3}{ +\begin{slide}{first steps: rough discretization} \begin{itemstep} \item example: homogenous field of force $\vec{F} = (0,-mg)$ \\ \begin{tabular}{ll} @@ -204,7 +181,7 @@ techniques \textcolor{red}{not yet} discussed in the talk:\footnote{if time is a initial condition: & $\vec{r}(t=0) = \vec{r_0} = (x_0,y_0)$ \\ & $\frac{d \vec{r}}{dt}|_{t=0} = (v_{x_0},v_{y_0})$ \\ \end{tabular} - \item algorithm using discretized time ($T_{total} = N \tau$): + \item algorithm using discretized time ($T = N \tau$): \begin{tabular}{lll} $x^1 = x_0;$ & $y^1 = y_0;$ & \\ $v^1_x = v_{x_0};$ & $v^1_y = v_{y_0};$ & \\ @@ -213,97 +190,193 @@ techniques \textcolor{red}{not yet} discussed in the talk:\footnote{if time is a & $x^1 = x^2;$ & $y^1 = y^2$ \\ & $v^1_x = v^2_x;$ & $v^1_y = v^2_y;$ \\ \end{tabular} + \item euler's method for solving o.d.e. \end{itemstep} \end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{10}{ +\begin{slide}{euler's method: error estimation} + \begin{itemstep} + \item truncation error $\epsilon_t$: + \begin{itemize} + \item $x_{t+\tau} = x(t) + v(t,x) \tau + O(\tau^2)$ + \item period $T$: $O(\tau^{-1})$ steps $\Rightarrow \epsilon_t \sim O(\tau)$ + \end{itemize} + \item machine accuracy: + \begin{itemize} + \item every floating point step: error of $O(\epsilon_m)$ + \item $O(\tau^{-1})$ steps $\Rightarrow$ error of $O(\frac{\epsilon_m}{\tau})$ + \end{itemize} + \item optimum: + \begin{itemize} + \item $\epsilon \sim \frac{\epsilon_m}{\tau} + \tau$ + \item 64-bit: $\epsilon_m \sim 10^{-16} \Rightarrow \tau \sim 10^{-8}$ + \item 32-bit: $\epsilon_m = 1.19 \times 10^{-7} \Rightarrow \tau \sim 3 \times 10^{-4}$ + \end{itemize} + \end{itemstep} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\begin{slide}{euler's method: accuracy} + \includegraphics[width=10cm]{euler.eps} +\end{slide} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{9}{ +\begin{slide}{monte carlo methods} + \begin{itemstep} + \item algorithms for solving computational problems using random numbers + \item deterministic pseudo-random sequences + \item applications: + \begin{itemize} + \item monte carlo integration + \item metropolis algorithm + \item simulated annealing + \end{itemize} + \item advantages: + \begin{itemize} + \item more efficient than other methods + \item no need fo simplifying assumptions + \end{itemize} + \end{itemstep} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{5}{ +\begin{slide}{random number generator} +linear congruential generator: + \begin{itemstep} + \item $I_{j+1} = ( a I_{j} + c ) \, mod \, m$ \\ + $a$: multiplier, $c$: increment \\ + $m$: modulus, $I_0$: seed + \item minimal standard by park and miller: \\ + $a = 7^5 = 16807, \quad m = 2^{31} - 1 = 2147483647, \quad c = 0$ + \item always seed the rng + \end{itemstep} +\FromSlide{4}{ +$\Rightarrow$ sequence of integers $\in [0,m[$ \\ +} +\vspace{2pt} +\FromSlide{5}{ +division by modulus $\Rightarrow$ uniform deviates : \\ +\[ + p(x)dx = \left\{ + \begin{array}{ll} + dx & 0 \leq x < 1 \\ + 0 & \textrm{sonst} + \end{array} \right. +\] +} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{8}{ +\begin{slide}{special deviates} + \begin{itemstep} + \item transformation method: + \begin{itemize} + \item arbitrary propability distribution $\rho(y)$ + \item trafo: $p(x) dx = \rho(y) dy \Rightarrow x = \int_{- \infty}^y \rho(y) dy$ + \item get inverse of $x(y) \Rightarrow y(x)$ + \end{itemize} + \item rejection method: \\ + \begin{minipage}{5cm} + \begin{itemize} + \item $p(x) \in [a,b]$ mit $p(x) \geq 0 \quad \forall x \in [a,b]$ + \item uniformly distributed $x \in [a,b]$ und $y \in [0,p_m]$ + \item if $y \leq p(x)$ use $x$, else reject $x$ + \end{itemize} + \end{minipage} + \begin{minipage}{5cm} + \includegraphics[width=5cm]{rej_meth.eps} \\ + \end{minipage} + \end{itemstep} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{5}{ +\begin{slide}{monte carlo integration} + basics: + \begin{itemstep} + \item $I = \int_{\Omega} f d \Omega$ + \item instead of regular $x_i$, choose them at random + \item $I \approx \Omega \pm \Omega \sqrt{\frac{ - ^2}{N}}$ \\ + $ = \frac{1}{N} \sum_{i=1}^{N} f(\vec{x_i})$ \\[6pt] + $ = \frac{1}{N} \sum_{i=1}^{N} f^2(\vec{x_i})$ + \end{itemstep} +\FromSlide{4}{ + example: gambling for $\pi$ \\ +} +\FromSlide{5}{ + \[ + \begin{array}{l} + \pi = \int_{-1}^1 \int_{-1}^1 p(x,y) dx dy \approx \frac{4}{N} \sum_{i=1}^N p(x_i,y_i) \\[6pt] + \textrm{with } p(x,y) = \left\{ + \begin{array}{ll} + 1 & x^2 + y^2 \leq 1 \\ + 0 & \textrm{sonst} + \end{array} \right. + \end{array} + \] +} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{5}{ +\begin{slide}{metropolis algorithm} +ising model: + \begin{itemstep} + \item $d$-dimensional periodic lattice + \item two possible states for magnetic moment at site $i$: \\ + $\mu_i = \mu S_i \qquad S_i = \pm 1 \quad \forall i$ + \item nearest neighbors moments interact, \\ + interaction strength $\frac{J_{ij}}{\mu^2}$ + \end{itemstep} +\FromSlide{4}{ +$\Rightarrow$ hamiltonian: $H = - \sum_{(i,j)} J_{ij} S_i S_j$ \\ +} +\FromSlide{5}{ +partition function: \\ +\[ +Z = \sum_{i=1}^N e^{\frac{-E_i}{k_B T}} = Tr(e^{-\beta H}) +\] +} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{4}{ +\begin{slide}{metropolis algorithm} + \begin{itemstep} + \item importance sampling: \\ + $ = \sum_i p_i A_i \approx \frac{1}{N} \sum_{i=1}^N A_i$ , with \\[6pt] + $\qquad p_i = \frac{e^{\beta E_i}}{Z}$ + \item markov process: \\ + \begin{itemize} + \item $P(A,t)$: probability of configuration $A$ at time $t$ + \item $W(A \rightarrow B)$: transition probability + \[ + \begin{array}{l} + P(A,t+1) = P(A,t) + \\ + \sum_B \Big( W(B \rightarrow A) P(B,t) - W(A \rightarrow B) P(A,t) \Big) + \end{array} + \] + \end{itemize} + \end{itemstep} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\overlays{5}{ +\begin{slide}{metropolis algorithm} + \begin{itemstep} + \item detailed balance + \item algorithm: + \begin{itemize} + \item visit every lattice site + \item calculate $\delta E$ for spin flip + \item flip spin if $r \leq e^{\frac{-\delta E}{k_B T}}$ + \end{itemize} + \end{itemstep} +\end{slide}} -%\overlays{3}{ -%\begin{slide}{} -% \begin{itemstep} -% \item -% \item -% \item -% \end{itemstep} -%\end{slide}} +\begin{slide}{summary} + \begin{itemize} + \item importance of computational physics + \item things to keep in mind when doing computational physics + \item euler's method for solving o.d.e. + \item introduction to monte carlo methods + \end{itemize} +\end{slide} \end{document} -- 2.20.1