chapter2-7.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7473c66a",
   "metadata": {},
   "source": [
    "# 2.7 High-order fixed-point iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4588514e",
   "metadata": {},
   "source": [
    "In the proof of Theorem 4 in Chapter 2-6, we showed\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{|p_{n+1}-p|}{|p_{n}-p|}=|g'(p)|\n",
    "\\end{equation*}\n",
    "which implied that the fixed-point iteration has linear convergence, if $g'(p)\\neq 0$.\n",
    "\n",
    "If this limit were zero, then we would have\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{|p_{n+1}-p|}{|p_{n}-p|}=0,\n",
    "\\end{equation*}\n",
    "which means the numerator is decreasing at a larger rate than the denominator.\n",
    "We could then ask if\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{|p_{n+1}-p|}{|p_{n}-p|^{\\alpha}}=\\text{nonzero constant}\n",
    "\\end{equation*} \n",
    "for some $\\alpha>1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a1679b7",
   "metadata": {},
   "source": [
    "\\begin{theorem}\\label{theo:chap2_thm46}\n",
    "Assume $p$ is a solution of $g(x)=x$\n",
    "where $g\\in C^\\alpha (I)$ for some interval $I$ that contains $p$, and for some $\\alpha\\geq2$. Furthermore assume\n",
    "\\begin{equation*}\n",
    "g'(p)=g''(p)=...=g^{(\\alpha-1)}(p)=0,\\text{ and }g^{(\\alpha)}(p)\\neq0.\n",
    "\\end{equation*}\n",
    "Then if the initial guess $p_{0}$ is sufficiently close to $p$,\n",
    "the fixed-point iteration $p_{n}=g(p_{n-1}),n\\geq1$, will have order\n",
    "of convergence of $\\alpha$, and\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{p_{n+1}-p}{(p_{n}-p)^{\\alpha}}=\\frac{g^{(\\alpha)}(p)}{\\alpha!}.\n",
    "\\end{equation*}\n",
    "\\end{theorem}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b09818de",
   "metadata": {},
   "source": [
    "\\begin{proof}\n",
    "From Taylor's theorem,\n",
    "\\begin{align*}\n",
    "p_{n+1} & =g(p_{n})=g(p)+(p_{n}-p)g'(p)+...+\\frac{(p_{n}-p)^{\\alpha-1}}{(\\alpha-1)!}g^{(\\alpha-1)}(p) +\\frac{(p_{n}-p)^{\\alpha}}{\\alpha!}g^{(\\alpha)}(\\xi_{n})\n",
    "\\end{align*}\n",
    "where $\\xi_{n}$ is a number between $p_{n}$ and $p$, and all numbers are in $I$. From the hypothesis,\n",
    "this simplifies as\n",
    "\\begin{equation*}\n",
    "p_{n+1}=p+\\frac{(p_{n}-p)^{\\alpha}}{\\alpha!}g^{(\\alpha)}(\\xi_{n})\\Rightarrow\\frac{p_{n+1}-p}{(p_{n}-p)^{\\alpha}}=\\frac{g^{(\\alpha)}(\\xi_{n})}{\\alpha!}.\n",
    "\\end{equation*}\n",
    "From {prf:ref}`chap2_thm44`, if $p_{0}$ is chosen sufficiently close to $p$, then $\\lim_{n\\rightarrow\\infty}p_{n}=p$.\n",
    " The order\n",
    "of convergence is $\\alpha$ with\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{|p_{n+1}-p|}{|p_{n}-p|^{\\alpha}}=\\lim_{n\\rightarrow\\infty}\\frac{|g^{(\\alpha)}(\\xi_{n})|}{\\alpha!}=\\frac{|g^{(\\alpha)}(p)|}{\\alpha!}\\neq0.\n",
    "\\end{equation*}\n",
    "\\end{proof}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "027c32d8",
   "metadata": {},
   "source": [
    "## Application to Newton's Method"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c7570f4",
   "metadata": {},
   "source": [
    "Recall Newton's iteration\n",
    "\\begin{equation*}\n",
    "p_{n}=p_{n-1}-\\frac{f(p_{n-1})}{f'(p_{n-1})}.\n",
    "\\end{equation*}\n",
    "Put $g(x)=x-\\frac{f(x)}{f'(x)}.$ Then the fixed-point iteration $p_{n}=g(p_{n-1})$\n",
    "is Newton's method. We have\n",
    "\\begin{equation*}\n",
    "g'(x)=1-\\frac{[f'(x)]^{2}-f(x)f''(x)}{[f'(x)]^{2}}=\\frac{f(x)f''(x)}{[f'(x)]^{2}}\n",
    "\\end{equation*}\n",
    "and thus\n",
    "\\begin{equation*}\n",
    "g'(p)=\\frac{f(p)f''(p)}{[f'(p)]^{2}}=0.\n",
    "\\end{equation*}\n",
    "Similarly,\n",
    "\\begin{equation*}\n",
    "g''(x)=\\frac{\\left(f'(x)f''(x)+f(x)f'''(x)\\right)(f'(x))^{2}-f(x)f''(x)2f'(x)f''(x)}{[f'(x)]^{4}}\n",
    "\\end{equation*}\n",
    "which implies\n",
    "\\begin{equation*}\n",
    "g''(p)=\\frac{\\left(f'(p)f''(p)\\right)(f'(p))^{2}}{[f'(p)]^{4}}=\\frac{f''(p)}{f'(p)}.\n",
    "\\end{equation*}\n",
    "\n",
    "If $f''(p)\\neq0$ (recall that Newton's method assumes $f'(p)\\ne 0$), then Theorem \\ref{theo:chap2_thm46} implies\n",
    "Newton's method has quadratic convergence with\n",
    "\\begin{equation*}\n",
    "\\lim_{n\\rightarrow\\infty}\\frac{p_{n+1}-p}{(p_{n}-p)^{2}}=\\frac{f''(p)}{2f'(p)}\n",
    "\\end{equation*}\n",
    "which was proved earlier in Theorem 1 in Chapter 2-3."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04ee8980",
   "metadata": {},
   "source": [
    "**Exercise 2.7-1**\n",
    "\n",
    "Let $g(x)=3^{-x}$.\n",
    "\n",
    "a. Prove that $g(x)$ has a unique fixed-point on $[1/4,1].$ (Hint: Use Theorem 1 and Remark 1 in Chapter 2-6.)\n",
    "\n",
    "b. Prove that the fixed-point iteration $p_n=g(p_{n-1})$ converges to the unique fixed-point of $g$ for any starting point $p_0 \\in [1/4,1]$. (Hint: Use Theorem 2 and Remark 2 in Chapter 2-6.)\n",
    "\n",
    "c. Pick some $p_0 \\in [1/4,1]$, and use Corollary 3 in Chapter 2-6, part (4), to find the number of iterations necessary to achieve $10^{-10}$ accuracy. Call this number $N$.\n",
    "\n",
    "d. Modify the Julia code for fixed-point iteration as follows: remove the stopping criterion $|p_1-p_0|<\\text{ eps}$ and make the code run until $N$ iterations, printing pzero as the output $p$ at the end. Using the new code, and your answer to the previous part, compute the fixed-point of $g(x)$ with an accuracy of $10^{-10}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4082ef7c",
   "metadata": {},
   "source": [
    "**Exercise 2.7-2**\n",
    "\n",
    "Let $g(x)=2x-cx^{2}$ where $c$ is a positive constant. Prove that if the fixed-point iteration $p_n=g(p_{n-1})$ converges to a non-zero limit, then the limit is $1/c$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e938063",
   "metadata": {},
   "source": [
    "**Exercise 2.7-3**\n",
    "\n",
    "Leonardo of Pisa (1175-1250), also known as Fibonacci, showed that the only real root of the cubic polynomial $x^3 + 2 x^2 + 10x − 20$ is (Brown and Brunson (2008))\n",
    "\\begin{equation*}\n",
    "1+\\frac{22}{60}+\\frac{7}{60^2} + \\frac{42}{60^3} + \\frac{33}{60^4} + \\frac{4}{60^5} + \\frac{40}{60^6}.\n",
    "\\end{equation*}\n",
    "Use any one of the methods of this chapter to find how good Fibonacci's approximation was."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "182b06cc",
   "metadata": {},
   "source": [
    "# References"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec9bbb8d",
   "metadata": {},
   "source": [
    "E. Brown and J.C. Brunson. Fibonacci's forgotten number. The College Mathematics Journal, 39:112–120, 2008."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}