Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics IV resit / 7

Start with $[a_0,b_0]=[a,b]$. At stage $n$, form the midpoint $c_n=(a_n+b_n)/2$. If $f(c_n)=0$, stop; for a sequence defined for all later indices, repeat $c_n$ forever. Otherwise retain the half-interval with opposite endpoint signs: set $[a_{n+1},b_{n+1}]=[a_n,c_n]$ if $f(a_n)f(c_n)<0$, and $[a_{n+1},b_{n+1}]=[c_n,b_n]$ otherwise. This is the bisection method.

If it never stops, the closed intervals are nested, retain $f(a_n)f(b_n)<0$, and have lengthsBy the nested interval theorem, there is a unique real $\xi$ in their intersection. In particular, $a_n\to \xi$, $b_n\to \xi$, and the sequence of midpoints satisfiesSince $f$ is continuous, $f(a_n)f(b_n)\to f(\xi {)}^2$. All these products are negative, so their limit of a sequence is nonpositive. Therefore $f(\xi {)}^2\le 0$, forcing $f(\xi )=0$. We have proved that the sequence is a convergent sequence whose limit of a sequence is a zero of a function:The error bound applies at every stage before exact termination; after termination the error is zero. The intermediate value theorem also guarantees a zero of a function in each retained interval, but the nested-interval argument identifies the particular one to which the sequence of midpoints converges.

For an unconstrained differentiable function of two real variables, an interior local minimum must solve the simultaneous stationary point equationsApply Newton's method in optimization to this gradient equation. The Jacobian matrix of the gradient is the Hessian matrixAt $p_n=(x_n,y_n{)}^T$, solve the linear system $H(p_n)s_n=-\nabla f(p_n)$, then set $p_{n+1}=p_n+s_n$. When the Hessian matrix is invertible, this isThis follows by setting the first order Taylor expansion $\nabla f(p_n+s_n)\simeq \nabla f(p_n)+H(p_n)s_n$ equal to zero. Solving the linear system avoids explicitly computing a matrix inverse. A stationary point need not be a local minimum: for example, a positive-definite matrix $H(p)$ suffices to classify a stationary point as a strict local minimum, whereas an indefinite Hessian matrix identifies a saddle point of a scalar function.

Expanding and taking partial derivatives gives the gradient and Hessian matrixAt $p_0=(-1,0{)}^T$, these are $\nabla f(p_0)=(-6,2{)}^T$ andThus the Newton step solvesThe second equation gives $s_y=1-2s_x$; substituting into the first gives $22s_x=10$. HenceAt $p_{\ast }=(-1/2,-1/2{)}^T$, however,The eigenvalues of this Hessian matrix are $-1$ in direction $(1,1)$ and $7$ in direction $(1,-1)$. It is invertible but indefinite. Thus the Newton step is zero, andThis illustrates that stationary points are fixed points of Newton's method. Here the fixed point is a saddle point of a scalar function, not a local minimum. Indeed, direct substitution along the two eigenvector directions givesFor sufficiently small nonzero $t$, one direction decreases $f$ and the other increases it. The global minimum is instead zero: the sum of squares vanishes at $(0,0)$ and $(-1,-1)$. These are the only real zeros, since $x=-y^2$ and $y=-x^2$ imply $y(y^3+1)=0$. Thus a zero gradient is an insufficient stopping certificate for minimization problem without classifying the stationary point.