Documentation

Mathlib.Topology.MetricSpace.Contracting

Contracting maps #

A Lipschitz continuous self-map with Lipschitz constant K < 1 is called a contracting map. In this file we prove the Banach fixed point theorem, some explicit estimates on the rate of convergence, and some properties of the map sending a contracting map to its fixed point.

Main definitions #

Tags #

contracting map, fixed point, Banach fixed point theorem

def ContractingWith {α : Type u_1} [EMetricSpace α] (K : NNReal) (f : αα) :

A map is said to be ContractingWith K, if K < 1 and f is LipschitzWith K.

Equations
Instances For
    theorem ContractingWith.toLipschitzWith {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) :
    theorem ContractingWith.one_sub_K_pos' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) :
    0 < 1 - K
    theorem ContractingWith.one_sub_K_ne_zero {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) :
    1 - K 0
    theorem ContractingWith.edist_inequality {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {x : α} {y : α} (h : edist x y ) :
    edist x y (edist x (f x) + edist y (f y)) / (1 - K)
    theorem ContractingWith.edist_le_of_fixedPoint {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {x : α} {y : α} (h : edist x y ) (hy : Function.IsFixedPt f y) :
    edist x y edist x (f x) / (1 - K)
    theorem ContractingWith.eq_or_edist_eq_top_of_fixedPoints {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {x : α} {y : α} (hx : Function.IsFixedPt f x) (hy : Function.IsFixedPt f y) :
    x = y edist x y =
    theorem ContractingWith.restrict {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {s : Set α} (hs : Set.MapsTo f s s) :

    If a map f is ContractingWith K, and s is a forward-invariant set, then restriction of f to s is ContractingWith K as well.

    theorem ContractingWith.exists_fixedPoint {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) (x : α) (hx : edist x (f x) ) :
    ∃ (y : α), Function.IsFixedPt f y Filter.Tendsto (fun (n : ) => f^[n] x) Filter.atTop (nhds y) ∀ (n : ), edist (f^[n] x) y edist x (f x) * K ^ n / (1 - K)

    Banach fixed-point theorem, contraction mapping theorem, EMetricSpace version. A contracting map on a complete metric space has a fixed point. We include more conclusions in this theorem to avoid proving them again later.

    The main API for this theorem are the functions efixedPoint and fixedPoint, and lemmas about these functions.

    noncomputable def ContractingWith.efixedPoint {α : Type u_1} [EMetricSpace α] {K : NNReal} (f : αα) [CompleteSpace α] (hf : ContractingWith K f) (x : α) (hx : edist x (f x) ) :
    α

    Let x be a point of a complete emetric space. Suppose that f is a contracting map, and edist x (f x) ≠ ∞. Then efixedPoint is the unique fixed point of f in EMetric.ball x ∞.

    Equations
    Instances For
      theorem ContractingWith.efixedPoint_isFixedPt {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) :
      theorem ContractingWith.tendsto_iterate_efixedPoint {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) :
      Filter.Tendsto (fun (n : ) => f^[n] x) Filter.atTop (nhds (ContractingWith.efixedPoint f hf x hx))
      theorem ContractingWith.apriori_edist_iterate_efixedPoint_le {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) (n : ) :
      edist (f^[n] x) (ContractingWith.efixedPoint f hf x hx) edist x (f x) * K ^ n / (1 - K)
      theorem ContractingWith.edist_efixedPoint_le {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) :
      edist x (ContractingWith.efixedPoint f hf x hx) edist x (f x) / (1 - K)
      theorem ContractingWith.edist_efixedPoint_lt_top {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) :
      theorem ContractingWith.efixedPoint_eq_of_edist_lt_top {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} [CompleteSpace α] (hf : ContractingWith K f) {x : α} (hx : edist x (f x) ) {y : α} (hy : edist y (f y) ) (h : edist x y ) :
      theorem ContractingWith.exists_fixedPoint' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
      ys, Function.IsFixedPt f y Filter.Tendsto (fun (n : ) => f^[n] x) Filter.atTop (nhds y) ∀ (n : ), edist (f^[n] x) y edist x (f x) * K ^ n / (1 - K)

      Banach fixed-point theorem for maps contracting on a complete subset.

      noncomputable def ContractingWith.efixedPoint' {α : Type u_1} [EMetricSpace α] {K : NNReal} (f : αα) {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) (x : α) (hxs : x s) (hx : edist x (f x) ) :
      α

      Let s be a complete forward-invariant set of a self-map f. If f contracts on s and x ∈ s satisfies edist x (f x) ≠ ∞, then efixedPoint' is the unique fixed point of the restriction of f to s ∩ EMetric.ball x ∞.

      Equations
      Instances For
        theorem ContractingWith.efixedPoint_mem' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
        ContractingWith.efixedPoint' f hsc hsf hf x hxs hx s
        theorem ContractingWith.efixedPoint_isFixedPt' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
        theorem ContractingWith.tendsto_iterate_efixedPoint' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
        Filter.Tendsto (fun (n : ) => f^[n] x) Filter.atTop (nhds (ContractingWith.efixedPoint' f hsc hsf hf x hxs hx))
        theorem ContractingWith.apriori_edist_iterate_efixedPoint_le' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) (n : ) :
        edist (f^[n] x) (ContractingWith.efixedPoint' f hsc hsf hf x hxs hx) edist x (f x) * K ^ n / (1 - K)
        theorem ContractingWith.edist_efixedPoint_le' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
        edist x (ContractingWith.efixedPoint' f hsc hsf hf x hxs hx) edist x (f x) / (1 - K)
        theorem ContractingWith.edist_efixedPoint_lt_top' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hf : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) :
        edist x (ContractingWith.efixedPoint' f hsc hsf hf x hxs hx) <
        theorem ContractingWith.efixedPoint_eq_of_edist_lt_top' {α : Type u_1} [EMetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {s : Set α} (hsc : IsComplete s) (hsf : Set.MapsTo f s s) (hfs : ContractingWith K (Set.MapsTo.restrict f s s hsf)) {x : α} (hxs : x s) (hx : edist x (f x) ) {t : Set α} (htc : IsComplete t) (htf : Set.MapsTo f t t) (hft : ContractingWith K (Set.MapsTo.restrict f t t htf)) {y : α} (hyt : y t) (hy : edist y (f y) ) (hxy : edist x y ) :
        ContractingWith.efixedPoint' f hsc hsf hfs x hxs hx = ContractingWith.efixedPoint' f htc htf hft y hyt hy

        If a globally contracting map f has two complete forward-invariant sets s, t, and x ∈ s is at a finite distance from y ∈ t, then the efixedPoint' constructed by x is the same as the efixedPoint' constructed by y.

        This lemma takes additional arguments stating that f contracts on s and t because this way it can be used to prove the desired equality with non-trivial proofs of these facts.

        theorem ContractingWith.one_sub_K_pos {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) :
        0 < 1 - K
        theorem ContractingWith.dist_le_mul {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) (x : α) (y : α) :
        dist (f x) (f y) K * dist x y
        theorem ContractingWith.dist_inequality {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) (x : α) (y : α) :
        dist x y (dist x (f x) + dist y (f y)) / (1 - K)
        theorem ContractingWith.dist_le_of_fixedPoint {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) (x : α) {y : α} (hy : Function.IsFixedPt f y) :
        dist x y dist x (f x) / (1 - K)
        theorem ContractingWith.fixedPoint_unique' {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) {x : α} {y : α} (hx : Function.IsFixedPt f x) (hy : Function.IsFixedPt f y) :
        x = y
        theorem ContractingWith.dist_fixedPoint_fixedPoint_of_dist_le' {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) (g : αα) {x : α} {y : α} (hx : Function.IsFixedPt f x) (hy : Function.IsFixedPt g y) {C : } (hfg : ∀ (z : α), dist (f z) (g z) C) :
        dist x y C / (1 - K)

        Let f be a contracting map with constant K; let g be another map uniformly C-close to f. If x and y are their fixed points, then dist x y ≤ C / (1 - K).

        noncomputable def ContractingWith.fixedPoint {α : Type u_1} [MetricSpace α] {K : NNReal} (f : αα) (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] :
        α

        The unique fixed point of a contracting map in a nonempty complete metric space.

        Equations
        Instances For

          The point provided by ContractingWith.fixedPoint is actually a fixed point.

          theorem ContractingWith.fixedPoint_unique {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] {x : α} (hx : Function.IsFixedPt f x) :
          theorem ContractingWith.dist_fixedPoint_le {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] (x : α) :
          dist x (ContractingWith.fixedPoint f hf) dist x (f x) / (1 - K)
          theorem ContractingWith.aposteriori_dist_iterate_fixedPoint_le {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] (x : α) (n : ) :
          dist (f^[n] x) (ContractingWith.fixedPoint f hf) dist (f^[n] x) (f^[n + 1] x) / (1 - K)

          Aposteriori estimates on the convergence of iterates to the fixed point.

          theorem ContractingWith.apriori_dist_iterate_fixedPoint_le {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] (x : α) (n : ) :
          dist (f^[n] x) (ContractingWith.fixedPoint f hf) dist x (f x) * K ^ n / (1 - K)
          theorem ContractingWith.tendsto_iterate_fixedPoint {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] (x : α) :
          Filter.Tendsto (fun (n : ) => f^[n] x) Filter.atTop (nhds (ContractingWith.fixedPoint f hf))
          theorem ContractingWith.fixedPoint_lipschitz_in_map {α : Type u_1} [MetricSpace α] {K : NNReal} {f : αα} (hf : ContractingWith K f) [Nonempty α] [CompleteSpace α] {g : αα} (hg : ContractingWith K g) {C : } (hfg : ∀ (z : α), dist (f z) (g z) C) :

          If a map f has a contracting iterate f^[n], then the fixed point of f^[n] is also a fixed point of f.