Petitverse

ニュートン法
かの有名なニュートン法。実数領域でのイメージが強いですが、初期値に複素数を与えてやれば複素数の解も求まるようです。

実装や原理が簡単ではありますが、実用性はなさそうです。

ベアストウ法
二次式による因数分解を繰り返して、因数の2次方程式を解くことで解を2つセットで得るアルゴリズムらしいです。
複素数の計算をしなくとも複素解を得られる上に、分かりやすい。
フォルマントを求める場合は、虚部が負の解は不要だったりする(虚部が負の部分はサンプリング周波数の半分より高い周波数に相当する)ので、虚部が正の解のみを簡単に得られるのも高ポイント。

https://fermiumbay13.hatenablog.com/

ミューラー法
情報があまり無かった。
ベアストウ法と同じく複素数の計算をしなくて良くて、虚部が正の解のみを得るのも容易だと思われ。

…と思ったけど、計算過程で複素数出てくる。

適切な初期値を決めるためにミューラー法を使う。ありな気はしますね。
そういえば、必要な精度も検討しないとですね。場合によっては精度を高める必要も無いかもしれません。
音声の解析をする場合、サンプル数によって必要な精度が決まりそうです。
それ以上精度を上げてもFFTとかディジタルフィルタの方がネックになってくるので、それ以上精度を上げる意味がない感じですね。

具体的に必要な精度は…後で考えます。

出ました。
11〜12桁。(計算式は省略)
結構必要。

ベアストウ法について調べました。
まず、使える条件は全ての係数が実数であること。
恐らく、因数に2次式を含むための条件と同じ。(根が必ず実数の組、あるいは共役となる複素数の組となる)

元の方程式をx^2+px+qで割った商をdとすると
(x^2+px+q)m+Rx+S=0になる。
RとSをp,qの関数と見たときにR=0,S=0となるようなp,qを二次元ニュートン法で求める感じになります。

なので、収束速度としてはニュートン法と大きく変わらないと思われ。

あと微分が結構面倒で、自動微分に頼りそうになった(非効率な自動微分しか書けないので手動でやるに越したことはない)

[悲報]求める多項式の次数、増えた(100次以上)

今更ながら、サイトを頼りにとりあえずC言語での実装は出来ました。
ただ、数式のミスが多い。特に10.17式の二項目の符号が間違えててだいぶ悩みました。
http://skomo.o.oo7.jp/f20/hp20_10.htm


そういえば、この手の反復計算をするときは反復回数を決め打ちで実行するのがセオリーって因幡めぐるちゃんが言ってたな…

古寺いろはちゃんでした。
因幡めぐるで検索しても見つからないわけだ…
https://togetter.com/li/973164