𝓜

Math Notes

University Mathematics

ConceptComplete

Convergence Analysis

Understanding convergence rates and basins of attraction is essential for selecting appropriate root-finding algorithms and initial guesses. Different algorithms offer trade-offs between convergence speed, robustness, and computational cost.

DefinitionOrder of Convergence

Let {xn}\{x_n\} converge to rr with xn≠rx_n \neq r for all nn. The sequence has order of convergence α≥1\alpha \geq 1 if: lim⁡n→∞∣xn+1−r∣∣xn−r∣α=C\lim_{n \to \infty} \frac{|x_{n+1} - r|}{|x_n - r|^\alpha} = C for some constant 0<C<∞0 < C < \infty. The case α=1\alpha = 1 with C<1C < 1 is linear convergence, α=2\alpha = 2 is quadratic convergence, and 1<α<21 < \alpha < 2 is superlinear convergence.

Higher convergence order means faster asymptotic convergence, but requires more regularity of ff and more computational work per iteration. The order characterizes how rapidly errors decrease once the iteration enters a neighborhood of the root.

ExampleComparing Methods for $f(x) = x^3 - 2$

Finding 23≈1.259921\sqrt[3]{2} \approx 1.259921 starting from x0=1x_0 = 1:

Bisection (linear, rate 1/2):

  • 10 iterations: error ≈10−3\approx 10^{-3}
  • 20 iterations: error ≈10−6\approx 10^{-6}

Secant (order 1.618):

  • 5 iterations: error ≈10−6\approx 10^{-6}
  • 7 iterations: error ≈10−12\approx 10^{-12}

Newton (quadratic):

  • 4 iterations: error ≈10−6\approx 10^{-6}
  • 5 iterations: error ≈10−12\approx 10^{-12}

Newton converges fastest asymptotically but requires computing f′(x)=3x2f'(x) = 3x^2 at each step.

Remark

Basin of Attraction: For an iterative method xn+1=ϕ(xn)x_{n+1} = \phi(x_n) with fixed point rr (so ϕ(r)=r\phi(r) = r), the basin of attraction is the set of initial values x0x_0 for which lim⁡n→∞xn=r\lim_{n \to \infty} x_n = r.

Newton's method can have fractal basin boundaries in the complex plane, meaning arbitrarily close initial guesses may converge to different roots or diverge. This motivates hybrid methods that combine global convergence guarantees with fast local convergence.

For Newton's method, if f∈C2f \in C^2 near rr with f(r)=0f(r) = 0 and f′(r)≠0f'(r) \neq 0, there exists δ>0\delta > 0 such that ∣x0−r∣<δ|x_0 - r| < \delta guarantees quadratic convergence. The size of δ\delta depends on the ratio ∣f′′(r)∣/∣f′(r)∣|f''(r)|/|f'(r)|: larger second derivatives or smaller first derivatives reduce the basin of attraction.

Multiple roots (f′(r)=0f'(r) = 0) reduce Newton's method to linear convergence. If ff has a zero of multiplicity mm at rr: f(x)=(x−r)mh(x),h(r)≠0f(x) = (x-r)^m h(x), \quad h(r) \neq 0 then the error satisfies: ∣xn+1−r∣∣xn−r∣≈1−1m\frac{|x_{n+1} - r|}{|x_n - r|} \approx 1 - \frac{1}{m}

This motivates modified methods that detect multiplicity or use deflation techniques to remove known roots.

Practical stopping criteria must balance multiple factors: absolute tolerance ∣xn+1−xn∣<ϵabs|x_{n+1} - x_n| < \epsilon_{\text{abs}}, relative tolerance ∣xn+1−xn∣/∣xn+1∣<ϵrel|x_{n+1} - x_n|/|x_{n+1}| < \epsilon_{\text{rel}}, and residual tolerance ∣f(xn)∣<ϵres|f(x_n)| < \epsilon_{\text{res}}. Ill-conditioned roots (where f′(r)≈0f'(r) \approx 0) can have small residuals but large errors in xx, requiring careful criterion selection.