Quadratura de Clenshaw-Curtis: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m neteja i estandardització de codi |
||
Línia 1:
La '''quadratura de Clenshaw–Curtis''' i les '''quadratures de Fejer''' són mètodes d'[[integració numèrica]] basats en l'expansió de l'integrant en termes dels [[polinomis de Txebixev]]. Un resum breu de l'algoritme és el següent: la [[funció]] <math>f(x)</math> que s'ha d'integrar és avaluada als extrems o arrels dels polinomis de Txebixev i aquests valors es fan servir per construir una aproximació polinòmica de la funció; aquesta és integrada exactament per donar una aproximació de la integral exacta que busquem. El càlcul dels pesos d'integració es pot fer mitjançant una [[Transformada cosinus discreta|DCT]], que a través de la [[Transformada Ràpida de Fourier|FFT]] es poden obtenir amb <math> O(n \log n) </math> operacions.
== Introducció general ==
Línia 8:
== Fórmules explícites ==
Es poden obtenir fórmules explícites de la quadrature de Clenshaw-Curtis i de Fejer I i II. Tot i que són poc útils a nivell computacional, ja que fan falta <math>O(n^2)</math> operacions per calcular-los, tenen la seva importància teòrica i a nivell didàctic.
Linha 37 ⟶ 36:
==Connection to Chebyshev polynomials==
The reason that this is connected to the Chebyshev polynomials <math>T_k(x)</math> is that, by definition, <math>T_k(\cos\theta) = \cos(k\theta)</math>, and so the cosine series above is really an approximation of <math>f(x)</math> by Chebyshev polynomials:
Linha 47 ⟶ 45:
==Fejér quadrature==
[[Lipót Fejér|Fejér]] proposed two quadrature rules very similar to Clenshaw–Curtis quadrature, but much earlier (in 1933).<ref name=Fejer33>Leopold Fejér, "[http://projecteuclid.org/euclid.bams/1183496842 On the infinite sequences arising in the theories of harmonic analysis, of interpolation, and of mechanical quadratures]", ''Bulletin of the American Mathematical Society'' '''39''' (1933), pp. 521–534. Leopold Fejér, "[http://www.digizeitschriften.de/resolveppn/GDZPPN002374498 Mechanische Quadraturen mit positiven Cotesschen Zahlen], ''Mathematische Zeitschrift'' '''37''', 287 (1933).</ref>
Linha 61 ⟶ 58:
==Comparison to Gaussian quadrature==
The classic method of [[Gaussian quadrature]] evaluates the integrand at <math>N+1</math> points and is constructed to ''exactly'' integrate polynomials up to [[degree of a polynomial|degree]] <math>2N+1</math>. In contrast, Clenshaw–Curtis quadrature, above, evaluates the integrand at <math>N+1</math> points and exactly integrates polynomials only up to degree <math>N</math>. It may seem, therefore, that Clenshaw–Curtis is intrinsically worse than Gaussian quadrature, but in reality this does not seem to be the case.
Linha 69 ⟶ 65:
==Integration with weight functions==
More generally, one can pose the problem of integrating an arbitrary <math>f(x)</math> against a fixed ''weight function'' <math>w(x)</math> that is known ahead of time:
Linha 89 ⟶ 84:
==Integration on infinite and semi-infinite intervals==
It is also possible to use Clenshaw–Curtis quadrature to compute integrals of the form <math>\int_0^\infty f(x) dx</math> and <math>\int_{-\infty}^\infty f(x) dx</math>, using a coordinate-remapping technique.<ref name=Boyd87>John P. Boyd, "Exponentially convergent Fourier–Chebshev <nowiki>[</nowiki>''sic''<nowiki>]</nowiki> quadrature schemes on bounded and infinite intervals," ''J. Scientific Computing'' '''2''' (2), p. 99-109 (1987).</ref> High accuracy, even exponential convergence for smooth integrands, can be retained as long as <math>f(x)</math> decays sufficiently quickly as |''x''| approaches infinity.
Linha 102 ⟶ 96:
:<math>\int_0^\infty f(x) dx = 2L \int_0^\pi \frac{f[L \cot^2(\theta/2)]}{[1 - \cos(\theta)]^2} \sin(\theta)d\theta .</math>
The factor multiplying sin(θ), ''f''(...)/(...)<sup>2</sup>, can then be expanded in a cosine series (approximately, using the discrete cosine transform) and integrated term-by-term, exactly as was done for ''f''(cos θ) above. To eliminate the singularity at θ=0 in this integrand, one merely requires that ''f''(''x'') go to zero sufficiently fast as ''x'' approaches infinity, and in particular ''f''(''x'') must decay at least as fast as 1/''x''<sup>3/2</sup>.<ref name=Boyd87/>
For a doubly infinite interval of integration, one can use the coordinate remapping <math>x = L\cot(\theta)</math> (where ''L'' is a user-specified constant as above) to transform the integral into:<ref name=Boyd87/>
Linha 114 ⟶ 108:
==Precomputing the quadrature weights==
In practice, it is inconvenient to perform a DCT of the sampled function values ''f''(cosθ) for each new integrand. Instead, one normally precomputes quadrature weights <math>w_n</math> (for ''n'' from 0 to ''N''/2, assuming that ''N'' is even) so that
Linha 152 ⟶ 145:
==See also==
* [[Euler–Maclaurin formula]]
* [[Gauss–Kronrod quadrature formula]]
-->
== Referències ==
{{Referències}}
| |||