X-Git-Url: https://hackdaworld.org/gitweb/?p=lectures%2Flatex.git;a=blobdiff_plain;f=computational_physics%2Fcp.tex;h=f112233ae9337bb392565fc5bac7346ed26eed74;hp=7c872436c957937a0476e09e41b52c6a4cd1cc7f;hb=f74a53b2acb28533ef22dbf3adb0c97dbb5dd958;hpb=7d3f0efdde7b7245dc2d13ce895147ea8bb2b78a

diff --git a/computational_physics/cp.tex b/computational_physics/cp.tex
index 7c87243..f112233 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,62 +114,272 @@ $\Rightarrow$ study and implementation of numerical algorithms
   \end{itemstep}
 \end{slide}}
 
-\overlays{3}{
-\begin{slide}{warning}
+\overlays{7}{
+\begin{slide}{warning - numerical errors}
   \begin{itemstep}
-    \item numerical precision of 64-bit floating point \\
-          {\small 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 foo
-    \item bar
+    \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}}
 
-\begin{slide}{}
+\overlays{4}{
+\begin{slide}{warning - recursive functions}
+  \begin{itemstep}
+    \item avoid recursive functions!
+          \verbatiminput{fak1.c}
+    \item better:
+          \verbatiminput{fak2.c}
+  \end{itemstep}
+\end{slide}}
 
+\begin{slide}{computational techniques}
+  \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}
 
-\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}
+\overlays{3}{
+\begin{slide}{first steps: rough discretization}
+  \begin{itemstep}
+    \item example: homogenous field of force $\vec{F} = (0,-mg)$ \\
+	  \begin{tabular}{ll}
+	  equation of motion: & $\vec{F} = m \vec{a} = m \frac{d^2 \vec{r}}{dt^2}$ \\
+	  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 = 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};$ & \\
+	  loop: & $x^2 = x^1 + \tau v^1_x;$ & $y^2 = y^1 + \tau v^1_y;$ \\
+	        & $v^2_x = v^1_x;$ & $v^2_y = v^1_y - g \tau;$ \\
+	        & $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{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}}
+
+\begin{slide}{euler's method: accuracy}
+  \includegraphics[width=10cm]{euler.eps}
 \end{slide}
 
-\begin{slide}{computational techniques}
-techniques \textcolor{red}{not yet} discussed in the talk:\footnote{if time is available this will be completed. 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}
+\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{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{8}{
+\begin{slide}{special deviates}
+  \begin{itemstep}
+    \item transformation method:
+          \begin{itemize}
+            \item arbitrary probability 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{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 <f> \pm \Omega \sqrt{\frac{<f^2> - <f>^2}{N}}$ \\
+          $<f> = \frac{1}{N} \sum_{i=1}^{N} f(\vec{x_i})$ \\[6pt]
+          $<f^2> = \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{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{2}{
+\begin{slide}{metropolis algorithm}
+  \begin{itemstep}
+    \item importance sampling: \\
+          $<A> = \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 detailed balance \\[6pt]
+          sufficient condition for equilibrium: \\
+          \[
+          W(A \rightarrow B) p(A) = W(B \rightarrow A) p(B)
+          \]
+          $\Rightarrow \frac{W(A \rightarrow B)}{W(B \rightarrow A)} = \frac{p(B)}{p(A)} = e^{\frac{- \Delta E}{k_B T}}$ \\[6pt]
+          with $\Delta E = E(B) - E(A)$
+  \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{metropolis algorithm}
+  \begin{itemstep}
+    \item choose $W$: \\
+          \[
+          W(A \rightarrow B) = \left\{
+          \begin{array}{ll}
+            e^{- \beta \Delta E} & : \Delta E > 0 \\
+            1 & : \Delta E < 0
+          \end{array} \right.
+          \]
+    \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}}
+
+\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}