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?
Do I have the right idea about Homotopy or am I talking in gibberish?
Does Homotopy give all the roots?
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?
What is a good rule of thumb for choosing $G(x)$?
Is there other iterative methods out there that is better or more efficient than N-R or Homotopy?
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 deform 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 method 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 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(x_0)$ for any arbitrary value of $x_0$. In this case the homotopy $H(x,t)=F(x)+(t-1)F(x_0)$ 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 convergent) where for any arbitrary solution x0, we can get a solution. In N-R method, the initial solution have to be close to the desired solution to be convergent other wise will be divergent.