[Date Index]
[Thread Index]
[Author Index]
Re: Homotopic algorithm to solve a system of equations
*To*: mathgroup at smc.vnet.net
*Subject*: [mg66930] Re: Homotopic algorithm to solve a system of equations
*From*: "aTn" <ayottes at dms.umontreal.ca>
*Date*: Sun, 4 Jun 2006 01:10:25 -0400 (EDT)
*References*: <e5mhml$kjl$1@smc.vnet.net><200606020809.EAA18052@smc.vnet.net> <e5resj$h3k$1@smc.vnet.net>
*Sender*: owner-wri-mathgroup at wolfram.com
I think you got the idea right, but I would NOT use differential
equations (read the post above yours carefully; you can also check out
the tutorial by Watson, its available on the net for you to download).
The idea is to 'deform' (precisely, to do a homotopy) of a 'simple' set
of equations to which you know the solution into the system of
equations you want to solve. The deformation creates a 'path' of
systems of equations starting from the simple problem g: R^n-->R^n (to
which you know a solution x0) and ending at the hard problem
f:R^n--->R^n. Say the system of equations at time ' t ' is noted f_t (
t goes from 0 to 1). We have f_0 = g and f_1 = f.
The procedure you use is iterative. The idea is to start at time 0 and
increment ' t ' by a small value epsilon. More precisely, say at time '
t ' you know the solution to f_t (x) = 0 (lets note that solution as
xt). You use xt as an initial point for the Newton method to solve the
problem f_(t + epsilon) (x) = 0. You go from t = 0 to t = 1 and find a
solution to you problem f(x) = 0.
Some problems may arise. To work, the Newton algorithm requires that
the differential of f_t be non-singular for all t (in other words, the
determinant of the jacobian of f_t is non-zero for all t). Sards
theorem (see my post above) insures us that there exists a path going
from f_0 to f_1 for which f_t has a non-singular differential at all
times t.
Hope this clarifies the idea.
Etienne
Prev by Date:
**Re: Simplifying algebraic expressions**
Next by Date:
**Re: Colored Tick Labels?**
Previous by thread:
**Re: Homotopic algorithm to solve a system of equations**
Next by thread:
**Re: Closed Form solution too much to hope for?**
| |