본문 바로가기
영문 위키피디아 번역

(번역) Trapezoidal rule

by 다움위키 2024. 4. 14.
Original article: w:Trapezoidal rule

 

수학(mathematics), 특히 수치 해석학(numerical analysis)에서, 사다리꼴 규칙(trapezoidal rule)은 한정 적분(definite integral)을 근사화하는 기법이며, 역시 trapezoid rule 또는 trapezium rule으로 알려져 있습니다; 용어에 대한 자세한 정보에 대해 사다리꼴(Trapezoid)을 참조하십시오:

\(\quad\displaystyle \int_a^b f(x) \, dx.\)

사다리꼴 규칙은 함수 \(f(x)\)의 그래프 아래 영역을 사다리꼴(trapezoid)로 근사화하고 그것의 넓이를 계산함으로써 작동합니다. 그것은 다음임을 따릅니다:

\(\quad\displaystyle \int_{a}^{b} f(x) \, dx \approx (b-a) \cdot \tfrac{1}{2}(f(a)+f(b)).\)

사다리꼴 규칙은 왼쪽(left)과 오른쪽(right) 리만 합(Riemann sum)을 평균함으로써 얻어진 결과로 보일 수 있고, 때때로 이 방법으로 정의됩니다. 그 적분은 적분 구간을 분할하고, 각 부분구간에 사다리꼴 규칙을 적용하고, 그런-다음 결과를 합함으로써 훨씬 더 잘 근사화될 수 있습니다. 실제로, 이 "연쇄된" (또는 "합성") 사다리꼴 규칙은 보통 "사다리꼴 규칙을 갖는 적분"에 의해 의미되는 것입니다. \(\{x_k\}\)를 \(a=x_0 < x_1 < \cdots < x_{N-1} < x_N = b\)를 만족하는 \([a,b]\)의 분할로 놓고 \(\Delta x_k\)를 \(k\)-번째 부분구간의 길이 (즉, \(\Delta x_k = x_k - x_{k-1}\))으로 놓으면, 다음입니다:

\(\quad\displaystyle \int_a^b f(x) \, dx \approx \sum_{k=1}^N \frac{f(x_{k-1}) + f(x_k)}{2} \Delta x_k.\)

분할이 규칙적인 간격을 가질 때, 종종 그렇듯이, 즉, 모든 \(\Delta x_k\)가 같은 값 \(\Delta x\)을 가질 때, 그 공식은 \(\Delta x\)을 인수로 묶어 냄으로써 계산 효율성을 위해 단순화될 수 있습니다:

\(\quad\displaystyle \int_a^b f(x) \, dx \approx \frac{\Delta x}{2} \left(f(x_0) + 2f(x_1) + 2f(x_2) + 2f(x_3) + 2f(x_4) + \cdots + 2f(x_{N-1}) + f(x_N)\right).\)

근사는 분할의 분해-정도가 증가함에 따라 더 정확하게 됩니다 (즉, 더 큰 \(N\)에 대해, 모든 \(\Delta x_k\)가 감소합니다).

아래에서 논의되는 바와 같이, 사다리꼴 규칙을 사용하여 추정된 한정 적분 값의 정확도에 대한 오차 경계를 두는 것도 가능합니다.

History

2016년 논문은 사다리꼴 규칙이 황도(ecliptic)를 따라 목성(Jupiter)의 속도를 적분화하는 데 기원전 50년 이전에 바빌로니아(Babylon)에서 사용되었다고 언급합니다.

Numerical implementation

Non-uniform grid

격자 간격이 비-균등할 때, 우리는 다음 공식을 사용할 수 있습니다:

\(\quad\displaystyle  \int_{a}^{b} f(x)\, dx \approx \sum_{k=1}^N \frac{f(x_{k-1}) + f(x_k)}{2} \Delta x_k\)

Uniform grid

\(N\) 같게 간격된 패널로 이산화된 도메인에 대해, 상당한 단순화가 발생할 수 있습니다. 다음으로 놓으면

\(\quad\displaystyle \Delta x_k = \Delta x = \frac{b-a}{N}\)

적분에 대한 근사는 다음이 됩니다:

\(\quad \begin{align}
\int_{a}^{b} f(x)\, dx
&\approx \frac{\Delta x}{2} \sum_{k=1}^{N} \left( f(x_{k-1}) + f(x_{k}) \right) \\[6pt]
&= \frac{\Delta x}{2} ( f(x_0) + 2f(x_1) + 2f(x_2) + 2f(x_3) + \dotsb + 2f(x_{N-1}) + f(x_N) ) \\[6pt]
&= \Delta x \left( \sum_{k=1}^{N-1} f(x_k) + \frac{f(x_N) + f(x_0) }{2}  \right).
\end{align}\)

Error analysis

합성 사다리꼴 규칙의 오차는 적분 값과 수치적 결과 사이의 차이입니다:

\(\quad\displaystyle  \text{E} = \int_a^b f(x)\,dx - \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right]\)

다음을 만족하는 a와 b 사이의 숫자 ξ가 존재합니다:

\(\quad\displaystyle  \text{E} = -\frac{(b-a)^3}{12N^2} f''(\xi)\)

만약 피적분이 위로 오목(concave up)이면 (및 따라서 양의 이차 도함수를 가지면), 그 오차는 음수이고 사다리꼴 규칙은 실제 값을 과대평가함을 따릅니다. 이것은 역시 기하학적 그림에서 보일 수 있습니다: 사다리꼴은 곡선 아래의 모든 넓이를 포함하고 곡선 위로 확장합니다. 유사하게, 아래로-오목(concave-down) 함수는 넓이가 곡선 아래에서 설명되지 않지만, 어떤 것도 위에 계산되지 않기 때문에 과소평가를 산출합니다. 만약 근사되는 적분의 구간이 변곡점을 포함하면, 그 오차는 식별하기가 더 어렵습니다.

N → ∞에 대해 점근적 오차 추정은 다음에 의해 제공됩니다:

\(\quad\displaystyle  \text{E} = -\frac{(b-a)^2}{12N^2} \big[ f'(b)-f'(a) \big] + O(N^{-3}). \)

이 오차 추정의 추가적인 항은 오일러–맥클로린 합계 공식에 의해 제공됩니다.

몇 가지 기법이 오차를 분석하기 위해 사용될 수 있으며, 다음을 포함합니다:

  1. 푸리에 급수(Fourier series)
  2. 잔여 미적분(Residue calculus)
  3. 오일러–맥클로린 합계 공식(Euler–Maclaurin summation formula)
  4. 다항식 보간(Polynomial interpolation)[6]

사다리꼴 규칙의 수렴 속력은 함수의 매끄러움의 클래스의 정의로 반영하고 사용될 수 있다고 주장됩니다.

Proof

먼저 \(h=\frac{b-a}{N}\)와 \(a_k=a+(k-1)h\)임을 가정합니다. \( g_k(t) = \frac{1}{2}  t[f(a_k)+f(a_k+t)] - \int_{a_k}^{a_k+t} f(x) dx\)를 \( |g_k(h)| \)가 구간, \( [a_k, a_k+h] \)의 하나 위에 사다리꼴 규칙의 오차임을 만족하는 함수로 놓습니다. 그런-다음

\(\quad\displaystyle  {dg_k \over dt}={1 \over 2}[f(a_k)+f(a_k+t)]+{1\over2}t\cdot f'(a_k+t)-f(a_k+t),\)

및

\(\quad\displaystyle  {d^2g_k \over dt^2}={1\over 2}t\cdot f''(a_k+t).\)

이제 \( \left\vert f''(x) \right\vert \leq f''(\xi)\)임을 가정하며, 이것은 만약 \( f \)가 충분하게 매끄러운 것이면 유지됩니다. 그런-다음 다음임을 따릅니다:

\(\quad \left\vert f''(a_k+t) \right\vert \leq f''(\xi)\)

이것은 다음과 동등합니다:

\(\quad\displaystyle  -f''(\xi) \leq f''(a_k+t) \leq f''(\xi)\), or \( -\frac{f''(\xi)t}{2} \leq g_k''(t) \leq \frac{f''(\xi)t}{2}.\)

\( g_k'(0)=0\)와 \( g_k(0)=0\)이기 때문에,

\(\quad\displaystyle  \int_0^t g_k''(x)  dx = g_k'(t)\) and \( \int_0^t g_k'(x) dx = g_k(t).\)

이들 결과를 사용하여, 우리는 다음을 찾습니다:

\(\quad\displaystyle  -\frac{f''(\xi)t^2}{4} \leq g_k'(t) \leq \frac{f''(\xi)t^2}{4}\)

및

\(\quad\displaystyle  -\frac{f''(\xi)t^3}{12} \leq g_k(t) \leq \frac{f''(\xi)t^3}{12}\)

\( t=h \)이라고 놓으면 우리는 다음을 찾습니다:

\(\quad\displaystyle  -\frac{f''(\xi)h^3}{12} \leq g_k(h) \leq \frac{f''(\xi)h^3}{12}.\)

모든 지역 오차 항을 합하면 다음을 찾습니다:

\(\quad\displaystyle  \sum_{k=1}^{N} g_k(h) = \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right] - \int_a^b f(x)dx.\)

그러나 다음이 되도록

\(\quad\displaystyle  -\frac{f''(\xi)h^3N}{12} \leq \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right]-\int_a^bf(x)dx \leq \frac{f''(\xi)h^3N}{12}\)

우리는 역시 다음을 가집니다:

\(\quad\displaystyle  - \sum_{k=1}^N \frac{f''(\xi)h^3}{12} \leq \sum_{k=1}^N g_k(h) \leq  \sum_{k=1}^N \frac{f''(\xi)h^3}{12}\)

및

\(\quad\displaystyle  \sum_{k=1}^N \frac{f''(\xi)h^3}{12}=\frac{f''(\xi)h^3N}{12}\).

그러므로 전체 오차는 다음에 의해 경계집니다:

\(\quad\displaystyle  \text{error}=\int_a^bf(x)dx - \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right] = \frac{f''(\xi)h^3N}{12}=\frac{f''(\xi)(b-a)^3}{12N^2}.\)

Periodic and peak functions

사다리꼴 규칙은 주기적 함수에 대해 빠르게 수렴합니다. 이것은 오일러-맥클로린 합계 공식(Euler-Maclaurin summation formula)의 쉬운 결과로, 만약 \(f\)가 주기 \(T\)를 갖는 \(p\)번 연속적으로 미분가능이면, 다음이라고 말합니다:

\(\quad\displaystyle \sum_{k=0}^{N-1} f(kh)h =
    \int_{0}^{T} f(x)\,dx  +
    \sum_{k=1}^{\lfloor p/2\rfloor} \frac{B_{2k}}{(2k)!} (f^{(2k - 1)}(T) - f^{(2k - 1)}(0)) - (-1)^{p}h^{p}\int_{0}^{T}\tilde{B}_{p}(x/T)f^{(p)}(x) \, \mathrm{d}x
\)

여기서 \(h:=T/N\)와 \(\tilde{B}_{p}\)는 \(p\)-번째 베르누이 다항식의 주기적 확장입니다. 주기성으로 인해, 끝점에서 도함수는 취소되고 우리는 그 오차가 \(O(h^p)\)임을 알 수 있습니다.

비슷한 효과는 가우스(Gaussian), 지수적으로 수정된 가우스(Exponentially modified Gaussian), 및 무시될 수 있는 적분 극한에서 도함수를 갖는 다른 함수와 같은 돌출부-계열 함수에 대해 사용할 수 있습니다. 1% 정확도를 갖는 사다리꼴 규칙에 의한 가우스 함수의 전체 적분 평가는 단지 4점을 사용하여 수행될 수 있습니다. 심슨의 규칙(Simpson's rule)은 같은 정확도를 달성하기 위해 1.8배 더 많은 점을 요구합니다.

비록 오일러-맥클로린 합계 공식을 더 높은 차원으로 확장하기 위해 약간의 노력이 있었지만, 더 높은 차원에서 사다리꼴 규칙의 빠른 수렴의 가장 직접적인 증명은 문제를 푸리에 급수의 수렴 문제로 줄이는 것입니다. 이 추론 선은 만약 \(f\)가 \(p\) 연속 도함수를 갖는 \(n\)-차원 공간 위에 주기적이면, 수렴의 속력은 \(O(h^{p/d})\)임을 보여줍니다. 매우 큰 차원에 대해, 몬테-카를로 적분이 더 나은 선택일 가능성이 가장 높지만, 2차원과 3차원에 대해 같은-간격된 표본화가 효율적임을 보여줍니다. 이것은 역수 격자에서 원시 셀에 걸쳐 같은-간격된 표본화가 ''몽크홀스트-팩 적분''(''Monkhorst-Pack integration'')으로 알려진 계산적 고체 상태 물리학에서 활용됩니다.

"Rough" functions

\(C^2\)에 있지 않는 함수에 대해, 위에 제공된 오차 경계는 적용할 수 없습니다. 그래도 여전히, 그러한 대략적인 함수에 대한 오차 경계는 유도될 수 있으며, 전형적으로 위에서 주어진 \(O(N^{-2})\) 행동보다 함수 평가 숫자 \(N\)에서 더 느린 수렴을 보여줍니다. 흥미롭게도, 이 경우에서 사다리꼴 규칙은 종종 같은 숫자의 함수 평가에 대해 심슨의 규칙(Simpson's rule)보다 더 날카로운 경계를 가집니다.

Applicability and alternatives

사다리꼴 규칙은 뉴턴–코츠 공식(Newton–Cotes formulas)이라고 불리는 수치적 적분(numerical integration)에 대해 공식 중의 가족 중 하나로, 이것의 중간점 규칙(midpoint rule)은 사다리꼴 규칙과 유사합니다. 심슨의 규칙(Simpson's rule)은 같은 가족의 또 다른 구성원이고, 일반적으로 비록 모든 특정 경우에서 그렇지 않지만 두 번 연속적으로 미분가능인 함수에 대해 사다리꼴 규칙보다 더 빠른 수렴을 가집니다. 어쨌든, 더 거친 함수 (더 약한 매끄러움 조건을 갖는 함수)의 다양한 클래스에 대해, 사다리꼴 규칙은 일반적으로 심슨의 규칙보다 더 빠른 수렴을 가집니다.

게다가, 사다리꼴 규칙은 주기 함수(periodic function)가 다양한 방법으로 분석될 수 있는 해당 주기에 걸쳐 적분될 때 극단적으로 정확하게 되는 경향이 있습니다. 비슷한 효과가 돌출부 함수에 대해 유효합니다.

비-주기적 함수에 대해, 어쨌든 가우스 구적법(Gaussian quadrature)과 클렌쇼–커티스 구적법(Clenshaw–Curtis quadrature)과 같이 같지 않은 간격된 점을 갖는 방법은 일반적으로 훨씬 더 정확합니다; 클렌쇼–커티스 구적법은 사다리꼴 규칙이 정확하게 적용될 수 있는 점에서 주기적 적분의 관점에서 임의적분 적분을 표현하기 위한 변수의 변경으로 보일 수 있습니다.

References

External links

 

관련글

티스토리툴바