Numerical methods for partial differential equations

Last updated

Numerical methods for partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs). [1] [2]

Contents

In principle, specialized methods for Hyperbolic, [3] Parabolic [4] or Elliptic partial differential equations [5] exist. [6] [7]

Overview of methods

Finite difference method

In this method, functions are represented by their values at certain grid points and derivatives are approximated through differences in these values.

Method of lines

The method of lines (MOL, NMOL, NUMOL [8] [9] [10] ) is a technique for solving partial differential equations (PDEs) in which all dimensions except one are discretized. MOL allows standard, general-purpose methods and software, developed for the numerical integration of ordinary differential equations (ODEs) and differential algebraic equations (DAEs), to be used. A large number of integration routines have been developed over the years in many different programming languages, and some have been published as open source resources. [11]

The method of lines most often refers to the construction or analysis of numerical methods for partial differential equations that proceeds by first discretizing the spatial derivatives only and leaving the time variable continuous. This leads to a system of ordinary differential equations to which a numerical method for initial value ordinary equations can be applied. The method of lines in this context dates back to at least the early 1960s. [12]

Finite element method

The finite element method (FEM) is a numerical technique for finding approximate solutions to boundary value problems for differential equations. It uses variational methods (the calculus of variations) to minimize an error function and produce a stable solution. Analogous to the idea that connecting many tiny straight lines can approximate a larger circle, FEM encompasses all the methods for connecting many simple element equations over many small subdomains, named finite elements, to approximate a more complex equation over a larger domain.

Gradient discretization method

The gradient discretization method (GDM) is a numerical technique that encompasses a few standard or recent methods. It is based on the separate approximation of a function and of its gradient. Core properties allow the convergence of the method for a series of linear and nonlinear problems, and therefore all the methods that enter the GDM framework (conforming and nonconforming finite element, mixed finite element, mimetic finite difference...) inherit these convergence properties.

Finite volume method

The finite-volume method is a method for representing and evaluating partial differential equations in the form of algebraic equations [LeVeque, 2002; Toro, 1999]. Similar to the finite difference method or finite element method, values are calculated at discrete places on a meshed geometry. "Finite volume" refers to the small volume surrounding each node point on a mesh. In the finite volume method, volume integrals in a partial differential equation that contain a divergence term are converted to surface integrals, using the divergence theorem. These terms are then evaluated as fluxes at the surfaces of each finite volume. Because the flux entering a given volume is identical to that leaving the adjacent volume, these methods are conservative. Another advantage of the finite volume method is that it is easily formulated to allow for unstructured meshes. The method is used in many computational fluid dynamics packages.

Spectral method

Spectral methods are techniques used in applied mathematics and scientific computing to numerically solve certain differential equations, often involving the use of the fast Fourier transform. The idea is to write the solution of the differential equation as a sum of certain "basis functions" (for example, as a Fourier series, which is a sum of sinusoids) and then to choose the coefficients in the sum that best satisfy the differential equation.

Spectral methods and finite element methods are closely related and built on the same ideas; the main difference between them is that spectral methods use basis functions that are nonzero over the whole domain, while finite element methods use basis functions that are nonzero only on small subdomains. In other words, spectral methods take on a global approach while finite element methods use a local approach. Partially for this reason, spectral methods have excellent error properties, with the so-called "exponential convergence" being the fastest possible, when the solution is smooth. However, there are no known three-dimensional single domain spectral shock capturing results. [13] In the finite element community, a method where the degree of the elements is very high or increases as the grid parameter h decreases to zero is sometimes called a spectral element method.

Meshfree methods

Meshfree methods do not require a mesh connecting the data points of the simulation domain. Meshfree methods enable the simulation of some otherwise difficult types of problems, at the cost of extra computing time and programming effort.

Domain decomposition methods

Domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains. A coarse problem with one or few unknowns per subdomain is used to further coordinate the solution between the subdomains globally. The problems on the subdomains are independent, which makes domain decomposition methods suitable for parallel computing. Domain decomposition methods are typically used as preconditioners for Krylov space iterative methods, such as the conjugate gradient method or GMRES.

In overlapping domain decomposition methods, the subdomains overlap by more than the interface. Overlapping domain decomposition methods include the Schwarz alternating method and the additive Schwarz method. Many domain decomposition methods can be written and analyzed as a special case of the abstract additive Schwarz method.

In non-overlapping methods, the subdomains intersect only on their interface. In primal methods, such as Balancing domain decomposition and BDDC, the continuity of the solution across subdomain interface is enforced by representing the value of the solution on all neighboring subdomains by the same unknown. In dual methods, such as FETI, the continuity of the solution across the subdomain interface is enforced by Lagrange multipliers. The FETI-DP method is hybrid between a dual and a primal method.

Non-overlapping domain decomposition methods are also called iterative substructuring methods.

Mortar methods are discretization methods for partial differential equations, which use separate discretization on nonoverlapping subdomains. The meshes on the subdomains do not match on the interface, and the equality of the solution is enforced by Lagrange multipliers, judiciously chosen to preserve the accuracy of the solution. In the engineering practice in the finite element method, continuity of solutions between non-matching subdomains is implemented by multiple-point constraints.

Finite element simulations of moderate size models require solving linear systems with millions of unknowns. Several hours per time step is an average sequential run time, therefore, parallel computing is a necessity. Domain decomposition methods embody large potential for a parallelization of the finite element methods, and serve a basis for distributed, parallel computations.

Multigrid methods

Multigrid (MG) methods in numerical analysis are a group of algorithms for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in (but not limited to) problems exhibiting multiple scales of behavior. For example, many basic relaxation methods exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid. [14] MG methods can be used as solvers as well as preconditioners.

The main idea of multigrid is to accelerate the convergence of a basic iterative method by global correction from time to time, accomplished by solving a coarse problem. This principle is similar to interpolation between coarser and finer grids. The typical application for multigrid is in the numerical solution of elliptic partial differential equations in two or more dimensions. [15]

Multigrid methods can be applied in combination with any of the common discretization techniques. For example, the finite element method may be recast as a multigrid method. [16] In these cases, multigrid methods are among the fastest solution techniques known today. In contrast to other methods, multigrid methods are general in that they can treat arbitrary regions and boundary conditions. They do not depend on the separability of the equations or other special properties of the equation. They have also been widely used for more-complicated non-symmetric and nonlinear systems of equations, like the Lamé system of elasticity or the Navier–Stokes equations. [17]

Comparison

The finite difference method is often regarded as the simplest method to learn and use. The finite element and finite volume methods are widely used in engineering and in computational fluid dynamics, and are well suited to problems in complicated geometries. Spectral methods are generally the most accurate, provided that the solutions are sufficiently smooth.

See also

Further reading

Related Research Articles

Partial differential equation Type of multivariable function

In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.

Computational fluid dynamics Analysis and solving of problems that involve fluid flows

Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows. Computers are used to perform the calculations required to simulate the free-stream flow of the fluid, and the interaction of the fluid with surfaces defined by boundary conditions. With high-speed supercomputers, better solutions can be achieved, and are often required to solve the largest and most complex problems. Ongoing research yields software that improves the accuracy and speed of complex simulation scenarios such as transonic or turbulent flows. Initial validation of such software is typically performed using experimental apparatus such as wind tunnels. In addition, previously performed analytical or empirical analysis of a particular problem can be used for comparison. A final validation is often performed using full-scale testing, such as flight tests.

Finite volume method

The finite volume method (FVM) is a method for representing and evaluating partial differential equations in the form of algebraic equations. In the finite volume method, volume integrals in a partial differential equation that contain a divergence term are converted to surface integrals, using the divergence theorem. These terms are then evaluated as fluxes at the surfaces of each finite volume. Because the flux entering a given volume is identical to that leaving the adjacent volume, these methods are conservative. Another advantage of the finite volume method is that it is easily formulated to allow for unstructured meshes. The method is used in many computational fluid dynamics packages. "Finite volume" refers to the small volume surrounding each node point on a mesh.

The boundary element method (BEM) is a numerical computational method of solving linear partial differential equations which have been formulated as integral equations, including fluid mechanics, acoustics, electromagnetics, fracture mechanics, and contact mechanics.

In numerical analysis, a multigrid method is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhibiting multiple scales of behavior. For example, many basic relaxation methods exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid. MG methods can be used as solvers as well as preconditioners.

Computational electromagnetics Branch of physics

Computational electromagnetics (CEM), computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment.

Method of lines Numerical method

The method of lines is a technique for solving partial differential equations (PDEs) in which all but one dimension is discretized. By reducing a PDE to a single continuous dimension, the method of lines allows solutions to be computed via methods and software developed for the numerical integration of ordinary differential equations (ODEs) and differential-algebraic systems of equations (DAEs). Many integration routines have been developed over the years in many different programming languages, and some have been published as open source resources.

Domain decomposition methods

In mathematics, numerical analysis, and numerical partial differential equations, domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains. A coarse problem with one or few unknowns per subdomain is used to further coordinate the solution between the subdomains globally. The problems on the subdomains are independent, which makes domain decomposition methods suitable for parallel computing. Domain decomposition methods are typically used as preconditioners for Krylov space iterative methods, such as the conjugate gradient method, GMRES, and LOBPCG.

In numerical analysis, mortar methods are discretization methods for partial differential equations, which use separate finite element discretization on nonoverlapping subdomains. The meshes on the subdomains do not match on the interface, and the equality of the solution is enforced by Lagrange multipliers, judiciously chosen to preserve the accuracy of the solution. Mortar discretizations lend themselves naturally to the solution by iterative domain decomposition methods such as FETI and balancing domain decomposition In the engineering practice in the finite element method, continuity of solutions between non-matching subdomains is implemented by multiple-point constraints.

Finite element method Numerical method for solving physical or engineering problems

The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential.

hp-FEM is a general version of the finite element method (FEM), a numerical method for solving partial differential equations based on piecewise-polynomial approximations that employs elements of variable size (h) and polynomial degree (p). The origins of hp-FEM date back to the pioneering work of Barna A. Szabó and Ivo Babuška who discovered that the finite element method converges exponentially fast when the mesh is refined using a suitable combination of h-refinements (dividing elements into smaller ones) and p-refinements. The exponential convergence makes the method a very attractive choice compared to most other finite element methods which only converge with an algebraic rate. The exponential convergence of the hp-FEM was not only predicted theoretically but also observed by numerous independent researchers.

In numerical analysis, coarse problem is an auxiliary system of equations used in an iterative method for the solution of a given larger system of equations. A coarse problem is basically a version of the same problem at a lower resolution, retaining its essential characteristics, but with fewer variables. The purpose of the coarse problem is to propagate information throughout the whole problem globally.

Jinchao Xu American-Chinese mathematician (born 1961)

Jinchao Xu is an American-Chinese mathematician. He is currently the Verne M. Willaman Professor in the Department of Mathematics at the Pennsylvania State University, University Park. He is known for his work on multigrid methods, domain decomposition methods, finite element methods, and more recently deep neural networks.

In numerical mathematics, the boundary knot method (BKM) is proposed as an alternative boundary-type meshfree distance function collocation scheme.

The Kansa method is a computer method used to solve partial differential equations. Its main advantage is it is very easy to understand and program on a computer. It is much less complicated than the finite element method. Another advantage is it works well on multi variable problems. The finite element method is complicated when working with more than 3 space variables and time.

Fluid motion is governed by the Navier–Stokes equations, a set of coupled and nonlinear partial differential equations derived from the basic laws of conservation of mass, momentum and energy. The unknowns are usually the flow velocity, the pressure and density and temperature. The analytical solution of this equation is impossible hence scientists resort to laboratory experiments in such situations. The answers delivered are, however, usually qualitatively different since dynamical and geometric similitude are difficult to enforce simultaneously between the lab experiment and the prototype. Furthermore, the design and construction of these experiments can be difficult, particularly for stratified rotating flows. Computational fluid dynamics (CFD) is an additional tool in the arsenal of scientists. In its early days CFD was often controversial, as it involved additional approximation to the governing equations and raised additional (legitimate) issues. Nowadays CFD is an established discipline alongside theoretical and experimental methods. This position is in large part due to the exponential growth of computer power which has allowed us to tackle ever larger and more complex problems.

Grids or meshes are geometrical shapes which are small-sized discrete cells that cover the physical domain, whose objective is to identify the discrete volumes or elements where conservation laws can be applied. They have applications in the fields of computational fluid dynamics (CFD), geography, designing and many more places where numerical solutions to the partial differential equations (PDEs) are required.

The closest point method (CPM) is an embedding method for solving partial differential equations on surfaces. The closest point method uses standard numerical approaches such as finite differences, finite element or spectral methods in order to solve the embedding partial differential equation (PDE) which is equal to the original PDE on the surface. The solution is computed in a band surrounding the surface in order to be computationally efficient. In order to extend the data off the surface, the closest point method uses a closest point representation. This representation extends function values to be constant along directions normal to the surface.

Numerical modeling (geology) Technique to solve geological problems by computational simulation

In geology, numerical modeling is a widely applied technique to tackle complex geological problems by computational simulation of geological scenarios.

References

  1. ↑ Pinder, George F. (2018). Numerical methods for solving partial differential equations : a comprehensive introduction for scientists and engineers. Hoboken, NJ. ISBN   978-1-119-31636-7. OCLC   1015215158.
  2. ↑ Rubinstein, Jacob; Pinchover, Yehuda, eds. (2005), "Numerical methods", An Introduction to Partial Differential Equations, Cambridge: Cambridge University Press, pp. 309–336, doi:10.1017/cbo9780511801228.012, ISBN   978-0-511-80122-8 , retrieved 2021-11-15
  3. ↑ "Hyperbolic partial differential equation, numerical methods - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2021-11-15.
  4. ↑ "Parabolic partial differential equation, numerical methods - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2021-11-15.
  5. ↑ "Elliptic partial differential equation, numerical methods - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2021-11-15.
  6. ↑ Evans, Gwynne (2000). Numerical methods for partial differential equations. J. M. Blackledge, P. Yardley. London: Springer. ISBN   3-540-76125-X. OCLC   41572731.
  7. ↑ Grossmann, Christian (2007). Numerical treatment of partial differential equations. Hans-Görg Roos, M. Stynes. Berlin: Springer. ISBN   978-3-540-71584-9. OCLC   191468303.
  8. ↑ Schiesser, W. E. (1991). The Numerical Method of Lines . Academic Press. ISBN   0-12-624130-9.
  9. ↑ Hamdi, S., W. E. Schiesser and G. W. Griffiths (2007), Method of lines, Scholarpedia, 2(7):2859.
  10. ↑ Schiesser, W. E.; Griffiths, G. W. (2009). A Compendium of Partial Differential Equation Models: Method of Lines Analysis with Matlab. Cambridge University Press. ISBN   978-0-521-51986-1.
  11. ↑ Lee, H. J.; Schiesser, W. E. (2004). Ordinary and Partial Differential Equation Routines in C, C++, Fortran, Java, Maple and Matlab. CRC Press. ISBN   1-58488-423-1.
  12. ↑ E. N. Sarmin, L. A. Chudov (1963), On the stability of the numerical integration of systems of ordinary differential equations arising in the use of the straight line method, USSR Computational Mathematics and Mathematical Physics, 3(6), (1537–1543).
  13. ↑ pp 235, Spectral Methods: evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007.
  14. ↑ Roman Wienands; Wolfgang Joppich (2005). Practical Fourier analysis for multigrid methods. CRC Press. p. 17. ISBN   1-58488-492-4.
  15. ↑ U. Trottenberg; C. W. Oosterlee; A. Schüller (2001). Multigrid. Academic Press. ISBN   0-12-701070-X.
  16. ↑ Yu Zhu; Andreas C. Cangellaris (2006). Multigrid finite element methods for electromagnetic field modeling. Wiley. p. 132 ff. ISBN   0-471-74110-8.
  17. ↑ Shah, Tasneem Mohammad (1989). Analysis of the multigrid method (Thesis). Oxford University. Bibcode:1989STIN...9123418S.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.