線形補間
線形補間（せんけいほかん、英: Linear interpolation, lerp）は、多項式補間の特殊なケースで、線形多項式（一次式）を用いた回帰分析の手法である。1次補間としても知られている。
なお、3つ以上のデータに対し線形補間といった場合、1つの線型近似によるフィッティングではなく、区分線形関数を使った区分線形補間（1次スプライン補間、いわゆる折れ線グラフ）のことである。
線形補間は数学の世界（特に数値解析）やコンピュータグラフィックスを含む多くの分野で非常によく使われている。補間の非常に単純な形式であり、これより単純なのは最近傍補間（0次補間）しかない。
線形補間を行う方法
座標(x0, y0)と(x1, y1)があるとする。ここで、 [x0, x1]の間にあるxが与えられたときに、この線上にある点を得たいとする。図をよく見ると次のことがわかる。
- [math]\frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0}. \,\![/math]
両辺と同じ値である値を[math]\alpha[/math]と置こう。これは補間係数である。これは、x0からx1までの距離とxに当たるまで動かした点までの距離の比である。xに入る値が分かれば、次の式によって[math]\alpha[/math]が得られる。
- [math]\alpha = \frac{x-x_0}{x_1-x_0}. \,\![/math]
また、次の式も成り立つ。
- [math]\alpha = \frac{y-y_0}{y_1-y_0} \,\![/math]
この式を代数的に操作すると次のどちらかの式が得られる。
- [math]y = (1 - \alpha) y_0 + \alpha y_1 \,\![/math]
- [math]y = y_0 + \alpha (y_1-y_0)\,\![/math]
この式から、[math]\alpha[/math]の値を計算すると直接yの値を得られることが分かる。この式はxがx0とx1の間になくても成立する。それ故に、[math]\alpha[/math]は0から1の間にないかもしれないが、その場合通常は比率とは呼ばれない。その場合は線形外挿法と呼ばれる。外挿を参照のこと。
yが既知でxを知りたい場合、xとyを交換してまったく同じ手続きをすればいい。これはもっと複雑な補間アルゴリズムにはない特徴である。
誤差評価
線形補間はしばしば、ある関数f上の他の2点の値を使って、その関数上のある値を近似するのに使われる。この近似による誤差は次のように定義される。
- [math]R_T = f(x) - p(x) \,\![/math]
ここで、pは線形補間多項式であり、以下で定義される。
- [math]p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0). \,\![/math]
エラーは次に示す式の範囲内にある。この式はもし、関数fが2次の連続する導関数を持つならば、ロルの定理を使えば証明できる。
- [math]|R_T| \leq \frac{(x_1-x_0)^2}{8} \max_{x_0 \leq x \leq x_1} |f''(x)|. \,\![/math]
見れば分かるが、与えられた関数上の2点間の近似は、近似された関数の2次導関数から計算された値よりも悪くなる。このことは、カーブを描いた関数は単純な線形補間を使った近似を行うと悪い値が出ることからも、直感的に正しいことが分かる。
特徴
計算量が非常に少ない。一般にスプライン補間は連立方程式を解くが、1次では例外的にその必要がなく、計算量は [math]O(n)[/math] にすぎない。
連続だが、区分的にしか滑らかでなく、導関数および高次導関数は一般に不連続である（一般に、n 次補間は n - 1 次導関数まで連続である）。連続性により、元データにない値が現れる（ただしこれは、最近傍補間や特殊なアルゴリズム以外に共通の特徴である）。また導関数が不連続であるので、元データの傾きが大きく変化する付近で、高調波が発生してしまう。
単調性が保持される。つまり、元データが単調増加だと補間結果も単調増加である（単調減少でも同じ）。このため、オーバーシュート（元データの傾きが大きく増える直前に補間結果が少し減ること、またはその逆）がない。
応用分野
線形補間はしばしば表の穴を埋めるのに使われる。もし、ある国の1970年、1980年、1990年、2000年の人口を表に持っていて、1994年の人口を見積もりたいとする。線形補間はこういうことを行うのには簡単な方法である。
2値間の線形補間のもっとも基本的な操作は、コンピュータグラフィックスでよく使われる。ブレゼンハムのアルゴリズム (Bresenham's algorithm) は、2点間を結ぶ線を段々に補間して描画する。
1次補間はたいていのグラフィックスプロセッサ (GPU) にハードウェアレベルで実装されている。この処理はより複雑な操作を行うための処理の一部として使われている。たとえば、バイリニア補間は2つの1次補間を使ってできる。画像は多くの場合、線形補間で十分な品質が得られるが、連続という性質上、インデックスカラー画像には使いにくい。リアルタイム処理系では、テクスチャフィルタリングに使われる補間モードにバイリニア補間がよく選ばれる。
この処理はコストが安いので、非常に多くのテーブルエントリを持たずに、滑らかな関数用に素早く参照できる正確なルックアップテーブルを実装するのもよい方法である。
歴史
線形補間は古くは表中の空白を埋めるのに使われていた。またしばしば天文学的なデータにも使われていた。この手法はセレウコス朝（紀元前3世紀終）やギリシャの天文学者や数学者であるヒッパルコス（紀元前2世紀）などによって使われていたと考えられている。線形補間の記述はプトレマイオス（2世紀）のアルマゲストに見ることができる。
拡張
要求される状況によっては、線形補間はしばしば十分に正確でないことがある。その場合は、（2次以上、通常3次の）多項式補間もしくはスプライン補間で置き換えることができる。
線形補間はまた、2変数の関数のためのバイリニア補間にも拡張できる。バイリニア補間はしばしば乱暴なアンチエイリアスフィルタとしても用いられる。似たものとして、トライリニア補間があるが、これは3変数の関数を補間するために使われる。線形補間の他の拡張としては、三角形や正四面体のメッシュのような他の網の目構造に適用される。
参照
- E. Meijering (2002). A Chronology of Interpolation. From Ancient Astronomy to Modern Signal and Image Processing. Proceedings of the IEEE 9 (3), 319–342.
関連項目
- 最近傍補間
- バイリニア補間 (双線形補間)
- トライリニア補間
- バイキュービック補間 (双三次補間)
- 曲線あてはめ