베어스토우 방법

수치해석학에서 베어스토우(Bairstow)의 방법은 임의의 차수의 실제 다항식의 근사해를 찾아내는 효율적인 알고리즘이다. 이 근 찾기 알고리즘은 레오나드 베어스토우(Leonard Bairstow)의 1920년 'Applied Aerodynamics' 책 부록에 처음 등장했다. 알고리즘은 실수 계산만을 사용하여 복소 공액 쌍의 근을 찾는다. 이는 다항식 장제법과 대수학의 기본정리에 기반하고 있다.

방법

고차 다항식의 일반적인 해를 찾는 베어스토우 방법은 주어진 방정식에서 ${\displaystyle x^{2}+ux+v}$형태를 갖는 2차식을 인수로 갖도록 설정해서 방정식의 차수를 낮추어감으로서 반복적으로 ${\displaystyle u,v}$의 값이 근에 접근하도록 한다.

${\displaystyle f(x)=a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+\cdots +a_{n-1}x+a_{n}=0}$ 로부터

다항식 장제법에서 ${\displaystyle P(x)=\sum _{i=0}^{n}{a_{i}x^{i}}}$ 이므로

${\displaystyle P(x)=(x^{2}+ux+v)Q(x)+cx+d}$

이어서

다항식 장제법에서 ${\displaystyle Q(x)=\sum _{i=0}^{n-2}{b_{i}x^{i}}}$

따라서

${\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}{b_{i}x^{i}}\right)+cx+d}$

계속해서

${\displaystyle Q(x)=(x^{2}+ux+v)R(x)+gx+h}$

${\displaystyle R(x)=\sum _{i=0}^{n-4}{f_{i}x^{i}}}$

${\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}{f_{i}x^{i}}\right)+gx+h}$

변수(계수) ${\displaystyle c,d,g,h}$ 그리고 ${\displaystyle u,v}$의 함수가 되는 ${\displaystyle b_{i},f_{i}}$는 재귀적으로 다음과 같이 찾아진다.

${\displaystyle b_{n}=b_{n-1}=0}$

${\displaystyle b_{i}=a_{i+2}-ub_{i+1}-vb_{i+2}}$

${\displaystyle c=a_{1}-ub_{0}-vb_{1}}$

${\displaystyle d=a_{0}-vb_{0}}$

${\displaystyle f_{n}=f_{n-1}=0}$

${\displaystyle f_{i}=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\cdots ,0)}$

${\displaystyle g=b_{1}-uf_{0}-vf_{1}}$

${\displaystyle h=b_{0}-vf_{0}}$

2차 방정식에서

${\displaystyle c(u,v)=d(u,v)=0}$이므로

이것은 편미분과 행렬에서

${\displaystyle {\begin{bmatrix}u\\v\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\begin{bmatrix}{\frac {\partial c}{\partial u}}&{\frac {\partial c}{\partial v}}\\[3pt]{\frac {\partial d}{\partial u}}&{\frac {\partial d}{\partial v}}\end{bmatrix}}^{-1}{\begin{bmatrix}c\\d\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\frac {1}{vg^{2}+h(h-ug)}}{\begin{bmatrix}-h&g\\[3pt]-gv&gu-h\end{bmatrix}}{\begin{bmatrix}c\\d\end{bmatrix}}}$

으로 표현될수있다.

한편, 수렴이 일어날 때까지 방정식의 해를 찾는 이 방법은 프로그래밍 언어로 구현될 수 있다.

예

${\displaystyle f(x)=6x^{5}+11x^{4}-33x^{3}-33x^{2}+11x+6=0}$

첫 번째 이차 다항식 ${\displaystyle f(x)}$의 세 계수로부터 형성된 정규화된 초기값으로 다항식을 설정해보면,

${\displaystyle u={{a_{n-1}} \over {a_{n}}}={{11} \over {6}},v={{a_{n-2}} \over {a_{n}}}={{33} \over {6}}}$

베어스토우 방법의 반복 단계

반복횟수	u	v	단계 길이	근
0	1.833333333333	−5.500000000000	5.579008780071	−0.916666666667±2.517990821623
1	2.979026068546	−0.039896784438	2.048558558641	−1.489513034273±1.502845921479
2	3.635306053091	1.900693009946	1.799922838287	−1.817653026545±1.184554563945
3	3.064938039761	0.193530875538	1.256481376254	−1.532469019881±1.467968126819
4	3.461834191232	1.385679731101	0.428931413521	−1.730917095616±1.269013105052
5	3.326244386565	0.978742927192	0.022431883898	−1.663122193282±1.336874153612
6	3.333340909351	1.000022701147	0.000023931927	−1.666670454676±1.333329555414
7	3.333333333340	1.000000000020	0.000000000021	−1.666666666670±1.333333333330
8	3.333333333333	1.000000000000	0.000000000000	−1.666666666667±1.333333333333

8회 반복한 후에,이 방법은 표현된 정밀도 내에서 근 -1/3 및 -3을 포함하는 2차 인자를 생성한다. 네 번째 반복에서 단계 길이는 초선형 수렴(Superlinear convergence) 속도를 나타낸다.

같이 보기

• 이분법
• 편미분
• 2차 방정식

참고

• Applied Aerodynamics,Leonard Bairstow,1920 인터넷 아카이브
• Applied Aerodynamics,Leonard Bairstow,Longmans, Green and Company, 1939
• Applied Aerodynamics,June 2, 2008