روش نیوتن کیست؟ توضیح بده.
در آنالیز عددی روش نیوتن، که همچنین به عنوان روش نیوتن-رافسون نیز شناخته می‌شود الگوریتم ریشه یابی است که تقریب‌های خوبی در نزدیکی ریشه یک تابع (صفرهای یک تابع) می‌زند. در پایه ای‌ترین حالت، الگوریتم نیوتن برای یک تابعی چون formula_1 با متغیر formula_2 و با مشتق formula_3 به همراه حدس اولیه formula_4 بکار می‌رود. اگر تابع حدس کافی و دقیقی را برآورد سازد و همچنین حدس اولیه نزدیک به ریشه تابع مفروض باشد (که با همگرایی تقریب‌ها این موضوع روشن می‌شود) آنگاهformula_5 تقریب بهتری نسبت به formula_4 به حساب می‌آید. چرا که با احتساب همگرایی جواب‌ها، هر تقریب نسبت به تقریب قبل از خودش از دقت بالاتری برخوردار بوده و به ریشه تابع نزدیک تر است. به لحاظ هندسیformula_7نقطه ای است که محور formula_8 و خط مماس تابع formula_9 در نقطهٔ formula_10 یکدیگر را قطع می‌کنند. شکل عمومی الگوریتم نیوتن به شرح زیر می‌باشد:که در اصل از رابطه formula_12 بدست آمده است. می‌دانیم که در نقطهٔ برخورد تابع با محورformula_8 مقدار تابع صفر خواهد بود لذا formula_14 که در آخر با تقسیم برformula_15 می‌توان رابطه را به فرم رو به رو بازنویسی کرد:formula_11همان‌طور که مشهود است روش نیوتن-رافسون از سری تیلور ناقص تابع مفروض به عنوان یک تقریب خطی حول نقطهٔ حدس اولیهformula_4 بهره می‌برد و از این جهت تقریب را ناقص می‌گویند که نیازی به نوشتن سری تابع تا مراتب بالاتر نبوده و به همان دو جمله ابتدایی بسنده می‌کند که این موضوع نیز دلیلی بر تقریب خطی بودن روش نیوتن می‌باشد. همچنین چون این روش معادلهٔ یک تابع را تا معادلهٔ یک تابع درجه یک تقیل می‌دهد، لذا صرف نظر از اینکه تابع چند ریشه دارد، در نهایت الگوریتم تنها یک جواب بدست می‌آورد.این روش همچنین می‌تواند در توابع مختلط و دستگاه معادلات بکار رود.شرح.سازوکار روش نیوتن شروع مراحل تخمین ریشه با انتخاب یک حدس اولیه است که به اندازه لازم به مقدار واقعی ریشه نزدیک باشد، سپس می‌توان با استفاده از خط مماس تابع را تقریب زد و نهایتاً با توجه به خط مماس طول از مبدأ (ریشه تقریب خطی) را معین ساخت. ریشه تقریب معمولاً تقریب بهتری از ریشه واقعی تابع نسبت به حدس اولیه است و الگوریتم به همین منوال می‌تواند تکرار شود.چگونگی نامگذاری الگوریتم.اسم " Newton's method " از شرح آیزاک نیوتن در حالت خاصی از روش مذکور در "آنالیز بوسیله سری‌های بیکران" (نوشته شده در ۱۶۶۹،منتشر شده در سال ۱۷۱۱ توسط ویلیام جونز که در اصل کاری ریاضیاتی از نیوتن بود) و در De metodis fluxionum et serierum infinitarum (نوشته شده در ۱۶۷۱، که در سال ۱۷۳۶ توسط جان کولسون ترجمه و منتشر شد) مشتق شده است.عدم موفقیت الگوریتم.روش نیوتن تنها زمانی یافتن ریشه تقریبی را تضمین می‌کند که شرایطی برقرار باشد.در برخی مواقع شرایطی که برای همگرایی لازم است برقرار است، اما نقطهٔ که به عنوان حدس اولیه انتخاب شده دربازه ای که روش نیوتن همگرایی دارد قرار نمی‌گیرد. این شرایط زمانی می‌تواند اتفاق بیفتد که برای مثال همچنان که formula_2 به formula_19 یا formula_20 میل می‌کند ریشه تابع به‌طور متناوب و به اندازه کافی و مطلوبی به صفر نزدیک شود. در اینگونه موارد روش بهتری مانند روش دوبخشی (تنصیف) باید بکار گرفته شود تا تخمین بهتری بدست آورد.به تابع:formula_21 دقت کنید:این تابع در نقطهٔ formula_22 ماکسیمم دارد و ریشه‌های آن formula_23 و formula_24 می‌باشد. اگر تکرار را از formula_25 شروع کنیم (نقطه ای که مشتق آن صفر و شیب خط تابع افقی است)formula_26 تعریف نشده خواهد بود:حتی اگر مشتق تابع در آن نقطه نزدیک به صفر باشد آنگاه تکرار مرحله، تقریب به مراتب بدتری را به همراه خواهد داشت.در برخی توابع، بعضی از نقاطی که به عنوان حدس اولیه انتخاب می‌شوند ممکن است که به یک دایره ختم شوند که این می‌تواند مانع از همگرایی شود.برای مثال تابع formula_28 را در نظر بگیرید و formula_29 را به عنوان حدس اولیه اختیار کنید. نخستین مرحله جواب را formula_30 بدست می آوردو دومین مرحله دوباره به formula_31 می‌رسد، بنابراین جواب‌ها مدام بین دو مقدار مذکور تناوب می‌کند.در حقیقت این دو نقطه ثابت هستند. در حقیقت رفتار در این حالت می‌تواند بسیار پیچیده باشد. جواب واقعی معادله formula_32می‌باشد.مثالها.با توجه به یافتن جذر یک عدد، روش نیوتن یکی از چندین راهی است که می‌توان از آن بهره گرفت.برای مثال اگر هدف یافتن جذر ۶۱۲ باشد، این موضوع را می‌توان معادل جواب formula_33 دانست. سپس تابعی را که قصد داریم تا روش نیوتن را برای آن بکار ببندیم می‌توان به فرم formula_34 در نظر گرفت که مشتق آن نیز formula_35 خواهد بود. اگر حدس اولیه را formula_36 در نظر بگیریم آنگاه الگوریتم نیوتن به صورت زیر محاسبه را انجام خواهد داد:جاییکه که زیر رقم صحیح خط کشیده شده است، تنها با چند تکرار می‌توان به یک جواب دقیق با ارقام اعشاری دست یافت. در صورت هگرایی هرچه روش را تکرار کنیم جواب‌ها دقیق تر و ارقام بعد اعشار نیز به مراتب از دقت بیش تری برخوردار خواهند بود. همان‌طور که مشخص است برخی از ارقام بعد ممیز در هر مرحله تکرار می‌شوند که این نشان از دقت و قطعیت آنها دارد. اما به صورت کلی یافتن چنین جواب‌هایی با بهره‌گیری از روش‌های عددیابی چون روش نیوتن،روش تکرار ساده (Iteration method)، دو بخشی (Bisection method)، وتری (Secant method)، نابجایی (False position)، روش مولر (Muller's method) و … نمی‌توان به کامل‌ترین جواب دست یافت، چرا که ارقام بعد ممیز همواره ادامه دارند و خاتمه نمی‌یابند از این رو تنها دقیق‌ترین و کامل‌ترین جواب تنها در صورتی بدست می‌آید که تکرار را تا بینهایت ادامه دهیم، با فرض اینکه ریشهٔ تابع formula_38 باشد، به زبان ریاضیاتی این موضوع را می‌توان در قالب زیر بیان کرد:می‌توان معادله را به فرم formula_41 بازنویسی کرد و همچنین formula_42 بدین صورت می‌باشد. از آنجایی که که برای هر formula_43 همواره formula_44 می‌باشد لذا برای هر formula_45 نیز formula_46 خواهد بود. می‌دانیم که پاسخ معادله بین formula_31 و formula_48 قرار دارد لذا حدس اولیه را با formula_49 شروع می‌کنیم (توجه داشته باشید که اگر حدس اولیه را با formula_31 شروع می‌کردیم آنگاه به یک نتیجه تعریف نشده می‌رسیدیم، این موضوع اهمیت انتخاب حدس اولیه را به خوبی روشن می‌سازد که به اندازه کافی باید به جواب واقعی نزدیک باشد).زیر ارقام صحیح و قطعی در مثالهای بالا خط کشیده شده است. به خصوص formula_52 که تا ۱۲ رقم بعد ممیز صحیح می‌باشد. می‌بینیم که تعداد ارقام صحیح از ۲ رقم برای formula_53 تا ۱۰ رقم برای formula_54 در حال افزایش است که نشان دهنده همگرایی است.مقایسه سرعت همگرایی در روش‌های مختلف.در این قسمت اهمیت انتخاب روش مناسب به خوبی مشخص خواهد شد، چرا که سرعت همگرایی الگوریتم‌های مذکور با یکدیگر متفاوت است.برای مثال تابعformula_55 را در نظر بگیرید:نقش انتخاب بازه در تعیین ریشه.یکی از موارد کلیدی در اینکه روش مورد استفاده به کدام یک از ریشه‌های تابع (در صورت وجود بیش از یک ریشه) همگرا شود انتخاب بازه می‌باشد.برای مثال تابع formula_56 را در نظر بگیرید و نقطهٔ formula_57 را به عنوان حدس اولیه اختیار کنید: