Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method | Computing Skip to main content
Log in

Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method

Numerische Lösung von nichtlinearen elliptischen partiellen Differentialgleichungen mit einer verallgemeinerten Methode der konjugierten Gradienten

  • Published:
Computing Aims and scope Submit manuscript

Abstract

We have studied previously a generalized conjugate gradient method for solving sparse positive-definite systems of linear equations arising from the discretization of elliptic partial-differential boundary-value problems. Here, extensions to the nonlinear case are considered. We split the original discretized operator into the sum of two operators, one of which corresponds to a more easily solvable system of equations, and accelerate the associated iteration based on this splitting by (nonlinear) conjugate gradients. The behavior of the method is illustrated for the minimal surface equation with splittings corresponding to nonlinear SSOR, to approximate factorization of the Jacobian matrix, and to elliptic operators suitable for use with fast direct methods. The results of numerical experiments are given as well for a mildy nonlinear example, for which, in the corresponding linear case, the finite termination property of the conjugate gradient algorithm is crucial.

Zusammenfassung

Wir haben früher eine verallgemeinerte Methode der konjugierten Gradienten studiert, um dünnbesetzte positiv definite Systeme von linearen Gleichungen zu lösen, die von der Diskretisierung von elliptischen partiellen Differential-Randwertproblemen herrühren. Wir betrachten hier die Verallgemeinerung auf den nichtlinearen Fall: Wir spalten den ursprünglichen diskretisierten Operator auf in eine Summe von zwei Operatoren. Einer von diesen Operatoren entspricht einem leicht lösbaren System von Gleichungen, und wir beschleunigen die aus dieser Spaltung hervorgehende Iteration mit (nichtlinearen) konjugierten Gradienten. Das Verhalten der Methode wird illustriert durch Anwendung auf die Minimalflächen-Gleichung, mit Spaltungen entsprechend dem nichtlinearen SSOR-Verfahren, der angenäherten Faktorisierung der Jacobi-Matrix, oder den elliptischen Operatoren, die sich für schnelle direkte Methoden eignen. Die Resultate von numerischen Experimenten für ein nur schwach nichtlineares Beispiel sind ebenfalls angegeben. Für den entsprechenden linearen Fall ist in diesem Fall die Konvergenz des konjugierten Gradienten-Algorithmus in einer endlichen Anzahl von Schritten wesentlich.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Axelsson, O.: On preconditioning and convergence acceleration in sparse matrix problems. Report 74-10, Data Handling Division, CERN, Geneva (1974).

    Google Scholar 

  2. Bank, R. E.: A FORTRAN implementation of the generalized marching algorithm. Trans. Math. Software. To appear.

  3. Bartels, R., Daniel, J. W.: A conjugate gradient approach to nonlinear elliptic boundary value problems in irregular regions. Proc. Conf. on the Numerical Solution of Differential Equations (Lecture Notes, Vol. 363), pp. 1–11. Berlin-Heidelberg-New York: Springer 1974.

    Google Scholar 

  4. Bertsekas, D.: Partial conjugate gradient methods for a class of optimal control problems. IEEE Trans. Automat Control AC-19 1974, 209–217.

    Google Scholar 

  5. Buzbee, B. L., Golub, G. H., Nielson, C. W.: On direct methods for solving Poisson's equations. SIAM J. Numer. Anal.7, 627–656 (1970).

    Google Scholar 

  6. Concus, P.: Numerical solution of the minimal surface equation. Math. Comp.21, 340–350 (1967).

    Google Scholar 

  7. Concus, P.: Numerical solution of the minimal surface equation by block nonlinear successive overrelaxation. Information Processing 68, Proc. IFIP Congress 1968, pp. 153–158. Amsterdam: North-Holland 1969.

    Google Scholar 

  8. Concus, P., Golub, G. H.: A generalized conjugate gradient method for nonsymmetric systems of linear equations. Proc. Second International Symposium on Computing Methods in Applied Sciences and Engineering IRIA, Paris, Dec. 1975 (Lecture Notes in Economics and Math. Systems, Vol. 134), pp. 56–65. Berlin-Heidelberg-New York: Springer 1976.

    Google Scholar 

  9. Concus, P., Golub, G. H., O'Leary, D. P.: A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in: Sparse Matrix Computations (Bunch, J. R., Rose, D. J., eds.), pp. 309–332. New York: Academic Press 1976.

    Google Scholar 

  10. Daniel, J. W.: The conjugate gradient method for linear and nonlinear operator equations. Ph. D. Thesis, Stanford University, and SIAM J. Numer. Anal.4, 10–26 (1967).

    Google Scholar 

  11. Dixon, L. C. W.: Conjugate gradient algorithms: quadratic termination without linear searches. J. Inst. Maths. Applics.15, 9–18 (1975).

    Google Scholar 

  12. Ehrlich, L. W.: On some experience using matrix splitting and conjugate gradient (abstract). SIAM Review18, 801 (1976).

    Google Scholar 

  13. Fischer, D., Golub, G. H., Hald, O., Leiva, C., Widlund, O.: On Fourier-Toeplitz methods for separable elliptic problems. Math. Comp.28, 349–368 (1974).

    Google Scholar 

  14. Fletcher, R., Reeves, C. M.: Function minimization by conjugate gradients. Computer J.7, 149–154 (1964).

    Google Scholar 

  15. Forsythe, G. E., Wasow, W. R.: Finite-difference Methods for Partial Differential Equations. New York: Wiley 1960.

    Google Scholar 

  16. Goldfarb, D.: A conjugate gradient method for nonlinear programming. Princeton University Press, Thesis, 1966.

  17. Hayes, L., Young, D. M., Schleicher, E.: The use of the accelerated SSOR method to solve large linear systems (abstract). SIAM Review18, 808 (1976).

    Google Scholar 

  18. Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand.49, 409–436 (1952).

    Google Scholar 

  19. Hockney, R. W.: The potential calculation and some applications. Methods in Computational Physics, 9. (Adler, B., Fernbach, S., Rotenberg, M., eds.), pp. 136–211. New York: Academic Press 1969.

    Google Scholar 

  20. Lenard, M.: Practical convergence conditions for restarted conjugate gradient methods. MRC Report 1373, University of Wisconsin (December 1973).

  21. Meijerink, J. A., van der Vorst, H. A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp.31, 148–162 (1977).

    Google Scholar 

  22. Nazareth, L.: A conjugate direction algorithm without line searches. J. Opt. Th. Applic. (to appear).

  23. O'Leary, D. P.: Hybrid conjugate gradient algorithms. Doctoral dissertation, Computer Science Department, Stanford University, Report No. STAN-CS-76-548 (1976).

  24. Ortega, J. M., Rheinboldt, W. C.: Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press 1970.

    Google Scholar 

  25. Powell, M. J. D.: Restart procedures for the conjugate gradient method. Report C. S. S. 24, AERE, Harwell, England (1975).

    Google Scholar 

  26. Reid, J. K.: On the method of conjugate gradients for the solution of large sparse systems of linear equations, in: Large Sparse Sets of Linear Equations (Reid, J. K., ed.), pp. 231–254. New York: Academic Press 1971.

    Google Scholar 

  27. Schecter, S.: Relaxation methods for convex problems. SIAM J. Numer. Anal.5, 601–612 (1968).

    Google Scholar 

  28. Swartztrauber, P., Sweet, R.: Efficient FORTRAN subprograms for the solution of elliptic partial differential equations. Report No. NCAR-TN/IA-109, National Center for Atmospheric Research, Boulder, CO (1975).

    Google Scholar 

  29. Underwood, R. R.: An approximate factorization procedure based on the block Cholesky decomposition and its use with the conjugate gradient method. Report No. NEDO-11386, General Electric Co., Nuclear Energy Systems Div., San Jose, CA (1976).

    Google Scholar 

  30. Zangwill, W. I.: Nonlinear Programming, A Unified Approach. Englewood Cliffs, N. J.: Prentice-Hall 1969.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Concus, P., Golub, G.H. & O'Leary, D.P. Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method. Computing 19, 321–339 (1978). https://doi.org/10.1007/BF02252030

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02252030

Keywords

Navigation