問題タブ [polynomial-math]

4 次関数の根を計算する必要がある高度な衝突検出を行う状況に遭遇しました。

ここで見られるように、フェラーリの一般的なソリューションを使用して正常に動作するように見える関数を作成しました: http://en.wikipedia.org/wiki/Quartic_function#Ferrari.27s_solution。

これが私の機能です：

唯一の問題は、いくつかの例外があるように見えることです。最も顕著なのは、2 つの実根と 2 つの虚根がある場合です。

たとえば、次の式: y = 0.9604000000000001x^4 - 5.997600000000001x^3 + 13.951750054511718x^2 - 14.326264455924333x + 5.474214401412618

ルートを返します: 1.7820304835380467 + 0i 1.34041662585388 + 0i 1.3404185025061823 + 0i 1.7820323472855648 + 0i

その特定の方程式をグラフにすると、実際の根が (およそ) 1.2 と 2.9 に近いことがわかります。4 つの間違った根をランダムとして無視することはできません。これらは実際には方程式の一次導関数の根の 2 つだからです。

y = 3.8416x^3 - 17.9928x^2 + 27.9035001x - 14.326264455924333

私が実際に投稿した方程式の特定の根を探しているわけではないことに注意してください。私の質問は、私が考慮していない特殊なケースがあるかどうかです。

何か案は？

バックグラウンド

Fortran90 / 95のホーナー法を使用して、複数の変数の多項式を解く必要があります。これを行う主な理由は、ホーナー法を使用して多項式を評価するときに発生する効率と精度の向上です。

私は現在、単変量/単変量多項式に対するホーナー法の実装を持っています。ただし、ホーナー法を使用して多変量多項式を評価する関数を開発することは、私を超えていることが証明されています。

二変量多項式の例は次のとおりです。12x^2y^ 2 + 8x ^ 2y + 6xy ^ 2 + 4xy + 2x + 2yこれはx（x（y（12y + 8））+ y（6y + 4）+2に因数分解されます）+ 2y次に、xとyの特定の値について評価されます。

リサーチ

調査を行ったところ、次のような多数の論文が見つかりました：
staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf
citeseerx.ist.psu.edu/viewdoc/download ？doi = 10.1.1.40.8637＆rep = rep1＆type = pdf
www.is.titech.ac.jp/~kojima/articles/B-433.pdf

問題

しかし、私は数学者でもコンピューター科学者でもないので、アルゴリズムやアイデアを伝えるために使用される数学に問題があります。

私が知る限り、基本的な戦略は、多変量多項式を個別の単変量多項式に変換し、そのように計算することです。

誰か助けてもらえますか？誰かが私が自分でFortranに実装できる疑似コードにアルゴリズムを変換するのを手伝ってくれるなら、私は非常にありがたいです。

部分和問題を解くための新しいアルゴリズムを思いついたのですが、それは多項式時間だと思います。私が間違っているか、天才だと言ってください。

クイックスターターファクト：

部分和問題はNP完全問題です。多項式時間でそれを解くことは、P=NPを意味します。
長さNのセット内のサブセットの数は2^Nです。

より有用な一方で、長さNの一意のサブセットの数は、最大でセット全体の合計から最小の要素を引いたものです。または、サブセットが生成できる可能性のある合計の範囲は、すべての負の要素の合計の間にあります。そして、すべての正の要素の合計。これは、すべての正または負の合計よりも大きいまたは小さい合計はあり得ないためです。これらの合計は、要素を追加すると線形速度で増加します。

これが意味するのは、Nが増加すると、重複するサブセットの数が指数関数的に増加し、一意で有用なサブセットの数が直線的にのみ増加することです。可能な限り早い機会に重複サブセットを削除できるアルゴリズムを考案できれば、多項式時間で実行できます。簡単な例は、バイナリから簡単に取得できます。2の累乗である数値のみから、任意の整数値に対して一意のサブセットを作成できます。そのため、他の数を含むサブセット（2の累乗がすべてある場合）は重複していて無駄です。それらとその導関数を計算しないことにより、2の累乗である数値が任意の整数と比較して対数的に発生するため、アルゴリズムの実行時間を実質的にすべて節約できます。

そのため、これらの重複を削除し、それらとそのすべての導関数を計算する必要をなくす単純なアルゴリズムを提案します。

まず、O（N log N）のみのセットを並べ替え、正と負の2つに分割します。負の数の手順は同じなので、正の数の概要のみを説明します（明確にするために、セットは正の半分だけを意味します）。

sumでインデックス付けされた配列を想像してみてください。この配列には、正の側のすべての可能な結果の合計のエントリがあります（線形のみです。覚えておいてください）。エントリを追加すると、値はサブセット内のエントリになります。したがって、array [3] = {1、2}のようになります。

一般に、セット内のすべてのサブセットを列挙するように移動します。これを行うには、1つの長さのサブセットから始めて、それらに追加します。すべての一意のサブセットがある場合、それらは配列を形成し、Horowitz/Sahniで使用されている方法でそれらを単純に反復します。

ここで、「第1世代」の値から始めます。つまり、元のデータセットに重複する数値がなかった場合、これらの値に重複がないことが保証されます。つまり、すべての単一値サブセット、およびセットのすべての長さから1つの長さのサブセットを引いたものです。これらは、セットを合計し、各要素を順番に減算することで簡単に生成できます。さらに、セット自体は、有効な第1世代の合計とサブセット、およびサブセットの個々の要素です。

次に、第2世代の値を実行します。配列内の各値をループし、一意のサブセットごとに、値がない場合はそれを追加して、新しい一意のサブセットを計算します。重複していると、楽しいことが起こります。衝突リストに追加します。新しいサブセットを追加するときは、それらが衝突リストにあるかどうかを確認します。あまり望ましくない（通常は大きいが、任意である可能性がある）等しいサブセットによってキーを設定します。サブセットに追加する場合、衝突が発生したとしても、何もしません。より望ましいサブセットを追加する場合、チェックを見逃して追加し、共通のサブセットを生成します。その後、他の世代のために繰り返します。

この方法で重複サブセットを削除することにより、重複をセットの残りの部分と結合し続ける必要も、衝突をチェックし続ける必要も、合計する必要もありません。最も重要なことは、一意ではない新しいサブセットを作成しないことで、それらから新しいサブセットを生成しないことです。これにより、アルゴリズムがNPからPに変わる可能性があります。これは、サブセットの成長が指数関数的ではなくなったためです。破棄します。それらの大部分は、次世代で「複製」し、他の重複しないサブセットと組み合わせることによって、より多くのサブセットを作成する前に行われます。

私はこれをあまりよく説明していないと思います。私は写真を持っています...それらは私の頭の中にあります。重要なことは、重複するサブセットを破棄することで、実質的にすべての複雑さを取り除くことができるということです。

たとえば、（この例を手作業で行っているため）ゼロを目指す-7から7（ゼロではない）の単純なデータセットを想像してみてください。並べ替えて分割すると、（1、2、3、4、5、6、7）が残ります。合計は28です。ただし、2 ^ 7は128です。したがって、128個のサブセットが1 .. 28の範囲に収まります。つまり、100セットが重複していることが事前にわかっています。8の場合、スロットは36しかありませんが、サブセットは256になります。したがって、重複の数が以前の2倍を超える220になっていることが簡単にわかります。

この場合、第1世代の値は1、2、3、4、5、6、7、28、27、26、25、24、23、22、21であり、それらを構成コンポーネントにマップします。

ここで、新しいサブセットを生成するために、各サブセットを順番に取得し、相互サブセットがない限り、他のサブセットに追加します。たとえば、28と27にはhueg相互サブセットがあります。したがって、1を取得して2に追加すると、3 = {1、2}になりますが、お待ちください。すでにアレイに含まれています。これが意味するのは、すでに2が含まれているサブセットに1を追加しないこと、およびその逆のことです。これは、3のサブセットと重複しているためです。

今、私たちは持っています

ここで、すべてに2を追加します。

3？

ご覧のとおり、毎回新しいサブセットを追加していますが、量は直線的にしか増加していません。

4？

5？

これで範囲内のすべての値が得られたので、停止してリスト1-28に追加します。負の数について繰り返し、リストを繰り返します。

編集：

このアルゴリズムは、どのような場合でも完全に間違っています。合計が重複しているサブセットは、到達方法が異なるため、つまり、折りたたむことができないため、サブセットを生成できる目的で重複することはありません。

多項式 P があり、P(y) = 0 modulo 2^r となるような y を見つけたいと思います。

私はヘンセルリフティングに沿って何かを試しましたが、通常は真ではない通常の条件 f'(y mod 2) != 0 mod 2 のため、これが機能するかどうかはわかりません。

利用可能な別のアルゴリズムはありますか? それとも、ヘンゼル リフティングのバリエーションが機能する可能性がありますか?

前もって感謝します

方程式y=3（x + 1）^ 2 + 5（x + 1）^4があります。

ホーナーのスキームを使用して、この多項式をこの形式で評価できます。y= 8 + x（26 + x（33 + x（20 + 5x）））、したがって8つの算術演算が必要です。

y =（x + 1）^ 2 *（（5x + 10）x + 8）の形式で評価することもでき、7回の操作が必要です。

これは5つの操作で実行できると言われていますが、ホーナーのアルゴリズムが最も効率的であると考えられており、7つの操作でしか実行できません。私は何かが足りないのですか？

この質問に対する回答を読みましたが、非常に役に立ちますが、助けが必要です。

次のように、Rにサンプルデータセットがあります。

モデルをこれらのデータに当てはめたいので、y = f(x). 3次多項式モデルにしたい。

Rでそれを行うにはどうすればよいですか？

さらに、R は最適なモデルを見つけるのに役立ちますか?

3次元点の多項式回帰ルーチンを作成するためのいくつかのポインターが必要です（つまり、特定の数の3D点に適合するX次多項式の係数を見つけます）。

2D多項式回帰のコードを見つけましたが、3次元を考慮する必要があります。

コード例や説明を探しています。

2次3次または4次多項式の根を解くなど、「単純な」数学計算に使用するのに最適なオンラインスクリプト言語は何でしょうか。

たとえば、ここにあるような小さなWeb「アプレット」を作成すると、テキストボックスに入力された値が挿入され、変数として「二次方程式」に入力され、2つのx値が解かれます。

プレーンJavaScriptは、これに使用するのに最適なスクリプト言語ですか？IMO、これがサーバー側である必要は実際にはありません。

二次方程式を解くためにJavaScriptのMathプロパティのいくつかを呼び出す必要がある、いくつかの「複雑な」数学を実行しようとしています。次の方法は機能しますか？

これは正しいように見えますか？

何らかの理由で、正しい結果が表示されません。

inputa、、、inputbおよびinputcはすべて、テキストフィールドからのユーザー入力を格納する変数です。

フルコード

多項式の根を求めた場合Mathematica、これをシンボリックに行っても、これらの正確な答えの数値近似を見つけても、数値的に行っても、同じ (近似) 答えが得られるはずです。これがひどく失敗する例 ( Mathematica 7OS X で実行中) を次に示します。

(注: これは実際にはローラン多項式であり、大きな累乗を掛けるとq問題は解決します。)

ここの最後の行は、見つかったソリューションが非常に異なることを示すだけです。実際、それは私たちが取り組んでいた問題で計算しようとしていた量です。

NSolve[poly == 0, q]との出力をよく見るとN[Solve[poly == 0, q]、NSolve54が予想される ではなく根しか与えないことがわかります56。繰り返されるルートなどを見逃しただけではありません。等級の 2 つの最大根がありません (約+/- 1.59)

これは Mathematica のバグですか？なぜこれが起こっているのか、誰にも説明がありますか？