A New Continuation Method For Tracing Solution Curves Of Parameterized Equations

In many fields, we often need to solve systems of nonlinear equations. Sometimes, there are some parameters in the system and, sometimes, although the original problem doas not include any parameter, to construct a globally convergent solution method (e.g., homotopy method), one often introduce a parameter into the system that it becomes a parametrized problem.Consider the following parameterized systems of nonlinear equations:when m> 1, (1) is a problem with multi-parameter which is difficult to treat and is often transformed into a problem with single parameter by restricting the variation of the parameter vector t. In this paper, we consider only the case that m = 1, that is, a system of nonlinear equations with single parameter. Assume that in the region considered, the solution set of (1) consists of some smooth curves. Our task is, tracing a curve among them from a given point on it to a target point. This is a basic and important problem in solving parameterized equations. It is significant to design robust and efficient continuation method to numerically tracing the solution curve of parameterized equations.In this paper, continuation methods for numerically tracing solution curves of parameterized equations are discussed. A survey of commonly used continuation methods is made, and then a new continuation method—Euler Predictor-Sphere Corrector method is presented. In contrast with commonly used continuation method, the new method is more robust and is suitable to apply to the case that solution curves are closed to each other or the case that the curve turns acutely at some point.At first, we list three commonly used continuation methods as follows, they adoptthe same predictor step—Euler predictor step:(x, t)fc+1 = (x, t)k + hM(x,i)k (2)where, (x,i)k is the value of (x, i) at (x,t)k, and use different corrector surface. For simplicity, without lass of generality, we set k = 0 in (2) from now on.1. Correcting on the hyperplane t = t\ [4]:The corrector procedure is the procedure for solving the system:FCM)-0. p)- . n — \je.g. Newton procedure\=\X% I -I F'(x''U) Ft{p: 'U) 1 F{-X A) 1,1 = 1,2, ■■? ti+1 ] \ U j \ 0 1 ) \ U-ti j(4)2. Correcting on the hyperplane that pass the predictor point and is vertical to the predictor direction [3]:The corrector procedure is the procedure for solving the system:e.g. Newton procedure3. Take the point on the curve that is nearest to the predictor point as the corrector point (generalized Newton method[5]):Aim at solving the minimizing problemmm{||(x,t)-(x?,<1)!ll^,<)=0} (7)one obtain the generalized Newton method: VUWU) (8)uThe first method can only applied to the case that the curve is monotone about t. All these methods have the problem that they are not robust and "jumping" often happens, in the case that the solution curves are closed to each other or the curve turns acutely at some point. In such cases, to make the tracing procedure success, we have to choose steplength very small, and thus make the procedure inefficient. 4. Euler Predictor-Sphere Corrector methodIn this paper, a robust continuation method—Euler Predictor-Sphere Corrector method is presented. Its corrector procedure is the procedure for solving the system:F(x,t)=0,/.. o \ (9)jyX,Z) — jt I ||^E, I) — {X,l)o — 2re.g. Newton procedure:On its convergence, we have the following resultsLet u(s) = (x(s), t(s)) be the parameterized presentation of the solution curve, and uq = (x(°\to) 6 F~x(0) is a given start point on it.Lemma 4.1 Let F : H?+1 —> F?is a smooth map, 0 is its regular value, and u0 € F-^O). There exists a /Vax > 0, such that for any h G (0,/i,nax], the following results hold:(1) Besides uq, the expanded systemwhere f(u) = ￡(||-u — Vq — |/k1|2 — (\h)2), has only one solution u 6 F~1(Q), or, in other words, the sphere that passes the start point uq and the predictor point v = i/0+h? (where <; is the Eider predictor direction) with the diameter h (the step size) intersects with the solution curves F'1^) at only uq and u>.(2) The Jacobian of M{u) at the point u is nonsingvlar, that is Af^u;)"1 exists.We call hraax in Lemma 4.1 as the granularity of the solution curves.Definition 4.1 Vz G ^(O), let Bk{x) intersect* with F~l(0) at only two points, where Bh(x) is the sphere that passes x and takes the tangent direction of the curve at x and length h as its diameterLet F C F~1(0) be a solution curve of F(x) = 0, we callas the granularity ofT.Theorem 4.3 (convergence theorem) Let F : Rn+l —> B? be a smooth map having zero as a regular value and u0 € F~1(Q). 3/imax > 0. Denote by ch(s) the polygonal path, starting at u0 € F-1(0), going through all points u generated by the algorithm 4-1- Denote by c(s) the corresponding curve in F~x(0) given by initial valueproblem < For definiteness, we assume that Cfc(0) = e(0) = uq. and that{ ?(0) = u0both curves are parametrized with respect to arclength. Then, for a given maximal ar-clength Smax,, and for given constants C,e > 0 as in the algorithm, there exist constants Co,7i, 72 > 0 such that(1) \\F(u)\\ < 2eh2 for all nodes u ofch(s);(2) \\F{ck(s))\\ < (3e + \^)h\ forOw(3) \\ch(s) - c{s)\\ < CQh2, forO theoretically, the expanded system M(u) = 0 has only one solution, besides u0- Numerically, we can find such a point by Newton iteration with line search.