Contraction mapping

Original article: w:Contraction mapping

수학(mathematics)에서, 메트릭 공간(metric space) (M, d) 위에 수축 매핑, 또는 수축 또는 수축기는 M에서 자체로의 함수(function) f이며, M에서 모든 x와 y에 대해 다음을 만족하는 일부 비-음의 실수(real number) $0\leq k<1$가 있다는 속성을 가집니다:

$d(f(x),f(y))\leq k\,d(x,y).$

k의 가장 작은 그러한 값은 f의 립시츠 상수라고 불립니다. 수축적 맵은 때때로 립시츠 맵이라고 불립니다. 만약 위의 수축이 k ≤ 1에 대해 대신 만족시키면, 매핑은 비-확장 맵(non-expansive map)이라고 말합니다.

보다 일반적으로, 수축적 매핑의 아이디어는 매트릭 공간 사이의 맵에 대해 정의될 수 있습니다. 따라서, 만약 (M, d)와 (N, d)가 둘의 메트릭 공간이면, $f:M\rightarrow N$는 M에서 모든 x와 y에 대해 다음을 만족하는 상수 $0\leq k<1$가 있으며 수축적 매핑입니다:

$d'(f(x),f(y))\leq k\,d(x,y)$.

모든 각 수축 매핑은 립시츠 연속(Lipschitz continuous)이고 따라서 균등 연속(uniformly continuous)입니다 (립시츠 연속 함수에 대해, 상수 k는 더 이상 1보다 작지 않습니다).

수축 매핑은 많아야 하나의 고정 점(fixed point)을 가집니다. 게다가, 바나흐 고정-점 정리(Banach fixed-point theorem)는 비-빈(non-empty) 완비 메트릭 공간(complete metric space) 위에 모든 각 수축 매핑이 고유한 고정 점을 가지고, M에서 임의의 x에 대해 반복된 함수(iterated function) 수열 x, f (x), f (f (x)), f (f (f (x))), ...는 고정 점으로 수렴한다고 말합니다. 이 개념은 수축 매핑이 종종 사용되는 반복된 함수 시스템(iterated function systems)에 매우 유용합니다. 바나흐의 고정-점 정리는 역시 보통의 미분 방정식(ordinary differential equation)의 해의 존재를 입증하는 것에 적용되고, 역 함수 정리(inverse function theorem)의 하나의 증명에서 사용됩니다.

수축 매핑은 동적 프로그래밍(dynamic programming) 문제에서 중요한 역할을 합니다.

Firmly non-expansive mapping

$k=1$을 갖는 비-확장 매핑은 만약 다음이 ${\mathcal {H}}$에서 모든 x와 y에 대해 유지되면 힐베르트 공간(Hilbert space) ${\mathcal {H}}$에서 확고하게 비-확장 매핑으로 강화될 수 있습니다:

$\|f(x)-f(y)\|^{2}\leq \,\langle x-y,f(x)-f(y)\rangle .$

여기서

$d(x,y)=\|x-y\|$.

이것은 $\alpha =1/2$를 갖는 비확장 연산자로 평균화된 $\alpha$의 특별한 경우입니다. 확고하게 비-확장 매핑은 코시–슈바르츠 부등식(Cauchy–Schwarz inequality)을 통해 항상 비-확장입니다.

확고하게 비-확장 맵의 클래스는 볼록 조합(convex combination) 아래에서 닫힌 것이지만, 합성에서는 아닙니다. 이 클래스는 적절한, 볼록, 아래로-반연속 함수의 근위 매핑(proximal mappings)을 포함하고, 따라서 그것은 역시 비-빈 닫힌 볼록 집합(convex set) 위로의 직교 투영(projections)을 포함합니다.

확고하게 비-확장 연산자의 클래스는 최대적으로 단조 연산자(monotone operators)의 분해의 집합과 같습니다. 놀랍게도, 비확장 맵을 반복하는 것이 고정 점을 찾기 위한 보장을 갖지 않지만 (예를 들어 −1에 의한 곱셈), 확고한 비-확장성은 고정 포인트에 대한 전역 수렴을 보장하기에 충분하며, 고정 점이 존재한다는 조건 아래 그렇습니다. 보다 정확하게, 만약 ${\text{Fix}}f:=\{x\in {\mathcal {H}}\ |\ f(x)=x\}\neq \varnothing$이면, 임의의 초기 점 $x_{0}\in {\mathcal {H}}$에 대해, 다음을 반복하는 것이

$(\forall n\in \mathbb {N} )\quad x_{n+1}=f(x_{n})$

고정 점 $x_{n}\to z\in {\text{Fix}}f$으로 수렴을 산출합니다. 이 수렴은 무한-차원 설정에서 약할(weak) 수 있습니다.

Subcontraction map

부분수축 맵 또는 부분수축기는 다음을 만족하는 메트릭 공간 (M, d) 위에 맵 f입니다:

$d(f(x),f(y))\leq d(x,y);$

$d(f(f(x)),f(x))<d(f(x),x)\quad {\text{unless}}\quad x=f(x).$

만약 부분수축기 f의 이미지(image)가 컴팩트(compact)이면, f는 고정 점을 가집니다.

Locally convex spaces

반노름(seminorm)의 집합 P에 의해 주어진 토폴로지(topology)를 갖는 지역적으로 볼록 공간(locally convex space) (E, P)에서, 우리는 p(f(x) − f(y)) ≤ k_p p(x − y)를 만족하는 일부 k_p < 1를 만족하는 임의의 p ∈ P에 대해 p-수축을 맵 f로 정의할 수 있습니다. 만약 f가 모든 p ∈ P에 대해 p-수축이고 (E, P)가 순차적으로 완비이면, f는 임의의 수열 x_n+1 = f(x_n)의 극한으로 주어진 고정 점을 가지고, 만약 (E, P)가 하우스도르프(Hausdorff)이면, 고정된 점은 고유합니다.

See also

• Short map
• Contraction (operator theory)
• Transformation

Further reading

• Istratescu, Vasile I. (1981). Fixed Point Theory : An Introduction. Holland: D.Reidel. ISBN 978-90-277-1224-0. provides an undergraduate level introduction.
• Granas, Andrzej; Dugundji, James (2003). Fixed Point Theory. New York: Springer-Verlag. ISBN 978-0-387-00173-9.
• Kirk, William A.; Sims, Brailey (2001). Handbook of Metric Fixed Point Theory. London: Kluwer Academic. ISBN 978-0-7923-7073-4.
• Naylor, Arch W.; Sell, George R. (1982). Linear Operator Theory in Engineering and Science. Applied Mathematical Sciences. Vol. 40 (Second ed.). New York: Springer. pp. 125–134. ISBN 978-0-387-90748-2.