Overview
Broyden's Method is a quasi-Newton method for systems of equations, replacing expensive exact Jacobians with rank-one updates.
SpecializedSource checked
Broyden's Method
Solves nonlinear systems by updating an approximate Jacobian instead of recomputing it.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Advanced
- Family
- Quasi-Newton Root Finding
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
nonlinear systemJacobian approximationrank-one updateresidual
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(k n^2)
Worst
O(k n^3)
Space
O(n^2)
When to Use
- Use when exact Jacobians are expensive but a Newton-like method is useful.
- Use when nonlinear equation systems is a central requirement.
When Not to Use
- Avoid when high reliability is needed and exact derivatives are available.
- Avoid when roundoff, conditioning, or discontinuities dominate the result.
What It Does
- Tracks an approximate Jacobian
- Solves a linearized step
- Updates the approximation from residual changes
Use Cases
- Nonlinear equation systems
- Expensive Jacobian problems
- Engineering model calibration
Inputs
- Vector function
- Initial guess
Outputs
- Approximate root vector
Key Formulas (1)
Secant condition
Bnext · s = y
B_next * s = yConstrains the updated Jacobian approximation to match the observed step and residual change.
Pseudocode
- 1.Start with an initial Jacobian approximation
- 2.Solve the linearized system for a step
- 3.Evaluate the function at the new point
- 4.Update the Jacobian approximation from the change
- 5.Repeat until residuals are small
Canonical Example
- Input
- two nonlinear equations, initial guess = [1, 1]
- Output
- root estimate updates each iteration
- Explanation
- The Jacobian approximation changes as residuals are observed.
Implementation Notes
- Restart with a fresh Jacobian approximation when progress stalls.
- Compare against a small hand-checkable case before scaling up.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- A poor initial Jacobian approximation can lead to slow or unstable progress.
- Ignoring conditioning can make a correct method return unreliable numbers.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a nonlinear system being solved with a tangent approximation that updates after each step.
Step 1 of 5: Start with an initial Jacobian approximation
numeric-iterationNotes
The method saves Jacobian work but may converge less robustly than Newton's Method.
Sources (1)
What each reference supports for this entry.
Numerical Recipes
BookNumerical methods reference covering quasi-Newton methods for nonlinear systems.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageApproximatesNewton's Method
Broyden's Method approximates Jacobian information for nonlinear systems.
Alternative toSecant Method
Both avoid exact derivatives, but Broyden handles multivariate systems.
Related Algorithms
Tags
Numerical MethodsRoot FindingQuasi-NewtonIterative