روش نیوتن

اگر تابع حدس کافی و دقیقی را برآورد سازد و همچنین حدس اولیه نزدیک به ریشه تابع مفروض باشد (که با همگرایی تقریب ها این موضوع روشن می شود) آنگاه${\displaystyle x_{1}\ \,}$ تقریب بهتری نسبت به ${\displaystyle x_{0}\,}$ به حساب می آید.چرا که با احتساب همگرایی جواب ها، هر تقریب نسبت به تقریب قبل از خودش از دقت بالاتری برخوردار بوده و به ریشه تابع نزدیک تر است.به لحاظ هندسی${\displaystyle {(x_{1},0)}\,}$نقطه ای است که محور ${\displaystyle {x}\,}$ و خط مماس تابع ${\displaystyle {f}\,}$ در نقطهٔ ${\displaystyle {(x_{0},f(x_{0}))}\,}$ یکدیگر را قطع میکنند. شکل عمومی الگوریتم نیوتن به شرح زیر میباشد:

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,}$

که در اصل از رابطه ${\displaystyle f(x)=f(x_{0})+{\frac {f'(x_{0})(x-x_{0})}{1!}}}$ بدست امده است. میدانیم که در نقطهٔ برخورد تابع با محور${\displaystyle {x}\,}$ مقدار تابع صفر خواهد بود لذا ${\displaystyle 0=f(x_{0})+{\frac {f'(x_{0})(x-x_{0})}{1!}}}$ که در آخر با تقسیم بر${\displaystyle {f'(x_{0})}}$ میتوان رابطه را به فرم رو به رو بازنویسی کرد:

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,}$

همانطور که مشهود است روش نیوتن-رافسون از سری تیلور ناقص تابع مفروض به عنوان یک تقریب خطی حول نقطهٔ حدس اولیه${\displaystyle x_{0}\,}$ بهره میبرد و از این جهت تقریب را ناقص میگویند که نیازی به نوشتن سری تابع تا مراتب بالاتر نبوده و به همان دو جمله ابتدایی بسنده میکند که این موضوع نیز دلیلی بر تقریب خطی بودن روش نیوتن میباشد. همچنین چون این روش معادلهٔ یک تابع را تا معادلهٔ یک تابع درجه یک تقیل میدهد، لذا صرف نظر از اینکه تابع چند ریشه دارد، در نهایت الگوریتم تنها یک جواب بدست می آورد.

این روش همچنین میتواند در توابع مختلط و دستگاه معادلات بکار رود.

ساز و کار روش نیوتن شروع مراحل تخمین ریشه با انتخاب یک حدس اولیه است که به اندازه لازم به مقدار واقعی ریشه نزدیک باشد ، سپس میتوان با استفاده از خط مماس تابع را تقریب زد و نهایتاً با توجه به خط مماس طول از مبدا (ریشه تقریب خطی) را معین ساخت. ریشه تقریب معمولاً تقریب بهتری از ریشه واقعی تابع نسبت به حدس اولیه است و الگوریتم به همین منوال میتواند تکرار شود.

اسم " Newton's method " از شرح آیزاک نیوتن در حالت خاصی از روش مذکور در "آنالیز بوسیله سری های بیکران" (نوشته شده در 1669،منتشر شده در سال 1711 توسط ویلیام جونز که در اصل کاری ریاضیاتی از نیوتن بود) و در De metodis fluxionum et serierum infinitarum (نوشته شده در 1671،که در سال 1736 توسط جان کولسون ترجمه و منتشر شد)مشتق شده است.

روش نیوتن تنها زمانی یافتن ریشه تقریبی را تضمین میکند که شرایطی برقرار باشد.

• نقاطی با شروع بد

در برخی مواقع شرایطی که برای همگرایی لازم است برقرار است،اما نقطهٔ که به عنوان حدس اولیه انتخاب شده دربازه ای که روش نیوتن همگرایی دارد قرار نمی‌گیرد.این شرایط زمانی میتواند اتفاق بیفتد که برای مثال همچنان که ${\displaystyle x\,}$  به ${\displaystyle +\infty }$  یا ${\displaystyle -\infty }$  میل میکند ریشه تابع به طور متناوب و به اندازه کافی و مطلوبی به صفر نزدیک شود. در اینگونه موارد روش بهتری مانند روش دوبخشی (تنصیف) باید بکار گرفته شود تا تخمین بهتری بدست آورد.

• زمانی که نقطهٔ تکرار ثابت است

به تابع :${\displaystyle f(x)=1-x^{2}.}$  دقت کنید:

این تابع در نقطهٔ ${\displaystyle x=0\,}$  ماکسیمم دارد و ریشه های آن ${\displaystyle x=+1\,}$  و ${\displaystyle x=-1\,}$  میباشد. اگر تکرار را از ${\displaystyle x_{0}=0\,}$  شروع کنیم (نقطه ای که مشتق آن صفر و شیب خط تابع افقی است)${\displaystyle x_{1}\,}$  تعریف نشده خواهد بود:

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=0-{\frac {1}{0}}.}$ 

حتی اگر مشتق تابع در آن نقطه نزدیک به صفر باشد آنگاه تکرار مرحله، تقریب به مراتب بدتری را به همراه خواهد داشت.

• حدس اولیه به یک دایره منتهی میشود

در برخی توابع، بعضی از نقاطی که به عنوان حدس اولیه انتخاب میشوند ممکن است که به یک دایره ختم شوند که این میتواند مانع از همگرایی شود. برای مثال تابع ${\displaystyle f(x)=x^{3}-2x+2\!}$  را در نظر بگیرید و ${\displaystyle x=0\,}$  را به عنوان حدس اولیه اختیار کنید. نخستین مرحله جواب را ${\displaystyle 1\,}$  بدست می آوردو دومین مرحله دوباره به ${\displaystyle 0\,}$  میرسد،بنابراین جواب ها مدام بین دو مقدار مذکور تناوب میکند. در حقیقت این دو نقطه ثابت هستند.در حقیقت رفتار در این حالت میتواند بسیار پیچیده باشد. جواب واقعی معادله ${\displaystyle -1.76929235\,}$ می باشد.

• جذر یک عدد

با توجه به یافتن جذر یک عدد، روش نیوتن یکی از چندین راهی است که میتوان از آن بهره گرفت. برای مثال اگر هدف یافتن جذر 612 باشد ، این موضوع را میتوان معادل جواب ${\displaystyle x^{2}=612\,}$  دانست. سپس تابعی را که قصد داریم تا روش نیوتن را برای آن بکار ببندیم میتوان به فرم ${\displaystyle {f(x)=x^{2}-612},}$  در نظر گرفت که مشتق آن نیز ${\displaystyle {f'=2x}\,}$  خواهد بود.اگر حدس اولیه را ${\displaystyle {10}\,}$  در نظر بگیریم آنگاه الگوریتم نیوتن به صورت زیر محاسبه را انجام خواهد داد:

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}}$ 

جاییکه که زیر رقم صحیح خط کشیده شده است ،تنها با چند تکرار میتوان به یک جواب دقیق با ارقام اعشاری دست یافت. در صورت هگرایی هرچه روش را تکرار کنیم جواب ها دقیق تر و ارقام بعد اعشار نیز به مراتب از دقت بیش تری برخوردار خواهند بود. همانطور که مشخص است برخی از ارقام بعد ممیز در هر مرحله تکرار میشوند که این نشان از دقت و قطعیت آنها دارد. اما به صورت کلی یافتن چنین جواب هایی با بهره گیری از روش های عددیابی چون روش نیوتن، روش تکرار ساده ( Iteration method)، دو بخشی (Bisection method)، وتری (Secant method)، نابجایی (False position)، روش مولر (Muller's method) و ... نمیتوان به کامل ترین جواب دست یافت، چرا که ارقام بعد ممیز همواره ادامه دارند و خاتمه نمی‌یابند از این رو تنها دقیق ترین و کامل ترین جواب تنها در صورتی بدست می آید که تکرار را تا بینهایت ادامه دهیم،با فرض اینکه ریشهٔ تابع ${\displaystyle \alpha \,}$  باشد، به زبان ریاضیاتی این موضوع را میتوان در قالب زیر بیان کرد:

${\displaystyle \lim _{n\to \infty }x_{n}=\alpha \ }$ 

• یافتن جواب ${\displaystyle cos(x)=x^{3}\,}$ 

میتوان معادله را به فرم ${\displaystyle f(x)=cos(x)-x^{3}\,}$  بازنویسی کرد و همچنین ${\displaystyle f'(x)=-sin(x)-3x^{2}\,}$  بدین صورت میباشد. از آنجایی که که برای هر ${\displaystyle x\,}$  همواره ${\displaystyle cos(x)\leq 1\,}$  میباشد لذا برای هر ${\displaystyle x>1\,}$  نیز ${\displaystyle x^{3}>1\,}$  خواهد بود. میدانیم که پاسخ معادله بین ${\displaystyle 0\,}$  و ${\displaystyle 1\,}$  قرار دارد لذا حدس اولیه را با ${\displaystyle x_{0}=0.5\,}$  شروع میکنیم ( توجه داشته باشید که اگر حدس اولیه را با ${\displaystyle 0\,}$  شروع میکردیم آنگاه به یک نتیجه تعریف نشده می‌رسیدیم،این موضوع اهمیت انتخاب حدس اولیه را به خوبی روشن می‌سازد که به اندازه کافی باید به جواب واقعی نزدیک باشد).

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}}$ 

زیر ارقام صحیح و قطعی در مثالهای بالا خط کشیده شده است. به خصوص ${\displaystyle x_{6}\,}$  که تا 12 رقم بعد ممیز صحیح میباشد. میبینیم که تعداد ارقام صحیح از 2 رقم برای ${\displaystyle x_{3}\,}$  تا 10 رقم برای ${\displaystyle x_{5}\,}$  در حال افزایش است که نشان دهنده همگرایی است.

مقایسه سرعت همگرایی در روش های مختلف

در این قسمت اهمیت انتخاب روش مناسب به خوبی مشخص خواهد شد، چرا که سرعت همگرایی الگوریتم های مذکور با یکدیگر متفاوت است.

برای مثال تابع${\displaystyle cos(x)++3^{x}+2x^{3}-5x-1=0\,}$  را در نظر بگیرید:

 

${\displaystyle n\,}$	نیوتن-رافسون	دوبخشی (تنصیف)	وتری (خط قاطع)	نابجایی
${\displaystyle 1\,}$	1.5144846069926343	2	1.0142608902188517	1.0142608902188517
${\displaystyle 2\,}$	1.2409015822217806	1.5	1.0268652076794869	1.0268652076794869
${\displaystyle 3\,}$	1.1288784389132172	1.25	1.1227742188629786	1.0379429317009117
${\displaystyle 4\,}$	1.1077940032164637	1.125	1.1048082422680339	1.047630656720699
${\displaystyle 5\,}$	1.1070571436969323	1.0625	1.1069994195564619	1.056065815978876
${\displaystyle 6\,}$	1.1070562546390645	1.09375	1.1070564643650112	1.0633822991162016
${\displaystyle 7\,}$	—	1.109375	—	1.0697073398074517
${\displaystyle ...\,}$
${\displaystyle 16\,}$	—	1.10711669921875	—	1.096746829671288
${\displaystyle ...\,}$
${\displaystyle 34\,}$	—	—	—	1.106527597620123

• در این مثال سرعت همگرایی دو روش وتری (خط قاطع) و روش نیوتن با یکدیگر تقریباً برابر است، همچنین مشاهده میشود که کند ترین روش در این مثال الگوریتم نابجایی میباشد، اما به‌طور کل نمیتوان این مثال خاص را به تمامی مثال ها تعمیم داد چرا که همواره سرعت همگرایی متغیر بوده و به شرایط مختلفی بستگی دارد، لذا انتخاب بهترین روش میتواند سهم به سزایی در سرعت عملیات تقریب زنی داشته باشد.همچنین مسئله ی دیگر که مطرح است این موضوع میباشد که هر کدام از روش ها مزایا و معایب خود را دارا هستند، برای مثال از معایب روش نیوتن عدم جواب در صورتی ست که مشتق تابع در نقطه ی مورد نظر صفر و یا نزدیک به صفر باشد و یا ایجاد سختی در هنگامی ست که مشتق گیری تابع عملیاتی دشوار باشد و از مزایای آن همگرایی سریع در صورت انتخاب حدس اولیه مناسب است ،اما باید توجه داشت همگرایی روش نیوتن-رافسون برخلاف برخی روش ها مانند روش دوبخشی تضمینی نیست.

نقش انتخاب بازه در تعیین ریشه

یکی از موارد کلیدی در اینکه روش مورد استفاده به کدام یک از ریشه های تابع (در صورت وجود بیش از یک ریشه) همگرا شود انتخاب بازه میباشد. برای مثال تابع ${\displaystyle 3cos(x)-x\,}$  را در نظر بگیرید و نقطه ی ${\displaystyle x=5\,}$  را به عنوان حدس اولیه اختیار کنید:

${\displaystyle \,}$	نیوتن-رافسون	دوبخشی (تنصیف)	وتری (خط قاطع)	نابجایی
${\displaystyle x_{approx}\,}$	2.938100393973599	1.1701202392578125	1.1701209480974004	1.1701199957162514

• در معادله ی فوق بازه ی انتخاب شده برای هر چهار روش یکسان بوده اما ریشه ی تقریبی حاصل از روش نیوتن متفاوت از سایرین است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Newton's method». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۵ نوامبر ۲۰۱۲.