수치해석학 에서 베어스토우(Bairstow)의 방법 은 임의의 차수의 실제 다항식의 근사해를 찾아내는 효율적인 알고리즘이다. 이 근 찾기 알고리즘 은 레오나드 베어스토우(Leonard Bairstow)의 1920년 'Applied Aerodynamics' 책 부록에 처음 등장했다. 알고리즘은 실수 계산만을 사용하여 복소 공액 쌍의 근을 찾는다. 이는 다항식 장제법 과 대수학의 기본정리 에 기반하고 있다.
고차 다항식의 일반적인 해를 찾는 베어스토우 방법은 주어진 방정식에서
x
2
+
u
x
+
v
{\displaystyle x^{2}+ux+v}
형태를 갖는 2차식을 인수로 갖도록 설정해서 방정식의 차수를 낮추어감으로서 반복적으로
u
,
v
{\displaystyle u,v}
의 값이 근에 접근하도록 한다.
f
(
x
)
=
a
0
x
n
+
a
1
x
n
−
1
+
a
2
x
n
−
2
+
⋯
+
a
n
−
1
x
+
a
n
=
0
{\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}
로부터
다항식 장제법 에서
P
(
x
)
=
∑
i
=
0
n
a
i
x
i
{\displaystyle P(x)=\sum _{i=0}^{n}{a_{i}x^{i}}}
이므로
P
(
x
)
=
(
x
2
+
u
x
+
v
)
Q
(
x
)
+
c
x
+
d
{\displaystyle P(x)=(x^{2}+ux+v)Q(x)+cx+d}
이어서
다항식 장제법에서
Q
(
x
)
=
∑
i
=
0
n
−
2
b
i
x
i
{\displaystyle Q(x)=\sum _{i=0}^{n-2}{b_{i}x^{i}}}
따라서
P
(
x
)
=
(
x
2
+
u
x
+
v
)
(
∑
i
=
0
n
−
2
b
i
x
i
)
+
c
x
+
d
{\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}{b_{i}x^{i}}\right)+cx+d}
계속해서
Q
(
x
)
=
(
x
2
+
u
x
+
v
)
R
(
x
)
+
g
x
+
h
{\displaystyle Q(x)=(x^{2}+ux+v)R(x)+gx+h}
R
(
x
)
=
∑
i
=
0
n
−
4
f
i
x
i
{\displaystyle R(x)=\sum _{i=0}^{n-4}{f_{i}x^{i}}}
Q
(
x
)
=
(
x
2
+
u
x
+
v
)
(
∑
i
=
0
n
−
4
f
i
x
i
)
+
g
x
+
h
{\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}{f_{i}x^{i}}\right)+gx+h}
변수 (계수 )
c
,
d
,
g
,
h
{\displaystyle c,d,g,h}
그리고
u
,
v
{\displaystyle u,v}
의 함수가 되는
b
i
,
f
i
{\displaystyle b_{i},f_{i}}
는 재귀적으로 다음과 같이 찾아진다.
b
n
=
b
n
−
1
=
0
{\displaystyle b_{n}=b_{n-1}=0}
b
i
=
a
i
+
2
−
u
b
i
+
1
−
v
b
i
+
2
{\displaystyle b_{i}=a_{i+2}-ub_{i+1}-vb_{i+2}}
c
=
a
1
−
u
b
0
−
v
b
1
{\displaystyle c=a_{1}-ub_{0}-vb_{1}}
d
=
a
0
−
v
b
0
{\displaystyle d=a_{0}-vb_{0}}
f
n
=
f
n
−
1
=
0
{\displaystyle f_{n}=f_{n-1}=0}
f
i
=
b
i
+
2
−
u
f
i
+
1
−
v
f
i
+
2
(
i
=
n
−
2
,
⋯
,
0
)
{\displaystyle f_{i}=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\cdots ,0)}
g
=
b
1
−
u
f
0
−
v
f
1
{\displaystyle g=b_{1}-uf_{0}-vf_{1}}
h
=
b
0
−
v
f
0
{\displaystyle h=b_{0}-vf_{0}}
2차 방정식 에서
c
(
u
,
v
)
=
d
(
u
,
v
)
=
0
{\displaystyle c(u,v)=d(u,v)=0}
이므로
이것은 편미분 과 행렬 에서
[
u
v
]
:=
[
u
v
]
−
[
∂
c
∂
u
∂
c
∂
v
∂
d
∂
u
∂
d
∂
v
]
−
1
[
c
d
]
:=
[
u
v
]
−
1
v
g
2
+
h
(
h
−
u
g
)
[
−
h
g
−
g
v
g
u
−
h
]
[
c
d
]
{\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}}}
으로 표현될수있다.
한편, 수렴이 일어날 때까지 방정식의 해를 찾는 이 방법은 프로그래밍 언어로 구현될 수 있다.
f
(
x
)
=
6
x
5
+
11
x
4
−
33
x
3
−
33
x
2
+
11
x
+
6
=
0
{\displaystyle f(x)=6x^{5}+11x^{4}-33x^{3}-33x^{2}+11x+6=0}
첫 번째 이차 다항식
f
(
x
)
{\displaystyle f(x)}
의 세 계수로부터 형성된 정규화된 초기값으로 다항식을 설정해보면,
u
=
a
n
−
1
a
n
=
11
6
,
v
=
a
n
−
2
a
n
=
33
6
{\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) 속도를 나타낸다.
같이 보기 [ 편집 ]