베어스토의 방법

이 기사는 주요 출처에 대한 언급에 너무 많이 의존하고 있다. 이차 또는 3차 소스를 추가하여 개선하십시오.(2018년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수치해석에서는 베어스토우(Bairstow)의 방법이 임의도의 실제 다항식의 뿌리를 찾는 효율적인 알고리즘이다.이 알고리즘은 레너드 베어스토우의 1920년 저서 Apply Aerodynamics의 부록에 처음 등장했다.^{[1][non-primary source needed]}이 알고리즘은 실제 산술만을 사용하여 복잡한 결합 쌍에서 뿌리를 찾는다.

다른 알고리즘은 루트 찾기 알고리즘을 참조하십시오.

방법 설명

베이르스토우의 접근법은 뉴턴의 방법을 사용하여 $2차{\displaystyle {}^{}}$ x 2${\displaystyle {}^{}}$+ u ${\displaystyle x}$+$$ {\$displaystyle$ x$^{2}+ux+v}$의 계수 u와 v를 그 뿌리가 풀리는 다항식의 뿌리가 될 때까지$$ 조정하는 것이다.그러면 이차근의 뿌리가 결정될 수 있고, 다항근은 이차근으로 나누어 그 뿌리를 제거할 수 있다.이 과정은 다항식이 2차 또는 선형이 될 때까지 반복되며, 모든 뿌리가 결정된다.

해결할 다항식의 긴 분할

${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}}}}$

$x{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$+ ${\displaystyle u}$ x${\displaystyle }$+ ${\displaystyle v}$ + v + v + ${\displaystyle x^{2}+ux$$+v$$}$에 의해 $Q{\displaystyle (x\underset{}{\overset{}{}})}$=${\displaystyle \underset{0}{\overset{}{}}}$ n${\displaystyle \underset{}{\overset{}{}}}$- ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle {bi}^{}}$ i$${\$displaystyle$ Q$(x)=\sum$_{$i=0}^{n-2}b_{i$}x$^{i$}}}}}}}}}}}과$$$$(x^{i$}$d)의 나머지 $cx$+ ${\displaystyle d}$ ${\d$)가$$ 산출된다$.$

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

A second division of ${\displaystyle Q(x)}$ by ${\displaystyle x^{2}+ux+v}$ is performed to yield a quotient ${\displaystyle R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}}$ and remainder ${\displaystyle gx+h}$ with

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

변수 $c{\displaystyle }$, ${\displaystyle d}$, ${\displaystyle g}$, h , ${\displaystyle h}$ ${\displaystyle$ c$,\,d,\,g,\,h$${\displaystyle }${${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle \{b_${i$}\},\;{f_{i$$}\\\\\displaysty u}$ 및 v}의 함수$$$.$그것들은 다음과 같이 재귀적으로 발견될 수 있다.

${\displaystyle {\begin{aligned}b_{n}&=b_{n-1}=0,&f_{n}&=f_{n-1}=0,\\b_{i}&=a_{i+2}-ub_{i+1}-vb_{i+2}&f_{i}&=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\ldots ,0),\\c&=a_{1}-ub_{0}-vb_{1},&g&=b_{1}-uf_{0}-vf_{1},\\d&=a_{0}-vb_{0},&h&=b_{0}-vf_{0}.\end{정렬}}}$

2차적 분포는 다음과 같은 경우 다항식을 고르게 나눈다.

${\displaystyle c(u,v)=d(u,v)=0.\,}$

$이{\displaystyle }$$$ 문제가 발생하는$$u {\$displaystyle u}$ 및$$ $v{\displaystyle }$ ${\displaystyle v}$ 값은 시작 값을 선택하고 뉴턴의 방법을 2차원으로 반복하여 검색할 수 있다.

${\displaystyle {\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}}:={\\bmatrix}u\\v\end{bmatrix}-{vg^{1}{vg^{2}+h(h-ug)}}{{\\\\\\\\\\\\\\\\}}{\not{bmatrix}-gv&g-h\[3pt]-gmatrix}}{bmatrix}}}}}}$

융합이 이루어질 때까지따라서 다항식의 영점을 찾기 위한 이 방법은 프로그래밍 언어 또는 스프레드시트로 쉽게 구현될 수 있다.

예

과제는 다항식의 한 쌍의 뿌리를 결정하는 것이다.

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

첫 번째 2차 다항식으로서 f(x)의 선행 3개 계수에서 형성된 정규화된 다항식을 선택할 수 있다.

${\displaystyle u={\frac {a_{n-1}{n1}}={\frac {11}{6}}}=\\frac v={a_2}}:{n}}=-{\frac {33}{6}\,},}$

그런 다음 반복을 통해 테이블이 생성된다.

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

Nr	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차 인자를 생성했다.네 번째 반복으로부터의 스텝 길이는 수렴의 초선형 속도를 보여준다.

퍼포먼스

베어스토우 알고리즘은 뉴턴 방법의 국소 이차적 수렴을 계승하는데, 그 인자에 대한 수렴이 선형일 때 1보다 높은 다중의 이차적 인자의 경우는 예외로 한다.다항식의 정도가 홀수이고 실제 뿌리가 하나만 있을 때 특정한 종류의 불안정성이 관찰된다.이 진짜 뿌리에서 작은 값을 갖는 이차적 요인들은 무한대로 분산되는 경향이 있다.

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

이미지는 쌍[− 3,3]2{\displaystyle(s,t)\in[-3,3]^{2}∈(s, t)}., 선형 요인에 뿌리는 그것과 0해당한다도±나는 계영 2+ux+에 v=()−는 그것)2+t2{\displaystyle x^{2}(x-s)^{2}+t^{2}}. 꼭 낮다{\displaystyle s\pm 그것}, 상대방은 상반신을 비행기 t을에 지점을 나타낸다. halF비행기 밀폐된<>2차 요인에 뿌리의±t{\displaystyles\pm지}과 0해당한다, 그, x2+ux은+v=()−는 그것)2− t2{\displaystyle x^{2}(x-s)^{2}-t^{2}}, 일반적으로 WTF는 따라 색을 그렇게(u, v))(− 2s, s2+tt){\displaystyle(u,\,v)=(-2s,\,s^{2}+t\ t)}..로베어스토 반복의 마지막 지점, 검은 점들은 서로 다른 행동을 나타낸다.

첫 번째 이미지는 단일 실제 루트 케이스의 시연이다.두 번째는 융합 속도를 늦추는 비용으로 실제 근원을 추가 도입해 상이한 행동을 고칠 수 있다는 의미다.또한 홀수 도 다항식의 경우 뉴턴의 방법 및/또는 구간 수축 방법을 사용하여 실제 뿌리를 먼저 찾을 수 있으므로 디플레이션 후 더 나은 행동의 고른 도 다항식이 남게 된다.세 번째 이미지는 위의 예와 일치한다.

참조

외부 링크

• 배어스토우 알고리즘
• Fortran 77 온라인에서의 수치적 조리법
• Bairstow의 방법을 사용한 다항식 루트 솔버(deg(P) ≤ 10)의 예
• LinBairstowSolve, VTK 라이브러리의 방법으로 이용할 수 있는 Lin-Bairstow 방식의 오픈 소스 C++ 구현
• Farhad Mazlumi에 의한 다항식의 온라인 루트 발견 - 베어스토우 방법