「プログラミングと数値計算」カテゴリーアーカイブ

一般固有値問題の対角化のプログラム(実対称行列、Fortran90)

intel Math Karnel Library (以降MKL)を用いて、一般固有値問題の対角化を行います。
特に、登場する行列が実対称行列である場合について考えます。

PDF版はこちらをどうぞ。
https://slpr.sakura.ne.jp/qp/supplement_data/diagonalize/GeneralizedEVP_symmetrixMatrix.pdf

概要


本稿で取り扱う一般固有値問題は、下記の固有値問題です。
\(\displaystyle
A\mathbf{x}=\lambda B \mathbf{x}
\)

ここで、\(A\)は\(N\times N\)の実対称行列、\(B\)は\(N\times N\)の実対称正定値行列(行列式がゼロではない)、\(\lambda, \mathbf{x}\)はこの問題の解であり、固有値、固有ベクトルを意味します。

MKLでは、下記の順で一般固有値問題の固有値・固有ベクトルを得ます。

  1. 一般固有値問題を標準形式の固有値問題に縮退(変形)
  2. 標準形式の固有値問題を解く

ここでいう標準形式の固有値問題とは、下記の形を持つ固有値問題です。
\(\displaystyle
A\mathbf{x}=\lambda \mathbf{x}
\)

ここで、\(A\)は\(N\times N\)の実対称行列です。

一般固有値問題から標準形式の固有値問題への式変形は、単純には両辺に左から\(B\)の逆行列\(B^{-1}\)を書ければ良いです。
ただし対称行列の逆行列は対称行列となりますが、この方法では\(B^{-1}A\)の計算を実施すると対称行列では無くなってしまうので、あまり良い方法ではありません。
また、数値計算においては逆行列をあらわに求めることはあまり意味がなく、内部的には例えばコレスキー因子分解を利用して標準形式の固有値問題に焼き直しています。
詳細は本稿のpdf、または
桂田祐史著, 『一般化固有値問題』http://nalab.mind.meiji.ac.jp/~mk/labo/text/generalized-eigenvalue-problem.pdf
をご参照ください

プログラム


MKLを使用して実対称行列を対象にする場合、?potrf?sygstを用いて、一般固有値問題から標準形式に変形します。

変形後、通常の固有値問題となりますので、?syevdなりで得れば良いです。

下記のプログラムで一般固有値問題を解くことができます。

https://slpr.sakura.ne.jp/qp/supplement_data/diagonalize/main.f90

MKLにリンクして実行すると下記の結果を得ます。

$ ./a.out
-1.1521485211112101
  1 -0.58476768299560977
  1 -0.80775482423872369
  1 1.0000000000000000

-0.33168880188026734
  2 -12.704343950958979
  2 9.0124895755548664
  2 1.0000000000000000

1.2162316891886606
  3 1.2579365740025481
  3 0.69934198729297192
  3 1.0000000000000000
$

信号と窓関数

以下のPDFにまとめました。
https://slpr.sakura.ne.jp/qp/supplement_data/signal/signal.pdf

周期的な信号に含まれるエネルギーは無限となってしまいます。
これは信号が無限続くためであり、意味がある量は時間当たりのエネルギー、すなわちパワーが重要な指標となります。

また、パワーを測定するためには無限の時間測定を実施しなければなりませんが、現実で測定を行う場合、必ず有限の時間で行われます。
そのため、有限の時間で行われた測定結果を無限に続く信号の結果に焼き直す必要があります。

無限の信号を切り出す操作を、信号に窓関数を掛ける、と表現します。
有限の時間の場合、歪められることを意味するため、この両者の関係は正確に対応付けなければなりません。

本稿はこの対応付けについて言及いたします。

また、窓関数の選び方によって本来の信号の歪められ方が変わってきます。何かの特徴が無限の信号を測定した場合に限りなく近くなる窓関数や、別の特徴が近づく窓関数などがあります。

上記のPDF内に示したFortran90によるプログラムは、以下においてあります。
https://slpr.sakura.ne.jp/qp/supplement_data/signal/signal_spectrum.tar.gz

(以下、PDF内の抜粋です。)

振動関数のphase unwrappnig

phase unwrapping


phase unwrappingという処理があります。
これは、振動関数から位相を抽出しよう、ということを実現する処理です。
具体的に問題を書けば、関数
\(\displaystyle
y(x)=\sin(\phi(x))
\)

があり、\(y(x)\)だけが分かっているときに、\(\phi(x)\)を求める、という問題です。
仮定として、\(\phi(x)\)は滑らかな関数であるとします。

逆関数を作用させれば良いということはすぐに思いつきます。つまり、\(\sin\)の逆関数である\(\sin^{-1}\)を作用させればよく、
\(\displaystyle
\begin{align}
\sin^{-1}y(x)&=\sin^{-1}\sin(\phi(x)) \\
&=\phi(x)
\end{align}
\)

を期待します。

しかしながら、ここで問題が生じます。
それは、\(\sin^{-1}(x)\)の値域は\([-\pi/2,\pi/2]\)ですので、この範囲に押し込まれてしまうということです。

もし\(\phi(x)\)が\([-\pi/2,\pi/2]\)の範囲以外にはない、という仮定があるならば話は別ですが、
通常は\(\phi(x)=[-\infty, \infty]\)ですので、\(\sin^{-1}(x)\)を作用させた場合、値域の端で位相に不連続が生じることになります。
つまり、ただ単に\(\sin^{-1}\)を作用させただけでは、\(\phi(x)\)が滑らかである、という条件に矛盾することになります。

しかしながら、\(\sin^{-1}\sin(\phi(x))\)と\(\phi(x)\)は全く無関係なもの、というわけではありません。
\(
\begin{align}
\sin(\theta)&=-\sin(-\theta) \\
\sin(\theta)&=\sin(\theta+2n\pi), ~~~(n=0,\pm 1,\pm 2,\cdots)
\end{align}
\)

の性質があるため、\(\sin^{-1}\cos(\phi(x))\)の角度を負に取ったり、適当に\(2n\pi\)を足したり引いたりすれば、どこかに元の\(\phi(x)\)と一致する組み合わせが見つかるはずです。

このように、関数の自由度を一つに決めて、制限された関数の値域を元に戻すことをunwrappingと言います。
位相の場合は特にphase unwrappingと呼ばれます。

先にどのようなことを考えるか図示してみます。
入力は下の図の黒線で、ここから赤線を復元できるか?という問題です。

どのように\(\phi(x)\)と一致する組み合わせ見つけるかは様々な方法が考えられますが、愚直な方法で実装しましょう。
ここでは一例として、\(\phi(x)\)は滑らかである場合を考えて、補外によってphase unwrappingを行う方法を実装してみます。

方針


滑らかに接続できたことを考えたとしても、絶対的な位相の量は分からないので、適当な\(x_0\)における位相の値\(\sin^{-1}\sin(\phi(x_0))\)を基準として、その位置から滑らかにつながることを想定します。

以下の仮定の下で考えます。

  • 離散的な\(y(x_n)=\sin^{-1}\sin(\phi(x_n)), (n=1,2,\cdots,N)\)が等間隔で与えられている。
  • 入力\(y(x_n)\)の値域は\([0,\pi]\)または\([-\pi/2,\pi/2]\)
  • \(\phi(x)\)は滑らかであること
  • \(\phi(x)\)が局所的には2次程度の多項式で書けること

まず、基準点より一つ進んだ点の候補(\(\sin(\theta)=-\sin(-\theta), \sin(\theta)=\sin(\theta+2n\pi)\)の関係から考えられるもの)を挙げ、その中から期待されるであろう補外の値に最も近い点がunwrappingされた点だ、と考えます。

unwrapされる候補の点を挙げる


左側の元の関数\(y(x_n)\)から、右のように候補を生成します。候補は、これまでにunwrapされた関数を値の周辺のみを候補とします。

補外と上手くいかない場合


基本的なアイデアは下図左側で、これまでにunwrapされた点を元に次の点を予測し、それに最も近い候補点がunwrapの値とします。この補外によって、\([-\pi/2,\pi/2]\)ないし\([0,\pi]\)から\([-\infty, \infty]\)の領域に拡張できます。

また、異なる候補と接近する境界付近では間違えて予測する可能性があります。それは右のような状況です。
これは補外が正しく行われないことが理由なので、逆向きにも次の点を予測し、その平均を取ることで精度が上がることを期待します。

コード


Fortran90のコードです。

失敗する場合


離散した点と点の間隔が広い場合

本アルゴリズムの場合、どうしても境界付近で曲がる場合、別の領域のものをトレースしてしまう可能性があります。
厳密に傾きがゼロになり、候補が複数ある場合に正解を選び出すのは不可能です。本アルゴリズムの適用を諦めましょう。
しかしながら、元のデータ点を補間なり何かをしてマシにすることはできますので、データ点を増やして再度実行すると成功するかもしれません。

具体的に例を挙げてみます。

関数
\(\displaystyle
\begin{align}
y(x)&=acos(cos(\phi(x))) \\
& phi(x)=3.1cos(2*x)**2+exp(-0.2x)-0.8
\end{align}
\)

を考えます(適当に試していた時に失敗した関数なので、これより単純な関数でも細かく離散化されていなければ失敗するはずです)。

離散化する間隔\(\Delta x\)を\(\Delta x=0.1\)でとり、unwrapすると失敗します。

上図の横軸は離散点のインデックス、縦軸は候補やその他の情報を示しています。\(cos(x)\)の任意性は無視しています。
数値的な解は緑線であり、9,10番目の離散点(\(x=0.9, 1.0\))で失敗しており、本来の解(赤線)とは異なる点を結んでしまっています。

しかしながら、離散化する間隔\(\Delta x\)を\(\Delta x=0.05\)でとり、unwrapすると成功します。

成功させるためには、できるだけ細かい間隔で離散化しましょう。

離散フーリエ変換 -数値計算に向けた解説書-

数値計算を行う方のための離散フーリエ変換に関する解説です。

詳細は以下のPDFをご覧ください。
途中式も含め、できる限り解説したつもりです。

https://slpr.sakura.ne.jp/qp/supplement_data/dft/fourier_transform.pdf

Fortran90を利用したプログラム例も載せています。
PDF内のプログラムは以下からダウンロードできます。

定義通りの離散フーリエ変換のプログラム

main_dft_def.f90

任意区間の離散フーリエ変換プログラム

main_dft_arb.f90

任意区間の離散フーリエ変換を利用した畳み込みプログラム

main_dft_conv.f90

上記のプログラムはIntel MKLを利用しますので、それぞれの環境で合ったコンパイルをして実行してください。

上のPDFの目次は以下の通りです。

  1. まとめ
  2. 連続の場合
    1. フーリエ変換
    2. 畳み込み
  3. 離散の場合
    1. 離散フーリエ変換
    2. 離散畳み込み
  4. プログラム
    1. Intel MKLを利用した離散フーリエ変換
    2. Intel MKLを利用した畳み込み
    3. DFTの計算速度
  5. 付録

Fortran90で構造体を使う

Fortran90で自分で型を定義し、それを使用します。
本稿でいう”型”は、一般には構造体と呼ばれます。
Fortran使用者にとっては”型”という名称が分かりやすいでしょう。

整数型、倍精度型などと同列にあるもの、と考えて差し支えないです。

本稿では基本的なことしか書いていません。

二階偏微分の計算の時でも構造体の考えを使用していますので、もう少し例が欲しい方はこちらもどうぞ。
Hyper-dual numbersによる二階偏微分の計算 -シキノート

概要

簡単な実例



module CEOM_mod
  implicit none
  type Particle
     double precision::m,x,v
  end type Particle
end module CEOM_mod

program main
  use CEOM_mod
  implicit none
  type(Particle)::p1

  p1%m  = 1d0
  p1%x  = 2d0
  p1%v  = 3d0

  write(6,*)p1%m,p1%x,p1%v

  stop
end program main

実行結果

$ ./a.out
   1.0000000000000000        2.0000000000000000        3.0000000000000000
$

説明


上は、粒子p1が質量m, 位置x, 速度vを持つ、ということを想定しています。

そこで、Particleという新しい”型”(複素数型みたいに、実部と虚部という2つの独立な変数を1つの複素数型変数が持つ、みたいな変数の型)を定義しました。
Particle型を持つ変数は、すべてm, x, vを内包するというイメージです。

mainプログラムではparticle型が定義されているモジュールを呼び出すために

    use CEOM_mod

という文を入れ、実際にparticle型の変数p1を定義するために

  type(Particle)::p1

と書いています。変数p1が定義されると自動的にp1が持つm,x,vの固有な値も定義されます。固有の値をいじる場合は

  p1%m  = 1d0

と書いて、変数に%をつけてm,x,vのいずれかを書いて代入します。


配列



module CEOM_mod
  implicit none
  type Particle
     double precision::m,x,v
  end type Particle
end module CEOM_mod

program main
  use CEOM_mod
  implicit none
  integer::i,N
  type(Particle),allocatable::p(:)

  N=5
  allocate(p(1:N))
  do i=1,N
     p(i)%m  = 1d0
     p(i)%x  = dble(i)
     p(i)%v  = 0.1d0*i
  enddo

  do i=1,N
     write(6,*)i,p(i)%m,p(i)%x,p(i)%v
  enddo

  stop
end program main

実行結果

$ ./a.out
                    1   1.0000000000000000        1.0000000000000000       0.10000000000000001<br />
                    2   1.0000000000000000        2.0000000000000000       0.20000000000000001<br />
                    3   1.0000000000000000        3.0000000000000000       0.30000000000000004<br />
                    4   1.0000000000000000        4.0000000000000000       0.40000000000000002<br />
                    5   1.0000000000000000        5.0000000000000000       0.50000000000000000
$

サブルーチンの利用



module CEOM_mod
  implicit none
  type Particle
     double precision::m,x,v
  end type Particle
end module CEOM_mod

subroutine twicemass(N,p)
  use CEOM_mod
  implicit none
  integer,intent(in)::N
  type(Particle),intent(inout)::p(1:N)

  integer::i
 
  do i=1,N
     p(i)%m  = 2 * p(i)%m
  enddo
 
  return
end subroutine twicemass

program main
  use CEOM_mod
  implicit none
  integer::i,N
  type(Particle),allocatable::p(:)

  N=3
  allocate(p(1:N))
  do i=1,N
     p(i)%m  = 1d0
     p(i)%x  = dble(i)
     p(i)%v  = 0.1d0*i
  enddo

  call twicemass(N,p)
 
  do i=1,N
     write(6,*)i,p(i)%m,p(i)%x,p(i)%v
  enddo

  stop
end program main

実行結果

$ ./a.out
                    1   2.0000000000000000        1.0000000000000000       0.10000000000000001<br />
                    2   2.0000000000000000        2.0000000000000000       0.20000000000000001<br />
                    3   2.0000000000000000        3.0000000000000000       0.30000000000000004<br />
$

補足


オブジェクト指向になれている方は、構造体の中身を外部から直接アクセスできる点で褒められた書き方ではないでしょう。
Fortran90にオブジェクト指向の考え方を持ってくるのは、計算速度というFortran90の長所を潰してしまうので、このくらいで良いでしょう。

陰関数の等高線を数値計算で求める

まとめ


関数

を求める問題を考えます。
\(f(x_0, y_0)=0\)を満たす\((x_0, y_0)\)が与えられている場合、\((x_1\equiv x_0+\Delta x, y_1\equiv y_0+\Delta y)\)を求めることを考えていきます。
まず、

の変換を行い、初期値\((x_0, y_0)\)を\((x’_0, y’_0)\)に変換します。
ここで、\(\theta\)は定数で

です。\((x’_0, y’_0)\)を新たな初期値として微分方程式

を解き、\(x_0′\)から微小距離\(h\)だけ発展させた\(x_1’\equiv x_0′ + h\)とその値\(y_1’\equiv y_0′ + \Delta y\)を求めます。
その後、逆変換

を経ることで\(f(x_1,y_1)=0\)を満たす\((x_1,y_1)\)の値を得ることができます。

導出


陰関数

を満たす\((x,y)\)を求めます。ある点\((x_0, y_0)\)において\(f(x_0, y_0)=0\)を満たすことが分かっている場合、
陰関数の全微分より、\((x_0, y_0)\)の近傍で

が満たされています。\(f(x_0,y_0)=0\)であり、\(\Delta x\approx \Delta y \to 0\)ならば、\(O(\Delta^2)\)の項を無視して

が成立する変化のみが許されます。両辺を\(\Delta x\)で割って、\(\Delta x\to 0\)の極限をとれば、

を得ます。すなわち、式(9)を何らかの手段、例えば数値計算で解けば等高線を得ることができます。

発散への対処


さて数値計算によって微分方程式(9)を解いて等高線を描く場合、\(y\)が\(x\)の一価関数になることはほとんどありません。
そのため、式(9)の右辺の分母がゼロになることがあり、微分が発散するため計算を行うことができなくなることがあります。言い換えれば、発散しない範囲しか計算できなくなるということです。
これを回避するためには様々な方法があると思いますが、例えば変数変換を適宜行いながら積分を実行していくことでこの問題を回避することができます。

発散を回避するためのアイデアは以下の通りです。
\(y\)を\(x\)の関数と見たとき、微分が発散するということは、分母がゼロになることを意味しています。
しかし、その点において90°回転させて\(y\)を\(x\)の関数としてみれば微分はゼロに等しいため、問題なく計算を進めることができます。
図示すれば以下の通りになります。

左図は座標を変化せずにそのままの関数ですが、右図のようにある点を計算したいときにその点近くの傾きと等しいように回転した座標から見るようにします。こうすることで発散を回避することができます。

これから変数変換について考えていきます。新たな変数\(x’, y’\)を用いて\(x=x(x’, y’),~y=y(x’, y’)\)(またはその逆関数)と書けているならば、

と書いても良いです。すなわち式(9)を解く代わりに\(x’\)と\(y’\)に関する方程式

を解いても良いのです。具体的に変数変換


を考えます。これは座標を\(\theta\)回転させた座標系への変換です。もちろん、\(\theta=0\)のとき、\(x=x’, y=y’\)が成立し、恒等変換となります。微分方程式は

であり、\((x’, y’)\)の空間で解いていきます。

さて、回転角\(\theta\)は任意ですが、式(15)の右辺が発散しないような\(\theta\)を選ぶ必要があります。
また、数値計算を行う上では、傾きがほとんど0に近いほうが有利です。そのため、方針としては現在の傾きを計算し、その傾き分だけ逆方向に座標回転させることでこれを実現させます。
すなわち、

分だけ回転させます。現在の傾きと座標軸の傾きを一致させることで傾きがほとんどゼロの座標軸に回転させるのです。

プログラム

以下にプログラムを示します。
必要な情報は\(f(x,y)\)の\(x, y\)方向の偏微分\(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\)の解析解です。関数名”fx”, ”fy”にそれぞれを入力してください。
計算は刻み幅制御の陽的ルンゲクッタ法を用いています。

具体例


具体的に関数\(f(x,y)=x^3-2xy+y^3\)の等高線を考えていきましょう。
関数の値がそれぞれ、\(0.01,1,2,5\)に等しいときの等高線を考えます。
具体的な初期値は、
\(\displaystyle
f(-2,1.3657)\approx 0.01,~f(-2,1.4646)\approx 1,~f(-2,1.5568)\approx 2,~f(-2,1.7977)\approx 5
\)
とします。
具体的に解いたのが左の図です。

”正解”としたgnuplotの等高線表示の結果と同じ結果が得られました。座標回転がうまく働いているようですね。微分の発散を抑えるだけでなく、数値計算量も抑えられているようです。

刻み幅\(h\)が正である場合と負である場合で進む方向が変わります。
また計算の途中で分岐がある場合、どうなるかは保証できません。

また、閉じた等高線が複数ある場合、その全てを計算することは本稿のプログラムだけではできません。初期値を求める別のプログラムを作成する必要があります。
更に、等高線がある値に等しい量を計算することはできません。初期値の値に等しい等高線を引きます。

追記


調べ物をしていたら

照井章, 佐々木建昭著『27.代数関数の陰関数描画について』
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0941-27.pdf
という素晴らしい資料がありました。

この文献では2つの方法が紹介されており、
1.\(f(x,y_0)=0\)を解いて\(x=x_1,x_2,\cdots,x_n\)を解く
2.陰関数定理から求める
という方法です。資料では、1.の方法を採用していましたが、本稿の方法は2.の方法でした。
1.はもれなく等高線を見つけることができますので、考えられる結果を得たい場合によい方法です。
一方、2.は全てのゼロ点を見つけることができませんが、計算が早くできます。別の方法などで注目したい等高線が分かっている場合に良い方法でしょう。

効率的に解くためには、場合によって使い分けることが一番です。

秋間補間

秋間補間と呼ばれる補間方法があります。

こんな補間結果となります(akimaとmodified akimaの線が秋間補間の結果です)。

秋間補間の特徴は、

  • 与えられた点を必ず通る
  • オーバーシュートが発生しにくい
  • 補間したい点から遠い補間点の影響を受けない
  • 導関数の連続性は保証されない
  • 元のデータ点を大きく逸脱するような補間は苦手(線形的な補間に近い)
  • 極値におけるデータ点など、元の関数の特徴的な値が分かっているときに良い補間結果を与える

ということです。オーバーシュートとは、元のデータが急峻に変化した場合、その前後の補間結果が振動してしまい大きく外れてしまうことを意味します([5]にオーバーシュートの様子を見ることができます)。
ただし、3次スプライン補間のような微分の連続性が保証されません。

それでは計算方法を追っていきます。

導出


秋間補間は1970年に秋間浩によって提案された補間方法です[1]。地図の等高線を表示するために生成されたようです。その後修正された秋間補間が紹介されました[2]。

具体的な計算方法を見ていきます。
補間は補間したい点を中心に前後のデータ点を用いるので、両端では特別な扱いが必要です。それを区別するために領域を3つに分けて考えます。具体的には下の図のような感じです。

領域IIにおける補間


まずは領域IIを考えます。簡単に考えるために、以下の図のように補間に用いるための6点\((x_i, y_i), i=0,5\)があった時、中間の領域である\(x_2\le x\le x_3\)の中の値を補間して求めたいと考えます。

補間は3次関数で行います。すなわち\(x_2\le x\le x_3\)において

の形で補間を行います。係数\(a_0, a_1, a_2, a_3\)は補間に用いる6点のデータ点から計算できて、

の通り求められます。ここで、\(q_1, q_2, m_1,\cdots, m_5\)は


の通り求められます。\(w_1, w_2\)は使用する秋間補間の種類によって変わります。通常の秋間補間では、

の通り計算し[1,3,4]、修正秋間補間においては

で計算します[2,3,4]。

領域I, IIIにおける補間


領域I, IIIについては以下の関係を満たすように、本来は存在しない補間用のデータ点を予測します。
領域I:最も左端のデータ点を\(x_3\)、その右隣のデータ点を\(x_4, x_5\)と置きます。すると、\(x_3\)より左のデータ点\(x_2, x_1\)を関係式(7)より予測します。
領域III:最も右端のデータ点を\(x_3\)、その左隣のデータ点を\(x_2, x_1\)と置きます。すると、\(x_3\)より右のデータ点\(x_4, x_5\)を関係式(7)より予測します。

ここで、\(m_{ij}\)は

を意味します。すると、秋間補間で用いる(本来は存在しない)端のデータ点は、

領域I)

領域III)

と求められます。

プログラム例


上の式をプログラムすれば、このようになるかと思います。
注意してプログラムを作らないとゼロ割が発生します。\(x_i\ne x_j\)を仮定していれば、式(5),(6)の\(w_1, w_2\)を計算する際にこれが発生します。なので、この回避を取り入れてプログラムを作成しています。

計算例


参考文献[4]に秋間補間と修正秋間補間の振る舞いの例があります。それを本稿のプログラムを用いて計算すると同じ振る舞いを示すことが分かります。

それでは、3次スプライン補間と秋間補間、修正された秋間補間を比べて、秋間補間にどのような特徴があるかみましょう。

オーバーシュートの抑圧


本当の答えを定義することは難しいですが、変化する点(\(x=2.8\sim 3.2\))近傍で直線とすれば傾きは5になります。一階導関数はどの補間方法も連続(右から極限と左から極限が一致の意味で)ですが、秋間補間は二階導関数は連続ではありません。3次スプラインは二階導関数まで連続であるという仮定の下での補間なので、一応連続的な変化をしています。

秋間補間では3次スプライン補間よりはオーバーシュートが抑えられているものの、近傍 \((x=2.5, 3.5)\)において外れた値となっています。
修正された秋間補間では、その点が改善されオーバーシュートが発生していないことが分かります。

振動関数の補間

振動関数を補間する例として、元の関数が\(y=\sin(x)\)だったとします。

sin関数

この場合は元の関数が十分滑らかであり、高階微分も連続であることが分かっています。与えられたデータ点も誤差がないので、3次スプラインが有効でしょう。
秋間補間では本来極値をとるはずの\(x=n\pi/2,~(nは整数)\)あたりで値があまり大きくならないことから、かなり局所的な補間である特徴が分かります。すなわち、大きくオーバーシュートしない反面、予測は得意ではないということです。これを回避するためには、元の関数の極値の値など特徴的なデータが必要であることが分かります。

二次元平面の補間は本稿には載せていませんが、[4,6]にどのような違いが表れるか図があるので、興味がある方は参照してみてください。
確かに、本来の目的である地図の等高線作成には大きな効果が期待できそうなことが分かります。おそらく、取得するデータ点も標高など、地形の特徴的な点におけるデータを集めることが主となるので、秋間補間との相性が良いのでしょう。

参考文献


[1]Akima H. A New Method of Interpolation and Smooth Curve Fitting Based on Local
Procedures. Journal of the ACM, 17(4), 589 ― 602. (1970).
doi:10.1145/321607.321609

[2]Akima H. A method of univariate interpolation that has the accuracy of a third-degree
polynomial. ACM Transactions on Mathematical Software, 17(3), 341 ― 366. (1991),
doi:10.1145/114697.116810

[3]
makima 修正Akima区分的3次エルミート内挿 -MathWorks
interp1 1次データ内挿(テーブルルックアップ) -MathWorks

[4]Cleve Moler, Makima Piecewise Cubic Interpolation

[5]スプラインによる補間

[6]格子点に内挿して等値線をひく

連成振動

弦を考えます。弦は重さ\(M\), 長さ\(L\), ばね定数\(K\)を持ちます。

この弦を波動方程式に頼らないで定式化しましょう。
波動方程式は、2次元の波動のうち、1次元分の方向を\(y=y(x, t)\)として表現するため、x軸にとって多価関数となる弦を表現することが出来ません。物性物理学等で格子の振動を考える場合は、結晶を構成する原子が平衡位置から殆ど動かないのでこういった問題は起こりません(起こったとしても無視される位少ないので、大多数の振る舞いを考える場合には問題になりません)。
よって多次元の問題を考えるには波動方程式を元にして考えるのは不適切です。そのため、弦を単なる連成振動として考えて、完全に2次元の問題として扱いたいと思います。

図のような連成振動のモデルを考えます。

質量\(m\)を持つ\(i\)番目の質点が、位置ベクトル\(\mathbf{x}_i\)で指定され、隣り合う質点との間が、ばね定数\(k\)、自然長\(l\)を持つ理想的なばねで繋がれているとします\((i=1,2,\cdots, N)\)。この時、運動方程式を立てると
\begin{eqnarray}
m\frac{d^2 \mathbf{x}_i}{dt^2}&=&
+k(|\mathbf{x}_{i+1}-\mathbf{x}_{i}|-l) \frac{\mathbf{x}_{i+1}-\mathbf{x}_{i}}{|\mathbf{x}_{i+1}-\mathbf{x}_{i}|}
-k(|\mathbf{x}_{i}-\mathbf{x}_{i-1}|-l)\frac{\mathbf{x}_i-\mathbf{x}_{i-1}}{|\mathbf{x}_i-\mathbf{x}_{i-1}|}
\end{eqnarray}
となります。全く同じですが、見通しをよくするため式変形すれば、
\begin{eqnarray}
m\frac{d^2 \mathbf{x}_i}{dt^2}&=& k\Bigl[A_i \mathbf{x}_{i+1}-\bigl(A_i+A_{i-1}\bigr)\mathbf{x}_{i}+A_{i-1} \mathbf{x}_{i-1}\Bigr]
\end{eqnarray}
と表せます。ここで、
\begin{equation}
A_i = \frac{|\mathbf{x}_{i+1}-\mathbf{x}_{i}|-l}{|\mathbf{x}_{i+1}-\mathbf{x}_{i}|},~~(i=1,\cdots, N, A_N = 0)
\end{equation}
と置きました。

さて、こうしたモデルを考えた時に、連成振動として考えた\(N\)分割した1つ1つの小さいばね(”ミクロなばね”と名づけます)とその弦を1つにみなした時の大きなばね(”マクロなばね”と名づけます)の間の関係式を考えましょう。
仮定として、等間隔に分割し、弦の密度は一様であるとします。

この条件の下で、
マクロなばねの重さ\(M\), 自然長\(L\), ばね定数\(K\)

ミクロなばねの重さ\(m\), 自然長\(l\), ばね定数\(k\)
の間の関係式を導出します。

結論として、マクロとミクロなばねの間に成り立つ関係は
\begin{eqnarray}
L&=&N l \\
M&=&N m \\
K &=& k/N
\end{eqnarray}
となります。

自然長

自然長\(L\)の弦を\(N\)分割するので、
\begin{equation}
L=N l
\end{equation}
の関係があります。

重さ

重さ\(M\)の弦を\(N\)分割するので、
\begin{equation}
M=N m
\end{equation}
と書けます。

ばね定数

最後にばね定数の関係を考えましょう。この関係は、弾性エネルギーを考えることで導くことができます。
マクロなばねとして全体を見た場合に長さ\(D\)だけ縮んだ時に蓄えられる弾性エネルギーと
同じだけ縮んだ時にミクロな\(N\)個のばねに蓄えられる弾性エネルギーが同じであってほしいと要請します。すなわち、ミクロなばねの縮みの合計がマクロなばねの縮み\(D\)に等しいとすると、
\begin{equation}
D=N d
\end{equation}
と書けます。
実は、大胆な過程をしないとマクロなばねとミクロなばねの関係を求めることが出来ません。
なぜなら、マクロなばねはいつでも線形応答をするかのように現在考えていますが、ミクロなばねでは場所ごとに違っても良いという様に定式化しています。なのでもともと無理な話なのです。
ではどうやって妥当な関係式を導出すればよいかといえば、ばねが非常にゆっくり運動が行われるときを仮定するのです。ゆっくり動くときの振る舞いは全てのばねが同じ動きをするとして差し支えないでしょう。そうして定式化します。
よって、
\begin{eqnarray}
\frac{1}{2}K D^2 &=& N\cdot \frac{1}{2} k d^2 \nonumber \\
\to ~~ K &=& k/N
\end{eqnarray}
という関係式が導けます。

あとは数値計算を行うだけです。陽的ルンゲクッタ法で解いたプログラムを以下に示します。

https://slpr.sakura.ne.jp/qp/supplement_data/wave_particles.tar.gz

実行は、

$ gfortran rkf45.f90 main.f90
$ ./a.out

でokだと思います。初期状態や、重さや自然長はinputファイルを見てください。

実行後、動画をgnuplot上で出力したければ、

$ gnuplot
$ call "movie.plt" 100

としてください。100は表示する時間ステップを表します。この引数の値の最大はinputファイルの中のNtまでです。

数値計算結果


実際に数値計算を行う条件として、自然長や重力があると波動方程式と若干異なる振る舞いになってしまうので、対応を見る上ではなくしています。すなわち、自然長\(L=0\)、重力\(g=0\)として計算します。

三角パルス

三角形の波がパルス状に存在するとします。
そして初期状態として、初速度がゼロであることを仮定しましょう。

この場合、波動方程式の考察から、
同じ関数であらわされる右向きの波\(f(x-vt)\)と左向きの波\(f(x+vt)\)の重ね合わせとして書かれることが分かっています。すなわち、解\(y=y(x,t)\)は
\begin{equation}
y(x,t)=f(x-vt)+f(x+vt)
\end{equation}
と書かれます。図で表せば以下のように時間発展していくことが期待されます。

これが本稿の連成振動モデルで実際にそうなっているのかを確かめるのは良い問いかけでしょう。
実際に連成振動を数値的に解くと以下の通りになります。

ゆっくりと時間発展を見ていくと

となります。明らかに右向きに進む波と左向きに進む波として分離します。分離した結果から、初期状態がそれらの波の重ね合わせで表現されていたことが分かるでしょう。

矩形パルス

矩形パルスを考えてみます。実際に数値計算をするとこんな感じです。

結局右向きと左向きの重ね合わせとしてあらわされることも確認できますが、決して単純なそれらの足し合わせで書かれているわけではないことがわかります。この振る舞いは、波動方程式に対応するように連成振動モデルを作っていないことから由来します。波動方程式としてあらわした二階微分の偏微分方程式の場合は多価関数をとることができません。なので縦に弦が伸びる場合、間に質点を置くことができないので質点の位置がいきなり飛ぶことになります。しかし、連成振動モデルではその制約をして初期状態を準備しているわけではありませんのでその違いが出て来ます。図で表せば、以下のようになります。

両者の違いがあるので、波動方程式の結論である
\begin{equation}
y(x,t)=f(x-vt)+f(x+vt)
\end{equation}
が成り立っていない、と解釈することができます。

少しずつ時間発展をみるとこの通りになります。

三角形の波

端まで三角形のパルスであった場合にどのように振る舞うかを見てみましょう。特に面白い振る舞いがあるわけではなく、上のパルスの、右向きと左向きの波の重ね合わせで説明ができるので、単にシミュレーション結果を載せるだけにとどめます。実際に計算してみると以下のようになります。

星形

初期状態が星型である場合も見てみましょう。振る舞いも同じです。

注意点としては、実際にこの振る舞いは起こりえないことに注意しておきましょう。なぜなら、本当の弦で行った場合、重なる場所があると弦の衝突が起こります。しかし、この連成振動モデルでは計算上、衝突は起こりません。

偏りがある三角形のパルス

偏りがある場合も波動方程式では記述することができません。こんな感じの初期状態です。

これを実際にシミュレートすると以下の通りになります。

3次元の場合

3次元の場合も載せておきます。ふるまい自体はそんなに変わるわけではないので、シミュレーション結果を載せるだけにとどめておきます。

弾道計算のコード(Excel)

Excelのマクロ(VBA)で弾道計算を行うコードを作成しました。

https://slpr.sakura.ne.jp/qp/supplement_data/BBullet_course_excel/BBbullet_course_ver1.41.xlsm
上記プログラムの利用の際は連絡先と著作権についてをご覧ください。

空気抵抗を修正したβ版を作成しました。参考設定は機能しません。
https://slpr.sakura.ne.jp/qp/supplement_data/BBullet_course_excel/BBbullet_course_ver1.5_beta.xlsm

以下の微分方程式を計算します。

エクセルシート”bullet”
\(
\begin{align}
m\frac{d^2 \vec{r}}{dt^2}&=
-mg\vec{k}-\frac{1}{2}C_d \rho \pi R^2 |\vec{V}|\vec{V}
-C_l \frac{4}{3}\pi R^3 2\rho |\vec{\omega}| |\vec{V}|\frac{\vec{V}\times\vec{\omega}}{|\vec{V}\times\vec{\omega}|} \\
\frac{d\mathbf{\omega}}{dt}&=N/I \\
N&=\frac{\rho C_f}{2}R\frac{4\pi R^2}{2}\left(|v_{up}|v_{up}+|v_{down}|v_{down}\right)
\end{align}
\)
回転の減衰は本来、弾道計算(BB弾)の理論で導いた通り積分を行わなければなりませんが、簡単にするためにBB弾を真四角の箱として近似して導いています。
この近似は本来の積分値と1パーセント程度の違いしか出てこないので、BB弾の計算には非常に良い近似です。
回転の減衰を取り入れたくない場合、入力パラメータの”回転の減衰”項目をNOにすることでそのように設定が出来ます。
ゼロインを固定した時の弾道の探索機能は実装していないので出来ません。
Excelの設定項目では、Fortranで実装したコードから求めたパラメータをあらかじめ用意しておきました。
設定されたものと書いてあっても、高精度に積分計算をして求めた結果と上の近似をもちいた本エクセルの結果は違くなります。数10cm程度のずれは出てきますので、その点は注意してください。

エクセルシート”barrel”
\(
\begin{align}
m\frac{d^2}{dt^2}x(t)&=\left[P(t)-P_0\right]S_{BB}-\frac{1}{2}C_d \rho \pi R^2 |v(t)|v(t) \\
m_s\frac{d^2}{dt^2}x_0(t)&=-k\left[x_0(t)-x_B-l\right]-[P(t)-P_0]S_s -F_f\label{bbin2} \\
\frac{d}{dt}V(t)&=v(t)S_{\text{barrel}}-v_0(t)S_s+c'(S_{barrel}-\pi R^2)\mathrm{sgn}(P(t)-P_0)\sqrt{\frac{2}{\rho}|P(t)-P_0|}
\end{align}
\)

内部は以下の構造をしていると想定しています。詳細はバレル内部でのBB弾の方程式をご覧ください。

計算手法はどちらも陽的4次ルンゲクッタ法を用いています。

使い方


  1. ファイルのダウンロード
  2. 最新
    https://slpr.sakura.ne.jp/qp/supplement_data/BBullet_course_excel/BBbullet_course_ver1.5_beta.xlsm

    をクリックでダウンロード、もしくは
    右クリックして、”名前を付けてリンク先を保存”からダウンロードしてください。

  3. 計算パラメータの入力
  4. 入力する場所は、色付きのセルです。

    • 弾道計算について

    • 出力結果は大きく分けて2つの項目に分かれています。
      1つ目は定数、射出高さに着弾、地面に着弾の項目は重要と思われるパラメータの抜粋、2つ目は弾道の時間ごとのデータです。
      グラフは、2つ目のデータを元に表示しているだけですので、必要に応じて追加、変更を行ってください。

    • バレル内部の計算について

    • 出力結果は大きく分けて2つの項目に分かれています。
      1つ目は定数、内圧が大気圧に等しい時に射出される時と指定したバレル長におけるパラメータの抜粋、2つ目はBB弾、ピストンの位置、速度の時間ごとのデータです。
      グラフは、2つ目のデータを元に表示しているだけですので、必要に応じて追加、変更を行ってください。

    手入力で入力することも可能ですが、参考設定と書かれたボタンを押すことで、予め設定されたパラメータを読み込ませることもできます。

  5. 計算開始
  6.   入力パラメータを入力した後、計算開始ボタンを押すことで計算が開始されます。

注意点

常識的なパラメータの範囲内でしか動作確認をしておりません。
この結果はあくまで一例です。本シミュレーションを信用して設計・組立を行い、本シミュレーションと結果が違う事があります。その場合私は責任を負いませんので、その点をご了承して使用してください。
BB弾で出来るからと言って、銃弾等の計算はそれなりの信用しかできないことを考慮してください。

追記


バレル内部の計算において、抜弾抵抗の考慮はしていません。すなわちホップが全く掛かっていない状況の計算です。
もし、ホップを掛けた状況を再現したいのであれば、以下のような考えで出来るでしょう。

まず、ホップを掛けた状態でBB弾をバレル内部から引き出す際に必要な力をどうにかして実験的に求めます。
このホップを掛けた際に必要な力\(F\)は、内部圧力\(P\)とBB弾の面積\(S_{BB}\)を用いて
\(
F=PS_{BB}
\)
と書けるはずです。すなわち、内圧がこの力に達した時にBB弾が射出されるとして考え、その内部圧力に達した際にBB弾の運動方程式を解き始める、という方法で可能なはずです。

参考文献

[1] 弾道計算の理論 -シキノート https://slpr.sakura.ne.jp/qp/bullet-course/
[2] BB弾の弾道学 -ハイパー道楽 http://www.hyperdouraku.com/colum/ballistics/index.html

極値を求めるニュートン法

ニュートン法に関するお話です。
”ニュートン法”と呼ばれる方法は
2種類(1.初期値近傍の極値を求めるニュートン法、2. ゼロ点を求めるためのニュートン法
があるようですが、ここでは1. 初期値近傍の極値を求める方のニュートン法についてのお話です。

まとめ

ベクトル\(\mathbf{x}=(x_1, x_2, \cdots, x_N)\)で指定される実数値関数\(f(\mathbf{x})\)の極値を求める事を考えます。
ここで、初期値近傍の点\(\mathbf{x}=\mathbf{x}^{(0)}\)が分かっている時、その近傍にある\(f(\mathbf{x})\)の極小値を与える\(\mathbf{x}=\mathbf{a}\)は適当な反復計算を行い、
\begin{equation}
\mathbf{a}=\lim_{k\to\infty}\mathbf{x}^{(k)}
\end{equation}
で与えられます。極値を求めるニュートン法を用いる場合、\(\mathbf{x}^{(k)}\)は漸化式として与えられ、
\begin{align}
\mathbf{x}^{(k+1)}&=\mathbf{x}^{(k)}+\mathbf{d}^{(k)} \\
\mathbf{d}^{(k)}&=-\left[H f\bigl(\mathbf{x}^{(k)}\bigr)\right]^{-1}\cdot \left[\nabla f\bigl(\mathbf{x}^{(k)}\bigr)\right]
\end{align}
として逐次的に与えられます。ここで、\(H f(\mathbf{x}), \nabla f\bigl(\mathbf{x}\bigr)\)は関数\(f(\mathbf{x})\)のヘッセ行列、傾き(Gradient)を表し、
\begin{equation}
\hat{H}f=
\begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} &\cdots &\frac{\partial^2 f}{\partial x_1 \partial x_n} \\
\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} &\cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\
\vdots & \vdots &\ddots & \vdots \\
\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} &\cdots &\frac{\partial^2 f}{\partial x_n^2} \\
\end{pmatrix}
,~~\nabla f=
\begin{pmatrix}
\frac{\partial f}{\partial x_1} \\
\frac{\partial f}{\partial x_2} \\
\vdots \\
\frac{\partial f}{\partial x_n}
\end{pmatrix}
\end{equation}
で与えられます。

特に\(f\)が\(x, y\)の2変数関数\(f(x,y)\)であるならば、
\begin{align}
\begin{pmatrix}
x^{(k+1)} \\
y^{(k+1)}
\end{pmatrix}
&=
\begin{pmatrix}
x^{(k)} \\
y^{(k)}
\end{pmatrix}
-\frac{1}{f_{xx}f_{yy}-f_{xy}f_{yx}}
\begin{pmatrix}
f_{yy} & -f_{xy} \\
-f_{yx} & f_{xx}
\end{pmatrix}
\begin{pmatrix}
f_x \\
f_y
\end{pmatrix}
\end{align}
ここで、
\begin{equation}
\hat{H}f
=
\begin{pmatrix}
f_{xx} & f_{xy} \\
f_{yx} & f_{yy}
\end{pmatrix}
,~~
\nabla f=
\begin{pmatrix}
f_x \\
f_y
\end{pmatrix}
\end{equation}
です。ここで、\(f_p\equiv\frac{\partial f}{\partial p}, ~f_{pq}\equiv\frac{\partial^2 f}{\partial p\partial q}, (p, q=x,y)\)と書きました。
微分を差分で近似するとします。\(x, y\)方向の刻み幅を\(h=h_x=h_y\)とすればそれぞれの偏微分は点\((x,y)\)近傍の7点を用いて
\begin{align}
f_x &= \frac{f(x+h, y) – f(x-h, y)}{2h} +O(h^2)\\
f_y &= \frac{f(x, y+h) – f(x, y-h)}{2h} +O(h^2)\\
f_{xx} &= \frac{f(x+h, y) – 2f(x, y)+ f(x-h, y)}{h^2} +O(h^2)\\
f_{xy} &=f_{yx}= \frac{1}{2h^2}\bigl[f(x+h, y) + f(x-h, y) + f(x, y+h) \\
&\hspace{1em}+ f(x, y-h)-2f(x,y)-f(x+h,y+h)-f(x-h,y-h)\bigr]+O(h^2) \\
f_{yy} &= \frac{f(x, y+h) – 2f(x, y)+ f(x, y-h)}{h^2} +O(h^2)
\end{align}
と書けます[2]。

導出


詳しくは述べませんが、1次元の問題における極小値を求めるニュートン法くらいは導いておきましょう。
多次元の場合は拡張すれば良く、考え方は変わりません。多次元では他の文献、例えば[1]を参考にして下さい。

関数\(f(x)\)を\(x=x^{(k)}\)周りでテイラー展開を行えば、
\begin{equation}
f(x)=f\bigl(x^{(k)}\bigr)+f’\bigl(x^{(k)}\bigr)\bigl(x-x^{(k)}\bigr)+\frac{1}{2}f^{\prime\prime}\bigl(x^{(k)}\bigr)\bigl(x-x^{(k)}\bigr)^2+O(\Delta^3)
\end{equation}
となります。ここで、\(\Delta=|x-x^{(k)}|\)とおきました。
今、欲しい解\(a\)は関数\(f(x)\)の極値なので、
\(\frac{df}{dx}=0\)を満たす\(x\)を探せばよいのです。よって、両辺を\(x\)で微分して、
\begin{align}
\frac{df(x)}{dx}=f’\bigl(x^{(k)}\bigr)+f^{\prime\prime}\bigl(x^{(k)}\bigr)\bigl(x-x^{(k)}\bigr)+O(\Delta^2)
\end{align}
を得ます。これが\(0\)になる\(x\)が解\(a\)なので、
\begin{equation}
\left. \frac{df(x)}{dx}\right|_{x=a}=f’\bigl(x^{(k)}\bigr)+f^{\prime\prime}\bigl(x^{(k)}\bigr)\bigl(a-x^{(k)}\bigr)+O(\Delta^2) = 0
\end{equation}
となります。今、\(O(\Delta^2)\)を無視すれば得られる解\(a\)は近似解\(a\approx x^{(k+1)}\)となるので、
\begin{equation}
f’\bigl(x^{(k)}\bigr)+f^{\prime\prime}\bigl(x^{(k)}\bigr)\bigl(x^{(k+1)}-x^{(k)}\bigr) = 0 \\
\end{equation}
を解いて
\begin{equation}
x^{(k+1)} = x^{(k)}-\frac{f’\bigl(x^{(k)}\bigr)}{f^{\prime\prime}\bigl(x^{(k)}\bigr)}
\end{equation}
となります。…ここまで来てしまうとニュートン・ラフソン法と同じですね。関数値がゼロになる点を探すのか、導関数値がゼロになる点を探すのかの違いなだけです。
多次元だと行列になってしまいシンプルではない形になり難しく見えますが、1次元では非常に単純です。

問題は1階(傾き)、2階導関数(ヘッセ行列)をどのように求めるかです。厳密な値が無い場合は近似的にしか得るしかありません。基本的にこれらの計算量は膨大になります。
最も簡単な方法は微分を差分に置き換えてしまうことですが、差分は余り良い方法とは言えません。

厳密なヘッセ行列は、例えば自動微分の考えで得ることが出来ます。例えば、Hyper-dual numbersによる二階偏微分の計算を参考にして得ることが出来ます。

また、引数が複素数で計算結果が実数で返ってくる関数\(f(z)\)の最小値を求めたいのであれば、\(z=x+iy\)として、\(f(x,y)\)の二変数関数としてその極致を探せば良いです。

2次元のプログラム


ここでは2次元の問題に限り、傾き、ヘッセ行列を差分で近似した場合のプログラムを記述します。

下のプログラムは関数
\begin{equation}
f(x,y)=x e^{-(x^2+y^2)/2}
\end{equation}
の、点\((x_0, y_0)=(-1.2, -0.3)\)近傍にある極値を求めるプログラムです。
グラフで示せば、以下の通りになります。
この関数の極値は黒点、初期値は赤点で示しています。

以下に実行例を示します。

$ gfortran main.f90
$ ./a.out
  -1.2000000000000000      -0.29999999999999999      -0.55840071716917605    
  -1.0000000016663813        3.4150669573473641E-013 -0.60653065971263342      4
$

1行目1,2,3列目はそれぞれ\(x,y\)の初期値, 関数\(f(x,y)\)の値を示しています。
また、2行目1,2,3,4列目は求まった\(x,y\)の値, 関数\(f(x,y)\)の値、そして収束に至るまでに行った繰り返しの回数を示しています。

参考文献


[1]塩浦昭義, 数理計画法 第13回
[2]Abramowitz and Stegun, “Handbook of Mathematical Functions”, http://people.math.sfu.ca/~cbm/aands/page_883.htm, http://people.math.sfu.ca/~cbm/aands/page_884.htm