الگوریتم‌های پیداکردن ریشه

## مقدمه
اساساً الگوریتم پیدا کردن ریشه یا ریشه‌یابی، یک الگوریتم برای پیدا کردن ریشه‌های توابع پیوسته‌است.

یک ریشه از تابع \begin{alignat}{2} f \end{alignat} هنگامی پیدا می‌شود که {\displaystyle {\begin{alignedat}{2}x\end{alignedat}}} در معادلهٔ {\displaystyle {\begin{alignedat}{2}f(x) = 0\end{alignedat}}} صدق کند و به آن x ریشهٔ تابع \begin{alignat}{2} f \end{alignat}می‌گوییم یا در معادلهٔ زیر هنگامی ریشهٔ \begin{alignat}{2} f \end{alignat}را پیدا می‌کنیم که حاصل تفریق دو تابع دیگر برابر ۰ شود.

\begin{alignat}{2} f(x) & = g(x) - h(x) \\
& => g(x) - f(x) = 0 \\
& => g(x) = f(x)
\end{alignat}

به‌طور کلی ریشه‌های بسیاری از توابع را نمی‌توان به صورت دقیق محاسبه کرد و الگوریتم پیدا کردن ریشه (**Root-finding algorithm**)به ما کمک می‌کند که به صورت تقریبی آنها را محاسبه کنیم.

اکثر الگوریتم‌های ریشه‌یابی با استفاده از انتخاب دنباله‌ای از اعداد امیدوارند که این دنباله به عنوان یک حد به سمت ریشه همگرایی داشته باشد. آنها با استفاده از یک یا چند حدس اولیه از ریشه، به عنوان مقادیر شروع می‌کنند سپس هر تکرار الگوریتم تقریب بهتری از ریشه را برای ما به ارمغان می‌آورد.

## روش‌های براکتی (Bracketing methods)
در این گونه روش‌ها با تعیین بازه‌های کوچک و استفاده از آنها در برخی فرمول‌ها سعی می‌کنیم که به ریشه دست پیدا کنیم.

### روش تنصیف یا دو بخشی
این روش از ساده‌ترین و قابل اعتمادترین روش‌های تکراری برای حل معادلهٔ غیر خطی است. این روش همچنین به عنوان روش تقسیم باینری(binary chopping) یا نیمه بازه(half-interval method)نیز شناخته می‌شود.

در این روش تابع \begin{alignat}{2} f \end{alignat}را به nبازهٔ مختلف [a,b]تقسیم می‌کنیم تا ریشه‌ای مانند \epsilonرا پیدا کنیم بدین صورت که:if \quad (f({(a_n + b_n)\over 2} )= 0) \quad  then  \quad \epsilon = {(a_n + b_n)\over 2}

if \quad (f(a_n)f({(a_n + b_n)\over 2} ) در غیر این صورت: set  a_{n+1}=\frac{a_{n}+b_{n}}{2}\quad ; \quad b_{n+1}=b_nبرای فهم بهتر به تصویر زیر توجه کنید:بندانگشتی

### [[روش نابجایی]]

در این روش مانند روش قبل تابع مورد نظر را بازه بازه می‌کنیم ولی در این روش سریع تر به این مسئله و رسیدن به ریشه اهمیت می‌دهیم. بدین صورت که: w = }می‌گیریم. سپس برای تابع f'ریشه را به دست می‌آوریم. ریشه نقطه‌ای مانند x_1می‌شود سپس برای نقطهٔ x_1از تابع fمشتق می‌گیریم و ریشهٔ این معادلهٔ به دست آمده به عنوان x_2ما انتخاب می‌شود و همین روال به صورت تکراری ادامه خواهد داشت.
بندانگشتی
برای درک بهتر به تصویر زیر توجه کنید:

### [[روش وتری]]
از آنجائیکه روش‌های دو بخشی و نابجایی با سرعت کمی به سمت ریشه میل می‌کنند، لذا شیوه ای سریعتر برای یافتن ریشه نیاز است. یک چنین شیوه ای، روش وتری نام دارد. مشابه شیوهٔ نابجایی ، اساس این روش نیز بر تقریب زدن ریشه تابع از طریق یک خط مستقیم قرار دارد که دو نقطه از نمودار تابع را به یکدیگر وصل می‌کند، اما نیازی نیست که نقاط حدس اولیه حتماً دارای عالمت مخالف باشند.
* گام اول:x_{i+1} = x_i - {{{f(x_i)}(x_{i-1}-x_i)}\over f(x_{i-1})-f(x_i)}
* گام دوم:e_n = |x_{i+1} - x_i| \leqslant \epsilon_i \quad and/or \quad e_n = |f(x_{i+1})| \leqslant \epsilon_2
* گام سوم: اگر شرط فوق برقرار باشد، به مرحله چهار برو، در غیراینصورت داریم:set \quad x_i = x_{i+1} , x_{i-1} = x_i
* گام چهارم :نمایش  x_{i+1}به عنوان ریشه و پایان الگوریتم.

بندانگشتی
یک شبه کد برای این الگوریتم:The\ Secant\ MethodGiven\ f(x)\ = 0 \, \epsilon \ and\ two\ initial\ points \ x_0 , x_1 ;Given\ max\ = maximum\ number\ of \ iterations;For \ i = 1 \ to\ max :compute\ \ g'(x_i) =  ; compute\ \ x_{i+1} = x_i - {f(x_i) \over g'(x_i)}; If\ | x_{i+1} - x_i| Solution = x_{i+1} ; stop\ the \ iterations; endif endfor 

## منابع


رده:الگوریتم‌های پیدا کردن ریشه
رده:ویکی‌سازی رباتیک