베어스토우 방법

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

방법

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

f (x) = a_{0} x^{n} + a_{1} x^{n - 1} + a_{2} x^{n - 2} + \dots + a_{n - 1} x + a_{n} = 0

로부터

P (x) = \sum_{i = 0}^{n} a_{i} x^{i}

이므로

P (x) = (x^{2} + u x + v) Q (x) + c x + d

이어서

다항식 장제법에서

Q (x) = \sum_{i = 0}^{n - 2} b_{i} x^{i}

따라서

P (x) = (x^{2} + u x + v) (\sum_{i = 0}^{n - 2} b_{i} x^{i}) + c x + d

계속해서

Q (x) = (x^{2} + u x + v) R (x) + g x + h

R (x) = \sum_{i = 0}^{n - 4} f_{i} x^{i}

Q (x) = (x^{2} + u x + v) (\sum_{i = 0}^{n - 4} f_{i} x^{i}) + g x + h

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

b_{n} = b_{n - 1} = 0

b_{i} = a_{i + 2} - u b_{i + 1} - v b_{i + 2}

c = a_{1} - u b_{0} - v b_{1}

d = a_{0} - v b_{0}

f_{n} = f_{n - 1} = 0

f_{i} = b_{i + 2} - u f_{i + 1} - v f_{i + 2} (i = n - 2, \dots, 0)

g = b_{1} - u f_{0} - v f_{1}

h = b_{0} - v f_{0}

c (u, v) = d (u, v) = 0

이므로

이것은 편미분과 행렬에서

[\begin{matrix} u \\ v \end{matrix}] : = [\begin{matrix} u \\ v \end{matrix}] - {[\begin{matrix} \frac{\partial c}{\partial u} & \frac{\partial c}{\partial v} \\ \frac{\partial d}{\partial u} & \frac{\partial d}{\partial v} \end{matrix}]}^{- 1} [\begin{matrix} c \\ d \end{matrix}] : = [\begin{matrix} u \\ v \end{matrix}] - \frac{1}{v g^{2} + h (h - u g)} [\begin{matrix} - h & g \\ - g v & g u - h \end{matrix}] [\begin{matrix} c \\ d \end{matrix}]

으로 표현될수있다.

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

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

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

u = \frac{a_{n - 1}}{a_{n}} = \frac{11}{6}, v = \frac{a_{n - 2}}{a_{n}} = \frac{33}{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) 속도를 나타낸다.