أسرع حل عددي لمتعدد الحدود المكعب الحقيقي؟

Question

سؤال ص:البحث عن أسرع طريقة لحل عددي لمجموعة من المكعبات العشوائية المعروفة بأن لها معاملات حقيقية وثلاثة جذور حقيقية.تم الإبلاغ عن أن دالة polyroot في R تستخدم خوارزمية Jenkins-Traub 419 لكثيرات الحدود المعقدة، ولكن بالنسبة لكثيرات الحدود الحقيقية يشير المؤلفون إلى أعمالهم السابقة.ما هي الخيارات الأسرع لمتعددة الحدود الحقيقية، أو بشكل عام لمتعددة الحدود الحقيقية؟

Answer 1

جسد إجابة أريتا أعلاه:

> 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

سواء كان ذلك أسرع أو أبطأ من استخدام Solver المكعب في حزمة GSL (كما اقترحه Knguyen أعلاه) هو مسألة معيارها على نظامك.

Answer 2

يتضمن الحل العددي للقيام بذلك عدة مرات بطريقة موثوقة ومستقرة ما يلي:(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 وoctave أيضًا على هذه المنهجية لحساب جذور كثيرات الحدود.انظر على سبيل المثال، هذا الرابط.

Answer 3

أسرع طريقة معروفة (أنني أدرك) للعثور على الحلول الحقيقية نظام متعدد الحدود التعسفية في ن المتغيرات هي homotopy متعدد الهيكلية. من المحتمل أن يكون التفسير التفصيلي يتجاوز إجابة Stackoverflow، ولكنه في الأساس، إنه خوارزمية مسار يستغل بنية كل معادلة باستخدام هندسة Toric. سوف جوجل تعطيك عدد من الأوراق.

ربما هذا السؤال مناسب لأفضل mathoverflow.?

Answer 4

هل تحتاج جميع الجذور الثلاثة أو واحدة فقط؟ إذا كان واحدا فقط، أعتقد أن طريقة نيوتن ستعمل على ما يرام. إذا كان الكل 3، فقد يكون مشكلة في الظروف التي تكون فيها اثنان من القريبة معا.

Answer 5

1) حل ل Verivative متعدد الحدود P "لتحديد موقع جذورك الثلاثة. يرى هناك لمعرفة كيفية القيام بذلك بشكل صحيح. اتصل بتلك الجذور A و B (مع <b)

2) بالنسبة للجذر الأوسط، استخدم بضع خطوات من التهدئة بين A و B، وعندما تكون قريبا بما فيه الكفاية، تنتهي من طريقة Newton.

3) بالنسبة إلى الجذر Min و MAX، "مطاردة" الحل. لجذر ماكس:

• ابدأ ب X0 = B، X1 = B + (B - A) * Lambda، حيث Lambda هو رقم معتدل (يقول 1.6)
• do x_n = b + (x_ {n - 1} - a) * lambda حتى p (x_n) و p (b) لها علامات مختلفة
• أداء التهدئة + نيوتن بين x_ {n - 1} و x_n

Answer 6

تتوفر الأساليب المشتركة: طريقة Newton، طريقة التهدئة، التكرار المخصص، نقطة ثابتة، إلخ. جوجل أي واحد منهم.

إذا كان لديك غير خطي النظام من ناحية أخرى (على سبيل المثال نظام على متعدد الحدود EQN في N غير معروف)، طريقة مثل نيتون عالي الجودة يمكن استخدامها.

Answer 7

هل حاولت النظر في حزمة GSL http://cran.r-project.org/web/packages/gsl/index.html.?