List of Numerical Analysis Topics - Finding Roots of Nonlinear Equations

Finding Roots of Nonlinear Equations

See #Numerical linear algebra for linear equations

Root-finding algorithm — algorithms for solving the equation f(x) = 0

• General methods:
  • Bisection method — simple and robust; linear convergence
    • Lehmer–Schur algorithm — variant for complex functions
  • Fixed-point iteration
  • Newton's method — based on linear approximation around the current iterate; quadratic convergence
    • Kantorovich theorem — gives a region around solution such that Newton's method converges
    • Newton fractal — indicates which initial condition converges to which root under Newton iteration
    • Quasi-Newton method — uses an approximation of the Jacobian:
      • Broyden's method — uses a rank-one update for the Jacobian
      • SR1 formula — a symmetric (but not necessarily positive definite) rank-one update of the Jacobian
      • Davidon–Fletcher–Powell formula — update of the Jacobian in which the matrix remains positive definite
      • BFGS method — rank-two update of the Jacobian in which the matrix remains positive definite
      • Limited-memory BFGS method — truncated, matrix-free variant of BFGS method suitable for large problems
      • Orthant-wise limited-memory quasi-Newton — designed for log-linear models with l₁-regularization
    • Steffensen's method — uses divided differences instead of the derivative
  • Secant method — based on linear interpolation at last two iterates
  • False position method — secant method with ideas from the bisection method
  • Muller's method — based on quadratic interpolation at last three iterates
  • Inverse quadratic interpolation — similar to Muller's method, but interpolates the inverse
  • Brent's method — combines bisection method, secant method and inverse quadratic interpolation
  • Ridders' method — fits a linear function times an exponential to last two iterates and their midpoint
  • Halley's method — uses f, f' and f''; achieves the cubic convergence
  • Householder's method — uses first d derivatives to achieve order d + 1; generalizes Newton's and Halley's method
• Methods for polynomials:
  • Aberth method
  • Bairstow's method
  • Durand–Kerner method
  • Graeffe's method
  • Jenkins–Traub algorithm — fast, reliable, and widely used
  • Laguerre's method
  • Splitting circle method
• Analysis:
  • Wilkinson's polynomial
• Numerical continuation — tracking a root as one parameters in the equation changes
  • Piecewise linear continuation