Sélection de la méthode pour la quadrature numérique

12

Il existe plusieurs familles de méthodes pour la quadrature numérique. Si j'ai une classe spécifique d'intégrandes, comment choisir la méthode idéale?

Quelles sont les questions pertinentes à poser à la fois sur l'intégrande (par exemple, est-elle fluide? A-t-elle des singularités?) Et sur le problème de calcul (par exemple, tolérance aux erreurs, budget de calcul)?

Comment les réponses à ces questions excluent-elles ou promeuvent-elles les différentes familles de méthodes? Pour plus de simplicité, considérons uniquement les intégrales simples ou de faible dimension.

Par exemple, l'article de Wikipedia sur QUADPACK déclare que la QAGSroutine assez générale " utilise une quadrature adaptative globale basée sur une quadrature de Gauss-Kronrod à 21 points dans chaque sous-intervalle, avec une accélération par l'algorithme epsilon de Peter Wynn "

Comment cette décision a-t-elle été prise? Comment peut-on prendre des décisions similaires lorsque l'on en sait plus?

MRocklin
la source
1
Des informations probablement plus spécifiques sont nécessaires pour y répondre correctement. Il n'y a pas de critère unique, la quadrature gaussienne fonctionne souvent bien pour des problèmes très lisses tandis que d'autres quadratures peuvent être utilisées en présence de singularités douces. Mais si vous êtes périodique, un simple trapèze pourrait le couper.
Reid.Atcheson
2
@ Reid.Atcheson, je pense que vous répondez à la question en ce moment. Je ne demande pas quelle est la meilleure méthode, je demande quel genre de questions poseriez-vous et que vous diraient ces réponses? Comment aborder ces types de problèmes en général?
MRocklin

Réponses:

11

Tout d'abord, vous devez vous poser la question si vous avez besoin d'une routine de quadrature complète qui devrait prendre un intégrant comme une boîte noire. Si c'est le cas, vous ne pouvez qu'opter pour la quadrature adaptative où vous espérez que l'adaptabilité va attraper des points "difficiles" dans l'intégrande. Et c'est l'une des raisons pour lesquelles Piessens et al. a choisi une règle de Gauss-Kronrod (ce type de règle permet de calculer une approximation de l'intégrale et une estimation de l'erreur d'approximation en utilisant les mêmes évaluations de fonction) d'ordre modeste appliqué dans un schéma adaptatif (avec subdivision de l'intervalle avec le erreur la plus élevée) jusqu'à ce que les tolérances requises soient atteintes. L'algorithme Wynn-epsilon permet de fournir une accélération de convergence et aide généralement dans les cas où il y a des singularités de point final.

Mais si vous connaissez la «forme» ou le «type» de votre intégrande, vous pouvez adapter votre méthode à ce dont vous avez besoin afin que le coût de calcul soit limité pour la précision dont vous avez besoin. Donc, ce que vous devez regarder:

Integrand:

  • Lissage: peut-il être (bien) approximé par un polynôme d'une famille de polynômes orthogonaux (si c'est le cas, la quadrature gaussienne fera bien)
  • Singularités: l'intégrale peut-elle être divisée en intégrales avec uniquement des singularités de point final (si c'est le cas, la règle IMT ou la quadrature exponentielle double sera bonne sur chaque sous-intervalle)
  • Coût de calcul pour l'évaluation?
  • L'intégrande peut-elle être calculée? Ou seulement des données ponctuelles limitées sont-elles disponibles?
  • Intégrande hautement oscillatoire: recherchez les méthodes de type Levin.

Lorsqu'il s'agit de singularités, on préfère généralement qu'elles soient au point final des intégrales (voir IMT, double exponentielle). Si ce n'est pas le cas, on peut recourir à l'intégration Clenshaw-Curtis où vous capturez les singularités dans la fonction de poids. On définit généralement des formes de singularités comme et établit des expressions pour les poids de la quadrature en fonction de et . c α|xc|αcα

Intervalle d'intégration: fini, semi-infini ou infini. En cas d'intervalles semi-infinis ou infinis, peuvent-ils être réduits à un intervalle fini par une transformation variable? Sinon, les polynômes de Laguerre ou Hermite peuvent être utilisés dans l'approche de quadrature gaussienne.

Je n'ai pas de référence pour un véritable organigramme pour la quadrature en général, mais le livre QUADPACK (pas les pages de manuel Netlib, mais le vrai livre) a un organigramme pour sélectionner la routine appropriée en fonction de l'intégrale que vous souhaitez évaluer. Le livre décrit également les choix d'algorithmes effectués par Piessens et al. pour les différentes routines.

Pour les intégrales de faible dimension, on opte généralement pour la quadrature unidimensionnelle imbriquée. Dans le cas particulier des intégrales bidimensionnelles (cubature), il existe des règles d'intégration pour différents cas de domaines d'intégration. R. Cools a rassemblé un grand nombre de règles dans son Encyclopedia of cubature formules et est le principal auteur du paquet Cubpack . Pour les intégrales de grande dimension, on a généralement recours aux méthodes de type Monte Carlo. Cependant, il faut généralement un très grand nombre d'évaluations d'intégrandes pour obtenir une précision raisonnable. Pour les intégrales de faible dimension, les méthodes d'approximation comme quadrature / cubature / quadrature imbriquée surpassent souvent ces méthodes stochastiques.

Références générales intéressantes:

  1. Quadpack, Piessens, Robert; de Doncker-Kapenga, Elise; Überhuber, Christoph W .; Kahaner, David (1983). QUADPACK: Un package de sous-programme pour l'intégration automatique. Springer-Verlag. ISBN 978-3-540-12553-2
  2. Méthodes d'intégration numérique: deuxième édition, Ph. Davis et Ph. Rabinowitz, 2007, Dover Books on Mathematics, ISBN 978-0486453392
GertVdE
la source
1
Belle réponse. Pourquoi QUADPACK aurait-il choisi la méthode Gauss-Kronrod en 21 points en particulier? Pourquoi le nombre magique?
MRocklin
@MRocklin: Je suppose que c'était un bon compromis entre précision et efficacité: vous ne voulez pas surpasser votre règle de quadrature (coûteux) mais vous ne voulez pas qu'elle soit trop faible non plus (trop de subdivisions dans la partie adaptative ). Pour être complet: dans la routine QAG, l'utilisateur doit spécifier la règle de quadrature; dans le QAGS (avec extrapolation), la valeur par défaut est la règle des 21 points mais cela peut être annulé en utilisant la routine d'appel étendue QAGSE.
GertVdE
1
@GertVdE Très belle réponse en effet. Pouvez-vous élaborer sur l'utilisation de Clenshaw-Curtis pour capturer des singularités à mi-intervalle ou fournir des références? Je ne l'ai jamais entendu utilisé de cette façon auparavant, et je n'ai trouvé aucun détail à partir d'une recherche rapide sur Google. Je vous remercie!
OscarB
3
@OscarB: désolé pour le long retard, était sorti sans accès net (ah la belle vie). Voir le livre Quadpack §2.2.3.3 et plus loin; Branders, Piessens, «An extension of Clenshaw-Curtis quadrature», 1975, J.Comp.Appl.Math., 1, 55-65; Piessens, Branders, "L'évaluation et l'application de certains moments modifiés", 1973, BIT, 13, 443-450; Piessens, Branders, "Calcul des intégrales oscillantes", 1975, J.Comp.Appl.Math., 1, 153-164. Si vous effectuez une recherche documentaire sur "Robert Piessens" quelque part entre 1972 et 1980, vous trouverez de nombreux articles intéressants.
GertVdE