Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I'm trying to solve the following system of equations for the variables $P,x_1$ and $x_2$ (all else are constants):

$$\frac{A(1-P)}{2}-k_1x_1=0 \\ \frac{AP}{2}-k_2x_2=0 \\ \frac{(1-P)(r_1+x_1)^4}{L_1}-\frac{P(r_1+x_2)^4}{L_2}=0$$

I can see that I can turn this system of equations into a single equation of a single variable $(P)$ by solving equations 1 and 2 for $x_1$ and $x_2$ respectively and substituting them into equation 3. In doing so, I am able to use matlab's fzero command to find the solution. Using the parameters $k_1=k_2=1$, $r_1=r_2=0.2$, and $A=2$, I found the true solution to be $P=x_1=x_2=0.5$.

However, when I use newton's method applied to the original 3 variate - 3 equation system, the iterations never converge to the solution, no matter how close I begin to the true solution $x^*=(P^*,x_1^*,x_2^*)=(0.5,0.5,0.5)$.

At first, I suspected my a bug in my implementation of newton's method. After checking several times, I found no bug. Then I tried using an initial guess $x_0=x^*$, and lo & behold: the Jacobian is singular. I know that a singular jacobian can reduce the order of convergence, but I don't think it necessarily prevents convergence to the true solution.

So, my question is, Given that the jacobian of the system at the true solution is singular:

  1. What other conditions are necessary to prove that newton's method will not converge to the root?

  2. Would a globalization strategy (e.g. line-search) guarantee convergence despite the singular jacobian?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

(1): This depends on the behavior of derivatives of the Jacobian (sic!) in the null space of the Jacobian at the solution. In practice, nobody calculates these derivatives, and i didn't even bother to remember the precise conditions.

(2) works, though convergence is only linear.

To get superlinear convergence (at least in the majority of cases), one may use tensor methods. See, e.g.,
https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/SAND2004-1944.pdf
http://www.jstor.org/stable/10.2307/2156931
http://www.springerlink.com/index/X5G827367G548327.pdf

share|improve this answer
add comment

Instead of a line-search you could try modifying your Newton's method to the Levenberg-Marquardt algorithm. The implementation is simple enough if you're using Matlab.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.