fixed-point-functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "tender-finland",
   "metadata": {},
   "source": [
    "# Fixed-point functions\n",
    "\n",
    "### First, let's find the golden ratio\n",
    "\n",
    "a:b is as b:a+b.\n",
    "\n",
    "Another way to write this is:\n",
    "\n",
    "a/b = b/(a+b)\n",
    "\n",
    "Alternatively we could flip the fractions:\n",
    "\n",
    "b/a = (a+b)/b.\n",
    "\n",
    "If we assume a=1, we can simplify to:\n",
    "\n",
    "b = (b+1)/b.\n",
    "\n",
    "We could also write this as:\n",
    "\n",
    "f(x) = (x+1)/x.\n",
    "\n",
    "Remember we are trying to find x. So:\n",
    "\n",
    "x = f(x)\n",
    "\n",
    "If this is the case, x = f(x) = f( f(x) ) = f( f( f(x) ) ), etc.\n",
    "\n",
    "So we can do fixed-point iteration to find the solution..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "monthly-active",
   "metadata": {},
   "outputs": [],
   "source": [
    "def golden(x):\n",
    "    return (x+1)/x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "activated-klein",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "solid-offense",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "alternative-average",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6666666666666667"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "administrative-captain",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(1))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "contemporary-veteran",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.625"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(1)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "cooperative-harmony",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6153846153846154"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(1))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "elect-reset",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.619047619047619"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(golden(1)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "latest-sleeve",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6176470588235294"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(golden(golden(1))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "sophisticated-alignment",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6181818181818182"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(golden(golden(golden(1)))))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "legendary-renewal",
   "metadata": {},
   "source": [
    "This should also work, no matter the starting point..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "organizational-graphic",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6176559204579692"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(golden(golden(golden(97)))))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bored-infrared",
   "metadata": {},
   "source": [
    "This function is defined such that a recursive execution of it is like a honing missle for the golden ratio.\n",
    "\n",
    "This seems very similar to how evolution may work. People output people, and by iterating, we get better.\n",
    "\n",
    "Perhaps any function that can be so framed \"automatically\" hones in to an optimal solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "multiple-paraguay",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.2-0.4j)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(1+2j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "scientific-ivory",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.6178585436004707-0.0002614720878546216j)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "golden(golden(golden(golden(golden(golden(golden(golden(golden(1+2j)))))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "inclusive-champagne",
   "metadata": {},
   "source": [
    "# What about other fixed-point functions?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "widespread-sword",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fixed1(x):\n",
    "    return x*2+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "other-leave",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed1(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "important-hungary",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed1(fixed1(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "allied-collector",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed1(fixed1(fixed1(1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "polar-brain",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed1(fixed1(fixed1(fixed1(1))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "injured-persian",
   "metadata": {},
   "source": [
    "Clearly, some iterated-on functions diverge. This is like a repulsive force.\n",
    "\n",
    "Recursively-iterated functions which diverge are like repulsers. Recursively-iterated functions which converge are like attractors.\n",
    "\n",
    "Question: Is there a simple way to know if a function converges or diverges? Also, some functions will converge in a specific area and diverge in others, like the Mandelbrot function: z=z**2+c."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "exclusive-wilderness",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mandelbrot(z, c):\n",
    "    return z**2+c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "humanitarian-eclipse",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mandelbrot(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "mineral-canadian",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mandelbrot(mandelbrot(1, 1), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "optical-cattle",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# diverge at 1+0j\n",
    "mandelbrot(mandelbrot(mandelbrot(1, 1), 1), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "bridal-rover",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# converge at 0+0j\n",
    "mandelbrot(mandelbrot(mandelbrot(0, 0), 0), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "successful-qatar",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# converge at -1+0j\n",
    "mandelbrot(mandelbrot(mandelbrot(-1, -1), -1), -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "protected-registrar",
   "metadata": {},
   "source": [
    "# The line between attraction and repulsion\n",
    "\n",
    "One very simple function that is an attractor in some places and a repulser in another is: f(x) = x**2. If x<1, it converges, and if x>1 it diverges..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "romance-leader",
   "metadata": {},
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    return x**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "breathing-screen",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "composite-nightlife",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(square(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "figured-hurricane",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "256"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(square(square(2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "fundamental-force",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "65536"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(square(square(square(2))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "serial-sally",
   "metadata": {},
   "source": [
    "For brevity, let's define a function to iterate a function so we don't keep having to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "spiritual-kernel",
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterate(func, start, num_times):\n",
    "    val = start\n",
    "    val_list = []\n",
    "    for i in range(num_times+1):\n",
    "        val_list.append(val)\n",
    "        val = func(val)\n",
    "    return val_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "accessible-flash",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 16, 256, 65536]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(square, 2, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "imported-convert",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 2.0,\n",
       " 1.5,\n",
       " 1.6666666666666667,\n",
       " 1.6,\n",
       " 1.625,\n",
       " 1.6153846153846154,\n",
       " 1.619047619047619,\n",
       " 1.6176470588235294,\n",
       " 1.6181818181818182,\n",
       " 1.6179775280898876,\n",
       " 1.6180555555555556,\n",
       " 1.6180257510729612]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(golden, 1, 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "popular-century",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.1,\n",
       " 1.2100000000000002,\n",
       " 1.4641000000000004,\n",
       " 2.143588810000001,\n",
       " 4.594972986357221,\n",
       " 21.1137767453526,\n",
       " 445.7915684525922]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# >1 diverges\n",
    "iterate(square, 1.1, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "periodic-inquiry",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.9,\n",
       " 0.81,\n",
       " 0.6561000000000001,\n",
       " 0.43046721000000016,\n",
       " 0.18530201888518424,\n",
       " 0.03433683820292518,\n",
       " 0.001179018457773862]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# <1 converges\n",
    "iterate(square, 0.9, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "directed-needle",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1,\n",
       " -2,\n",
       " -33,\n",
       " -39135394,\n",
       " -91801241053644953553642221885011784225,\n",
       " -6519927434790921611644421835063525424902891356389795386439001633774343881310329902383751163504348619662623089904493770596045628788998692217412903744200798649266250348434521475456717275390626]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(lambda x: x**5-1, -1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "technical-effort",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 3.0,\n",
       " 1.6666666666666667,\n",
       " 2.2,\n",
       " 1.909090909090909,\n",
       " 2.047619047619048,\n",
       " 1.9767441860465114,\n",
       " 2.0117647058823533,\n",
       " 1.9941520467836253,\n",
       " 2.0029325513196485,\n",
       " 1.9985358711566619,\n",
       " 2.0007326007326007,\n",
       " 1.9996338337605273]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(lambda x: (x+2)/x, 1, 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "meaning-breeding",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 4.0,\n",
       " 1.75,\n",
       " 2.7142857142857144,\n",
       " 2.1052631578947367,\n",
       " 2.425,\n",
       " 2.2371134020618557,\n",
       " 2.3410138248847927,\n",
       " 2.281496062992126,\n",
       " 2.3149266609145815,\n",
       " 2.295937383525904,\n",
       " 2.306655844155844,\n",
       " 2.300584136814695]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(lambda x: (x+3)/x, 1, 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "united-absolute",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 11.0,\n",
       " 1.9090909090909092,\n",
       " 6.238095238095238,\n",
       " 2.6030534351145036,\n",
       " 4.841642228739003,\n",
       " 3.0654149000605693,\n",
       " 4.262201146018573,\n",
       " 3.3462055537527235,\n",
       " 3.9884595669220433,\n",
       " 3.507233640509776,\n",
       " 3.851250023521815,\n",
       " 3.5965595427261814]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(lambda x: (x+10)/x, 1, 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "completed-carry",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 0.5,\n",
       " 0.16666666666666666,\n",
       " 0.023809523809523808,\n",
       " 0.0005537098560354374,\n",
       " 3.0642493416460287e-07,\n",
       " 9.389621150564078e-14,\n",
       " 8.8164985351112e-27,\n",
       " 7.773064641961794e-53,\n",
       " 6.042053392811663e-105,\n",
       " 3.6506409201586933e-209]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterate(lambda x: (x**2)/(x+1), 1, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bibliographic-highland",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}