1146:"Local" adaptive quadrature makes the acceptable error for a given interval proportional to the length of that interval. This criterion can be difficult to satisfy if the integrands are badly behaved at only a few points, for example with a few step discontinuities. Alternatively, one could require only that the sum of the errors on each of the subintervals be less than the user's requirement. This would be "global" adaptive quadrature. Global adaptive quadrature can be more efficient (using fewer evaluations of the integrand) but is generally more complex to program and may require more working space to record information on the current set of intervals.
22:
133:
using static quadrature rules on adaptively refined subintervals of the region of integration. Generally, adaptive algorithms are just as efficient and effective as traditional algorithms for "well behaved" integrands, but are also effective for "badly behaved" integrands for which traditional
1116:
Some quadrature algorithms generate a sequence of results which should approach the correct value. Otherwise one can use a "null rule" which has the form of the above quadrature rule, but whose value would be zero for a simple integrand (for example, if the integrand were a polynomial of the
723:
583:
281:
1092:
429:(line 4), the interval is subdivided (line 5) and the quadrature is applied on both halves separately (line 6). Either the initial estimate or the sum of the recursively computed halves is returned (line 7).
995:
499:
206:
877:
605:
407:
814:
780:
753:
427:
909:
355:
127:
51:
1108:
An algorithm may elect to use different quadrature methods on different subintervals, for example using a high-order method only where the integrand is smooth.
326:
387:
1295:
510:
211:
1258:
1277:
1102:
917:
1010:
1217:
1155:
73:
933:
442:
152:
1001:
924:
1166:
786:
718:{\displaystyle Q_{n}\quad =\quad \sum _{i=0}^{n}w_{i}f(x_{i})\quad \approx \quad \int _{a}^{b}f(x)\,\mathrm {d} x}
1204:
34:
822:
1124:
44:
38:
30:
130:
98:
55:
1191:
1259:
John R. Rice. A Metalgorithm for
Adaptive Quadrature. Journal of the ACM 22(1) pp 61-82 (January 1975).
433:
90:
1128:
1098:
297:
5. m = (a + b) / 2 6. Q = integrate(f, a, m, Ď„/2) + integrate(f, m, b, Ď„/2) 7.
392:
1231:
1160:
1273:
1247:
1239:
1221:
792:
758:
731:
412:
885:
331:
103:
1195:
311:
360:
1289:
1213:
591:
There are several variants of this scheme. The most common will be discussed later.
578:{\displaystyle \varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,\mathrm {d} x\right|,}
1265:
916:
276:{\displaystyle \varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,\mathrm {d} x\right|}
588:
and the logic for deciding which interval to subdivide, and when to terminate.
1251:
1243:
1235:
1226:
1199:
1172:
94:
409:(line 3). If the estimated error is larger than the required tolerance
1087:{\displaystyle x_{i}=\cos \left({\frac {2(i+0.5)}{n+1}}\pi \right).}
1200:"Algorithm 145: Adaptive numerical integration by Simpson's rule"
1264:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007),
15:
990:{\displaystyle x_{i}=\cos \left({\frac {2i}{n}}\pi \right).}
494:{\displaystyle Q\approx \int _{a}^{b}f(x)\,\mathrm {d} x,}
201:{\displaystyle Q\approx \int _{a}^{b}f(x)\,\mathrm {d} x}
1175:, a FORTRAN library that uses global adaptive quadrature
1272:(3rd ed.), New York: Cambridge University Press,
1013:
936:
888:
825:
795:
761:
734:
608:
513:
445:
415:
395:
363:
334:
314:
214:
155:
106:
389:is computed (line 2), as well as an error estimate
1270:Numerical Recipes: The Art of Scientific Computing
1086:
989:
911:has been evaluated can be re-used upon recursion:
903:
871:
808:
774:
747:
717:
577:
493:
421:
401:
381:
349:
320:
275:
200:
121:
43:but its sources remain unclear because it lacks
142:Adaptive quadrature follows the general scheme
882:When such rules are used, the points at which
599:The quadrature rules generally have the form
8:
872:{\displaystyle x_{i}=a+{\frac {b-a}{n}}i.}
1225:
1038:
1018:
1012:
961:
941:
935:
887:
845:
830:
824:
800:
794:
789:of even degree are used, where the nodes
766:
760:
739:
733:
707:
706:
688:
683:
665:
649:
639:
628:
613:
607:
559:
558:
540:
535:
512:
480:
479:
461:
456:
444:
414:
394:
362:
333:
313:
260:
259:
241:
236:
213:
190:
189:
171:
166:
154:
105:
74:Learn how and when to remove this message
1169:for an example of adaptive quadrature
7:
816:are evenly spaced in the interval:
1296:Numerical integration (quadrature)
1266:"Section 4.7. Adaptive Quadrature"
1156:Adaptive numerical differentiation
708:
560:
481:
261:
191:
14:
432:The important components are the
1097:Other quadrature rules, such as
927:, where the nodes are chosen as
923:A similar strategy is used with
915:
149:integrate ( f, a, b, Ď„ ) 2.
20:
678:
674:
623:
619:
1056:
1044:
898:
892:
703:
697:
671:
658:
555:
549:
476:
470:
376:
364:
344:
338:
256:
250:
186:
180:
116:
110:
1:
402:{\displaystyle \varepsilon }
782:are generally precomputed.
1312:
925:Clenshaw–Curtis quadrature
1205:Communications of the ACM
1167:Adaptive Simpson's method
1125:Richardson extrapolation
1103:Gauss-Kronrod quadrature
29:This article includes a
58:more precise citations.
1088:
991:
905:
873:
810:
785:In the simplest case,
776:
749:
719:
644:
579:
495:
423:
403:
383:
351:
322:
277:
202:
123:
1227:10.1145/355580.369102
1117:appropriate degree).
1089:
992:
906:
874:
811:
809:{\displaystyle x_{i}}
787:Newton–Cotes formulas
777:
775:{\displaystyle w_{i}}
750:
748:{\displaystyle x_{i}}
720:
624:
580:
496:
424:
422:{\displaystyle \tau }
404:
384:
352:
323:
278:
203:
134:algorithms may fail.
124:
91:numerical integration
1105:, may also be used.
1011:
934:
904:{\displaystyle f(x)}
886:
823:
793:
759:
732:
606:
511:
504:the error estimator
443:
413:
393:
361:
350:{\displaystyle f(x)}
332:
312:
212:
153:
122:{\displaystyle f(x)}
104:
93:method in which the
1099:Gaussian quadrature
693:
545:
466:
328:to the integral of
246:
176:
87:Adaptive quadrature
1161:Adaptive step size
1084:
987:
901:
869:
806:
772:
745:
715:
679:
575:
531:
491:
452:
419:
399:
379:
357:over the interval
347:
318:
273:
232:
198:
162:
119:
31:list of references
1279:978-0-521-88068-8
1194:(December 1962).
1192:McKeeman, William
1142:Subdivision logic
1137:Epsilon algorithm
1071:
974:
861:
321:{\displaystyle Q}
308:An approximation
84:
83:
76:
1303:
1282:
1255:
1229:
1129:Romberg's method
1112:Error estimation
1093:
1091:
1090:
1085:
1080:
1076:
1072:
1070:
1059:
1039:
1023:
1022:
1002:Fejér quadrature
996:
994:
993:
988:
983:
979:
975:
970:
962:
946:
945:
919:
910:
908:
907:
902:
878:
876:
875:
870:
862:
857:
846:
835:
834:
815:
813:
812:
807:
805:
804:
781:
779:
778:
773:
771:
770:
754:
752:
751:
746:
744:
743:
728:where the nodes
724:
722:
721:
716:
711:
692:
687:
670:
669:
654:
653:
643:
638:
618:
617:
584:
582:
581:
576:
571:
567:
563:
544:
539:
500:
498:
497:
492:
484:
465:
460:
428:
426:
425:
420:
408:
406:
405:
400:
388:
386:
385:
382:{\displaystyle }
380:
356:
354:
353:
348:
327:
325:
324:
319:
282:
280:
279:
274:
272:
268:
264:
245:
240:
207:
205:
204:
199:
194:
175:
170:
128:
126:
125:
120:
79:
72:
68:
65:
59:
54:this article by
45:inline citations
24:
23:
16:
1311:
1310:
1306:
1305:
1304:
1302:
1301:
1300:
1286:
1285:
1280:
1263:
1196:Gotlieb, Calvin
1190:
1187:
1182:
1152:
1144:
1114:
1060:
1040:
1037:
1033:
1014:
1009:
1008:
963:
960:
956:
937:
932:
931:
884:
883:
847:
826:
821:
820:
796:
791:
790:
762:
757:
756:
735:
730:
729:
661:
645:
609:
604:
603:
597:
524:
520:
509:
508:
441:
440:
411:
410:
391:
390:
359:
358:
330:
329:
310:
309:
306:
225:
221:
210:
209:
151:
150:
140:
102:
101:
80:
69:
63:
60:
49:
35:related reading
25:
21:
12:
11:
5:
1309:
1307:
1299:
1298:
1288:
1287:
1284:
1283:
1278:
1261:
1256:
1208:(Periodical).
1186:
1183:
1181:
1178:
1177:
1176:
1170:
1164:
1158:
1151:
1148:
1143:
1140:
1139:
1138:
1135:
1132:
1113:
1110:
1095:
1094:
1083:
1079:
1075:
1069:
1066:
1063:
1058:
1055:
1052:
1049:
1046:
1043:
1036:
1032:
1029:
1026:
1021:
1017:
998:
997:
986:
982:
978:
973:
969:
966:
959:
955:
952:
949:
944:
940:
921:
920:
900:
897:
894:
891:
880:
879:
868:
865:
860:
856:
853:
850:
844:
841:
838:
833:
829:
803:
799:
769:
765:
742:
738:
726:
725:
714:
710:
705:
702:
699:
696:
691:
686:
682:
677:
673:
668:
664:
660:
657:
652:
648:
642:
637:
634:
631:
627:
622:
616:
612:
596:
593:
586:
585:
574:
570:
566:
562:
557:
554:
551:
548:
543:
538:
534:
530:
527:
523:
519:
516:
502:
501:
490:
487:
483:
478:
475:
472:
469:
464:
459:
455:
451:
448:
418:
398:
378:
375:
372:
369:
366:
346:
343:
340:
337:
317:
271:
267:
263:
258:
255:
252:
249:
244:
239:
235:
231:
228:
224:
220:
217:
197:
193:
188:
185:
182:
179:
174:
169:
165:
161:
158:
144:
139:
138:General scheme
136:
118:
115:
112:
109:
82:
81:
39:external links
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
1308:
1297:
1294:
1293:
1291:
1281:
1275:
1271:
1267:
1262:
1260:
1257:
1253:
1249:
1245:
1241:
1237:
1233:
1228:
1223:
1219:
1215:
1211:
1207:
1206:
1201:
1197:
1193:
1189:
1188:
1184:
1179:
1174:
1171:
1168:
1165:
1162:
1159:
1157:
1154:
1153:
1149:
1147:
1141:
1136:
1133:
1130:
1126:
1123:
1122:
1121:
1118:
1111:
1109:
1106:
1104:
1100:
1081:
1077:
1073:
1067:
1064:
1061:
1053:
1050:
1047:
1041:
1034:
1030:
1027:
1024:
1019:
1015:
1007:
1006:
1005:
1003:
984:
980:
976:
971:
967:
964:
957:
953:
950:
947:
942:
938:
930:
929:
928:
926:
918:
914:
913:
912:
895:
889:
866:
863:
858:
854:
851:
848:
842:
839:
836:
831:
827:
819:
818:
817:
801:
797:
788:
783:
767:
763:
740:
736:
712:
700:
694:
689:
684:
680:
675:
666:
662:
655:
650:
646:
640:
635:
632:
629:
625:
620:
614:
610:
602:
601:
600:
594:
592:
589:
572:
568:
564:
552:
546:
541:
536:
532:
528:
525:
521:
517:
514:
507:
506:
505:
488:
485:
473:
467:
462:
457:
453:
449:
446:
439:
438:
437:
435:
430:
416:
396:
373:
370:
367:
341:
335:
315:
304:
300:
296:
293:
289:
286:
269:
265:
253:
247:
242:
237:
233:
229:
226:
222:
218:
215:
195:
183:
177:
172:
167:
163:
159:
156:
148:
143:
137:
135:
132:
113:
107:
100:
96:
92:
88:
78:
75:
67:
57:
53:
47:
46:
40:
36:
32:
27:
18:
17:
1269:
1209:
1203:
1145:
1119:
1115:
1107:
1096:
999:
922:
881:
784:
755:and weights
727:
598:
590:
587:
503:
436:rule itself
431:
307:
302:
298:
294:
291:
287:
284:
146:
141:
131:approximated
86:
85:
70:
61:
50:Please help
42:
1220:: 604–605.
595:Basic rules
64:August 2019
56:introducing
1252:1011805770
1185:References
1134:Null rules
1127:(see also
434:quadrature
1244:0001-0782
1236:1557-7317
1074:π
1031:
1004:is used,
1000:Or, when
977:π
954:
852:−
681:∫
676:≈
626:∑
533:∫
529:−
518:≈
515:ε
454:∫
450:≈
417:τ
397:ε
234:∫
230:−
219:≈
216:ε
164:∫
160:≈
147:procedure
1290:Category
1214:New York
1173:QUADPACK
1150:See also
99:function
95:integral
1198:(ed.).
301:8.
283:4.
208:3.
52:improve
1276:
1250:
1242:
1234:
1212:(12).
1163:in ODE
303:return
1232:eISSN
1180:Notes
1120:See:
299:endif
290:>
97:of a
89:is a
37:, or
1274:ISBN
1248:OCLC
1240:ISSN
295:then
1222:doi
1218:ACM
1101:or
1054:0.5
1028:cos
951:cos
145:1.
129:is
1292::
1268:,
1246:.
1238:.
1230:.
1216::
1202:.
305:Q
285:if
41:,
33:,
1254:.
1224::
1210:5
1131:)
1082:.
1078:)
1068:1
1065:+
1062:n
1057:)
1051:+
1048:i
1045:(
1042:2
1035:(
1025:=
1020:i
1016:x
985:.
981:)
972:n
968:i
965:2
958:(
948:=
943:i
939:x
899:)
896:x
893:(
890:f
867:.
864:i
859:n
855:a
849:b
843:+
840:a
837:=
832:i
828:x
802:i
798:x
768:i
764:w
741:i
737:x
713:x
709:d
704:)
701:x
698:(
695:f
690:b
685:a
672:)
667:i
663:x
659:(
656:f
651:i
647:w
641:n
636:0
633:=
630:i
621:=
615:n
611:Q
573:,
569:|
565:x
561:d
556:)
553:x
550:(
547:f
542:b
537:a
526:Q
522:|
489:,
486:x
482:d
477:)
474:x
471:(
468:f
463:b
458:a
447:Q
377:]
374:b
371:,
368:a
365:[
345:)
342:x
339:(
336:f
316:Q
292:Ď„
288:ε
270:|
266:x
262:d
257:)
254:x
251:(
248:f
243:b
238:a
227:Q
223:|
196:x
192:d
187:)
184:x
181:(
178:f
173:b
168:a
157:Q
117:)
114:x
111:(
108:f
77:)
71:(
66:)
62:(
48:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
