Iterative Processes: Bisection & Convergence

• Topics covered:
  • Definition of iterative processes.
  • The Bisection Method
  • The Order of Convergence of an Iterative Method
  • Numerical Stability of Iterative Method

Definition of Iterative Process

• An iterative process solves a problem by repeatedly applying a procedure in cycles
• Each cycle builds on the previous one, approaching the desired solution
• Repetition is a key aspect
• A set of instructions or a process is applied multiple times
• Feedback: Each iteration uses the output of the previous iteration as its input
• Convergence: The goal is to converge towards a solution, fixed point, or optimal state, making progress with each iteration
• Stopping Condition: A condition or criterion is needed to define when the process should stop
  • Stopping conditions:
  • Reaching a desired level of accuracy or tolerance
  • A maximum number of iterations has been performed
  • The change between successive iterations becomes smaller than a predefined threshold
• Iterative processes often produce approximate solutions rather than exact ones
• A well-designed process converges to a solution
• Computational cost depends on the complexity and the number of iterations

The Bisection Method

• This method helps find the roots of a continuous function using numerical techniques

• It relies on having an interval known to contain a root

• The method uses the Intermediate Value Theorem

• States that if a continuous function f(x) has opposite signs at interval endpoints [a, b], there's at least one root in that interval

• The method halves the interval [a, b] repeatedly, keeping the subinterval where the sign change occurs

• Steps:

  • Start with an interval [a, b] where f(a) and f(b) have opposite signs, guaranteeing a root
  • Calculate the midpoint: c = (a + b) / 2
  • Subinterval Selection:
    • If f(c) = 0, c is the root, and the process stops
    • If f(a) * f(c) < 0, the root lies in [a, c]. Set b = c
    • If f(b) * f(c) < 0, the root lies in [c, b]. Set a = c
  • Repeat the process with the new interval [a, b]

• The process continues until a desired level of accuracy is reached

  • Stopping criteria include:
    • The interval width becomes smaller than a specified tolerance (e.g., |b - a| < ε)
    • The absolute value of f(c) becomes smaller than a tolerance (e.g., |f(c)| < ε)
    • A maximum number of iterations is reached

• Advantages:

  • Simple to understand and implement
  • Guaranteed to converge to a root if the initial interval contains a root and the function is continuous
  • Robust to the shape of the function, if it's continuous

• Disadvantages:

  • Slow convergence compared to other methods, especially for high accuracy
  • Needs an initial interval that brackets the root
  • Finds only one root at a time, converging to one in the initial interval without predicting which one

The Order of Convergence of an Iterative Method

• Describes how quickly a sequence of approximations approaches the true solution
• Indicates how the error decreases with each iteration
• A sequence {x_n} converges to a limit x (the true solution)
• There are constants C > 0 and α > 0 such that: lim (n->∞) |x_(n+1) - x| / |x_n - x|^α = C
• The sequence {x_n} converges to x with order α, where C is the asymptotic error constant
• Interpretation:
  • α = 1: Linear convergence i.e. the error decreases linearly
  • α = 2: Quadratic convergence i.e. the error decreases quadratically (much faster)
  • α = 3: Cubic convergence (even faster)
• Linear convergence involves steady progress, but it might take many steps
• Quadratic convergence covers ground quickly, reaching the destination in fewer steps
• Higher-order convergence requires fewer iterations
• Methods with higher-order convergence reduce computational cost, especially for high accuracy
• Theoretical analysis that involves using Taylor series can reveal its order of convergence
• Numerical experiments by Using different initial guesses can estimate the order of convergence empirically
• Key points:
  • The order of convergence is a crucial factor in assessing the efficiency
  • Higher-order convergence usually leads to faster convergence
  • The specific order can vary

Numerical Stability of Iterative Method

• Numerical stability indicates how sensitive the computed results are to small errors or perturbations during the calculation
• A numerically stable method produces results slightly affected by small errors
• An unstable method amplifies these errors, leading to wildly inaccurate results
• An iterative method is numerically stable if small errors during computation do not lead to large deviations in the computed solution
• Types of Instability:
  • Rounding Error Propagation: Accumulation and growth of tiny rounding errors due to finite precision, corrupting the entire solution
  • Sensitivity to Initial Conditions: Sensitivity to the initial guess, leading to different results even if the method is otherwise stable
  • Growth of Errors: Uncontrolled growth of errors during the iteration, becoming large even from small initial errors
• Factors:
  • Algorithm: Some algorithms are inherently more stable
  • Problem Conditioning: Ill-conditioned problems make even stable algorithms appear unstable
  • Floating-Point Arithmetic: Higher precision can improve stability
• Analyzing Numerical Stability:
  • Error Analysis: Studying the growth of errors over multiple iterations
  • Numerical Experiments: Observing how results change with different initial guesses and small perturbations
  • Stability Theory: Using mathematical theory in numerical analysis, such as matrix analysis
• Numerical stability is essential for reliable computations
• Unstable methods can produce garbage results, even if the algorithm is correct
• Stability is closely related to accuracy, as unstable methods amplify errors, making it difficult to obtain accurate solutions