베어스토우 방법 문서 원본 보기

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

== 방법 ==
고차 다항식의 일반적인 해를 찾는 베어스토우 방법은 주어진 방정식에서 <math>x^2+ux+v</math>형태를 갖는 2차식을 인수로 갖도록 설정해서 방정식의 차수를 낮추어감으로서 반복적으로 <math>u , v</math>의 값이 근에 접근하도록 한다.
:<math>f(x)=a_0 x^n + a_1 x^{n-1} +a_2 x^{n-2}+ \cdots + a_{n-1} x +a_n = 0 </math> 로부터
:[[다항식 장제법]]에서 <math>P (x)= \sum_{i=0}^{n}{a_i x^i}</math> 이므로
:<math>P(x)= (x^2+ux+v)Q(x)+cx+d</math>
이어서
:다항식 장제법에서 <math>Q(x)= \sum_{i=0}^{n-2}{b_i x^i}</math>
따라서
:<math>P(x)= (x^2+ux+v)\left( \sum_{i=0}^{n-2}{b_i x^i} \right)+cx+d</math>
계속해서
:<math>Q(x)= (x^2+ux+v) R(x)+gx+h</math>
:<math>R(x)= \sum_{i=0}^{n-4}{f_i x^i}</math>
:<math>Q(x)= (x^2+ux+v)\left( \sum_{i=0}^{n-4}{f_i x^i} \right)+gx+h</math>
[[변수 (수학)|변수]]([[계수]]) <math>c,d,g,h</math> 그리고 <math>u,v</math>의 함수가 되는 <math>b_i , f_i</math>는 재귀적으로 다음과 같이 찾아진다.
:<math>b_n = b_{n-1}=0  </math>
:<math>b_i = a_{i+2}-ub_{i+1}-vb_{i+2}  </math>
:<math>c = a_{1}-ub_{0}-vb_{1}  </math>
:<math>d = a_{0}-vb_{0}  </math>
:<math>  f_n= f_{n-1}=0</math>
:<math>  f_i= b_{i+2}-uf_{i+1}-vf_{i+2} \qquad (i=n-2,\cdots,0)</math>
:<math>g = b_{1}-uf_{0}-vf_{1}  </math>
:<math>h = b_{0}-vf_{0}  </math>

[[2차 방정식]]에서
:<math>c(u,v)= d(u,v)=0  </math>이므로
이것은 [[편미분]]과 [[행렬]]에서
:<math>
\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}
</math>
으로 표현될수있다.

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

== 예 ==
:<math>f(x)=6x^5 +11x^4 -33x^3 -33x^2 +11x+6 = 0 </math>

첫 번째 이차 다항식 <math>f(x)</math>의 세 계수로부터 형성된 정규화된 초기값으로 다항식을 설정해보면,
:<math>u={{a_{n-1}}\over{a_n}}={{11}\over{6}},v={{a_{n-2}}\over{a_n}}={{33}\over{6}}</math>
{| class="wikitable" border="1"
|+ 베어스토우 방법의 반복 단계
! 반복횟수
! 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차 방정식]]

== 참고 ==
* [https://archive.org/details/appliedaerodynam00bairrich Applied Aerodynamics,Leonard Bairstow,1920] [[인터넷 아카이브]]
* [https://books.google.co.kr/books/about/Applied_Aerodynamics.html?id=pBZDAAAAIAAJ&redir_esc=y Applied Aerodynamics,Leonard Bairstow,Longmans, Green and Company, 1939]
* [https://www.amazon.com/Applied-Aerodynamics-Leonard-Bairstow/dp/0548999457 Applied Aerodynamics,June 2, 2008]

[[분류:대수학]]
[[분류:근 찾기 알고리즘]]