Institut für Theoretische Physik Universität zu Köln
\n",
"
\n",
"
Prof. Dr. Simon Trebst Peter Bröcker
\n",
"
\n",
"
\n",
"\n",
"
Computerphysik
\n",
"
Übungsblatt 2
\n",
"\n",
"
Sommersemester 2016
\n",
"\n",
"**Website:** [http://www.thp.uni-koeln.de/trebst/Lectures/2016-CompPhys.shtml](http://www.thp.uni-koeln.de/trebst/Lectures/2016-CompPhys.shtml)\n",
"\n",
"**Abgabe**: Montag, 25. April, 2016 vor der Vorlesung\n",
"\n",
"**Name**: Bitte geben Sie ihren Namen an\n",
"\n",
"**Matrikelnummer**: Bitte geben Sie ihre Matrikelnummer an"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
\n",
"
Divide and Conquer
\n",
"
(4 Punkte)
\n",
"\n",
"Eine häufig wiederkehrende Aufgabe ist die Bestimmung von Nullstellen einer beliebigen\n",
"Funktion. Um dies zu tun, haben Sie in der Vorlesung einige iterative Verfahren kennengelernt,\n",
"die wir im Rahmen dieser Übung implementieren und vergleichen wollen. Die beiden hier behandelten Methoden zählen zum Bereich der *divide and conquer* Algorithmen, in denen wir ein Problem so lange in kleine Probleme zerlegen, bis sie irgendwann als lösbar gelten.\n",
"\n",
"Als erste Methode soll eine **grid search** implementiert werden. Dazu wird ein Stück des Definitionsbereich um die Nullstelle herum in kleinere Bereiche unterteilt. Als nächstes wird der Bereich identifiziert, in dem die Nullstelle liegt und dieser wieder unterteilt. Wenn die gewünschte Präzision erreicht ist, wird das Verfahren abgebrochen.\n",
"\n",
"Alternativ dazu kann ein Verfahren angewendet werden, das Sie bereits in der Mathematik als Intervallschachtelung kennengelernt haben und auch als **binary search** bekannt ist. Nachdem zwei Endpunkte gewählt wurden, wird der Bereich so halbiert, dass die Nullstelle wieder im Bereich liegt. Wie zuvor wird auch dieser Vorgang dann abgebrochen, wenn die gewünschte Genauigkeit erreicht ist.\n",
"\n",
"In dieser und der nächsten Aufgabe soll eine Funktion untersucht werden, die Sie in der Quantenmechanik kennenlernen werden oder bereits kennengelernt haben. Bei der Lösung des Problems eines Teilchens in einem endlichen Potentialtopf trifft man auf die Gleichung\n",
"\n",
"$\\quad k\\tan(ka) - \\kappa = 0$\n",
"\n",
"in der wir nun $a, \\kappa = 1$ setzen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"f(k) = k * tan(k) - 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Grid Search\n",
"\n",
"Als erste Methode sollen Sie den untenstehenden Code zu einer Funktion ausbauen, die eine *grid search* durchführt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"function grid_search(f, x_left, x_right, n_grid_points, precision)\n",
" iterations = 100 # how many tries for better precision before giving up\n",
" grid = linspace(x_left, x_right, n_grid_points) # grid on x-axes\n",
" x0 = x_left + abs(x_left - x_right) / 2 #initial guess\n",
" f_left = f(grid[1])\n",
" f_right = f(grid[end])\n",
" \n",
" for i in 1:iterations\n",
" # check each pair of neighboring points on grid\n",
" # for sign change, indicating the presence of a zero in between\n",
" for j in 1:n_grid_points - 1 \n",
" ###...\n",
" ### Fuegen Sie Ihren Code hier ein\n",
" ###...\n",
" end\n",
" \n",
" # precision on x_axis\n",
" if max(abs(f_left), abs(f_right)) < precision\n",
" return (x0, i)\n",
" end\n",
" end\n",
" \n",
" return (x0, iterations)\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Mit den folgenden Parametern ausgeführt, sollte die Ausgabe der Funktion $x_0 = 3.425$ sein."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"grid_search(f, 2, 5, 100, 1e-3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Binary Search\n",
"\n",
"Vervollständigen Sie nun auch das folgende Skelett, um die Nullstelle mittels *binary search* zu finden"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"function binary_search(f, x_left, x_right, precision)\n",
" iterations = 100\n",
" \n",
" for i in 1:iterations\n",
" ###...\n",
" ### Fuegen Sie Ihren Code hier ein\n",
" ###...\n",
" end\n",
"end"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"binary_search(f, 2, 5, 1e-3)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 0.4.2",
"language": "julia",
"name": "julia-0.4"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "0.4.2"
}
},
"nbformat": 4,
"nbformat_minor": 0
}