고정점(수학)

수학에서, 고정점(fix point) 또는 불변점(fix point)은 주어진 변환 하에서 변하지 않는 값입니다.구체적으로 함수의 경우 고정점은 함수에 의해 자신과 매핑되는 요소입니다.

함수의 고정점

형식적으로는 $c$ 가 $도메인$ 과 코드 도메인 모두에 속하고 $f (c)$ = c인 $경우$ c는 함수의 고정점입니다.

예를 들어 만약 f가 실수에 정의된다면 다음과 같이

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

f

(2)

=

2

이므로 2는 f 의 고정된

점

입니다.

모든 함수에 고정된 점이 있는 것은 아닙니다. $예$ 를 들어 f $(x)$ = $x$ + 1은 고정된 점이 없습니다. $x$ 는 어떤 실수에 $대해서$ 도x + $1$ 과 동일하지 않기 때문입니다.그래픽 용어에서 고정점 $x$ 는 점 $(x,$ $f (x))$ 가 $y$ = $x$ 선 위에 있음을 의미하거나, 다른 말로 $f$ 의 그래프가 해당 선과 공통된 점을 가지고 있음을 의미합니다.

고정점반복

수치 분석에서 고정점 반복은 함수의 고정점을 계산하는 방법입니다. $특히$ f {\ $displaystyle$ f $}$ 도메인의 $x_{0}$ 점 $x_{0}$ $x_{0}$ ${\$ $displaystyle x_{0}$ 인 도메인과 코드 도메인이 동일한 $f$ f {\ $displaystyle$ f $}$ 가 주어졌을 $f$ 때 고정점 반복은

x_{n+1}=f(x_{n}),\,n=0,1,2,\dots

which gives rise to the sequence $x_{0},x_{1},x_{2},\dots$ of iterated function applications $x_{0},f(x_{0}),f(f(x_{0})),\dots$ which is hoped to converge to a point $x$ . If $f$ is continuous, then one can prove that the obtained $x$ $x$ 은 $x$ (는) $f$ 의 고정 지점입니다 $f$

고정점 반복에 대해 고정점 유인, 고정점 반발 및 주기점 개념이 정의됩니다.

고정점 정리

고정점 정리는 어떤 일반적인 조건 하에서 적어도 하나의 고정점이 존재한다는 것을 말하는 결과입니다.^[1]

예를 들어, 바나흐 고정점 정리(1922)는 고정점 반복이 만족될 경우 항상 고정점으로 수렴한다는 것을 보장하는 일반적인 기준을 제공합니다.

브라우어 고정점 정리(1911)는 n차원 유클리드 공간의 닫힌 단위 공에서 자신으로 이어지는 연속 함수는 반드시 고정점을 가져야 한다고 말하지만, 그것은 고정점을 찾는 방법을 설명하지 않습니다.

대수적 위상수학의 레프셰츠 고정점 정리(및 닐슨 고정점 정리)는 고정점을 셀 수 있는 방법을 제공합니다.

그룹 작업의 고정점

대수학에서, $그룹$ 작용 ⋅가 ${\displaystyle$ \cdot}인 집합 X에 작용하는 그룹 G에 대해, X의 $g\cdot x=x$ 는 g $g\cdot x=x$ ⋅ x = x {\ $displaystyle$ g $\cdot$ x = x}인 경우의 고정 $g\cdot x=x$ 이라고 합니다.

군 G의 자기 변형 f 의 $G^{f}$ 고정점 부분군 $G^{f}$ ${\$ 는 G의 부분군입니다.

G^{f}=\{g\in G\mid f(g)=g\

마찬가지로, 링 R의 오토모피즘 f의 $R^{f}$ 고정점 서브링 $R^{f}$ ${\$ 는 고정점 f의 서브링, 즉,

R^{f}=\{r\in R\mid f(r)=r\}

갈루아 이론에서, 장 오토모피즘 집합의 고정점 집합은 오토모피즘 집합의 고정장이라고 불리는 장입니다.

위상고정점속성

위상 공간 $X$ $X$ 은(는) 연속 함수인 경우 고정 점 속성(FPP)을 갖는다고 합니다 $X$ .

f\colon X\to X

$f(x)=x$ ( x) = x {\ $displaystyle$ f(x) = x $f(x)=x$ 인 x $f(x)=x$ ∈ X ${\$ displaystyle x\in X}가 존재합니다.

FPP는 위상 불변이며, 즉 어떤 동형에 의해서도 보존됩니다.FPP는 또한 임의의 후퇴에 의해서도 보존됩니다.

브라우어 고정점 정리에 따르면, 유클리드 공간의 모든 콤팩트하고 볼록한 부분 집합은 FPP를 가집니다.콤팩트성만으로는 FPP를 의미하지 않으며 볼록성은 위상학적 특성도 아니므로 FPP를 위상적으로 특성화하는 방법을 묻는 것이 타당합니다.1932년 보르수크는 수축성과 함께 콤팩트함이 FPP가 유지할 필요충분조건이 될 수 있는지 물었습니다.이 문제는 FPP가 없는 압축 가능한 공간의 예를 발견한 키노시타에 의해 추측이 반증될 때까지 20년 동안 열려 있었습니다.^[2]

부분주문고정점

도메인 이론에서 고정점의 개념과 용어는 부분 순서로 일반화됩니다.≤를 집합 X에 대한 부분 차수라고 하고 f를 X에 대한 함수라고 합니다. X → X → X를 X에 대한 함수라고 합니다.그러면 f 의 프리픽스 포인트(또한 프리픽스 포인트 또는 프리픽스 포인트로 단축됨)^{[citation needed]}는 f(p) ≤ p인 임의의 p입니다. 마찬가지로, 포스트픽스 포인트 of f 는 p ≤ f(p)인 임의의 p입니다.^[3]반대되는 용법이 간혹 나타납니다.^[4]말키스는 여기에 제시된 정의를 다음과 같이 정당화합니다: "f는 f(x) ≤ x의 부등호 앞에 있기 때문에, 그러한 x를 접두점이라고 합니다."^[5]고정점은 접두사점이면서 후픽스점인 점입니다.접두사점과 후픽스점은 이론 컴퓨터 과학에 응용됩니다.^[6]

최소고정점

순서 이론에서, 부분 순서 집합(포셋)에서 자신으로의 함수의 최소 고정점은 포셋의 순서에 따라 서로 다른 고정점보다 작은 고정점입니다.함수에 최소 고정점이 있을 필요는 없지만, 고정점이 있을 경우 최소 고정점이 유일합니다.

크나스터-타르스키 정리를 표현하는 한 가지 방법은 완전한 격자 위의 단조 함수가 최소 접두점과 일치하는 최소 고정점을 갖는다고 말하는 것입니다(그리고 마찬가지로 최대 고정점은 최대 후 고정점과 일치합니다.^[7]

고정점결합기

컴퓨터 과학의 조합 논리에서, 고정점 조합기(fix-point combinator)는 고차 함수 ${\textsf {fix}}$ {\ $displaystyle {\textsf {fix}}$ 이며 ${\textsf {fix}}$ , 인수 함수의 고정점이 존재하는 경우 이 함수를 반환합니다.공식적으로, 함수 f 가 하나 이상의 고정점을 가지면,

{\textsf {fix}}\f=f\({\textsf {fix}\f)\,

고정점 논리

수학적 논리학에서 고정점 논리는 재귀를 표현하기 위해 도입된 고전적 술어 논리의 확장입니다.그들의 발전은 설명적 복잡성 이론과 데이터베이스 쿼리 언어, 특히 데이터로그와의 관계에 의해 동기 부여되어 왔습니다.

적용들

많은 분야에서 평형 또는 안정성은 고정점으로 설명할 수 있는 기본 개념입니다.몇 가지 예가 있습니다.

투영 기하학에서 투영도의 고정점을 이중점이라고 합니다.^[8]^[9]
경제학에서, 게임의 내쉬 균형은 게임의 최상의 반응 대응의 고정점입니다.존 내쉬는 노벨 경제학상을 수상한 획기적인 논문으로 카쿠타니 고정점 정리를 이용했습니다.
물리학에서, 더 정확하게는 상전이 이론에서, 불안정한 고정점 근처의 선형화는 윌슨의 노벨상 수상작이 재규격화 그룹을 발명하게 했고, "임계현상"이라는 용어에 대한 수학적 설명으로 이어졌습니다.^[10]^[11]
프로그래밍 언어 컴파일러는 코드 최적화를 위해 종종 필요한 데이터 흐름 분석과 같은 프로그램 분석을 위해 고정 지점 계산을 사용합니다.일반 프로그램 분석 방법 추상적 해석에서 사용하는 핵심 개념이기도 합니다.^[12]
유형 이론에서 고정점 결합기는 비유형 람다 미적분학에서 재귀 함수의 정의를 허용합니다.
모든 웹 페이지의 페이지 랭크 값 벡터는 World Wide Web의 링크 구조에서 도출된 선형 변환의 고정점입니다.
마코프 체인의 정지 분포는 원스텝 전이 확률 함수의 고정점입니다.
고정점은 반복 함수에 대한 공식을 찾는 데 사용됩니다.

참고 항목

불변 (수학)

메모들

^ Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.
^ Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. doi:10.4064/fm-40-1-96-98. ISSN 0016-2736.
^ Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). Proceedings, 18th IEEE Symposium on Foundations of Computer Science. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062.
^ Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF). Pacific Journal of Mathematics. 82 (1): 43–57. doi:10.2140/pjm.1979.82.43.
^ Malkis, Alexander (2015). "Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial" (PDF). Reachability Problems. Lecture Notes in Computer Science. 9328: 114–127. doi:10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID 17640585. Archived from the original (PDF) on 2022-08-10.
^ Yde Venema (2008) Wayback Machine에서 2012년 3월 21일 보관된 Modal μ-calculus에 대한 강의
^ Yde Venema (2008) Wayback Machine에서 2012년 3월 21일 보관된 Modal μ-calculus에 대한 강의
^ Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.
^ G. B. Halsted (1906) 합성 투영 기하학 27페이지
^ Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture". Physical Review B. 4 (9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi:10.1103/PhysRevB.4.3174.
^ Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior". Physical Review B. 4 (9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi:10.1103/PhysRevB.4.3184.
^ "P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints".

외부 링크

고정점 그리기를 위한 우아한 솔루션

[1] Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.

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

[SmythPlotkin1982-3] Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). Proceedings, 18th IEEE Symposium on Foundations of Computer Science. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062.

[CousotCousot1979-4] Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF). Pacific Journal of Mathematics. 82 (1): 43–57. doi:10.2140/pjm.1979.82.43.

[5] Malkis, Alexander (2015). "Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial" (PDF). Reachability Problems. Lecture Notes in Computer Science. 9328: 114–127. doi:10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID 17640585. Archived from the original (PDF) on 2022-08-10.

[6] Yde Venema (2008) Wayback Machine에서 2012년 3월 21일 보관된 Modal μ-calculus에 대한 강의

[7] Yde Venema (2008) Wayback Machine에서 2012년 3월 21일 보관된 Modal μ-calculus에 대한 강의

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

[9] G. B. Halsted (1906) 합성 투영 기하학 27페이지

[10] Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture". Physical Review B. 4 (9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi:10.1103/PhysRevB.4.3174.

[11] Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior". Physical Review B. 4 (9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi:10.1103/PhysRevB.4.3184.

[12] "P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Search