룽게 현상

9차 다항식 보간법 (10개 지점에서 빨간색 곡선을 정확히 복제) 수학의 수치해석학 분야에서 **룽게 현상**(Runge's phenomenon, lang)은 등간격 보간점 집합에 대해 고차 다항식을 사용하여 다항식 보간법을 사용할 때 발생하는 구간 가장자리에서의 진동 문제이다. 이는 카를 다비트 톨메 룽게가 1901년에 특정 함수를 근사하기 위해 다항식 보간법을 사용할 때 오류의 동작을 탐색하면서 발견했다.url = https://archive.org/details/zeitschriftfrma12runggoog 이 발견은 차수를 높이는 것이 항상 정확도를 향상시키지는 않는다는 것을 보여준다. 이 현상은 푸리에 급수 근사에서의 깁스 현상과 유사하다. 바이어슈트라스 근사 정리는 구간 [a, b]에서 정의된 모든 연속 함수 f(x)에 대해, n=0, 1, 2, \ldots에 대한 다항식 함수 P_n(x) 집합이 존재하며, 각 함수의 차수가 최대 n이고, n이 무한대로 갈 때 [a, b]에서 f(x)에 균등 수렴한다고 명시한다. 이는 다음과 같이 표현할 수 있다. \lim_{n \rightarrow \infty} \left( \sup_{a \leq x \leq b} \left| f(x) - P_n(x) \right| \right) = 0. 함수 f(x)의 n+1개의 등간격 점들을 통과하는 n차 다항식 P_n(x)를 사용하여 보간하고자 하는 경우를 생각해보자. 자연스럽게 바이어슈트라스 정리로부터 더 많은 점을 사용하면 f(x)를 더 정확하게 재구성할 수 있을 것이라고 예상할 수 있다. 그러나 이 특정 다항식 함수 집합 P_n(x)는 균등 수렴 속성을 가질 것이라고 보장되지 않는다. 이 정리는 다항식 함수 집합이 존재한다고만 명시할 뿐, 이를 찾는 일반적인 방법을 제공하지는 않는다. 이러한 방식으로 생성된 P_n(x)는 사실 n이 증가함에 따라 f(x)에서 벗어날 수 있다. 이는 일반적으로 보간점 끝 근처에서 증폭되는 진동 패턴으로 발생한다. 이 현상의 발견은 룽게에 기인한다.jstor=2323093
# 문제
**룽게 함수**를 고려하자. f(x) = \frac{1}{1+25x^2}\, (아녜시의 마녀의 스케일링된 버전). 룽게는 이 함수가 −1과 1 사이의 등간격 점 xi에서 보간될 때 다음과 같이 된다는 것을 발견했다. x_i = \frac{2i}{n} - 1,\quad i \in \left\\{ 0, 1, \dots, n \right\\} 차수가 ≤ n인 다항식 P_n(x)를 사용하면, 결과 보간은 구간의 끝, 즉 −1과 1 근처에서 진동한다. 다항식의 차수가 증가하면 보간 오차가 (무한히) 증가한다는 것을 증명할 수도 있다. \lim_{n \rightarrow \infty} \left( \sup_{-1 \leq x \leq 1} | f(x) -P_n(x)| \right) = \infty. 이는 등간격 점에서 고차 다항식 보간이 문제가 될 수 있음을 보여준다.
## 이유
룽게 현상은 이 문제의 두 가지 속성에서 비롯된다. * 이 특정 함수의 n차 미분 계수의 크기는 n이 증가함에 따라 빠르게 증가한다. * 점들 사이의 등간격은 n이 증가함에 따라 빠르게 증가하는 르베그 상수를 초래한다. 두 속성이 결합하여 진동의 크기를 증가시키기 때문에 이 현상은 그래픽적으로 명확하다. 생성함수 (수학)와 n차 보간 다항식 간의 오차는 다음과 같이 주어진다. f(x) - P_n(x) = \frac{f^{(n + 1)}(\xi)}{(n + 1)!} \prod_{i=0}^{n} (x - x_i) . (−1, 1)에 있는 어떤 \xi에 대해. 따라서, \max_{-1 \leq x \leq 1} |f(x) - P_n(x)| \leq \max_{-1 \leq x \leq 1} \frac{\left|f^{(n + 1)}(x)\right|}{(n + 1)!} \max_{-1 \leq x \leq 1} \prod_{i=0}^n |x - x_i|. 노달 함수 w_n(x)를 다음과 같이 표기하자. w_n(x) = (x - x_0)(x - x_1)\cdots(x - x_n) 그리고 W_n를 w_n 함수의 크기의 최댓값이라고 하자. W_n=\max_{-1 \leq x \leq 1} |w_n(x)|. 등간격 노드에서 다음과 같다는 것을 증명하는 것은 기본적인 일이다. W_n \leq n!h^{n+1} 여기서 h=2/n는 스텝 크기이다. 더욱이, f의 (n+1)차 미분 계수가 유계라고 가정하자. 즉, \max_{-1 \leq x \leq 1} |f^{(n+1)}(x)| \leq M_{n+1}. 따라서, \max_{-1 \leq x \leq 1} |f(x) - P_{n}(x)| \leq M_{n+1} \frac{h^{n+1{(n+1)}. 그러나 룽게 함수의 (n+1)차 미분 계수의 크기는 n이 증가할 때 증가한다. 그 결과, n이 무한대로 갈 때 결과적인 상한은 무한대로 발산한다. 룽게 현상을 설명하는 데 자주 사용되지만, 오차의 상한이 무한대로 간다는 사실이 반드시 오차 자체도 n과 함께 발산한다는 것을 의미하지는 않는다.
# 완화책

## 보간점 변경
진동은 구간의 가장자리, 특히 (구간 [-1,1]에서) 다음 공식으로 주어진 점근 밀도를 가진 노드를 사용하여 최소화할 수 있다.citeseerx=10.1.1.15.5097 \frac{1}{\sqrt{1-x^2. 이러한 노드 집합의 표준 예시는 체비쇼프 노드이며, 이를 사용하면 룽게 함수를 근사하는 최대 오차가 다항식 차수가 증가함에 따라 감소하는 것이 보장된다.
## 리샘플링 없는 S-룽게 알고리즘
잘 작동하는 노드 집합에서 리샘플링이 불가능하여 등간격 샘플을 사용해야 하는 경우 S-룽게 알고리즘을 고려할 수 있다. doi-access = free 이 접근 방식에서는 원래 노드 집합을 체비쇼프 노드 집합에 매핑하여 안정적인 다항식 재구성을 제공한다. 이 방법의 특이점은 매핑된 노드(가짜 노드라고도 함)에서 리샘플링할 필요가 없다는 것이다.
## 조각별 다항식 사용
조각별 다항식인 스플라인 곡선을 사용하면 이 문제를 피할 수 있다. 보간 오차를 줄이려고 할 때 사용되는 다항식의 차수를 높이는 대신 스플라인을 구성하는 데 사용되는 다항식 조각의 수를 늘릴 수 있다.
## 제약된 최소화
또한 더 높은 차수의 다항식(예를 들어, n개의 점을 사용하여 n + 1이 아닌 N = n^2 차수의 다항식을 사용)을 맞추고, 첫 번째 (또는 두 번째) 미분 계수의 L^2 노름이 최소인 보간 다항식을 맞출 수 있다. 유사한 접근 방식은 다항식의 m차 미분 계수와 m차 미분 계수의 평균값 사이의 L^p 거리의 제약된 버전을 최소화하는 것이다. 명시적으로 다음을 최소화한다. V_p = \int_a^b \left|\frac{\mathrm{d}^m P_N(x)}{\mathrm{d} x^m} - \frac{1}{b-a} \int_a^b \frac{\mathrm{d}^m P_N(z)}{\mathrm{d} z^m} \mathrm{d}z\right|^p \mathrm{d} x - \sum_{i=1}^n \lambda_i \, \left(P_N(x_i) - f(x_i)\right), 여기서 N \ge n - 1이고 m < N 이며, 다항식 계수와 라그랑주 승수 \lambda_i에 대해이다. N = n - 1일 때, 라그랑주 승수에 의해 생성된 제약 방정식은 P_N(x)를 모든 n개의 점을 통과하는 최소 다항식으로 축소한다. 반대쪽 끝에서 \lim_{N \to \infty} P_N(x)는 조각별 다항식 근사와 매우 유사한 형태에 접근할 것이다. 특히 m=1일 때 \lim_{N \to \infty} P_N(x)는 선형 조각별 다항식, 즉 보간점을 직선으로 연결하는 것에 접근한다. V_p를 최소화하는 과정에서 p가 하는 역할은 평균값에서 벗어나는 변동의 크기 중요도를 제어하는 것이다. p가 클수록 작은 변동에 비해 큰 변동이 더 많이 불이익을 받는다. 유클리드 노름, p=2의 가장 큰 장점은 해석적 해를 허용하고 V_p가 단일 최소값만 갖는다는 것을 보장한다는 것이다. p\neq 2일 때는 V_p에 여러 최소값이 있을 수 있으므로, 발견된 특정 최소값이 국소 최소값이 아닌 전역 최소값이 되도록 보장하기 어렵다.
## 최소제곱법 피팅
다항식 피팅 또 다른 방법은 최소제곱법을 사용하여 낮은 차수의 다항식을 피팅하는 것이다. 일반적으로 m개의 등간격 점을 사용할 때, N < 2\sqrt{m}이면 최소제곱 근사 P_N(x)는 잘 조건화된다.url=https://archive.org/details/numericalmethods00dahl/page/101
## 베른슈타인 다항식
베른슈타인 다항식을 사용하면 닫힌 구간에서 모든 연속 함수를 균등하게 근사할 수 있지만, 이 방법은 계산 비용이 상당히 많이 든다.
## 외부 가짜 제약 보간법
이 방법은 보간 구간의 각 면의 끝점 근처에 외부적으로 배치된 노드에 1=P″(x) = 0 유형의 제약 조건을 최적으로 쌓는 것을 제안하는데, 여기서 P"(x)는 보간 다항식의 2차 미분 계수이다. 이러한 제약 조건을 외부 가짜 제약 조건이라고 부르는데, 이는 보간 구간에 속하지 않고 룽게 함수의 동작과 일치하지 않기 때문이다. 이 방법은 룽게 현상을 완화하는 데 조각별 다항식(스플라인)보다 더 나은 보간 성능을 보여주었다.url = https://cdn.ima.org.uk/wp/wp-content/uploads/2017/03/Belanger-paper.pdf
# 근사 이론과 관련된 진술
근사 이론 미리 정의된 각 보간 노드 표에는 해당 노드에 대한 보간 다항식의 시퀀스가 발산하는 연속 함수가 있다.url = https://www.ams.org/bookstore-getitem/item=gsm-101 모든 연속 함수에는 보간 과정이 수렴하는 노드 표가 있다. 체비쇼프 보간(즉, 체비쇼프 노드에서의)은 모든 절대 연속 함수에 대해 균등하게 수렴한다.