Misplaced Pages

Lebedev quadrature

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Lebedev grid)

In numerical analysis, Lebedev quadrature, named after Vyacheslav Ivanovich Lebedev, is an approximation to the surface integral of a function over a three-dimensional sphere. The grid is constructed so to have octahedral rotation and inversion symmetry. The number and location of the grid points together with a corresponding set of integration weights are determined by enforcing the exact integration of polynomials (or equivalently, spherical harmonics) up to a given order, leading to a sequence of increasingly dense grids analogous to the one-dimensional Gauss-Legendre scheme.

The Lebedev grid is often employed in the numerical evaluation of volume integrals in the spherical coordinate system, where it is combined with a one-dimensional integration scheme for the radial coordinate. Applications of the grid are found in fields such as computational chemistry and neutron transport.

Angular integrals

The surface integral of a function over the unit sphere,

I [ f ] = ∫ d Ω   f ( Ω ) = ∫ 0 π sin ⁡ ( θ ) d θ ∫ 0 2 π d φ   f ( θ , φ ) , {\displaystyle I=\int \mathrm {d} \Omega \ f(\Omega )=\int _{0}^{\pi }\sin(\theta )\mathrm {d} \theta \int _{0}^{2\pi }\mathrm {d} \varphi \ f(\theta ,\varphi ),}

is approximated in the Lebedev scheme as

I ~ [ f ] = 4 π ∑ i = 1 N   w i f ( θ i , φ i ) , {\displaystyle {\tilde {I}}=4\pi \sum _{i=1}^{N}\ w_{i}f(\theta _{i},\varphi _{i}),}

where the particular grid points and grid weights are to be determined. The use of a single sum, rather than two one dimensional schemes from discretizing the θ and φ integrals individually, leads to more efficient procedure: fewer total grid points are required to obtain similar accuracy. A competing factor is the computational speedup available when using the direct product of two one-dimensional grids. Despite this, the Lebedev grid still outperforms product grids. However, the use of two one-dimensional integration better allows for fine tuning of the grids, and simplifies the use of any symmetry of the integrand to remove symmetry equivalent grid points.

Construction

The Lebedev grid points are constructed so as to lie on the surface of the three-dimensional unit sphere and to be invariant under the octahedral rotation group with inversion. For any point on the sphere, there are either five, seven, eleven, twenty-three, or forty-seven equivalent points with respect to the octahedral group, all of which are included in the grid. Further, all points equivalent under the rotational and inversion group share the same weights. The smallest such set of points is constructed from all six permutations of (±1, 0, 0) (collectively denoted as a), leading to an integration scheme

I ~ 6 [ f ] = A 1 ∑ i = 1 6 f ( a i 1 ) , {\displaystyle {\tilde {I}}_{6}=A_{1}\sum _{i=1}^{6}f(a_{i}^{1}),}
Distinct classes of grid points
Typical element Constraint Number of points
a 1 {\displaystyle a^{1}\,} ( 1 , 0 , 0 ) {\displaystyle (1,0,0)\,} 6
a 2 {\displaystyle a^{2}\,} 1 2 ( 1 , 1 , 0 ) {\displaystyle {\frac {1}{\sqrt {2}}}(1,1,0)} 12
a 3 {\displaystyle a^{3}\,} 1 3 ( 1 , 1 , 1 ) {\displaystyle {\frac {1}{\sqrt {3}}}(1,1,1)} 8
b k {\displaystyle b^{k}\,} ( l k , l k , m k ) {\displaystyle (l_{k},l_{k},m_{k})\,} 2 l k 2 + m k 2 = 1 {\displaystyle 2l_{k}^{2}+m_{k}^{2}=1} 24
c k {\displaystyle c^{k}\,} ( p k , q k , 0 ) {\displaystyle (p_{k},q_{k},0)\,} p k 2 + q k 2 = 1 {\displaystyle p_{k}^{2}+q_{k}^{2}=1} 24
d k {\displaystyle d^{k}\,} ( r k , S k , W k ) {\displaystyle (r_{k},S_{k},W_{k})\,} r k 2 + S k 2 + W k 2 = 1 {\displaystyle r_{k}^{2}+S_{k}^{2}+W_{k}^{2}=1} 48

where the grid weight is A1. Geometrically these points correspond to the vertices of a regular octahedron when aligned with the Cartesian axes. Two more sets of points, corresponding to the centers and vertices of the octahedron, are all eight uncorrelated permutations of 1 / 3 ( ± 1 , ± 1 , ± 1 ) {\displaystyle 1/{\sqrt {3}}(\pm 1,\pm 1,\pm 1)} (denoted as a), and all twelve permutations of 1 / 2 ( ± 1 , ± 1 , 0 ) {\displaystyle 1/{\sqrt {2}}(\pm 1,\pm 1,0)} (denoted as a). This selection of grid points gives rise to the scheme

I ~ 26 [ f ] = A 1 ∑ i = 1 6 f ( a i 1 ) + A 2 ∑ i = 1 12 f ( a i 2 ) + A 3 ∑ i = 1 8 f ( a i 3 ) , {\displaystyle {\tilde {I}}_{26}=A_{1}\sum _{i=1}^{6}f(a_{i}^{1})+A_{2}\sum _{i=1}^{12}f(a_{i}^{2})+A_{3}\sum _{i=1}^{8}f(a_{i}^{3}),}

where A1, A2, and A3 are the weight functions that still need to be determined. Three further types of points can be employed as shown in the table. Each of these types of classes can contribute more than one set of points to the grid. In complete generality, the Lebedev scheme is

I ~ N [ f ] = A 1 ∑ i = 1 6 f ( a i 1 ) + A 2 ∑ i = 1 12 f ( a i 2 ) + A 3 ∑ i = 1 8 f ( a i 3 ) + ∑ k = 1 N 1 B k ∑ i = 1 24 f ( b i k ) + ∑ k = 1 N 2 C k ∑ i = 1 24 f ( c i k ) + ∑ k = 1 N 3 D k ∑ i = 1 48 f ( d i k ) , {\displaystyle {\begin{aligned}{\tilde {I}}_{N}=A_{1}\sum _{i=1}^{6}f(a_{i}^{1})&+A_{2}\sum _{i=1}^{12}f(a_{i}^{2})+A_{3}\sum _{i=1}^{8}f(a_{i}^{3})\\&+\sum _{k=1}^{N_{1}}B_{k}\sum _{i=1}^{24}f(b_{i}^{k})+\sum _{k=1}^{N_{2}}C_{k}\sum _{i=1}^{24}f(c_{i}^{k})+\sum _{k=1}^{N_{3}}D_{k}\sum _{i=1}^{48}f(d_{i}^{k}),\end{aligned}}}

where the total number of points, N, is

N = 26 + 24 ( N 1 + N 2 ) + 48 N 3 . {\displaystyle N=26+24(N_{1}+N_{2})+48N_{3}.\,}

but in some cases A2 is set to zero and the number of points is

N = 14 + 24 ( N 1 + N 2 ) + 48 N 3 . {\displaystyle N=14+24(N_{1}+N_{2})+48N_{3}.\,}

The determination of the grid weights is achieved by enforcing the scheme to integrate exactly all polynomials up to a given order. On the unit sphere, this is equivalent to integrating all spherical harmonics up to the same order. This problem is simplified by a theorem of Sergei Lvovich Sobolev implying that this condition need be imposed only on those polynomials which are invariant under the octahedral rotation group with inversion. Enforcing these conditions leads to a set of nonlinear equations which have been solved and tabulated up to order 131 in the polynomial.

References

  1. Koch, Wolfram; Max C. Holthausen (2001). A Chemist's Guide to Density Functional Theory. Weinheim: Wiley-VCH. p. 107. ISBN 978-3-527-30372-4.
  2. Marchuk, G. I.; V. I. Lebedev (1986). Numerical Methods in the Theory of Neutron Transport. Taylor & Francis. p. 123. ISBN 978-3-7186-0182-0.
  3. Murray, C. W.; N. C. Handy; G. J. Laming (1993). "Quadrature schemes for integrals of density functional theory". Mol. Phys. 78 (4): 997–1014. Bibcode:1993MolPh..78..997M. doi:10.1080/00268979300100651.
  4. ^ Lebedev, V. I. (1975). "Values of the nodes and weights of ninth to seventeenth order Gauss-Markov quadrature formulae invariant under the octahedron group with inversion". Zh. Vȳchisl. Mat. Mat. Fiz. 15 (1): 48–54. doi:10.1016/0041-5553(75)90133-0.
  5. Sobolev, S. L. (1962). "Formulae for mechanical cubature on the surface of a sphere". Sibirskii Matem. Zh. 3 (5): 769–796.
  6. Lebedev, V. I. (1976). "Quadratures on a sphere". Zh. Vȳchisl. Mat. Mat. Fiz. 16 (2): 293–306. doi:10.1016/0041-5553(76)90100-2.
  7. Lebedev, V. I. (1977). "Spherical quadrature formulas exact to orders 25–29". Siberian Math. J. 18 (1): 99–107. Bibcode:1977SibMJ..18...99L. doi:10.1007/BF00966954.
  8. Lebedev, V. I.; A. L. Skorokhodov (1992). "Quadrature formulas of orders 41, 47, and 53 for the sphere". Russian Acad. Sci. Dokl. Math. 45: 587–592.
  9. Lebedev, V. I. (1995). "A quadrature formula for the sphere of 59th algebraic order of accuracy". Russian Acad. Sci. Dokl. Math. 50: 283–286.
  10. Lebedev, V. I.; D. N. Laikov (1999). "A quadrature formula for the sphere of the 131st algebraic order of accuracy". Doklady Mathematics. 59 (3): 477–481.

External links

Numerical integration
Newton–Cotes formulas
Gaussian quadrature
Other
Category: