{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "9c2df5f9", "metadata": { "tags": [ "remove-cell" ] }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "┌ Info: verify download of index files...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:139\n", "┌ Info: reading database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:23\n", "┌ Info: adding metadata...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:67\n", "┌ Info: adding svd data...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:69\n", "┌ Info: writing database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:74\n", "┌ Info: used remote sites are sparse.tamu.edu with MAT index and math.nist.gov with HTML index\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:141\n" ] } ], "source": [ "using FundamentalsNumericalComputation\n", "FNC.init_format()" ] }, { "cell_type": "markdown", "id": "6ae33a31", "metadata": {}, "source": [ "(section-nonlineqn-fixed-point)=\n", "# Fixed-point iteration\n", "\n", "In this section, we consider the alternative form of the rootfinding problem known as the *fixed-point problem*.\n", "\n", "```{index} ! fixed-point problem\n", "```\n", "```{proof:definition} Fixed-point problem\n", "Given a function $g$, the **fixed-point problem** is to find a value $p$, called a **fixed point**, such that $g(p)=p$.\n", "```\n", "\n", "Given $f$ for rootfinding, we could define $g(x)=x-f(x)$, and then $f(r)=0$ implies $g(r)=r$ and vice versa. There are infinitely many ways to make this transformation, such as $g(x)=x+cf(x)$ for any constant $c$. The process can be reversed, too. Given $g(x)$, we could define $f(x)=x-g(x)$, and then $g(p)=p$ implies $f(p)=0$.\n", "\n", "\n", "There is an extraordinarily simple way to try to find a fixed point of any given $g(x)$.\n", "\n", "```{index} ! fixed-point iteration\n", "```\n", "\n", "```{proof:algorithm} Fixed-point iteration\n", "Given function $g$ and initial value $x_1$, define\n", "```{math}\n", " :label: fixedpointiter\n", " x_{k+1} = g(x_k), \\qquad k=1,2,\\ldots.\n", "```\n", "\n", "This is our first example of an iterative algorithm that never quite gets to the answer, even if we use exact numbers. The idea is to generate a sequence of values that one hopes will converge to the correct result, and stop when we are satisfied that we are close enough to the limit. \n", "\n", "(demo-fp-spiral)=\n", "```{proof:demo}\n", "```\n", "\n", "```{raw} html\n", "