離散的な世界に登場！差分系テイラー展開！(1)

みなさんご無沙汰しております。ラスクです。

連日うだるような暑さですが、どうぞ体調などにはお気をつけください。

さて、私事ですが先日大学の長期休暇に入りました。
もちろん休みといえども自分の勉強や研究の手を抜くわけにはいきませんが、普段よりは時間にゆとりができるので、このブログの更新ペースも一時的に上げていきたいと思っております。暑さに負けないよう尽力いたしますので、どうかお付き合いのほどよろしくお願いいたします！

では、本題に入りましょう。
今回のテーマは以前の記事で少し予告しました「差分系テイラー展開」です！！
予告してから、ずいぶんと時間がたってしまい申し訳ありません。

以前の記事では
「べき乗和の公式を差分という方法を用いて考察する」
という事をやりました。
その際、べき乗和の代わりに下降階乗冪の和というのを考えると以下のようなとてもきれいな公式が成り立つのでした。

\begin{align}
\sum_{k=1}^{n-1} k^{\underline{m}}=\frac{1}{m+1}n^{\underline{m+1}}\ (m\ge1)
\end{align}

詳しく知りたい方は是非、こちらをご覧ください。

mathforeveryone.hatenablog.com

そして今回は、「差分」という操作を軸にしてもう少し異なる内容、具体的には数値計算で用いられる「ニュートンの補間法」というものをご紹介します。

少し長くなりそうでしたので、全2回に分けてご説明しようと思います。
なので本記事では、どのような問題を考えるのかという導入と準備のための定義をいくつかしていきます。
そして次回の記事でニュートンの補間法の内容やその例をご紹介したいと思っております。

あまり前置きが長くなってもいけませんので、さっそく始めていきましょう。

補間法

今回考えるのは以下のような問題です。

与えられた個の点
\begin{align}
(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n) \end{align}
(ただしかつならば)
をすべて通るような次以下の多項式関数を求める。

つまり、平面上にそれぞれ座標が異なる個の点が与えられていて、それらをすべて通る関数を求めようというわけです。これの意味について解説しましょう。

まず具体的な形がよくわからない関数が一つあったとします。このとき、まずその関数に個の値を入れてみてそのデータを集めます。これが上でいう個の点に当たるものです。科学的にはこれは実験をしてデータを集めていることに当たります。そしてその個のデータに見合うような多項式を見つけ、それによって元の関数を近似しようというわけです。
この操作は得られた個の飛び飛びなデータから関数全体の形を近似しよう、つまり”間を埋めよう”としていることに他ならないので数値計算の分野では「補間法」と呼ばれ、得られた多項式のことを補間多項式といいます*1。

例を見てみましょう。

例１(の場合について)
のときは与えられる点は2点ですから、これらを通る多項式関数としては1次関数
\begin{align}
y=\frac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0
\end{align}
が取れます。正確に言えばのときは定数関数(0次式)になってしまいますが、どちらにせよ上式の形で表現できています。

例2(の場合について)
次にのときは与えられている点は3点ですから2次(以下)の多項式ですべての点を通るものが存在します。その関数を
\begin{align}
y=a+bx+cx^2\ (a,b,c\in\mathbb{R})
\end{align}
とおいて各係数を求めてみましょう。この多項式が上の3点を通るという条件を素直に書き下せば
\begin{align}
\left\{ \begin{array}{l} y_0=a+bx_0+cx_0^2 \\ y_1=a+bx_1+cx_1^2 \\y_2=a+bx_2+cx_2^2 \end{array}\right. \tag{1}
\end{align}
となり、これを行列を使って書けば、
\begin{align}
\left(
\begin{array}{ccc}
1 & x_0 & x_0^2 \\
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2
\end{array}
\right)\left(
\begin{array}{ccc}
a\\
b\\
c
\end{array}
\right)
=\left(\begin{array}{ccc}
y_0 \\ y_1 \\ y_2
\end{array}
\right)
\end{align}
となります。このとき左辺の行列はヴァンデルモンド行列と呼ばれていて、その行列式は以下のような形になることが知られています。
\begin{align}
\mathrm{det}\left(
\begin{array}{ccc}
1 & x_0 & x_0^2 \\
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2
\end{array}
\right)=(x_1-x_0)(x_2-x_0)(x_2-x_1)
\end{align}
今、はそれぞれ異なることから上の行列式はではありません。
したがってヴァンデルモンド行列は逆行列を持ち連立方程式(1)はただ一つの解を持つことがわかります。
このようにしてが求まり、3点を通る2次(以下の)多項式を求めることが出来るというわけです。

一般のの場合でもそれぞれの式を次関数の式に代入して連立方程式を解いて…という風に計算すれば原理的には、求めたい関数を得ることが出来ます。しかしこの方法には二つ問題点があります。
一つ目は皆さん、お気づきかもしれませんがこの「連立方程式を解く」という操作がが大きくなるにつれてどんどん大変になっていきます*2。この方法を解決する手段として「ラグランジュの補間法」というものが考えられますが、これについてはまた次の機会にご紹介することにします。
二つ目はもっと実用的な問題点です。上のような素朴なやり方（もしくはラグランジュの補完法）で個のデータを用いて補間多項式を計算したあと、もう一つ別のデータを追加し補間多項式を修正しようと思うと、計算を最初からやり直さなければならないのです。もちろん今のようにコンピュータが発展していればそこまで大きな問題ではないのかもしれませんが、もっと前の時代、それこそニュートンやライプニッツたちが活躍していた時代であればこれは大問題です。
そこでそれをうまく解決したのがまさに「ニュートンの補間法」であります。

そこで以下では、それを扱うための準備をしていきます。

差分と差分商

差分

「ニュートンの補間法」を説明するために、前の記事で定義した差分を一般化しておきましょう。
引き続き関数から個の点(データ)
\begin{align}
(x_0,f(x_0)),(x_1,f(x_1)),\ldots,(x_n,f(x_n))
\end{align}
が与えられているとして、差分を次のように定義します。

定義（差分）
における(前進)差分を
\begin{align}
\Delta f (x_i):=f(x_{i+1})-f(x_i)\ (i=0,1,\ldots,n-1)
\end{align}
と定義する。また高階の差分を
\begin{align}
\Delta^k f(x_i):=\Delta(\Delta^{k-{}1} f(x_i))\ (i=0,1,\ldots,n-k)
\end{align}
と再帰的に定義する。ただしはに線形に作用するとする。

何を言っているかわかりにくいかもしれないので、少し説明を加えます。
まず、前半で言っていることはよいでしょう。ある点における値とその次の点での値の差をとっているだけです。
そして後半についてですが、再帰的に定義すると書いた通り、これは小さいから順番に高階の差分を定めていくことになります。

実際にやってみましょう。

まず、二階の差分について定義により
\begin{align}
\Delta^2 f(x_i)&=\Delta(\Delta f(x_i)) \\
&=\Delta(f(x_{i+1})-f(x_i)) \\
&=\Delta f(x_{i+1})-\Delta f(x_i)\\
&=(f(x_{i+2})-f(x_{i+1}))-(f(x_{i+1})-f(x_i))\\
&=f(x_{i+2})-2f(x_{i+1})+f(x_i)
\end{align}
となります。途中でを二つに分けたところでの線形性を使っています*3。
三階差分についても同様の計算をすることで
\begin{align}
\Delta^3 f(x_i)=f(x_{i+3})-3f(x_{i+2})+3f(x_{i+1})-f(x_i)
\end{align}
をえます。これは演習問題とします！！

このように順番に高階の差分を定めていくわけです。
ここで、この操作を図にまとめると次のようになります。

\begin{align}
\begin{array}{ccccccccc}
f(x_0)&\Delta f(x_0)&\Delta^2 f(x_0)&\Delta^3 f(x_0)\\
\\
f(x_0)&{}&{}&{}\\
{}&f(x_1)-f(x_0)&{}&{}\\
f(x_1)&{}&f(x_2)-2f(x_1)+f(x_0)&{}\\
{}&f(x_2)-f(x_1)&{}&f(x_3)-3(x_2)+3f(x_1)-f(x_0)\\
f(x_2)&{}&f(x_3)-2f(x_2)+f(x_1)&\\
{}&f(x_3)-f(x_2)&{}&\\
f(x_3)&{}&&{}\\
\end{array}
\end{align}

こうしてみると何をしているかが非常にわかりやすいですね。ただ左の方から順番に上下隣同士の差をとって表を埋めていっているだけです。

では次に差分商を定義しましょう！

差分商

定義(差分商)
まずにおける０階の差分商を単に
\begin{align}
f[x_i]:=f(x_i)
\end{align}
とする。次ににおける1階の差分商を
\begin{align}
f[x_i,x_{i+1}]:=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}
\end{align}
とする。さらに一般ににおける階の差分商を
\begin{align}
f[x_i,\ldots,x_{i+k}]:=\frac{f[x_{i+1},\ldots,x_{i+k}]-f[x_i,\ldots,x_{i+k-{}1}]}{x_{i+k}-x_i}
\end{align}
で再帰的に定義する。

はい、こんな感じです。定義の仕方としては差分と同じ再帰的な定義をしているので詳しい説明は省きますが、要はこれも小さいから順番に高階の差分商が定義されていく仕組みになっています。
式の形を見てお分かりの通り、これは連続的な世界における微分を意識したものです。ただ、今は離散的な世界（というか離散的な値しかわかっていない状態）なので、座標の変化率をに飛ばすという極限操作が取れず、分母にはギャップが残ったままになっています。

差分の時と同様、上の再帰的な定義を図に書き表してみると次のようになります。

\begin{align}
\begin{array}{ccccccccccc}
f[x_0]&f[x_0,x_{1}]&f[x_0,x_{1},x_{2}]&f[x_0,x_{1},x_{2},x_{3}]\\
\\
f[x_0]&{}&{}&{}\\
{}&\frac{f[x_1]-f[x_0]}{x_1-x_0}&{}&{}\\
f[x_1]&{}&\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}&\\
{}&\frac{f[x_2]-f[x_1]}{x_2-x_1}&{}&\frac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0}\\
f[x_2]&{}&\frac{f[x_2,x_3]-f[x_1,x_2]}{x_3-x_1}&\\
{}&\frac{f[x_3]-f[x_2]}{x_3-x_2}&{}&\\
f[x_3]&{}&&{}\\
\end{array}
\end{align}

ここで、]などはという値を使って直接書き下すこともできますが、それをすると表が大変なことになるのでやめました。

この図はのちのち重要になってくるので是非覚えておいてください。この図の特徴から先ほど言った「新いデータを付け加えた時に初めから計算をし直す必要がない」という事が従います。

最後に少し具体的な値で計算をしてみましょう。

例３４点が与えられているとしましょう。差分と差分商をそれぞれ計算すると

\begin{align}
\begin{array}{ccccccccc}
f(x_0)&\Delta f(x_0)&\Delta^2 f(x_0)&\Delta^3 f(x_0)\\
\\
4&{}&{}&{}\\
{}&1-4=-3&{}&{}\\
1&{}&1-(-3)=4&{}\\
{}&2-1=1&{}&3-4=-1\\
2&{}&4-1=3&\\
{}&6-2=4&{}&\\
6&{}&&{}\\
\end{array}
\end{align}

\begin{align}
\begin{array}{ccccccccccc}
f[x_0]&f[x_0,x_{1}]&f[x_0,x_{1},x_{2}]&f[x_0,x_{1},x_{2},x_{3}]\\
\\
4&{}&{}&{}\\
{}&\frac{1-4}{0-(-2)}=-\frac{3}{2}&{}&{}\\
1&{}&\frac{1-(-\frac{3}{2})}{1-(-2)}=\frac{5}{6}&\\
{}&\frac{2-1}{1-0}=1&{}&\frac{\frac{1}{3}-\frac{5}{6}}{3-(-2)}=-\frac{1}{15}\\
2&{}&\frac{2-1}{3-0}=\frac{1}{3}&\\
{}&\frac{6-2}{3-1}=2&{}&\\
6&{}&&{}\\
\end{array}
\end{align}

となります。どのように計算すればよいかお分かりいただけたでしょうか？

まとめ

ということで、今回はここまでにしたいと思います。
この記事は準備のためのものなので、まず補間法という方法の問題意識を設定し、高階の差分や差分商を定義していきました。
次回からこれらの道具を使ってやりたかったことに入っていきますので、楽しみにお待ちください！！

では最後までご覧いただきありがとうございました！！

コメントはどんなものでも絶賛受け付け中です！
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします！

それではまた次回お会いいたしましょう！

*1:多項式で近似しようとするのが常に良いとは限りませんし、そうでない補間法も多く存在しますが今回は多項式の場合に限定して話をします。

*2:4次くらいまでなら高校入試の連立方程式とかになりそうですね(笑)

*3:線形性とは和をバラバラにできて、定数倍を外に出せることです