2

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

4

7 に答える 7

6

これを信頼できる安定した方法で何度も行うための数値解法には、(1)コンパニオン行列を作成し、(2)コンパニオン行列の固有値を見つけることが含まれます。

これは元の問題よりも解決が難しい問題だと思うかもしれませんが、これがほとんどの実稼働コード(Matlabなど)でのソリューションの実装方法です。

多項式の場合:

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

コンパニオンマトリックスは次のとおりです。

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

そのような行列の固有値を見つけます。それらは元の多項式の根に対応します。

これを非常に高速に行うには、LAPACKから特異値サブルーチンをダウンロードしてコンパイルし、コードにリンクします。係数のセットが多すぎる(たとえば、約100万)場合は、これを並行して実行します。

の係数t^3が1であることに注意してください。これが多項式に当てはまらない場合は、全体を係数で除算してから続行する必要があります。

幸運を。

編集:Numpyとoctaveも、多項式の根を計算するためにこの方法論に依存しています。たとえば、このリンクを参照してください。

于 2010-01-05T01:29:30.543 に答える
4

n個の変数の任意の多項式のシステムが実際の解を見つけるための(私が知っている)最も速い既知の方法は、多面体ホモトピーです。詳細な説明はおそらくStackOverflowの答えを超えていますが、本質的には、トーリックジオメトリを使用して各方程式の構造を活用するパスアルゴリズムです。グーグルはあなたにたくさんの論文を与えるでしょう。

おそらく、この質問はmathoverflowに適していますか?

于 2010-01-05T01:09:26.043 に答える
2

上記のアリエッタの答えを具体化する:

> 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次ソルバーを使用するよりも速いか遅いか(上記のknguyenが示唆しているように)は、システムでのベンチマークの問題です。

于 2010-01-12T16:38:34.677 に答える
1

3つのルートすべてが必要ですか、それとも1つだけが必要ですか?1つだけなら、ニュートン法は問題なく機能すると思います。3つすべての場合、2つが接近している状況では問題が発生する可能性があります。

于 2010-01-05T01:02:50.957 に答える
1

1)微分多項式P'を解いて、3つの根を見つけます。それを正しく行う方法を知るためにそこを参照してください。それらの根をaとbと呼びます(a <b)

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

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の間で二等分+ニュートンを実行します
于 2011-02-25T17:26:24.827 に答える
0

一般的な方法が利用可能です:ニュートン法、二分法、割線、固定小数点反復など。それらのいずれかをグーグルで検索します。

一方、非線形システムがある場合(たとえば、N個の未知数のN個の多項式eqnのシステム)、高次ニュートンなどの方法を使用できます。

于 2010-01-05T01:07:30.743 に答える
0

GSLパッケージhttp://cran.r-project.org/web/packages/gsl/index.htmlを調べてみましたか?

于 2010-01-09T19:37:06.127 に答える