Math 2.0

Numerical analysis Nonlinear equations Theorem

Broyden's method

Builds on Newton's methodJacobian matrixLipschitz conditionRate of convergenceInvertible matrixFrobenius normSecant method

Statement

Let U⊆ℝnU \subseteq \R^n be open and let F ⁣:U→ℝnF \colon U \to \R^n be continuously differentiable, with Jacobian matrix J(x)J(x). Let x∗∈Ux^* \in U satisfy F(x∗)=0F(x^*) = 0, let J(x∗)J(x^*) be invertible, and let JJ be Lipschitz continuous near x∗x^*. Broyden's method starts from x0∈Ux_0 \in U and an invertible n×nn \times n matrix B0B_0, and for k≥0k \ge 0 sets xk+1=xk−Bk−1F(xk),sk=xk+1−xk,yk=F(xk+1)−F(xk),x_{k+1} = x_k - B_k^{-1} F(x_k), \qquad s_k = x_{k+1} - x_k, \qquad y_k = F(x_{k+1}) - F(x_k), Bk+1=Bk+(yk−Bksk) skTskTsk.B_{k+1} = B_k + \frac{(y_k - B_k s_k) \, s_k^T}{s_k^T s_k}. Then there are ε>0\varepsilon > 0 and δ>0\delta > 0 such that, if ∥x0−x∗∥<ε\norm{x_0 - x^*} < \varepsilon and ∥B0−J(x∗)∥<δ\norm{B_0 - J(x^*)} < \delta, the iterates are defined and xk→x∗x_k \to x^* superlinearly: lim⁡k→∞∥xk+1−x∗∥∥xk−x∗∥=0,\lim_{k \to \infty} \frac{\norm{x_{k+1} - x^*}}{\norm{x_k - x^*}} = 0, whenever xk≠x∗x_k \ne x^* for all kk.

Remarks

The update makes Bk+1B_{k+1} satisfy the secant equation Bk+1sk=ykB_{k+1} s_k = y_k, the analogue of the secant method slope in several variables. Among all matrices that satisfy it, Bk+1B_{k+1} is the closest to BkB_k in the Frobenius norm, and Bk+1−BkB_{k+1} - B_k has rank at most 11. By the Sherman–Morrison formula, Bk+1−1B_{k+1}^{-1} is obtained from Bk−1B_k^{-1} in O(n2)O(n^2) operations, so no linear system has to be solved from scratch. The proof first shows that the errors decrease linearly while BkB_k stays close to J(x∗)J(x^*), and then that (Bk−J(x∗))sk/∥sk∥→0(B_k - J(x^*)) s_k / \norm{s_k} \to 0, which is the Dennis–Moré condition for superlinear convergence. The matrices BkB_k need not converge to J(x∗)J(x^*). For n=1n = 1 the method is the secant method.

Going deeper

For a student

Broyden's method is the first and simplest quasi-Newton method for nonlinear systems. Its update is the model for the BFGS and DFP updates in optimization, which keep the matrix symmetric. In practice B0B_0 is often a finite-difference Jacobian, and a line search or trust region makes the method converge from farther away.

Reading path

To understand this page from the ground up, read these 21 pages in order. The foundations come first.

Show the path as a graph
Continuously differentiable function, concept, no evidence levelContinuously differen…conceptDerivative, concept, no evidence levelDerivativeconceptEuclidean space, object, no evidence levelEuclidean spaceobjectFrobenius norm, concept, no evidence levelFrobenius normconceptFunction, concept, no evidence levelFunctionconceptInvertible matrix, concept, no evidence levelInvertible matrixconceptLimit point of a set, definition, no evidence levelLimit point of a setdefinitionLipschitz condition, concept, no evidence levelLipschitz conditionconceptRate of convergence, concept, no evidence levelRate of convergenceconceptRoot-finding algorithm, concept, no evidence levelRoot-finding algorithmconceptSecond derivative, concept, no evidence levelSecond derivativeconceptTotal derivative, concept, no evidence levelTotal derivativeconceptFunction of several variables, concept, no evidence levelFunction of several v…conceptSecant method, statement, no evidence levelSecant methodstatementLimit of a function, definition, no evidence levelLimit of a functiondefinitionPartial derivative, concept, no evidence levelPartial derivativeconceptDerivative, definition, no evidence levelDerivativedefinitionJacobian matrix, concept, no evidence levelJacobian matrixconceptTangent line, concept, no evidence levelTangent lineconceptNewton's method, concept, no evidence levelNewton's methodconceptBroyden's method, statement, no evidence levelBroyden's methodstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Continuously differentiable function concept
  2. Derivative concept
  3. Euclidean space object
  4. Frobenius norm concept
  5. Function concept
  6. Invertible matrix concept
  7. Limit point of a set definition
  8. Lipschitz condition concept
  9. Rate of convergence concept
  10. Root-finding algorithm concept
  11. Second derivative concept
  12. Total derivative concept
  13. Function of several variables concept
  14. Secant method statement
  15. Limit of a function definition
  16. Partial derivative concept
  17. Derivative definition
  18. Jacobian matrix concept
  19. Tangent line concept
  20. Newton's method concept
  21. Broyden's method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Broyden%27s_method
About this page
TagGYNYT7KTC3
URIm2://GYNYT7KTC3
Kindstatement, theorem
WritingW0 stub
MSC65H10
StatusThis copy of the site has no build data. Run m2 status GYNYT7KTC3.
AboutNewton's method
UsesNewton's method, Jacobian matrix, Lipschitz condition, Rate of convergence, Invertible matrix, Frobenius norm, Secant method
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.