Robust continuation methods for tracing solution curves of parameterized systems (Q457042): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(8 intermediate revisions by 6 users not shown) | |||
Property / author | |||
Property / author: Yan Yu / rank | |||
Property / author | |||
Property / author: Yan Yu / rank | |||
Normal rank | |||
Property / review text | |||
Let \[ F(x,t)=0,\,\, x\in \mathbb {R}^n,\,\, t \in \mathbb {R}, \] be a parameterized system of nonlinear equations. Assume \(F: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^n\) is smooth, there is a point \(u_0 \in \mathbb{R}^{n+1}\) such that \(F(u_0) = 0\), and the Jacobian matrix \(F'(u_0)\) has maximum rank. Then the solution set of \(F\) contains a smooth curve \(c(s)\), \(s\) the arclength, with \(c(0) = u_0\), and there exists an open interval \(I\) such that for all \(\alpha \in I\), \(c'(\alpha) \neq 0\), and \(\mathrm{rank}(F'(c(\alpha))) = n\). Homotopy continuation, or curve tracing, consists of the iteration of two steps: predicting and correcting. In this paper, the predictor strategy known as the Euler predictor is used, and various corrector strategies are studied. Two corrector strategies often employed are: 1) the plane corrector, which finds the point \(u_{k+1}\) at the intersection of the curve with the hyperplane perpendicular to the tangent of the curve at the point \(u_{k}\) and containing the predicted point \(v_{k+1}\) and 2) the nearest point corrector, which finds the point \(u_{k+1}\) on the curve nearest to the predicted point \(v_{k+1}\). While these methods work well in general if the solution curves are close to each other, or the curve turns sharply at some point, ``curve jumping'' can occur. This forces the predictor steplength to be very small, reducing the overall efficiency of the algorithm. The authors present a new ``sphere corrector'' strategy. The method finds the point \(u_{k+1}\) which is the intersection of the curve, and the sphere whose diameter is the straight line segment joining the points \(u_{k}\) and the predicted point \(v_{k+1}\). This intersection is found using Netwon's method, or variants thereof, and the steplength must be adjusted to make the sphere intersect \(c(s)\) at only the two points \(u_{k}\) and \(u_{k+1}\). The authors prove that the method approximates a solution curve if the steplength is small enough. Further, the steplength is adapted (increased or decreased as necessary) throughout the algorithm using the convergence (or lack thereof) of the iterative method used to find the intersection. The authors suggest using Newton's method, Newton's method with ``line search'' step control or Netwon's method with ``trust region'' step control to solve the nonlinear system generated by the corrector step. The paper concludes with a comparison of the three corrector methods on systems of two concentric circles with various radii. The results illustrate that the sphere corrector method is more robust and efficient than the other two. | |||
Property / review text: Let \[ F(x,t)=0,\,\, x\in \mathbb {R}^n,\,\, t \in \mathbb {R}, \] be a parameterized system of nonlinear equations. Assume \(F: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^n\) is smooth, there is a point \(u_0 \in \mathbb{R}^{n+1}\) such that \(F(u_0) = 0\), and the Jacobian matrix \(F'(u_0)\) has maximum rank. Then the solution set of \(F\) contains a smooth curve \(c(s)\), \(s\) the arclength, with \(c(0) = u_0\), and there exists an open interval \(I\) such that for all \(\alpha \in I\), \(c'(\alpha) \neq 0\), and \(\mathrm{rank}(F'(c(\alpha))) = n\). Homotopy continuation, or curve tracing, consists of the iteration of two steps: predicting and correcting. In this paper, the predictor strategy known as the Euler predictor is used, and various corrector strategies are studied. Two corrector strategies often employed are: 1) the plane corrector, which finds the point \(u_{k+1}\) at the intersection of the curve with the hyperplane perpendicular to the tangent of the curve at the point \(u_{k}\) and containing the predicted point \(v_{k+1}\) and 2) the nearest point corrector, which finds the point \(u_{k+1}\) on the curve nearest to the predicted point \(v_{k+1}\). While these methods work well in general if the solution curves are close to each other, or the curve turns sharply at some point, ``curve jumping'' can occur. This forces the predictor steplength to be very small, reducing the overall efficiency of the algorithm. The authors present a new ``sphere corrector'' strategy. The method finds the point \(u_{k+1}\) which is the intersection of the curve, and the sphere whose diameter is the straight line segment joining the points \(u_{k}\) and the predicted point \(v_{k+1}\). This intersection is found using Netwon's method, or variants thereof, and the steplength must be adjusted to make the sphere intersect \(c(s)\) at only the two points \(u_{k}\) and \(u_{k+1}\). The authors prove that the method approximates a solution curve if the steplength is small enough. Further, the steplength is adapted (increased or decreased as necessary) throughout the algorithm using the convergence (or lack thereof) of the iterative method used to find the intersection. The authors suggest using Newton's method, Newton's method with ``line search'' step control or Netwon's method with ``trust region'' step control to solve the nonlinear system generated by the corrector step. The paper concludes with a comparison of the three corrector methods on systems of two concentric circles with various radii. The results illustrate that the sphere corrector method is more robust and efficient than the other two. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65H10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65H20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6348385 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
parameterized system of nonlinear equations | |||
Property / zbMATH Keywords: parameterized system of nonlinear equations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
continuation method | |||
Property / zbMATH Keywords: continuation method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
homotopy method | |||
Property / zbMATH Keywords: homotopy method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Newton's method | |||
Property / zbMATH Keywords: Newton's method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
curve jumping | |||
Property / zbMATH Keywords: curve jumping / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Euler predictor | |||
Property / zbMATH Keywords: Euler predictor / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Taylor polynomial predictor | |||
Property / zbMATH Keywords: Taylor polynomial predictor / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Alyson A. Reeves / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: SQPlab / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: PLCP / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s11075-013-9716-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079665769 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3898785 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Estimates for piecewise linear approximations of implicitly defined manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3998344 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Introduction to Numerical Continuation Methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numerical optimization. Theoretical and practical aspects. Transl. from the French / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A numerical continuation method based on Padé approximants / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Tracing an Implicitly Defined Curve by Quasi-Newton Steps and Calculating Bifurcation by Local Perturbations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new steplength control for continuation with the asymptotic numerical method / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A continuation method based on a high order predictor and an adaptive steplength control / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polyhedral end games for polynomial continuation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numerical continuation methods for dynamical systems. Path following and boundary value problems. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: High-order predictor-corrector algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Polynomial Predictor-Corrector Trust-Region Algorithm for Linear Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Newton's method with deflation for isolated singularities of polynomial systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Variable Order Adams-Bashforth Predictors with an Error-Stepsize Control for Continuation Methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numerical differentiation of implicitly defined space curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A power series method for computing singular solutions to nonlinear analytic systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5491447 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Mehrotra-Type Predictor-Corrector Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mehrotra-type predictor-corrector algorithm revisited / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Higher Order Predictors and Adaptive Steplength Control in Path Following Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Superlinear Convergence of an Infeasible Predictor-Corrector Path-Following Interior Point Algorithm for a Semidefinite Linear Complementarity Problem Using the Helmberg–Kojima–Monteiro Direction / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:50, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Robust continuation methods for tracing solution curves of parameterized systems |
scientific article |
Statements
Robust continuation methods for tracing solution curves of parameterized systems (English)
0 references
26 September 2014
0 references
Let \[ F(x,t)=0,\,\, x\in \mathbb {R}^n,\,\, t \in \mathbb {R}, \] be a parameterized system of nonlinear equations. Assume \(F: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^n\) is smooth, there is a point \(u_0 \in \mathbb{R}^{n+1}\) such that \(F(u_0) = 0\), and the Jacobian matrix \(F'(u_0)\) has maximum rank. Then the solution set of \(F\) contains a smooth curve \(c(s)\), \(s\) the arclength, with \(c(0) = u_0\), and there exists an open interval \(I\) such that for all \(\alpha \in I\), \(c'(\alpha) \neq 0\), and \(\mathrm{rank}(F'(c(\alpha))) = n\). Homotopy continuation, or curve tracing, consists of the iteration of two steps: predicting and correcting. In this paper, the predictor strategy known as the Euler predictor is used, and various corrector strategies are studied. Two corrector strategies often employed are: 1) the plane corrector, which finds the point \(u_{k+1}\) at the intersection of the curve with the hyperplane perpendicular to the tangent of the curve at the point \(u_{k}\) and containing the predicted point \(v_{k+1}\) and 2) the nearest point corrector, which finds the point \(u_{k+1}\) on the curve nearest to the predicted point \(v_{k+1}\). While these methods work well in general if the solution curves are close to each other, or the curve turns sharply at some point, ``curve jumping'' can occur. This forces the predictor steplength to be very small, reducing the overall efficiency of the algorithm. The authors present a new ``sphere corrector'' strategy. The method finds the point \(u_{k+1}\) which is the intersection of the curve, and the sphere whose diameter is the straight line segment joining the points \(u_{k}\) and the predicted point \(v_{k+1}\). This intersection is found using Netwon's method, or variants thereof, and the steplength must be adjusted to make the sphere intersect \(c(s)\) at only the two points \(u_{k}\) and \(u_{k+1}\). The authors prove that the method approximates a solution curve if the steplength is small enough. Further, the steplength is adapted (increased or decreased as necessary) throughout the algorithm using the convergence (or lack thereof) of the iterative method used to find the intersection. The authors suggest using Newton's method, Newton's method with ``line search'' step control or Netwon's method with ``trust region'' step control to solve the nonlinear system generated by the corrector step. The paper concludes with a comparison of the three corrector methods on systems of two concentric circles with various radii. The results illustrate that the sphere corrector method is more robust and efficient than the other two.
0 references
parameterized system of nonlinear equations
0 references
continuation method
0 references
homotopy method
0 references
Newton's method
0 references
curve jumping
0 references
Euler predictor
0 references
Taylor polynomial predictor
0 references
0 references
0 references
0 references
0 references
0 references