एक (घन) बहुपद की वास्तविक जड़ों को खोजने का एक आसान तरीका क्या है?

Question

यह मेरे लिए एक स्पष्ट प्रश्न जैसा प्रतीत होता है, लेकिन मुझे इसे SO पर कहीं भी नहीं मिला। मेरे पास एक घन बहुपद है और मुझे फ़ंक्शन की वास्तविक जड़ें खोजने की ज़रूरत है। ऐसा करने का तरीका क्या है?

मुझे एक क्यूबिक फ़ंक्शन की जड़ों के लिए कई बंद फॉर्म सूत्र मिल गए हैं, लेकिन उनमें से सभी जटिल संख्या या बहुत से गोनोमेट्रिक फ़ंक्शंस का उपयोग करते हैं और मुझे उन्हें पसंद नहीं है (और यह भी नहीं पता कि कौन से को चुनना है) ।

मुझे कुछ सरल चाहिए; तेजी से बेहतर है; और मुझे पता है कि मुझे अंततः उच्च क्रम के बहुपदों को हल करने की आवश्यकता होगी, इसलिए एक संख्यात्मक सॉल्वर होने से भी मदद मिलेगी। मुझे पता है कि मैं कुछ पुस्तकालय का उपयोग मेरे लिए कड़ी मेहनत करने के लिए कर सकता हूं, लेकिन कहता हूं कि मैं इसे एक अभ्यास के रूप में करना चाहता हूं।

मैं सी में कोडिंग कर रहा हूं, इसलिए import magic_poly_solver, कृपया।

बोनस प्रश्न: मैं केवल दिए गए अंतराल के अंदर जड़ें कैसे पा सकता हूं?

Answer 1

एक घन बहुपद के लिए closed form solutions हैं, लेकिन वे संख्यात्मक गणक के लिए विशेष रूप से उपयुक्त नहीं हैं।

मैं क्यूबिक मामले के लिए निम्नलिखित कार्य करता हूं: किसी भी घन बहुपद में कम से कम एक असली जड़ है, आप इसे न्यूटन की विधि के साथ आसानी से पा सकते हैं। फिर, आप शेष चौथाई बहुपद को हल करने के लिए deflation का उपयोग करें, इस उत्तर चरण को सही तरीके से करने के लिए मेरे उत्तर there देखें।

चेतावनी का एक शब्द: यदि भेदभाव शून्य के करीब है, तो संख्यात्मक रूप से एकाधिक वास्तविक रूट होगी, और न्यूटन की विधि बुरी तरह विफल हो जाएगी। इसके अलावा, रूट के आसपास के लिए, बहुपद (x - x0)^2 की तरह है, आप अपने आधे महत्वपूर्ण अंक खो देंगे (चूंकि पी (एक्स) < ईपीएसलॉन होगा जैसे ही x - x0 < sqrt (epsilon))। तो आप इस नियम को रद्द कर सकते हैं और इस विशेष मामले में बंद फॉर्म समाधान का उपयोग कर सकते हैं, या व्युत्पन्न बहुपद को हल कर सकते हैं।

यदि आप किसी दिए गए अंतराल में जड़ों को ढूंढना चाहते हैं, तो Sturm's theorem देखें।

जेनेरिक बहुपद समाधान के लिए एक अधिक सामान्य (जटिल) एल्गोरिदम Jenkins-Traub algorithm है। यह स्पष्ट रूप से यहां तक ​​कि अधिक है, लेकिन यह क्यूबिक्स पर अच्छी तरह से काम करता है। आमतौर पर, आप किसी तृतीय-पक्ष कार्यान्वयन का उपयोग करते हैं।

चूंकि आप सी करते हैं, GSL का उपयोग करके निश्चित रूप से आपकी सबसे अच्छी शर्त है।

उदाहरण के साथ companion matrix के eigenvalues ​​को खोजने के लिए एक और सामान्य विधि है। संतुलित क्यूआर अपघटन, या घरेलू रूप में कमी। यह जीएसएल द्वारा लिया गया दृष्टिकोण है।

Answer 2

यदि आप बंद समाधानों (या बड़े आदेश के बहुपदों की अपेक्षा करते हैं) का उपयोग नहीं करना चाहते हैं, तो सबसे स्पष्ट विधि Newton's method का उपयोग करके अनुमानित जड़ों की गणना करना होगा।

दुर्भाग्य से यह तय करना संभव नहीं है कि आप जड़ें कब प्राप्त करेंगे, हालांकि यह प्रारंभिक मूल्य पर निर्भर करता है।

here भी देखें।

Answer 3

Solving quartics and cubics for graphics डी हर्बिसन-इवांस द्वारा ग्राफिक्स जेम्स V में प्रकाशित किया गया।

Answer 4

/******************************************************************************* 
* FindCubicRoots solves: 
*  coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0 
* returns: 
*  3 - 3 real roots 
*  1 - 1 real root (2 complex conjugate) 
*******************************************************************************/ 

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]); 

हालांकि सावधानी के

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots