Examples and questions

Section 11.4 Examples and questions

These are additional examples for reviewing the topic we have covered. When reading each example, try to find your own solution before clicking “Answer”. There are also questions for reviewing the concepts of this section.

🔗

Example 11.4.1. Use Broyden’s method to find all roots of a cubic polynomial.

Redo Example 10.4.2 using Broyden’s method instead of Newton’s method.

🔗

Solution.

We have the same vector function to be equated to zero

\begin{equation*} \mathbf F(\mathbf x) = \begin{pmatrix} x_1+x_2+x_3 +2 \\ x_1x_2 + x_1x_3 + x_2x_3 + 7 \\ x_1x_2x_3 + 1 \end{pmatrix} \end{equation*}

but no longer use its Jacobian matrix. The code is modified by computing the steps as h = -B*F(x) and updating the matrix B according to Broyden’s method.

🔗

F = @(x) [x(1) + x(2) + x(3) + 2; 
          x(1)*x(2) + x(1)*x(3) + x(2)*x(3) + 7;
          x(1)*x(2)*x(3) + 1];

x = [1; 2; 3];
B = eye(3);
max_tries = 10000;

for k = 1:max_tries
    h = -B*F(x);
    w = F(x+h) - F(x);
    B = B + (h - B*w)*h'*B / (h'*B*w);
    x = x + h;
    if norm(h) < 100*eps(norm(x))
        break
    end
end

if k < max_tries
    fprintf('Found a solution after %d steps:\n', k);
    disp(x)
    fprintf('The norm of F(x) is %g\n', norm(F(x)))
else
    disp('Failed to converge')
end

Starting from the same point [1; 2; 3] as we used for Newton’s method, we get:

🔗

Found a solution after 1359 steps:
    1.7240
   -3.8737
    0.1497

By contrast, Newton’s method converged in 9 steps. There is a price to pay for the lack of Jacobian matrix.

🔗

Question 11.4.2. The role of the initial point.

The initial point [1; 2; 3] seems unfortunately chosen in Example 11.4.1, because if we start with [1; 1; 1] instead, the method converges much faster: in 37 steps. Recall that for Newton’s method this initial point did not work at all: the Jacobian was not invertible. Why is it possible to use it for Broyden’t method?

🔗

The initial point [1; -2; 3] leads to even faster convergence.

🔗

Question 11.4.3. The role of the initial matrix.

If we keep the initial point [1; 2; 3] in Example 11.4.1 but change the initial guess for inverse Jacobian to the matrix

B = 0.1*eye(3);

the algorithm converges much faster: in 53 steps. Why could this be? In what way does the “smaller” matrix help?

🔗