Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So far I have been using Newton-Raphson (N-R) to solve nonlinear systems. However N-R might run into the problem of singularity depending on the initial guess.

I found an alternate approach which is Homotopy. From what I have found on the internet, $$H(x,t) = tF(x) + (1-t)G(x),$$ where $F(x)$ is the original system and $G(x)$ is the auxiliary function.

First, starts off by solving $G(x),$ something that is either known or easy to solve. Then vary the variable $t$ from $0$ to $1,$ and then eventually it will take you to $F(x).$ But there are so many types of Homotopy, i.e., Homotopy Continuation, Newton Homotopy, Fixed-Point Homotopy etc. Frankly, I'm confused and I'm not a mathematician, and I tried to understand what they are by reading math papers, they gave me headaches. Does anyone know enough about Homotopy that can answer a couple of quesitons I have?

  1. Do I have the right idea about Homotopy or am I talking in gibberish?

  2. Does Homotopy give all the roots?

  3. If so, when I plug in some value of $x,$ does $H(x,t)$ give the closest root or some random roots like N-R?

  4. What is a good rule of thumb for choosing $G(x)$?

  5. Is there other iterative methods out there that is better or more efficient than N-R or Homotopy?

share|improve this question
    
Just as an aside, there's a whole theory of convex optimization to consider. You can use interior point methods, semi-Newton methods, gradient methods, or even basic line search methods to find roots. I'm not suggesting that your interest in homotopy methods is bad, but you'll probably be much better served by considering the half-century old ideas on root-finding with linear algebra before going off to homotopy. –  EMS Apr 3 '12 at 22:25
    
Thanks EMS, I will look them up. I don't know much about solving nonlinear system other than using N-R, gauss-seidel and fixed-point iterative method. And as far as I know, N-R is the "best". –  Jackie Apr 3 '12 at 22:56

1 Answer 1

1. Do I have the right idea about Homotopy or am I talking in gibberish? Homotopy methods are good numerical methods which can be used to solve nonlinear systems (Algebraic or differential) of equations. The idea is to defort the given system f(x)=0 to be another system H(x,t)=tf(x)+(1-t)g(x) where g(x) has a known solution and t is a parameter in the closed interval [0, 1]. This new system is called homotopy or deformation of f(x). Here f(x) and g(x) are called homotopic because H(x,0)=g(x) and H(x,1)=f(x). Starting from the known slution of g(x)=0 at t=0, we can trace the zero curve (path) until t=1 where the answer is x* is the desired solution.

2. Does Homotopy give all the roots? Homotopy methods will give different roots based on the selection of the initial solution (the solution of G(x)=0 at t=0). One root will be obtained for each initial solution.

3. If so, when I plug in some value of x, does H(x,t) give the closest root or some random roots like N-R? The closet root can be obtained depends on the smoothness of the path. I mean as small as you choosed the value of ∆t, you will get good solution of the given system.

4. What is a good rule of thumb for choosing G(x) ? G(x) can be choosed by for any formula with condition G(x) can be easily solved to get the initial solution. For example, you can choose G(x)=F(x)-F(x0) for any arbitray value of x0. In this case the homotopy H(x,t)=F(x)+(t-1)F(x0) is called Newton homotopy. Also, you can put G(x)=x-x0 and the obtained homotopy in this case is called fixed point homotopy. I created my own homotopies like constant homotopy and identity homotopy and I found that the are work to find a good solution for the given system.

5. Is there other iterative methods out there that is better or more efficient than N-R or Homotopy? Until now, the homotopy methods methods can be considered as the best methods to solve nonlinear algebraic systems because they are global methods (always convergen) where for any arbitrary solution x0, we can get a solution. In N-R method, the initial solution have to be close to the deired solution to be convergent other wise will be divergent.

share|improve this answer
    
I didn't know about Homotopy solver. But suppose $F(x) = (x-1)^2$, $G(x) = x$. Than for $t\in (0.2,1)$ $H(x,t)$ does not have a solution. Doesn't it cause troubles? –  tom Jun 7 '13 at 11:13
    
My idea is to define $H$ as $H(x,t) = (tF(x) + (1-t)G(x))^2$ and while moving $t$ staying with $x(t)$ in the valley(local minima). But still I can find example for which it might fail. Take $F(x) = 5 ((x - 1)^2 - 2 (x - 1)^4 + 1.1 (x - 1)^6) - 0.1$ and $G(x) = x$. –  tom Jun 7 '13 at 11:30

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.