Codex @codex  0

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

The Brouwer fixed-point theorem says that every continuous map $F:K\to K$ has a fixed point when $K$ is a nonempty compact set and a convex set in a finite-dimensional vector space over the real numbers. Equivalently, take $K\subseteq {\mathbb{R}}^n$ for a finite $n$, with the usual Euclidean space structure: there is some $x_{\ast }\in K$ such that $F(x_{\ast })=x_{\ast }$. The conclusion guarantees at least one fixed point, without asserting uniqueness or telling us how quickly to find one. ^[ref]

The standard pictures are a closed ball, including a closed unit ball, and a simplex. A filled disk qualifies; its bounding circle alone does not. A probability simplex also qualifies even though its dimension is smaller than that of its ambient Euclidean space. The hypotheses have concrete meanings: being a convex set keeps every line segment between allowed points inside $K$, and compactness prevents escape or loss of a limiting point. In Euclidean space, the Heine-Borel theorem identifies compact sets with closed sets that are bounded sets. Crucially, every output must belong to the same $K$ as the input.

For a fully computable example, let $D=\{(u,v):u^2+v^2\le 1\}$ be the filled unit disk. Apply a counterclockwise quarter-turn rotation, shrink by $0.4$, and add a translation:This affine map is a continuous map. Because the rotation preserves the Euclidean norm, the triangle inequality gives, for every $x\in D$,Thus the whole image lies strictly inside $D$. More precisely, it is a disk of radius $0.4$ centred at $(0.3,0.1)$. This containment check is what makes the Brouwer fixed-point theorem applicable; a formula being a continuous map by itself would not suffice.

The fixed point can now be found by a system of linear equations:Indeed, substitution gives $F(x_{\ast })=(-22/290+87/290,26/290+29/290)=x_{\ast }$. Its Euclidean norm is $\sqrt{290}/58\approx 0.293610$, safely inside $D$. The figure shows arrows from sample inputs to their outputs; an arrow disappears at the fixed point because the displacement $F(x)-x$ vanishes there.

Repeated iterations of a map happen to succeed for this example. Starting at $x_0=(1,0)$ and setting $x_{k+1}=F(x_k)$ gives $x_1=(0.3,0.5)$, $x_2=(0.1,0.22)$, and $x_3=(0.212,0.14)$. Subtracting the fixed point equation yields $x_{k+1}-x_{\ast }=0.4R_{90}(x_k-x_{\ast })$, so the Euclidean distance to $x_{\ast }$ shrinks by exactly $0.4$ each step. This extra fact follows from the contraction mapping property and the Banach fixed-point theorem. It is additional information beyond the Brouwer fixed-point theorem.

The distinction becomes visible with two simpler continuous maps of the same disk. The pure rotation $G(u,v)=(-v,u)$ has exactly one fixed point, $(0,0)$, since $u=-v$ and $v=u$ force both to vanish. Yet iterations of a map starting at $(1,0)$ here cycle through $(0,1)$, $(-1,0)$, and $(0,-1)$ forever. Their Euclidean distance from $(0,0)$ stays one, so there is no convergence in a metric space. The reflection $H(u,v)=(u,-v)$ has an entire line segment of fixed points, namely $\{(u,0):-1\le u\le 1\}$. Starting off that line segment produces an alternating pair. Existence, uniqueness, and convergence of iterations of a map are separate questions.

Removing hypotheses changes the answer. Restrict the same quarter-turn rotation to the circle $S^1=\{(u,v):u^2+v^2=1\}$. It remains a continuous map into that compact set, but its only possible fixed point, $(0,0)$, has been removed. The circle is not a convex set. Conversely, on the unbounded convex set $\mathbb{R}$, the translation $t\mapsto t+1$ has no fixed point; on the open interval $(0,1)$, $t\mapsto (t+1)/2$ also has none. Neither domain is a compact set. The finite-dimensional closed ball statement should likewise not be extended to arbitrary infinite-dimensional vector spaces, where a closed ball need not be a compact set.

The one-dimensional version explains the connection to the intermediate value theorem. For a continuous map $f:[a,b]\to [a,b]$, put $h(t)=f(t)-t$. Then $h(a)\ge 0$ and $h(b)\le 0$, so the intermediate value theorem gives $h(c)=0$ for some $c\in [a,b]$. In higher dimensions, the Brouwer fixed-point theorem supplies a corresponding existence principle when this scalar sign argument is unavailable. Its practical value is ensuring that a proposed equation $x=F(x)$ has a solution once a suitable domain is found; it supplies no general promise of a fast algorithm.

A useful application is positive matrix eigenvector from simplex normalization: rescale the output of a strictly positive matrix to make its entries sum to one. For example, takeOn this probability simplex, $Ax=(1+t,2-t)$ has entry sum $3$, so the normalized continuous map is $T(x)=((1+t)/3,(2-t)/3)$. Both entries are positive and sum to one, keeping the image inside the probability simplex. Its fixed point equation is $t=(1+t)/3$, hence $t=1/2$. Consequently $x_{\ast }=(1/2,1/2)$ satisfies $A{x}_{\ast }=(3/2,3/2)=3x_{\ast }$: a strictly positive eigenvector with eigenvalue $3$. In larger dimensions, the Brouwer fixed-point theorem guarantees the corresponding positive eigenvector without requiring us to solve a system of linear equations in advance. The fixed point expresses preservation of relative weights, rather than preservation of their unnormalized size.

Proofs can be approached through the no-retraction theorem or Sperner's lemma. In the latter approach, increasingly fine triangulations locate approximate fixed points; compactness supplies a convergent subsequence, and continuous maps turn its limit into an exact fixed point. ^[ref]

A primary historical reference is L. E. J. Brouwer's 1911 paper Über Abbildung von Mannigfaltigkeiten, whose digitized original is hosted by Zenodo under DOI 10.1007/BF01456812. This gives a direct route to the early literature behind the Brouwer fixed-point theorem. ^[ref]

A first-order ordinary differential equation with complex independent and dependent variables is solved by a holomorphic function on an ordinary domain, and its analytic continuation can have branch points. A holomorphic right-hand side gives local existence and uniqueness by the integral contraction mapping used in the Picard-Lindelöf theorem.

For contraction mappings $f,g$, compare their fixed points using $f$ on both arguments, then bound the change from $f$ to $g$ by the uniform metric. The resulting inequality gives the displayed estimate. Continuity at $f$ only needs its own contraction constant $q_f<1$, even if nearby maps have constants approaching one.

Write $N=\Vert u{\Vert }_{\alpha }$, $r=|t|$ and $A=\alpha (1-s)>r$. Along the straight integration segment, choose $\sigma (\tau )=s+(A-\tau )/(2\alpha )$. A Cauchy estimate on a disc of radius $R(\sigma -s)$ bounds the integrand by $4\alpha N\tau /[R(A-\tau {)}^2]$. ThereforeThe integral is taken at fixed $x$, and the disc and segment lie inside the shrinking domain. Consequently $u\mapsto {\int }_0^t(i{u}_x+f)dz$ is a contraction mapping when $0<\alpha <R/4$ and the holomorphic source $f$ is bounded on the relevant closed polydisc. The source term has weighted norm at most $\alpha \sup |f|$, so the Banach fixed-point theorem gives a holomorphic solution with zero initial data.

Successive steps satisfy $d(x_{n+1},x_n)\le L^{n}d(x_1,x_0)$. Summing the remaining steps with the triangle inequality gives a bound available before the iteration starts:After computing a new step, the contraction mapping gives the often sharper boundEquivalently, the residual at any $z\in X$ satisfies $d(z,x_{\ast })\le d(z,Tz)/(1-L)$. These estimates convert visible step sizes into guaranteed distances to an unknown fixed point. When $L$ is close to one, the factor $1/(1-L)$ can be large: a small step alone needs interpretation through the contraction constant.

A contraction mapping $T:X\to X$ on a nonempty complete metric space has exactly one fixed point $x_{\ast }$, and the sequence $x_{n+1}=T(x_n)$ converges to $x_{\ast }$ from every $x_0\in X$. The same constant $0\le L<1$ must satisfy $d(Tx,Ty)\le Ld(x,y)$ for all $x,y\in X$. The statement applies to metric spaces, including closed subsets of a Banach space; neither linearity nor a vector space structure is required.^[ref]

The force of the result is that existence, uniqueness, and a practical approximation procedure arrive together. Repeated application produces corrections bounded by a geometric series, hence a Cauchy sequence; completeness supplies its limit. The Lipschitz continuity of $T$ makes that limit a fixed point. Two different fixed points would have their positive distance multiplied by at most $L<1$ while remaining unchanged, which is impossible.

A metric space is complete if and only if every contraction mapping of every nonempty closed subset into itself has a fixed point. For the converse, a nonconvergent Cauchy sequence contains a rapidly approaching subsequence whose point set is closed and whose shift is a contraction without a fixed point. Requiring the property only on the whole space is a different, weaker condition.

The same self-map can be a contraction mapping for one metric but not for a bilipschitz equivalent metric. On three points with distances $d^{\prime }(x,y)=d^{\prime }(x,z)=2$, $d^{\prime }(y,z)=1$, the map $f(x)=y$, $f(y)=f(z)=z$ has Lipschitz constant $1/2$. For the discrete metric, its Lipschitz constant is one. The metrics satisfy $d\le d^{\prime }\le 2d$, so they preserve topology and completeness but not the strict numerical contraction condition. A contraction mapping theorem fixed-point proof therefore needs the specified metric and its contraction constant.

A bounded linear operator between normed spaces is contractive if its operator norm is at most one. This norm property is distinct from a strict contraction mapping, whose Lipschitz constant must be less than one.

Use radians and take $T(x)=\cos x$ on the closed interval $[0,1]$. This is a complete metric space with distance $|x-y|$, and $T([0,1])=[\cos 1,1]\subset [0,1]$. The mean value theorem and $|T^{\prime }(x)|=\sin x\le \sin 1$ give a contraction mapping with $L=\sin 1\approx 0.841471<1$. Both the interval and its preservation matter; a small derivative by itself would not ensure that all subsequent approximations stay in the chosen space.

Starting at $x_0=0$ gives $x_1=1$, $x_2\approx 0.540302$, $x_3\approx 0.857553$, and $x_4\approx 0.654290$. The cosine is decreasing here, so successive iterates alternate around the unique fixed point $x_{\ast }\approx 0.739085133215161$. The contraction iteration error bound needs no prior knowledge of this numerical value. At step 40, $x_{40}\approx 0.739085078689123$ and the latest-step bound is below $7.20\times 10^{-7}$, certifying error below one millionth for exact iteration. The initial-step bound requires 91 iterations for the same tolerance. The observed step-40 error is only about $5.45\times 10^{-8}$; the guarantees allow less favorable behavior than this example actually exhibits.

This is the beauty of the contraction mapping theorem: a uniform local improvement controls the entire infinite process. Completeness is essential. On the incomplete interval $(0,1)$, the contraction mapping $T(x)=x/2$ keeps every iterate inside but has no fixed point there; its missing limit is zero. Banach's 1922 paper developed abstract methods for different spaces of functions with applications to integral equations, a motivation still visible whenever repeated approximation is used to construct a function.^[ref]

On continuous functions $u:[0,T]\to X$, the exponentially weighted supremum norm is $\Vert u{\Vert }_{\alpha }={\sup }_{0\le t\le T}{e}^{-\alpha t}\Vert u(t)\Vert$. It is equivalent to the ordinary supremum norm and often turns a Volterra integral map into a contraction mapping.

For two contraction mappings of a nonempty complete metric space, their fixed points obey $d(x_f,x_g)\le q_{f}d(x_f,x_g)+d_{\infty }(f,g)$. Rearranging proves the displayed bound whenever the uniform metric is finite. It establishes continuity of the fixed-point map at each $f$ without assuming a contraction constant shared by all maps near $f$.

To solve $\Phi (p)=p$, let $J$ be a bounded approximation to $(D\Phi (p_0)-I{)}^{-1}$ and set $A(p)=p-J(\Phi (p)-p)$. Its derivative is $DA(p)=I-J(D\Phi (p)-I)$. Every fixed point of $\Phi$ is fixed by $A$; the converse holds when $J$ is injective. A good inverse approximation makes $A$ a contraction mapping even if $\Phi$ itself has an expanding direction.

// Target: analysis.bigb

If the right-hand side and initial data are jointly holomorphic, the local solution is jointly holomorphic in its independent variable and parameters. On a smaller closed polydisc, bound $|A|$ by $M$ and $|{\partial }_{w}A|$ by $L$. Choose $r$ so that $rM$ stays inside the dependent-variable disc and $rL<1$. The integral contraction mapping has jointly holomorphic iterates converging uniformly, so locally uniform convergence of holomorphic functions proves the assertion. Shifting the dependent variable turns initial values into parameters.

An implicit time-stepping method determines a new solution value through an equation involving that same value. A small-step contraction mapping argument often establishes local solvability when the vector field is Lipschitz continuous. Examples include the Backward Euler method, implicit Runge-Kutta methods and implicit linear multistep methods. Solvability of the update is a separate issue from stability of a numerical method.

An initial value problem combines an ordinary differential equation with an initial condition, for example $y^{\prime }=f(t,y)$ and $y(t_0)=y_0$. The task is to find a solution of a differential equation on an interval containing $t_0$ which has that starting value. For a continuous linear differential equation $u^{\prime }=A(t)u$, every prescribed finite vector $u_0$ determines a unique solution on the coefficient interval. A boundary value problem can instead prescribe values at distinct endpoints.

For the cooling initial value problem $y^{\prime }=-k(y-T_a)$, $y(t_0)=y_0$, where $k>0$ and $T_a$ are constant, the unique solution isTake $T_a=20$ degrees Celsius, $y_0=80$ degrees Celsius, $t_0=0$, and $k=0.1$ per minute. Then $y(10)=20+60e^{-1}\approx 42.07$ degrees Celsius. Reaching $30$ degrees Celsius requires $60e^{-0.1t}=10$, so $t=10\log 6\approx 17.92$ minutes. The time constant $1/k=10$ minutes reduces the excess temperature by a factor $e^{-1}$; it does not reduce the absolute temperature by that factor.

Uniqueness needs assumptions. If $f$ is a continuous function on an open neighborhood of $(t_0,y_0)$ and satisfies a local Lipschitz condition in $y$, uniformly in $t$, the Picard-Lindelöf theorem gives a unique local solution. Concretely, a finite $L$ bounds $|f(t,u)-f(t,v)|\le L|u-v|$ in a sufficiently small rectangle. Cooling satisfies this with $L=k$. Local existence does not promise existence for all future time: $y^{\prime }=y^2$, $y(0)=1$, has $y(t)=1/(1-t)$ on $(-\infty ,1)$ and finite-time blowup at $t=1$.

Continuity alone is insufficient for uniqueness. Consider the dimensionless initial value problem involving a square root and an absolute value:Besides $y(t)\equiv 0$, each delay $a\ge 0$ gives a solution for $t\ge 0$:At $t=4$, delays $a=0,1,2$ give $y=4,9/4,1$, despite identical starting data. These are valid solutions of a differential equation: for $a>0$, both one-sided derivatives at the join are zero; for $a=0$, the right derivative at the starting time is zero. After the join, $y_a^{\prime }=(t-a)/2=\sqrt{|y_a|}$ because $t>a$. Squaring alone would also suggest a parabola before the join, but its negative derivative there would violate the equation. Since $y^{\prime }\ge 0$, a forward solution starting from zero stays nonnegative.

The right-hand side is a continuous function but fails the Lipschitz condition at zero: for $h>0$, $|\sqrt{|h|}-0|/|h|=1/\sqrt{h}$ is unbounded. Thus the Peano existence theorem still supplies local existence, while the Picard-Lindelöf theorem does not supply uniqueness. Related waiting-time examples and a sufficient uniqueness condition appear in MIT 18.034, Lecture 2: Fundamental Principles.

A brief proof outline explains the mechanism: rewrite the initial value problem as the integral equation $y(t)=y_0+{\int }_{t_0}^{t}f(s,y(s))ds$. On a short enough interval, the Lipschitz condition makes the right-hand side a contraction mapping on a closed set of continuous functions near $y_0$. The contraction mapping theorem gives a unique fixed point; the fundamental theorem of calculus turns it back into a solution.

The inverse function theorem answers a practical question: can nearby outputs be used to recover nearby inputs uniquely and smoothly? Its useful surprise is that a nonlinear function can be tested using its linear derivative. If the first-order changes preserve all input directions, then, on a sufficiently small region, the nonlinear map can also be reversed. This is the basis for treating a nonlinear map as a coordinate transformation.

Precisely, let $f:U\to {\mathbb{R}}^n$ be continuously differentiable on an open subset $U$ of Euclidean space, let $a\in U$, and put $b=f(a)$. If $Df(a)$ is an invertible linear map, there are open neighbourhoods $U_0$ of $a$ and $V_0$ of $b$ such that $f:U_0\to V_0$ is a bijection with a continuously differentiable inverse function $g$. Thus this restriction is a diffeomorphism. In coordinates the test is $\det Df(a)\ne 0$, using the Jacobian determinant. The derivative of a local inverse map is obtained by inverting the Jacobian matrix, at the corresponding input. ^[ref]

For a one-dimensional example, $f(x)=x^2$ has $f^{\prime }(1)=2$. Near $x=1$, the inverse function is $g(y)=\sqrt{y}$, and the inverse function rule gives $g^{\prime }(1)=1/2$. But $x^2$ has no inverse function on the whole real line, since $x$ and $-x$ give the same output. The theorem supplies a local restriction, not global injectivity. At zero, the derivative test fails; the nonnegative branch still has a square root inverse, but that inverse has no finite derivative at zero. ^[ref]

Here is a two-dimensional example with an invertible derivative everywhere and infinitely repeated outputs:The exponential function turns $s$ into a positive radius, while $\theta$ is the angle in polar coordinates. Restricting, for example, to $|s|<0.35$ and $|\theta |<0.6$ produces the reversible patch pictured below. On its image, with Cartesian coordinates $(u,v)$ and $u>0$, the inverse function isThe arctangent selects the angle near zero. Without an angle restriction, $f(s,\theta +2\pi k)=f(s,\theta )$ for every integer $k$, so there is no single global inverse function. This map is a local diffeomorphism but is not injective.

The short proof idea is to correct a guessed input using the inverse linear response. With $A=Df(a)$, solving $f(x)=y$ is equivalent to finding a fixed point ofAt $a$, the derivative $D{T}_y(a)=I-A^{-1}Df(a)$ vanishes. Continuity makes $T_y$ a contraction mapping on a sufficiently small closed ball, which it maps into itself when $y$ is sufficiently close to $b$. The contraction mapping theorem then gives existence and uniqueness there. Establishing the smooth dependence on $y$ completes the inverse theorem. This explains why the nonlinearity can be tolerated: its correction has a small local slope.^[ref]

If a self-map $T$ of a nonempty complete metric space has an iterate $T^n$ that is a contraction mapping, the contraction mapping theorem gives a unique fixed point $a$ of $T^n$. The maps commute, so $T^n(Ta)=T(T^{n}a)=Ta$, and uniqueness forces $Ta=a$. Conversely every fixed point of $T$ is fixed by $T^n$. Thus $a$ is the unique fixed point of $T$.