``broyden''

The modified Broyden algorithm discussed in class is:

1. Trial step --
   • Form trial step $\mbox{Rho}_{it+1}=\mbox{Rho}_{it}+\alpha \mbox{g}_{it}$
2. Prediction step --
   • Form matrix
     
     $$\mbox{\bf G}=\left(\begin{array}{cccc} \vec g_1 \cdot g_1 & \... ...t+1} & -\frac{1}{2} \\ 1 & \ldots & 1 & 0 \end{array}\right)$$
     
     

   • Form vector
     
     $$\vec{\mbox{u}} = \left(\begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \\ 1 \end{array}\right)$$
     
     

   • Solve
     
     $$\mbox{\bf G} \vec{\mbox{b}} = \vec{\mbox{u}}$$
     
     

   • Form final prediction
     

     $$\mbox{Rho}_{it+1} \longleftarrow \sum_{itp=1}^{it} \mbox{b}_{itp} \mbox{Rho}_{itp} + \mbox{b}_{it+1} \mbox{Rho}_{it+1}$$ (4)

     
     

Important note: This formulation of the algorithm uses Rho$_{it+1}$ and g$_{it+1}$ in two different ways: to store the trial step and residual (which we called Rho' and g' in lecture) and to store the final prediction step. This becomes important for coding only at the stage where we form the final Rho$_{it+1}$. At the final step, you should first multiply the contents of Rho$_{it+1}$ by b$_{it+1}$, and then loop over all of the preceding Rho$_{itp}$, multiplying by b$_{itp}$ and accumulating the final result into Rho$_{it+1}$.

Beginning with your code ``test_it'', make a new program ``broyden'' with the modifications below.