14

私は自明でない次数（4+）の多項式を持っており、それらが区間[0、T]に根を持っているかどうかをロバストかつ効率的に決定する必要があります。根の正確な位置や数は私には関係ありません。少なくとも1つあるかどうかを知る必要があります。

現在、ルートが存在できないことを証明できるかどうかを確認するためのクイックチェックとして区間演算を使用しています。できない場合は、Jenkins-Traubを使用してすべての多項式の根を解きます。これは、すべての実際のルートをチェックし、それらの正確な位置を見つけるため、明らかに非効率的です。情報は必要ありません。

使用すべき標準的なアルゴリズムはありますか？そうでない場合、すべての根に対して完全なJenkins-Traub解を行う前に、他に効率的なチェックを行うことができますか？

たとえば、私が実行できる最適化の1つは、多項式f（t）が0とTで同じ符号を持っているかどうかを確認することです。そうでない場合は、明らかに区間にルートがあります。もしそうなら、私はf'（t）の根を解き、区間[0、T]のf'のすべての根でfを評価することができます。これらの評価のすべてがf（0）およびf（T）と同じ符号を持っている場合に限り、f（t）はその区間にルートを持ちません。これにより、ルート検索する必要のある多項式の次数が1つ減ります。大きな最適化ではありませんが、おそらく何もないよりはましです。

4

5 に答える 5

16

スツルムの定理を使用すると、範囲内の実根の数を計算できます(a, b)。ルートの数を考えると、少なくとも1つあるかどうかがわかります。このペーパーの4ページの下半分から：

f（x）を実多項式とします。それをf0（x）で表し、その導関数f'（x）をf1（x）で表します。ユークリッドの互除法のように進んで見つけます

f0(x) = q1(x) · f1(x) − f2(x),
f1(x) = q2(x) · f2(x) − f3(x),
.
.
.
fk−2(x) = qk−1(x) · fk−1(x) − fk,

ここで、fkは定数であり、1≤i≤kの場合、fi（x）はfi-1（x）よりも次数が低くなります。剰余の符号は、ユークリッドアルゴリズムの符号から否定されます。

最後の消えない剰余fk（またはfk = 0の場合はfk-1）は、f（x）とf'（x）の最大公約数であることに注意してください。シーケンスf0、f1 、。。。、fk（またはfk = 0の場合はfk-1）は、多項式fのスツルムシーケンスと呼ばれます。

定理1（スツルムの定理）（a、b）に実係数を持つ多項式f（x）の個別の実数ゼロの数は、シーケンスf0（a）の符号の変化の数の超過に等しい。 。、fk-1（a）、fkシーケンスf0（b）、...、fk-1（b）、fkの符号の変化の数。

于 2010-12-23T11:29:22.793 に答える
3

あなたは確かにあなたの区間演算で二分探索をすることができます。[0、T]から始めて、それを多項式に代入します。結果の間隔に0が含まれていない場合は、これで完了です。もしそうなら、間隔を2に分割し、それぞれの半分で繰り返します。このスキームは、各ルートのおおよその位置を非常にすばやく見つけます。

最終的にルートで4つの別々の間隔を取得した場合は、完了したことがわかります。それ以外の場合は、f'（[x、y]）にゼロが含まれない区間[x、y]に到達する必要があると思います。つまり、関数は単調に増加または減少しているため、最大で1つのゼロが含まれます。二重根は問題を引き起こすかもしれません、私はそれについてもっと考えなければならないでしょう。

編集：重根が疑われる場合は、同じ手順を使用してf'の根を見つけます。

于 2010-12-22T02:44:11.217 に答える
1

それほど効率的ではありませんが、非常に信頼性があります。多項式のコンパニオン行列（固有値が多項式の根であるスパース行列）を作成できます。

与えられた間隔で固有値を見つけることができる効率的な固有値アルゴリズムがあります。それらの1つは逆反復です（ある入力値に最も近い固有値を見つけることができます。間隔の中間点を上記の値として指定するだけです）。

于 2010-12-23T11:06:18.330 に答える
1

デカルトの記号の規則を使用して、いくつかの情報を収集します。係数の符号変化の数を数えるだけです。これにより、正の実根の数の上限が得られます。多項式 P を考えます。

P = 131.1 - 73.1*x + 52.425*x^2 - 62.875*x^3 - 69.225*x^4 + 11.225*x^5 + 9.45*x^6 + x^7

実際、ルートの単純なリストを持つように P を構築しました。彼らです...

{-6, -4.75, -2, 1, 2.3, -i, +i}

区間 [0,3] に根があるかどうかを判断できますか? エンドポイントで P の値に符号の変化がないことに注意してください。

P(0) = 131.1
P(3) = 4882.5

P の係数の符号の変化はいくつありますか? 符号の変化は 4 回あるため、4 つの正の根が存在する可能性があります。

しかし、ここで、x を x+3 で P に代入します。

Q(x) = P(x+3) = ...
  4882.5 + 14494.75*x + 15363.9*x^2 + 8054.675*x^3 + 2319.9*x^4 + 370.325*x^5 + 30.45*x^6 + x^7

Q(x) の係数に符号の変化がないことを確認してください。すべての係数は正の値です。したがって、3 より大きい根は存在しません。

したがって、区間 [0,3] には 2 つまたは 4 つの根が存在する可能性があります。

少なくともこれは、わざわざ見る必要があるかどうかを示しています。もちろん、関数が区間の両端に反対の符号を持っている場合、その区間に奇数の根があることがわかります。

于 2010-12-23T00:10:12.410 に答える
0

値の場合f(0)*f(t)<=0、ルートがあることが保証されます。それ以外の場合は、ドメインを2つの部分（二分法）に分割し、そのセグメントにルートがないと確信できるまで、最後の値を確認できます。

どちらかがない場合f(0)*f(t)>0、2、4、..ルート。あなたの限界は多項式の次数です。f(0)*f(t)<0あなたが1、3、5、..ルーツを持っているかもしれないなら。

于 2010-12-22T02:43:45.683 に答える