Homotopy Continuation Method to Solve A System of Nonlinear Algebraic Equations
​Authors: Housam Binous and Ahmed Bellagi

FindRoot fails to give a correct solution to a system of nonlinear algebraic equations unless a good initial guess is chosen . Difficulty in finding a suitable initial guess is avoided by using homotopy continuation methods such as the fixed point and the Newton homotopy methods .
FindRoot fails to give correct solution unless a good initial guess is chosen. Difficulty in finding an initial guess is avoided by using homotopy continuation methods such as the fixed point and the Newton homotopy methods.
In[]:=
FindRoot[{x^2-xy1,Sqrt[x+1]+y0},{x,-0.1},{y,0.5}]
FindRoot
:Failed to converge to the requested accuracy or precision within 100 iterations.
Out[]=
{x-1.-0.0000512881,y4.30262×
-7
10
-0.000102576}
In[]:=
FindRoot[{x^2-xy1,Sqrt[x+1]+y0},{x,0.5},{y,-1}]
Out[]=
{x0.554958,y-1.24698}
Fixed Point Homotopy :
​H(x,t)=(1-t) (x-x0)+tf(x) with x0=(-0.1,0.5)
In[]:=
H[x_,y_,t_]:={(1-t)(x+0.1)+t(x^2-xy-1),​​(1-t)(y-0.5)+t(Sqrt[x+1]+y)}
In[]:=
H[x,y,t]
Out[]=
(1-t)(0.1+x)+t(-1+
2
x
-xy),(1-t)(-0.5+y)+t
1+x
+y
In[]:=
Off[General::"spell"]
In[]:=
MyGrad[fon_,var_List]:=D[fon,#]&/@var
In[]:=
J=MyGrad[H[x,y,t],{x,y,t}]
Out[]=
1-t+t(2x-y),
t
2
1+x
,{-tx,1},-1.1-x+
2
x
-xy,0.5+
1+x

In[]:=
Js=J/.xx[s]/.yy[s]/.tt[s]
Out[]=
1-t[s]+t[s](2x[s]-y[s]),
t[s]
2
1+x[s]
,{-t[s]x[s],1},-1.1-x[s]+
2
x[s]
-x[s]y[s],0.5+
1+x[s]

In[]:=
Eq[1]=D[x[s],{s,1}]Det[Drop[Js,1]]
Out[]=
′
x
[s]1.1+x[s]-0.5t[s]x[s]-
2
x[s]
-t[s]x[s]
1+x[s]
+x[s]y[s]
In[]:=
Eq[2]=D[y[s],{s,1}]-Det[Drop[Js,{2}]]
Out[]=
′
y
[s]-0.5+0.5t[s]-1.t[s]x[s]-
0.55t[s]
1+x[s]
-
t[s]x[s]
2
1+x[s]
+
t[s]
2
x[s]
2
1+x[s]
-
1+x[s]
+t[s]
1+x[s]
-2t[s]x[s]
1+x[s]
+0.5t[s]y[s]-
t[s]x[s]y[s]
2
1+x[s]
+t[s]
1+x[s]
y[s]
In[]:=
Eq[3]=D[t[s],{s,1}]Det[Drop[Js,{3}]]
Out[]=
′
t
[s]1-t[s]+2t[s]x[s]+
2
t[s]
x[s]
2
1+x[s]
-t[s]y[s]
In[]:=
sol=NDSolve[{Eq[1],Eq[2],Eq[3],t[0]0,x[0]-0.1,y[0]0.5},{x[s],y[s],t[s]},{s,0,0.9}]
Out[]=
x[s]InterpolatingFunction
Domain: {{0.,0.9}}
Output: scalar
[s],y[s]InterpolatingFunction
Domain: {{0.,0.9}}
Output: scalar
[s],t[s]InterpolatingFunction
Domain: {{0.,0.9}}
Output: scalar
[s]
In[]:=
Plot[Evaluate[t[s]/.sol],{s,0,0.9}]
Out[]=
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
1.0
1.2
In[]:=
sol1=FindRoot[(t[s]/.sol/.sa)1,{a,0.9}]
Out[]=
{a0.823182}
Fixed Point Homotopy and FindRoot give same result
In[]:=
{Evaluate[x[s]/.sol/.sa/.sol1],Evaluate[y[s]/.sol/.sa/.sol1]}
Out[]=
{{0.554958},{-1.24698}}
In[]:=
FindRoot[{x^2-xy1,Sqrt[x+1]+y0},{x,0.5},{y,-1}]
Out[]=
{x0.554958,y-1.24698}
Newton Homotopy :​
​H(x,t)= f(x) - (1-t) f(x0) with x0=(-0.1,0.5)
In[]:=
{x^2-xy-1,Sqrt[x+1]+y}/.x-0.1/.y0.5
Out[]=
{-0.94,1.44868}
In[]:=
H[x_,y_,t_]:={-(1-t)(-0.94)+(x^2-xy-1),​​-(1-t)(1.4486832980505138)+(Sqrt[x+1]+y)}
In[]:=
J=MyGrad[H[x,y,t],{x,y,t}]
Out[]=
2x-y,
1
2
1+x
,{-x,1},{-0.94,1.44868}
In[]:=
Js=J/.xx[s]/.yy[s]/.tt[s]
Out[]=
2x[s]-y[s],
1
2
1+x[s]
,{-x[s],1},{-0.94,1.44868}
In[]:=
Eq[1]=D[x[s],{s,1}]Det[Drop[Js,1]]
Out[]=
′
x
[s]0.94-1.44868x[s]
In[]:=
Eq[2]=D[y[s],{s,1}]-Det[Drop[Js,{2}]]
Out[]=
′
y
[s]-2.89737x[s]-
0.47
1+x[s]
+1.44868y[s]
In[]:=
Eq[3]=D[t[s],{s,1}]Det[Drop[Js,{3}]]
Out[]=
′
t
[s]2x[s]+
x[s]
2
1+x[s]
-y[s]
In[]:=
sol=NDSolve[{Eq[1],Eq[2],Eq[3],t[0]0,x[0]-0.1,y[0]0.5},{x[s],y[s],t[s]},{s,0,4}]
Out[]=
x[s]InterpolatingFunction
Domain: {{0.,4.}}
Output: scalar
[s],y[s]InterpolatingFunction
Domain: {{0.,4.}}
Output: scalar
[s],t[s]InterpolatingFunction
Domain: {{0.,4.}}
Output: scalar
[s]
In[]:=
Plot[Evaluate[t[s]/.sol],{s,0,2.5}]
Out[]=
0.5
1.0
1.5
2.0
2.5
2
4
6
8
In[]:=
sol1=FindRoot[(t[s]/.sol/.sa)1,{a,2}]
Out[]=
{a1.4332}
Newton Homotopy and FindRoot give same result
In[]:=
{Evaluate[x[s]/.sol/.sa/.sol1],Evaluate[y[s]/.sol/.sa/.sol1]}
Out[]=
{{0.554958},{-1.24698}}
In[]:=
FindRoot[{x^2-xy1,Sqrt[x+1]+y0},{x,0.5},{y,-1}]
Out[]=
{x0.554958,y-1.24698}
Reference : B . G . Higgins and H . Binous, A Simple Method for Tracking Turning Points in Parameter Space, Journal of Chemical Engineering of Japan, Vol . 43, No . 12, pp . 1035–1042, 2010.