روش نیوتن
در آنالیز عددی روش نیوتن ، که همچنین به عنوان روش نیوتن-رافسون نیز شناخته میشود الگوریتم ریشه یابی است که تقریب های خوبی در نزدیکی ریشه یک تابع (صفرهای یک تابع) میزند.در پایه ای ترین حالت، الگوریتم نیوتن برای یک تابعی چون 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 " از شرح آیزاک نیوتن در حالت خاصی از روش مذکور در "آنالیز بوسیله سری های بیکران" (نوشته شده در 1669،منتشر شده در سال 1711 توسط ویلیام جونز که در اصل کاری ریاضیاتی از نیوتن بود) و در De metodis fluxionum et serierum infinitarum (نوشته شده در 1671،که در سال 1736 توسط جان کولسون ترجمه و منتشر شد)مشتق شده است. روش نیوتن تنها زمانی یافتن ریشه تقریبی را تضمین میکند که شرایطی برقرار باشد. در برخی مواقع شرایطی که برای همگرایی لازم است برقرار است،اما نقطهٔ که به عنوان حدس اولیه انتخاب شده دربازه ای که روش نیوتن همگرایی دارد قرار نمی‌گیرد.این شرایط زمانی میتواند اتفاق بیفتد که برای مثال همچنان که 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می باشد. با توجه به یافتن جذر یک عدد، روش نیوتن یکی از چندین راهی است که میتوان از آن بهره گرفت. برای مثال اگر هدف یافتن جذر 612 باشد ، این موضوع را میتوان معادل جواب 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 که تا 12 رقم بعد ممیز صحیح میباشد. میبینیم که تعداد ارقام صحیح از 2 رقم برای formula_53 تا 10 رقم برای formula_54 در حال افزایش است که نشان دهنده همگرایی است.
در این قسمت اهمیت انتخاب روش مناسب به خوبی مشخص خواهد شد، چرا که سرعت همگرایی الگوریتم های مذکور با یکدیگر متفاوت است.
برای مثال تابعformula_55 را در نظر بگیرید:
یکی از موارد کلیدی در اینکه روش مورد استفاده به کدام یک از ریشه های تابع (در صورت وجود بیش از یک ریشه) همگرا شود انتخاب بازه میباشد. برای مثال تابع formula_56 را در نظر بگیرید و نقطه ی formula_57 را به عنوان حدس اولیه اختیار کنید: