next up previous
Next: About this document ... Up: Appendix Previous: Newton-Raphson Method (Uni-Variate)

Newton-Raphson Method (Multi-Variate)

The above method can be generalized to multi-variate case to solve n simultaneous algebraic equations

\begin{displaymath}\left\{ \begin{array}{c} f_1(x_1,\cdots,x_n)=f_1({\mathbf x})...
f_n(x_1,\cdots,x_n)=f_n({\mathbf x})=0 \end{array} \right. \end{displaymath}

where ${\mathbf x}=[x_1,\cdots,x_n]^T$ is an n-dimensional vector. This equation system can be more concisely represented in vector form as ${\mathbf f}({\mathbf x})=0$. The Newton-Raphson formula for multi-variate problem is

\begin{displaymath}{\mathbf x} \Leftarrow {\mathbf x}-J_f^{-1}({\mathbf x}) f({\mathbf x}) \end{displaymath}

where $J_f({\mathbf x})$ is the Jacobian of function ${\mathbf f}({\mathbf x})$:

\begin{displaymath}J_f( {\mathbf x})=\left[ \begin{array}{ccc}
\frac{\partial f...
...dots & \frac{\partial f_n}{\partial x_n}
\end{array} \right] \end{displaymath}

To derive this iteration, consider Taylor series

\begin{displaymath}f_i( {\mathbf x}+\delta {\mathbf x})=
f_i( {\mathbf x}) +\su...
... \delta x_j
+O(\delta {\mathbf x}^2)\;\;\;\;\;(i=1,\cdots,n)

We ignore the terms of $\delta {\mathbf x}^2$ and higher and let $f_i( {\mathbf x}+\delta {\mathbf x})$ be zero (i.e., ${\mathbf x}+\delta {\mathbf x}$ is the zero-crossing of the tangent), and get

\begin{displaymath}\sum_j \frac{\partial f_i}{\partial x_j} \delta x_j=-f_i( {\mathbf x})
\;\;\;\;\;(i=1,\cdots,n) \end{displaymath}

Solving this linear equation system for $\delta x_j$, we get

\begin{displaymath}\delta {\mathbf x}=-J_f^{-1}({\mathbf x}) f({\mathbf x}) \end{displaymath}

and the Newton-Raphson formula:

\begin{displaymath}{\mathbf x} \Leftarrow {\mathbf x}+\delta {\mathbf x}=
{\mathbf x}-J_f^{-1}({\mathbf x}) f({\mathbf x}) \end{displaymath}

Ruye Wang 2014-09-18