Concept# Stirling's approximation

Summary

In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.
One way of stating the approximation involves the logarithm of the factorial:
\ln(n!) = n\ln n - n +O(\ln n),
where the big O notation means that, for all sufficiently large values of n, the difference between \ln(n!) and n\ln n-n will be at most proportional to the logarithm. In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to use instead the binary logarithm, giving the equivalent form
\log_2 (n!) = n\log_2 n - n\log_2 e +O(\log_2 n). The error term in either base can be expressed more precisely as \tfrac12\log(2\pi n)+

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (13)

Loading

Loading

Loading

Related units (1)

Related concepts (1)

In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common function

Related people (1)

Simone Brugiapaglia, Fabio Nobile

We present a theoretical analysis of the CORSING (COmpRessed SolvING) method for the numerical approximation of partial differential equations based on compressed sensing. In particular, we show that the best s-term approximation of the weak solution of a PDE with respect to an orthonormal system of N trial functions, can be recovered via a Petrov-Galerkin approach using m < N orthonormal test functions. This recovery is guaranteed if the local a-coherence associated with the bilinear form and the selected trial and test bases fulfills suitable decay properties. The fundamental tool of this analysis is the restricted infsup property, i.e., a combination of the classical inf-sup condition and the well-known restricted isometry property of compressed sensing.

Simone Brugiapaglia, Fabio Nobile

We present a theoretical analysis of the CORSING (COmpRessed SolvING) method for the numerical approximation of partial differential equations based on compressed sensing. In particular, we show that the best s-term approximation of the weak solution of a PDE with respect to a system of N trial functions, can be recovered via a Petrov-Galerkin approach using m < N test functions. This recovery is guaranteed if the local a-coherence associated with the bilinear form and the selected trial and test bases fulfills suitable decay properties. The fundamental tool of this analysis is the restricted inf-sup property, i.e., a combination of the classical inf-sup condition and the well-known restricted isometry property of compressed sensing.

2018In this work, we focus on the Dynamical Low Rank (DLR) approximation of PDEs equations with random parameters. This can be interpreted as a reduced basis method, where the approximate solution is expanded in separable form over a set of few deterministic basis functions at each time, with the peculiarity that both the deterministic modes and the stochastic coefficients are computed on the fly and are free to adapt in time so as best describe the structure of the random solution. Our first goal is to generalize and reformulate in a variational setting the Dynamically Orthogonal (DO) method, proposed by Sapsis and Lermusiaux (2009) for the approximation of fluid dynamic problems with random initial conditions. The DO method is reinterpreted as a Galerkin projection of the governing equations onto the tangent space along the approximate trajectory to the manifold M_S , given by the collection of all functions which can be expressed as a sum of S linearly independent deterministic modes combined with S linearly independent stochastic modes. Depending on the parametrization of the tangent space, one obtains a set of nonlinear differential equations, suitable for numerical integration, for both the coefficients and the basis functions of the approximate solution. By formalizing the DLR variational principle for parabolic PDEs with random parameters we establish a precise link with similar techniques developed in different contexts such as the Multi-Configuration Time-Dependent Hartree method in quantum dynamics and the Dynamical Low-Rank approximation in the finite dimensional setting. By the use of curvature estimates for the approximation manifold M_S , we derive a theoretical bound for the approximation error of the S-terms DO solution by the corresponding S-terms best approximation at each time instant. The bound is applicable for full rank DLR approximate solutions on the largest time interval in which the best S-terms approximation is continuously differentiable in time. Secondly, we focus on parabolic equations, especially incompressible Navier-Stokes equations, with random Dirichlet boundary conditions and we propose a DLR technique which allows for the strong imposition of such boundary conditions. We show that the DLR variational principle can be set in the constrained manifold of all S rank random fields with a prescribed value on the boundary, expressed in low-rank format, with rank M smaller than S. We characterize the tangent space to the constrained manifold by means of the Dual Dynamically Orthogonal formulation, in which the stochastic modes are kept orthonormal and the deterministic modes satisfy suitable boundary conditions, consistent with the original problem. The same formulation is also used to conveniently include the incompressibility constraint when dealing with incompressible Navier-Stokes equations with random parameters. Finally, we extend the DLR approach for the approximation of wave equations with random parameters. We propose the Symplectic DO method, according to which the governing equation is rewritten in Hamiltonian form and the approximate solution is sought in the low dimensional manifold of all complex-valued random fields with fixed rank. Recast in the real setting, the approximate solution is expanded over a set of a few dynamical symplectic deterministic modes and satisfies the symplectic projection of the Hamiltonian system into the tangent space of the approximation manifold along the trajectory.

Related courses (10)

Dans ce cours, nous présentons les méthodes de base du traitement des signaux.

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees, describe scalable solution techniques and algorithms, and illustrate the trade-offs involved.

Ce cours aborde la théorie des systèmes linéaires discrets invariants par décalage (LID). Leurs propriétés et caractéristiques fondamentales y sont discutées, ainsi que les outils fondamentaux permettant de les étudier (transformée de Fourier et transformée en Z).

Related lectures (11)