실제 입방 다항식의 가장 빠른 수치 솔루션?

Question

R 질문 : 실제 계수와 3 개의 실제 뿌리를 가진 것으로 알려진 임의의 입방체를 수치 적으로 해결하는 가장 빠른 방법을 찾고 있습니다. R의 폴리 루트 함수는 복잡한 다항식에 Jenkins-Traub의 알고리즘 419를 사용하는 것으로보고되었지만 실제 다항식의 경우 저자는 이전 작업을 언급합니다. 실제 입방을위한 더 빠른 옵션은 무엇입니까?

Answer 1

위의 Arietta의 대답을 살펴 보았습니다.

> a <- c(1,3,-4)
> m <- matrix(c(0,0,-a[1],1,0,-a[2],0,1,-a[3]), byrow=T, nrow=3)
> roots <- eigen(m, symm=F, only.values=T)$values

위의 Knguyen이 제안한대로 GSL 패키지에서 입방 솔버를 사용하는 것보다 더 빠르거나 느리게하는지 여부는 시스템에서 벤치마킹하는 문제입니다.

Answer 2

신뢰할 수 있고 안정적인 방식 으로이 작업을 여러 번 수행하기위한 수치 솔루션은 다음과 관련이 있습니다. (1) 동반자 행렬을 형성하고 (2) 동반자 행렬의 고유 값을 찾으십시오.

이것이 원래의 것보다 해결하기가 더 어려운 문제라고 생각할 수도 있지만, 이것이 대부분의 생산 코드 (예 : MATLAB)에서 솔루션이 구현되는 방법입니다.

다항식을 위해 :

p(t) = c0 + c1 * t + c2 * t^2 + t^3

동반자 매트릭스는 다음과 같습니다.

[[0 0 -c0],[1 0 -c1],[0 1 -c2]]

그러한 매트릭스의 고유 값을 찾으십시오. 그것들은 원래 다항식의 뿌리에 해당합니다.

이 작업을 매우 빠르게 수행하려면 Lapack에서 단일 가치 서브 루틴을 다운로드하여 컴파일 한 다음 코드에 연결하십시오. 계수 세트가 너무 많으면이를 동시에 수행하십시오.

계수가 있습니다 t^3 하나 인 경우, 이것이 다항식의 경우가 아닌 경우 모든 것을 계수로 나누고 진행해야합니다.

행운을 빕니다.

편집 : Numpy와 Octave는 또한 다항식의 뿌리를 계산하기위한이 방법론에 의존합니다. 예를 들어, 이 링크.

Answer 3

진정한 솔루션을 임의의 다항식 시스템으로 찾는 가장 빠른 알려진 방법 (내가 알고있는) N 변수는 다면체 동종 토피입니다. 자세한 설명은 아마도 Stackoverflow 답변을 넘어선 것일 수 있지만, 본질적으로 Toric Geometries를 사용하여 각 방정식의 구조를 악용하는 경로 알고리즘입니다. 구글이 당신에게 줄 것입니다 많은 논문.

아마도이 질문은 더 적합 할 것입니다 Mathoverflow?

Answer 4

3 개의 뿌리가 모두 필요합니까? 단 하나만 있다면 뉴턴의 방법이 잘 작동 할 것이라고 생각합니다. 3이 모두 있다면 두 개가 서로 가까이있는 상황에서 문제가 될 수 있습니다.

Answer 5

1) 세 가지 뿌리를 찾기 위해 파생 된 다항식 p '를 해결하십시오. 보다 거기 올바르게 수행하는 방법을 알고 있습니다. 그 뿌리 A와 B를 호출하십시오 (a <b)

2) 중간 뿌리의 경우 A와 B 사이에 몇 단계의 이등분을 사용하고 충분히 가까이 있으면 Newton의 방법으로 마무리하십시오.

3) 최소 및 최대 루트의 경우 솔루션을 "사냥"하십시오. 최대 루트의 경우 :

• x0 = b, x1 = b + (b -a)로 시작하십시오. 람다는 람다가 적당한 숫자 (1.6)입니다.
• do x_n = b + (x_ {n -1} -a) * p (x_n) 및 p (b)까지의 람다가 다른 징후를 갖습니다.
• x_ {n -1}과 x_n 사이의 이분학 + 뉴턴을 수행하십시오.

Answer 6

일반적인 방법은 Newton 's Method, Bisection Method, Secant, 고정 지점 반복 등을 사용할 수 있습니다. Google 중 하나.

비선형이있는 경우 체계 한편 고차 뉴턴 사용될 수있다.

Answer 7

GSL 패키지를 살펴 보셨습니까? http://cran.r-project.org/web/packages/gsl/index.html?