Multivariate Root Finding

Multivariate Root Finding#

Imagine a vector function,

\begin{array}{r} f (x) = (\begin{array}{c} f_{1} (x) \\ f_{2} (x) \\ ⋮ \\ f_{N} (x) \end{array}) \end{array}

where

\begin{array}{r} x = (\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{N} \end{array}) \end{array}

We want to find the $x$ that zeros $f (x)$ , i.e.,

f (x) = 0

We’ll use a generalization of Newton’s method to systems of equations.

Solution procedure#

Note

This is the simplest case of a multivariable root finding algorithm. More sophisticated methods exist, but this method will give you a feel for what is involve

Start with an initial guess, $x^{(0)}$

Taylor expand our function seeking a correction $δ x$ . Each component has the form:

f_{i} (x^{(0)} + δ x) \approx 0 = f_{i} (x^{(0)}) + \sum_{j = 1}^{N} \frac{\partial f_{i}}{\partial x_{j}} δ x_{j} + \dots

and we can write the vector form as:

f (x^{(0)} + δ x) = f (x^{(0)}) + J δ x + \dots \approx 0

where $J$ is the Jacobian:

\begin{array}{r} J = (\begin{array}{cccc} \frac{\partial f_{1}}{\partial x_{1}} & \frac{\partial f_{1}}{\partial x_{2}} & \dots & \frac{\partial f_{1}}{\partial x_{N}} \\ \frac{\partial f_{2}}{\partial x_{1}} & \frac{\partial f_{2}}{\partial x_{2}} & \dots & \frac{\partial f_{2}}{\partial x_{N}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{\partial f_{N}}{\partial x_{1}} & \frac{\partial f_{N}}{\partial x_{2}} & \dots & \frac{\partial f_{N}}{\partial x_{N}} \end{array}) \end{array}

This can be expresses as the linear system:

J δ x = - f (x^{(0)})

Our solution procedure is iterative:

Iterate over $k$ , seeking a new guess at the solution $x^{k + 1}$ :
- Solve the linear system:
  
  $J δ x = - f (x^{(k)})$
- Correct our initial guess:
  
  $x^{(k + 1)} = x^{(k)} + δ x$
- Stop iteration if
  
  $‖ δ x ‖ < ϵ ‖ x^{(k)} ‖$
  
  where $‖ \cdot ‖$ is a suitable vector norm.

Multivariate Root Finding

Contents

Multivariate Root Finding#

Solution procedure#