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 Bielecki norm method changes the norm used for an integral contraction mapping, allowing a larger time interval without changing the underlying continuous functions. On $C([a,b],X)$ for a Banach space $X$, useFor $Tu(t)=u_0+{\int }_a^{t}f(s,u(s))ds$ with a uniformly $L$-Lipschitz continuous right-hand side,Thus $\beta >L$ makes $T$ a contraction mapping. On a fixed finite interval this weighted supremum norm is equivalent to the usual one. The Banach fixed-point theorem applies when $T$ maps the chosen complete function space into itself.

For integration from $1$ to $t\in [1,b]$, the weight $t^{-c}$ gives the alternative bound $Lb/(c+1)$ for $c\ge 0$. Both versions reduce the integral operator bound by choosing a weight, rather than by claiming that a local existence theorem automatically gives a global solution for an arbitrary nonlinear vector field.

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 a fixed bounded smooth three-dimensional domain, the nonlinear mapsends $H^2$ into $L^2$. The Sobolev embedding theorem gives $H^2\hookrightarrow W^{1,4}\cap L^{\infty }$, and Holder inequality yieldsThe domain regularity is part of the embedding hypotheses.

For real $u,v$, write $w=u-v$. The difference identityand the same embeddings giveThus its local Lipschitz continuity constant on a ball of radius $R$ is $O(R^2)$. Composing this small nonlinear bound with a bounded linear elliptic inverse gives a contraction mapping on a sufficiently small ball, which is the mechanism of small-data existence for a nonlinear elliptic Dirichlet problem.

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 Picard iteration $y_{n+1}(x)=b+{\int }_a^{x}f(s,y_n(s))ds$, $y_0=b$, assume $|f|\le M$ and a Lipschitz constant $L$ on a rectangle containing every iterate. The first difference is at most $M|x-a|$. Integrating the preceding bound multiplied by $L$ proves the displayed estimate by mathematical induction. Its uniform bounds sum to a convergent exponential series for every finite $Lh$, so the Weierstrass M-test gives uniform convergence without requiring $Lh<1$.

For two arbitrary initial functions $y,z$ in a function set preserved by the Picard iteration operator $T$, the same induction givesThus some iterate is a contraction mapping on any fixed finite interval for which every iterate stays in that set. The iterated contraction argument gives a unique fixed point of $T$ on a nonempty complete metric space, without requiring $Lh<1$. For a rectangle with field bound $M$ and vertical radius $k$, $Mh\le k$ supplies the required self-mapping property.

Fixed-point iteration seeks a fixed point of a map $F$ by repeatedly setting $x_{k+1}=F(x_k)$. Convergence requires additional hypotheses; for example, a contraction mapping on a complete metric space has a unique fixed point reached by this iteration.

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$.

Let $T$ be a self-map of a nonempty closed subset of a Banach space, with the displayed bounds. Then $T$ has a unique fixed point $p$ and every orbit $x_n=T^n{x}_0$ converges to it. Indeed, $\Vert x_{n+1}-x_n\Vert \le {\alpha }_n\Vert x_1-x_0\Vert$ makes the orbit Cauchy by summing successive increments. The first bound makes $T$ continuous, so the limit is fixed. Since ${\alpha }_n\to 0$, the bounds also imply uniqueness. The tail sum gives $\Vert p-x_n\Vert \le {\sum }_{k\ge n}{\alpha }_k\Vert x_1-x_0\Vert$ for $n\ge 1$. A Volterra integral equation supplies factorially decreasing bounds even when the first iterate is not a contraction mapping.

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.