Skip to main content

Section 11.3 Details of Broyden's method

Recall from Section 11.1 that we seek to improve our guess for the inverse of Jacobian by finding a matrix \(B_1\) such that

\begin{equation*} B_1(\mathbf F(\mathbf x_1) - \mathbf F(\mathbf x_0)) = \mathbf x_1 - \mathbf x_0 \end{equation*}

To simplify notation, let \(\mathbf h = \mathbf x_1 - \mathbf x_0\) and \(\mathbf w = \mathbf F(\mathbf x_1) - \mathbf F(\mathbf x_0)\text{;}\) both these vectors are known. We need

\begin{equation} B_1 \mathbf w = \mathbf h\label{eq-B1-equation}\tag{11.3.1} \end{equation}

We already know how to find a matrix that satisfies (11.3.1), by taking an outer product multiplied by a scalar (11.2.2). But this would be a bad, illogical choice for \(B_1\text{.}\) Why?

We want \(B_1\) to have some similarity to \(B_0\) in the hope that the process of improving guesses \(B_0, B_1, \dots\) will converge to something, rather than just jump around. We want to improve the previous guess, not replace it entirely. So, let \(B_1 = (I + M)B_0 = B_0 + MB_0\) where \(M\) can be constructed from an outer product as in (11.2.2). Namely, we want

\begin{equation*} B_0 \mathbf w + M B_0 \mathbf w = \mathbf h \end{equation*}

so

\begin{equation*} M B_0 \mathbf w = \mathbf h - B_0 \mathbf w \end{equation*}

According to (11.2.2) we can achieve this by letting

\begin{equation*} M = \frac{1}{\mathbf h^T \mathbf B_0 \mathbf w} (\mathbf h - B_0 \mathbf w) \mathbf h^T \end{equation*}

where the chose the term \(\mathbf b\) to be \(\mathbf h\text{.}\) To summarize, the formula for updating our guess for inverse Jacobian is

\begin{equation*} B_1 = B_0 + \frac{1}{\mathbf h^T \mathbf B_0 \mathbf w} (\mathbf h - B_0 \mathbf w) \mathbf h^T B_0 \end{equation*}

It looks messy, but at least the derivation was logical.

The matrix \(B_1\) is still a guess, it may be very different from the actual inverse of Jacobian matrix. But it is a more educated guess, and as this process repeats, these repeated corrections will produce more accurate guesses.