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
- References:
- Re: Homotopic algorithm to solve a system of equations
- From: "aTn" <ayottes@dms.umontreal.ca>
- Re: Homotopic algorithm to solve a system of equations