موضوع مقاله: روش نیوتن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش نیوتن | مقدمه: در آنالیز عددی روش نیوتن، که همچنین به عنوان روش نیوتن-رافسون نیز شناخته می‌شود الگوریتم ریشه یابی است که تقریب‌های خوبی در نزدیکی ریشه یک تابع (صفرهای یک تابع) می‌زند. | ## بخش 1: روش نیوتن | در پایه ای‌ترین حالت، الگوریتم نیوتن برای یک تابعی چون با متغیر و با مشتق به همراه حدس اولیه بکار می‌رود. اگر تابع حدس کافی و دقیقی را برآورد سازد و همچنین حدس اولیه نزدیک به ریشه تابع مفروض باشد (که با همگرایی تقریب‌ها این موضوع روشن می‌شود) آنگاه تقریب بهتری نسبت به به حساب می‌آید. چرا که با احتساب همگرایی جواب‌ها، هر تقریب نسبت به تقریب قبل از خودش از دقت بالاتری برخوردار بوده و به ریشه تابع نزدیک تر است. می‌دانیم که در نقطهٔ برخورد تابع با محور مقدار تابع صفر خواهد بود لذا که در آخر با تقسیم بر می‌توان رابطه را به فرم رو به رو بازنویسی کرد: همان‌طور که مشهود است روش نیوتن-رافسون از سری تیلور ناقص تابع مفروض به عنوان یک تقریب خطی حول نقطهٔ حدس اولیه بهره می‌برد و از این جهت تقریب را ناقص می‌گویند که نیازی به نوشتن سری تابع تا مراتب بالاتر نبوده و به همان دو جمله ابتدایی بسنده می‌کند که این موضوع نیز دلیلی بر تقریب خطی بودن روش نیوتن می‌باشد. همچنین چون این روش معادلهٔ یک تابع را تا معادلهٔ یک تابع درجه یک تقیل می‌دهد، لذا صرف نظر از اینکه تابع چند ریشه دارد، در نهایت الگوریتم تنها یک جواب بدست می‌آورد. شرح سازوکار روش نیوتن شروع مراحل تخمین ریشه با انتخاب یک حدس اولیه است که به اندازه لازم به مقدار واقعی ریشه نزدیک باشد، سپس می‌توان با استفاده از خط مماس تابع را تقریب زد و نهایتاً با توجه به خط مماس طول از مبدأ (ریشه تقریب خطی) را معین ساخت. ریشه تقریب معمولاً تقریب بهتری از ریشه واقعی تابع نسبت به حدس اولیه است و الگوریتم به همین منوال می‌تواند تکرار شود. عدم موفقیت الگوریتم روش نیوتن تنها زمانی یافتن ریشه تقریبی را تضمین می‌کند که شرایطی برقرار باشد. نقاطی با شروع بد در برخی مواقع شرایطی که برای همگرایی لازم است برقرار است، اما نقطهٔ که به عنوان حدس اولیه انتخاب شده دربازه ای که روش نیوتن همگرایی دارد قرار نمی‌گیرد. | ## بخش 2: روش نیوتن | این شرایط زمانی می‌تواند اتفاق بیفتد که برای مثال همچنان که به یا میل می‌کند ریشه تابع به‌طور متناوب و به اندازه کافی و مطلوبی به صفر نزدیک شود. در اینگونه موارد روش بهتری مانند روش دوبخشی (تنصیف) باید بکار گرفته شود تا تخمین بهتری بدست آورد. زمانی که نقطهٔ تکرار ثابت است به تابع: دقت کنید: این تابع در نقطهٔ ماکسیمم دارد و ریشه‌های آن و می‌باشد. اگر تکرار را از شروع کنیم (نقطه ای که مشتق آن صفر و شیب خط تابع افقی است) تعریف نشده خواهد بود: حتی اگر مشتق تابع در آن نقطه نزدیک به صفر باشد آنگاه تکرار مرحله، تقریب به مراتب بدتری را به همراه خواهد داشت. حدس اولیه به یک دایره منتهی می‌شود در برخی توابع، بعضی از نقاطی که به عنوان حدس اولیه انتخاب می‌شوند ممکن است که به یک دایره ختم شوند که این می‌تواند مانع از همگرایی شود. نخستین مرحله جواب را بدست می آوردو دومین مرحله دوباره به می‌رسد، بنابراین جواب‌ها مدام بین دو مقدار مذکور تناوب می‌کند. مثالها جذر یک عدد با توجه به یافتن جذر یک عدد، روش نیوتن یکی از چندین راهی است که می‌توان از آن بهره گرفت. سپس تابعی را که قصد داریم تا روش نیوتن را برای آن بکار ببندیم می‌توان به فرم در نظر گرفت که مشتق آن نیز خواهد بود. اگر حدس اولیه را در نظر بگیریم آنگاه الگوریتم نیوتن به صورت زیر محاسبه را انجام خواهد داد: جاییکه که زیر رقم صحیح خط کشیده شده است، تنها با چند تکرار می‌توان به یک جواب دقیق با ارقام اعشاری دست یافت. | ## بخش 3: روش نیوتن | در صورت هگرایی هرچه روش را تکرار کنیم جواب‌ها دقیق تر و ارقام بعد اعشار نیز به مراتب از دقت بیش تری برخوردار خواهند بود. همان‌طور که مشخص است برخی از ارقام بعد ممیز در هر مرحله تکرار می‌شوند که این نشان از دقت و قطعیت آنها دارد. می‌دانیم که پاسخ معادله بین و قرار دارد لذا حدس اولیه را با شروع می‌کنیم (توجه داشته باشید که اگر حدس اولیه را با شروع می‌کردیم آنگاه به یک نتیجه تعریف نشده می‌رسیدیم، این موضوع اهمیت انتخاب حدس اولیه را به خوبی روشن می‌سازد که به اندازه کافی باید به جواب واقعی نزدیک باشد). می‌بینیم که تعداد ارقام صحیح از ۲ رقم برای تا ۱۰ رقم برای در حال افزایش است که نشان دهنده همگرایی است. مقایسه سرعت همگرایی در روش‌های مختلف در این قسمت اهمیت انتخاب روش مناسب به خوبی مشخص خواهد شد، چرا که سرعت همگرایی الگوریتم‌های مذکور با یکدیگر متفاوت است. همان‌طور که نمایان است همهٔ الگوریتم‌های بکار گرفته شده تنها قادر به یافتن یک جواب در یک بازه معین هستند. نیوتن-رافسوندوبخشی (تنصیف)وتری (خط قاطع)نابجایی۱٫۵۱۴۴۸۴۶۰۶۹۹۲۶۳۴۳۲۱٫۰۱۴۲۶۰۸۹۰۲۱۸۸۵۱۷۱٫۰۱۴۲۶۰۸۹۰۲۱۸۸۵۱۷۱٫۲۴۰۹۰۱۵۸۲۲۲۱۷۸۰۶۱٫۵۱٫۰۲۶۸۶۵۲۰۷۶۷۹۴۸۶۹۱٫۰۲۶۸۶۵۲۰۷۶۷۹۴۸۶۹۱٫۱۲۸۸۷۸۴۳۸۹۱۳۲۱۷۲۱٫۲۵۱٫۱۲۲۷۷۴۲۱۸۸۶۲۹۷۸۶۱٫۰۳۷۹۴۲۹۳۱۷۰۰۹۱۱۷۱٫۱۰۷۷۹۴۰۰۳۲۱۶۴۶۳۷۱٫۱۲۵۱٫۱۰۴۸۰۸۲۴۲۲۶۸۰۳۳۹۱٫۰۴۷۶۳۰۶۵۶۷۲۰۶۹۹۱٫۱۰۷۰۵۷۱۴۳۶۹۶۹۳۲۳۱٫۰۶۲۵۱٫۱۰۶۹۹۹۴۱۹۵۵۶۴۶۱۹۱٫۰۵۶۰۶۵۸۱۵۹۷۸۸۷۶۱٫۱۰۷۰۵۶۲۵۴۶۳۹۰۶۴۵۱٫۰۹۳۷۵۱٫۱۰۷۰۵۶۴۶۴۳۶۵۰۱۱۲۱٫۰۶۳۳۸۲۲۹۹۱۱۶۲۰۱۶—۱٫۱۰۹۳۷۵—۱٫۰۶۹۷۰۷۳۳۹۸۰۷۴۵۱۷—۱٫۱۰۷۱۱۶۶۹۹۲۱۸۷۵—۱٫۰۹۶۷۴۶۸۲۹۶۷۱۲۸۸ — — —۱٫۱۰۶۵۲۷۵۹۷۶۲۰۱۲۳ در این مثال سرعت همگرایی دو روش وتری (خط قاطع) و روش نیوتن با یکدیگر تقریباً برابر است، همچنین مشاهده می‌شود که کندترین روش در این مثال الگوریتم نابجایی می‌باشد، اما به‌طور کل نمی‌توان این مثال خاص را به تمامی مثال‌ها تعمیم داد چرا که همواره سرعت همگرایی متغیر بوده و به شرایط مختلفی بستگی دارد، لذا انتخاب بهترین روش می‌تواند سهم به سزایی در سرعت عملیات تقریب زنی داشته باشد. همچنین مسئلهٔ دیگر که مطرح است این موضوع می‌باشد که هر کدام از روش‌ها مزایا و معایب خود را دارا هستند، برای مثال از معایب روش نیوتن عدم جواب در صورتی ست که مشتق تابع در نقطهٔ مورد نظر صفر یا نزدیک به صفر باشد یا ایجاد سختی در هنگامی ست که مشتق‌گیری تابع عملیاتی دشوار باشد و از مزایای آن همگرایی سریع در صورت انتخاب حدس اولیه مناسب است، اما باید توجه داشت همگرایی روش نیوتن-رافسون برخلاف برخی روش‌ها مانند روش دوبخشی تضمینی نیست. نقش انتخاب بازه در تعیین ریشه یکی از موارد کلیدی در اینکه روش مورد استفاده به کدام یک از ریشه‌های تابع (در صورت وجود بیش از یک ریشه) همگرا شود انتخاب بازه می‌باشد. | ## جمع‌بندی | برای مثال تابع را در نظر بگیرید و نقطهٔ را به عنوان حدس اولیه اختیار کنید: نیوتن-رافسوندوبخشی (تنصیف)وتری (خط قاطع)نابجایی۲٫۹۳۸۱۰۰۳۹۳۹۷۳۵۹۹۱٫۱۷۰۱۲۰۲۳۹۲۵۷۸۱۲۵۱٫۱۷۰۱۲۰۹۴۸۰۹۷۴۰۰۴۱٫۱۷۰۱۱۹۹۹۵۷۱۶۲۵۱۴ در معادلهٔ فوق بازهٔ انتخاب شده برای هر چهار روش یکسان بوده اما ریشهٔ تقریبی حاصل از روش نیوتن متفاوت از سایرین است.