ITP 방식

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "ITP 방법" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2021년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수치해석에서는 인터폴 절단 및 프로젝트의 줄임말인 ITP법이 이분법 중 최악의 경우 최적의^[2] 성능을 유지하면서 제분법의^[1] 비선형 정합성을 달성하는 최초의 뿌리찾기 알고리즘이다.^[3]또한 어떤 연속적인 분포하에서도 이분법보다 엄격하게 평균성능이 보장된 첫 번째 방법이기도 하다.^[3]실제로 그것은 잘 동작된 기능에 대해 초선형적으로 수렴할 뿐만 아니라 보간이 실패하는 잘못된 동작의 기능에서도 빠른 성능을 보장하기 때문에 전통적인 보간 및 하이브리드 기반 전략(브렌트 방법, 일리노이주 Ridders, Brent's Method)^[3]보다 더 좋은 성능을 발휘한다.

ITP 방식은 뿌리의 위치 상·하한을 추적하는 표준 브래킷링 전략과 동일한 구조를 따르지만, 최악의 경우 성능이 상한을 유지하는 지역도 추적한다.브래킷링 전략으로서, 각 반복에서 ITP는 한 점에 기능 값을 조회하고 기능 값이 동일한 부호를 공유하는 두 지점 사이의 간격 부분을 삭제한다.쿼리된 지점은 세 단계로 계산된다. 즉, 레지울라 팔시 추정치를 찾아 인터폴한 다음, 추정치를 동요/실행한 다음(레굴라 팔시의 Regula 팔시 § 개선사항과 유사함) 양분 중간 지점의 인접한 간격에 퍼진 추정치를 투영한다.최소 최대 최적성을 보장하기 위해 각 반복에서 이분법 지점 주위의 이웃을 계산한다(의 Theorem 2.1 of )The method depends on three hyper-parameters ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ and ${\displaystyle n_{0}\in [0,\infty )}$ where ${\displaystyle \phi }$ is the golden ratio ${\displa$$ystyle {\tfrac{1}{2}}(1+{\sqrt{5$ 처음 두 개는 잘림 크기를 제어하고 세 번째는 투영 단계의 간격 크기를 제어하는 느슨한 변수다.^[a]

루트 찾기 문제

Given a continuous function ${\displaystyle f}$ defined from ${\displaystyle [a,b]}$ to ${\displaystyle \mathbb {R} }$ such that ${\displaystyle f(a)f(b)\leq 0}$, where at the cost of one query one can access the values of ${\displaystyle f(x)}$ on any given ${\displ$$aystyle x}$. 그리고 사전 지정된 목표 정밀도 > 0 ${\displaystyle \epsilon >0}$을를) 주어진 루트 탐색 알고리즘은 가능한 최소한의 질의로 다음과 같은 문제를 해결하도록 설계되어 있다.

문제 정의:${\displaystyle x\hat{}}$ ${\displaystyle \{\backslash }$$displaystyle$ ${\$$displaystyle {\displaystyle {\x}-x$^{*} \leq $\epsilon }}$을$($를) 찾으십시오$.$ 여기서 $x{\displaystyle {}^{}}$ ${\displaystyle {^}^{}}$ ${\displaystyle {\{\backslash }^{}}$$displaystyle$ $x$$^{*}}$는 $(x^{*}=0$

이 문제는 수치 분석, 컴퓨터 과학과 공학에서 매우 흔하며, 뿌리 찾기 알고리즘이 그것을 해결하기 위한 표준 접근법이다.흔히 뿌리 찾기 절차는 더 큰 맥락 안에서 더 복잡한 상위 알고리즘에 의해 호출되며, 이러한 이유로 인해 더 큰 맥락을 고려할 때 비효율적인 접근방식이 높은 계산 비용으로 나타날 수 있기 때문에 매우 중요하다.This is what the ITP method attempts to do by simultaneously exploiting interpolation guarantees as well as minmax optimal guarantees of the bisection method that terminates in at most ${\displaystyle n_{1/2}\equiv \lceil (b_{0}-a_{0})/2\epsilon \rceil }$ iterations when initiated on an interval${\displaystyle }$[ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle [a_{0},b_{0}]}$.

방법

Given ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$, ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ and ${\displaystyle n_{0$$}\in [0,\infty )}$ where ${\displaystyle \phi }$ is the golden ratio ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$, in each iteration ${\displaystyle j=0,1,2\dots }$ the ITP method calculates the point ${\displaystyle x_{\text{$$ITP}}:$3단계$$:

1. [인터폴레이션 단계] bisection 및 regula falsi 지점 계산: x ${\displaystyle {1\mathrm{}}_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}\frac{}{}a\frac{}{}}$ + ${\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{2}{}}$ ${\$}{2}$}}$ 및$$${\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}b\frac{}{}}$ ${\displaystyle \frac{f}{}}$( a${\displaystyle \frac{}{}}$)${\displaystyle \frac{}{}}$- ${\displaystyle \frac{f}{}}$(${\displaystyle \frac{}{}}$)${\displaystyle \frac{}{}}$- ${\displaystyle \frac{f}{}}$ (${\displaystyle \frac{}{}}$) - f${\displaystyle \frac{}{}}$( )${\$ ;
2. [Truncation Step] Perturb the estimator towards the center: ${\displaystyle x_{t}\equiv x_{f}+\sigma \delta }$ where ${\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})}$ and ${\di$$splaystyle \equiv \min\{\kappa _{1$} $b-a ^{\cappa _{2}}, x_{1/2}-x_{f} \}}}}}$ ;
3. [Projection Step] 추정기를 minmax 간격으로 투영: $x{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}{1\mathrm{}}_{}}$1 / ${\displaystyle {2\mathrm{}}_{}}$ -${\displaystyle {}_{}{}_{}}$ ${\displaystyle k_{}}$ { k ${\$$ITP}}\equiv x_{1/2}-\sigma \rho _{k}}$ where ${\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}}, x_{t}-x_{1/2} \right\}}$.

f($x{\displaystyle {\text{ITP}}_{}}$ )${\displaystyle f(x_{\text$} 함수$$값이 점에 있어서$$ $ITP}}}}$을(를) 쿼리한 다음, 각 끝에서 반대 기호의 함수 값으로 하위간격을 유지하여 루트를 괄호화하도록 간격을 줄인다.

알고리즘

(pseudocode로 쓰여진) 있을 경우 y의 초기 값{\displaystyle y_{}으로 가정한다 다음 알고리즘}와 yb{\displaystyle y_{b}}과 y<>를 만족시키다;;0<, y_{b}}}와 yb≡ f(b){\dis 0<> 베b{\displaystyle y_{}&lt이 y ≡ f(를){\displaystyle y_{}\equiv f(를)이 주어진다.playstyle y_${b}\equiv f($$b$$)\};$ 그리고 ${\displaystyle 최대\stackrel{}{}}$$$ ${\displaystyle {n\mathrm{}}_{}}$1 / 2${\displaystyle {}_{}}$+ ${\displaystyle 0_{}}$에서 x ${\displaystyle \stackrel{}{^}}$- ${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\displaystyle \le {}^{}}$ ϵ ${\displaystyle {\x}-x^{*} \leq \epsilon$$$$}}$을(를$)$ 만족하는$$ $추정치{\displaystyle \stackrel{}{}}$ x${\displaystyle \stackrel{}{}}$^$${\$displaystystytyle$ {\{\$n_{\{\n}$을 반환한다$.$

Input: ${\displaystyle a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f}$ Preprocessing: ${\displaystyle n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil }$, ${\displaystyle n_{\max }=n_{1/2}+n_{0$$\}\},$ 및 j${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle j=0};$while (- a > 2 ${\displaystyle b-a>2\epsilon })$계산 매개 변수: ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle \frac{\mathrm{}}{}}$ /${\displaystyle {2\mathrm{}}_{}}$=${\displaystyle \frac{}{}}$+ ${\displaystyle b\frac{}{}}$ ${\displaystyle \frac{2}{}}$ ${\$2}{2}{$2$}{2}$}}}$, ${\displaystyle r=\epsilon 2^{n_{\max }-j}-(b-a)/2}$, ${\displaystyle \delta =\kappa _{1}(b-a)^{\kappa _{2}}}$;         Interpolation: ${\displaystyle x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y$$_{a}}}}$;         Truncation: ${\displaystyle \sigma ={\text{sign}}(x_{1/2}-x_{f})}$;             If ${\displaystyle \delta \leq  x_{1/2}-x_{f} }$ then ${\displaystyle x_{t}=x_{f}+\sigma \delta }$,             Else ${\displaystyle x_t=x_{}}$${\displaystyle 1_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$ ${\$; 투영:${\displaystyle x{}_{}}$ ${\displaystyle {}_{}}$ -${\displaystyle {}_{}{1\mathrm{}}_{}}$/ ${\displaystyle 2{}_{}}$≤ r ${\displaystyle x_{t}-x_{1/2} \leq r}$일 경우$$ $x{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ = x t ${\$text}$ITP}}=x_{t$ 기타 $x{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$= ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$ -${\displaystyle {}_{}\sigma }$ ${\displaystyle r}$ ${\displaystyle x_{\text}$$ITP}}=x_{1/2}-\sigma r$ 업데이트 간격: $y{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$= ${\displaystyle f}$ ${\displaystyle ({}_{}}$ ${\displaystyle {\text{ITP}}_{}}$) ${\displaystyle y_{\text{}$$ITP}=$$f(x_{\text{$$ITP$   > 0 ${\displaystyle y_{\text{$$ITP}>0$$}$ 이후 $b{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle I_{}}$ ${\displaystyle T_{}}$ ${\displaystyle P_{}}$ ${\$$ITP}$ 및$$ $y{\displaystyle {}_{}}$ ${\displaystyle b_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$ ${\$$ITP$ Escif  < 0 ${\displaystyle y_{\text{$$ITP$$}}<$$0}$ 이후 $a{\displaystyle }$= x ${\displaystyle {\text{ITP}}_{}}$ ${\${$ITP}}$ 및$$ ${\displaystyle y_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$ ${\$$ITP$ 기타 $a{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$ ${\$$ITP}}$ 및$$ $b{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$ ${\$$ITP$ j${\displaystyle }$= ${\displaystyle \mathrm{j}}$+ 1 ${\displaystyle j=j+1$ $출력{\displaystyle \stackrel{}{}}$: x ${\displaystyle \stackrel{}{^}}$=${\displaystyle \frac{}{}}$+ ${\displaystyle \frac{\mathrm{}}{}}$ 2 ${\$}$}}}$

예:다항식의 루트 찾기

Suppose that the ITP method is used to find a root of the polynomial ${\displaystyle f(x)=x^{3}-x-2\,.}$ Using ${\displaystyle \epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2}$ and ${\displaystyle n_{0}=1}$ we find that:

반복	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.43333333333333	-0.488629629629630
2	1.43333333333333	2	1.52713145056966	0.0343383329048983
3	1.43333333333333	1.52713145056966	1.52009281150978	-0.00764147709265051
4	1.52009281150978	1.52713145056966	1.52137899116052	-4.25363464540141e-06
5	1.52137899116052	1.52713145056966	1.52138301273268	1.96497878177659e-05
6	1.52137899116052	1.52138301273268	∘정지기준 충족

이 예는 Bisection 방법 § 사례:다항식의 뿌리 찾기와 비교할 수 있다.ITP 방법은 최소값 보증에 대한 비용 없이 루트의 더 정확한 추정치를 얻기 위해 이분법보다 반복 횟수의 절반 미만이 필요했다.다른 방법들도 ITP 방법에 의해 주어지는 minmax 보증 없이 유사한 융합 속도(Ridders, Brent 등)를 얻을 수 있다.

분석

ITP 방법의 주요 $장점$은 n${\displaystyle {}_{}0}$ = 0 ${\displaystyle n_{0}=0}$일 때 이분법보다 더 많은 반복을 요구하지 않는다는 것이다$.$ 따라서 보간법이 실패하더라도 평균 성능은 이분법보다 더 좋을 것으로 보장된다.나아가 보간이 실패하지 않으면(원활한 기능), 보간 기반 방법으로 높은 순위의 수렴을 누릴 수 있는 것이 보장된다.

최악의 경우 성능

ITP 방법은 n ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 슬랙으로$$ 추정기를 Minmax 간격에 투영하기 때문에, 최대 $n{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$/${\displaystyle {}_{}{2\mathrm{}}_{}}$ + ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 반복이$$ 필요할 것이다(의 Theorem 2.1).$n{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을(를) $n{\displaystyle {}_{}}$ 0${\displaystyle {}_{}}$= ${\displaystyle 0}$ ${\displaystyle n_{0}=0}$으로 선택한$$ 경우 이분법처럼 최소값 최적이다$.$

평균실적

$n{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$+ ${\displaystyle {n\mathrm{}}_{}}$ 0 ${\$을(를) 반복하지 않기 때문에, 평균 반복 횟수는 ${\displaystyle \mathrm{n}}$ ${\displaystyle {0\mathrm{}}_{}}$= 0 ${\displaystyle n_{0}=0}($의 계산 2.2)일 때 고려되는 분포에 대해 항상 이분법보다 작을 것이다.

점근 성능

If the function ${\displaystyle f(x)}$ is twice differentiable and the root ${\displaystyle x^{*}}$ is simple, then the intervals produced by the ITP method converges to 0 with an order of convergence of ${\displaystyle {\sqrt {\kappa _{2}}}}$ if ${\displaystyle n_{0}\neq 0}$ or if $$${\displaystyle n_{0}=0}$ and ${\displaystyle (b-a)/\epsilon }$ is not a power of 2 with the term ${\displaystyle {\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}}$ not too close to zero (Theorem 2.3 of ^[3]).

참고 항목

• 이등분법
• 리더스법
• 레굴라 팔시
• 브렌트의 방법

메모들

참조

외부 링크

• 쿠도스에 의한 개선된 이분법