DerivationNonlinear systemsintermediate

Derivation: Newton for systems by linearization

The first-order multivariate Taylor expansion linearizes F around the current iterate; setting that linearization to zero gives the Newton step, with the Jacobian in the role of the derivative.

Linearize and set to zero

  1. The Jacobian matrix collects all first partial derivatives of the coordinate functions:

    F′(X)=[∂f1∂x1⋯∂f1∂xn⋮⋮∂fn∂x1⋯∂fn∂xn]F'(X)=\begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_n}\\ \vdots & & \vdots\\ \frac{\partial f_n}{\partial x_1} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix}

  2. The first-order multivariate Taylor expansion around the current iterate x(k)x^{(k)} is the vector version of the tangent line in the scalar derivation:

    F(X)≈F(x(k))+F′(x(k))(X−x(k))F(X)\approx F\bigl(x^{(k)}\bigr)+F'\bigl(x^{(k)}\bigr)\bigl(X-x^{(k)}\bigr)

  3. We seek the point that makes this linear approximation vanish (the analogue of the tangent crossing the axis). Setting it to zero and solving, with the Jacobian inverse instead of the quotient:

    x(k+1)=x(k)−[F′(x(k))]−1F(x(k))x^{(k+1)}=x^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F\bigl(x^{(k)}\bigr)

Example: building F and its Jacobian

ExampleA 2×2 system

Write the system exey+xcos⁡y=0e^xe^y+x\cos y=0, x+y=1x+y=1 in the form F(X)=0F(X)=0, and compute its Jacobian matrix.

  1. Move everything to the left-hand side:

    F(X)=[exey+xcos⁡yx+y−1]=[00]F(X)=\begin{bmatrix} e^xe^y+x\cos y\\ x+y-1 \end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}

  2. Differentiating each component with respect to each variable:

    F′(X)=[exey+cos⁡yexey−xsin⁡y11]F'(X)=\begin{bmatrix} e^xe^y+\cos y & e^xe^y-x\sin y\\ 1 & 1 \end{bmatrix}

This system is solved with Newton in the solved exercise. Note that on the constraint x+y=1x+y=1 one has exey=ex+y=ee^xe^y=e^{x+y}=e: at the solution, xcos⁡(1−x)=−ex\cos(1-x)=-e.