근사 이론

수학에서, 근사 이론은 함수가 더 단순한 함수로 가장 잘 근사될 수 있는 방법과 그에 의해 도입된 오차를 양적으로 특징짓는 것과 관련이 있다.best와 simple의 의미는 어플리케이션에 따라 달라집니다.

밀접하게 관련된 주제는 일반화 푸리에 급수에 의한 함수 근사, 즉 직교 다항식에 기초한 일련의 항의 합계에 기초한 근사치이다.

특히 관심 있는 문제 중 하나는 컴퓨터나 계산기에서 수행할 수 있는 연산(예: 덧셈과 곱셈)을 사용하여 컴퓨터 수학 라이브러리의 함수를 근사하여 결과가 가능한 한 실제 함수에 근접하도록 하는 것이다.이는 일반적으로 다항식 또는 유리(다항식의 비율) 근사치를 사용하여 수행됩니다.

목적은 근사치를 가능한 한 실제 함수에 가깝게 하는 것입니다.일반적으로 기본 컴퓨터의 부동소수점 산술에 가까운 정확도로 합니다.이는 다항식을 사용하거나 다항식이 함수를 근사해야 하는 영역을 좁힘으로써 달성된다.영역을 좁히는 것은 종종 대략적인 함수에 대한 다양한 덧셈 또는 스케일링 공식을 사용하여 수행할 수 있습니다.현대의 수학 라이브러리는 종종 도메인을 많은 작은 세그먼트로 줄이고 각 세그먼트에 대해 낮은 수준의 다항식을 사용합니다.

최적 다항식과 로그(x)(빨간색), 체비셰프 근사치와 로그(x)(파란색) 사이의 오차 [2, 4]입니다.세로눈금은 10입니다−5.최적 다항식의 최대 오차는 6.07 × 10이다−5.

최적 다항식과 exp(x)(빨간색), 체비셰프 근사치 및 exp(x)(파란색) 사이의 오차 [-1, 1]입니다.세로눈금은 10입니다−4.최적 다항식의 최대 오차는 5.47 × 10이다−4.

최적 다항식

일단 도메인(일반적으로 구간)과 다항식의 정도를 선택하면 최악의 오류를 최소화하기 위해 다항식 자체가 선택됩니다.${\displaystyle 즉}$, P${\displaystyle (x)}$ - ${\displaystyle f}($${\displaystyle x)}$의 최대값을 최소화하는 것이 목표입니다.여기서 P$($x$)$는 근사 다항식, f$($x$)$는 실제 함수, x는 선택한 간격에 따라 달라집니다.$정상적$으로 동작하는 함수의 경우 $+(\backslash {\displaystyle }$$display style$ +\$)$와 -$(\displaystyle$ -\varepsilon$$$)$ 사이에서 총 N+2회 오차를 발생시키는 N차 다항식이 존재합니다$.$곡선에서 N+1 점을 보간할 수 있는 N차 다항식입니다.이러한 다항식은 항상 최적입니다.이러한 다항식이 존재하지 않는 함수는 f(x)로 만들 수 있지만 실제로는 거의 발생하지 않습니다.

예를 들어, 오른쪽에 표시된 그래프는 N = 4에 대한 근사 로그(x) 및 exp(x)의 오류를 보여 줍니다.최적 다항식의 경우 빨간색 곡선은 ${\displaystyle \mathrm{수평}}$입니다. 즉, $+(\displaystyle +\varepsilon)$와${\displaystyle }$-$(\displaystyle -\varepsilon)$ 사이에서${\displaystyle }$정확히 진동합니다.각각의 경우 극단값은 N+2, 즉 6이라는 점에 유의하십시오.극단 중 2개는 구간의 끝점, 그래프의 왼쪽과 오른쪽 가장자리에 있습니다.

일반적으로 이것이 참임을 증명하기 위해, P가 설명된 성질을 가진 N차 다항식이라고 가정하자. 즉, P는 N + 2 극단 a, 교대 부호와 같은 크기를 갖는 오차 함수를 발생시킨다고 가정하자.오른쪽의 빨간색 그래프는 이 오류 함수가 N = 4일 때 어떻게 보일 수 있는지를 보여 줍니다.Q(x)(오른쪽 파란색으로 표시된 오류 함수)가 P보다 f에 더 나은 근사치인 또 다른 N도 다항식이라고 가정합니다.특히 Q는 각 값 x에_i 대해 P보다 f에 가깝기 때문에 P-f의 극단값이 발생합니다.

$\displaystyle Q(x_{i})-f(x_{i})< P(x_{i})-f(x_{i}.}$

x에서_i 최대 P-f가 발생하면

$\displaystyle Q(x_{i})-f(x_{i})-leq Q(x_{i})< P(x_{i})-f(x_{i})=P(x_{i}-f(x_{i}),}$

그리고 x에서 최소_i P-f가 발생하면

$\displaystyle f(x_{i})-Q(x_{i})-f(x_{i})< P(x_{i})-f(x_{i})=f(x_{i})-P(x_{i}).}$

따라서 그래프에서 볼 수 있듯이 [P(x) - f(x)] - [Q(x) - f(x)]는 x의_i N + 2 값에 대해 교대로 부호화되어야 합니다. 그러나 [P(x) - f(x)] - [Q(x) - f(x)]는 N의 다항식인 P(x) - Q(x)로 감소합니다.이 함수는 최소 N+1번 부호를 변경하므로 중간값 정리에 따라 N+1 0을 가지며, 이는 N차 다항식의 경우 불가능합니다.

체비셰프 근사

체비셰프 다항식의 관점에서 주어진 함수를 확장한 다음 원하는 정도로 확장을 차단하면 최적 다항식에 매우 가까운 다항식을 얻을 수 있다.이는 일반적인 삼각 함수 대신 체비셰프 다항식을 사용하는 함수의 푸리에 분석과 유사합니다.

함수에 대한 체비셰프 확장의 계수를 계산하는 경우:

${\displaystyle f(x)\sim \sum _{i=0}^{\infty}c_{i}T_{i}(x)}$

그런 ${\displaystyle {다음}_{}}$ T$$N({$displaystyle T_{$N$$}) 항 $뒤$에 시리즈를 끊으면 N차 다항식 근사 f(x)를 얻을 수 있습니다.

이 다항식이 거의 최적인 이유는 빠르게 수렴되는 멱급수를 갖는 함수의 경우, 어떤 기간 후에 급수가 끊어지면 컷오프에서 발생하는 총 오차가 컷오프 후의 첫 번째 기간에 가깝기 때문입니다.즉, 컷오프 후의 첫 번째 항이 이후의 모든 항을 지배한다.팽창이 버킹 다항식의 관점에서 이루어지는 경우에도 마찬가지입니다.$(\$ $후$에 체비셰프 확장이 끊긴 경우 ${\displaystyle {오류}_{}}$는 T${\displaystyle {\mathrm{N}}_{}}$+ 1(\$displaystyle T_{N+$1$\})$의 배수 근처에 있습니다.체비셰프 다항식은 수평이라는 특성이 있습니다. 즉, [-1, 1] 구간에서 +1과 -1 사이에서 진동합니다.${\displaystyle T_{}}$N + $({$ T_${N+1})$은 N+2 레벨 극단입니다.${\displaystyle {즉}_{}}$, f(x)와 T N$({$으로 확장되는 체비셰프 사이의 오차는 N+2 극단값의 레벨 함수에 가깝기 때문에 최적의 N차 다항식에 가깝습니다.

위의 그래프에서 파란색 오류 함수가 빨간색 함수보다 좋을 때도 있고 더 나쁘기도 합니다. 즉, 최적 다항식이 아니라는 의미입니다.이 차이는 로그 함수보다 매우 빠르게 수렴되는 멱급수를 갖는 exp 함수의 경우 심각하지 않습니다.

체비셰프 근사치는 수치 적분 기법인 클렌쇼-커티스 직교법의 기초이다.

레메즈 알고리즘

Remez 알고리즘(Remes라고도 함)은 주어진 간격에 걸쳐 주어진 함수 f(x)에 근사한 최적의 다항식 P(x)를 생성하는 데 사용됩니다.N+2 레벨 극단값의 오차 함수를 갖는 다항식으로 수렴하는 반복 알고리즘입니다.위의 정리에 따르면, 그 다항식이 최적이다.

Remez의 알고리즘은 주어진 N+2 검정 지점에서 수준 및 교대 오차 값으로 이어지는 N차 다항식을 구성할 수 있다는 사실을 사용합니다.

N+2 테스트 ${\displaystyle {포인트x\mathrm{}}_{}}$ 1$$(\$displaystyle x_$${$$1$$\}),$ $x{\displaystyle {}_{}}$$$${\displaystyle 2_{}}$ (\$displaystyle x_{N+2$}),$$ ...$$x ${\displaystyle {N\mathrm{}}_{}}$${\displaystyle {}_{}}$+$$ $(\$${$1} 및 ${\displaystyle {x\mathrm{N}}_{}}$ +$$2 (\$displaystyle x_{N+2}})$가 주어진 경우, 다음 방정식을 풀어야 합니다.

$({displaystyle {begin{1}P(x_{1})-f(x_{2})-f(x_{3})-f(x_{3})=+\varepsilon \\\p(x_{2})-f(x_{3})-f(x_{3})-\varepsilon \\\\\p(x)\dots)\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p\p=\pm \varepsilon .\end{aligned}}$

오른쪽이 번갈아 표시된다.

그것은,

$디스플레이 스타일P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\pares +P_{N}-f(x_{1})^{N}&=+\varepsilon \\P_{0}+P_{1}x_{2}x_{2}+P_{3}}x_{2}^{3}+\param +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \&\\vdots \end{aligned}}$

${\displaystyle {x\mathrm{}}_{}}$ 1$({$ ..., ${\displaystyle x_{}}$N +$$({$displaystyle x_{$$N+2})$가 지정되었기 $때문$에 그 파워는 모두 알 수 있습니다${\displaystyle .}f{\displaystyle }$ ( ${\displaystyle {x\mathrm{}}_{}}$ 1)$${ $displaystyle$$$f $(x_{1}},$ ...,${\displaystyle }f{\displaystyle }$ (${\displaystyle x_{}}$N + ${\displaystyle 2_{}}$도 알 수 있습니다.즉, 위의 방정식은 N+2 $변수{\displaystyle {}_{}}$ ${\displaystyle {P\mathrm{}}_{}}$0({$displaystyle P_{0$ ${\displaystyle {P\mathrm{}}_{}}$1({$displaystyle P_{1$$},$ ...), ${\displaystyle P_{}}$ N$({$ 및$$P $N{\displaystyle }$({$displaystyle P_$${$N$\})$의 N+2 선형 방정식일 뿐입니다.테스트 ${\displaystyle {포인트}_{}}$는 1$({$ X$\},$ )입니다.$le$ x_${N+2$ 이 시스템을 풀면 다항식 P와 $숫자{\displaystyle }${\(\$style \varepsilon$을 얻을 수 있습니다.

아래 그래프는 [-1, 1]에 ${\displaystyle {대해}^{}}$4차 다항식 $근사$e x ${\displaystyle$ e^{x$}$를 생성하는 예를 보여줍니다.테스트 포인트는 -1, -0.7, -0.1, +0.4, +0.9 및 1로 설정되었습니다.이러한 값은 녹색으로 표시됩니다.${\$ { $displaystyle$\ $varepsilon }$의 값은 4.43 × 10입니다⁻⁴.

에러 그래프는 엔드 포인트를 포함한 6개의 테스트 포인트에서 ±$$†(\$displaystyle\pm\varepsilon)$의${\displaystyle }$값을 취하지만 이러한 포인트는 극단값이 아닙니다.만약 네 개의 내부 테스트 지점이 극단이었다면(즉, 함수의 P(x)f(x)가 최대값 또는 최소값을 가졌다), 다항식은 최적일 것이다.

레메즈 알고리즘의 두 번째 단계는 오류 함수가 실제 국소 최대값 또는 최소값을 갖는 대략적인 위치로 테스트 지점을 이동하는 것으로 구성됩니다.예를 들어, 그래프를 보면 -0.1의 점이 약 -0.28이어야 한다는 것을 알 수 있습니다.알고리즘에서 이것을 하는 방법은 뉴턴의 방법을 한 바퀴 사용하는 것입니다.P(x) - f(x)의 첫 번째와 두 번째 도함수를 알고 있기 때문에, 도함수가 0이 되도록 시험점을 대략 얼마나 이동해야 하는지를 계산할 수 있다.

다항식의 도함수를 계산하는 것은 간단하다.f(x)의 1차 도함수와 2차 도함수를 계산할 수 있어야 한다.Remez 알고리즘에서는 f${\displaystyle }$(${\displaystyle x}$ $){$ f$(x$ ${\displaystyle f{}^{}(}$ (${\displaystyle }$x $){$ f$'(x$ 및 $f{\displaystyle {}^{}}$ ${\displaystyle (}$ (${\displaystyle x}$){$displaystyle$ f$'(x)}$를 매우 정밀하게 $계산$할 수 있어야 합니다.전체 알고리즘은 결과의 원하는 정밀도보다 높은 정밀도로 수행되어야 한다.

테스트 포인트를 이동한 후 선형 방정식 부분을 반복하여 새로운 다항식을 얻고, 다시 뉴턴법을 사용하여 테스트 포인트를 이동시킨다.이 시퀀스는 결과가 원하는 정확도로 수렴될 때까지 계속됩니다.알고리즘은 매우 빠르게 수렴됩니다.컨버전스는 정상적으로 동작하는 기능에서 2차적인 것입니다.테스트 포인트가 올바른 결과로부터${\displaystyle {}^{}}$10 $-$ ${\displaystyle {15}^{}}$(\$displaystyle$ 10$^{$ - $15})$ ${\displaystyle {\mathrm{이내}}^{}}$에 있는 경우, 다음 라운드 후 테스트 포인트는 올바른 결과로부터 약 10 ${\displaystyle {-}^{}}$ $(\$ 10$^{$ - $30})$ ${\displaystyle {\mathrm{이내}}^{}}$에 있습니다.

Remez의 알고리즘은 일반적으로 체비셰프 $다항식{\displaystyle {}_{}}$ ${\displaystyle T_{}}$ N${\displaystyle {}_{}}$+ $({$ T_${N+1})$의 극한을 초기 포인트로 선택하는 것으로 시작됩니다. 최종 오차 함수는 해당 다항식과 유사하기 때문입니다.

주요 저널

• 근사 이론 저널
• 건설적 근사
• 근사치에 관한 East 저널

「 」를 참조해 주세요.

• 추정 이론
• 푸리에 급수
• 함수 근사
• 직교 정규 기준
• 파데 근사
• 쇼더 베이스

레퍼런스

• N. I. Achiezer(Akhiezer), 근사 이론, 찰스 J. 옮김.하이만 프레데릭 웅가 출판사, 뉴욕 1956 x+307 페이지.
• A. F. Timan, 실수 변수의 함수 근사 이론, 1963 ISBN0-486-67830-X
• C. 헤이스팅스 주니어디지털 컴퓨터의 근사치.프린스턴 대학 출판부, 1955년
• J. F. 하트, E. W. 체니, C. L. 로슨, H. J. Mahly, C. K. 메스텐이, J. R. 라이스, H. C.Thacher Jr., C. Witzgall, 컴퓨터 근사치와일리, 1968년 리브회의: 67~23326
• L. 폭스와 I. B. 파커"수치 분석에서의 체비셰프 다항식"옥스퍼드 대학 출판사, 1968년.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 5.8. Chebyshev Approximation", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
• W. J. Cody Jr., W. Waite, 기초 기능을 위한 소프트웨어 매뉴얼.프렌티스홀, 1980년 ISBN 0-13-822064-6.
• E. Remes [Remez], "Surle calculate effectif des polynomes d'absacement de Tschebyschef.". 1934 C. R. Acad. 파리 시, 199, 337-340
• K.-G. Steffens, "근사 이론의 역사: 오일러에서 번스타인으로", Birkhauser, Boston 2006 ISBN 0-8176-4353-2.
• T. 에르델리, "다항식의 구별되는 실수 0의 수에 대한 블로흐-폴랴 정리 확장", 보르도 20 저널 (2008), 281–287.
• T. Erdelyi, "시프트 가우시안들의 선형 조합에 대한 레메즈 부등식", 수학. 검사님 캠브입니다 Phil. Soc. 146(2009), 523-530.
• L. N. Trefeten, "근사 이론 및 근사 실무", SIAM 2013.[1]

외부 링크

• 근사 이론의 역사(HAT)
• 근사 이론 조사(SAT)