HOME

TheInfoList



OR:

Numerical methods for partial differential equations is the branch of
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
that studies the numerical solution of
partial differential equations In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function. The function is often thought of as an "unknown" to be solved for, similarly to ...
(PDEs). In principle, specialized methods for hyperbolic, parabolic or
elliptic partial differential equations Second-order linear partial differential equations (PDEs) are classified as either elliptic, hyperbolic, or parabolic. Any second-order linear PDE in two variables can be written in the form :Au_ + 2Bu_ + Cu_ + Du_x + Eu_y + Fu +G= 0,\, where ...
exist.


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, NUMOLHamdi, S., W. E. Schiesser and G. W. Griffiths (2007)
Method of lines
''Scholarpedia'', 2(7):2859.
) is a technique for solving
partial differential equations In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function. The function is often thought of as an "unknown" to be solved for, similarly to ...
(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 equation In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast ...
s (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 Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized so ...
resources. 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.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).


Finite element method

The finite element method (FEM) is a numerical technique for finding approximate solutions to
boundary value problem In mathematics, in the field of differential equations, a boundary value problem is a differential equation together with a set of additional constraints, called the boundary conditions. A solution to a boundary value problem is a solution to t ...
s for
differential equations In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
. It uses variational methods (the
calculus of variations The calculus of variations (or Variational Calculus) is a field of mathematical analysis that uses variations, which are small changes in functions and functionals, to find maxima and minima of functionals: mappings from a set of functions t ...
) 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 Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
.


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 equation In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function. The function is often thought of as an "unknown" to be solved for, similarly to h ...
s in the form of algebraic equations eVeque, 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 In vector calculus, divergence is a vector operator that operates on a vector field, producing a scalar field giving the quantity of the vector field's source at each point. More technically, the divergence represents the volume density of ...
term are converted to
surface integral In mathematics, particularly multivariable calculus, a surface integral is a generalization of multiple integrals to integration over surfaces. It can be thought of as the double integral analogue of the line integral. Given a surface, one ...
s, using the
divergence theorem In vector calculus, the divergence theorem, also known as Gauss's theorem or Ostrogradsky's theorem, reprinted in is a theorem which relates the '' flux'' of a vector field through a closed surface to the ''divergence'' of the field in the ...
. 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 Conservatism is a cultural, social, and political philosophy that seeks to promote and to preserve traditional institutions, practices, and values. The central tenets of conservatism may vary in relation to the culture and civilization in ...
. 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 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 ...
packages.


Spectral method

Spectral methods are techniques used in
applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...
and
scientific computing Computational science, also known as scientific computing or scientific computation (SC), is a field in mathematics that uses advanced computing capabilities to understand and solve complex problems. It is an area of science that spans many disc ...
to numerically solve certain
differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, ...
s, often involving the use of the
fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in ...
. The idea is to write the solution of the differential equation as a sum of certain "basis functions" (for example, as a
Fourier series A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or '' ...
, which is a sum of
sinusoid A sine wave, sinusoidal wave, or just sinusoid is a mathematical curve defined in terms of the ''sine'' trigonometric function, of which it is the graph. It is a type of continuous wave and also a smooth periodic function. It occurs often in ...
s) 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 In computational fluid dynamics, shock-capturing methods are a class of techniques for computing inviscid flows with shock waves. The computation of flow containing shock waves is an extremely difficult task because such flows result in sharp, disc ...
results.pp 235, Spectral Methods
evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007.
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 In the numerical solution of partial differential equations, a topic in mathematics, the spectral element method (SEM) is a formulation of the finite element method (FEM) that uses high degree piecewise polynomials as basis functions. The spectral ...
.


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 In mathematics, in the field of differential equations, a boundary value problem is a differential equation together with a set of additional constraints, called the boundary conditions. A solution to a boundary value problem is a solution to t ...
by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains. A
coarse problem : ''This article deals with a component of numerical methods. For coarse space in topology, see coarse structure.'' In numerical analysis, coarse problem is an auxiliary system of equations used in an iterative method for the solution of a given la ...
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 Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different f ...
. Domain decomposition methods are typically used as
preconditioner In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducin ...
s for Krylov space
iterative method In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
s, such as the
conjugate gradient method In mathematics, the conjugate gradient method is an algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a c ...
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 In numerical analysis, the balancing domain decomposition method (BDD) is an iterative method to find the solution of a symmetric positive definite system of linear algebraic equations arising from the finite element method.J. Mandel, ''Balancing do ...
and
BDDC In numerical analysis, BDDC (balancing domain decomposition by constraints) is a domain decomposition method for solving large symmetric, positive definite systems of linear equations that arise from the finite element method. BDDC is used as a prec ...
, 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 Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
are a group of
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s for solving
differential equations In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
using a
hierarchy A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an important ...
of
discretization In applied mathematics, discretization is the process of transferring continuous functions, models, variables, and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerica ...
s. 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 In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph ...
approach to multigrid. MG methods can be used as solvers as well as
preconditioner In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducin ...
s. 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 article deals with a component of numerical methods. For coarse space in topology, see coarse structure.'' In numerical analysis, coarse problem is an auxiliary system of equations used in an iterative method for the solution of a given la ...
. This principle is similar to
interpolation In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points. In engineering and science, one often has ...
between coarser and finer grids. The typical application for multigrid is in the numerical solution of
elliptic partial differential equation Second-order linear partial differential equations (PDEs) are classified as either elliptic, hyperbolic, or parabolic. Any second-order linear PDE in two variables can be written in the form :Au_ + 2Bu_ + Cu_ + Du_x + Eu_y + Fu +G= 0,\, whe ...
s in two or more dimensions. 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. 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 Lamé may refer to: *Lamé (fabric), a clothing fabric with metallic strands *Lamé (fencing), a jacket used for detecting hits * Lamé (crater) on the Moon * Ngeté-Herdé language, also known as Lamé, spoken in Chad *Peve language, also known ...
of elasticity or the
Navier–Stokes equations In physics, the Navier–Stokes equations ( ) are partial differential equations which describe the motion of viscous fluid substances, named after French engineer and physicist Claude-Louis Navier and Anglo-Irish physicist and mathematician Geo ...
.


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 Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more speciali ...
and in
computational fluid dynamics 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 ...
, 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

* List of numerical analysis topics#Numerical methods for partial differential equations *
Numerical methods for ordinary differential equations Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as " numerical integration", although this term can also ...


Further reading

* *


References


External links


Numerical Methods for Partial Differential Equations
course at
MIT OpenCourseWare MIT OpenCourseWare (MIT OCW) is an initiative of the Massachusetts Institute of Technology (MIT) to publish all of the educational materials from its undergraduate- and graduate-level courses online, freely and openly available to anyone, anyw ...
.
IMS
the Open Source IMTEK Mathematica Supplement (IMS)
Numerical PDE Techniques for Scientists and Engineers
open access Lectures and Codes for Numerical PDEs {{DEFAULTSORT:Numerical Partial Differential Equations Partial differential equations