0
$\begingroup$

I've recently had occasion (providing an engineering colleague with a little mathematical help) to solve a non linear system

$\begin{align*}f(x,y)&=0,\\ g(x,y)&=0.\end{align*}$

If derivatives of $f$ and $g$ were available, I could use Newton's method

$\mathbf{x}_{n+1}=\mathbf{x}_n-J_n^{-1}\mathbf{x}_n$

where $J$ is of course the Jacobian

$\displaystyle{\frac{\partial(f,g)}{\partial(x,y)}}$.

Since the functions are too complicated to be easily differentiated (computing each of $f$ and $f$ requires multiple steps), my next approach would be to use a secant method: something like Broyden's method.

However, given that this is only a 2D system, I wonder what is wrong with using a Newton-type iteration where the partial derivatives in the Jacobian are approximated by finite differences, so that, for example:

$\displaystyle{\frac{\partial f}{\partial x}\approx \frac{f(x_n,y_n)-f(x_{n-1},y_n)}{x_n-x_{n-1}}}$.

Broyden's formula aims to simplify the updating of the Jacobian approximation each step, and chooses that approximation to be a matrix $J_n$ for which

$J_n(\mathbf{x}_n-\mathbf{x}_{n-1})=\mathbf{F}(\mathbf{x}_n)-\mathbf{F}(\mathbf{x}_{n-1})$.

The use of finite differences provides a Jacobian approximation which doesn't satisfy any nice properties, but on the other hand it is very easy to implement (only a few lines of code), and seems to be quite fast. And for a 2D system I would guess it to be reasonably efficient.

My question is: is there any good reason for using Broyden's method for a 2D system, over the simpler finite-difference method? (Which, if it has a formal name, I don't know it). I'm not a numerical analyst (my knowledge is limited to the simple methods I've taught as part of elementary numerical methods courses), so if anybody can offer some expert opinions, I'll be glad to hear them.

$\endgroup$
  • $\begingroup$ Not an expert, but I think your only danger is that the difference type Jacobian may not well approximate the real thing; or that the errors may add up and overwhelm the computation. Especially if your functions are not linear. I don't know Broyden's method, but it may have the advantage of being known to converge and keep the errors down. Also, could you simplify the equations? Are there terms that don't contribute much? $\endgroup$ – Betty Mock Dec 3 '13 at 4:33
  • $\begingroup$ Getting finite difference approximations to work is tricky. If the step is too large, the secant is a poor approximation of the tangent. If the step is too small, you get disastrous subtractive cancellation. Personally, I generally just turn to the Numerical Recipes book. The experts often criticize it, but it seems to work for me, typically. $\endgroup$ – bubba Dec 3 '13 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.