Multivariate Newton's Method

In higher dimensions it becomes difficult to generalize most of the one-dimensional root finding methods, such as bisection.

Basic Newton's Method

If we have a system of equations, $F(x) = 0$ , in which both $F$ and $x$ are $n$ -dimensional vectors (so $F : \Omega \rightarrow \mathbb{R}^n$ for some subset $\Omega \subset \mathbb{R}^n$ ), then Newton's method generalizes to

$x_{m+1} = x_m - DF|_{x_m}^{-1} F(x_m)$

where $DF$ is the Jacobian matrix of derivatives of $F$ . It has components

$(DF)_{i,j} = \frac{\partial F_i}{\partial x_j}$

Usually its a bad idea to explicitly invert the Jacobian matrix, and instead we solve the linear system

$DF|_{x_m} x_{m+1} = DF|_{x_m} x_m - F(x_m)$

for $x_{m+1}$ .

Broyden Methods

In many cases it is either impossible or prohibitively expensive to calculate the Jacobian matrix (or its inverse) directly, and we need to approximate it. This is done iteratively along with the Newton iteration. In the first Broyden method, we approximate the Jacobian at each step by matrice $A_m$ , updated as

$A_{m+1} = A_m + \frac{(D_{m+1} - A_m d_{m+1}) d_{m+1}^T}{d_{m+1}^T d_{m+1}}$

In the second Broyden method (sometimes referred to a little unfairly as the "Bad Broyden method"), we directly estimate $DF^{-1}$ by $B_m$ , using the iteration

$B_{m+1} = B_m + \frac{(d_{m+1} - B_m D_{m+1}) d_{m+1}^T B_m}{d_{m+1}^T B_m D_{m+1}}$