×

Large sparse continuation problems. (English) Zbl 0688.65035

This article begins by reviewing continuation methods in general, using clear and careful notation; this includes a brief review of literature on exploitation of matrix structure in large continuation problems. The next section deals with incorporation of a nonlinear conjugate gradient method for the corrector phase (as opposed to using a linear conjugate gradient method for a Newton’s method-based corrector, as other authors have done). In this method, the line searches are taylored to the fact that we can adjust the predictor steplength so that higher-order terms in the objective function are negligible.
Despite the context of a solution manifold instead of isolated solutions, several convergence results are presented, and it is conjectured that the scheme is locally superlinearly convergent. Practicalities, such as preconditioners and use of higher-order predictors to offset the somewhat slower convergence of the conjugate gradient method, are discussed. Handling bifurcation in this context is discussed; local perturbations are used, since determinant sign changes are not readily available from the nonlinear conjugate gradient method.
Numerical experiments dealing with nonlinear eigenvalue problems corresponding to buckled plates of various shapes are given; solutions are presented graphically. The reference list is sufficiently complete to guide a beginner through a thorough self-study of the underlying concepts.
Reviewer: B.Kearfott

MSC:

65H10 Numerical computation of solutions to systems of equations
74K20 Plates

Software:

PITCON; PLTMGC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Baali, M., Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. Numer. Anal., 5, 121-124 (1985) · Zbl 0578.65063
[2] Allgower, E. L.; Chien, C.-S., Continuation and local perturbation for multiple bifurcations, SIAM J. Sci. Stat. Comput., 7, 1265-1281 (1986) · Zbl 0617.65056
[3] Allgower, E. L.; Georg, K., Predictor-corrector and simplicial methods for approximating fixed points and zero points of nonlinear mappings, (Bachem, A.; Grötschel, M.; Korte, B., Mathematical Programming: The State of the Art (1983), Springer: Springer Berlin/Heidelberg/New York) · Zbl 0541.65032
[4] Bank, R. E.; Chan, T. F., PLTMGC: A multi-grid continuation program for parameterized nonlinear elliptic systems, SIAM J. Sci. Stat. Comput., 7, 540-559 (1986) · Zbl 0589.65074
[5] Berger, M. S., Nonlinearity and Functional Analysis (1977), Academic Press: Academic Press New York/London
[6] Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods (1984), Academic Press: Academic Press New York/London
[7] Beyn, W.-J., On discretizations of bifurcation problems, (Mittelmann, H. D.; Weber, H., Bifurcation Problems and their Numerical Solution. Bifurcation Problems and their Numerical Solution, Internat. Ser. Numer. Math., 54 (1980), Birkhäuser: Birkhäuser Basel), 46-76
[8] Beyn, W.-J., Lösungszweige nichtlinearer Randwertaufgaben und ihre Approximation mit dem Differenzenverfahren, (Habilitationsschrift (1981), Univ. Konstanz)
[9] Beyn, W.-J., Defining equations for singular solutions and numerical applications, (Küpper, T.; Mittelmann, H. D.; Weber, H., Numerical Methods for Bifurcation Problems. Numerical Methods for Bifurcation Problems, Internat. Ser. Numer. Math., 70 (1984), Birkhäuser: Birkhäuser Basel), 42-56
[10] Bolstad, J. H.; Keller, H. B., A multigrid continuation method for elliptic problems with folds, SIAM J. Sci. Stat. Comput., 7, 1081-1104 (1986) · Zbl 0631.65052
[11] Brezzi, F.; Rappaz, J.; Raviart, P. A., Finite dimensional approximation of nonlinear problems, Part 3: Simple bifurcation points, Numer. Math., 38, 1-30 (1981) · Zbl 0525.65037
[12] Chan, T. F., Techniques for large sparse systems arising from continuation methods, (Küpper, T.; Mittelmann, H.; Weber, H., Numerical Methods for Bifurcation Problems. Numerical Methods for Bifurcation Problems, Internat. Ser. Numer. Math., 70 (1984), Birkhäuser: Birkhäuser Basel), 116-128
[13] Chan, T. F.; Keller, H. B., Arclength continuation and multi-grid techniques for nonlinear eigenvalue problems, SIAM J. Sci. Stat. Comput., 3, 173-194 (1982) · Zbl 0497.65028
[14] Chow, S. N.; Hale, J. K., Methods of Bifurcation Theory (1982), Springer: Springer Berlin/Heidelberg/New York
[15] Cohen, A. I., Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal., 9, 248-259 (1972) · Zbl 0279.65051
[16] Crandall, M. G.; Rabinowitz, P. H., Bifurcation from simple eigenvalues, J. Funct. Anal., 8, 321-340 (1971) · Zbl 0219.46015
[17] Den Heijer, C.; Rheinboldt, W. C., On steplength algorithms for a class of continuation methods, SIAM J. Numer. Anal., 18, 925-948 (1981) · Zbl 0472.65042
[18] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[19] Dennis, J. E.; Turner, K., Generalized conjugate directions, Linear Algebra Appl., 88/89, 187-209 (1987) · Zbl 0644.65025
[20] Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1984) · Zbl 0132.11701
[21] Georg, K., On tracing an implicitly defined curve by quasi-Newton steps and calculating bifurcation by local perturbation, SIAM J. Sci. Stat. Comput., 2, 35-50 (1981) · Zbl 0463.65034
[22] Georg, K., Zur numerischen Realisierung von Kontinuitätsmethoden mit Prädiktor-Korrektor-oder simplizialen Verfahren, (Habilitationsschrift (1982), Univ. Bonn)
[23] Georg, K., A note on stepsize control for numerical curve following, (Eaves, B. C.; Gould, F. J.; Peitgen, H.-O.; Todd, M. J., Homotopy Methods and Global Convergence (1983), Plenum Press: Plenum Press New York), 145-154 · Zbl 0508.65021
[24] Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic Press: Academic Press New York/London · Zbl 0503.90062
[25] Glowinski, R.; Keller, H. B.; Reinhart, L., Continuation-conjugate gradient methods for the least square solution of nonlinear boundary value problems, SIAM J. Sci. Stat. Comput., 6, 793-832 (1985) · Zbl 0589.65075
[26] Golub, G. H.; Van Loan, Ch. F., Matrix Computations (1983), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0559.65011
[27] Jürgens, H.; Peitgen, H.-O.; Saupe, D., Topological perturbations in the numerical study of nonlinear eigenvalue and bifurcation problems, (Robinson, S. M., Analysis and Computation of Fixed Points (1980), Academic Press: Academic Press New York/London), 139-181
[28] Keener, J. P.; Keller, H. B., Perturbed bifurcation theory, Arch. Rational Mech. Anal., 50, 159-175 (1974) · Zbl 0254.47080
[29] Keller, H. B., Nonlinear bifurcation, J. Differential Equations, 7, 417-434 (1970) · Zbl 0208.36802
[30] Keller, H. B., Numerical solution of bifurcation and nonlinear eigenvalue problems, (Rabinowitz, P., Application of Bifurcation Theory (1977), Academic Press: Academic Press New York/London), 359-384 · Zbl 0581.65043
[31] Keller, H. B., Lectures on Numerical Methods in Bifurcation Problems (1987), Springer: Springer Berlin/Heidelberg/New York · Zbl 0656.65063
[32] (Küpper, T.; Mittelmann, H. D.; Weber, H., Numerical Methods for Bifurcation Problems. Numerical Methods for Bifurcation Problems, Internat. Ser. Numer. Math., 70 (1984), Birkhäuser: Birkhäuser Basel) · Zbl 0535.00021
[33] (Küpper, T.; Seydel, R.; Troger, H., Bifurcation: Analysis, Algorithms, Applications. Bifurcation: Analysis, Algorithms, Applications, Internat. Ser. Numer. Math., 79 (1987), Birkhäuser: Birkhäuser Basel) · Zbl 0632.00010
[34] McCormick, G. P.; Ritter, K., Alternate proofs of the convergence properties of the conjugate gradient method, J. Optim. Theor. Appl., 13, 497-518 (1974) · Zbl 0261.90053
[35] Mittelmann, H. D., Continuation near symmetry-breaking bifurcation points, (Küpper, T.; Mittelmann, H.; Weber, H., Numerical Methods for Bifurcation Problems. Numerical Methods for Bifurcation Problems, Internat. Ser. Numer. Math., 70 (1984), Birkhäuser: Birkhäuser Basel) · Zbl 0539.65040
[36] Nirenberg, L., Topics in nonlinear functional analysis (1974), Courant Institute: Courant Institute New York · Zbl 0286.47037
[37] Polak, E.; Ribière, G., Note sur la convergence de méthodes de directions conjugées, Rev. Franc. Inf. Rech. Oper., 16, 35-43 (1969) · Zbl 0174.48001
[38] Powell, M. J.D., Restart procedures for the conjugate gradient method, Math. Programming, 12, 241-254 (1977) · Zbl 0396.90072
[39] Powell, M. J.D., Nonconvex minimization calculations and the conjugate gradient method, (Griffiths, D. F., Numerical Analysis, Dundee 1983. Numerical Analysis, Dundee 1983, Lecture Notes in Math. (1984), Springer: Springer Berlin/Heidelberg/New York) · Zbl 0531.65035
[40] Rabinowitz, P. H., Some global results for nonlinear eigenvalue problems, J. Funct. Anal., 7, 487-513 (1971) · Zbl 0212.16504
[41] Reinhart, L., Sur la résolution numérique de problèmes aux limites non linéaires par des méthodes de continuation, (Thèse de 3-ème cycle (1980), Univ. Paris VI)
[42] Reinhart, L., On the numerical analysis of the von Karman equations: Mixed finite element approximation and continuation techniques, Numer. Math., 39, 371-404 (1982) · Zbl 0503.73048
[43] Rheinboldt, W. C., Numerical methods for a class of finite dimensional bifurcation problems, SIAM J. Numer. Anal., 15, 1-11 (1978) · Zbl 0389.65024
[44] Rheinboldt, W. C., Numerical analysis of continuation methods for nonlinear structural problems, Comput. & Structures, 13, 130-141 (1981)
[45] Rheinboldt, W. C., Numerical Analysis of Parametrized Nonlinear Equations (1986), Wiley: Wiley New York · Zbl 0572.65034
[46] Saad, Y.; Schultz, M., GMRES: a generalized minimal residual method for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[47] Schwetlick, H., On the choice of steplength in path following methods, Z. Angew. Math. Mech., 64, 391-396 (1984) · Zbl 0593.65036
[48] Shampine, L. F.; Gordon, M. K., Computer solutions of ordinary differential equations: The initial value problem (1975), Freeman: Freeman New York · Zbl 0347.65001
[49] Stoer, J., Solution of large linear systems of equations by conjugate gradient type methods, (Bachem, A.; Grötschel, M.; Korte, B., Mathematical Programming: The State of the Art (1983), Springer: Springer Berlin/Heidelberg/New York), 540-565 · Zbl 0553.65022
[50] Winther, R., Some superlinear convergence results for the conjugate gradient method, SIAM J. Numer. Anal., 17, 14-18 (1980) · Zbl 0447.65021
[51] Walker, H. F., Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Stat. Comput., 9, 152-163 (1988) · Zbl 0698.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.