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

The Euclidean algorithm givesThe last nonzero remainder is the greatest common divisor, so $\boxed{\gcd (259,497)=7}$.

Back-substitution in the Euclidean algorithm gives the Bezout identityMultiplying by five produces a particular solution $(x,y)=(-115,60)$. Since $259/7=37$ and $497/7=71$ are coprime integers, all solutions of the linear Diophantine equation areReplacing $t$ by $t+2$ gives the smaller equivalent starting solutionIndeed $259\cdot 27-497\cdot 14=35$. Conversely, subtracting this solution from any other gives $37(x-27)=-71(y+14)$. Coprimality forces $71$ to divide $x-27$, and then $y+14$ is the corresponding multiple of $-37$. This proves completeness of the family.

Define the relative reciprocal error ${\epsilon }_k=1-p{x}_k$. The iteration has the exact identitysoConsequently $|1-p{x}_0|<1$ guarantees $x_k\to 1/p$. For real $p,x_0$, this condition is $0<p{x}_0<2$. A starting guess can be found without division by choosing $x_0$ with the sign of $p$ and repeatedly halving its magnitude until $0<p{x}_0<2$.

For the absolute signed error $e_k=x_k-1/p$, the same identity givesThus the method has cubic convergence, of order of convergence three, with asymptotic error constant $p^2>0$ for a nonexact convergent start. Convergence requires a suitable guess: $p{x}_0=0$ and $p{x}_0=2$ correspond to ${\epsilon }_0=1$ and ${\epsilon }_0=-1$, respectively, so both are fixed failures. For $|1-p{x}_0|>1$ the error magnitude grows without bound. The exact initial value $p{x}_0=1$ is already the answer.

For a twice continuously differentiable function $F$, its gradient and Hessian matrix areA critical point solves $\nabla F=0$. The Jacobian matrix of this vector equation is $H_F$, so the multivariable Newton iteration isEquivalently ${\mathbf{x}}_{k+1}={\mathbf{x}}_k-H_F({\mathbf{x}}_k{)}^{-1}\nabla F({\mathbf{x}}_k)$ when the Hessian matrix is invertible. Solving the linear system is the direct computational form. A critical point found in this way need not be a local minimum; its type requires a separate check.

The gradient and constant Hessian matrix areAt ${\mathbf{x}}_0=(1,0{)}^T$, $\nabla F=(10,-8{)}^T$ and $H_F^{-1}\nabla F=(1,-1{)}^T$. Hence one multivariable Newton iteration givesAt this point the gradient vanishes, so every subsequent iterate is $(0,1)$. The one-step result follows because the gradient of a quadratic polynomial is affine and its linearization is exact. Since the leading principal minors of $H_F$ are $6>0$ and $8>0$, it is a positive-definite matrix. Alternatively,directly proves that $(0,1)$ is the unique global minimum, with value $-1$.