Bairstow法による求根

Bairstow法は、1次元多項式に対して効率的に全ての解を求める求根アルゴリズム.二次式の解を求めて関数を割るのを低次の式になるまで繰り返す手法.数値的な性質はよくなく桁落ちしやすいとされる. 二次式の解を求める時にニュートン法を用いて解を算出する.

ニュートン法についてはリンクを参照

Bairstow法の手順 1. 多項式\(f(x)\)、適当な初期値\(u_0, v_0\)として二次式\(x^2+u_0x+v_0\)を用意 2. \(f(x)\)を\(x^2+ux+v\)で割った時の余り\(cx+d\)は\(u,v\)の関数になるため、これを $$c(u,v) = 0, d(u,v) = 0$$ の解を求める二変数のニュートン法と捉えることで、\(u,v\)を求める. 3. 上記の計算を\(f(x)\)の次数が二次以下になるまで繰り返す.