리처드슨 외삽법은 수치 해석에서 사용되는 오차를 줄이는 기법으로, 알려진 데이터와 점근 전개를 사용하여 함수의 극한값을 더욱 정확하게 추정한다. 이 방법은 절단 오차를 줄여 더 나은 근사값을 얻기 위해 반복적으로 적용되며, 수렴 속도를 추정하는 데에도 활용될 수 있다.
알려진 두 데이터 값 f(x)와 f(\lambda x) (단, 0 < \lambda < 1)로부터, x \to 0의 극한값 F의 근사값 \bar{f}^{(1)}_1을 구하는 알고리즘은 다음과 같다.:\bar{f}^{(1)}_1 = \frac{f(\lambda x)-\lambda^{p_1} f(x)}{1-\lambda^{p_1}}단, p_1은 f를 x의 다항식으로 점근 전개한 다음 식에 나타나는 지수이다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots, \qquad 0또한, 추가 데이터로 f(\lambda^2 x),\ldots,f(\lambda^M x)를 구할 수 있다면,:\begin{align}\bar{f}^{(0)}_i&=f(\lambda^i x),\quad i=1,\ldots,M \\\bar{f}^{(j)}_i&=\frac{\bar{f}^{(j-1)}_i-\lambda^{p_j}\bar{f}^{(j-1)}_{i-1}}{1-\lambda^{p_j}},\quad j=1,\ldots,i\end{align}을 차례로 구함으로써, 더욱 정밀한 근사값 \bar{f}^{(M)}_M을 구할 수 있다. 2. 1. 표기법 A_0(h)를 단계 크기 ''h'' (여기서 0 < h < 1)에 의존하는 ''A^*''(정확한 값)의 근사값이라고 하자. 오차 공식은 다음과 같다. A^* = A_0(h)+a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots 여기서 a_i는 미지의 상수이고 k_i는 h^{k_i} > h^{k_{i+1}}를 만족하는 알려진 상수이다. 또한 O(h^{k_i})는 A^* = A_i(h)+O(h^{k_i})와 같은 A_i(h) 근사의 절단 오차를 나타낸다. 마찬가지로, A^*=A_i(h)+O(h^{k_i})에서 근사 A_i(h)는 O(h^{k_i}) 근사라고 한다.빅 오 표기법으로 단순화하면 다음 공식은 동일하다. \begin{align}A^* &= A_0(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots \\A^* &= A_0(h)+ a_0h^{k_0} + O(h^{k_1}) \\A^* &= A_0(h)+O(h^{k_0})\end{align} 2. 2. 목적 리처드슨 외삽법은 어떤 값 A^*를 추정할 때, 초기 근사값 A_0(h)와 그 오차 O(h^{k_0})를 이용하여 더 정확한 근사값 A_1(h)를 찾는 방법이다. 이 과정의 핵심 목표는 오차를 나타내는 항 중에서 가장 큰 영향을 주는 주요 항(O(h^{k_0}))을 제거하는 것이다. 이를 통해 결과적으로 더 작은 절단 오차 O(h^{k_1}) (k_1 > k_0)를 갖는 개선된 근사값 A_1(h)를 얻게 된다.즉, 리처드슨 외삽법을 사용하면 동일한 단계 크기 h를 사용하더라도 초기 근사값보다 더 높은 정확도를 가진 결과를 얻을 수 있다는 이점이 있다. 일반적으로 이 과정을 반복하여 얻어지는 근사값 A_i(h)는 이전 단계의 근사값 A_j(h) (단, i>j)보다 더 정확한 추정치가 된다. 이 외삽 과정은 반복적으로 적용될 수 있으며, 반복할수록 더 많은 오차 항들이 순차적으로 제거되어 점점 더 정확한 근사값을 얻는 것이 가능하다. 2. 3. 절차 단계 크기 h와 상수 t에 대해, h / t를 사용하여 A^*에 대한 두 가지 공식을 표현하면 다음과 같다.A^* = A_0(h)+ a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + O(h^{k_3}) A^* = A_0\!\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + a_1\left(\frac{h}{t}\right)^{k_1} + a_2\left(\frac{h}{t}\right)^{k_2} + O(h^{k_3}) 여기서 첫 번째 오차 항(a_0h^{k_0})을 제거하여 근사치의 정확도를 O(h^{k_0})에서 O(h^{k_1})로 개선할 수 있다. 이를 위해 두 번째 식에 t^{k_0}을 곱하고 첫 번째 식을 빼면 다음 식을 얻는다. (t^{k_0}-1)A^* = \bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg] + \bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)+ \bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg) + O(h^{k_3}). 이 연산을 통해 \bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg] 항이 (t^{k_0}-1)A^*의 O(h^{k_1}) 근사치가 된다. 이 식을 A^*에 대해 정리하면 다음과 같다.A^* = \frac{\bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg]}{t^{k_0}-1}+ \frac{\bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)}{t^{k_0}-1}+ \frac{\bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg)}{t^{k_0}-1}+O(h^{k_3}) 여기서 새로운 근사식 A_1(h)를 다음과 같이 정의하면,A_1(h) = \frac{t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)}{t^{k_0}-1} .A^* = A_1(h)+O(h^{k_1})로 표현할 수 있으며, 이는 기존 A_0(h)보다 개선된 근사치이다.알려진 두 데이터 값 f(x)와 f(\lambda x) (단, 0 < \lambda < 1)를 이용하여 x \to 0일 때의 극한값 F에 대한 근사값 \bar{f}^{(1)}_1을 구하는 일반적인 알고리즘은 다음과 같다.\bar{f}^{(1)}_1 = \frac{f(\lambda x)-\lambda^{p_1} f(x)}{1-\lambda^{p_1}}이때 p_1은 함수 f(x)를 x에 대한 다항식으로 점근 전개했을 때 나타나는 첫 번째 항의 지수이다.f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots, \qquad (0만약 f(\lambda^2 x), \ldots, f(\lambda^M x)와 같이 추가적인 데이터를 얻을 수 있다면, 다음의 반복 계산을 통해 더욱 정밀한 근사값 \bar{f}^{(M)}_M을 구할 수 있다.초기값 설정:\bar{f}^{(0)}_i = f(\lambda^i x), \quad i=1, \ldots, M 반복 계산:\bar{f}^{(j)}_i = \frac{\bar{f}^{(j-1)}_i - \lambda^{p_j} \bar{f}^{(j-1)}_{i-1}}{1-\lambda^{p_j}}, \quad j=1, \ldots, i; \quad i=1, \ldots, M이 과정을 통해 최종적으로 \bar{f}^{(M)}_M은 F에 대한 더 정확한 근사값을 제공한다. 2. 4. 점화식 근사값에 대한 일반적인 점화 관계는 다음과 같이 정의할 수 있다. A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1} 여기서 k_{i+1}은 다음을 만족한다. A^* = A_{i+1}(h) + O(h^{k_{i+1}}) 알려진 두 데이터 f(x)와 f(\lambda x) (단, 0 < \lambda < 1)로부터, x \to 0일 때의 극한값 F의 근사값 \bar{f}^{(1)}_1을 구하는 알고리즘은 다음과 같다.:\bar{f}^{(1)}_1 = \frac{f(\lambda x)-\lambda^{p_1} f(x)}{1-\lambda^{p_1}}단, p_1은 f를 x의 다항식으로 점근 전개한 다음 식에 나타나는 지수이다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots, \qquad 0또한, 추가 데이터로 f(\lambda^2 x),\ldots,f(\lambda^M x)를 구할 수 있다면,:\begin{align}\bar{f}^{(0)}_i&=f(\lambda^i x),\quad i=1,\ldots,M \\\bar{f}^{(j)}_i&=\frac{\bar{f}^{(j-1)}_i-\lambda^{p_j}\bar{f}^{(j-1)}_{i-1}}{1-\lambda^{p_j}},\quad j=1,\ldots,i\end{align}을 차례로 구함으로써, 더욱 정밀한 근사값 \bar{f}^{(M)}_M을 구할 수 있다. 2. 5. 성질 A_0(h)를 단계 크기 h (여기서 0 < h < 1)에 의존하는 실제 값 A^*의 근사값이라고 하자. 이때 오차는 다음과 같은 형태로 표현될 수 있다. A^* = A_0(h)+a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots 여기서 a_i는 알 수 없는 상수이고, k_i는 h^{k_i} > h^{k_{i+1}}를 만족하는 알려진 상수이다. O(h^{k_i})는 A^* = A_i(h)+O(h^{k_i})와 같이 근사값 A_i(h)의 절단 오차를 나타낸다. 이 경우, 근사 A_i(h)는 O(h^{k_i}) 차수의 정확도를 가진다고 말한다.빅 오 표기법을 사용하여 위 오차 공식을 단순화하면 다음과 같이 나타낼 수 있다. \begin{align}A^* &= A_0(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots \\A^* &= A_0(h)+ a_0h^{k_0} + O(h^{k_1}) \\A^* &= A_0(h)+O(h^{k_0})\end{align} 가장 낮은 차수의 오차항 O(h^{k_0})이 전체 오차를 지배하게 된다. 리처드슨 외삽법은 이러한 오차항을 단계적으로 제거하여 더 정확한 근사값을 얻는 방법이다. 2. 5. 1. 수렴 속도 추정 리처드슨 외삽법은 선형 수열 변환으로 간주될 수 있다.또한, 이 방법은 k_0의 값이나 실제 값 A^*를 미리 알지 못할 때, 절단 오차의 주요 항이 단계 크기(h)에 따라 어떻게 변하는지를 나타내는 지수 k_0를 추정하는 데 사용될 수 있다. 이러한 기술은 알려지지 않은 수렴 속도를 정량화하는 데 유용할 수 있다. h, h / t, h / s라는 세 가지 다른 단계 크기를 사용하여 얻은 근사값 A_i(h), A_i(h/t), A_i(h/s)가 주어지면, 실제 값 A^*에 대해 다음 관계식이 성립한다.A^*=\frac{t^{k_0}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} + O(h^{k_1}) = \frac{s^{k_0}A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1} + O(h^{k_1})이 식으로부터 다음과 같은 근사 관계식을 얻을 수 있다. (참고: 위 식의 O(h^{k_1}) 항은 다음 차수의 오차항을 나타내는데, 두 표현에서 이 오차항의 정확한 형태는 다를 수 있으므로, 이 항들을 무시하고 얻는 아래의 관계식은 근사적인 것이다.)A_i\left(\frac{h}{t}\right) + \frac{A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} \approx A_i\left(\frac{h}{s}\right) +\frac{A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1}이 근사식을 수치적으로 풀면, 적절히 선택된 h, s, t 값에 대해 k_0를 추정할 수 있다.t \neq 1이고 t>0일 때, 특별히 s = t^2로 선택하면, 위 근사 관계식은 t^{k_0}에 대한 이차 방정식으로 간단해진다. 이를 통해 주어진 h와 t 값에 대해 k_0를 더 쉽게 구할 수 있다. 3. 방법 리처드슨 외삽법은 알려진 두 개 이상의 데이터 값과 함수의 점근 전개 정보를 이용하여 더 정확한 극한값을 추정하는 방법이다. 함수 f(x)가 x \to 0일 때 극한값 F를 가지고, 다음과 같은 점근 전개를 가진다고 가정한다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots, \qquad (0이때, 서로 다른 두 점 x와 \lambda x (단, 0 < \lambda < 1)에서의 함수 값 f(x)와 f(\lambda x)를 이용하여 가장 낮은 차수의 오차항(a_1 x^{p_1})을 소거함으로써 F에 대한 더 나은 근사값을 얻는 것이 기본 원리이다. 더 많은 데이터를 사용하여 점차적으로 더 높은 차수의 오차항을 제거하면 극한값 F에 대한 근사 정확도를 높일 수 있다. 자세한 계산 과정은 아래 '알고리즘' 섹션에서 설명한다. 3. 1. 알고리즘 알려진 두 데이터 f(x)와 f(\lambda x) (단, 0 < \lambda < 1)로부터, x \to 0일 때의 극한값 F의 근사값 \bar{f}^{(1)}_1을 구하는 기본적인 알고리즘은 다음과 같다.:\bar{f}^{(1)}_1 = \frac{f(\lambda x)-\lambda^{p_1} f(x)}{1-\lambda^{p_1}}여기서 p_1은 함수 f를 x에 대한 다항식으로 점근 전개했을 때, 가장 낮은 차수 항의 지수를 의미한다. 점근 전개식은 다음과 같은 형태를 가진다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots (단, 0)만약 f(\lambda^2 x), \ldots, f(\lambda^M x)와 같이 추가적인 데이터를 더 얻을 수 있다면, 다음과 같은 점화식을 이용하여 더 정밀한 근사값을 계산할 수 있다.:\begin{align}\bar{f}^{(0)}_i&=f(\lambda^i x),\quad i=1,\ldots,M \\\bar{f}^{(j)}_i&=\frac{\bar{f}^{(j-1)}_i-\lambda^{p_j}\bar{f}^{(j-1)}_{i-1}}{1-\lambda^{p_j}},\quad j=1,\ldots,i\end{align}이 계산을 j=1부터 j=M까지 순차적으로 수행하면, 최종적으로 더욱 정확한 근사값인 \bar{f}^{(M)}_M을 얻을 수 있다. 4. 정확도 \bar{f}^{(1)}_1는 x^{p_2}에 비례하는 오차를 갖는 근사값이다. 이를 수식으로 표현하면 다음과 같다.:\bar{f}^{(1)}_1 = F + O(x^{p_2})여기서 F는 참값이며, O(x^{p_2})는 점근 표기법으로 나타낸 오차항이다.마찬가지로, 리처드슨 외삽법을 M번 반복하여 얻은 근사값 \bar{f}^{(M)}_M의 오차는 다음 식과 같이 평가된다.:\bar{f}^{(M)}_M=F+O(x^{p_{M+1}})이는 외삽 과정을 반복할수록 오차항의 차수(p_{M+1})가 높아져 더 정확한 근사값을 얻을 수 있음을 의미한다. 5. 예제 리처드슨 외삽법은 근사 계산의 정확도를 높이는 데 유용한 기법으로, 특히 수치 해석 분야에서 널리 사용된다. 예를 들어, 상미분 방정식(ODE)을 수치적으로 풀 때 적용될 수 있다.구체적인 예시로 y'(t) = -y^2 (초기 조건 y(0) = 1)와 같은 상미분 방정식을 사다리꼴 공식으로 푸는 경우를 살펴볼 수 있다. 사다리꼴 공식만 사용할 경우, 정확도를 높이려면 단계 크기 h를 줄여야 하지만, h를 너무 작게 하면 반올림 오차나 계산 비용 증가 문제가 발생할 수 있다.리처드슨 외삽법은 서로 다른 단계 크기(h와 h/t)를 이용한 계산 결과를 조합하여 이러한 문제를 완화한다. 즉, 단순히 h를 매우 작게 만드는 대신, 외삽 과정을 통해 더 효율적으로 오차를 줄이고 높은 정확도의 근사값을 얻는 데 도움을 준다. 결과적으로 더 적은 계산량으로 원하는 정밀도에 도달하는 경우가 많다.아래 하위 섹션에서는 이 예시에 대한 구체적인 수학적 원리 설명과 리처드슨 외삽법 적용 과정을 보여주는 MATLAB 스타일의 의사 코드를 자세히 다룬다. 5. 1. 리처드슨 보외법 예시 우리가 어떤 값 A^*를 근사적으로 구하고 싶다고 가정해 보자. 이때 사용하는 근사 방법 A(h)가 작은 매개변수 h에 의존하며, 다음과 같은 형태를 가진다고 하자.A(h) = A^\ast + C h^n + O(h^{n+1}).여기서 C는 상수이고, O(h^{n+1})는 h가 0에 가까워질 때 h^{n+1}보다 빠르게 0으로 수렴하는 항들, 즉 h가 0에 가까워질 때 C h^n 항보다 훨씬 작은 고차 오차 항들을 나타낸다. 이 식은 A(h)의 주요 오차가 C h^n임을 의미한다.리처드슨 외삽법은 두 개의 서로 다른 단계 크기 h와 \frac{h}{t} (여기서 t는 보통 2와 같은 상수)를 이용하여 새로운 함수 R(h,t)를 정의함으로써 오차를 개선하는 방법이다. R(h,t)는 다음과 같이 정의된다. R(h,t) := \frac{ t^n A(h/t) - A(h)}{t^n-1} 이제 A(h)의 정의를 R(h,t) 식에 대입하여 정리하면 다음과 같다. \begin{align} R(h, t) &= \frac{ t^n \left( A^* + C \left(\frac{h}{t}\right)^n + O(h^{n+1}) \right) - \left( A^* + C h^n + O(h^{n+1}) \right) }{ t^n - 1} \\ &= \frac{ t^n A^* + t^n C \frac{h^n}{t^n} + t^n O(h^{n+1}) - A^* - C h^n - O(h^{n+1}) }{ t^n - 1} \\ &= \frac{ (t^n - 1) A^* + (C h^n - C h^n) + (t^n - 1) O(h^{n+1}) }{ t^n - 1} \\ &= A^* + \frac{(t^n - 1) O(h^{n+1})}{t^n - 1} \\ &= A^* + O(h^{n+1}). \end{align} 위 유도 과정에서 O(h^{n+1})는 h가 0에 가까워질 때 h^{n+1}에 비례하는 항들을 나타내며, 상수 계수(t^n 등)가 곱해지거나 더해져도 여전히 O(h^{n+1})로 표현될 수 있다.계산 결과 R(h,t) = A^* + O(h^{n+1}) 를 얻는다. R(h,t) 는 A(h)의 리처드슨 외삽법이라고 불리며, 이는 리처드슨 외삽법을 통해 얻은 새로운 근사값 R(h,t) 의 오차가 기존의 A(h) 의 오차 O(h^n) 보다 더 높은 차수인 O(h^{n+1}) 를 갖는다는 것을 보여준다. 즉, h가 작아질수록 R(h,t) 는 A(h) 보다 훨씬 빠르게 참값 A^*에 수렴한다.따라서 많은 경우, 단순히 h를 매우 작게 만들어 A(h')를 계산하는 것보다, 적절한 h와 t를 사용하여 R(h,t)를 계산하는 것이 원하는 정밀도를 얻는 데 더 효율적일 수 있다. 왜냐하면 h를 너무 작게 하면 컴퓨터 계산 시 반올림 오차가 커지거나, 계산에 필요한 계산 비용(시간과 자원)이 급격히 증가하는 문제가 발생할 수 있기 때문이다. 리처드슨 외삽법은 이러한 문제들을 완화하면서 더 정확한 근사값을 얻는 데 도움을 준다. 5. 2. 의사 코드 예시 다음은 리처드슨 외삽법을 사용하여 상미분 방정식(ODE) y'(t) = -y^2, y(0) = 1을 사다리꼴 공식으로 푸는 과정을 보여주는 MATLAB 스타일의 의사 코드이다. 이 예제에서는 각 반복마다 단계 크기 h를 절반으로 줄인다. 이는 위에서 설명한 t = 2에 해당한다. 사다리꼴 공식의 오차는 홀수 거듭제곱 항으로 표현될 수 있으므로, 여러 단계를 거친 누적 오차는 짝수 거듭제곱 항으로 나타난다. 따라서 t를 제곱한 4 = 2^2 = t^2의 거듭제곱을 의사 코드의 외삽 계산에 사용한다. 목표는 y(5)의 값을 구하는 것이다. 주어진 ODE의 정확한 해는 y(t) = \frac{1}{1 + t}이므로, y(5)의 정확한 값은 \frac{1}{5 + 1} = \frac{1}{6} \approx 0.1666...이다.이 의사 코드는 `Trapezoidal(f, tStart, tEnd, h, y0)`라는 함수가 이미 정의되어 있다고 가정한다. 이 함수는 함수 `f` (즉, y'), 시작 시간 `tStart`, 종료 시간 `tEnd`, 단계 크기 `h`, 초기값 `y0`를 입력받아 사다리꼴 공식을 사용하여 `y(tEnd)`의 근사값을 계산한다.초기 단계 크기 h를 너무 작게 설정하면 최종 결과에 불필요한 오차가 누적될 수 있다. 최적의 초기 단계 크기를 선택하는 방법들이 있지만, 한 가지 간단한 접근 방식은 상대적으로 큰 단계 크기로 시작하여 리처드슨 외삽법을 반복 적용하면서 오차가 원하는 허용 오차 범위 내에 들어올 때까지 단계 크기를 점진적으로 줄여나가는 것이다. tStart = 0 % 시작 시간 t = 0 tEnd = 5 % 종료 시간 t = 5 f = @(t,y) -y^2 % y의 도함수 정의: y' = f(t, y(t)) = -y^2 % 이 ODE의 해석적 해는 y(t) = 1/(1 + t) y0 = 1 % 초기 조건: y(tStart) = y(0) = 1 tolerance = 1e-11 % 목표 허용 오차 (약 10자리 정확도) % === 반복 제어 및 초기화 === maxRows = 20 % 최대 반복 횟수 (무한 루프 방지) initialH = tEnd - tStart % 초기 단계 크기 (여기서는 전체 구간 길이로 설정) haveWeFoundSolution = false % 해를 찾았는지 여부를 나타내는 플래그 h = initialH % 현재 단계 크기 % 리처드슨 외삽 결과를 저장할 행렬 A 초기화 (maxRows x maxRows 크기) % 실제로는 하삼각 행렬이며, 계산에는 이전 행과 현재 행만 필요함 A = zeros(maxRows, maxRows) % === 첫 번째 근사값 계산 === % 가장 큰 단계 크기(initialH)를 사용하여 첫 번째 근사값 계산 A(1, 1) = Trapezoidal(f, tStart, tEnd, h, y0) % === 리처드슨 외삽 반복 === % i는 행 번호를 나타냄 (1부터 maxRows - 1까지) for i = 1 : maxRows - 1 % 단계 크기를 절반으로 줄임 h = h / 2 % 새로운 단계 크기로 사다리꼴 공식을 적용하여 (i+1)행의 첫 번째 요소 계산 A(i + 1, 1) = Trapezoidal(f, tStart, tEnd, h, y0) % 리처드슨 외삽 공식을 사용하여 (i+1)행의 나머지 요소 계산 % j는 열 번호를 나타냄 (1부터 i까지) for j = 1 : i % 외삽 공식: A(i+1, j+1) = (4^j * A(i+1, j) - A(i, j)) / (4^j - 1) % 여기서 4는 t^2 = 2^2 임 (단계 크기를 반으로 줄였으므로 t=2) A(i + 1, j + 1) = ((4^j) * A(i + 1, j) - A(i, j)) / (4^j - 1) end % === 수렴 확인 === % 현재 단계에서 가장 정확한 근사값 (대각선 요소)과 이전 단계의 근사값 비교 % 두 값의 차이가 허용 오차보다 작으면 수렴한 것으로 간주 if abs(A(i + 1, i + 1) - A(i, i)) < tolerance print("y = ", A(i + 1, i + 1)) % 결과 출력 (MATLAB 스타일) haveWeFoundSolution = true break % 루프 종료 end end % === 결과 처리 === % 최대 반복 횟수 내에 해를 찾지 못한 경우 경고 메시지 출력 if ~haveWeFoundSolution print("경고: 원하는 허용 오차 ", tolerance," 내에서 해를 찾을 수 없습니다.") % 경고 출력 (MATLAB 스타일) print("마지막으로 계산된 외삽 값은 ", A(maxRows, maxRows),"입니다.") % 마지막 값 출력 (MATLAB 스타일) end
리처드슨 외삽법은 알려진 두 개 이상의 데이터 값과 함수의 점근 전개 정보를 이용하여 더 정확한 극한값을 추정하는 방법이다. 함수 f(x)가 x \to 0일 때 극한값 F를 가지고, 다음과 같은 점근 전개를 가진다고 가정한다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots, \qquad (0이때, 서로 다른 두 점 x와 \lambda x (단, 0 < \lambda < 1)에서의 함수 값 f(x)와 f(\lambda x)를 이용하여 가장 낮은 차수의 오차항(a_1 x^{p_1})을 소거함으로써 F에 대한 더 나은 근사값을 얻는 것이 기본 원리이다. 더 많은 데이터를 사용하여 점차적으로 더 높은 차수의 오차항을 제거하면 극한값 F에 대한 근사 정확도를 높일 수 있다. 자세한 계산 과정은 아래 '알고리즘' 섹션에서 설명한다. 3. 1. 알고리즘 알려진 두 데이터 f(x)와 f(\lambda x) (단, 0 < \lambda < 1)로부터, x \to 0일 때의 극한값 F의 근사값 \bar{f}^{(1)}_1을 구하는 기본적인 알고리즘은 다음과 같다.:\bar{f}^{(1)}_1 = \frac{f(\lambda x)-\lambda^{p_1} f(x)}{1-\lambda^{p_1}}여기서 p_1은 함수 f를 x에 대한 다항식으로 점근 전개했을 때, 가장 낮은 차수 항의 지수를 의미한다. 점근 전개식은 다음과 같은 형태를 가진다.:f(x) = F + \sum_{i\geq 1}a_i x^{p_i} = F + a_1 x^{p_1} + a_2 x^{p_2} + \cdots (단, 0)만약 f(\lambda^2 x), \ldots, f(\lambda^M x)와 같이 추가적인 데이터를 더 얻을 수 있다면, 다음과 같은 점화식을 이용하여 더 정밀한 근사값을 계산할 수 있다.:\begin{align}\bar{f}^{(0)}_i&=f(\lambda^i x),\quad i=1,\ldots,M \\\bar{f}^{(j)}_i&=\frac{\bar{f}^{(j-1)}_i-\lambda^{p_j}\bar{f}^{(j-1)}_{i-1}}{1-\lambda^{p_j}},\quad j=1,\ldots,i\end{align}이 계산을 j=1부터 j=M까지 순차적으로 수행하면, 최종적으로 더욱 정확한 근사값인 \bar{f}^{(M)}_M을 얻을 수 있다.
\bar{f}^{(1)}_1는 x^{p_2}에 비례하는 오차를 갖는 근사값이다. 이를 수식으로 표현하면 다음과 같다.:\bar{f}^{(1)}_1 = F + O(x^{p_2})여기서 F는 참값이며, O(x^{p_2})는 점근 표기법으로 나타낸 오차항이다.마찬가지로, 리처드슨 외삽법을 M번 반복하여 얻은 근사값 \bar{f}^{(M)}_M의 오차는 다음 식과 같이 평가된다.:\bar{f}^{(M)}_M=F+O(x^{p_{M+1}})이는 외삽 과정을 반복할수록 오차항의 차수(p_{M+1})가 높아져 더 정확한 근사값을 얻을 수 있음을 의미한다.
리처드슨 외삽법은 근사 계산의 정확도를 높이는 데 유용한 기법으로, 특히 수치 해석 분야에서 널리 사용된다. 예를 들어, 상미분 방정식(ODE)을 수치적으로 풀 때 적용될 수 있다.구체적인 예시로 y'(t) = -y^2 (초기 조건 y(0) = 1)와 같은 상미분 방정식을 사다리꼴 공식으로 푸는 경우를 살펴볼 수 있다. 사다리꼴 공식만 사용할 경우, 정확도를 높이려면 단계 크기 h를 줄여야 하지만, h를 너무 작게 하면 반올림 오차나 계산 비용 증가 문제가 발생할 수 있다.리처드슨 외삽법은 서로 다른 단계 크기(h와 h/t)를 이용한 계산 결과를 조합하여 이러한 문제를 완화한다. 즉, 단순히 h를 매우 작게 만드는 대신, 외삽 과정을 통해 더 효율적으로 오차를 줄이고 높은 정확도의 근사값을 얻는 데 도움을 준다. 결과적으로 더 적은 계산량으로 원하는 정밀도에 도달하는 경우가 많다.아래 하위 섹션에서는 이 예시에 대한 구체적인 수학적 원리 설명과 리처드슨 외삽법 적용 과정을 보여주는 MATLAB 스타일의 의사 코드를 자세히 다룬다.
[1] 간행물 The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam [2] 간행물 The deferred approach to the limit [3] Citation Some pioneers of extrapolation methods https://www.worldsci[...] WORLD SCIENTIFIC 2009-11-01 [4] 서적 Ordinary differential equations John Wiley and sons [5] 서적 Cで学ぶ数値計算アルゴリズム 共立出版
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다. 모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다. 하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다. 따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다. 문의하기 : help@durumis.com