Newton's Method

Newton's method for systems of equations

Overview

The multivariable Newton's method is an iterative algorithm for finding the roots of a system of nonlinear equations, denoted as $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}$. It extends the concept of the derivative (slope of the tangent line) in one dimension to the "Jacobian matrix" in multiple dimensions, enabling the solution of complex nonlinear problems.

Update Formula:

\[ \boldsymbol{x}_{k+1} = \boldsymbol{x}_k - \boldsymbol{J}(\boldsymbol{x}_k)^{-1} \boldsymbol{f}(\boldsymbol{x}_k) \]

*In practice, the correction $\Delta \boldsymbol{x}$ is obtained by solving the linear system $\boldsymbol{J}(\boldsymbol{x}_k) \Delta \boldsymbol{x} = -\boldsymbol{f}(\boldsymbol{x}_k)$ instead of computing the inverse matrix directly.

The Jacobian Matrix

The Jacobian matrix $\boldsymbol{J}$ plays the most crucial role in the multivariable Newton's method. Composed of partial derivatives of each function with respect to each variable, it represents the multidimensional gradient (slope) at the current point.

\[ \boldsymbol{J}(\boldsymbol{x}) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix} \]

Algorithm Steps

Set the initial guess vector $\boldsymbol{x}_0$.
At current point $\boldsymbol{x}_k$, calculate function vector $\boldsymbol{f}(\boldsymbol{x}_k)$ and Jacobian matrix $\boldsymbol{J}(\boldsymbol{x}_k)$.
Solve the linear system $\boldsymbol{J}(\boldsymbol{x}_k) \Delta \boldsymbol{x} = -\boldsymbol{f}(\boldsymbol{x}_k)$ to find the correction $\Delta \boldsymbol{x}$.
Update the values: $\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \Delta \boldsymbol{x}$.
Repeat until $\|\Delta \boldsymbol{x}\|$ falls within the tolerance.

Connection to SPICE

In the SPICE-oriented approach, each element of the Jacobian matrix corresponds to the "equivalent conductance" in a circuit. SPICE simulators utilize this iterative process internally to efficiently determine the operating points of complex nonlinear circuits.

Calculation Example (2 Variables)

Consider the process of solving the following simple system of two nonlinear equations:

\[ \begin{cases} f_1(x_1, x_2) = x_1^2 + x_2^2 - 1 = 0 \\ f_2(x_1, x_2) = x_1 - x_2 = 0 \end{cases} \]

(This is equivalent to finding the intersections of a unit circle and the line $x_1 = x_2$)

1. Deriving the Jacobian Matrix

Differentiating each function with respect to each variable:

\[ \boldsymbol{J}(x_1, x_2) = \begin{bmatrix} 2x_1 & 2x_2 \\ 1 & -1 \end{bmatrix} \]

2. Iteration (1st Step)

Assuming an initial guess of $\boldsymbol{x}_0 = [1, 0]^T$:

Step A: Compute function values and Jacobian
$\boldsymbol{f}(1, 0) = [1^2 + 0^2 - 1, 1 - 0]^T = [0, 1]^T$
$\boldsymbol{J}(1, 0) = \begin{bmatrix} 2(1) & 2(0) \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 1 & -1 \end{bmatrix}$
Step B: Calculate correction $\Delta \boldsymbol{x}$
Solving the linear system $\begin{bmatrix} 2 & 0 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} \Delta x_1 \\ \Delta x_2 \end{bmatrix} = - \begin{bmatrix} 0 \\ 1 \end{bmatrix}$:
$2\Delta x_1 = 0 \Rightarrow \Delta x_1 = 0$
$1(0) - \Delta x_2 = -1 \Rightarrow \Delta x_2 = 1$
Step C: Update the values
$\boldsymbol{x}_1 = \boldsymbol{x}_0 + \Delta \boldsymbol{x} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

By repeatedly calculating the correction vector $\Delta \boldsymbol{x}$ in multidimensional space, the solution converges to the true root (in this case, $[1/\sqrt{2}, 1/\sqrt{2}]^T$).

Considerations

In multivariable problems, the calculation may fail if the Jacobian matrix becomes singular (i.e., non-invertible). As the number of variables increases, computational costs rise significantly, making the choice of initial values and the exploitation of matrix sparsity critical.