質問
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のとオクターブもの多項式の根を計算するため、この方法論に依存しています。このリンクの、例えば、参照してください。
N の変数に実際のソリューションに任意の多項式のシステムを見つけるための最速の知られている方法は、(私の知ること)多面体ホモトピーです。詳細な説明は、おそらくStackOverflowの答えを超えているが、基本的にそれはトーリックジオメトリを使用して、各式の構造を利用パスアルゴリズムです。 Googleがあなたの <強いを与えます>論文の数のを。
おそらく、この質問はの mathoverflow のの?
により適していますあなたはすべての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">を使用することができるの高次ニュートン