Fixed-point iteration is a powerful method for solving nonlinear equations. It works by repeatedly applying a function to an initial guess until a solution is found. This technique is especially useful when direct solutions are hard to come by.

The method's success hinges on choosing the right function and initial guess. It can be applied to various types of equations and even systems of equations. Understanding its convergence behavior and limitations is key to using it effectively.

Fixed-point iteration principles

Fundamentals of fixed-point iteration

• Fixed-point iteration finds solutions to equations in the form x = g(x), where g(x) represents a continuous function
• Fixed-point theorem guarantees a unique fixed point x* where x* = g(x) if g(x) is a contraction mapping on a closed interval [a,b]
• Iterative process involves repeatedly applying g(x) to an initial guess x0 until convergence
• Applies to various nonlinear equations (algebraic, transcendental, mixed)
• Useful for complex problems where direct analytical solutions are challenging (engineering, scientific applications)
• Geometrically interpreted as finding the intersection of y = x and y = g(x)

Function selection and interpretation

• Choice of g(x) critically impacts success and efficiency of fixed-point iteration
• Different g(x) formulations lead to varied convergence behaviors
• Example: For equation $x^3 + x - 1 = 0$, possible g(x) formulations include:
  • $g(x) = \sqrt[3]{1-x}$
  • $g(x) = 1 - x^3$
• Selecting appropriate g(x) requires understanding of problem characteristics and desired convergence properties
• Graphical analysis helps visualize convergence behavior (plotting y = x and y = g(x))

Fixed-point iteration algorithms

General algorithm and implementation

• Define function g(x)
• Select initial guess x0
• Iterate using formula $x_{n+1} = g(x_n)$ until stopping criterion met
• Common stopping criteria:
  • Reach maximum number of iterations
  • Achieve desired accuracy $|x_{n+1} - x_n| < \varepsilon$
• Careful consideration of numerical stability and error propagation ensures accurate results
• Implementation example in Python:

  def fixed_point_iteration(g, x0, epsilon, max_iter):
      x = x0
      for i in range(max_iter):
          x_new = g(x)
          if abs(x_new - x) < epsilon:
              return x_new
          x = x_new
      return None  # Convergence not achieved
  

Advanced techniques and extensions

• Apply to systems of nonlinear equations using vector-valued functions and vector norms
• Acceleration techniques improve convergence rate:
  • Aitken's Δ2 process
  • Steffensen's method
• Adapt for parallel computing to solve large-scale problems efficiently
• Combine with other numerical methods (Newton's method, secant method) for hybrid algorithms
• Example hybrid algorithm (Fixed-point iteration with Newton's method):

  def hybrid_fixed_point_newton(g, g_prime, x0, epsilon, max_iter):
      x = x0
      for i in range(max_iter):
          x_new = g(x)
          if abs(x_new - x) < epsilon:
              return x_new
          x = x - (x - g(x)) / g_prime(x)  # Newton's method step
      return None  # Convergence not achieved
  

Convergence of fixed-point iteration

Convergence criteria and behavior

• Convergence guaranteed if $|g'(x)| < 1$ near fixed point (contraction mapping principle)
• Linear convergence rate with error reduction factor proportional to $$|g'(x^)|$ (x is fixed point)
• Divergence occurs if $|g'(x)| > 1$ near fixed point, leading to instability
• Basin of attraction represents set of initial guesses leading to convergence
• Analyze global iteration behavior using basins of attraction
• Example: For $g(x) = \cos(x)$, basin of attraction includes all real numbers

Limitations and challenges

• Slow convergence or failure for functions with nearly horizontal tangent lines near fixed point
• Multiple fixed points possible for given g(x)
• Initial guess influences which solution iteration converges to
• Sensitive to rounding errors and numerical instabilities (ill-conditioned problems, near-singular situations)
• May not suit finding complex roots or handling discontinuous functions
• Example of ill-conditioned problem: $x^3 - 1000x^2 + 1 = 0$ near x = 1000