KonkurStudy
همه کارت‌ها
الگوریتممبانی آنالیز عددیریشه‌یابی معادلات غیرخطی

روش‌های ریشه‌یابی: تنصیف، نیوتن و روش وتری

مسیر کامل حل عددی f(x)=0f(x)=0: مکان‌یابی ریشه‌ها با یکنوایی و قضیهٔ مقدار میانی، محصورسازی آن‌ها، و سپس تکرار با روش تنصیف (p=1p=1)، نقطهٔ ثابت، نیوتن (p=2p=2، اما p=1p=1 در ریشهٔ مکرر) یا روش وتری (p=(1+5)/2p=(1+\sqrt5)/2) — همراه با فرض‌های دقیق، کران‌های خطا و تعداد گام‌هایی که هر یک به همراه دارد.

کارت الگوریتم کنکور ارشد ریاضی

اهمیت
۰/۵

ریشه (صفر) یک تابع ff نقطه‌ای مانند rr است که f(r)=0f(r)=0. چون معادلهٔ f(x)=0f(x)=0 تقریباً هیچ‌گاه جواب بسته ندارد، آنالیز عددی به‌جای حل کردن، تولید یک دنباله x0,x1,x2,⋯→rx_0,x_1,x_2,\dots\to r را می‌نشاند. هر پرسش کنکوری در این مبحث در یکی از سه مرحله جای می‌گیرد: (۰) مکان‌یابی — چند ریشهٔ حقیقی، و در کدام بازه؛ (۱) تکرار — تنصیف، نقطهٔ ثابت، نیوتن، وتری؛ (۲) نرخ — با چه سرعتی، در چند گام، با چه مرتبه‌ای.

۰. مرحلهٔ صفر — شمارش و محصورسازی ریشه‌ها

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

قضیهٔ بولتزانو / مقدار میانی. اگر ff روی [a,b][a,b] پیوسته باشد و f(a) f(b)<0f(a)\,f(b)<0، آنگاه f(r)=0f(r)=0 برای برخی r∈(a,b)r\in(a,b). اگر افزون بر آن ff روی [a,b][a,b] اکیداً یکنوا باشد (مثلاً f′f' در آنجا علامت ثابت داشته باشد)، آن ریشه یکتا است.

دو نکتهٔ یک‌طرفه: آزمون علامت فقط وجود را می‌دهد، هرگز یکتایی را؛ و f(a)f(b)>0f(a)f(b)>0 به معنای «ریشه‌ای در [a,b][a,b] نیست» نیست — یعنی «تعداد زوجی ریشه، با احتساب مرتبهٔ تکرار».

دستور کار — معادلهٔ g(x)=cg(x)=c چند جواب حقیقی دارد و کجا؟

۱. معادلهٔ g′(x)=0g'(x)=0 را حل کنید و R\mathbb{R} را به شاخه‌های یکنوای ماکسیمال افراز کنید. ۲. مقادیر اکسترمم موضعی g(critical points)g(\text{critical points}) را همراه با lim⁡x→±∞g(x)\lim_{x\to\pm\infty}g(x) حساب کنید: این‌ها مقادیر انتهایی‌اند که هر شاخه می‌پیماید. ۳. خط افقی y=cy=c هر شاخهٔ یکنوا را حداکثر یک بار قطع می‌کند، و دقیقاً یک بار اگر و تنها اگر cc اکیداً بین دو مقدار انتهایی آن شاخه باشد. شمردن شاخه‌های واجد شرط، تعداد ریشه‌های حقیقی را می‌دهد. ۴. روی هر شاخهٔ واجد شرط، f=g−cf=g-c را در اعداد صحیح مناسب ارزیابی کنید تا علامت عوض شود؛ همان زوج، بازهٔ محصورکنندهٔ شماست.

واقعیت‌های کمکی که ارزش حفظ‌کردن دارند:

  • یک چندجمله‌ای حقیقی با درجهٔ فرد دست‌کم یک ریشهٔ حقیقی دارد، و ریشه‌های ناحقیقی یک چندجمله‌ای حقیقی به‌صورت زوج‌های مزدوج ظاهر می‌شوند؛
  • چندجمله‌ای درجه‌سومِ تقلیل‌یافتهٔ t3+pt+qt^{3}+pt+q مبیّن Δ=−4p3−27q2\Delta=-4p^{3}-27q^{2} دارد؛ با Δ>0\Delta>0 سه ریشهٔ حقیقی متمایز، با Δ=0\Delta=0 یک ریشهٔ حقیقی مکرر، و با Δ<0\Delta<0 دقیقاً یک ریشهٔ حقیقی (هر معادلهٔ درجه‌سوم با تغییر متغیر x↦x−b3ax\mapsto x-\tfrac{b}{3a} به این شکل درمی‌آید)؛
  • کران کوشی: هر ریشهٔ xn+an−1xn−1+⋯+a0x^{n}+a_{n-1}x^{n-1}+\cdots+a_0 در ∣x∣≤1+max⁡i∣ai∣\lvert x\rvert\le 1+\max_i\lvert a_i\rvert صدق می‌کند؛ قاعدهٔ علامت‌های دکارت نیز تعداد ریشه‌های مثبت را کران‌دار می‌کند.

یک مکان‌یابی حل‌شده. معادلهٔ x(x−1)(x−2)=1x(x-1)(x-2)=1، یعنی f(x)=x3−3x2+2x−1=0f(x)=x^{3}-3x^{2}+2x-1=0 را در نظر بگیرید. قرار دهید g(x)=x(x−1)(x−2)g(x)=x(x-1)(x-2)؛ انتقال t=x−1t=x-1 آن را به معادلهٔ درجه‌سوم فردِ g=t3−tg=t^{3}-t تبدیل می‌کند، پس g′=3t2−1=0g'=3t^{2}-1=0 در t=±13t=\pm\tfrac{1}{\sqrt3} و مقادیر اکسترمم موضعی برابرند با gmax⁡=−gmin⁡=233=239≈0.385.g_{\max}=-g_{\min}=\frac{2}{3\sqrt3}=\frac{2\sqrt3}{9}\approx0.385 . تراز c=1c=1 بالای ماکسیمم موضعی قرار دارد، پس y=1y=1 نخستین شاخهٔ صعودی و کل شاخهٔ نزولی را از دست می‌دهد و تنها شاخهٔ صعودی پایانی را قطع می‌کند: دقیقاً یک ریشهٔ حقیقی، که آن‌سوی بزرگ‌ترین صفر یعنی x=2x=2 قرار دارد (چون g≤0.385<1g\le0.385<1 روی تمام [0,2][0,2]). با مبیّنِ t3−t−1t^{3}-t-1 راستی‌آزمایی کنید: Δ=4−27=−23<0\Delta=4-27=-23<0، یک ریشهٔ حقیقی. حالا آن را محصور کنید: f(2)=−1<0f(2)=-1<0 و f(3)=5>0f(3)=5>0، پس r∈(2,3)r\in(2,3) — ورودی همهٔ روش‌های زیر. (به‌طور دقیق: r=1+ρ≈2.324718r=1+\rho\approx2.324718 که ρ\rho عدد پلاستیکی است.)

۱. تنصیف — جست‌وجوی دودویی روی تغییر علامت

فرض‌ها: f∈C[a0,b0]f\in C[a_0,b_0] و f(a0)f(b0)<0f(a_0)f(b_0)<0. هیچ چیز دیگر — نه مشتق، نه هموارساری.

while (b - a) > tol:
    m = (a + b) / 2
    if f(m) == 0: return m
    if f(a) * f(m) < 0: b = m      # root is in the left half
    else:               a = m      # root is in the right half
return (a + b) / 2

کران خطا. اگر xnx_n نقطهٔ میانی nn-ام باشد، بازهٔ باقی‌مانده طول (b0−a0)/2 n−1(b_0-a_0)/2^{\,n-1} دارد و xnx_n مرکز آن است، پس ∣xn−r∣ ≤ b0−a02 n →n→∞ 0.\lvert x_n-r\rvert\ \le\ \frac{b_0-a_0}{2^{\,n}}\ \xrightarrow[n\to\infty]{}\ 0 . بنابراین هزینهٔ رسیدن به دقت ε\varepsilon چنین است: n ≥ log⁡2b0−a0ε⟹n=⌈log⁡2b0−a0ε⌉.n\ \ge\ \log_2\frac{b_0-a_0}{\varepsilon}\qquad\Longrightarrow\qquad n=\left\lceil\log_2\frac{b_0-a_0}{\varepsilon}\right\rceil . یک بیت در هر گام، یعنی log⁡210≈3.32\log_2 10\approx3.32 گام برای هر رقم اعشاری — تعدادِ گام‌ها از پیش معلوم است، چیزی که هیچ روش دیگری عرضه نمی‌کند.

روش تنصیف سراسری و بی‌قیدوشرط همگرا می‌شود (مرتبهٔ p=1p=1، عامل مجانبی 12\tfrac12)، اما کُند است، بزرگی ff را نادیده می‌گیرد، ریشهٔ با مرتبهٔ تکرار زوج را نمی‌بیند (تغییر علامتی رخ نمی‌دهد) و برای دستگاه‌ها هیچ معادلی ندارد.

۲. تکرار نقطهٔ ثابت — چارچوبی که بقیه را توضیح می‌دهد

معادلهٔ f(x)=0f(x)=0 را به شکل x=g(x)x=g(x) بازنویسی کنید و xn+1=g(xn)x_{n+1}=g(x_n) را تکرار کنید؛ ریشه‌های ff همان نقاط ثابت gg هستند.

قضیهٔ انقباض (باناخ). اگر g∈C[a,b]g\in C[a,b] با g([a,b])⊆[a,b]g([a,b])\subseteq[a,b] و ∣g(x)−g(y)∣≤L∣x−y∣\lvert g(x)-g(y)\rvert\le L\lvert x-y\rvert برای همهٔ x,y∈[a,b]x,y\in[a,b] با ثابتی 0≤L<10\le L<1 (که وقتی ∣g′∣≤L<1\lvert g'\rvert\le L<1 روی [a,b][a,b] باشد تضمین می‌شود)، آنگاه gg یک نقطهٔ ثابت یکتا r∈[a,b]r\in[a,b] دارد، تکرار برای هر x0∈[a,b]x_0\in[a,b] همگرا می‌شود، و ∣xn−r∣ ≤ Ln1−L ∣x1−x0∣.\lvert x_n-r\rvert\ \le\ \frac{L^{n}}{1-L}\,\lvert x_1-x_0\rvert . هر دو فرض مهم‌اند: خودنگاشتی تکرارها را درون بازه نگه می‌دارد و انقباض آن‌ها را همگرا می‌کند.

آزمون موضعی. ∣g′(r)∣<1\lvert g'(r)\rvert<1 نقطهٔ rr را جاذب می‌کند (همگرایی خطی با نرخ ∣g′(r)∣\lvert g'(r)\rvert)؛ ∣g′(r)∣>1\lvert g'(r)\rvert>1 آن را دافع می‌کند — هیچ شروع غیر دقیقی نمی‌تواند به آن همگرا شود. حالت مرزی ∣g′(r)∣=1\lvert g'(r)\rvert=1 چیزی تعیین نمی‌کند: تکرار xn+1=sin⁡xnx_{n+1}=\sin x_n دارای g′(0)=1g'(0)=1 است ولی باز هم به 00 همگرا می‌شود، منتها زیرخطی (xn∼3/nx_n\sim\sqrt{3/n}).

قضیهٔ مرتبه. اگر gg در نزدیکی rr از رستهٔ CpC^{p} باشد و g′(r)=g′′(r)=⋯=g(p−1)(r)=0g'(r)=g''(r)=\cdots=g^{(p-1)}(r)=0 و g(p)(r)≠0g^{(p)}(r)\ne0، آنگاه تکرار دقیقاً مرتبهٔ pp دارد: lim⁡n→∞en+1en p=g(p)(r)p!,en=xn−r.\lim_{n\to\infty}\frac{e_{n+1}}{e_n^{\,p}}=\frac{g^{(p)}(r)}{p!},\qquad e_n=x_n-r . صفر کردن مشتق‌های gg در ریشه، دقیقاً همان چیزی است که سرعت می‌خرد — و به همین دلیل است که نیوتن درجه‌دو است.

۳. نیوتن–رافسون

خطی‌سازی کنید: از 0=f(xn+h)≈f(xn)+h f′(xn)0=f(x_n+h)\approx f(x_n)+h\,f'(x_n) نتیجه می‌شود h=−f(xn)/f′(xn)h=-f(x_n)/f'(x_n)، یعنی گام برداشتن به نقطه‌ای که مماس در xnx_n محور را قطع می‌کند: xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} . به‌عنوان نگاشت نقطهٔ ثابتِ g=x−ff′g=x-\dfrac{f}{f'} داریم g′=ff′′(f′)2g'=\dfrac{f f''}{(f')^{2}}، پس در یک ریشهٔ ساده g′(r)=0g'(r)=0 — و آنگاه قضیهٔ مرتبه p=2p=2 را پیش‌بینی می‌کند.

قضیهٔ همگرایی (ریشهٔ ساده). فرض کنید f∈C2f\in C^{2} در نزدیکی rr، f(r)=0f(r)=0، f′(r)≠0f'(r)\ne0. آنگاه δ>0\delta>0ای وجود دارد که برای هر x0∈[r−δ,r+δ]x_0\in[r-\delta,r+\delta] تکرارها در بازه می‌مانند، به rr همگرا می‌شوند، و lim⁡n→∞∣en+1∣en 2=∣f′′(r)2f′(r)∣.\lim_{n\to\infty}\frac{\lvert e_{n+1}\rvert}{e_n^{\,2}}=\left\lvert\frac{f''(r)}{2f'(r)}\right\rvert . همگرایی درجه‌دو: تعداد ارقام درست در هر گام تقریباً دو برابر می‌شود. توجه کنید که قضیه موضعی است — برای یک x0x_0 دوردست هیچ تضمینی نمی‌دهد.

معیار سراسری (یکنوا) — شرط کافی محبوب کنکور. اگر روی [a,b][a,b] داشته باشیم f(a)f(b)<0f(a)f(b)<0 و هر دوی f′f' و f′′f'' ناصفر و با علامت ثابت باشند، آنگاه ریشه یکتاست و روش نیوتن با شروع از سرِ بازه‌ای که در f(x0) f′′(x0)>0f(x_0)\,f''(x_0)>0 صدق می‌کند، به‌طور یکنوا به آن همگرا می‌شود (مماس همواره در یک سمت ریشه فرود می‌آید).

ریشه‌های مکرر. اگر rr مرتبهٔ تکرار m≥2m\ge2 داشته باشد، یعنی f(x)=(x−r)mq(x)f(x)=(x-r)^{m}q(x) با q(r)≠0q(r)\ne0، آنگاه g′(r)=1−1m≠0g'(r)=1-\tfrac1m\ne0 و نیوتن به همگرایی خطی با نرخ 1−1m1-\tfrac1m تنزل می‌کند (12\tfrac12 برای ریشهٔ مضاعف). دو راه ترمیم:

  • نیوتن اصلاح‌شده xn+1=xn−mf(xn)f′(xn)x_{n+1}=x_n-m\dfrac{f(x_n)}{f'(x_n)} — دوباره درجه‌دو، اما باید mm را بدانید؛
  • نیوتن معمولی را روی u=f/f′u=f/f' به کار ببرید، که ریشه‌اش در rr هرچه mm باشد ساده است.

حالت‌های شکست. f′(xn)=0f'(x_n)=0 (مماس افقی: گام منفجر می‌شود)؛ دور افتادن — برای f(x)=x3−2x+2f(x)=x^{3}-2x+2 با x0=0x_0=0 داریم x1=1x_1=1، x2=0x_2=0، و همین‌طور تا ابد؛ پرش به ریشه‌ای دیگر؛ و واگرایی وقتی منحنی در دوردست تخت می‌شود (f=arctan⁡xf=\arctan x برای ∣x0∣>1.3917…\lvert x_0\rvert>1.3917\ldots واگرا می‌شود). هزینه: دو ارزیابی (ff و f′f') در هر گام.

۴. روش وتری

f′(xn)f'(x_n) را با شیب گذرنده از دو تکرار آخر جایگزین کنید: xn+1=xn−f(xn) xn−xn−1f(xn)−f(xn−1)=xn−1f(xn)−xnf(xn−1)f(xn)−f(xn−1).x_{n+1}=x_n-f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}=\frac{x_{n-1}f(x_n)-x_nf(x_{n-1})}{f(x_n)-f(x_{n-1})} . این روش به دو مقدار آغازین x0,x1x_0,x_1 نیاز دارد، به مشتق نیازی ندارد، و در هر گام تنها یک ارزیابی تازهٔ تابع می‌خواهد (از f(xn−1)f(x_{n-1}) دوباره استفاده می‌شود).

مرتبه. برای یک ریشهٔ ساده و f∈C2f\in C^{2} خطا از en+1≈C enen−1e_{n+1}\approx C\,e_n e_{n-1} با C=∣f′′(r)2f′(r)∣C=\left\lvert\dfrac{f''(r)}{2f'(r)}\right\rvert پیروی می‌کند؛ قرار دادن en∼Ken−1pe_n\sim K e_{n-1}^{p} رابطهٔ p2=p+1p^{2}=p+1 را الزام می‌کند، پس p=1+52≈1.618 (the golden ratio),lim⁡n→∞∣en+1∣∣en∣ p=C p−1.p=\frac{1+\sqrt5}{2}\approx1.618\ (\text{the golden ratio}),\qquad \lim_{n\to\infty}\frac{\lvert e_{n+1}\rvert}{\lvert e_n\rvert^{\,p}}=C^{\,p-1}. فوق‌خطی اما زیرِ درجه‌دو. با این حال اگر به ازای هر ارزیابی تابع بسنجیم، روش وتری امتیاز 1.6181.618 می‌گیرد در برابر 2≈1.414\sqrt2\approx1.414 برای نیوتن (دو ارزیابی برای مرتبهٔ 22): هرگاه هزینهٔ f′f' به‌اندازهٔ ff باشد، وتری کاراتر است.

خطرها: هیچ بازهٔ محصورکننده‌ای نگه نمی‌دارد، پس می‌تواند واگرا شود؛ و f(xn)=f(xn−1)f(x_n)=f(x_{n-1}) گام را تعریف‌نشده می‌کند.

۵. نابه‌جایی (وضع خطا / رگولا فالسی) و خویشاوندانش

همان فرمول وتری، اما دو نقطه همیشه به‌گونه‌ای نگه داشته می‌شوند که ریشه را در میان بگیرند: پس از محاسبهٔ xn+1x_{n+1}، آن سرِ بازه‌ای را دور بریزید که مقدار ff آن هم‌علامت با f(xn+1)f(x_{n+1}) است. این پیوند محصورکننده به‌اندازهٔ تنصیف قابل‌اعتماد همگرا می‌شود، اما مرتبه‌اش به خطی برمی‌گردد، زیرا برای ff محدب یکی از دو سرِ بازه برای همیشه ثابت می‌ماند و تنها دیگری حرکت می‌کند. گونهٔ ایلینوی مقدار ذخیره‌شده در سرِ نگه‌داشته‌شده را نصف می‌کند و سرعت فوق‌خطی را بازمی‌گرداند.

دیگر اعضای نام‌دار: استفنسن، xn+1=xn−f(xn)2f(xn+f(xn))−f(xn)x_{n+1}=x_n-\dfrac{f(x_n)^{2}}{f\big(x_n+f(x_n)\big)-f(x_n)} — درجه‌دو بدون مشتق؛ مولر — درون‌یابی درجه‌دو، مرتبهٔ ≈1.84\approx1.84، می‌تواند از محور حقیقی خارج شود و ریشه‌های مختلط بیابد؛ آیتکن Δ2\Delta^{2} — هر دنبالهٔ خطی همگرا را شتاب می‌دهد.

۶. جدول مقایسه

روش فرض‌ها ارزیابی‌های تازهٔ ff در هر گام بازهٔ محصورکننده حفظ می‌شود؟ مرتبهٔ pp همگرایی
تنصیف پیوستگی + تغییر علامت 11 بله 11، با عامل 12\tfrac12 تضمین‌شده، سراسری
نابه‌جایی پیوستگی + تغییر علامت 11 بله 11 (معمولاً) تضمین‌شده، سراسری
نقطهٔ ثابت x=g(x)x=g(x) ∣g′∣≤L<1\lvert g'\rvert\le L<1، خودنگاشتی 11 خیر 11، یا pp اگر g′(r)=⋯=g(p−1)(r)=0g'(r)=\cdots=g^{(p-1)}(r)=0 سراسری روی بازهٔ انقباض
وتری دو مقدار آغازین، f∈C2f\in C^{2}، ریشهٔ ساده 11 خیر 1+52≈1.618\tfrac{1+\sqrt5}{2}\approx1.618 موضعی
نیوتن در دسترس بودن f′f'، f∈C2f\in C^{2}، f′(r)≠0f'(r)\ne0 22 خیر 22 موضعی؛ سراسری تحت آزمون ff′′>0f f''>0
نیوتن در ریشه‌ای با مرتبهٔ تکرار mm مانند بالا اما f′(r)=0f'(r)=0 22 خیر 11، با نرخ 1−1m1-\tfrac1m موضعی
نیوتن اصلاح‌شده، با گام mf/f′m f/f' f′f' و مرتبهٔ تکرار mm 22 خیر 22 موضعی

۷. مثال کوچک حل‌شده — یک ریشه، سه روش

همان ریشهٔ محصورشدهٔ بالا را بگیرید: f(x)=x3−3x2+2x−1f(x)=x^{3}-3x^{2}+2x-1 روی [2,3][2,3]، f′(x)=3x2−6x+2f'(x)=3x^{2}-6x+2، r=2.324718r=2.324718.

تنصیف. x1=2.5x_1=2.5 با f(2.5)=0.875>0f(2.5)=0.875>0، پس بازه به [2,2.5][2,2.5] تبدیل می‌شود؛ x2=2.25x_2=2.25 با f=−0.2969<0f=-0.2969<0، بازه [2.25,2.5][2.25,2.5]؛ x3=2.375x_3=2.375 با f=0.2246>0f=0.2246>0، بازه [2.25,2.375][2.25,2.375]. خطا پس از nn گام ≤2−n\le2^{-n} است، پس دقت 10−310^{-3} به n≥log⁡21000=9.97n\ge\log_2 1000=9.97 نیاز دارد، یعنی 1010 گام.

نیوتن از x0=2.5x_0=2.5. f(2.5)=0.875f(2.5)=0.875، f′(2.5)=5.75f'(2.5)=5.75، پس x1=2.5−0.8755.75=2.347826,x2=2.347826−0.1006774.449899=2.325202,x3=2.3247180.x_1=2.5-\frac{0.875}{5.75}=2.347826,\qquad x_2=2.347826-\frac{0.100677}{4.449899}=2.325202,\qquad x_3=2.3247180 . خطاها 1.8⋅10−1, 2.3⋅10−2, 4.8⋅10−4, 2⋅10−71.8\cdot10^{-1},\ 2.3\cdot10^{-2},\ 4.8\cdot10^{-4},\ 2\cdot10^{-7}: هر یک تقریباً 0.930.93 برابرِ مربعِ قبلی است، که با ∣f′′(r)2f′(r)∣=6r−62(3r2−6r+2)≈0.93\left\lvert\frac{f''(r)}{2f'(r)}\right\rvert=\frac{6r-6}{2(3r^{2}-6r+2)}\approx0.93 می‌خواند. دو گام نیوتن از ده گام تنصیف بهتر است.

وتری از x0=2, x1=3x_0=2,\ x_1=3. با f(2)=−1f(2)=-1 و f(3)=5f(3)=5، x2=3−5⋅3−25−(−1)=3−56=2.1667,f(x2)=−0.5787,x_2=3-5\cdot\frac{3-2}{5-(-1)}=3-\frac56=2.1667,\qquad f(x_2)=-0.5787, x3=x2−f(x2)x2−x1f(x2)−f(x1)=2.1667+0.5787⋅−0.8333−5.5787=2.2531,x_3=x_2-f(x_2)\frac{x_2-x_1}{f(x_2)-f(x_1)}=2.1667+0.5787\cdot\frac{-0.8333}{-5.5787}=2.2531, که بدون آنکه هرگز به f′f' دست بزند به همان rr همگرا می‌شود. توجه کنید که x2x_2 در اینجا دقیقاً نخستین نقطهٔ روش نابه‌جایی نیز هست؛ دو روش تنها از گام بعد از هم جدا می‌شوند، آنجا که رگولا فالسی بر حفظ تغییر علامت پافشاری می‌کند.

۸. تکرارهای نیوتنیِ مبدل که باید در نگاه اول بشناسید

کنکور عاشق آن است که یک تکرار به شما بدهد و حد یا مرتبه‌اش را بپرسد. ff را وارونه‌مهندسی کنید:

تکرار نیوتن برای حد مرتبه
xn+1=12(xn+axn)x_{n+1}=\tfrac12\left(x_n+\frac{a}{x_n}\right) f(x)=x2−af(x)=x^{2}-a a\sqrt a برای هر x0>0x_0>0 22
xn+1=1k((k−1)xn+axn k−1)x_{n+1}=\tfrac1k\left((k-1)x_n+\frac{a}{x_n^{\,k-1}}\right) f(x)=xk−af(x)=x^{k}-a a1/ka^{1/k} 22
xn+1=xn(2−axn)x_{n+1}=x_n(2-a x_n) f(x)=1x−af(x)=\frac1x-a 1a\frac1a، بدون هیچ تقسیمی 22
xn+1=xnxn2+3a3xn2+ax_{n+1}=x_n\dfrac{x_n^{2}+3a}{3x_n^{2}+a} هالی اعمال‌شده بر x2−ax^{2}-a a\sqrt a 33
xn+1=cos⁡xnx_{n+1}=\cos x_n نقطهٔ ثابت ساده، g′(r)≈−0.67g'(r)\approx-0.67 0.739…0.739\ldots 11

برای موردِ بدون تقسیم، اثباتی یک‌خطی برای همگرایی درجه‌دو وجود دارد: 1−axn+1=1−2axn+a2xn2=(1−axn)2,1-a x_{n+1}=1-2a x_n+a^{2}x_n^{2}=(1-a x_n)^{2}, پس خطای نسبی در هر گام به توان دو می‌رسد — و تکرار اگر و تنها اگر ∣1−ax0∣<1\lvert 1-ax_0\rvert<1، یعنی 0<x0<2/a0<x_0<2/a، همگرا می‌شود.

۹. معیارهای توقف

وقتی ∣xn+1−xn∣≤ε(1+∣xn∣)\lvert x_{n+1}-x_n\rvert\le\varepsilon\left(1+\lvert x_n\rvert\right) (معیار آمیختهٔ مطلق/نسبی) و ∣f(xn)∣≤δ\lvert f(x_n)\rvert\le\delta برقرار شد متوقف شوید، همواره با سقفی بر تعداد تکرارها. باقی‌مانده‌ی کوچک به معنای خطای کوچک نیست: چون ∣xn−r∣≈∣f(xn)∣/∣f′(r)∣\lvert x_n-r\rvert\approx\lvert f(x_n)\rvert/\lvert f'(r)\rvert، یک ff تقریباً تخت (ریشه‌های مکرر یا خوشه‌ای) آزمون باقی‌مانده را به‌شدت خوش‌بین می‌کند. جنبهٔ خوش‌وضعی این گزاره در کارت تحلیل خطا بسط داده شده است.

۱۰. کنکور این مبحث را چگونه می‌آزماید

  • شمردن و مکان‌یابی ریشه‌های حقیقی یک معادلهٔ درجه‌سوم یا یک معادلهٔ متعالی، که چهار گزینه تعداد یا بازه‌ها را نام می‌برند. با مقادیر بحرانی به‌علاوهٔ یک آزمون علامت (قضیهٔ مقدار میانی) حل کنید — هرگز با تلاش برای تجزیه.
  • «چند گام تنصیف برای دقت ε\varepsilon روی [a,b][a,b]؟» — پاسخ ⌈log⁡2b−aε⌉\lceil\log_2\frac{b-a}{\varepsilon}\rceil است و گزینه‌های انحرافی همان شمارش‌های یکی‌کم/یکی‌بیشِ همسایه‌اند.
  • اجرای یک یا دو گام با دست از نیوتن، وتری یا نابه‌جایی از یک نقطهٔ آغازین داده‌شده؛ گزینه‌های انحرافی از تغییر علامت در f/f′f/f' یا از وارون‌کردن خارج‌قسمت تفاضلی می‌آیند.
  • «مرتبهٔ همگرایی چیست؟» با گزینه‌های 1, 1.618, 2, 31,\ 1.618,\ 2,\ 3 — تلهٔ کلاسیک، نیوتن در ریشهٔ مکرر است که پاسخ 11 است، نه 22.
  • «کدام gg باعث می‌شود xn+1=g(xn)x_{n+1}=g(x_n) به rr همگرا شود؟» — شرط ∣g′(r)∣<1\lvert g'(r)\rvert<1 را روی هر گزینه بسنجید؛ چند بازنویسیِ یک معادله عرضه می‌شود و تنها یکی از آن‌ها انقباضی است.
  • بازشناسی یک تکرار نیوتنی مبدل (a\sqrt a، a1/ka^{1/k}، 1/a1/a) و بیان حد و مرتبه‌اش.
  • درست/نادرست‌های مقایسهٔ روش‌ها: کدام روش همگرایی تضمین‌شده دارد (تنصیف، نابه‌جایی)، کدام به مشتق نیاز دارد (نیوتن)، کدام به دو نقطهٔ آغازین نیاز دارد (وتری)، کدام ریشهٔ با مرتبهٔ تکرار زوج را از دست می‌دهد (هر روش محصورکننده).

نکتهٔ کنکوری: پیش از هر محاسبه‌ای، بر پایهٔ فرض‌ها دسته‌بندی کنید. تغییر علامت داده شده است ⇒\Rightarrow تنصیف/نابه‌جایی، و پاسخ یک شمارش log⁡2\log_2ی است. مشتق داده شده است ⇒\Rightarrow نیوتن، مرتبهٔ 22 مگر آنکه f′(r)=0f'(r)=0. دو نقطهٔ آغازین و بدون مشتق ⇒\Rightarrow وتری، مرتبهٔ 1.6181.618. و برای «چند ریشه»، هرگز بسط ندهید و دنبال عامل‌ها نگردید: تراز cc را با مقادیر اکسترمم موضعی gg بسنجید — y=cy=c هر شاخهٔ یکنوا را دقیقاً یک بار قطع می‌کند وقتی cc میان مقادیر انتهایی آن شاخه باشد، پس تعداد (و بازه) بی‌درنگ به دست می‌آید.

تلهٔ رایج: f(a)f(b)>0f(a)f(b)>0 به این معنا نیست که ریشه‌ای در [a,b][a,b] وجود ندارد، و همگرایی درجه‌دو یک وعدهٔ سراسری نیست. نیوتن از یک x0x_0 نامناسب واگرا می‌شود، دور می‌افتد، یا به ریشهٔ نادرست می‌پرد، و در ریشه‌ای با مرتبهٔ تکرار mm به سرعت صرفاً خطی (نرخ 1−1m1-\tfrac1m) فرومی‌افتد — دقیقاً همان وضعیتی که در آن باقی‌مانده ∣f(xn)∣\lvert f(x_n)\rvert نیز دربارهٔ خطای واقعی دروغ می‌گوید.

فرمول‌های کلیدی

Newton–Raphson iteration
xn+1=xn−f(xn)f′(xn),lim⁡n→∞∣xn+1−r∣∣xn−r∣2=∣f′′(r)2f′(r)∣x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\qquad \lim_{n\to\infty}\frac{\lvert x_{n+1}-r\rvert}{\lvert x_n-r\rvert^{2}}=\left\lvert\frac{f''(r)}{2f'(r)}\right\rvert

Tangent-line step; quadratic (p = 2) at a simple root of a C² function, but only linear with rate 1 − 1/m at a root of multiplicity m.

Secant iteration and its order
xn+1=xn−1f(xn)−xnf(xn−1)f(xn)−f(xn−1),p=1+52≈1.618x_{n+1}=\frac{x_{n-1}f(x_n)-x_nf(x_{n-1})}{f(x_n)-f(x_{n-1})},\qquad p=\frac{1+\sqrt{5}}{2}\approx1.618

Derivative-free Newton: one new function evaluation per step, superlinear order equal to the golden ratio (root of p² = p + 1).

Bisection error bound and step count
∣xn−r∣≤b0−a02 n⟹n=⌈log⁡2b0−a0ε⌉\lvert x_n-r\rvert\le\frac{b_0-a_0}{2^{\,n}}\qquad\Longrightarrow\qquad n=\left\lceil\log_2\frac{b_0-a_0}{\varepsilon}\right\rceil

Guaranteed, a-priori accuracy for a continuous f with f(a₀)f(b₀) < 0: one bit per iteration, about 3.32 iterations per decimal digit.

#root-finding#bisection#newton-method#secant-method#fixed-point-iteration#root-localization

کارت‌های مرتبط

مفهوممبانی آنالیز عددی
حساب ممیز شناور، شرطی‌بودن و پایداری عددی

گرد کردن هر عدد حقیقی را روی شبکه‌ای می‌نشاند که فاصلهٔ محلی‌اش یک واحد در آخرین رقم است، عدد شرطی دقیقاً همان ضریبی است که مسئله با آن این خطای اجتناب‌ناپذیر داده را در پاسخ تقویت می‌کند، و الگوریتم پایدارِ پسرو تنها قول می‌دهد که مسئله‌ای مجاور را به‌طور دقیق حل کرده است.

floating-pointmachine-epsiloncondition-numberbackward-stability
مفهوممبانی آنالیز عددی
تکرار نقطهٔ ثابت و روش نیوتن: مرتبهٔ همگرایی

مرتبهٔ یک تکرار را نخستین مشتق ناصفرِ تابع تکرار در نقطهٔ ثابت تعیین می‌کند — و همین است که نیوتن را در ریشهٔ ساده درجه‌دو، در ریشهٔ مکرر تنها خطی، و تکرار سینوسی را صرفاً مماسی می‌سازد.

fixed-point-iterationorder-of-convergencenewton-methodsecant-method

سوالات تمرینی

مبانی آنالیز عددیآسانریشه‌یابی معادلات غیرخطیکنکور ارشد ریاضی ۱۴۰۰ — سؤال ۳۱

تعداد و محل تقریبی ریشه‌های حقیقی معادلهٔ x(x-1)(x-2)=1 ، کدام است؟