FAQ: Homotopy continuation method

From: http://math.stackexchange.com/questions/127774/using-homotopy-to-solve-system-of-nonlinear-equations


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 solution 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 chosen the value of ∆t, you will get the good solution of the given system.

4. What is a good rule of thumb for choosing G(x) ? G(x) can be chosen 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 arbitrary 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 are better or more efficient than N-R or Homotopy? Until now, the homotopy methods can be considered as the best methods to solve nonlinear algebraic systems because they are global methods (always converge) where for any arbitrary solution x0, we can get a solution. In N-R method, the initial solution has to be close to the desired solution to be convergent otherwise will be divergent.


Published by

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s