Computational Fluid Dynamics - Elementary (k)

Newton's Method (1-D, 2-D, and 3-D)

Newton's method is an algorithm to find roots of a function $f(\textbf{x})$ using its first terms of the Taylor's series. Such an expansion is provided in the neighborhood of the suspected root, whose position is updated in an iteration procedure. Newton's method is, in fact, a second order iteration method based on the linearisation of the function $f$ provided in the current approximation of the root ($\textbf{x}^{(i)} \sim \textbf{x}_0 : f(\textbf{x}_0) = 0 $).

In 1-D (see Fig. k.1) the method looks as follows:
\begin{equation} x^{(i+1)} = x^{(i)} - \frac{f(x^{(i)})}{f'(x^{(i)})} \end{equation}
Fig. k.1: 1-D Newton's method iteration (animation created by Ralf Pfeifer)

The method can however be unstable near a horizontal asymptote or a local extremum; so, a good initial guess for the iterative procedure is very important for the convergence of the iteration procedure.

In multidimensional domains the method can be used to find the roots of a system of functions $\textbf{f}(\textbf{x})$ and the first order derivative is substituted by the Jacobian matrix of the system. Therefore, the method looks as follows:
\begin{equation} \textbf{x}^{(i+1)} = \textbf{x}^{(i)} - \left[J\right]^{-1}_{\textbf{x}^{(i)}}\textbf{f}(\textbf{x}^{(i)}) \end{equation}
The relevant Matlab codes can be downloaded using the following link:
Matlab Codes Bank

No comments:

Post a Comment