実数三次多項式の最速の数値解法は?

StackOverflow https://stackoverflow.com/questions/2003465

  •  18-09-2019
  •  | 
  •  

質問

Rの質問:実数係数と 3 つの実数根を持つことが知られている一連の任意の 3 次関数を数値的に解く最速の方法を探しています。R のポリルート関数は、複素多項式に対して Jenkins-Traub のアルゴリズム 419 を使用すると報告されていますが、実多項式については、著者は以前の研究を参照しています。実三次関数、またはより一般的には実多項式の場合、より高速なオプションは何ですか?

役に立ちましたか？

解決

上記のアリエッタの答えを具体的にすると、次のようになります。

> 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

これが GSL パッケージの 3 次ソルバーを使用するよりも速いか遅いかは、システムでのベンチマークの問題です。

他のヒント

、信頼性の高い、安定した状態で、この何度も行うための数値解法を伴う：（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のとオクターブもの多項式の根を計算するため、この方法論に依存しています。このリンクの、例えば、参照してください。

あなたはすべての3つのルートまたは1つだけ必要ですか？一つだけならば、私はニュートン法がOKに働くだろうと思うだろう。もし全ての3それは、2つの近接している状況では問題となる可能性があります。

1) 導関数多項式 P' を解き、3 つの根を見つけます。見る そこには それを適切に行う方法を知るためです。これらのルートを a および b (a < b) と呼びます。

2) 中央のルートについては、a と b の間で数ステップの二等分を使用し、十分に近づいたら、ニュートン法で終了します。

3) 最小ルートと最大ルートについては、ソリューションを「ハント」します。最大ルートの場合:

  • x0 = b、x1 = b + (b - a) * lambda から始めます。ここで、lambda は適度な数 (たとえば 1.6)
  • P(x_n) と P(b) の符号が異なるまで x_n = b + (x_{n - 1} - a) * ラムダを実行します
  • x_{n - 1} と x_n の間で二等分 + ニュートンを実行します

一般的な方法が用意されています。ニュートン法、二分法、割線、定点反復などGoogleのそれらのいずれか

あなたは一方で非直線をのシステムの持っている場合（例えば、N個の未知数Nの多項式EQNのオンシステム）は、そのような<のhref = "HTTPなどの方法：// EN。 wikipedia.org/wiki/Newton%27s_method#Nonlinear_systems_of_equations」REL = "nofollowをnoreferrer">を使用することができるの高次ニュートン

あなたはGSLパッケージます。http：// CRAN .R-project.org /ウェブ/パッケージ/ GSL / index.htmlをに？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top