ルンゲ現象

数値解析の数学の分野において、ルンゲ現象（ドイツ語: [ˈʁʊŋə] ）は、等間隔の補間点の集合に対して高次数の多項式による多項式補間を使用するときに発生する、区間の端における振動の問題である。これは、カール・ダーヴィト・トルメ・ルンゲ(1901) が、多項式補間を使用して特定の関数を近似する際の誤差の挙動を調査しているときに発見された。^[1]この発見は、次数が高くなっても必ずしも精度が向上するわけではないことを示している。この現象は、フーリエ級数近似における ギブス現象 に似ている。

ワイエルシュトラスの近似定理は、区間[ a , b ]で定義されたすべての連続関数 f ( x ) に対して、 n =0, 1, 2, ...に対して、各次数が最大でnの多項式関数P _n ( x ) の集合が存在し、nが無限大に近づくにつれてf ( x ) を[ a , b ]にわたって一様収束で近似する、つまり、

${\displaystyle \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 ) のセットは、一様収束の特性を持つことが保証されていません。定理は、多項式関数のセットが存在することを述べているだけで、それを見つける一般的な方法は提供していません。

このようにして生成されたPn ( x )は、 nが増加するにつれてf ( x )から実際に発散する可能性があります_。これは通常、補間点の端近くで拡大する振動パターンで発生します。この現象の発見はルンゲによるものです。^[2]

ルンゲ関数を考える

${\displaystyle f(x)={\frac {1}{1+25x^{2}}}\,}$

(アグネシの魔女の縮小版)。ルンゲは、この関数を-1 と 1 の間の等距離の点x _iで補間すると、次のようになることを発見しました。

${\displaystyle x_{i}={\frac {2i}{n}}-1,\quad i\in \left\{0,1,\dots ,n\right\}}$

次数 ≤  nの多項式 P _n ( x )では、結果として得られる補間は区間の終わりに向かって、つまり -1 と 1 に近づくにつれて振動します。多項式の次数が増加すると、補間誤差が（無制限に）増加することが証明されています。

${\displaystyle \lim _{n\rightarrow \infty }\left(\sup _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\right)=\infty .}$

これは、等距離の点での高次多項式補間が問題になる可能性があることを示しています。

ルンゲ現象は、この問題の 2 つの特性の結果です。

• この特定の関数のn次導関数の大きさは、 n が増加すると急速に大きくなります。
• 点間の等距離により、n が増加するとルベーグ定数が急速に増加します。

この現象は、両方の特性が組み合わさって振動の振幅が増大するため、図で見ると明らかです。

生成関数とn次の補間多項式の間の誤差は次のように表される。

${\displaystyle f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})}$

（−1, 1）に 属するものに対して。したがって、${\displaystyle \xi }$

${\displaystyle \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}|}$。

節点関数 で表す${\displaystyle w_{n}(x)}$

${\displaystyle w_{n}(x)=(x-x_{0})(x-x_{1})\cdots (x-x_{n})}$

そして関数の大きさの最大値とします。 ${\displaystyle W_{n}}$${\displaystyle w_{n}}$

${\displaystyle W_{n}=\max _{-1\leq x\leq 1}|w_{n}(x)|}$。

等距離のノードで証明するのは基本的である

${\displaystyle W_{n}\leq n!h^{n+1}}$

ステップサイズは どこですか。${\displaystyle h=2/n}$

さらに、の( n +1)次導関数が有界であると仮定する。すなわち 、${\displaystyle f}$

${\displaystyle \max _{-1\leq x\leq 1}|f^{(n+1)}(x)|\leq M_{n+1}}$。

したがって、

${\displaystyle \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq M_{n+1}{\frac {h^{n+1}}{(n+1)}}}$。

しかし、 n が増加すると、ルンゲ関数の ( n +1) 次導関数の大きさは増加します。その結果、 n が無限大に近づくと、結果として得られる上限も無限大に近づきます。

ルンゲ現象を説明するためによく使用されますが、誤差の上限が無限大になるという事実は、もちろん、誤差自体もn とともに発散することを必ずしも意味するものではありません。

振動は、区間の端に向かってより密に分布するノード、具体的には式^{[3]で与えられる漸近密度（区間}[−1, 1]上）を持つノードを使用することで最小限に抑えることができます。このようなノードセットの標準的な例はチェビシェフノードであり、ルンゲ関数を近似する際の最大誤差は多項式次数が増加するにつれて減少することが保証されています。 ${\displaystyle {\frac {1}{\sqrt {1-x^{2}}}}}$

適切に動作するノードセットの再サンプリングが実行不可能なため等距離サンプルを使用する必要がある場合は、S-ルンゲアルゴリズムを検討できます。^[4]このアプローチでは、元のノードセットがチェビシェフノードのセットにマッピングされ、安定した多項式再構成が提供されます。この方法の特徴は、マッピングされたノード（偽のノードとも呼ばれます）での再サンプリングが不要なことです。この手順のPython実装は、こちらで確認できます。

この問題は、区分多項式であるスプライン曲線を使用することで回避できます。補間誤差を減らすには、使用する多項式の次数を増やすのではなく、スプラインの構築に使用する多項式の部分の数を増やすことができます。

また、より高次の多項式を近似することもできます（たとえば、点 では、 の代わりに次数の多項式を使用します）。また、1 次（または 2 次）導関数のノルムが最小である補間多項式を近似することもできます。 ${\displaystyle n}$${\displaystyle N=n^{2}}$${\displaystyle n+1}$${\displaystyle L^{2}}$

同様のアプローチは、多項式の- 次導関数と - 次導関数の平均値との間の距離の制約バージョンを最小化することです。明示的に、最小化するには ${\displaystyle L^{p}}$${\displaystyle m}$${\displaystyle m}$

${\displaystyle 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),}$

ここで、およびは、多項式係数およびラグランジュ乗数に関して、です。 のとき、ラグランジュ乗数によって生成される制約方程式は、すべての点を通過する最小の多項式に簡約されます。 の反対の端では、は区分多項式近似に非常によく似た形に近づきます。特に のとき、は線形区分多項式、つまり補間点を直線で結ぶものに近づきます。 ${\displaystyle N\geq n-1}$${\displaystyle m<N}$${\displaystyle \lambda _{i}}$${\displaystyle N=n-1}$${\displaystyle P_{N}(x)}$${\displaystyle n}$${\displaystyle \lim _{N\to \infty }P_{N}(x)}$${\displaystyle m=1}$${\displaystyle \lim _{N\to \infty }P_{N}(x)}$

を最小化するプロセスでが果たす役割は、平均値からの変動の大きさの重要性を制御することです。 が大きいほど、小さな変動に比べて大きな変動がペナルティを受けます。 ユークリッドノルム の最大の利点は、解析解が可能であり、 が単一の最小値のみを持つことを保証することです。に複数の最小値が存在する可能性がある場合、見つかった特定の最小値が局所的な最小値ではなく 全体的な最小値になることを保証することは困難です。${\displaystyle p}$${\displaystyle V_{p}}$${\displaystyle p}$${\displaystyle p=2}$${\displaystyle V_{p}}$${\displaystyle p\neq 2}$${\displaystyle V_{p}}$

もう一つの方法は、最小二乗法を用いて低次の多項式を近似する方法である。一般に、等距離の点を使用する場合、最小二乗近似は条件が整う。^[5]${\displaystyle m}$${\displaystyle N<2{\sqrt {m}}}$${\displaystyle P_{N}(x)}$

バーンスタイン多項式を使用すると、閉区間内のすべての連続関数を均一に近似することができますが、この方法は計算コストがかなり高くなります。^[要出典]

この方法は、補間区間の各辺の端点付近の外部に配置されたノードに、 P ″( x ) = 0型の制約の密な分布を最適に積み重ねることを提案する。ここで、P"(x) は補間多項式の 2 次導関数である。これらの制約は補間区間に属さず、ルンゲ関数の動作と一致しないため、外部偽制約と呼ばれる。この方法は、ルンゲ現象を軽減するために、区分多項式 (スプライン) よりも優れた補間性能を持つことが実証されている。^[6]

定義済みの補間ノードテーブルごとに、それらのノード上の補間多項式のシーケンスが発散する連続関数が存在します。^[7]すべての連続関数には、補間プロセスが収束するノードテーブルがあります。^[要出典]チェビシェフ補間（つまり、チェビシェフノード上）は、すべての絶対連続関数に対して一様に収束します。

• チェビシェフノード
• 正弦波基底関数のギブス現象と比較する
• オッカムの剃刀はより単純なモデルを主張する
• 過剰適合はモデルの過度の複雑さによって引き起こされる可能性がある
• シュヴァルツランタン、収束の失敗のもう一つの例
• ストーン・ワイエルシュトラスの定理
• テイラー級数
• ウィルキンソンの多項式