Vincent's theorem
ریاضی میں، ونسنٹ کا نظریہ-جس کا نام الیگزینڈر جوزف ہڈلف ونسنٹ کے نام پر رکھا گیا ہے-ایک نظریہ ہے جو کثیر الجہتی کی حقیقی جڑوں کو عقلی گتانک کے ساتھ الگ کرتا ہے۔ اگرچہ ونسنٹ کا نظریہ کثیر الجہتی کی حقیقی جڑوں کو الگ کرنے کے تیز ترین طریقہ کار کی بنیاد ہے، لیکن اسے تقریبا مکمل طور پر فراموش کر دیا گیا تھا، جسے اسٹرم کے نظریہ نے چھایا ہوا تھا۔ اس کے نتیجے میں، یہ نظریہ مساوات (20 ویں صدی کی) پر کسی بھی کلاسیکی کتاب میں ظاہر نہیں ہوتا ہے، سوائے یوسپنسکی کی کتاب کے۔ اس تھیوریم کی دو قسمیں پیش کی گئی ہیں، ان کے ساتھ ساتھ ان سے اخذ کردہ کئی (مسلسل فریکشن اور بائیسیکشن) حقیقی جڑ کی علیحدگی کے طریقے بھی پیش کیے گئے ہیں۔ علامت کی تغیرات c0، c1، c2،. حقیقی اعداد کی ایک محدود یا لامحدود ترتیب ہونے دیں۔ فرض کریں کہ l <r اور مندرجہ ذیل شرائط برقرار ہیں: اگر r = l + 1 ہے تو اعداد کل اور کر کے مخالف نشانات ہیں۔ اگر r ≤ l + 2 تو اعداد کل + 1،.، کر-1 تمام صفر ہیں اور اعداد کل اور کر مخالف نشانات رکھتے ہیں۔ اسے کل اور کر اعداد کے درمیان علامت کی تبدیلی یا علامت کی تبدیلی کہا جاتا ہے۔ ایک متغیر میں کثیر الجہتی p (x) سے نمٹتے وقت، p (x) کے اشاروں کے تغیرات کی تعداد کو اس کے گتانک کی ترتیب میں اشاروں کے تغیرات کی تعداد کے طور پر بیان کیا جاتا ہے۔ اس تھیوریم کے دو ورژن پیش کیے گئے ہیں: ونسنٹ کی وجہ سے مسلسل فریکشن ورژن، اور الیسینا اور گلوزی کی وجہ سے بائیسیکشن ورژن۔ ونسنٹ تھیوریم: مسلسل فریکشن ورژن (1834 اور 1836) اگر ایک کثیر الجہتی مساوات میں عقلی گتانک کے ساتھ اور متعدد جڑوں کے بغیر، کوئی اس شکل کی یکے بعد دیگرے تبدیلیاں کرتا ہے جہاں کوئی مثبت تعداد ایک سے زیادہ یا اس کے برابر ہوتی ہے، تو اس طرح کی متعدد تبدیلیوں کے بعد، نتیجے میں تبدیل شدہ مساوات میں یا تو صفر علامت کی تغیرات ہوتی ہیں یا اس میں واحد علامت کی تغیرات ہوتی ہیں۔ پہلی صورت میں کوئی جڑ نہیں ہے، جبکہ دوسری صورت میں ایک واحد مثبت حقیقی جڑ ہے۔ مزید برآں، مجوزہ مساوات کی متعلقہ جڑ کا تخمینہ محدود مسلسل فریکشن سے لگایا جاتا ہے: مزید برآں، اگر اس خاصیت کو مطمئن کرنے والے لامحدود تعداد میں پائے جا سکتے ہیں، تو جڑ کی نمائندگی (لامحدود) متعلقہ مسلسل فریکشن سے کی جاتی ہے۔ مندرجہ بالا بیان ونسنٹ کے اصل کاغذات میں پائے جانے والے نظریہ کا عین مطابق ترجمہ ہے۔ تاہم، واضح تفہیم کے لیے درج ذیل تبصرے درکار ہیں: اگر n متبادلات کے بعد حاصل کردہ کثیر الجہتی کی نشاندہی کرتا ہے (اور ڈینومینیٹر کو ہٹانے کے بعد)، تو N اس طرح موجود ہے کہ سب کے لیے یا تو کوئی نشانی تغیر نہیں ہے یا اس میں ایک علامت تغیر ہے۔ مؤخر الذکر صورت میں سب کے لیے ایک واحد مثبت حقیقی جڑ ہے۔ مسلسل حصہ اصل مساوات کے مثبت جڑ کی نمائندگی کرتا ہے، اور اصل مساوات میں ایک سے زیادہ مثبت جڑ ہو سکتی ہے۔ مزید برآں، یہ فرض کرتے ہوئے کہ ہم صرف اصل مساوات کی جڑ حاصل کر سکتے ہیں جو کہ> 1 ہے۔ صوابدیدی مثبت جڑ حاصل کرنے کے لیے ہمیں یہ فرض کرنے کی ضرورت ہے۔ منفی جڑیں x کو −x سے بدل کر حاصل کی جاتی ہیں، ایسی صورت میں منفی جڑیں مثبت ہو جاتی ہیں۔ ونسنٹ تھیوریم: بائیسیکشن ورژن (الیسینا اور گالوزی 2000) فرض کریں کہ پی (ایکس) ڈگری ڈیگ (پی) کا ایک حقیقی کثیر الجہتی ہے جس کی صرف سادہ جڑیں ہیں۔ مثبت مقدار δ کا تعین کرنا ممکن ہے تاکہ مثبت حقیقی اعداد کے ہر جوڑے a، b کے ساتھ، شکل کے ہر تبدیل شدہ کثیر الجہتی میں بالکل 0 یا 1 علامت کی تغیرات ہوں۔ دوسرا معاملہ اس صورت میں ممکن ہے جب p (x) کا (a، b) کے اندر ایک ہی جڑ ہو۔ الیسینا-گلوزی "اے بی روٹس ٹیسٹ" مساوات () سے درج ذیل معیار حاصل کیا جاتا ہے تاکہ یہ طے کیا جا سکے کہ آیا کسی کثیر الجہتی کی وقفہ (اے، بی) میں کوئی جڑیں ہیں: پی (ایکس) پر متبادل انجام دیں اور تبدیل شدہ کثیر الجہتی کے گتانک کی ترتیب میں علامت کے تغیرات کی تعداد شمار کریں۔ یہ نمبر کھلے وقفہ (اے، بی) کے اندر حقیقی جڑوں پی (ایکس) کی تعداد پر ایک اوپری حد دیتا ہے۔ مزید واضح طور پر، R [x] میں کثیر الجہتی p (x) کے کھلے وقفے (a، b)-ضرب شمار میں حقیقی جڑوں کی تعداد ρab (p)، ڈگری ڈگری ڈگری (p) کی، اوپر نشان کی تغیرات کی تعداد سے منسلک ہے، جہاں جیسا کہ ڈیکارٹس کے اصولوں کے مطابق اگر وراب (p) = 0 ہے تو یہ ρab (p) = 0 کی پیروی کرتا ہے اور اگر وراب (p) = 1 ہے تو یہ ρab (p) = 1 کی پیروی کرتا ہے۔ الیسینا-گلوزی "اے بی روٹس ٹیسٹ" کا ایک خاص معاملہ بوڈن کا "0 _ 1 روٹس ٹیسٹ" ہے۔ ثبوت کا خاکہ ونسنٹ کے نظریہ کی تفصیلی بحث، اس کی توسیع، اس میں شامل تبدیلیوں کی ہندسی تشریح اور تین مختلف ثبوت الیسینا اور گلوزی کے کام میں مل سکتے ہیں۔ چوتھا ثبوت آسٹرووسکی کی وجہ سے ہے جس نے اوبریشکوف، صفحہ 81، کی طرف سے 1920-1923 میں بیان کردہ تھیوریم کا ایک خاص کیس دوبارہ دریافت کیا۔ ونسنٹ کے نظریہ کو ثابت کرنے کے لیے (دونوں ورژن) الیسینا اور گالوزی سے پتہ چلتا ہے کہ نظریہ میں مذکور تبدیلیوں کے ایک سلسلے کے بعد، ایک مثبت جڑ والے کثیر الجہتی میں بالآخر ایک علامت کی تبدیلی ہوتی ہے۔ اسے ظاہر کرنے کے لیے، وہ پہلے مذکور 1920-1923 کے اوبریشکوف کے نظریہ کے لیے درج ذیل نتیجہ کا استعمال کرتے ہیں۔ یعنی، درج ذیل نتیجہ ضروری شرائط فراہم کرتا ہے جس کے تحت ایک مثبت جڑ والے کثیر الجہتی کے کوفشنٹس کی ترتیب میں بالکل ایک علامت کی تغیر ہوتی ہے۔ متعلقہ اعداد و شمار کو بھی دیکھیں۔ کورلری۔ (اوبریشکوف کا شنک یا سیکٹر تھیوریم، 1920-1923 p. 81): اگر ایک حقیقی کثیر الجہتی کا ایک سادہ جڑ ہے، اور دیگر تمام (ممکنہ طور پر متعدد) جڑیں سیکٹر میں ہیں تو اس کے کوفیشنٹس کی ترتیب میں بالکل ایک علامت کی تبدیلی ہوتی ہے۔ اب موبیئس کی تبدیلی اور متعلقہ شکل میں دکھائے گئے تین حلقوں پر غور کریں۔ فرض کریں کہ (پیلا) دائرہ جس کا قطر حقیقی محور پر ہے، اختتامی نکات کے ساتھ اور خیالی محور پر الٹا موبیئس کی تبدیلی کے ذریعے نقشہ بنایا گیا ہے۔ مثال کے طور پر نقطہ کو نقطہ پر نقشہ بنایا جاتا ہے۔ بیرونی نکات کو نصف سطح پر نقشہ بنایا جاتا ہے۔ مرکز اور رداس کے ساتھ دو دائرے (صرف ان کے نیلے ہلال نظر آتے ہیں) کو لائنوں پر الٹا موبیئس تبدیلی کے ذریعے نقشہ بنایا جاتا ہے۔ مثال کے طور پر نقطہ کو اس نقطہ پر نقشہ بنایا جاتا ہے بیرونی نکات (جو آٹھ شکل کے اعداد و شمار سے باہر ہیں) کو سیکٹر پر نقشہ بنایا جاتا ہے۔ مذکورہ بالا سے یہ واضح ہو جاتا ہے کہ اگر کسی کثیر الجہتی کی آٹھ شکل کی شکل کے اندر ایک ہی مثبت جڑ ہے اور دیگر تمام جڑیں اس سے باہر ہیں، تو یہ اس کے گتانک کی ترتیب میں ایک علامت کی تغیر پیش کرتا ہے۔ یہ عمل کے خاتمے کی ضمانت بھی دیتا ہے۔ تاریخی پس منظر ونسنٹ کے نظریہ کی ابتدائی ایپلی کیشنز اپنے بنیادی مقالے میں، ونسنٹ نے ایسی مثالیں پیش کیں جو واضح طور پر ظاہر کرتی ہیں کہ مسلسل حصوں کے ساتھ کثیر الجہتی کی حقیقی جڑوں کو الگ کرنے کے لیے اپنے نظریہ کو کس طرح استعمال کیا جائے۔ تاہم اس کے نتیجے میں آنے والے طریقہ کار میں ایکسپونینشیل کمپیوٹنگ ٹائم تھا، یہ ایک حقیقت ہے کہ ریاضی دانوں کو اس وقت احساس ہوا ہوگا، جیسا کہ ایک صدی بعد یوسپنسکی پی۔ 136 نے محسوس کیا تھا۔ ونسنٹ کے الگورتھم کی ایکسپونینشل نوعیت جزوی کوٹینٹس AI (ونسنٹ کے تھیوریم میں) کے حساب لگانے کے طریقے کی وجہ سے ہے۔ یعنی، ہر جزوی حصص AI کا حساب لگانے کے لیے (یعنی، یہ معلوم کرنے کے لیے کہ x-محور پر جڑیں کہاں ہیں) ونسنٹ بوڈن کے نظریہ کو "کوئی جڑ ٹیسٹ نہیں" کے طور پر استعمال کرتا ہے ؛ دوسرے لفظوں میں، جڑ کا عدد حصہ تلاش کرنے کے لیے ونسنٹ x-1x + 1 کی شکل کے یکے بعد دیگرے متبادل انجام دیتا ہے اور صرف اس صورت میں رکتا ہے جب کثیر الجہتی p (x) اور p (x + 1) اپنے کوفشنٹس کی ترتیب میں اشارے کے تغیرات کی تعداد میں مختلف ہوں (یعنی۔ جب p (x + 1) کے نشان کے تغیرات کی تعداد کم ہو جائے)۔ متعلقہ خاکہ دیکھیں جہاں جڑ وقفہ (5، 6) میں ہے۔ یہ آسانی سے اندازہ لگایا جا سکتا ہے کہ، اگر جڑ اصل سے بہت دور ہے، تو اس کے انٹیجر حصے کو اس طرح تلاش کرنے میں بہت وقت لگتا ہے، لہذا ونسنٹ کے طریقہ کار کی ایکسپونینشیل نوعیت ہے۔ ذیل میں اس بات کی وضاحت کی گئی ہے کہ اس خامی پر کیسے قابو پایا جاتا ہے۔ ونسنٹ کے نظریہ کی گمشدگی ونسنٹ 19 ویں صدی کا آخری مصنف تھا جس نے اپنے نظریہ کو کثیر الجہتی کے حقیقی جڑوں کو الگ کرنے کے لیے استعمال کیا۔ اس کی وجہ 1827 میں اسٹرم تھیوریم کا ظہور تھا، جس نے کثیر الجہتی وقت میں حقیقی جڑ کے الگ تھلگ ہونے کے مسئلے کو حل کیا، ایک کثیر الجہتی کے حقیقی جڑوں کی درست تعداد کو حقیقی کھلے وقفے (a، b) میں بیان کرکے۔ کثیر الجہتی کی حقیقی جڑوں کی گنتی کے لیے نتیجے میں (اسٹرم کا) طریقہ صرف ایک ہی وسیع پیمانے پر جانا جاتا ہے اور اس کے بعد سے استعمال ہوتا رہا ہے-تقریبا 1980 تک، جب اسے ونسنٹ کے نظریہ سے اخذ کردہ طریقوں سے (تقریبا تمام کمپیوٹر الجبرا سسٹمز میں) تبدیل کیا گیا، سب سے تیز ترین ونسنٹ-اتراٹاس-اسٹرزبوسکی (وی اے ایس) طریقہ ہے۔ سیرٹ نے اپنے الجبرا، پی پی 363-368، ونسنٹ تھیوریم کو اس کے ثبوت کے ساتھ شامل کیا اور تمام دلچسپی رکھنے والے قارئین کو ونسنٹ کے مقالے کی طرف ہدایت کی کہ اس کا استعمال کیسے کیا جاتا ہے۔ سیرٹ 19 ویں صدی میں ونسنٹ کے نظریہ کا ذکر کرنے والے آخری مصنف تھے۔ 20 ویں صدی میں ونسنٹ کا نظریہ مساوات کی کتابوں کے کسی بھی نظریہ میں نہیں پایا جا سکتا۔ صرف مستثنیات یوسپنسکی اور اوبریشکوف کی کتابیں ہیں، جہاں دوسرے میں صرف نظریہ کا بیان ہے۔ یوسپنسکی کی کتاب میں ہی آکریتاس نے ونسنٹ تھیوریم دریافت کیا اور اسے اپنے پی ایچ ڈی تھیسس "ونسنٹ تھیوریم ان الجیبرک مینیپولیشن"، نارتھ کیرولائنا اسٹیٹ یونیورسٹی، یو ایس اے، 1978 کا موضوع بنایا۔ اس وقت کی ایک بڑی کامیابی ونسنٹ کے 1836 کے اصل مقالے کو پکڑنا تھا، جو کہ یوسپنسکی سے بچ گیا تھا-جس کے نتیجے میں ایک بڑی غلط فہمی پیدا ہوئی۔ ونسنٹ کا 1836 کا اصل مقالہ ریاستہائے متحدہ امریکہ کی وسکونسن-میڈیسن یونیورسٹی کی لائبریری میں ایک لائبریرین کی قابل تعریف کوششوں (انٹر لائبریری لون) کے ذریعے آکریتاس کو دستیاب کرایا گیا تھا۔ ونسنٹ کے نظریہ سے اخذ کردہ حقیقی جڑ کو الگ کرنے کے طریقے کسی کثیر الجہتی کے حقیقی جڑوں کو الگ کرنا کھلے جداگانہ وقفوں کو تلاش کرنے کا عمل ہے جس میں ہر ایک بالکل ایک حقیقی جڑ پر مشتمل ہوتا ہے اور ہر حقیقی جڑ کسی وقفے میں موجود ہوتی ہے۔ 19 ویں صدی کے فرانسیسی اسکول آف میتھمیٹکس کے مطابق، یہ حقیقی جڑوں کی گنتی کا پہلا قدم ہے، دوسرا کسی بھی حد تک درستگی کے لیے ان کا تخمینہ ہے۔ اس کے علاوہ، مثبت جڑوں پر توجہ مرکوز کی جاتی ہے، کیونکہ کثیر الجہتی p (x) کے منفی جڑوں کو الگ کرنے کے لیے x کو −x (x) سے تبدیل کیا جاتا ہے اور اس عمل کو دہرایا جاتا ہے۔ ونسنٹ تھیوریم کے مسلسل فریکشن ورژن کو ڈگری ڈیگ (پی) کے دیئے گئے کثیر الجہتی پی (ایکس) کے مثبت جڑوں کو الگ کرنے کے لیے استعمال کیا جا سکتا ہے۔ اسے دیکھنے کے لیے، موبیئس ٹرانسفارمیشن کے ذریعے اس مسلسل فریکشن کی نمائندگی کریں جو ایک تبدیل شدہ کثیر الجہتی کی طرف لے جاتا ہے جس میں اس کے کوفیشنٹس کی ترتیب میں ایک نشانی کی تبدیلی ہوتی ہے۔ پھر، f (x) کا واحد مثبت جڑ (وقفہ (0، φ) میں) p (x) کے اس مثبت جڑ سے مطابقت رکھتا ہے جو اختتامی نکات اور کے ساتھ کھلے وقفے میں ہے۔ یہ اختتامی نکات ترتیب نہیں دیے گئے ہیں اور بالترتیب M (0) اور M (ini) سے مطابقت رکھتے ہیں۔ لہذا، کسی کثیر الجہتی کے مثبت جڑوں کو الگ کرنے کے لیے، جو کچھ کرنا ضروری ہے وہ یہ ہے کہ-ہر جڑ کے لیے-متعلقہ موبیئس تبدیلی کے متغیر a، b، c، d کا حساب لگانا ہے جو مساوات () کی طرح ایک تبدیل شدہ کثیر الجہتی کی طرف لے جاتا ہے، جس میں اس کے گتانک کی ترتیب میں ایک علامت کی تبدیلی ہوتی ہے۔ اہم مشاہدہ: موبیئس ٹرانسفارمیشن (ونسنٹ کے نظریہ میں) کے متغیر a، b، c، d جو ایک تبدیل شدہ کثیر الجہتی کی طرف لے جاتے ہیں-جیسا کہ مساوات () میں-اس کے گتانک کی ترتیب میں ایک نشانی کے تغیر کے ساتھ شمار کیا جاسکتا ہے: یا تو مسلسل حصوں سے، جو ونسنٹ-اتراٹس-اسٹرزبنسکی (VAS) مسلسل حصوں کے طریقہ کار کی طرف لے جاتا ہے، یا بائیسیکشن کے ذریعے، جو (دوسروں کے درمیان) ونسنٹ-کولنز-اتراٹس (VCA) بائیسیکشن طریقہ کی طرف لے جاتا ہے۔ اس تمام اہم مشاہدے کا "بائیسیکشن حصہ" الیسینا اور گلوزی کے مقالے میں ایک خاص نظریہ کے طور پر ظاہر ہوا۔ ذیل میں بیان کردہ تمام طریقوں (ان کے تاریخی پس منظر کے لیے بوڈن کے نظریہ پر مضمون دیکھیں) کو زیر غور کثیر الجہتی کے مثبت جڑوں کی اقدار پر (ایک بار) ایک اوپری باؤنڈ، ub کا حساب لگانے کی ضرورت ہے۔ مستثنی وی اے ایس طریقہ ہے جہاں اضافی طور پر نچلی حدود، ایل بی، کو مرکزی لوپ کے تقریبا ہر چکر پر شمار کیا جانا چاہیے۔ کثیر الجہتی p (x) کے نچلے باؤنڈ lb کا حساب لگانے کے لیے کثیر الجہتی کے اوپری باؤنڈ ub کا حساب لگائیں اور سیٹ کریں۔ صرف کثیر الجہتی کی مثبت جڑوں کی اقدار پر بہترین (اوپری اور نچلے) حدود کو آکریٹاس، اسٹریزبوسکی اور ویگکلاس نے ڈورو اسٹیفنسکو کے پچھلے کام کی بنیاد پر تیار کیا ہے۔ ان کی وضاحت پی۔ ایس۔ ویگکلاس کے پی۔ ایچ۔ ڈی تھیسس اور دوسری جگہوں پر کی گئی ہے۔ یہ حدود پہلے ہی کمپیوٹر الجبرا سسٹمز میتھمیٹکا، سیج میتھ، سمپی، ایکسکاس وغیرہ میں نافذ کی جا چکی ہیں۔ ذیل میں بیان کردہ تینوں طریقے فرانسوا بولر، صفحہ 24 کی بہترین پیش کش پر عمل کرتے ہیں۔ مسلسل فریکشن کا طریقہ ونسنٹ کے نظریہ سے صرف ایک مسلسل فریکشن کا طریقہ اخذ کیا گیا ہے۔ جیسا کہ اوپر بیان کیا گیا ہے، اس کا آغاز 1830 کی دہائی میں ہوا جب ونسنٹ نے کاغذات میں کئی مثالیں پیش کیں جو یہ ظاہر کرتی ہیں کہ مسلسل حصوں کے ساتھ کثیر الجہتی کی حقیقی جڑوں کو الگ کرنے کے لیے اپنے نظریہ کو کس طرح استعمال کیا جائے۔ تاہم نتیجے میں آنے والے طریقہ کار میں ایکسپونینشیل کمپیوٹنگ ٹائم تھا۔ ذیل میں اس بات کی وضاحت کی گئی ہے کہ یہ طریقہ کیسے تیار ہوا۔ ونسنٹ-اریکٹاس-اسٹرزبوسکی (وی اے ایس، 2005) یہ دوسرا طریقہ ہے (وی سی اے کے بعد) جو ونسنٹ کے طریقہ کار کے متغیر رویے کو سنبھالنے کے لیے تیار کیا گیا ہے۔ وی اے ایس مسلسل فریکشن کا طریقہ ونسنٹ تھیوریم کا براہ راست نفاذ ہے۔ یہ اصل میں ونسنٹ نے 1834 سے 1938 تک پیپرز میں ایک ایکسپونینشل شکل میں پیش کیا تھا۔ یعنی، ونسنٹ نے ہر جزوی حصص AI کا حساب یونٹ انکریمنٹس AI-1 + 1 کے ایک سلسلے کے ذریعے کیا، جو کہ x-1x + 1 کی شکل کے متبادلات کے مساوی ہیں۔ ونسنٹ کے طریقہ کار کو اکریتاس نے اس کی کثیر الجہتی پیچیدگی کی شکل میں تبدیل کیا، جس نے اپنی 1978 کی پی ایچ ڈی تھیسس (ونسنٹ تھیوریم ان الجیبرک ہیرا پھیری، نارتھ کیرولائنا اسٹیٹ یونیورسٹی، یو ایس اے) میں ہر جزوی حصص آئی کو نچلے باؤنڈ، ایل بی کے طور پر شمار کیا۔ اسے مثالی مثبت نچلی جڑ کا پابند کہا جاتا ہے جو سب سے چھوٹے مثبت جڑ کے عدد حصے کا حساب لگاتا ہے (متعلقہ اعداد و شمار دیکھیں)۔ سمجھدار ہونے کے لیے، اب آئی۔ ایل۔ بی سیٹ کریں یا، مساوی طور پر، متبادل ایکس۔ ایکس + ایل۔ بی انجام دیں، جس میں متبادل ایکس۔ ایکس + 1 کے برابر وقت لگتا ہے۔ آخر میں، چونکہ مثالی مثبت نچلی جڑ کی حد موجود نہیں ہے، اس لیے اسٹریزبوسکی نے 2005 میں متبادل متعارف کرایا، جب بھی ؛ عام طور پر اور قیمت 16 کا تعین تجرباتی طور پر کیا گیا تھا۔ مزید برآں، یہ دکھایا گیا ہے کہ وی اے ایس (مسلسل فریکشن) طریقہ وی سی اے (بائیسیکشن) طریقہ کار کے تیز ترین نفاذ سے زیادہ تیز ہے، ایک ایسی حقیقت جس کی آزادانہ طور پر تصدیق کی گئی تھی۔ زیادہ واضح طور پر، ہائی ڈگری وی اے ایس کے مگنوٹ کثیرالجہتی کے لیے وی سی اے کے تیز ترین نفاذ سے تقریبا 50,000 گنا زیادہ تیز ہے۔ 2007 میں شرما نے آئیڈیل مثبت لوور باؤنڈ کے مفروضے کو ہٹا دیا اور ثابت کیا کہ وقت میں وی اے ایس اب بھی کثیر الجہتی ہے۔ وی اے ایس ریاضی، سیج میتھ، سمپی، ایکسکاس میں جڑ کی تنہائی کے لیے ڈیفالٹ الگورتھم ہے۔ اسٹرم کے طریقہ کار اور وی اے ایس کے درمیان موازنہ کے لیے ایکسکاس کے فنکشنز ریئلروٹ (پولی) اور ٹائم (ریئلروٹ (پولی)) کا استعمال کریں۔ پہلے سے طے شدہ طور پر، پولی ریالروٹ کی حقیقی جڑوں کو الگ کرنے کے لیے وی اے ایس طریقہ استعمال کیا جاتا ہے ؛ اسٹرم کا طریقہ استعمال کرنے کے لیے ریالروٹ لکھیں (اسٹرم، پولی)۔ اینڈرائیڈ ڈیوائسز کے لیے اے برکاکس کی ایپلی کیشن کے بیرونی لنکس بھی دیکھیں جو ایک ہی کام کرتے ہیں۔ یہاں یہ ہے کہ وی اے ایس (پی، ایم) کیسے کام کرتا ہے، جہاں سادگی کے لیے اسٹریزبوسکی کی شراکت شامل نہیں ہے: فرض کریں کہ پی (ایکس) ڈگری ڈگری ڈیگ (پی) کا ایک کثیر الجہتی ہو جیسے کہ پی (0)  ऒत्त 0۔ اس کی مثبت جڑوں کو الگ کرنے کے لیے، p (x) کے ساتھ موبیئس تبدیلی M (x) = x کو منسلک کریں اور درج ذیل مراحل کو دہرائیں جب کہ جوڑے {p (x)، M (x)} پر کارروائی کی جانی ہے۔ اگر ممکن ہو تو حساب لگانے کے لیے p (x) پر ڈیکارٹس کی علامتوں کی حکمرانی کا استعمال کریں، (اس کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد وار کا استعمال کرتے ہوئے) وقفہ (0، φ) کے اندر اس کی جڑوں کی تعداد۔ اگر کوئی جڑیں خالی سیٹ کو واپس نہیں کرتی ہیں، تو यु بی خالی سیٹ کو واپس کرتا ہے، جبکہ اگر ایک جڑ ہے تو وقفہ (اے، بی) واپس کرتا ہے، جہاں اے = منٹ (ایم (0)، ایم (≤)، اور بی = میکس (ایم (0)، ایم (≤)) ؛ اگر بی = ≤ سیٹ بی = یو بی، جہاں یو بی پی (ایکس) کے مثبت جڑوں کی اقدار پر ایک اوپری باؤنڈ ہے۔ اگر دو یا دو سے زیادہ اشاروں میں تغیرات ہیں تو ڈیکارٹس کے اشاروں کے اصول کا مطلب یہ ہے کہ وقفہ (0، φ) کے اندر صفر، ایک یا زیادہ حقیقی جڑیں ہو سکتی ہیں۔ اس صورت میں وقفہ (0، 1) کے اندر موجود p (x) کی جڑوں کو وقفہ (1، φ) کے اندر موجود جڑوں سے الگ سے سمجھیں۔ 1 کے لیے ایک خصوصی ٹیسٹ ہونا چاہیے۔ اس بات کی ضمانت کے لیے کہ وقفہ (0، 1) مثالی نچلی حد کے اندر جڑیں ہیں، lb استعمال کیا جاتا ہے ؛ یعنی سب سے چھوٹے مثبت جڑ کا عدد حصہ نچلی حد کی مدد سے، p (x) کے مثبت جڑوں کی اقدار پر شمار کیا جاتا ہے۔ اگر، متبادل p (x) اور M (x) پر انجام دیا جاتا ہے، جبکہ اگر جڑ (ز) کے انٹیجر حصے کو تلاش کرنے کے لیے متبادل (ز) x → x + 1 کا استعمال کریں۔ وقفہ (0، 1) کے اندر جڑوں کی گنتی کرنے کے لیے p (x) اور M (x) کا متبادل انجام دیں اور جوڑے پر عمل کریں جبکہ وقفہ (1، φ) میں جڑوں کی گنتی کرنے کے لیے x → x + 1 سے p (x) اور M (x) کا متبادل انجام دیں اور جوڑے {p (1 + x)، M (1 + x)} پر عمل کریں۔ یہ اچھی طرح سے پتہ چل سکتا ہے کہ 1 p (x) کا جڑ ہے، اس صورت میں، M (1) اصل کثیر الجہتی کا جڑ ہے اور تنہائی کا وقفہ ایک نقطہ تک کم ہو جاتا ہے۔ ذیل میں وی اے ایس (پی، ایم) کی تکراری پیشکش ہے۔ وی اے ایس (پی، ایم): ان پٹ: ڈگری ڈیگ (پی) کا ایک غیر متغیر، مربع فری کثیر الجہتی، اور موبیئس ٹرانسفارمیشن آؤٹ پٹ: پی (ایکس) کے مثبت جڑوں کے الگ تھلگ وقفوں کی فہرست۔ p (x)// Descartes کی علامتوں کی حکمرانی کی علامتوں کی تغیرات کی تعداد ؛ 2 اگر ور = 0 تو واپسی; 3 اگر ور = 1 تو واپسی {(a, b)}// a = منٹ (M (0)، M (≤))، b = زیادہ سے زیادہ (M (0)، M (≤))، لیکن اگر b = ≤ سیٹ b = ub ہے، جہاں p (x) کے مثبت جڑوں کی اقدار پر ub ایک اوپری باؤنڈ ہے ؛ 4 lb کی مثبت جڑوں پر مثالی نچلی باؤنڈ ؛ 5 اگر lb ≤ 1 تو p (x + lb) 8 p1 ≤ p (x + 1)، M1 ≤ M (x + 1)// (1، ≤) میں حقیقی جڑیں تلاش کریں ؛ 9 اگر p (1) ≤ 0 تو 10 ریٹرن واس (p01, M01) ≤ VAS (p1 ≤, M1 ≤) 11 اور 12 ریٹرن واس (p01, M01) ≤ {[[m, m]} ≤ VAS (p1 ≤, M1 ≤) 13 اختتامی ریمارکس سادگی کے لیے اسٹریزبوسکی کی شراکت شامل نہیں ہے۔ مندرجہ بالا الگورتھم میں ہر کثیر الجہتی کے ساتھ ایک موبیئس تبدیلی M (x) وابستہ ہے۔ لائن 1 میں ڈیکارٹس کی علامتوں کی حکمرانی کا اطلاق ہوتا ہے۔ اگر لائن 4 اور 5 کو وی اے ایس (پی، ایم) سے ہٹا دیا جائے تو اس کے نتیجے میں الگورتھم ونسنٹ کا ایکسپونینشیل ہے۔ کثیر الجہتی p (x) پر انجام دیا جانے والا کوئی بھی متبادل متعلقہ موبیئس تبدیلی M (x) (لائنیں 5 6 اور 8) پر بھی انجام دیا جاتا ہے۔ الگ تھلگ وقفوں کا حساب لائن 3 میں موبیئس تبدیلی سے کیا جاتا ہے، سوائے انٹیجر جڑوں کے جو لائن 7 (بھی 12) میں شمار کیے جاتے ہیں۔ وی اے ایس (پی، ایم) کی مثال ہم وی اے ایس طریقہ کار کو لاگو کرتے ہیں (نوٹ کریں کہ:)۔ تکرار 1 VAS (x3 − 7x + 7, x) 1 ور ≤ 2// p (x) = x3 − 7x + 7 4 lb ≤ 1// مثالی نچلے باؤنڈ کے کوفیشنٹس کی ترتیب میں سائن کے تغیرات کی تعداد-lb کمپیوٹیڈ اور متبادل (s) x ≤ x + 1 5 p ≤ x3 + 3x2 − 4x + 1، M ≤ x + 1 6 p01 ≤ x3 − 2x + 1، M01 ≤ 7 m ≤ 1 8 p1 ≤ ≤ x3 + 6x2 + 5x + 1، M1 ≤ ≤ x + کا استعمال کرتے ہوئے پایا جاتا ہے۔ تکرار 2 VAS (x3 − x2 − 2x + 1،) 1 ور ≤ 2// p (x) = x3 − x2 − 2x + 1 4 lb ≤ 0// مثالی نچلے باؤنڈ کے کوفیشنٹس کی ترتیب میں سائن کے تغیرات کی تعداد-lb کمپیوٹیڈ اور متبادل (s) x ≤ x + 1 6 p01 ≤ x3 + x2 − 2x − 1، M01 ≤ 7 m ≤ 8 p1 ≤ x3 + 2x2 − x−1، M1 ≤ 10 ریٹرن واس (x3 + x2 − 2x−1،) کا استعمال کرتے ہوئے پایا جاتا ہے۔ تکرار 3 VAS (x3 + x2−2x−1،) 1 وار/1/p (x) = x3 + x2−23 ریٹرن {(، 2)} کے کوفشنٹس کی ترتیب میں نشان کی تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 4 وی اے ایس (x3 + 2x2 − x−1,) 1 ور 1// p (x) = x3 + 2x2 − x−13 ریٹرن {(1,)} کے کوفشنٹس کی ترتیب میں نشان کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 5 وی اے ایس (x3 + 6x2 + 5x + 1, x + 2) 1 ور۔ 0// p (x) = x3 + 6x2 + 5x + 1 2 ریٹرن کے کوفشنٹس کی ترتیب میں اشاروں کے تغیرات کی تعداد۔ الگ تھلگ وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: ختم ہو گیا۔ نتیجہ لہذا، کثیر الجہتی کے دو مثبت جڑ الگ تھلگ وقفوں اور} کے اندر ہوتے ہیں۔ ہر جڑ کا تخمینہ (مثال کے طور پر) تنہائی کے وقفے کو دو حصوں میں تقسیم کرکے لگایا جا سکتا ہے جب تک کہ اختتامی نکات کا فرق اس سے چھوٹا نہ ہو۔ اس نقطہ نظر پر عمل کرتے ہوئے، جڑیں اور بن جاتی ہیں۔ تقسیم کے طریقے ونسنٹ کے نظریہ سے اخذ کردہ مختلف تقسیم کے طریقے ہیں۔ ان سب کو کہیں اور پیش کیا جاتا ہے اور ان کا موازنہ کیا جاتا ہے۔ یہاں ان میں سے دو سب سے اہم طریقے بیان کیے گئے ہیں، یعنی ونسنٹ-کولنز-اریکٹاس (وی سی اے) طریقہ اور ونسنٹ-الیسینا-گلوزی (وی اے جی) طریقہ۔ ونسنٹ-الیسینا-گلوزی (وی اے جی) طریقہ ونسنٹ کے نظریہ سے اخذ کردہ تمام طریقوں میں سب سے آسان ہے لیکن اس کا تعین کرنے کے لیے سب سے زیادہ وقت طلب ٹیسٹ (لائن 1 میں) ہے کہ آیا کسی کثیر الجہتی کی جڑیں دلچسپی کے وقفے میں ہیں۔ یہ اسے اس مضمون میں پیش کردہ طریقوں میں سب سے سست بناتا ہے۔ اس کے برعکس، ونسنٹ-کولنز-اتراٹس (وی سی اے) طریقہ زیادہ پیچیدہ ہے لیکن وی اے جی کے مقابلے میں ایک آسان ٹیسٹ (لائن 1 میں) کا استعمال کرتا ہے۔ اس نے کچھ بہتریوں کے ساتھ ساتھ وی سی اے کو سب سے تیز بائیسیکشن طریقہ بنا دیا ہے۔ ونسنٹ-کولنز-اتراٹس (وی سی اے، 1976) یہ ونسنٹ کے اصل نقطہ نظر کی تیز رفتار نوعیت پر قابو پانے کے لیے تیار کیا گیا پہلا طریقہ تھا، اور جہاں تک اس کے نام کا تعلق ہے اس کی کافی دلچسپ تاریخ رہی ہے۔ یہ طریقہ، جو ڈیکارٹس کی علامتوں کی حکمرانی اور ونسنٹ کے نظریہ کا استعمال کرتے ہوئے حقیقی جڑوں کو الگ کرتا ہے، کو اصل میں اس کے موجد کولنز اور آکریٹاس نے ترمیم شدہ یوسپنسکی کا الگورتھم کہا تھا۔ "کولنز-اتراٹس میتھڈ" اور "ڈیکارٹس میتھڈ" جیسے ناموں کو دیکھنے کے بعد (اگر کوئی فوریر کے مضمون پر غور کرتا ہے تو بہت زیادہ الجھن میں پڑ جاتا ہے)، آخر کار للی یونیورسٹی کے فرانکوئس بولئیر نے اسے ونسنٹ-کولنز-اتراٹس (وی سی اے) میتھڈ، صفحہ 24 کا نام دیا، اس حقیقت کی بنیاد پر کہ "یوسپنسکی کا طریقہ" موجود نہیں ہے اور نہ ہی "ڈیکارٹس کا طریقہ" موجود ہے۔ اس طریقہ کار کا بہترین نفاذ رولیئر اور زیمرمین کی وجہ سے ہے، اور آج تک، یہ سب سے تیز بائیسیکشن طریقہ ہے۔ اس میں وہی بدترین کیس پیچیدگی ہے جو اسٹرم کے الگورتھم کی ہے، لیکن تقریبا ہمیشہ بہت تیز ہوتی ہے۔ اسے میپل کے روٹ فائنڈنگ پیکیج میں لاگو کیا گیا ہے۔ وی سی اے (پی، (اے، بی)) کس طرح کام کرتا ہے: ڈگری ڈیگ (پی) کے کثیر الجہتی پورجیگ (ایکس) کو اس طرح دیا گیا ہے کہ پورجیگ (0)  ऒत्त 0، جس کے مثبت جڑوں کو الگ کرنا ضروری ہے، پہلے ان مثبت جڑوں کی اقدار پر ایک اوپری باؤنڈ، یو بی کا حساب لگائیں اور پی (ایکس) = پورجیگ (یو بی * ایکس) اور (اے، بی) = (0، یو بی) سیٹ کریں۔ p (x) کی مثبت جڑیں تمام وقفہ (0,1) میں ہوتی ہیں اور ان کے اور پورگ (x) کی جڑوں کے درمیان ایک بائیجیکشن ہوتا ہے، جو تمام وقفہ (a, b) = (0, ub) میں ہوتا ہے (متعلقہ اعداد و شمار دیکھیں) ؛ اس بائیجیکشن کا اظہار α (a, b) = a + α (0,1) (b−a) سے ہوتا ہے۔ اسی طرح، وقفوں (0، 1) اور (0، ub) کے درمیان ایک بائیجیکشن ہے۔ درج ذیل مراحل کو دہرائیں جب کہ جوڑے {p (x)، (a، b)} پر کارروائی کی جانی ہے۔ وقفہ (0، 1) کے اندر اس کی جڑوں کی تعداد کا حساب لگانے کے لیے (اس کے کوفیشنٹس کی ترتیب میں سائن کے تغیرات کی تعداد وار کا استعمال کرتے ہوئے) پی (ایکس) پر بوڈن کا "0 _ 1 روٹس ٹیسٹ" استعمال کریں۔ اگر کوئی جڑ نہیں ہے تو خالی سیٹ واپس کرتا ہے، اور اگر ایک جڑ ہے تو وقفہ (a، b) واپس کرتا ہے۔ اگر دو یا دو سے زیادہ اشاروں میں تغیرات ہیں تو بڈان کے "0 _ 1 جڑوں کے ٹیسٹ" کا مطلب یہ ہے کہ وقفہ (0، 1) کے اندر صفر، ایک، دو یا زیادہ حقیقی جڑیں ہو سکتی ہیں۔ اس صورت میں اسے آدھے حصے میں کاٹ لیں اور وقفہ (0،) کے اندر p (x) کی جڑوں پر الگ سے غور کریں-اور جو وقفہ (a، (a + b) کے اندر پورگ (x) کی جڑوں سے مطابقت رکھتے ہیں اور وقفہ (1) کے اندر ان سے مطابقت رکھتے ہیں اور وقفہ ((a + b)، b) کے اندر پورگ (x) کی جڑوں سے مطابقت رکھتے ہیں۔ یعنی، عمل، بالترتیب، جوڑے (متعلقہ شکل دیکھیں)۔ یہ اچھی طرح سے پتہ چل سکتا ہے کہ یہ p (x) کا جڑ ہے، اس صورت میں (a + b) پورگ (x) کا جڑ ہے اور تنہائی کا وقفہ ایک نقطہ تک کم ہو جاتا ہے۔ ذیل میں اصل الگورتھم وی سی اے (پی، (اے، بی)) کی تکراری پیشکش ہے۔ وی سی اے (پی، (اے، بی)) ان پٹ: ایک غیر متغیر، مربع فری کثیر الجہتی پی (یو بی * ایکس) bul زیڈ [ایکس]، پی (0) 0 ڈگری ڈیگ (پی)، اور کھلا وقفہ (اے، بی) = (0، یو بی)، جہاں یو بی پی (ایکس) کے مثبت جڑوں کی اقدار پر ایک اوپری پابند ہے۔ (p (ub * x) کے مثبت جڑ تمام کھلے وقفے (0، 1) میں ہیں)۔ آؤٹ پٹ: پی (ایکس) 1 ور کے مثبت جڑوں کے الگ تھلگ وقفوں کی فہرست، (ایکس + 1) ڈیگ (پی) پی ()/بوڈن کے "0 _ 1 جڑوں کے ٹیسٹ" کی علامت میں تغیرات کی تعداد ؛ 2 اگر ور = 0 ہے تو واپسی ؛ 3 اگر ور = 1 ہے تو واپسی [(اے، بی)] ؛ 4 پی 0، 2 ڈیگ (پی) پی ()// میں حقیقی جڑوں کی تلاش کریں ؛ 5 ایم، (اے + بی)// کیا جڑ ہے؟ (، 1) میں حقیقی جڑوں کی تلاش کریں ؛ 7 اگر p ()  ऒत्त 0 ہے تو 8 RETURN VCA (p0، (a, m)) ≤ VCA (p1، (m, b)) 9 اور 10 RETURN VCA (p0، (a, m)) ≤ {[[m, m]} ≤ VCA (p1, (m, b)) 11 اختتامی ریمارک مندرجہ بالا الگورتھم میں ہر کثیر الجہتی کے ساتھ ایک وقفہ (a, b) وابستہ ہے۔ جیسا کہ دوسری جگہوں پر دکھایا گیا ہے، صفحہ 11، ایک موبیئس تبدیلی کو ہر کثیر الجہتی کے ساتھ بھی جوڑا جا سکتا ہے جس صورت میں وی سی اے زیادہ وی اے ایس کی طرح نظر آتا ہے۔ لائن 1 میں بوڈان کا "0 _ 1 روٹس ٹیسٹ" لاگو کیا جاتا ہے۔ وی سی اے (پی، (اے، بی)) کی مثال کثیر الجہتی کو دیکھتے ہوئے اور مثبت جڑوں کی اقدار پر اوپری حد کے طور پر غور کرتے ہوئے وی سی اے طریقہ کار کے دلائل یہ ہیں: اور۔ (x + 1) 3p () = 7x3 − 7x2 − 35x + 43 4 p0 → 64x3 − 112x + 56 5 m → 2 6 p1 → 64x3 + 192x2 + 80x + 8 p () = 1 8 ریٹرن وی سی اے (64x3 − 112x + 56, (0,2)) ≤ وی سی اے (64x3 + 192x2 + 80x + 8, (2,4) تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 2 وی سی اے (64x3 −112x + 56, (0,2)) 1 ور ≤ 2// (x + 1) 3p () = 56x3 + 56x2 − 56x + 8 4 p ≤ 64x3 − 448x + 448 5 m ≤ 1 6 p1 ≤ 64x3 + 192x2 − 256x + 64 7 p () = 8 ریٹرن وی سی اے (64x3 − 448x + 448, (0,1)) ≤ وی سی اے (64x3 + 192x2 − 256x + 64, (1,2)) تکرار 3 وی سی اے (64x3 − 448x + 448, (0,1)) 1 ور (x + 1) 3p () = 448x3 + 896x2 + 448x + 642 ریٹرن کے کوفشنٹس کی ترتیب میں نشان کے تغیرات کی تعداد۔ الگ تھلگ وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 4 وی سی اے (64x3 + 192x2 −256x + 64, (1,2) 1 ور/2// (x + 1) 3p () = 64x3 −64x2 −128x + 64 4 p0 → 64x3 + 384x2 −1024x + 5125 m → 6 p1 → 64x3 + 576x2 −64x + 64 7 p () = −8 ریٹرن وی سی اے (64x3 + 384x2 −1024x + 512, (1,)) ¥ وی سی اے (64x3 + 57) کے کوفشنٹس کی ترتیب میں سائن تغیرات کی تعداد۔ تکرار 5 وی سی اے (64x3 + 384x2−1024x + 512، (1،)) 1 ور/1/(x + 1) 3p () = 512x3 + 512x2−128x−64 3 ریٹرن ((1،)) کے کوفشنٹس کی ترتیب میں نشان کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 6 وی سی اے (64x3 + 576x2 − 64x−64، (، 2)) 1 ور 1// (x + 1) 3p () = −64x3 − 256x2 + 256x + 5123 ریٹرن ((، 2)} کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 7 وی سی اے (64x3 + 192x2 + 80x + 8، (2، 4)) 1 ور۔ 0// (x + 1) 3p () = 8x3 + 104x2 + 376x + 344 2 ریٹرن کے کوفشنٹس کی ترتیب میں نشان کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: عمل کرنے والے جوڑوں کی فہرست: ختم ہو گیا۔ نتیجہ لہذا، کثیر الجہتی کے دو مثبت جڑ الگ تھلگ وقفوں اور} کے اندر ہوتے ہیں۔ ہر جڑ کا تخمینہ (مثال کے طور پر) تنہائی کے وقفے کو دو حصوں میں تقسیم کرکے لگایا جا سکتا ہے جب تک کہ اختتامی نکات کا فرق اس سے چھوٹا نہ ہو۔ اس نقطہ نظر پر عمل کرتے ہوئے، جڑیں اور بن جاتی ہیں۔ ونسنٹ-الیسینا-گلوزی (وی اے جی، 2000) یہ آخری بار تیار کیا گیا تھا اور ونسنٹ کے نظریہ سے ماخوذ سب سے آسان حقیقی جڑ کو الگ کرنے کا طریقہ ہے۔ یہاں وی اے جی (پی، (اے، بی)) کیسے کام کرتا ہے: ڈگری ڈیگ (پی) کے کثیر الجہتی پی (ایکس) کو اس طرح دیا گیا ہے کہ پی (0)  ऒत्त 0، جس کے مثبت جڑوں کو الگ کرنا ضروری ہے، پہلے ان مثبت جڑوں کی اقدار پر ایک اوپری باؤنڈ، یو بی کا حساب لگائیں اور (اے، بی) = (0، یو بی) سیٹ کریں۔ p (x) کی مثبت جڑیں تمام وقفہ (a، b) میں ہوتی ہیں۔ درج ذیل مراحل کو دہرائیں جب کہ وقفے (a، b) پر کارروائی کی جانی ہے۔ اس صورت میں کثیر الجہتی p (x) یکساں رہتا ہے۔ وقفہ (a، b) کے اندر اس کے جڑوں کی تعداد کا حساب لگانے کے لیے p (x) پر الیسینا-گلوزی "a _ b جڑوں کی جانچ" کا استعمال کریں (اس کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد وار کا استعمال کرتے ہوئے)۔ اگر کوئی جڑ نہیں ہے تو خالی سیٹ واپس کرتا ہے، اور اگر ایک جڑ ہے تو وقفہ (a، b) واپس کرتا ہے۔ اگر دو یا دو سے زیادہ اشاروں میں تغیرات ہیں تو الیسینا-گلوزی "اے بی روٹس ٹیسٹ" کا مطلب ہے کہ وقفہ (اے، بی) کے اندر صفر، ایک، دو یا زیادہ حقیقی جڑیں ہو سکتی ہیں۔ اس صورت میں اسے آدھے حصے میں کاٹ لیں اور وقفہ (a، (a + b)) کے اندر p (x) کی جڑوں کو وقفہ ((a + b)، b) کے اندر کے جڑوں سے الگ کریں۔ یعنی عمل، بالترتیب، وقفے (a، (a + b)) اور ((a + b)، b)۔ یہ اچھی طرح سے پتہ چل سکتا ہے کہ (a + b) p (x) کا جڑ ہے، ایسی صورت میں تنہائی کا وقفہ ایک نقطہ تک کم ہو جاتا ہے۔ ذیل میں وی اے جی (پی، (اے، بی)) کی تکراری پیشکش ہے۔ وی اے جی (پی، (اے، بی)) ان پٹ: ایک غیر متغیر، مربع فری کثیر الجہتی پی (ایکس) bul زیڈ [ایکس]، پی (0) 0 ڈگری ڈیگ (پی) اور کھلا وقفہ (اے، بی) = (0، یو بی)، جہاں یو بی پی (ایکس) کے مثبت جڑوں کی اقدار پر ایک اوپری باؤنڈ ہے۔ آؤٹ پٹ: p (x) کے مثبت جڑوں کے الگ الگ وقفوں کی فہرست۔ (x + 1) ڈگری (p) p ()// الیسینا-گلوزی "a _ b جڑوں کی جانچ" کے اشاروں کے تغیرات کی تعداد ؛ 2 اگر ور = 0 ہے تو واپسی; 3 اگر ور = 1 ہے تو واپسی {(a, b)} ؛ 4 m· (a + b)/وقفہ (a, b) کو دو مساوی حصوں میں تقسیم کریں ؛ 5 اگر p (m) ≤ 0 ہے تو 6 واپسی VAG (p, (a, m)) ≤ VAG (p, (p, (m, b)) 7 اور 8 واپسی VAG (p, (p, (a, m)) ≤ جیسا کہ الیسینا اور گلوزی بتاتے ہیں، صفحہ 189، ڈوناٹو سیلی کی وجہ سے اس الگورتھم کی ایک قسم ہے۔ سیلی نے تجویز پیش کی کہ اختتامی نکات کے وسط کو ان کے وسط کے بجائے استعمال کیا جائے۔ تاہم، یہ دکھایا گیا ہے کہ اختتامی نکات کے میڈینٹ کا استعمال عام طور پر "مڈ پوائنٹ" ورژن کے مقابلے میں بہت سست ہے۔ VAG (p, (a, b)) کی مثال کثیر الجہتی p (x) = x3 − 7x + 7 کو دیکھتے ہوئے اور مثبت جڑوں ub = 4 کی اقدار پر اوپری باؤنڈ کے طور پر غور کرتے ہوئے VAG کے دلائل یہ ہیں: p (x) = x3 − 7x + 7 اور (a, b) = (0,4)۔ (x + 1) 3p () = 43x3 − 35x2 − 7x + 7 4 m (0 + 4) = 2 5 p (m) = 1 8 ریٹرن وی اے جی (x3 − 7x + 7, (0,2) ≤ وی اے جی (x3 − 7x + 7, (2,4) الگ تھلگ وقفوں کی فہرست: {} کارروائی کیے جانے والے وقفوں کی فہرست: {(0,2), (2,4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 2 وی اے جی (x3−7x + 7، (0، 2)) 1 ور (x + 1) 3 پی () = x3−7x2 + 7x + 7 4 ایم (0 + 2) = 1 5 پی (ایم) = 1 8 ریٹرن وی اے جی (x3−7x + 7، (0، 1)) ≤ وی اے جی (x3−7x + 7، (1، 2) الگ تھلگ وقفوں کی فہرست: {} کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد۔ کارروائی کیے جانے والے وقفوں کی فہرست: {(0,1), (1,2), (2,4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 3 وی اے جی (x3−7x + 7، (0، 1)) 1 ور۔ 0// (x + 1) 3p () = x3 + 7x2 + 14x + 7 2 ریٹرن کے کوفشنٹس کی ترتیب میں نشان کی تغیرات کی تعداد۔ الگ تھلگ وقفوں کی فہرست: {}۔ کارروائی کیے جانے والے وقفوں کی فہرست: {(1,2), (2,4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 4 وی اے جی (x3−7x + 7، (1، 2)) 1 ور Â2// (x + 1) 3p () = x3−2x2−x + 1 4 m Â (1 + 2) = 5 p (m) = −8 ریٹرن وی اے جی (x3−7x + 7، (1،)) Â وی اے جی (x3−7x + 7، (، 2)) الگ تھلگ وقفوں کی فہرست: {} کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد۔ کارروائی کیے جانے والے وقفوں کی فہرست: {(1,), (, 2), (2,4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 5 وی اے جی (x3−7x + 7، (1،)) 1 ور 1// 23 (x + 1) 3p () = x3 + 2x2−8x−83 ریٹرن (1،) کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: {(1،)}۔ کارروائی کیے جانے والے وقفوں کی فہرست: {(، 2)، (2، 4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 6 وی اے جی (x3−7x + 7، (2)) 1 ور 1// 23 (x + 1) 3p () = 8x3 + 4x2 − 4x−13 ریٹرن (، 2) کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد۔ تنہائی کے وقفوں کی فہرست: {(1،)، (، 2)}۔ کارروائی کیے جانے والے وقفوں کی فہرست: {(2,4)}۔ پہلے کو ہٹا دیں اور اس پر عمل کریں۔ تکرار 7 وی اے جی (x3 − 7x + 7, (2,4)) 1 ور ≤ 0// (x + 1) 3p () = 344x3 + 376x2 + 104x + 8 2 ریٹرن युزل کی فہرست کے کوفشنٹس کی ترتیب میں علامت کے تغیرات کی تعداد: {(1,), (, 2)}۔ عمل کیے جانے والے وقفوں کی فہرست: यु۔ ختم ہو گیا۔ نتیجہ لہذا، کثیر الجہتی کے دو مثبت جڑ الگ تھلگ وقفوں اور} کے اندر ہوتے ہیں۔ ہر جڑ کا تخمینہ (مثال کے طور پر) تنہائی کے وقفے کو دو حصوں میں تقسیم کرکے لگایا جا سکتا ہے جب تک کہ اختتامی نکات کا فرق اس سے چھوٹا نہ ہو۔ اس نقطہ نظر پر عمل کرتے ہوئے، جڑیں اور بن جاتی ہیں۔ کثیر الجہتی جڑوں کی خصوصیات بھی دیکھیں روٹ فائنڈنگ الگورتھم ویتاہ کے فارمولے نیوٹن کا طریقہ حوالہ جات بیرونی لنکس برکاکس، اینٹونس: ریئل روٹس، اینڈرائیڈ ڈیوائسز کے لیے اسٹرم کے طریقہ کار اور وی اے ایس https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots ریاضیاتی نظریات کا موازنہ کرنے کے لیے ایک مفت ایپ ہے۔