ExerciseNonlinear systemsintermediate

Exercise: Newton for a system, by hand

Two Newton steps by hand on the system x2+y2=1x^2+y^2=1, x=yx=y: building the Jacobian, solving each step's 2×22\times2 linear system and visible quadratic convergence towards (2/2,2/2)(\sqrt2/2,\sqrt2/2).

Solution

ExampleIntersection of circle and bisector

Approximate with two Newton steps the positive solution of the system x2+y2=1x^2+y^2=1, x−y=0x-y=0, starting from x(0)=(1,1)x^{(0)}=(1,1). The exact solution is α=(22,22)=(0.7071068, 0.7071068)\alpha=\bigl(\frac{\sqrt2}{2},\frac{\sqrt2}{2}\bigr)=(0.7071068,\,0.7071068).

  1. Function and Jacobian:

    F(x,y)=[x2+y2−1x−y],F′(x,y)=[2x2y1−1]F(x,y)=\begin{bmatrix}x^2+y^2-1\\ x-y\end{bmatrix},\qquad F'(x,y)=\begin{bmatrix}2x & 2y\\ 1 & -1\end{bmatrix}

  2. First step: at (1,1)(1,1), F=(1,0)TF=(1,0)^T and the linear system F′u=FF'u=F is 2u1+2u2=12u_1+2u_2=1, u1−u2=0u_1-u_2=0, with solution u=(14,14)u=(\tfrac14,\tfrac14):

    x(1)=(1,1)−(14,14)=(0.75,  0.75)x^{(1)}=(1,1)-\bigl(\tfrac14,\tfrac14\bigr)=(0.75,\;0.75)

  3. Second step: at (0.75,0.75)(0.75,0.75), F=(0.125, 0)TF=(0.125,\,0)^T and the system is 1.5 u1+1.5 u2=0.1251.5\,u_1+1.5\,u_2=0.125, u1−u2=0u_1-u_2=0, that is, u=(124,124)u=(\tfrac{1}{24},\tfrac{1}{24}):

    x(2)=(0.75,  0.75)−(124,124)=(0.7083333,  0.7083333)x^{(2)}=(0.75,\;0.75)-\bigl(\tfrac{1}{24},\tfrac{1}{24}\bigr)=(0.7083333,\;0.7083333)

The errors are 0.293→0.043→0.00120.293\to 0.043\to 0.0012: each step roughly squares the error, the signature of quadratic convergence. A third step would give 0.70710780.7071078, with error 10−610^{-6}. (In this symmetric system the iteration reduces to scalar Newton for 2x2=12x^2=1.)