가우스 구적법

[[파일:Comparison Gaussquad trapezoidal.svg|섬네일|upright=1.5|alt=2점 가우스 구적법과 사다리꼴 구적법의 비교.|2점 가우스 구적법과 사다리꼴 구적법의 비교.
파란색 곡선은 구간 [−1, 1]에서의 정적분을 계산하려는 함수(피적분함수)를 보여준다. 사다리꼴 공식은 함수의 양 끝점과 일치하는 선형 함수로 함수를 근사하며 주황색 점선으로 표시된다. 근사는 명백히 좋지 않으므로 오차가 크다 (사다리꼴 공식은 3인 올바른 값에 대해 적분의 근사값으로 1=y(−1) + y(1) = −10을 제공한다). 더 정확한 결과를 얻으려면 구간을 많은 부분 구간으로 분할한 다음 합성 사다리꼴 공식을 사용해야 하므로 훨씬 더 많은 계산이 필요하다.
가우스 구적법은 대신 더 적합한 점을 선택하므로 선형 함수도 함수를 더 잘 근사한다(검은색 점선). 피적분 함수가 3차 다항식 2 − 3x + 3이므로, 2점 가우스 구적법은 심지어 정확한 결과를 반환한다.]] 수치해석학에서 카를 프리드리히 가우스의 이름을 딴 n점 **가우스 구적법**(Gaussian quadrature)은 1=i = 1, ..., n에 대해 노드 i 및 가중치 i를 적절히 선택하여 차수 2n − 1 이하의 다항식에 대해 정확한 결과를 얻도록 구성된 구적법이다.1815 직교 다항식을 사용한 현대적인 공식은 1826년 카를 구스타프 야코프 야코비에 의해 개발되었다.1826 이러한 규칙에 대한 가장 일반적인 적분 영역은 [−1, 1]로 간주되므로 규칙은 다음과 같이 표현된다. \int_{-1}^1 f(x)\,dx \approx \sum_{i=1}^n w_i f(x_i), 이것은 차수 2n − 1 이하의 다항식에 대해 정확하다. 이 정확한 규칙은 가우스-르장드르 구적법 규칙으로 알려져 있다. 이 구적법 규칙은 f (x)가 [−1, 1]에서 차수 2n − 1 이하의 다항식으로 잘 근사될 때만 위의 적분에 대한 정확한 근사값이 된다. 가우스-르장드르 구적법 규칙은 일반적으로 끝점 특이점을 가진 적분 가능한 함수에는 사용되지 않는다. 대신 피적분 함수를 다음과 같이 쓸 수 있다면 f(x) = \left(1 - x\right)^\alpha \left(1 + x\right)^\beta g(x),\quad \alpha,\beta > -1, 여기서 g(x)는 낮은 차수의 다항식으로 잘 근사된다면, 대안적인 노드 i'와 가중치 i'가 일반적으로 더 정확한 구적법 규칙을 제공한다. 이것들은 가우스-야코비 구적법 규칙으로 알려져 있다. 즉, \int_{-1}^1 f(x)\,dx = \int_{-1}^1 \left(1 - x\right)^\alpha \left(1 + x\right)^\beta g(x)\,dx \approx \sum_{i=1}^n w_i' g\left(x_i'\right). 일반적인 가중치로는 \frac{1}{\sqrt{1 - x^2 (체비쇼프-가우스) 및 \sqrt{1 - x^2}이 포함된다. 또한 반무한(가우스-라게르 구적법) 및 무한 구간(가우스-에르미트 구적법)에 대해 적분할 수도 있다. 가우스 구적법 노드와 가중치를 계산하기 위한 핵심 관찰인 구적법 노드 i가 직교 다항식 클래스(가중 내적에 대해 직교하는 클래스)에 속하는 다항식의 근이라는 것을 보일 수 있다 (Press 외 또는 Stoer와 Bulirsch 참조).
# 가우스-르장드르 구적법
가우스-르장드르 구적법 1=n = 5까지) 위에서 언급한 가장 간단한 적분 문제, 즉 [-1, 1]에서 f(x)가 다항식으로 잘 근사되는 경우, 관련 직교 다항식은 Pn(x)로 표기되는 르장드르 다항식이다. n번째 다항식을 1=Pn(1) = 1로 정규화하면, i번째 가우스 노드 xi는 Pn의 i번째 근이며 가중치는 다음 공식으로 주어진다.p=887 w_i = \frac{2}{\left( 1 - x_i^2 \right) \left[P'_n(x_i)\right]^2}. 일부 저차 구적법 규칙은 아래에 표로 정리되어 있다 (구간 [−1, 1]에 대한 내용이며, 다른 구간에 대해서는 아래 섹션을 참조). {| class="wikitable" | 점, xi ! colspan="2" | 가중치, wi |- | 1 | colspan="2" | 0 | colspan="2" | 2 |- | 2 | \pm\frac{1}{\sqrt{3 || ±0.57735... | colspan="2" | 1 |- | rowspan="2" | 3 | colspan="2" | 0 | \frac{8}{9} || 0.888889... |- | \pm\sqrt{\frac{3}{5 || ±0.774597... | \frac{5}{9} || 0.555556... |- | rowspan="2" | 4 | \pm\sqrt{\frac{3}{7} - \frac{2}{7}\sqrt{\frac{6}{5 || ±0.339981... | \frac{18 + \sqrt{30{36} || 0.652145... |- | \pm\sqrt{\frac{3}{7} + \frac{2}{7}\sqrt{\frac{6}{5 || ±0.861136... | \frac{18 - \sqrt{30{36} || 0.347855... |- | rowspan="3" | 5 | colspan="2" | 0 | \frac{128}{225} || 0.568889... |- | \pm\frac{1}{3}\sqrt{5 - 2\sqrt{\frac{10}{7 || ±0.538469... | \frac{322 + 13\sqrt{70{900} || 0.478629... |- | \pm\frac{1}{3}\sqrt{5 + 2\sqrt{\frac{10}{7 || ±0.90618... | \frac{322 - 13\sqrt{70{900} || 0.236927... |}
# 구간 변경
가우스 구적법 규칙을 적용하기 전에 [a, b]에 대한 적분을 [−1, 1]에 대한 적분으로 변경해야 한다. 이 구간 변경은 다음과 같이 할 수 있다. \int_a^b f(x)\,dx = \int_{ -1}^1 f\left(\frac{b-a}{2}\xi + \frac{a+b}{2}\right)\,\frac{dx}{d\xi}d\xi 여기서 \frac{dx}{d\xi} = \frac{b-a}{2} n점 가우스 구적법 (\xi, w) 규칙을 적용하면 다음 근사값이 나온다. \int_a^b f(x)\,dx \approx \frac{b-a}{2} \sum_{i=1}^n w_i f\left(\frac{b-a}{2}\xi_i + \frac{a+b}{2}\right).
# 2점 가우스 구적법 규칙 예시
2점 가우스 구적법 규칙을 사용하여 로켓이 t = 8\mathrm{s} 에서 t = 30\mathrm{s}까지 이동한 거리를 다음과 같이 근사한다. s = \int_{8}^{30}{\left( 2000\ln\left[ \frac{140000}{140000 - 2100t} \right] - 9.8t \right){dt 표 1에 주어진 가중치와 절편을 사용할 수 있도록 적분 한계를 변경한다. 또한 절대 상대 오차를 구한다. 실제 값은 11061.34m로 주어진다. 해결 먼저 적분 한계를 \left[ 8,30 \right]에서 \left[ - 1,1 \right]로 변경하면 \begin{align} \int_{8}^{30} {f(t) dt} &= \frac{30 - 8}{2} \int_{- 1}^{1}{f\left( \frac{30 - 8}{2}x + \frac{30 + 8}{2} \right){dx \\\ &= 11\int_{- 1}^{1}{f\left( 11x + 19 \right){dx \end{align} 다음으로 표 1에서 2점 규칙에 대한 가중치 인자와 함수 인수 값을 얻는다. *c_1 = 1.000000000 *x_1 = - 0.577350269 *c_2 = 1.000000000 *x_2 = 0.577350269 이제 가우스 구적법 공식을 사용할 수 있다. \begin{align} 11\int_{-1}^{1}{f\left( 11x + 19 \right){dx & \approx 11\left[ c_1 f\left( 11 x_1 + 19 \right) + c_2 f\left( 11 x_2 + 19 \right) \right] \\\ &= 11\left[ f\left( 11( - 0.5773503) + 19 \right) + f\left( 11(0.5773503) + 19 \right) \right] \\\ &= 11\left[ f(12.64915) + f(25.35085) \right] \\\ &= 11\left[ (296.8317) + (708.4811) \right] \\\ &= 11058.44 \end{align} 이유는 다음과 같다. \begin{align} f(12.64915) & = 2000\ln\left[ \frac{140000}{140000 - 2100(12.64915)} \right] - 9.8(12.64915) \\\ &= 296.8317 \end{align} \begin{align} f(25.35085) & = 2000\ln\left[ \frac{140000}{140000 - 2100(25.35085)} \right] - 9.8(25.35085) \\\ &= 708.4811 \end{align} 실제 값이 11061.34m이므로 절대 상대 오차 \left| \varepsilon_{t} \right|는 다음과 같다. \left| \varepsilon_{t} \right| = \left| \frac{11061.34 - 11058.44}{11061.34} \right| \times 100\% = 0.0262\%
# 다른 형식
적분 문제는 피적분 함수에 양의 무게 함수 ω를 도입하고 [−1, 1] 이외의 구간을 허용함으로써 약간 더 일반적인 방식으로 표현될 수 있다. 즉, 문제는 다음을 계산하는 것이다. \int_a^b \omega(x)\,f(x)\,dx a, b, ω를 일부 선택한다. 1=a = −1, 1=b = 1, 1=ω(x) = 1의 경우 문제는 위에서 고려한 것과 동일하다. 다른 선택은 다른 적분 규칙으로 이어진다. 이들 중 일부는 아래에 표로 정리되어 있다. Abramowitz and Stegun (A & S)에 대한 방정식 번호가 주어진다. {| class="wikitable" |- | −1, 1 || 1 || 르장드르 다항식 || 25.4.29 || 가우스-르장드르 구적법 |- | −1, 1 || \left(1 - x\right)^\alpha \left(1 + x\right)^\beta,\quad \alpha, \beta > -1 || 야코비 다항식 || 25.4.33 (1=β = 0) || 가우스-야코비 구적법 |- | −1, 1 || \frac{1}{\sqrt{1 - x^2 || 체비쇼프 다항식 (1종) || 25.4.38 || 체비쇼프-가우스 구적법 |- | −1, 1 || \sqrt{1 - x^2} || 체비쇼프 다항식 (2종) || 25.4.40 || 체비쇼프-가우스 구적법 |- | 0, ∞ || e^{-x}\, || 라게르 다항식 || 25.4.45 || 가우스-라게르 구적법 |- | 0, ∞ || x^\alpha e^{-x},\quad \alpha>-1 || 일반화된 라게르 다항식 || || 가우스-라게르 구적법 |- | −∞, ∞ || e^{-x^2} || 에르미트 다항식 || 25.4.46 || 가우스-에르미트 구적법 |}
## 기본 정리
pn을 다음과 같은 차수 n의 자명하지 않은 다항식이라고 하자. \int_a^b \omega(x) \, x^k p_n(x) \, dx = 0, \quad \text{for all } k = 0, 1, \ldots, n - 1. 위의 모든 직교 다항식에 대해 이것이 참이라는 점에 유의하라. 왜냐하면 각 pn은 jj에 대해 직교하도록 구성되어 있으며, xk는 그 집합의 스팬에 있기 때문이다. n개의 노드 xi를 pn의 근으로 선택하면, 차수 2n − 1 이하의 모든 다항식 h(x)에 대해 가우스 구적법 계산 적분을 정확하게 만드는 n개의 가중치 wi가 존재한다. 또한 이 모든 노드 xi는 열린 구간 (a, b)에 놓인다.pp=172–175 이 주장의 첫 번째 부분을 증명하기 위해, 차수 2n − 1 이하의 임의의 다항식 h(x)를 취한다. 이를 직교 다항식 pn으로 나누면 다음과 같다. h(x) = p_n(x) \, q(x) + r(x). 여기서 q(x)는 차수 n − 1 이하인 몫이며(그 차수와 제수 pn의 차수의 합은 피제수의 차수와 같아야 하므로), r(x)은 나머지이며 역시 차수 n − 1 이하이다(나머지의 차수는 항상 제수의 차수보다 작기 때문). pn은 가정에 따라 차수 n 미만의 모든 단항식에 직교하므로 몫 q(x)에 직교해야 한다. 따라서 \int_a^b \omega(x)\,h(x)\,dx = \int_a^b \omega(x)\,\big( \, p_n(x) q(x) + r(x) \, \big)\,dx = \int_a^b \omega(x)\,r(x)\,dx. 나머지 r(x)는 차수 n − 1 이하이므로 라그랑주 다항식 li(x)을 사용하여 n개의 보간점을 사용하여 정확하게 보간할 수 있다. 여기서 l_i(x) = \prod _{j \ne i} \frac{x-x_j}{x_i-x_j}. 다음이 성립한다. r(x) = \sum_{i=1}^n l_i(x) \, r(x_i). 그러면 그것의 적분은 다음과 같다. \int_a^b \omega(x)\,r(x)\,dx = \int_a^b \omega(x) \, \sum_{i=1}^n l_i(x) \, r(x_i) \, dx = \sum_{i=1}^n \, r(x_i) \, \int_a^b \omega(x) \, l_i(x) \, dx = \sum_{i=1}^n \, r(x_i) \, w_i, 여기서 노드 xi와 관련된 가중치 wi는 li(x)의 가중 적분과 같도록 정의된다 (가중치에 대한 다른 공식은 아래 참조). 그러나 모든 xi는 pn의 근이므로 위 나눗셈 공식에 의해 다음이 성립한다. h(x_i) = p_n(x_i) \, q(x_i) + r(x_i) = r(x_i), 모든 i에 대해. 따라서 최종적으로 다음을 얻는다. \int_a^b \omega(x)\,h(x)\,dx = \int_a^b \omega(x) \, r(x) \, dx = \sum_{i=1}^n w_i \, r(x_i) = \sum_{i=1}^n w_i \, h(x_i). 이는 차수 2n − 1 이하의 모든 다항식 h(x)에 대해 그 적분이 가우스 구적법 합계로 정확하게 주어진다는 것을 증명한다. 주장의 두 번째 부분을 증명하기 위해, 다항식 pn의 인수 분해된 형태를 고려한다. 임의의 켤레 복소수 근은 실수 전체에 걸쳐 엄격히 양수 또는 엄격히 음수인 이차 인수를 생성한다. 구간 a에서 b 외부의 근에 해당하는 인수는 해당 구간에 걸쳐 부호를 변경하지 않는다. 마지막으로 구간 a에서 b 내부의 근 xi에 해당하는 홀수 차수 인수의 경우, pn에 하나의 인수를 더 곱하여 새로운 다항식을 만든다. p_n(x) \, \prod_i (x - x_i). 이 다항식은 해당 구간 내의 모든 근이 이제 짝수 차수이므로 구간 a에서 b에 걸쳐 부호를 변경할 수 없다. 따라서 적분은 \int_a^b p_n(x) \, \left( \prod_i (x - x_i) \right) \, \omega(x) \, dx \ne 0, 무게 함수 ω(x)는 항상 음수가 아니기 때문이다. 그러나 pn은 차수 n − 1 이하의 모든 다항식에 직교하므로 곱의 차수는 \prod_i (x - x_i) 최소 n이어야 한다. 따라서 pn은 구간 a에서 b에 n개의 서로 다른 실수 근을 가진다.
### 가중치에 대한 일반 공식
가중치는 다음과 같이 표현할 수 있다. 1 여기서 a_{k}는 p_{k}(x)에서 x^{k}의 계수이다. 이를 증명하기 위해 라그랑주 보간을 사용하여 r(x)를 r(x_{i})로 표현할 수 있음을 유의하라. r(x) = \sum_{i=1}^{n} r(x_{i}) \prod_{\begin{smallmatrix} 1 \leq j \leq n \\\ j \neq i \end{smallmatrix\frac{x-x_{j{x_{i}-x_{j 왜냐하면 r(x)는 차수가 n보다 작아서 n개의 다른 점에서 가지는 값에 의해 고정되기 때문이다. 양변에 ω(x)를 곱하고 a에서 b까지 적분하면 \int_{a}^{b}\omega(x)r(x)dx = \sum_{i=1}^{n} r(x_{i}) \int_{a}^{b}\omega(x)\prod_{\begin{smallmatrix} 1 \leq j \leq n \\\ j \neq i \end{smallmatrix \frac{x-x_{j{x_{i}-x_{jdx 따라서 가중치 wi는 다음과 같이 주어진다. w_{i} = \int_{a}^{b}\omega(x)\prod_{\begin{smallmatrix}1\leq j\leq n\\\j\neq i\end{smallmatrix\frac{x-x_{j{x_{i}-x_{jdx w_{i}에 대한 이 적분 표현식은 직교 다항식 p_{n}(x)와 p_{n-1}(x)로 다음과 같이 표현할 수 있다. 다음과 같이 쓸 수 있다. \prod_{\begin{smallmatrix} 1 \leq j \leq n \\\ j \neq i \end{smallmatrix \left(x-x_{j}\right) = \frac{\prod_{1\leq j\leq n} \left(x - x_{j}\right)}{x-x_{i = \frac{p_{n}(x)}{a_{n}\left(x-x_{i}\right)} 여기서 a_{n}은 p_{n}(x)에서 x^n의 계수이다. L'Hôpital의 정리를 사용하여 x가 x_{i}로 가는 극한을 취하면 \prod_{\begin{smallmatrix} 1 \leq j \leq n \\\ j \neq i \end{smallmatrix \left(x_{i}-x_{j}\right) = \frac{p'_{n}(x_{i})}{a_{n 따라서 가중치에 대한 적분 표현식을 다음과 같이 쓸 수 있다. 2 적분에서 다음과 같이 쓴다. \frac{1}{x-x_i} = \frac{1 - \left(\frac{x}{x_i}\right)^{k{x - x_i} + \left(\frac{x}{x_i}\right)^{k} \frac{1}{x - x_i} 다음이 나온다. \int_a^b\omega(x)\frac{x^kp_n(x)}{x-x_i}dx = x_i^k \int_{a}^{b}\omega(x)\frac{p_n(x)}{x-x_i}dx k \leq n인 경우, 왜냐하면 \frac{1-\left(\frac{x}{x_{i\right)^{k{x-x_{i 는 차수 k − 1의 다항식이며 p_{n}(x)에 대해 직교한다. 따라서 q(x)가 최대 n차 다항식이라면 다음이 성립한다. \int_{a}^{b}\omega(x)\frac{p_{n}(x)}{x-x_{i dx = \frac{1}{q(x_{i})} \int_{a}^{b} \omega(x)\frac{q(x) p_n(x)}{x-x_{idx q(x) = p_{n-1}(x)에 대해 오른쪽 적분을 다음과 같이 평가할 수 있다. \frac{p_{n}(x)}{x-x_{i는 차수 n − 1의 다항식이므로 \frac{p_{n}(x)}{x-x_{i = a_{n}x^{n-1} + s(x) 여기서 s(x)는 차수 n - 2의 다항식이다. s(x)는 p_{n-1}(x)에 대해 직교하므로 \int_{a}^{b}\omega(x)\frac{p_{n}(x)}{x-x_{idx=\frac{a_{n{p_{n-1}(x_{i})} \int_{a}^{b}\omega(x)p_{n-1}(x)x^{n-1}dx 그러면 다음과 같이 쓸 수 있다. x^{n-1} = \left(x^{n-1} - \frac{p_{n-1}(x)}{a_{n-1\right) + \frac{p_{n-1}(x)}{a_{n-1 괄호 안의 항은 차수 n - 2의 다항식이므로 p_{n-1}(x)에 대해 직교한다. 따라서 적분은 다음과 같이 쓸 수 있다. \int_{a}^{b}\omega(x)\frac{p_{n}(x)}{x-x_{idx = \frac{a_{n{a_{n-1} p_{n-1}(x_{i})} \int_{a}^{b}\omega(x) p_{n-1}(x)^{2} dx 방정식 (2)에 따라 가중치는 이것을 p'_{n}(x_{i})로 나누어 얻으며, 이는 방정식 (1)의 표현식을 산출한다. w_{i}는 직교 다항식 p_{n}(x)와 이제 p_{n+1}(x)를 사용하여 표현할 수도 있다. 3항 점화식 p_{n+1}(x_{i}) = (a) p_{n}(x_{i}) + (b) p_{n-1}(x_{i})에서 p_{n}(x_{i}) 항은 사라지므로 Eq. (1)의 p_{n-1}(x_{i})는 \frac{1}{b} p_{n+1} \left(x_i\right)로 대체될 수 있다.
### 가중치가 양수라는 증명
차수 2n - 2의 다음 다항식을 고려한다. f(x) = \prod_{\begin{smallmatrix} 1 \leq j \leq n \\\ j \neq i \end{smallmatrix\frac{\left(x - x_j\right)^2}{\left(x_i - x_j\right)^2} 여기서, 위에서처럼, xj는 다항식 p_{n}(x)의 근이다. 분명히 f(x_j) = \delta_{ij}이다. f(x)의 차수는 2n - 1보다 작으므로 p_{n}(x)에서 얻은 가중치와 노드를 포함하는 가우스 구적법 공식이 적용된다. j가 i와 같지 않을 때 f(x_{j}) = 0이므로, 다음이 성립한다. \int_{a}^{b}\omega(x)f(x)dx=\sum_{j=1}^{n}w_{j}f(x_{j}) = \sum_{j=1}^{n} \delta_{ij} w_j = w_{i} > 0. \omega(x)와 f(x) 모두 음이 아닌 함수이므로 w_{i} > 0이 성립한다.
## 가우스 구적법 규칙 계산
가우스 구적법 규칙의 노드 xi와 가중치 wi를 계산하는 많은 알고리즘이 있다. 가장 널리 사용되는 방법은 O(n2) 연산이 필요한 골룹-웰시 알고리즘, 평가에 3항 점화식을 사용하는 p_n(x) = 0을 해결하기 위한 뉴턴 방법(이는 O(n2) 연산이 필요함), 그리고 큰 n에 대해 O(n) 연산이 필요한 점근 공식이 있다.
### 점화식
스칼라 곱 (\cdot , \cdot)에 대해 r \ne s일 때 (p_r, p_s) = 0을 만족하고 차수 (p_r) = r이며 선행 계수가 1인 직교 다항식 p_r(일계수 다항식)는 다음 점화식을 만족한다. p_{r+1}(x) = (x - a_{r,r}) p_r(x) - a_{r,r-1} p_{r-1}(x) \cdots - a_{r,0}p_0(x) 및 스칼라 곱은 다음과 같이 정의된다. (f(x),g(x))=\int_a^b\omega(x)f(x)g(x)dx r = 0, 1, \ldots, n - 1에 대해 여기서 n은 무한대로 취할 수 있는 최대 차수이며, 여기서 a_{r,s} = \frac{\left(xp_r, p_s\right)}{\left(p_s, p_s\right)}이다. 우선, p_0(x) = 1로 시작하는 점화식으로 정의된 다항식은 선행 계수가 1이고 올바른 차수를 가진다. p_0로 시작점을 주면 p_r의 직교성은 귀납법으로 보일 수 있다. r = s = 0에 대해 다음이 성립한다. (p_1,p_0) = (x-a_{0,0}) (p_0,p_0) = (xp_0,p_0) - a_{0,0}(p_0,p_0) = (xp_0,p_0) - (xp_0,p_0) = 0. 이제 p_0, p_1, \ldots, p_r이 직교하면 p_{r+1}도 직교한다. 왜냐하면 다음 식에서 (p_{r+1}, p_s) = (xp_r, p_s) - a_{r,r}(p_r, p_s) - a_{r,r-1}(p_{r-1}, p_s)\cdots - a_{r,0}(p_0, p_s) 모든 스칼라 곱은 첫 번째 곱과 p_s가 같은 직교 다항식을 만나는 곳을 제외하고는 사라진다. 따라서 (p_{r+1},p_s) = (xp_r,p_s) - a_{r,s}(p_s,p_s) = (xp_r,p_s)-(xp_r,p_s) = 0. 그러나 스칼라 곱이 (xf, g) = (f,xg)를 만족하면(가우스 구적법의 경우 해당), 점화식은 3항 점화식으로 축소된다. s < r - 1이면 xp_s는 차수 r − 1 이하인 다항식이다. 반면에 p_r은 차수 r − 1 이하인 모든 다항식에 직교한다. 따라서 s < r − 1에 대해 (xp_r, p_s) = (p_r, xp_s) = 0 및 a_{r,s} = 0이 성립한다. 그러면 점화식은 다음으로 간단해진다. p_{r+1}(x) = (x-a_{r,r}) p_r(x) - a_{r,r-1} p_{r-1}(x) 또는 p_{r+1}(x) = (x-a_r) p_r(x) - b_r p_{r-1}(x) (규약 p_{-1}(x) \equiv 0을 사용) 여기서 a_r := \frac{(xp_r,p_r)}{(p_r,p_r)}, \qquad b_r := \frac{(xp_r,p_{r-1})}{(p_{r-1},p_{r-1})} = \frac{(p_r,p_r)}{(p_{r-1},p_{r-1})} (마지막 식은 (xp_r, p_{r-1}) = (p_r, xp_{r-1}) = (p_r, p_r) 때문이다. 왜냐하면 xp_{r-1}은 차수 r 미만의 다항식으로 p_r과 다르기 때문).
### 골룹-웰시 알고리즘
3항 점화식은 행렬 형식 J\tilde{P} = x\tilde{P} - p_n(x) \mathbf{e}_n으로 쓸 수 있다. 여기서 \tilde{P} = \begin{bmatrix} p_0(x) & p_1(x) & \cdots & p_{n-1}(x) \end{bmatrix}^\mathsf{T}, \mathbf{e}_n은 n번째 표준 기저 벡터, 즉 \mathbf{e}_n = \begin{bmatrix} 0 & \cdots & 0 & 1 \end{bmatrix}^\mathsf{T}이고, J는 다음 3중 대각 행렬이며 야코비 행렬이라고 한다. \mathbf{J} = \begin{bmatrix} a_0 & 1 & 0 & \cdots & 0 \\\ b_1 & a_1 & 1 & \ddots & \vdots \\\ 0 & b_2 & \ddots & \ddots & 0 \\\ \vdots & \ddots & \ddots & a_{n-2} & 1 \\\ 0 & \cdots & 0 & b_{n-1} & a_{n-1} \end{bmatrix}. 가우스 구적법의 노드로 사용되는 차수 n까지의 다항식의 근 x_j는 이 행렬의 고유값을 계산하여 찾을 수 있다. 이 절차는 골룹-웰시 알고리즘으로 알려져 있다. 가중치와 노드를 계산하기 위해 다음 요소가 있는 대칭 3중 대각 행렬 \mathcal{J}를 고려하는 것이 좋다. \begin{align} \mathcal{J}_{k,i} = J_{k,i} &= a_{k-1} & k &= 1,2,\ldots,n \\\\[2.1ex] \mathcal{J}_{k-1,i} = \mathcal{J}_{k,k-1} = \sqrt{J_{k,k-1}J_{k-1,k &= \sqrt{b_{k-1 & k &= \hphantom{1,\,}2,\ldots,n. \end{align} 즉, \mathcal{J} = \begin{bmatrix} a_0 & \sqrt{b_1} & 0 & \cdots & 0 \\\ \sqrt{b_1} & a_1 & \sqrt{b_2} & \ddots & \vdots \\\ 0 & \sqrt{b_2} & \ddots & \ddots & 0 \\\ \vdots & \ddots & \ddots & a_{n-2} & \sqrt{b_{n-1 \\\ 0 & \cdots & 0 & \sqrt{b_{n-1 & a_{n-1} \end{bmatrix}. **J**와 \mathcal{J}는 닮음 행렬이므로 같은 고유값(노드)을 가진다. 가중치는 해당 고유 벡터에서 계산할 수 있다. \phi^{(j)}가 고유값 xj와 관련된 정규화된 고유 벡터(즉, 유클리드 노름이 1인 고유 벡터)이면 해당 가중치는 이 고유 벡터의 첫 번째 성분에서 계산할 수 있다. w_j = \mu_0 \left(\phi_1^{(j)}\right)^2 여기서 \mu_0는 무게 함수의 적분이다. \mu_0 = \int_a^b \omega(x) dx. 자세한 내용은 2007 등을 참조하라.
## 오차 추정
가우스 구적법 규칙의 오차는 다음과 같이 나타낼 수 있다.loc=Thm 3.6.24 2n개의 연속 도함수를 갖는 피적분 함수에 대해 \int_a^b \omega(x)\,f(x)\,dx - \sum_{i=1}^n w_i\,f(x_i) = \frac{f^{(2n)}(\xi)}{(2n)!} \, (p_n, p_n) (a, b)의 어떤 ξ에 대해, 여기서 pn은 1을 선행 계수로 갖는 일계수 차수 n의 직교 다항식이고 (f,g) = \int_a^b \omega(x) f(x) g(x) \, dx. 1=ω(x) = 1의 중요한 특수한 경우에 대한 오차 추정은 다음과 같다.loc=§5.2 \frac{\left(b - a\right)^{2n+1} \left(n!\right)^4}{(2n + 1)\left[\left(2n\right)!\right]^3} f^{(2n)} (\xi), \qquad a < \xi < b. Stoer와 Bulirsch는 이 오차 추정이 실제로는 불편하다고 지적한다. 왜냐하면 차수 2n 도함수를 추정하기 어려울 수 있으며, 또한 실제 오차가 도함수에 의해 확립된 경계보다 훨씬 작을 수 있기 때문이다. 다른 접근 방식은 서로 다른 차수의 두 가지 가우스 구적법 규칙을 사용하고 두 결과 간의 차이로 오차를 추정하는 것이다. 이러한 목적을 위해 가우스-크론로드 구적법 규칙이 유용할 수 있다.
## 가우스-크론로드 규칙
가우스-크론로드 구적법 공식 구간 [a, b]가 세분되면 새로운 부분 구간의 가우스 평가 지점은 이전 평가 지점과 절대 일치하지 않으며(홀수 개수에 대해 0인 경우 제외) 따라서 모든 지점에서 피적분 함수를 평가해야 한다. 가우스-크론로드 규칙은 n점 규칙에 n + 1점을 추가하여 결과 규칙이 차수 2n + 1이 되도록 확장된 가우스 구적법 규칙이다. 이를 통해 저차 추정의 함수 값을 재사용하면서 고차 추정을 계산할 수 있다. 가우스 구적법 규칙과 크론로드 확장 간의 차이는 종종 근사 오차의 추정으로 사용된다.
## 가우스-로바토 규칙
네덜란드 수학자 레우엘 로바토(Rehuel Lobatto)의 이름을 따서 **로바토 구적법**이라고도 알려져 있다.p=888 가우스 구적법과 유사하며 다음과 같은 차이점이 있다. # 적분 지점에는 적분 구간의 끝점이 포함된다. # 적분 지점의 개수 n에 대해 차수 2n − 3까지의 다항식에 대해 정확하다.2000 구간 [−1, 1]에 대한 함수 f(x)의 로바토 구적법: \int_{-1}^1 {f(x) \, dx} = \frac {2} {n(n-1)}[f(1) + f(-1)] + \sum_{i = 2}^{n-1} {w_i f(x_i)} + R_n. 절편: xi는 P'_{n-1}(x)의 (i - 1)번째 근이며, 여기서 P_m(x)는 m차 표준 르장드르 다항식을 나타내고 대시는 미분을 나타낸다. 가중치: w_i = \frac{2}{n(n - 1)\left[P_{n-1}\left(x_i\right)\right]^2}, \qquad x_i \ne \pm 1. 나머지: R_n = \frac{-n\left(n - 1\right)^3 2^{2n-1} \left[\left(n - 2\right)!\right]^4}{(2n-1) \left[\left(2n - 2\right)!\right]^3} f^{(2n-2)}(\xi), \qquad -1 < \xi < 1. 일부 가중치는 다음과 같다. {| class="wikitable" |- | rowspan="2" | 3 | 0 || \frac{4}{3} |- | \pm 1 || \frac{1}{3} |- | rowspan="2" | 4 | \pm \sqrt{\frac{1}{5 || \frac{5}{6} |- | \pm 1 || \frac{1}{6} |- | rowspan="3" | 5 | 0 || \frac{32}{45} |- | \pm\sqrt{\frac{3}{7 || \frac{49}{90} |- | \pm 1 || \frac{1}{10} |- | rowspan="3" | 6 | \pm\sqrt{\frac{1}{3}-\frac{2\sqrt{7{21 || \frac{14+\sqrt{7{30} |- | \pm\sqrt{\frac{1}{3} + \frac{2\sqrt{7{21 || \frac{14 - \sqrt{7{30} |- | \pm 1 || \frac{1}{15} |- | rowspan="4" | 7 | 0 || \frac{256}{525} |- | \pm\sqrt{\frac{5}{11}-\frac{2}{11}\sqrt{\frac{5}{3 || \frac{124 + 7\sqrt{15{350} |- | \pm\sqrt{\frac{5}{11} + \frac{2}{11}\sqrt{\frac{5}{3 || \frac{124 - 7\sqrt{15{350} |- | \pm 1 || \frac{1}{21} |} 내부 노드가 2개인 이 알고리즘의 적응형 변형2000은 GNU 옥타브 및 매트랩에서 각각 `quadl` 및 `integrate`로 제공된다.20122018
## 인용
=