ریاضیات

در ریاضیات ، دنباله استورم از یک چند جمله ای p یک متغیره ، دنباله ای از چندجمله ای مرتبط با p و مشتق آن با یک نوع از الگوریتم اقلیدس برای چندجمله ای است . قضیه استورم بیان تعداد متمایز واقعی ریشه ازp واقع در یک فاصله زمانی از نظر تعدادی از تغییرات نشانه هایی از ارزش های دنباله استورم در مرزهای فاصله. با استفاده از فاصله همه اعداد واقعی ، تعداد کل ریشه های واقعی p را نشان می دهد . [1]
در حالی که قضیه اساسی جبر به راحتی تعداد کلی ریشه های پیچیده را که با کثرت شمارش می شود ، به دست می آورد ، روشی برای محاسبه آنها ارائه نمی دهد. قضیه استورم تعداد ریشه های واقعی متمایز را شمرده و آنها را در فواصل زمانی قرار می دهد. با تقسیم فواصل حاوی برخی از ریشه ها ، می توان ریشه ها را در فواصل کوچک دلخواه جدا کرد که هر یک دقیقاً یک ریشه دارد. این بازده قدیمی ترین الگوریتم جداسازی ریشه واقعی و الگوریتم دقیق یافتن ریشه برای چندجمله ای یک متغیره است.
برای محاسبه طول اعداد حقیقی ، قضیه استورم کارآمد کمتر از روش های دیگر بر اساس است حکومت دکارت از نشانه . با این حال ، آن را در هر زمینه بسته واقعی کار می کند ، و بنابراین ، برای مطالعه نظری پیچیدگی محاسباتی از تجزیه پذیری و حذف کمی در تئوری مرتبه اول اعداد واقعی اساسی است.
توالی استورم و قضیه استورم به نام ژاک چارلز فرانسوا استورم نامگذاری شده است که در سال 1829 قضیه را کشف کرد. [2]
 فهرست1قضیه2مثال3تعمیم4استفاده از توالی های شبه باقیمانده5جداسازی ریشه6کاربرد7همچنین ببینید8منابعقضیه [ ویرایش ]
زنجیره استورم و یا توالی استورم یک چند جمله ای های تک متغیری( P ( X  با ضرایب حقیقی دنباله ای از چند جمله ای است به طوری که

برای من ≥ 1 ، که در آن P ' است مشتق از P ، وباقی مانده از است تقسیم اقلیدسی از توسططول دنباله
در ریاضیات ، دنباله استورم از یک چند جمله ای p یک متغیره ، دنباله ای از چندجمله ای مرتبط با p و مشتق آن با یک نوع از الگوریتم اقلیدس برای چندجمله ای است . قضیه استورم بیان تعداد متمایز واقعی ریشه ازp واقع در یک فاصله زمانی از نظر تعدادی از تغییرات نشانه هایی از ارزش های دنباله استورم در مرزهای فاصله. با استفاده از فاصله همه اعداد واقعی ، تعداد کل ریشه های واقعی p را نشان می دهد . [1]
در حالی که قضیه اساسی جبر به راحتی تعداد کلی ریشه های پیچیده را که با کثرت شمارش می شود ، به دست می آورد ، روشی برای محاسبه آنها ارائه نمی دهد. قضیه استورم تعداد ریشه های واقعی متمایز را شمرده و آنها را در فواصل زمانی قرار می دهد. با تقسیم فواصل حاوی برخی از ریشه ها ، می توان ریشه ها را در فواصل کوچک دلخواه جدا کرد که هر یک دقیقاً یک ریشه دارد. این بازده قدیمی ترین الگوریتم جداسازی ریشه واقعی و الگوریتم دقیق یافتن ریشه برای چندجملهای یک متغیره است.
برای محاسبه طول اعداد حقیقی ، قضیه استورم کارآمد کمتر از روش های دیگر بر اساس است حکومت دکارت از نشانه . با این حال ، آن را در هر زمینه بسته واقعی کار می کند ، و بنابراین ، برای مطالعه نظری پیچیدگی محاسباتی از تجزیه پذیری و حذف کمی در تئوری مرتبه اول اعداد واقعی اساسی است.
توالی استورم و قضیه استورم به نام ژاک چارلز فرانسوا استورم نامگذاری شده است که در سال 1829 قضیه را کشف کرد. [2]
 فهرست1قضیه2مثال3تعمیم4استفاده از توالی های شبه باقیمانده5جداسازی ریشه6کاربرد7همچنین ببینید8منابعقضیه [ ویرایش ]
زنجیره استورم و یا توالی استورم یک چند جمله ای های تک متغیری  (P ( X  با ضرایب حقیقی دنباله ای از چند جمله ای است به طوری که

برای من ≥ 1 ، که در آن P ' است مشتق از P ، وباقی مانده از است تقسیم اقلیدسی از توسططول دنباله Sturm حداکثر درجه P است .
تعداد تغییرات علامت در ξ دنباله Sturm از P تعداد تغییرات علامت-نادیده گرفتن صفرها در دنباله اعداد واقعی است

این تعداد از علائم در اینجا( V ( ξ مشخص شده است .
کشورهای قضیه استورم که اگر P است چند جمله ای رایگان مربع ، تعداد ریشه حقیقی متمایز از P در فاصله نیمه باز ( ، ب ] است   [1]
قضیه با تعیین علامت در + ∞ چند جمله ای به عنوان علامت ضریب پیشرو آن (به عنوان مثال ضریب اصطلاح بالاترین درجه) به فواصل نامحدود گسترش می یابد . در -∞ نشانه ای از یک چند جمله ای به نشانه ضریب پیشرو آن برای یک چند جمله ای حتی درجه، و علامت مخالف برای یک چندجملهای از درجه فرد است.
در مورد یک چند جمله ای غیر آزاد مربع، اگر نه و نه ب ریشه های متعدد از است p ، پس از آن V ( ) - V ( ب ) تعداد است متمایز ریشه های حقیقی P .
اثبات قضیه به شرح زیر است: وقتی مقدار x از a به b افزایش یابد ، ممکن است از صفر برخی عبور کند( i > 0 )؛ وقتی این اتفاق می افتد ، تعداد تغییرات علامت ازتغییر نمی کند. وقتی x از یک ریشه عبور می کند تعداد تغییرات علائم از 1 به 0 کاهش می یابد. این تنها مقادیر x است که ممکن است برخی از علائم تغییر کند.مثال [ ویرایش ]
فرض کنید ما می خواهیم تعداد ریشه ها را در چند دامنه برای چند جمله ای پیدا کنیم. بنابراین

باقی مانده از تقسیم اقلیدسی از p 0 توسط p 1 استضرب آن را با 1 پوند بدست می آوریم
.
تقسیم بعدی p 1 بر p 2 و ضرب باقیمانده توسط − 1 ، به دست می آوریم
.
اکنون p 2 را بر p 3 تقسیم می کنیم و باقیمانده را با − 1 ضرب می کنیم ، به دست می آوریم
.
از آنجا که این یک ثابت است ، این محاسبه محاسبات دنباله استورم را تمام می کند.
برای پیدا کردن تعداد ریشه های واقعی یکی به ارزیابی توالی از نشانه های این چند جمله ای در -∞ و ∞ ، که به ترتیب (+، -، +، +، -) و (+، +، +، -، -) . بدین ترتیب

که نشان می دهد p دارای دو ریشه واقعی است.
این امر را می توان با ذکر این نکته تأیید کرد که p ( x ) را می توان به عنوان ( x 2 - 1) ( x 2 + x + 1) تعیین کرد ، جایی که عامل اول دارای ریشه −1 و 1 است و فاکتور دوم ریشه واقعی ندارد. این آخرین ادعا از فرمول درجه دوم و همچنین از قضیه اشتورم حاصل می شود که توالی های علامت (+ ، - ، -) را در −∞ و (+ ، + ، -) در + gives به دست می دهد .تعمیم [ ویرایش ]
توالی Sturm از دو جهت تعمیم یافته است. برای تعریف هر چند جمله ای در دنباله ، Sturm از منفی باقی مانده تقسیم اقلیدسی دو مورد قبلی استفاده کرد. این قضیه صادق است اگر کسی منفی باقیمانده را توسط محصول یا مقدار آن با یک ثابت مثبت یا مربع چند جمله ای جایگزین کند. همچنین در نظر گرفتن سکانس هایی که چند جمله ای دوم مشتق اول نیست ، مفید است (در زیر مراجعه کنید).
توالی استورم تعمیم یک دنباله متناهی از چند جمله ای با ضرایب حقیقی است

به طوری کهدرجه بعد از درجه اول کاهش می یابد:برای i = 2 ، ... ، m ؛ هیچ ریشه واقعی ندارد و یا نشانه ای را در نزدیکی ریشه واقعی خود تغییر نمی دهد.اگر P i ( ξ ) = 0 برای 0 i m و ξ یک عدد واقعی باشد ، P P - 1 ( ξ ) P i + 1 ( ξ )
شرط آخر دلالت بر این دارد که دو چند جمله ای متوالی هیچ ریشه واقعی مشترکی ندارند. به طور خاص ، توالی اصلی استورم یک توالی استورم تعمیم یافته است ، اگر (و تنها در صورت این کار) چند جمله ای دارای ریشه واقعی چندگانه نیست (در غیر این صورت ، دو چند جمله ای اول دنباله استورم دارای یک ریشه مشترک هستند).
هنگام محاسبه توالی اصلی استورم  توسط تقسیم اقلیدسی ، ممکن است اتفاق بیفتد که شخص با چند جمله ای روبرو شود که عاملی دارد که هرگز منفی نباشد ، چنین  یا. در این حالت ، اگر کسی محاسبات را با چند جمله ای که توسط فاکتور غیر منفی جایگزین آن شده است ، ادامه دهد ، یک دنبالهاستورم تعمیم داده می شود که ممکن است برای محاسبه تعداد ریشه های واقعی نیز استفاده شود ، زیرا اثبات قضیه Sturm هنوز هم اعمال می شود ( به دلیل شرط سوم). این ممکن است گاهی اوقات محاسبه را ساده کند ، اگرچه پیدا کردن چنین عواملی غیر منفی به استثنای قدرتهای x حتی معمولاً دشوار است .استفاده از توالی های شبه باقیمانده [ ویرایش ]
در جبر رایانه ، چند جمله ای که در نظر گرفته می شود ضرایب عدد صحیح دارند یا ممکن است به ضرایب عدد صحیح تبدیل شوند. دنباله Sturm از چند جمله ای با ضرایب عدد صحیح ، عموماً شامل چند جمله ای است که ضرایب آن عدد صحیح نیستند (مثال بالا را ببینید).
برای جلوگیری از محاسبه با اعداد منطقی ، یک روش معمول جایگزینی تقسیم اقلیدسی توسط تقسیم شبه برای محاسبه بزرگترین تقسیم کننده های چند جمله ای است . این به معنای جایگزینی توالی باقیمانده الگوریتم اقلیدسی توسط یک دنباله شبه باقیمانده است ، یک دنباله شبه باقیمانده یک دنباله است. از چند جمله ای به طوری که ثابت وجود دارد  و  به طوری که بخش باقیمانده بخش اقلیدسی است  توسط  (انواع مختلف توالی های شبه باقیمانده با انتخاب گزینه ها تعریف می شوند و  معمولا، برای معرفی مخرج در طول تقسیم اقلیدسی انتخاب نشده است ، و یک تقسیم کننده مشترک ضرایب باقیمانده است. دیدن دنباله شبه باقی مانده برای جزئیات بیشتر.) به عنوان مثال، دنباله باقی مانده از الگوریتم اقلیدسی رشته شبه باقی مانده استبرای هر من ، و دنباله استورم از چند جمله ای یک دنباله شبه باقیمانده با است و برای هر من .
توالی های شبه باقیمانده مختلف برای محاسبه بزرگترین تقسیم کننده مشترک چند جمله ای با ضرایب عدد صحیح و بدون معرفی مخرج طراحی شده اند ( دنباله شبه باقیمانده را ببینید ). همه آنها را می توان با انتخاب علامت توالی استورم تعمیم داد برعکس نشانه  این امکان استفاده از قضیه استورم را با توالی شبه باقی مانده فراهم می کند.جداسازی ریشه [ ویرایش ]
برای چند جمله ای با ضرایب واقعی ، جداسازی ریشه شامل یافتن ، برای هر ریشه واقعی ، بازه ای است که شامل این ریشه است و هیچ ریشه دیگری ندارد.
این برای یافتن ریشه مفید است و امکان انتخاب ریشه فراهم می شود و نقطه شروع خوبی برای الگوریتم های عددی سریع مانند روش نیوتن است . همچنین برای تأیید نتیجه مفید است ، زیرا اگر روش نیوتن در خارج از فاصله زمانی همگرا شود ممکن است بلافاصله استنباط شود که به ریشه اشتباه همگرا می شود.
جداسازی ریشه برای محاسبه با اعداد جبری نیز مفید است . برای محاسبه با اعداد جبری ، یک روش معمول این است که آنها را به عنوان یک جفت چند جمله ای که عدد جبری یک ریشه است ، و یک فاصله انزوا نشان دهید. مثلا ممکن است توسط ابهامات نمایان شود
قضیه استورم راهی برای جداسازی ریشه های واقعی فراهم می کند که از کارایی کمتری (برای چند جمله ای ها با ضرایب عدد صحیح) نسبت به سایر روش های حاکم بر نشانه های دکارت برخوردار است . با این وجود ، در برخی شرایط ، عمدتاً برای مقاصد تئوری ، مفید است ، برای مثال برای الگوریتم های هندسه جبری واقعی که شامل نامتناهی ها است .
برای جداسازی ریشه های واقعی ، فرد از یک فاصله شروع می شود  حاوی تمام ریشه های واقعی ، یا ریشه های مورد علاقه (اغلب ، معمولاً در مشکلات جسمی ، فقط ریشه های مثبت جالب هستند) ، و یکی محاسبه می کند  و برای تعریف این بازه شروع ، می توانید از اندازه ریشه ها استفاده کنید (به ویژگی های ریشه چند جمله ای: محدودیت های روی ریشه های چند جملهای (پیچیده) مراجعه کنید ). سپس ، با انتخاب c در وسط ، این فاصله را به دو قسمت تقسیم می کنیم محاسبه  تعداد ریشه های واقعی را در  و و ممکن است یکی از عملیات های مشابه در هر زیر زیر تکرار شود. هنگامی که فرد مواجه می شود ، در طی این فرآیند فاصله ای که هیچ ریشه ای ندارد ، ممکن است از لیست فواصل مورد نظر سرکوب شود. هنگامی که یک فرد با فاصله ای دقیقاً یک ریشه روبرو می شود ، ممکن است فرد از تقسیم آن متوقف شود ، زیرا این یک فاصله ایزوله است. این فرآیند سرانجام متوقف می شود ، هنگامی که فقط فواصل ایزوله سازی باقی می ماند.
این فرایند جداسازی ممکن است با هر روشی برای محاسبه تعداد ریشه های واقعی در یک بازه استفاده شود. تجزیه و تحلیل پیچیدگی نظری و تجربیات عملی نشان می دهد که روش های مبتنی بر قانون علائم دکارت کارایی بیشتری دارند. از این رو نتیجه می گیرد که امروزه ، توالی استورم  بندرت برای جداسازی ریشه استفاده می شود.برنامه [ ویرایش ]
توالی استورم Generalized اجازه می دهد تا ریشه های چند جمله ای را که چند جمله ای دیگری نیز مثبت است (یا منفی) شمرده ، بدون محاسبه صریح این ریشه. اگر کسی فاصله ایزوله کننده برای ریشه اولین چند جملهای خود را بداند ، این امکان را می دهد تا بدون محاسبه تقریبی بهتر ریشه ، علامت چند جملهای دوم را نیز در این ریشه خاص چند جملهای اول پیدا کنید.
بگذارید( P ( x  و (Q ( x  دو چند جمله ای با ضرایب واقعی باشند به گونه ای که P و Q هیچ ریشه مشترکی ندارند و P دارای ریشه چندگانه نیست. به عبارت دیگر ، P و P '  Q چند جمله ای های coprime هستند . این محدودیت واقعاً بر کلی بودن آنچه در پی می آید تأثیر نمی گذارد ، زیرا محاسبات GCD اجازه می دهد تا پرونده کلی را برای این مورد کاهش دهیم ، و هزینه محاسبه یک دنبالهاستورم همان اندازه یک GCD است.
بگذارید W ( a ) تعداد تغییرات علامت را در یک توالی استورم تعمیم یافته با شروع از P و P '  Q مشخص کند . اگر a b دو عدد واقعی باشد ، W ( a ) - W ( b ) تعداد ریشه های P در فاصله استبه گونه ای که Q ( a )> 0 منفی تعداد ریشه ها در همان فاصله است به گونه ای که Q ( a ) P در همان بازه ای که با قضیه استورم داده شده است ، این تعداد ریشه های P را به گونه ای می دهد که Q ( a )> 0 و تعداد ریشه های P به گونه ای باشد که Q ( a ) [1]
حداکثر درجه P است .
تعداد تغییرات علامت در ξ دنباله
در ریاضیات ، دنباله استورم از یک چند جمله ای p یک متغیره ، دنباله ای از چندجملهای مرتبط با p و مشتق آن با یک نوع از الگوریتم اقلیدس برای چندجملهای است . قضیه استورم بیان تعداد متمایز واقعی ریشه ازp واقع در یک فاصله زمانی از نظر تعدادی از تغییرات نشانه هایی از ارزش های دنباله استورم در مرزهای فاصله. با استفاده از فاصله همه اعداد واقعی ، تعداد کل ریشه های واقعی p را نشان می دهد . [1]
در حالی که قضیه اساسی جبر به راحتی تعداد کلی ریشه های پیچیده را که با کثرت شمارش می شود ، به دست می آورد ، روشی برای محاسبه آنها ارائه نمی دهد. قضیه استورم تعداد ریشه های واقعی متمایز را شمرده و آنها را در فواصل زمانی قرار می دهد. با تقسیم فواصل حاوی برخی از ریشه ها ، می توان ریشه ها را در فواصل کوچک دلخواه جدا کرد که هر یک دقیقاً یک ریشه دارد. این بازده قدیمی ترین الگوریتم جداسازی ریشه واقعی و الگوریتم دقیق یافتن ریشه برای چندجملهای یک متغیره است.
برای محاسبه طول اعداد حقیقی ، قضیه استورم کارآمد کمتر از روش های دیگر بر اساس است حکومت دکارت از نشانه . با این حال ، آن را در هر زمینه بسته واقعی کار می کند ، و بنابراین ، برای مطالعه نظری پیچیدگی محاسباتی از تجزیه پذیری و حذف کمی در تئوری مرتبه اول اعداد واقعی اساسی است.
توالی استورم و قضیه استورم به نام ژاک چارلز فرانسوا استورم نامگذاری شده است که در سال 1829 قضیه را کشف کرد. [2]
 فهرست1قضیه2مثال3تعمیم4استفاده از توالی های شبه باقیمانده5جداسازی ریشه6کاربرد7همچنین ببینید8منابعقضیه [ ویرایش ]
زنجیره استورم و یا توالی استورم یک چند جمله ای های تک متغیری P ( X ) با ضرایب حقیقی دنباله ای از چند جمله ای است به طوری که

برای من ≥ 1 ، که در آن P ' است مشتق از P ، وباقی مانده از است تقسیم اقلیدسی از توسططول دنباله Sturm حداکثر درجه P است .
تعداد تغییرات علامت در ξ دنباله Sturm از P تعداد تغییرات علامت-نادیده گرفتن صفرها در دنباله اعداد واقعی است

این تعداد از علائم در اینجا( V ( ξ مشخص شده است .
کشورهای قضیه استورم که اگر P است چند جمله ای رایگان مربع ، تعداد ریشه حقیقی متمایز از P در فاصله نیمه باز ( ، ب ] است V ( ) - V ( ب ) (در اینجا، و ب هستند اعداد واقعی به گونه ای که یک b ). [1]
قضیه با تعیین علامت در + ∞ چند جمله ای به عنوان علامت ضریب پیشرو آن (به عنوان مثال ضریب اصطلاح بالاترین درجه) به فواصل نامحدود گسترش می یابد . در -∞ نشانه ای از یک چند جمله ای به نشانه ضریب پیشرو آن برای یک چند جمله ای حتی درجه، و علامت مخالف برای یک چندجملهای از درجه فرد است.
در مورد یک چند جمله ای غیر آزاد مربع، اگر نه و نه ب ریشه های متعدد از است p ، پس از آن V ( ) - V ( ب ) تعداد است متمایز ریشه های حقیقی P .
اثبات قضیه به شرح زیر است: وقتی مقدار x از a به b افزایش یابد ، ممکن است از صفر برخی عبور کند( i > 0 )؛ وقتی این اتفاق می افتد ، تعداد تغییرات علامت ازتغییر نمی کند. وقتی x از یک ریشه عبور می کند تعداد تغییرات علائم از 1 به 0 کاهش می یابد. این تنها مقادیر x است که ممکن است برخی از علائم تغییر کند.مثال [ ویرایش ]
فرض کنید ما می خواهیم تعداد ریشه ها را در چند دامنه برای چند جمله ای پیدا کنیم. بنابراین

باقی مانده از تقسیم اقلیدسی از p 0 توسط p 1 استضرب آن را با 1 پوند بدست می آوریم
.
تقسیم بعدی p 1 بر p 2 و ضرب باقیمانده توسط − 1 ، به دست می آوریم
.
اکنون p 2 را بر p 3 تقسیم می کنیم و باقیمانده را با − 1 ضرب می کنیم ، به دست می آوریم
.
از آنجا که این یک ثابت است ، این محاسبه محاسبات دنباله استورم را تمام می کند.
برای پیدا کردن تعداد ریشه های واقعی یکی به ارزیابی توالی از نشانه های این چند جمله ای در -∞ و ∞ ، که به ترتیب (+، -، +، +، -) و (+، +، +، -، -) . بدین ترتیب

که نشان می دهد p دارای دو ریشه واقعی است.
این امر را می توان با ذکر این نکته تأیید کرد که p ( x ) را می توان به عنوان ( x 2 - 1) ( x 2 + x + 1) تعیین کرد ، جایی که عامل اول دارای ریشه −1 و 1 است و فاکتور دوم ریشه واقعی ندارد. این آخرین ادعا از فرمول درجه دوم و همچنین از قضیه اشتورم حاصل می شود که توالی های علامت (+ ، - ، -) را در −∞ و (+ ، + ، -) در + gives به دست می دهد .تعمیم [ ویرایش ]
توالی Sturm از دو جهت تعمیم یافته است. برای تعریف هر چند جمله ای در دنباله ، Sturm از منفی باقی مانده تقسیم اقلیدسی دو مورد قبلی استفاده کرد. این قضیه صادق است اگر کسی منفی باقیمانده را توسط محصول یا مقدار آن با یک ثابت مثبت یا مربع چند جمله ای جایگزین کند. همچنین در نظر گرفتن سکانس هایی که چند جمله ای دوم مشتق اول نیست ، مفید است (در زیر مراجعه کنید).
توالی استورم تعمیم یک دنباله متناهی از چند جمله ای با ضرایب حقیقی است

به طوری کهدرجه بعد از درجه اول کاهش می یابد:برای i = 2 ، ... ، m ؛ هیچ ریشه واقعی ندارد و یا نشانه ای را در نزدیکی ریشه واقعی خود تغییر نمی دهد.اگر P i ( ξ ) = 0 برای 0 i m و ξ یک عدد واقعی باشد ، P P - 1 ( ξ ) P i + 1 ( ξ )
شرط آخر دلالت بر این دارد که دو چند جمله ای متوالی هیچ ریشه واقعی مشترکی ندارند. به طور خاص ، توالی اصلی استورم یک توالی استورم تعمیم یافته است ، اگر (و تنها در صورت این کار) چند جمله ای دارای ریشه واقعی چندگانه نیست (در غیر این صورت ، دو چند جمله ای اول دنباله استورم دارای یک ریشه مشترک هستند).
هنگام محاسبه توالی اصلی استورم  توسط تقسیم اقلیدسی ، ممکن است اتفاق بیفتد که شخص با چند جمله ای روبرو شود که عاملی دارد که هرگز منفی نباشد ، چنین  یا. در این حالت ، اگر کسی محاسبات را با چند جمله ای که توسط فاکتور غیر منفی جایگزین آن شده است ، ادامه دهد ، یک دنبالهاستورم تعمیم داده می شود که ممکن است برای محاسبه تعداد ریشه های واقعی نیز استفاده شود ، زیرا اثبات قضیه Sturm هنوز هم اعمال می شود ( به دلیل شرط سوم). این ممکن است گاهی اوقات محاسبه را ساده کند ، اگرچه پیدا کردن چنین عواملی غیر منفی به استثنای قدرتهای x حتی معمولاً دشوار است .استفاده از توالی های شبه باقیمانده [ ویرایش ]
در جبر رایانه ، چند جمله ای که در نظر گرفته می شود ضرایب عدد صحیح دارند یا ممکن است به ضرایب عدد صحیح تبدیل شوند. دنباله Sturm از چند جمله ای با ضرایب عدد صحیح ، عموماً شامل چند جمله ای است که ضرایب آن عدد صحیح نیستند (مثال بالا را ببینید).
برای جلوگیری از محاسبه با اعداد منطقی ، یک روش معمول جایگزینی تقسیم اقلیدسی توسط تقسیم شبه برای محاسبه بزرگترین تقسیم کننده های چند جمله ای است . این به معنای جایگزینی توالی باقیمانده الگوریتم اقلیدسی توسط یک دنباله شبه باقیمانده است ، یک دنباله شبه باقیمانده یک دنباله است. از چند جمله ای به طوری که ثابت وجود دارد  و  به طوری که بخش باقیمانده بخش اقلیدسی است  توسط  (انواع مختلف توالی های شبه باقیمانده با انتخاب گزینه ها تعریف می شوند و  معمولا، برای معرفی مخرج در طول تقسیم اقلیدسی انتخاب نشده است ، و یک تقسیم کننده مشترک ضرایب باقیمانده است. دیدن دنباله شبه باقی مانده برای جزئیات بیشتر.) به عنوان مثال، دنباله باقی مانده از الگوریتم اقلیدسی رشته شبه باقی مانده استبرای هر من ، و دنباله استورم از چند جمله ای یک دنباله شبه باقیمانده با است و برای هر من .
توالی های شبه باقیمانده مختلف برای محاسبه بزرگترین تقسیم کننده مشترک چند جمله ای با ضرایب عدد صحیح و بدون معرفی مخرج طراحی شده اند ( دنباله شبه باقیمانده را ببینید ). همه آنها را می توان با انتخاب علامت توالی استورم تعمیم داد برعکس نشانه  این امکان استفاده از قضیه استورم را با توالی شبه باقی مانده فراهم می کند.جداسازی ریشه [ ویرایش ]
برای چند جمله ای با ضرایب واقعی ، جداسازی ریشه شامل یافتن ، برای هر ریشه واقعی ، بازه ای است که شامل این ریشه است و هیچ ریشه دیگری ندارد.
این برای یافتن ریشه مفید است و امکان انتخاب ریشه فراهم می شود و نقطه شروع خوبی برای الگوریتم های عددی سریع مانند روش نیوتن است . همچنین برای تأیید نتیجه مفید است ، زیرا اگر روش نیوتن در خارج از فاصله زمانی همگرا شود ممکن است بلافاصله استنباط شود که به ریشه اشتباه همگرا می شود.
جداسازی ریشه برای محاسبه با اعداد جبری نیز مفید است . برای محاسبه با اعداد جبری ، یک روش معمول این است که آنها را به عنوان یک جفت چند جمله ای که عدد جبری یک ریشه است ، و یک فاصله انزوا نشان دهید. مثلا ممکن است توسط ابهامات نمایان شود
قضیه استورم راهی برای جداسازی ریشه های واقعی فراهم می کند که از کارایی کمتری (برای چند جمله ای ها با ضرایب عدد صحیح) نسبت به سایر روش های حاکم بر نشانه های دکارت برخوردار است . با این وجود ، در برخی شرایط ، عمدتاً برای مقاصد تئوری ، مفید است ، برای مثال برای الگوریتم های هندسه جبری واقعی که شامل نامتناهی ها است .
برای جداسازی ریشه های واقعی ، فرد از یک فاصله شروع می شود  حاوی تمام ریشه های واقعی ، یا ریشه های مورد علاقه (اغلب ، معمولاً در مشکلات جسمی ، فقط ریشه های مثبت جالب هستند) ، و یکی محاسبه می کند  و برای تعریف این بازه شروع ، می توانید از اندازه ریشه ها استفاده کنید (به ویژگی های ریشه چند جمله ای: محدودیت های روی ریشه های چند جملهای (پیچیده) مراجعه کنید ). سپس ، با انتخاب c در وسط ، این فاصله را به دو قسمت تقسیم می کنیم محاسبه  تعداد ریشه های واقعی را در  و و ممکن است یکی از عملیات های مشابه در هر زیر زیر تکرار شود. هنگامی که فرد مواجه می شود ، در طی این فرآیند فاصله ای که هیچ ریشه ای ندارد ، ممکن است از لیست فواصل مورد نظر سرکوب شود. هنگامی که یک فرد با فاصله ای دقیقاً یک ریشه روبرو می شود ، ممکن است فرد از تقسیم آن متوقف شود ، زیرا این یک فاصله ایزوله است. این فرآیند سرانجام متوقف می شود ، هنگامی که فقط فواصل ایزوله سازی باقی می ماند.
این فرایند جداسازی ممکن است با هر روشی برای محاسبه تعداد ریشه های واقعی در یک بازه استفاده شود. تجزیه و تحلیل پیچیدگی نظری و تجربیات عملی نشان می دهد که روش های مبتنی بر قانون علائم دکارت کارایی بیشتری دارند. از این رو نتیجه می گیرد که امروزه ، توالی استورم  بندرت برای جداسازی ریشه استفاده می شود.برنامه [ ویرایش ]
توالی استورم Generalized اجازه می دهد تا ریشه های چند جمله ای را که چند جمله ای دیگری نیز مثبت است (یا منفی) شمرده ، بدون محاسبه صریح این ریشه. اگر کسی فاصله ایزوله کننده برای ریشه اولین چند جملهای خود را بداند ، این امکان را می دهد تا بدون محاسبه تقریبی بهتر ریشه ، علامت چند جملهای دوم را نیز در این ریشه خاص چند جملهای اول پیدا کنید.
بگذارید( P ( x  و (Q ( x  دو چند جمله ای با ضرایب واقعی باشند به گونه ای که P و Q هیچ ریشه مشترکی ندارند و P دارای ریشه چندگانه نیست. به عبارت دیگر ، P و P '  Q چند جمله ای های coprime هستند . این محدودیت واقعاً بر کلی بودن آنچه در پی می آید تأثیر نمی گذارد ، زیرا محاسبات GCD اجازه می دهد تا پرونده کلی را برای این مورد کاهش دهیم ، و هزینه محاسبه یک دنبالهاستورم همان اندازه یک GCD است.
بگذارید W ( a ) تعداد تغییرات علامت را در یک توالی استورم تعمیم یافته با شروع از P و P '  Q مشخص کند . اگر a b دو عدد واقعی باشد ، W ( a ) - W ( b ) تعداد ریشه های P در فاصله استبه گونه ای که Q ( a )> 0 منفی تعداد ریشه ها در همان فاصله است به گونه ای که Q ( a ) P در همان بازه ای که با قضیه استورم داده شده است ، این تعداد ریشه های P را به گونه ای می دهد که Q ( a )> 0 و تعداد ریشه های P به گونه ای باشد که Q ( a ) [1]
منبع
https://en.wikipedia.org/wiki/Sturm%27s_theorem
از P تعداد تغییرات علامت-نادیده گرفتن صفرها در دنباله اعداد واقعی است

این تعداد از علائم در اینجا( V ( ξ مشخص شده است .
کشورهای قضیه استورم که اگر P است چند جمله ای رایگان مربع ، تعداد ریشه حقیقی متمایز از P در فاصله نیمه باز ( ، ب ] است V ( ) - V ( ب ) (در اینجا، و ب هستند اعداد واقعی به گونه ای که یک b ). [1]
قضیه با تعیین علامت در + ∞ چند جمله ای به عنوان علامت ضریب پیشرو آن (به عنوان مثال ضریب اصطلاح بالاترین درجه) به فواصل نامحدود گسترش می یابد . در -∞ نشانه ای از یک چند جمله ای به نشانه ضریب پیشرو آن برای یک چند جمله ای حتی درجه، و علامت مخالف برای یک چندجملهای از درجه فرد است.
در مورد یک چند جمله ای غیر آزاد مربع، اگر نه و نه ب ریشه های متعدد از است p ، پس از آن V ( ) - V ( ب ) تعداد است متمایز ریشه های حقیقی P .
اثبات قضیه به شرح زیر است: وقتی مقدار x از a به b افزایش یابد ، ممکن است از صفر برخی عبور کند( i > 0 )؛ وقتی این اتفاق می افتد ، تعداد تغییرات علامت ازتغییر نمی کند. وقتی x از یک ریشه عبور می کند تعداد تغییرات علائم از 1 به 0 کاهش می یابد. این تنها مقادیر x است که ممکن است برخی از علائم تغییر کند.مثال [ ویرایش ]
فرض کنید ما می خواهیم تعداد ریشه ها را در چند دامنه برای چند جمله ای پیدا کنیم. بنابراین

باقی مانده از تقسیم اقلیدسی از p 0 توسط p 1 استضرب آن را با 1 پوند بدست می آوریم
.
تقسیم بعدی p 1 بر p 2 و ضرب باقیمانده توسط − 1 ، به دست می آوریم
.
اکنون p 2 را بر p 3 تقسیم می کنیم و باقیمانده را با − 1 ضرب می کنیم ، به دست می آوریم
.
از آنجا که این یک ثابت است ، این محاسبه محاسبات دنباله استورم را تمام می کند.
برای پیدا کردن تعداد ریشه های واقعی یکی به ارزیابی توالی از نشانه های این چند جمله ای در -∞ و ∞ ، که به ترتیب (+، -، +، +، -) و (+، +، +، -، -) . بدین ترتیب

که نشان می دهد p دارای دو ریشه واقعی است.
این امر را می توان با ذکر این نکته تأیید کرد که p ( x ) را می توان به عنوان ( x 2 - 1) ( x 2 + x + 1) تعیین کرد ، جایی که عامل اول دارای ریشه −1 و 1 است و فاکتور دوم ریشه واقعی ندارد. این آخرین ادعا از فرمول درجه دوم و همچنین از قضیه اشتورم حاصل می شود که توالی های علامت (+ ، - ، -) را در −∞ و (+ ، + ، -) در + gives به دست می دهد .تعمیم [ ویرایش ]
توالی Sturm از دو جهت تعمیم یافته است. برای تعریف هر چند جمله ای در دنباله ، Sturm از منفی باقی مانده تقسیم اقلیدسی دو مورد قبلی استفاده کرد. این قضیه صادق است اگر کسی منفی باقیمانده را توسط محصول یا مقدار آن با یک ثابت مثبت یا مربع چند جمله ای جایگزین کند. همچنین در نظر گرفتن سکانس هایی که چند جمله ای دوم مشتق اول نیست ، مفید است (در زیر مراجعه کنید).
توالی استورم تعمیم یک دنباله متناهی از چند جمله ای با ضرایب حقیقی است

به طوری کهدرجه بعد از درجه اول کاهش می یابد:برای i = 2 ، ... ، m ؛ هیچ ریشه واقعی ندارد و یا نشانه ای را در نزدیکی ریشه واقعی خود تغییر نمی دهد.اگر P i ( ξ ) = 0 برای 0 i m و ξ یک عدد واقعی باشد ، P P - 1 ( ξ ) P i + 1 ( ξ )  .
شرط آخر دلالت بر این دارد که دو چند جمله ای متوالی هیچ ریشه واقعی مشترکی ندارند. به طور خاص ، توالی اصلی استورم یک توالی استورم تعمیم یافته است ، اگر (و تنها در صورت این کار) چند جمله ای دارای ریشه واقعی چندگانه نیست (در غیر این صورت ، دو چند جمله ای اول دنباله استورم دارای یک ریشه مشترک هستند).
هنگام محاسبه توالی اصلی استورم  توسط تقسیم اقلیدسی ، ممکن است اتفاق بیفتد که شخص با چند جمله ای روبرو شود که عاملی دارد که هرگز منفی نباشد ، چنین  یا. در این حالت ، اگر کسی محاسبات را با چند جمله ای که توسط فاکتور غیر منفی جایگزین آن شده است ، ادامه دهد ، یک دنبالهاستورم تعمیم داده می شود که ممکن است برای محاسبه تعداد ریشه های واقعی نیز استفاده شود ، زیرا اثبات قضیه Sturm هنوز هم اعمال می شود ( به دلیل شرط سوم). این ممکن است گاهی اوقات محاسبه را ساده کند ، اگرچه پیدا کردن چنین عواملی غیر منفی به استثنای قدرتهای x حتی معمولاً دشوار است .استفاده از توالی های شبه باقیمانده [ ویرایش ]
در جبر رایانه ، چند جمله ای که در نظر گرفته می شود ضرایب عدد صحیح دارند یا ممکن است به ضرایب عدد صحیح تبدیل شوند. دنباله Sturm از چند جمله ای با ضرایب عدد صحیح ، عموماً شامل چند جمله ای است که ضرایب آن عدد صحیح نیستند (مثال بالا را ببینید).
برای جلوگیری از محاسبه با اعداد منطقی ، یک روش معمول جایگزینی تقسیم اقلیدسی توسط تقسیم شبه برای محاسبه بزرگترین تقسیم کننده های چند جمله ای است . این به معنای جایگزینی توالی باقیمانده الگوریتم اقلیدسی توسط یک دنباله شبه باقیمانده است ، یک دنباله شبه باقیمانده یک دنباله است. از چند جمله ای به طوری که ثابت وجود دارد  و  به طوری که بخش باقیمانده بخش اقلیدسی است  توسط  (انواع مختلف توالی های شبه باقیمانده با انتخاب گزینه ها تعریف می شوند و  معمولا، برای معرفی مخرج در طول تقسیم اقلیدسی انتخاب نشده است ، و یک تقسیم کننده مشترک ضرایب باقیمانده است. دیدن دنباله شبه باقی مانده برای جزئیات بیشتر.) به عنوان مثال، دنباله باقی مانده از الگوریتم اقلیدسی رشته شبه باقی مانده استبرای هر من ، و دنباله استورم از چند جمله ای یک دنباله شبه باقیمانده با است و برای هر من .
توالی های شبه باقیمانده مختلف برای محاسبه بزرگترین تقسیم کننده مشترک چند جمله ای با ضرایب عدد صحیح و بدون معرفی مخرج طراحی شده اند ( دنباله شبه باقیمانده را ببینید ). همه آنها را می توان با انتخاب علامت توالی استورم تعمیم داد برعکس نشانه  این امکان استفاده از قضیه استورم را با توالی شبه باقی مانده فراهم می کند.جداسازی ریشه [ ویرایش ]
برای چند جمله ای با ضرایب واقعی ، جداسازی ریشه شامل یافتن ، برای هر ریشه واقعی ، بازه ای است که شامل این ریشه است و هیچ ریشه دیگری ندارد.
این برای یافتن ریشه مفید است و امکان انتخاب ریشه فراهم می شود و نقطه شروع خوبی برای الگوریتم های عددی سریع مانند روش نیوتن است . همچنین برای تأیید نتیجه مفید است ، زیرا اگر روش نیوتن در خارج از فاصله زمانی همگرا شود ممکن است بلافاصله استنباط شود که به ریشه اشتباه همگرا می شود.
جداسازی ریشه برای محاسبه با اعداد جبری نیز مفید است . برای محاسبه با اعداد جبری ، یک روش معمول این است که آنها را به عنوان یک جفت چند جمله ای که عدد جبری یک ریشه است ، و یک فاصله انزوا نشان دهید. مثلا ممکن است توسط ابهامات نمایان شود
قضیه استورم راهی برای جداسازی ریشه های واقعی فراهم می کند که از کارایی کمتری (برای چند جمله ای ها با ضرایب عدد صحیح) نسبت به سایر روش های حاکم بر نشانه های دکارت برخوردار است . با این وجود ، در برخی شرایط ، عمدتاً برای مقاصد تئوری ، مفید است ، برای مثال برای الگوریتم های هندسه جبری واقعی که شامل نامتناهی ها است .
برای جداسازی ریشه های واقعی ، فرد از یک فاصله شروع می شود  حاوی تمام ریشه های واقعی ، یا ریشه های مورد علاقه (اغلب ، معمولاً در مشکلات جسمی ، فقط ریشه های مثبت جالب هستند) ، و یکی محاسبه می کند  و برای تعریف این بازه شروع ، می توانید از اندازه ریشه ها استفاده کنید (به ویژگی های ریشه چند جمله ای: محدودیت های روی ریشه های چند جملهای (پیچیده) مراجعه کنید ). سپس ، با انتخاب c در وسط ، این فاصله را به دو قسمت تقسیم می کنیم محاسبه  تعداد ریشه های واقعی را در  و و ممکن است یکی از عملیات های مشابه در هر زیر زیر تکرار شود. هنگامی که فرد مواجه می شود ، در طی این فرآیند فاصله ای که هیچ ریشه ای ندارد ، ممکن است از لیست فواصل مورد نظر سرکوب شود. هنگامی که یک فرد با فاصله ای دقیقاً یک ریشه روبرو می شود ، ممکن است فرد از تقسیم آن متوقف شود ، زیرا این یک فاصله ایزوله است. این فرآیند سرانجام متوقف می شود ، هنگامی که فقط فواصل ایزوله سازی باقی می ماند.
این فرایند جداسازی ممکن است با هر روشی برای محاسبه تعداد ریشه های واقعی در یک بازه استفاده شود. تجزیه و تحلیل پیچیدگی نظری و تجربیات عملی نشان می دهد که روش های مبتنی بر قانون علائم دکارت کارایی بیشتری دارند. از این رو نتیجه می گیرد که امروزه ، توالی استورم  بندرت برای جداسازی ریشه استفاده می شود.برنامه [ ویرایش ]
توالی استورم Generalized اجازه می دهد تا ریشه های چند جمله ای را که چند جمله ای دیگری نیز مثبت است (یا منفی) شمرده ، بدون محاسبه صریح این ریشه. اگر کسی فاصله ایزوله کننده برای ریشه اولین چند جملهای خود را بداند ، این امکان را می دهد تا بدون محاسبه تقریبی بهتر ریشه ، علامت چند جملهای دوم را نیز در این ریشه خاص چند جملهای اول پیدا کنید.
بگذارید( P ( x  و (Q ( x  دو چند جمله ای با ضرایب واقعی باشند به گونه ای که P و Q هیچ ریشه مشترکی ندارند و P دارای ریشه چندگانه نیست. به عبارت دیگر ، P و P '  Q چند جمله ای های coprime هستند . این محدودیت واقعاً بر کلی بودن آنچه در پی می آید تأثیر نمی گذارد ، زیرا محاسبات GCD اجازه می دهد تا پرونده کلی را برای این مورد کاهش دهیم ، و هزینه محاسبه یک دنبالهاستورم همان اندازه یک GCD است.
بگذارید W ( a ) تعداد تغییرات علامت را در یک توالی استورم تعمیم یافته با شروع از P و P '  Q مشخص کند . اگر a b دو عدد واقعی باشد ، W ( a ) - W ( b ) تعداد ریشه های P در فاصله استبه گونه ای که Q ( a )> 0 منفی تعداد ریشه ها در همان فاصله است به گونه ای که Q ( a )  . همراه با تعداد کل ریشه های P در همان بازه ای که با قضیه استورم داده شده است ، این تعداد ریشه های P را به گونه ای می دهد که Q ( a )> 0 و تعداد ریشه های P به گونه ای باشد که Q ( a )  . [1]
منبع
https://en.wikipedia.org/wiki/Sturm%27s_theorem