روش نیوتن

جاییکه که زیر رقم صحیح خط کشیده شده است ،تنها با چند تکرار میتوان به یک جواب دقیق با ارقام اعشاری دست یافت. در صورت هگرایی هرچه روش را تکرار کنیم جواب ها دقیق تر و ارقام بعد اعشار نیز به مراتب از دقت بیش تری برخوردار خواهند بود. همانطور که مشخص است برخی از ارقام بعد ممیز در هر مرحله تکرار میشوند که این نشان از دقت و قطعیت آنها دارد. اما به صورت کلی یافتن چنین جواب هایی با بهره گیری از روش های عددیابی چون روش نیوتن، روش تکرار ساده ( 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

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