칸토로비치 정리

칸토로비치 정리, 즉 뉴턴-칸토로비치 정리는 뉴턴의 방법의 반 국부적 수렴에 관한 수학적인 진술이다.1948년 레오니드 칸토로비치에 의해 처음 진술되었다.^[1][2]고정점이라기보다는 0의 존재와 고유성을 기술하고 있지만 바나흐 고정점 정리의 형태와 유사하다.^[3]

뉴턴의 방법은 특정 ${\displaystyle \mathrm{조건}}$에서 $방정식{\displaystyle }$ f${\displaystyle (}$ x${\displaystyle }$)${\displaystyle }$= $(\displaystyle f(x)=0$}의$$$$ 솔루션 $x{\displaystyle }$ ${\displaystyle$ x$} 또는$ $방정식{\displaystyle }$ F${\displaystyle (x)}$= $(\displaystyle F(x)=0}$의 벡터 솔루션으로 수렴되는 일련의 점을 구성한다$.$ 칸토로비치 정리는 이 초기 지점에 조건을 제시한다.순서를 정하다만약 그러한 조건들이 충족된다면, 해결책은 초기 지점 가까이에 존재하고, 순서는 그 지점으로 수렴된다.^[1][2]

가정

Let ${\displaystyle X\subset \mathbb {R} ^{n}}$ be an open subset and ${\displaystyle F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ a differentiable function with a Jacobian ${\displaystyle F^{\prime }(\mathbf {x} )}$ that is locally Lipschitz continuous (for instance$F{\displaystyle }$ ${\displaystyle F}$이(가) 두 배 다른 경우.즉, 열려 있는 하위 집합 $U{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle X}$ ${\displaystyle U\subset X}$의 경우, 모든 $x{\displaystyle \mathbf{}}$ , y${\displaystyle y}$U ${\displaystyle \mathbf$ {x$} ,\mathbf$ {$y} \$in $U}$과 같은 L > ${\displaystyle$L$>0}$ 상수가 있다고 가정한다.

${\displaystyle \ F'(\mathbf {x} )-F'(\mathbf {y})\\leq L\;\\mathbf {x} -\mathbf {y} \ \}$

holds. 왼쪽의 표준은 오른쪽의 벡터 표준과 호환되는 일부 연산자 표준이다.이 불평등은 벡터 노먼만을 사용하기 위해 다시 쓰일 수 있다.그런 다음 벡터 $v{\displaystyle \mathbf{}}$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\$에 대해 불평등

${\displaystyle \F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y})\\leq L\;\mathbf {x}\mathbf {y}\,\mathbf {v} \}}$

버텨야 한다

Now choose any initial point ${\displaystyle \mathbf {x} _{0}\in X}$. Assume that ${\displaystyle F'(\mathbf {x} _{0})}$ is invertible and construct the Newton step ${\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _$${0}).}$

The next assumption is that not only the next point ${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}}$ but the entire ball ${\displaystyle B(\mathbf {x} _{1},\ \mathbf {h} _{0}\ )}$ is contained inside the set ${\displaystyle X}$. Let ${\displaystyle M\le L}$$이$ 공을 놓고 야코비안의 립스키츠 상수가 되어라$$$.$

$마지막$ 준비로, 가능한 한, 시퀀스$($ ${\displaystyle k_{}}$ )$$k {\$displaystyle$ (\$mathbf {$x}$$$_$${k$$}}},$$$(${\displaystyle {}_{}{}_{}}$)$$k {$k$$$($α$ ${\displaystyle k_{}{}_{}}$)$k$에 따라$$ 반복적으로 생성한다$.$

${\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})\\[0.4em]\alpha _{k}&=M\,\ F'(\mathbf {x} _{k})^{-1}\ \,\ \mathbf {h} _{k}\ \\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{aignedat}}}$

성명서

이제$$ $\alpha {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \frac{1}{}}$ ${\displaystyle 2\frac{\mathrm{}}{}}$ ${\$}:{2$}}:$

1. a solution ${\displaystyle \mathbf {x} ^{*}}$ of ${\displaystyle F(\mathbf {x} ^{*})=0}$ exists inside the closed ball ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\ \mathbf {h} _{0}\ )}$ and
2. $x{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$에서 시작하는 뉴턴 반복은 최소 선형 수렴 순서로 x${\displaystyle {}^{}}x$ ${\$에 수렴한다$$.

좀 더 정밀하지만 증명하기가 조금 더 어려운 진술은 2차 다항식의 뿌리$$ $t{\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ $t$ t t ${\displaystyle {\ast }^{}}$ { { ${\displaystyle {\{}^{}}$ { { { { { {$${ { { { { $\st }\leq$ t$^{*}}}}}$를 사용한다.

${\displaystyle p(t)=\left({\tfrac {1}{2}}L\ F'(\mathbf {x} _{0})^{-1}\ ^{-1}\right)t^{2}-t+\ \mathbf {h} _{0}\ }$,

${\displaystyle t^{\ast /**}={\frac {2\\\mathbf {h} _{0}\{1\pm}{1\sqrt{1-2\pm_{0}}}}}}}}}}}}}:$

그리고 그 비율

${\displaystyle \theta ={\frac {t^{*}{t^{**}}={\frac {1-{\sqrt{1-2\propert_{0}}}{1+{\sqrt{1-2\propert_{0}}}}}}}}}.}$

그러면

1. a solution ${\displaystyle \mathbf {x} ^{*}}$ exists inside the closed ball ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \ \mathbf {h} _{0}\ )\subset {\bar {B}}(\mathbf {x} _{0},t^{*})}$
2. 더 큰 볼 $B{\displaystyle ({\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\displaystyle {\ast }^{}}$) ${\displaystyle B(\mathbf {x} _{0},t^{**\ast }}}}})$ 내부에서는 독특하다.
3. 그리고 F{F\displaystyle}의 해결의 융합은 2차 다항식 p(t){\displaystyle p(t)}의 작은 뿌리 t을 향한 뉴턴 반복의 하나로 수렴시킴으로써({\displaystyle t^{\ast}},[4]만약 t0=0tk+1)tk− p(kt)p′(kt)지배하고 있다. {\d$isplaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac$ {$p(t_{k$}}}}}, 그러면 ${p$'(t_{k$\}\}\}\}\}\}\},$

   ${\displaystyle \mathbf {x} _{k+p}-\mathbf {x} _{k}\leq t_{k+p}-t_{k}.}$

4. 2차 수렴은 오차 추정에서^[5] 얻는다.

   ${\displaystyle \ \mathbf {x} _{n+1}-\mathbf {x} ^{*}\ \leq \theta ^{2^{n}}\ \mathbf {x} _{n+1}-\mathbf {x} _{n}\ \leq {\frac {\theta ^{2^{n}}}{2^{n}}}\ \mathbf {h} _{0}\ .}$

코롤라리

1986년 야마모토는 도링(1969년), 오스트로우스키(1971년, 1973년),^[6][7] 그라그-타피아(1974년), 포트라-팍(1980년),^[8] 미엘(1981년),^[9] 포트라(1984년)^[10] 등 뉴턴 수법의 오류평가가 칸토로비치 정리에서 도출될 수 있음을 증명했다.^[11]

일반화

칸토로비치 정리에는 q-아날로그가 있다.^[12][13]기타 일반화/변수는 Ortega & Rheinboldt(1970년)를 참조하십시오.^[14]

적용들

오이시와 타나베는 칸토로비치 정리가 적용되어 선형 프로그래밍의 신뢰성 있는 해결책을 얻을 수 있다고 주장했다.^[15]

참조

추가 읽기

• 존 H. 허버드와 바바라 버크 허버드:벡터 미적분, 선형대수 및 미분양식: 통일 접근법, 매트릭스 에디션, ISBN 978-0-9715766-3-6 (칸트를 포함한 3.1판 및 샘플 재료 사전)
• Yamamoto, Tetsuro (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.