Fixed point (mathematics)

수학(mathematics)에서, 함수(function)의 고정된 점(fixed point) (때때로 고정점(fixpoint)으로 단축되며, 역시 불변 점(invariant point)으로 알려져 있음)은 함수에 의해 자체로 매핑되는 함수의 도메인(domain)의 원소입니다. 즉 말하자면, c는 만약 f(c) = c이면 함수 f의 고정된 점입니다. 이것은 f(f(...f(c)...)) = fⁿ(c) = c임을 의미하며, f를 재귀적으로 계산할 때 중요한 종료하는 고려-사항입니다. 고정된 점의 집합(set)은 때때로 고정된 집합(fixed set)이라고 불립니다.

예를 들어, 만약 f가 다음에 의해 실수(real number) 위에 정의되면,

f(x)=x^{2}-3x+4,

2는 f의 고정된 점인데, 왜냐하면 f(2) = 2이기 때문입니다.

모든 함수가 고정된 점을 가지는 것은 아닙니다: 예를 들어, 만약 f가 실수 위에 f(x) = x + 1로 정의된 함수이면, 그것은 고정된 점을 가지지 않는데, 왜냐하면 x는 임의의 실수에 대해 x + 1과 절대 같지 않기 때문입니다. 그래픽 용어에서, 고정된 점 x는 점 (x, f(x))가 직선 y = x 위에 있음을 의미하거나, 다른 말로, f의 그래프(graph)는 해당 직선과 공통으로 점을 가집니다.

함수의 유한 횟수의 반복(iterations) 후에 같은 값으로 돌아오는 점은 주기 점(periodic point)이라고 불립니다. 고정된 점은 주기가 일과 같은 주기 점입니다. 투영 기하학(projective geometry)에서, 투영성(projectivity)의 고정된 점은 두배 점(double point)이라고 불립니다.^[1]^[2]

갈루아 이론(Galois theory)에서, 필드 자기-동형(field automorphism)의 집합의 고정된 점의 집합은 동형의 집합의 고정된 필드(fixed field)로 불리는 필드(field)입니다.

Attractive fixed points

함수 f의 당기는 고정된 점(attractive fixed point)은 x₀에 충분히 가까운 도메인에서 x의 임의의 값에 대해, 다음 반복된 함수(iterated function) 수열이 x₀에 수렴(converges)하는 것을 만족하는 f의 고정된 점 x₀입니다:

x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots

.

전제-조건의 표현과 그러한 해의 존재에 대한 증명은 바나흐 고정된-점 정리(Banach fixed-point theorem)에 의해 제공됩니다.

자연스러운 코사인(radian) 함수 ("자연스러운"은 도 또는 다른 단위에서가 아니라 라이안(radian)에서를 의미합니다)는 정확히 하나의 고정된 점을 가지며, 이것은 당기는 것입니다. 이 경우에서, "충분히 가까운"은 엄격한 기준은 아닙니다—이것을 시연하기 위해, 임의의 실수에서 시작하고 계산기에서 cos 키를 반복적으로 누르십시오 (먼저 계산기가 "라디안" 모든인지를 확인하십시오). 결국 약 0.739085133으로 수렴하며, 이것은 고정된 점입니다. 즉, 코사인 함수의 그래프가 직선 $y=x$ 와 교차하는 곳입니다.^[3]

모든 고정된 점이 당기는 것은 아닙니다. 예를 들어, x = 0는 함수 f(x) = 2x의 고정된 점이지만, 영 이외의 임의의 값에 대해 이 함수의 반복은 빠르게 발산합니다. 어쨌든, 함수 f가 고정된 점 x₀의 열린 이웃에서 연속적으로 미분-가능이고, $|f\,'(x_{0})|<1$ 이면, 당김은 보장됩니다.

당기는 고정된 점은 끌개(attractor)의 더 넓은 수학적 개념의 특별한 경우입니다.

당기는 고정된 점은 만약 그것이 역시 랴푸노프 안정(Lyapunov stable)이면 안정된 고정된 점(stable fixed point)으로 말합니다.

고정된 점이 만약 랴푸노프 안정(Lyapunov stable)이지만 당기는 것이 아니면 중립적으로 안정된 고정된 점(neutrally stable fixed point)으로 말합니다. 이차의 선형 동차 미분 방정식(linear homogeneous differential equation)의 중심은 중립적으로 안정된 고정된 점의 예제입니다.

여러 당기는 점은 당기는 고정된 집합(attractive fixed set)에서 수집될 수 있습니다.

Applications

많은 필드에서, 평형 또는 안정성(stability)은 고정된 점의 관점에서 설명될 수 있는 기본 개념입니다. 일부 예제는 뒤따릅니다.

경제학(economics)에서, 게임(game)의 내쉬 균형(Nash equilibrium)은 게임의 최상의 응답 대응(best response correspondence)의 고정된 점입니다. 존 내쉬(John Nash)는 경계학에서 노벨 상을 얻었던 그의 생산적인 논문에 대해 가쿠타니 고정된-점 정리(Kakutani fixed-point theorem)를 개발합니다.

물리학(physics)에서, 위상 전이의 이론(theory of phase transitions)에서 보다 정확하게, 불안정한 고정된 점 근처의 선형화는 재정규화 그룹(renormalization group)을 발명한 윌슨(Wilson)의 노벨 상을 수상한 연구와 용어 "임계 현상(critical phenomenon)"의 수학적 설명으로 이어졌습니다.^[4]^[5]

프로그래밍 언어(Programming language) 컴파일러(compilers)는 프로그램 분석에 고정된 점 계산을 사용합니다. 예를 들어, 데이터-흐름 분석(data-flow analysis), 이것은 코드 최적화(optimization)에 종종 요구됩니다. 그것들은 역시 일반적인 프로그램 분석 방법 추상 해석(abstract interpretation)에 의해 사용되는 핵심 개념입니다.^[6]

유형 이론(type theory)에서, 고정된-점 조합기(fixed-point combinator)는 비-유형된 람다 계산법(untyped lambda calculus)에서 재귀 함수의 정의를 허용합니다.

모든 웹 페이지의 페이지랭크(PageRank) 값의 벡터는 월드 와이드 웹(World Wide Web)의 링크 구조에서 파생된 선형 변환(linear transformation)의 고정된 점입니다.

마르코프 체인(Markov chain)의 정류 분포는 일 단계 전이 확률 함수의 고정된 점입니다.

논리학자 솔 크립키(Saul Kripke)는 그의 영향력-있는 진리의 이론에서 고정된 점의 사용을 만듭니다. 그는 단어의 발생을 포함하지 않은 언어의 분절에서 시작하여 "진리"를 재귀적으로 정의하고, 프로세스가 중단되어 임의의 새로 잘-정의된 문장이 나오지 않을 때까지 계속함으로써 부분적으로 정의된 진리 술어 ("이 문장은 사실이 아닙니다"와 같이 문제가-있는 문장에 대해 비-정의된 채로 남겨두는 문장)를 생성하는 방법을 보여줍니다. (이것은 셀-수-있는 무한(countable infinity) 단계를 취합니다.) 즉, 언어 L에 대해, L′ ( "엘-프라임"으로 읽음)을 L에 더해짐으로써, L에서 각 문장 S에 대해, 문장 "S는 참입니다."와 같이 생성된 언어로 놓습니다. 고정된 점은 L′이 L일 때 도달됩니다; 이 시점에서 "이 문장은 참이 아닙니다"와 같은 문장은 비-정의된 채로 남겨지므로, 크립키에 따르면, 그 이론은 그것 자신의 진리 술어를 포함하는 자연어에 대해 적합합니다.

Topological fixed point property

토폴로지적 공간(topological space) $X$ 는 만약 임의의 다음 연속 함수(continuous function)에 대해

f\colon X\to X

$f(x)=x$ 를 만족하는 $x\in X$ 가 존재하면 고정된 점 속성(fixed point property, 짧게 FPP)를 가진다고 말합니다.

FPP는 토폴로지적 불변(topological invariant)입니다. 즉, FPP는 임의의 위상-동형(homeomorphism)에 의해 보존됩니다. FPP는 역시 임의의 수축(retraction)에 의해 보존됩니다.

브라우어르 고정된-점 정리(Brouwer fixed-point theorem)에 따르면, 유클리드 공간(Euclidean space)의 모든 각 컴팩트(compact) 및 볼록(convex) 부분-집합(subset)은 FPP를 가집니다. 컴팩트성 단독으로 FPP를 의미하지는 않고 볼록성은 심지어 토폴로지적 속성도 의미하지는 않으므로 FPP를 토폴로지적으로 특성을 부여하는 방법을 묻는 것이 좋습니다. 1932년에 보르수크(Borsuk)는 축약-가능성(contractibility)과 함께 컴팩트성이 FPP에 대해 유지하기 위한 필요 및 충분 조건일 수 있는지 여부를 물었습니다. 그 문제는 추측이 키노시타(Kinosita)에 의해 FPP없이 컴팩트 축약-가능 공간의 사례를 발견하여 반증될 때까지 20년 동안 열려 있었습니다.^[7]

Generalization to partial orders: prefixpoint and postfixpoint

그 개념과 용어는 부분 순서로 일반화됩니다. ≤을 집합 X에 걸쳐 부분 순서로 놓고 f: X → X를 X에 걸쳐 함수로 놓습니다. 그런-다음 f의 이전-고정점 (prefixpoint, 또는 pre-fixpoint)는 f(p) ≤ p를 만족하는 임의의 p입니다. 마찬가지로 f의 이후-고정점 (postfixpoint 또는 post-fixpoint)은 p ≤ f(p)를 만족하는 p입니다.^[8] (크나스터–타르스키 정리(Knaster–Tarski theorem)를 표현하기 위한 한 방법은 완전 격자(complete lattice) 위에 단조 함수(monotone function)가 그것의 최소 이전-고정점과 일치하는 최소 고정점(least fixpoint) (및 비슷하게 최대 이후-고정점을 일치하는 최대 고정점)을 가진다라고 말하는 것입니다. 이전-고정점 및 이후-고정점은 이론적 컴퓨터 과학(theoretical computer science)에서 응용을 가집니다.^[9]

Notes

^ Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.
^ G. B. Halsted (1906) Synthetic Projective Geometry, page 27
^ Weisstein, Eric W. "Dottie Number". Wolfram MathWorld. Wolfram Research, Inc. Retrieved 23 July 2016.
^ https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3174
^ https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3184
^ https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml
^ Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. ISSN 0016-2736.
^ B. A. Davey; H. A. Priestley (2002). Introduction to Lattices and Order. Cambridge University Press. p. 182. ISBN 978-0-521-78451-1.
^ Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine

External links

An Elegant Solution for Drawing a Fixed Point

[1] Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.

[2] G. B. Halsted (1906) Synthetic Projective Geometry, page 27

[wolfram-3] Weisstein, Eric W. "Dottie Number". Wolfram MathWorld. Wolfram Research, Inc. Retrieved 23 July 2016.

[4] ttps://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3174

[5] ttps://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3184

[6] ttps://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml

[7] Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. ISSN 0016-2736.

[DaveyPriestley2002-8] B. A. Davey; H. A. Priestley (2002). Introduction to Lattices and Order. Cambridge University Press. p. 182. ISBN 978-0-521-78451-1.

[9] Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]