애버스법

애버스 방법 또는 애버스-에를리히 방법, 올리버 애버스와^[1] 루이 W의 이름을 따서 명명되었다.에를리히(^[2]Ehrlich)는 단변 다항식의 모든 뿌리의 동시 근사치를 위해 1967년에 개발된 뿌리 찾기 알고리즘이다.

이 방법은 입체적으로 수렴하는데, 이는 모든 뿌리를 한번에 근사하게 하는 또 다른 알고리즘인 듀란트-케너 방법보다 개선된 것으로, 2차적으로 수렴된다.(단,^[1]^[2] 두 알고리즘 모두 다중 0에서 선형적으로 수렴한다.)^[3]

이 방법은 다항식의 모든 루트를 임의의 정밀도에 근사하기 위한 기준 소프트웨어인 MPSolve에 사용된다.

설명

Let $p(x)=p_{n}x^{n}+p_{n-1}x^{n-1}+\cdots +p_{1}x+p_{0}$ be a univariate polynomial of degree $n$ with real or complex coefficients.그러면 다음과 같은 인자를 주는 $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ 숫자 z $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ z $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ ∗, …, z n $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ $p(x)$ $displaystyle z_{1}^{*},\,$ z_{2}^{*},\ $dots,z_{n}^{$ n}^{*}}, $p(x)$ ( $p(x)$ )의 뿌리인 $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ ${\displaystyle$ p $(x)$ 가 존재한다.

p(x)=p_{n}\cdot (x-z_{1}^{*})\cdot (x-z_{2}^{*})\cdots (x-z_{n}^{*})

그러한 숫자들은 알 수 없지만, 절대값의 상한과 하한은 다항식의 계수로 계산할 수 있다.이제 절대값이 같은 범위 내에 있도록 복잡한 평면에서 $n$ $n$ 개의 $n$ 고유 숫자를 무작위 또는 균등하게 선택할 수 있다. (또한 0이 대칭인 경우 시작점이 같은 축을 따라 정확히 대칭이 되어서는 안 된다. 이는 정합성을 방해할 수 있기 때문이다.)^[1]그러한 숫자의 집합을 $p(x)$ ( x $p(x)$ ) $p(x)$ 의 뿌리 집합의 초기 근사라고 한다 $p(x)$ 이 근사치는 다음 절차를 사용하여 반복적으로 개선할 수 있다.

Let $z_{1},\dots ,z_{n}\in \mathbb {C}$ be the current approximations of the zeros of $p(x)$ . Then offset numbers $w_{1},\dots ,w_{n}\in \mathbb {C}$ are computed as

w_{k}={\frac {p(z_{k}})}{p'(z_{k}}}}}{1-{p_{p}}}}}}}{p_{k}}}}}\cdotsum _{j\cd}{z_{k}-z}-z_{j}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

여기서 $p'(z_{k})$ $p'(z_{k})$ ( $p'(z_{k})$ $p'(z_{k})$ ) ${\displaystyle p'(z_{k}})$ 는 $p'(z_{k})$ $p$ {\ $displaystyle$ p $}$ 의 다항식 파생상품으로, $z_{k}$ $z_{k}$ ${\$ 지점에서 평가된다 $p$ $z_{k}$

$p(x)$ ( $p(x)$ ) $p(x)$ 의 다음 루트 집합은 $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ - w $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ , $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ - w ${\$ n}-{ $n}$ _{n $z_{1}-w_{1},\dots ,z_{n}-w_{n}$ 다항 값이나 오프셋 크기로 현재 근사치의 품질을 측정할 수 있다.

개념적으로 이 방법은 정전기적 유추를 사용하여 근사치 0을 이동 가능한 음점 전하로 모델링하며, 이 0은 고정된 양의 점 전하에 의해 표현되는 참 0으로 수렴한다.^[1]뉴턴의 방법을 각각의 근사치 0에 직접 적용하면 복수의 출발점이 같은 뿌리로 잘못 수렴되는 경우가 많다.애버스트 방법은 이동 전하가 서로에게 미치는 반발 효과를 모델링함으로써 이를 방지한다.이와 같이 이동 가능한 전하가 0에 수렴되면 이들의 전하가 취소되어 다른 이동 전하가 더 이상 그 위치에 끌리지 않게 되어, 다른 이동 전하가 "사용되지 않은" 다른 0에 수렴하도록 유도한다.(스티엘트제스는 정전기 문제에 대한 해결책으로 다항식의 0의 위치를 모델링하기도 했다.)

애버러스 방법의 공식 안에서 뉴턴의 방법과 듀란트-케너 방법의 원소를 찾을 수 있다.효율적인 구현을 위한 세부 사항(예: 양호한 초기 근사 선택의 경우)은 비니(1996)에서 확인할 수 있다.^[3]

뿌리의 업데이트는 Jacobi 유사 동시 반복으로 실행될 수 있다. 이 반복은 첫 번째 모든 새로운 근사치가 구 근사치에서 계산되거나 계산된 시점부터 각각의 새로운 근사치를 사용하는 순차 Gauss-Seel 유사 반복으로 계산된다.

매우 유사한 방법이 뉴턴-매흘리 방법이다.0을 차례차례 계산하지만, 노골적인 디플레이션 대신 이미 획득한 선인자로 즉석에서 나눈다.애버스의 방법은 마지막 루트를 계산하는 뉴턴-매흘리 방법과 같다. 다른 루트를 이미 찾은 척하면서 마지막 루트를 계산하는 것은 뉴턴-매흘리 방법과 같다.^[4]

뉴턴의 방법으로부터의 파생

반복 공식은 함수에 대한 일변량 뉴턴 반복이다.

F(x)={\frac {p(x)}{\prod _{j=1;\,j\neq k}^{n}(x-z_{j}}}}}}}}}

If the values $z_{1},\dots ,z_{n}$ are already close to the roots of $p(x)$ , then the rational function $F(x)$ is almost linear with a dominant root close to $z_{k}$ and poles at $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ , $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ ${\$ 자신과 가까운 p(x)의 뿌리에서 뉴턴 반복을 유도한다 $z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}$ .즉, 해당 어트랙션의 베이스는 다소 작아지는 반면, $z_{k}$ $z_{k}$ ${\$ 에 가까운 루트는 어트랙션 영역이 넓다 $z_{k}$ .

일변량 사례의 ${\tfrac {F(x)}{F'(x)}}$ 뉴턴 단계 ${\tfrac {F(x)}{F'(x)}}$ ( ${\tfrac {F(x)}{F'(x)}}$ ) ${\tfrac {F(x)}{F'(x)}}$ ${\tfrac {F(x)}{F'(x)}}$ ( x ${\tfrac {F(x)}{F'(x)}}$ ) ${\$ 은 로그파생물의 역수 값이다.

{\begin{aligned}{\frac {F'(x)}{F(x)}}&={\frac {d}{dx}}\ln  F(x) \\&={\frac {d}{dx}}{\big (}\ln  p(x) -\sum _{j=1;\,j\neq k}^{n}\ln  x-z_{j} {\big )}\\&={\frac {p'(x)}{p(x)}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{x-z_{j}}}\end{aligned}}

따라서, 새로운 근사치는 다음과 같이 계산된다.

z_{k}'=z_{k}-{\frac {F(z_{k})}{F'(z_{k})}}=z_{k}-{\frac {1}{{\frac {p'(z_{k})}{p(z_{k})}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{z_{k}-z_{j}}}}}\,,

이것은 Averth-Ehrlich 방법의 최신 공식이다.

문학

^ ^a ^b ^c ^d Aberth, Oliver (1973). "Iteration methods for finding all zeros of a polynomial simultaneously". Math. Comp. Mathematics of Computation, Vol. 27, No. 122. 27 (122): 339–344. doi:10.2307/2005621. JSTOR 2005621. Because of the obvious analogy from electrostatics, this field may be called the field of a unit plus charge ... To avoid this, we assign a unit minus charge at each sampling point. The idea here is that when a sampling point z, is near a simple zero, the field from the minus charge at z, should counteract that from the plus charge at the zero, preventing a second sampling point from converging to this zero.
^ ^a ^b Ehrlich, Louis W. (1967). "A modified Newton method for polynomials". Comm. ACM. 10 (2): 107–108. doi:10.1145/363067.363115.
^ ^a ^b Bini, Dario Andrea (1996). "Numerical computation of polynomial zeros by means of Aberth's method". Numerical Algorithms. 13 (2): 179–200. Bibcode:1996NuAlg..13..179B. doi:10.1007/BF02207694.
^ Bauer, F.L.; Stoer, J. (1962). "Algorithm 105: Newton Maehly". Comm. ACM. 5 (7): 387–388. doi:10.1145/368273.368423.

참고 항목

MPSolve 다항식 루트의 수치 계산을 위한 패키지.과학적 목적을 위한 무료 사용.

[:0-1] Aberth, Oliver (1973). "Iteration methods for finding all zeros of a polynomial simultaneously". Math. Comp. Mathematics of Computation, Vol. 27, No. 122. 27 (122): 339–344. doi:10.2307/2005621. JSTOR 2005621. Because of the obvious analogy from electrostatics, this field may be called the field of a unit plus charge ... To avoid this, we assign a unit minus charge at each sampling point. The idea here is that when a sampling point z, is near a simple zero, the field from the minus charge at z, should counteract that from the plus charge at the zero, preventing a second sampling point from converging to this zero.

[:2-2] Ehrlich, Louis W. (1967). "A modified Newton method for polynomials". Comm. ACM. 10 (2): 107–108. doi:10.1145/363067.363115.

[:1-3] Bini, Dario Andrea (1996). "Numerical computation of polynomial zeros by means of Aberth's method". Numerical Algorithms. 13 (2): 179–200. Bibcode:1996NuAlg..13..179B. doi:10.1007/BF02207694.

[4] Bauer, F.L.; Stoer, J. (1962). "Algorithm 105: Newton Maehly". Comm. ACM. 5 (7): 387–388. doi:10.1145/368273.368423.

[1]

[2]

[3]

[4]

Search

애버스법

네임스페이스

더

목차

설명

뉴턴의 방법으로부터의 파생

문학

참고 항목