{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"\n",
"\n",
"\n",
"*This notebook contains an excerpt from the [Python Programming and Numerical Methods - A Guide for Engineers and Scientists](https://www.elsevier.com/books/python-programming-and-numerical-methods/kong/978-0-12-819549-9), the content is also available at [Berkeley Python Numerical Methods](https://pythonnumericalmethods.berkeley.edu/notebooks/Index.html).*\n",
"\n",
"*The copyright of the book belongs to Elsevier. We also have this interactive book online for a better learning experience. The code is released under the [MIT license](https://opensource.org/licenses/MIT). If you find this content useful, please consider supporting the work on [Elsevier](https://www.elsevier.com/books/python-programming-and-numerical-methods/kong/978-0-12-819549-9) or [Amazon](https://www.amazon.com/Python-Programming-Numerical-Methods-Scientists/dp/0128195495/ref=sr_1_1?dchild=1&keywords=Python+Programming+and+Numerical+Methods+-+A+Guide+for+Engineers+and+Scientists&qid=1604761352&sr=8-1)!*"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"\n",
"< [19.4 Newton-Raphson Method](chapter19.04-Newton-Raphson-Method.ipynb) | [Contents](Index.ipynb) | [CHAPTER 20. Numerical Differentiation](chapter20.00-Numerical-Differentiation.ipynb) >"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Summary\n",
"\n",
"\n",
"1. Roots are an important property of functions.\n",
"2. The bisection method is a way of finding roots based on divide and conquer. Although stable, it might converge slowly compared to the Newton-Raphson method.\n",
"3. The Newton-Raphson method is a different way of finding roots based on approximation of the function. The Newton-Raphson method converges quickly close to the actual root, but can have unstable behavior."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Problems\n",
"\n",
"1. Write a function $my\\_nth\\_root(x, n, tol)$, where $x$ and $tol$ are strictly positive scalars, and $n$ is an integer strictly greater than 1. The output argument, $r$, should be an approximation $r = \\sqrt[N]{x}$, the $N$-th root of $x$. This approximation should be computed by using the Newton Raphson method to find the root of the function $f(y) = y^N - x$. The error metric should be $|f(y)|$.\n",
"\n",
"2. Write a function $my\\_fixed\\_point(f, g, tol, max_iter)$, where $f$ and $g$ are function objects and $tol$ and $max\\_iter$ are strictly positive scalars. The input argument, $max\\_iter$, is also an integer. The output argument, $X$, should be a scalar satisfying $|f(X) - g(X)| < tol$; that is, $X$ is a point that (almost) satisfies $f(X) = g(X)$. To find $X$, you should use the Bisection method with error metric, $|F(m)| < tol$. The function $my\\_fixed\\_point$ should \"give up\" after $max\\_iter$ number of iterations and return $X = []$ if this occurs.\n",
"\n",
"3. Why does the bisection method fail for $f(x) = 1/x$ with error given by $|b-a|$? Hint: How does $f(x)$ violate the intermediate value theorem?\n",
"\n",
"4. Write a function $my\\_bisection(f, a, b, tol)$, that returns $[R, E]$, where $f$ is a function object, $a$ and $b$ are scalars such that $a < b$, and $tol$ is a strictly positive scalar value. The function should return an array, $R$, where $R[i]$ is the estimation of the root of $f$ defined by $(a + b)/2$ for the $i$-th iteration of the bisection method. Remember to include the initial estimate. The function should also return an array, $E$, where $E[i]$ is the value of $| f(R[i]) |$ for the $i$-th iteration of the bisection method. The function should terminate when $E(i) < tol$. You may assume that ${\\text{sign}}(f(a)) \\neq {\\text{sign}}(f(b))$.\n",
"\n",
" Clarification: The input $a$ and $b$ constitute the first iteration of bisection, and therefore $R$ and $E$ should never be empty.\n",
" \n",
" Test Cases:\n",
" \n",
" ```python\n",
" In: f = lambda x: x**2 - 2\n",
" [R, E] = my_bisection(f, 0, 2, 1e-1)\n",
" Out: R = [1, 1.5, 1.25, 1.375, 1.4375]\n",
" E = [1, 0.25, 0.4375, 0.109375, 0.06640625]\n",
" \n",
" In: f = lambda x: np.sin(x) - np.cos(x)\n",
" [R, E] = my_bisection(f, 0, 2, 1e-2)\n",
" Out: R = [1, 0.5, 0.75, 0.875, 0.8125, 0.78125]\n",
" E = [0.30116867893975674, 0.39815702328616975, 0.05005010885048666, 0.12654664407270177, 0.038323093040207645, 0.005866372111545948]\n",
" ```\n",
"\n",
"5. Write a function $my\\_newton(f, df, x0, tol)$, that returns $[R, E]$, where $f$ is a function object, $df$ is a function object to the derivative of $f$, $x0$ is an initial estimation of the root, and $tol$ is a strictly positive scalar. The function should return an array, $R$, where $R[i)]$ is the Newton-Raphson estimation of the root of $f$ for the $i$-th iteration. Remember to include the initial estimate. The function should also return an array, $E$, where $E[i]$ is the value of $| f(R[i]) |$ for the $i$-th iteration of the Newton-Raphson method. The function should terminate when $E(i) < tol$. You may assume that the derivative of $f$ will not hit 0 during any iteration for any of the test cases given.\n",
"\n",
" Test Cases:\n",
" \n",
" ```python\n",
" In: f = lambda x: x**2 - 2\n",
" df = lambda x: 2*x\n",
" [R, E] = my_newton(f, df, 1, 1e-5)\n",
" Out: R = [1, 1.5, 1.4166666666666667, 1.4142156862745099]\n",
" E = [1, 0.25, 0.006944444444444642, 6.007304882871267e-06]\n",
" \n",
" In: f = lambda x: np.sin(x) - np.cos(x)\n",
" df = lambda x: np.cos(x) + np.sin(x)\n",
" [R, E] = my_newton(f, df, 1, 1e-5)\n",
" Out: R = [1, 0.782041901539138, 0.7853981759997019]\n",
" E = [0.30116867893975674, 0.004746462127804163, 1.7822277875723103e-08]\n",
" ```\n",
"\n",
"6. Consider the problem of building a pipeline from an offshore oil platform, a distance $H$ miles from the shoreline, to an oil refinery station on land, a distance $L$ miles along the shore. The cost of building the pipe is $C_{\\text{ocean}/\\text{mile}}$ while the pipe is under the ocean and $C_{\\text{land}/\\text{mile}}$ while the pipe is on land. The pipe will be built in a straight line toward the shore where it will make contact at some point, $x$, between 0 and $L$. It will continue along the shore on land until it reaches the oil refinery. See the figure for clarification.\n",
"\n",
" \n",
" \n",
" Write a function $my\\_pipe\\_builder(C\\_ocean, C\\_land, L, H)$, where the input arguments are as described earlier, and $x$ is the x-value that minimizes the total cost of the pipeline. You should use the bisection method to determine this value to within a tolerance of $1\\times10^{-6}$ starting at an initial bound of $a=0$ and $b=L$. \n",
" \n",
" Test Cases:\n",
" \n",
" ```python\n",
" In: my_pipe_builder(20, 10, 100, 50)\n",
" Out: 28.867512941360474\n",
" \n",
" In: my_pipe_builder(30, 10, 100, 50)\n",
" Out: 17.677670717239380\n",
" \n",
" In: my_pipe_builder(30, 10, 100, 20)\n",
" Out: 7.071067392826080\n",
" ```\n",
" \n",
"7. Find a function $f(x)$ and guess for the root of $f, x_0$, such that the Newton-Raphson method would oscillate between $x_0$ and $-x_0$ indefinitely."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"\n",
"< [19.4 Newton-Raphson Method](chapter19.04-Newton-Raphson-Method.ipynb) | [Contents](Index.ipynb) | [CHAPTER 20. Numerical Differentiation](chapter20.00-Numerical-Differentiation.ipynb) >"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.8"
}
},
"nbformat": 4,
"nbformat_minor": 2
}