8.5 Broyden's method

Broyden's method is a clever way to solve tricky math problems without doing all the hard work. It's like finding shortcuts in a maze. Instead of mapping out every turn, you make educated guesses based on what you've learned so far.

This method builds on what we've learned about solving equations, but with a twist. It's faster and uses less brain power than other methods, making it great for tackling big, complex problems in science and engineering.

Broyden's method for nonlinear equations

Concept and derivation

• Broyden's method solves systems of nonlinear equations without explicitly computing the Jacobian matrix
• Approximates the Jacobian matrix using the secant condition relating function change to variable change
• Derives update formula by minimizing Frobenius norm of difference between current and previous Jacobian approximations, subject to secant condition
• Uses Sherman-Morrison formula to efficiently update inverse of Jacobian approximation in each iteration
• Generalizes secant method for systems of equations
• Maintains superlinear convergence rate of Newton's method while reducing computational cost per iteration
• Secant condition formula: $B_{k+1}(x_{k+1} - x_k) = f(x_{k+1}) - f(x_k)$
• Broyden's update formula: $B_{k+1} = B_k + \frac{(y_k - B_k s_k)s_k^T}{s_k^T s_k}$
  • Where $y_k = f(x_{k+1}) - f(x_k)$ and $s_k = x_{k+1} - x_k$

Applications and advantages

• Solves systems of nonlinear equations in various fields (engineering, physics, economics)
• Particularly effective for problems with expensive function evaluations
• Requires fewer function evaluations per iteration compared to Newton's method
• Reduces memory requirements by storing only Jacobian approximation
• Suitable for large-scale problems where explicit Jacobian computation becomes impractical
• Examples of applications
  • Solving chemical equilibrium problems
  • Optimizing network flow in transportation systems
  • Finding roots of complex polynomial systems

Implementation and convergence of Broyden's method

Algorithm implementation

• Initialize Jacobian approximation (identity matrix or finite differences)
• Iteratively update solution and refine Jacobian approximation
• Update formula for solution vector involves solving linear system using current Jacobian approximation
• Solution update equation: $x_{k+1} = x_k - B_k^{-1} f(x_k)$
• Implement convergence criteria (check norm of function value or change in solution vector)
• Pseudocode for basic Broyden's method:

</>Code
Initialize x0, B0
While not converged:
    Solve Bk * sk = -f(xk) for sk
    xk+1 = xk + sk
    yk = f(xk+1) - f(xk)
    Bk+1 = Bk + (yk - Bk*sk) * sk^T / (sk^T * sk)

Convergence properties and improvements

• Exhibits local and q-superlinear convergence under certain conditions
• Convergence rate between linear and quadratic (superlinear with order 1 + √2)
• Initial guess must be sufficiently close to solution for convergence
• Incorporate safeguarding techniques to improve global convergence
  • Line searches (backtracking, Armijo rule)
  • Trust region methods (restrict step size based on model accuracy)
• Damped Broyden's method improves stability for ill-conditioned problems
• Broyden-Fletcher-Goldfarb-Shanno (BFGS) method extends Broyden's idea to optimization problems

Broyden's method vs other nonlinear equation solvers

Comparison with Newton's method

• Requires fewer function evaluations per iteration than Newton's method
• Lower memory requirement (stores only Jacobian approximation)
• Generally faster for problems with expensive function evaluations
• Performance depends on problem structure and initial Jacobian approximation accuracy
• Newton's method advantages
  • Quadratic convergence rate (faster near solution)
  • More robust for highly nonlinear problems
• Broyden's method advantages
  • No need for explicit Jacobian computation
  • Lower computational cost per iteration

Comparison with other methods

• Converges faster than fixed-point iteration methods (Picard iteration, successive substitution)
• More robust than simple secant method for systems of equations
• Less effective for highly nonlinear or ill-conditioned Jacobians
• Hybrid approaches can outperform pure Broyden's method
  • Broyden-GMRES method (combines with Generalized Minimal Residual method)
  • Anderson acceleration (improves convergence for some problem classes)
• Trade-offs between convergence speed, robustness, and computational cost per iteration
• Examples of method selection criteria
  • Problem size (Broyden's for large-scale problems)
  • Function evaluation cost (Broyden's for expensive evaluations)
  • Jacobian structure (Newton's for sparse, easily computed Jacobians)