{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Times" 0 14 0 0 0 1 2 1 2 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "Courier" 0 11 0 0 0 1 2 1 2 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 0 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Unit 8: Numerical Methods " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Chapt er 43: Numeric Integration" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "Section 43.4: adaptive quadrature" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 9 "Copyright" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "C opyright * 2001 by Addison Wesley Longman, Inc." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 302 "All rights reserved. No part of this publication may be reproduced, stored in a retrieval sys tem, or transmitted, in any form or by any means, electronic, mechanic al, photocopying, recording, or otherwise, without the prior written p ermission of the publisher. Printed in the United States of America." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 15 "Initializations" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "with(linalg):\nwith(studen t):\nread(`pvac.txt`):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Motivation" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "Suppose Simpson' s rule requires " }{XPPEDIT 18 0 "n+1" "6#,&%\"nG\"\"\"F%F%" }{TEXT -1 32 " points to evaluate the integral" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "Lambda = Int(f(x ),x=a..b)" "6#/%'LambdaG-%$IntG6$-%\"fG6#%\"xG/F+;%\"aG%\"bG" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "to an accuracy \+ of " }{XPPEDIT 18 0 "epsilon" "6#%(epsilonG" }{TEXT -1 54 ". It may w ell be that in one portion of the interval " }{XPPEDIT 18 0 "[a,b]" "6 #7$%\"aG%\"bG" }{TEXT -1 14 " the function " }{XPPEDIT 18 0 "f(x)" "6# -%\"fG6#%\"xG" }{TEXT -1 134 " varies more rapidly than in another, so that the number of function evaluations is actually being determined \+ by only a small part of " }{XPPEDIT 18 0 "[a,b]" "6#7$%\"aG%\"bG" } {TEXT -1 74 ". If so, it might be more efficient to integrate over ea ch subsection of " }{XPPEDIT 18 0 "[a,b]" "6#7$%\"aG%\"bG" }{TEXT -1 143 ", each time using just enough points appropriate for that subsect ion. Perhaps the total number of function evaluations can thereby be \+ reduced." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "By way of illustration, consider the function" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "f := cosh(s qrt(1+x+2*x^2));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "and the definite integral" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Lambda := Int(f,x=-2..3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "which evaluates to" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "lambda := evalf(Lambda);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Using Simpson's rule t o approximate " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 31 " w ith an error no greater than " }{XPPEDIT 18 0 "10^(-4)" "6#)\"#5,$\"\" %!\"\"" }{TEXT -1 71 " takes 51 function-evaluations, as seen from the following computation." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "for k from 24 to 25 do\nevalf(simps on(f,x=-2..3,2*k)-lambda);\nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "With " }{XPPEDIT 18 0 " n=48" "6#/%\"nG\"#[" }{TEXT -1 41 ", the error is still too large, but with " }{XPPEDIT 18 0 "n=50" "6#/%\"nG\"#]" }{TEXT -1 94 ", so the to tal number of function-evaluations is 51, the error drops under the re quired bound." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "Suppose we split the interval " }{XPPEDIT 18 0 "[-2,3]" " 6#7$,$\"\"#!\"\"\"\"$" }{TEXT -1 47 " exactly in half, forming the two subintervals " }{XPPEDIT 18 0 "[-2,1/2]" "6#7$,$\"\"#!\"\"*&\"\"\"F(F %F&" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "[1/2,3]" "6#7$*&\"\"\"F%\"\"# !\"\"\"\"$" }{TEXT -1 86 ", then integrate separately over the two sub intervals, permitting an error of at most " }{XPPEDIT 18 0 "epsilon/2= .5*x*10^(-4)" "6#/*&%(epsilonG\"\"\"\"\"#!\"\"*($\"\"&F(F&%\"xGF&)\"#5 ,$\"\"%F(F&" }{TEXT -1 64 " on each subinterval. On each subinterval \+ we have the integrals" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "Lambda[1] := Int(f,x=-2..1/2);\nLam bda[2] := Int(f,x=1/2..3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "whose values are, respecti vely," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "lambda[1] := evalf(Lambda[1]);\nlambda[2] := evalf(La mbda[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 146 "To determine the number of function-eval uations needed by Simpson's rule on each subinterval, perform the foll owing calculations. To approximate " }{XPPEDIT 18 0 "Lambda[1]" "6#&% 'LambdaG6#\"\"\"" }{TEXT -1 8 ", obtain" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "for k from 8 to 9 do\n Left_error[2*k] := evalf(simpson(f,x=-2..1/2,2*k)-lambda[1]);\nod;" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "so that 19 function-evaluations are needed to make the er ror smaller than " }{XPPEDIT 18 0 "epsilon/2=.5*x*10^(-4)" "6#/*&%(eps ilonG\"\"\"\"\"#!\"\"*($\"\"&F(F&%\"xGF&)\"#5,$\"\"%F(F&" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "To \+ approximate " }{XPPEDIT 18 0 "Lambda[2]" "6#&%'LambdaG6#\"\"#" }{TEXT -1 8 ", obtain" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 88 "for k from 14 to 15 do\nRight_error[2*k] := ev alf(simpson(f,x=1/2..3,2*k)-lambda[2]);\nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "so that \+ 31 function-evaluations are needed to make the error smaller than " } {XPPEDIT 18 0 "epsilon/2=.5*x*10^(-4)" "6#/*&%(epsilonG\"\"\"\"\"#!\" \"*($\"\"&F(F&%\"xGF&)\"#5,$\"\"%F(F&" }{TEXT -1 21 ". Hence, a total of " }{XPPEDIT 18 0 "19+31-1=49" "6#/,(\"#>\"\"\"\"#JF&F&!\"\"\"#\\" }{TEXT -1 166 " function-evaluations are needed with the interval-spli tting technique. (Since the two subintervals are contiguous, the func tion need be computed at the midpoint of " }{XPPEDIT 18 0 "[-2,3]" "6# 7$,$\"\"#!\"\"\"\"$" }{TEXT -1 77 " just once, not twice.) This is a \+ slight savings over the original tally of " }{XPPEDIT 18 0 "51" "6#\"# ^" }{TEXT -1 129 ", but our intent was merely to provide a motivation \+ for the interval-splitting that constitutes the adaptive quadrature st rategy." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 20 "Error-Test \+ Mechanism" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 184 "A key ingredient of an adaptive scheme is the error-test mechanism. In Section 4.1, in the context of numeric solutions of di fferential equations, we derived the error-test mechanism " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "y[exact]-y[approx](h/2)=(y[approx](h/2)-y[approx](h))/(2^k-1)" "6#/ ,&&%\"yG6#%&exactG\"\"\"-&F&6#%'approxG6#*&%\"hGF)\"\"#!\"\"F2*&,&-&F& 6#F-6#*&F0F)F1F2F)-&F&6#F-6#F0F2F),&)F1%\"kGF)F)F2F2" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "valid if the error in \+ " }{XPPEDIT 18 0 "y[approx]" "6#&%\"yG6#%'approxG" }{TEXT -1 4 " is " }{XPPEDIT 18 0 "O(h^k)" "6#-%\"OG6#)%\"hG%\"kG" }{TEXT -1 88 ". Thus, the error in the more accurate approximation (i.e., the one made with stepsize " }{XPPEDIT 18 0 "h/2" "6#*&%\"hG\"\"\"\"\"#!\"\"" }{TEXT -1 59 "), is measured by the difference between the more accurate " } {XPPEDIT 18 0 "``(h/2)" "6#-%!G6#*&%\"hG\"\"\"\"\"#!\"\"" }{TEXT -1 38 "-approximation, and the less-accurate " }{XPPEDIT 18 0 "h" "6#%\"h G" }{TEXT -1 31 "-approximation, all divided by " }{XPPEDIT 18 0 "2^k- 1" "6#,&)\"\"#%\"kG\"\"\"F'!\"\"" }{TEXT -1 97 ". This very calculati on was reviewed in Section 42.2 in the context of Richardson extrapola tion." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 " Since Simpson's composite rule is " }{XPPEDIT 18 0 "O(h^4)" "6#-%\"OG6 #*$%\"hG\"\"%" }{TEXT -1 68 ", the factor in the denominator of the er ror-test estimate would be " }{XPPEDIT 18 0 "2^4-1=15" "6#/,&*$\"\"#\" \"%\"\"\"F(!\"\"\"#:" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "We will show how the interval-splittin g strategy is coupled with this error-test expression to produce an ad aptive, or self-directed, numeric integration scheme." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 49 "Naive Maple Implementation of Ada ptive Quadrature" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 376 "We next sketch a naive implementation of an adaptiv e quadrature scheme based on Simpson's rule. Since its purpose is mer ely to illustrate the strategy, no attempt is made to minimize the num ber of function-evaluations. For the moment, we ignore the efficienci es that would accrue we saved all function-evaluations which get re-co mputed during the execution of our algorithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "We implement our algorith m in Maple, and use Maple's built-in " }{TEXT 256 7 "simpson" }{TEXT -1 160 " command, thereby ignoring the efficiencies that would be had \+ if we stored all function-evaluations which get re-computed during the execution of our algorithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "To evaluate the definite integral" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 260 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "Lambda=Int(f(x),x=a..b)" "6#/%'LambdaG-%$IntG6$-%\"fG6#%\"xG/F+;%\" aG%\"bG" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "we apply Simpson's rule with stepsize " }{XPPEDIT 18 0 "h=b-a" "6# /%\"hG,&%\"bG\"\"\"%\"aG!\"\"" }{TEXT -1 26 " and again, with stepsize " }{XPPEDIT 18 0 "h/2" "6#*&%\"hG\"\"\"\"\"#!\"\"" }{TEXT -1 65 ". T he first computation is done by invoking Simpson's rule with " } {XPPEDIT 18 0 "n=2" "6#/%\"nG\"\"#" }{TEXT -1 19 ", the second, with \+ " }{XPPEDIT 18 0 "n=4" "6#/%\"nG\"\"%" }{TEXT -1 46 ". As a consequen ce, we have two estimates of " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" } {TEXT -1 109 ", from which the error in the more accurate approximatio n can be determined by dividing the difference by 15." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "If the error is small \+ enough, we accept the more accurate " }{XPPEDIT 18 0 "``(h/2)" "6#-%!G 6#*&%\"hG\"\"\"\"\"#!\"\"" }{TEXT -1 48 "-approximation, and the compu tation is finished." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 67 "If the error is too large, the process is repeated on t he interval " }{XPPEDIT 18 0 "[a,(a+b)/2]" "6#7$%\"aG*&,&F$\"\"\"%\"bG F'F'\"\"#!\"\"" }{TEXT -1 20 ", with the interval " }{XPPEDIT 18 0 "[( a+b)/2,b]" "6#7$*&,&%\"aG\"\"\"%\"bGF'F'\"\"#!\"\"F(" }{TEXT -1 35 " s et aside in a last-in, first-out " }{TEXT 257 5 "stack" }{TEXT -1 351 ", for processing later. If the numeric approximation for the left-ha nd subinterval is acceptable, its value is stored, and the process rep eated on the right-hand subinterval. The accuracy demanded of any sub interval is proportional to the ratio of the length of the subinterval to the length of the original interval. If the over-all tolerance fo r " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 4 " is " } {XPPEDIT 18 0 "epsilon" "6#%(epsilonG" }{TEXT -1 46 ", then the permit ted error in any subinterval " }{XPPEDIT 18 0 "[alpha,beta]" "6#7$%&al phaG%%betaG" }{TEXT -1 4 " is " }{XPPEDIT 18 0 "epsilon" "6#%(epsilonG " }{TEXT -1 34 " times the ratio of the length of " }{XPPEDIT 18 0 "[a lpha,beta]" "6#7$%&alphaG%%betaG" }{TEXT -1 18 " to the length of " } {XPPEDIT 18 0 "[a,b]" "6#7$%\"aG%\"bG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 130 "To help follow the lo gic of this process, we define two functions. The first, performs two Simpson's rule integrations, one with " }{XPPEDIT 18 0 "n=2" "6#/%\"n G\"\"#" }{TEXT -1 14 " and one with " }{XPPEDIT 18 0 "n=4" "6#/%\"nG\" \"%" }{TEXT -1 34 ". The inputs to the function are " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 28 ", the integrand, and a list " } {XPPEDIT 18 0 "[alpha,beta]" "6#7$%&alphaG%%betaG" }{TEXT -1 229 " rep resenting the interval over which Simpson's rule is to be applied. Th e output of the function is a list of three numbers, the more accurate of the two Simpson's rule evaluations, the estimate of the error in t his value, and " }{XPPEDIT 18 0 "h=beta-alpha" "6#/%\"hG,&%%betaG\"\" \"%&alphaG!\"\"" }{TEXT -1 87 ", the length of the interval over which these two Simpson's rule evaluations were done." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 141 "INT := pro c(f,X)\nlocal S2,S4;\nS2 := evalf(simpson(f,x=X[1]..X[2],2));\nS4 := e valf(simpson(f,x=X[1]..X[2],4));\n[S4,(S4-S2)/15,X[2]-X[1]];\nend:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 133 "The second function we define performs the error-test. \+ Its input is the list output by the first function, and its output is \+ either " }{TEXT 258 4 "true" }{TEXT -1 4 " or " }{TEXT 259 5 "false" } {TEXT -1 27 ", depending on whether the " }{XPPEDIT 18 0 "``(h/2)" "6# -%!G6#*&%\"hG\"\"\"\"\"#!\"\"" }{TEXT -1 217 "-approximation is accura te enough or not. The accuracy demanded of any subinterval is proport ional to the ratio of the length of the subinterval to the length of t he original interval. If the over-all tolerance for " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 4 " is " }{XPPEDIT 18 0 "epsilon" "6# %(epsilonG" }{TEXT -1 46 ", then the permitted error in any subinterva l " }{XPPEDIT 18 0 "[alpha,beta]" "6#7$%&alphaG%%betaG" }{TEXT -1 4 " \+ is " }{XPPEDIT 18 0 "epsilon" "6#%(epsilonG" }{TEXT -1 34 " times the \+ ratio of the length of " }{XPPEDIT 18 0 "[alpha,beta]" "6#7$%&alphaG%% betaG" }{TEXT -1 18 " to the length of " }{XPPEDIT 18 0 "[a,b]" "6#7$% \"aG%\"bG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 "errorcheck := proc(Y)\nif abs(Y[2]) < abs(evalf(Y[3]*E/H)) then true else false;fi;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "To evaluate the integral " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "Lambda := Int(sqrt(3-x),x=-1 ..1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "we define the integrand as" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "f := integr and(Lambda);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "and execute the following Maple code in w hich " }{XPPEDIT 18 0 "[a,b]=[-1,1]" "6#/7$%\"aG%\"bG7$,$\"\"\"!\"\"F) " }{TEXT -1 6 ", and " }{XPPEDIT 18 0 "epsilon=10^(-8)" "6#/%(epsilonG )\"#5,$\"\")!\"\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 387 "A := -1:\nB := 1:\nH := B-A :\nE := 10^(-8):\nSigma := 0:\nL := [NULL]:\nP := [A,B]:\nN := 1:\nwhi le N>0 do\nOUT:=INT(f,P):\nif errorcheck(OUT) then Sigma := Sigma+OUT[ 1]:\n N := nops(L):\n if N>0 then P := L[N]; \n L := [seq(L[k],k=1..N-1)];\n fi;\nelse\n C := ( P[1]+P[2])/2:\n L := [op(L),[C,P[2]]]:\n P := [P[1],C]; \n N := nop s([L]):\nfi;\nod:\nprint(Sigma);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "That the val ue produced by this code is within the prescribed error bound, we comp ute the difference between " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" } {TEXT -1 47 " and the adaptive value stored in the variable " } {XPPEDIT 18 0 "Sigma" "6#%&SigmaG" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "evalf(Lambd a-Sigma);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "Modifying the code to accumulate and prin t lists of intervals, we obtain Table 43.13." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 861 "A := -1:\nB := 1 :\nH := B-A:\nE := 10^(-8):\nSigma := 0:\nPseq := NULL:\nLseq := NULL: \nIseq := NULL:\nL := [NULL]:\nP := [A,B]:\nPseq := Pseq,P:\nLseq := L seq,L:\nN := 1:\nwhile N>0 do\nOUT := INT(f,P):\nIseq := Iseq,errorche ck(OUT):\nif errorcheck(OUT) then Sigma := Sigma+OUT[1]:\n \+ N := nops(L):\n if N>0 then P := L[N]; \n \+ L := [seq(L[k],k=1..N-1)];\n Pseq := Pseq,P:\n \+ Lseq := Lseq,L:\n fi;\nelse\n C := (P[1]+P[2])/2:\n L := [op(L),[C,P[2]]]:\n P := [P[1],C];\n Pseq := Pseq,P:\n Lseq := Lse q,L: \n N := nops([L]):\nfi;\nod:\nIIseq := subs(true=`pass`,false=`f ail`,[Iseq]):\nM := augment([seq(k,k=1..nops([Iseq]))], vector([Pseq]) , vector([Lseq]), vector(IIseq)):\nstackmatrix([`row`,`Present`,`Prese nt`,`Integration Outcome`],[`index`,`Interval`,`Stack`,`on Present Int erval`],[``,``,``,``],M);\nprint(Sigma);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 420 "The left-han d column indexes the \"cycles\" executed by the code. The second colu mn lists the \"active interval,\" the interval over which integration \+ is presently taking place. The third column lists the contents of the stack, the pile of subintervals over which integration has yet to tak e place. The fourth column lists the outcome of the error-test applie d to the integration on the \"active interval.\" Where it says " } {TEXT 264 4 "pass" }{TEXT -1 113 ", the integration was accurate enoug h, and no further splitting of that interval need take place. Where i t says " }{TEXT 260 4 "fail" }{TEXT -1 207 ", the integration was not \+ accurate enough, and the \"active integral\" must be split in half, wi th the left-hand portion becoming the next \"active interval\" and the right-hand portion being added to the stack." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "Taking the computation fr om the start, we begin with " }{XPPEDIT 18 0 "[-1,1]" "6#7$,$\"\"\"!\" \"F%" }{TEXT -1 87 " as the active, or present, interval. Simpson's r ule is applied to this interval with " }{XPPEDIT 18 0 "h=2" "6#/%\"hG \"\"#" }{TEXT -1 6 ", and " }{XPPEDIT 18 0 "h/2=1" "6#/*&%\"hG\"\"\"\" \"#!\"\"F&" }{TEXT -1 14 ", by invoking " }{TEXT 261 7 "simpson" } {TEXT -1 6 " with " }{XPPEDIT 18 0 "n=2" "6#/%\"nG\"\"#" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "n=4" "6#/%\"nG\"\"%" }{TEXT -1 137 ", respectiv ely. As seen from Table 43.13, this first integration is not accurate enough, so the interval is split into the subintervals " }{XPPEDIT 18 0 "[-1,0]" "6#7$,$\"\"\"!\"\"\"\"!" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "[0,1]" "6#7$\"\"!\"\"\"" }{TEXT -1 3 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "In cycle 2, the active in terval is " }{XPPEDIT 18 0 "[-1,0]" "6#7$,$\"\"\"!\"\"\"\"!" }{TEXT -1 18 " and the interval " }{XPPEDIT 18 0 "[0,1]" "6#7$\"\"!\"\"\"" } {TEXT -1 90 " is placed on the stack. Again, integration over the act ive interval is done twice, with " }{XPPEDIT 18 0 "n=2,4" "6$/%\"nG\" \"#\"\"%" }{TEXT -1 256 ", respectively, in Simpson's rule. The outco me of the integrations is passed to the error-test, and again, the int egration over the active interval is not accurate enough. Hence, the \+ active interval is split again, this time into the new active interval " }{XPPEDIT 18 0 "[-1,-1/2]" "6#7$,$\"\"\"!\"\",$*&F%F%\"\"#F&F&" } {TEXT -1 19 ", and the interval " }{XPPEDIT 18 0 "[-1/2,0]" "6#7$,$*& \"\"\"F&\"\"#!\"\"F(\"\"!" }{TEXT -1 30 " which is placed on the stack ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "In c ycle 3, the active integral is " }{XPPEDIT 18 0 "[-1,-1/2]" "6#7$,$\" \"\"!\"\",$*&F%F%\"\"#F&F&" }{TEXT -1 51 ", and integration over it is performed twice, with " }{XPPEDIT 18 0 "n=2,4" "6$/%\"nG\"\"#\"\"%" } {TEXT -1 218 ", respectively, in Simpson's rule. The outcome of the t wo integrations is passed to the error-test, and again, the error is t oo large. Once again, the active interval is split, this time into th e new active interval " }{XPPEDIT 18 0 "[-1,-3/4]" "6#7$,$\"\"\"!\"\", $*&\"\"$F%\"\"%F&F&" }{TEXT -1 18 " and the interval " }{XPPEDIT 18 0 "[-3/4,-1/2]" "6#7$,$*&\"\"$\"\"\"\"\"%!\"\"F),$*&F'F'\"\"#F)F)" } {TEXT -1 30 " which is placed on the stack." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "In cycle 4, the active integral is " }{XPPEDIT 18 0 "[-1,-3/4]" "6#7$,$\"\"\"!\"\",$*&\"\"$F%\"\"%F&F &" }{TEXT -1 51 ", and integration over it is performed twice, with " }{XPPEDIT 18 0 "n=2,4" "6$/%\"nG\"\"#\"\"%" }{TEXT -1 153 ", respectiv ely, in Simpson's rule. The outcome of the two integrations is passed to the error-test, and finally, the error is deemed small enough. Th e " }{XPPEDIT 18 0 "n=4" "6#/%\"nG\"\"%" }{TEXT -1 145 " value produce d by Simpson's rule is accepted as the value of the integral over the \+ active interval, and this number is added to the accumulator " } {XPPEDIT 18 0 "Sigma" "6#%&SigmaG" }{TEXT -1 260 " which was initializ ed to 0 at the very start of the computation. No new subinterval is a dded to the stack. In fact, the last subinterval added to the stack a t the end of cycle 3 is now removed from the stack, and becomes the ne w active interval for cycle 5." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 161 "We leave it to the reader to continue th is exposition, cycle-by-cycle. Instead, we turn our attention to some final aspects of the logic leading to Table 43.13." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 131 "1. Each time integrat ion over a subinterval is deemed accurate enough for that value to be \+ \"kept,\" it is added to the accumulator " }{XPPEDIT 18 0 "Sigma" "6#% &SigmaG" }{TEXT -1 3 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 93 "2. The computation ends when integration over the present interval is accepted as accurate, " }{TEXT 262 3 "and" } {TEXT -1 320 " the stack is empty. Table 43.13 shows the stack is emp ty after cycles 8, 12, 14, and 16. However, the integration in cycles 9, 13, and 15 do not pass the error test, so the integration does not terminate. Only after cycle 16 does the next integration pass the er ror test, and that is when the integration terminates." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "3. When the integra tion process ends, the value accumulated in " }{XPPEDIT 18 0 "Sigma" " 6#%&SigmaG" }{TEXT -1 33 " is the desired approximation of " } {XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 1 "." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "4. To program a \"spli t\" of the active interval " }{XPPEDIT 18 0 "[alpha,beta]" "6#7$%&alph aG%%betaG" }{TEXT -1 23 ", compute its midpoint " }{XPPEDIT 18 0 "C=(a lpha+beta)/2" "6#/%\"CG*&,&%&alphaG\"\"\"%%betaGF(F(\"\"#!\"\"" } {TEXT -1 38 ", and form the right-hand subinterval " }{XPPEDIT 18 0 "[ C,beta]" "6#7$%\"CG%%betaG" }{TEXT -1 42 " before forming the left-han d subinterval " }{XPPEDIT 18 0 "[alpha,C]" "6#7$%&alphaG%\"CG" }{TEXT -1 6 ". If " }{XPPEDIT 18 0 "beta" "6#%%betaG" }{TEXT -1 21 " were ov erwritten by " }{XPPEDIT 18 0 "C" "6#%\"CG" }{TEXT -1 24 " first, the \+ subinterval " }{XPPEDIT 18 0 "[C,beta]" "6#7$%\"CG%%betaG" }{TEXT -1 22 " would be unavailable." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 31 "Minimizing Function-Evaluations" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 406 "It is highly inefficient to i nvoke a Simpson procedure twice for each cycle, and to invoke Simpson' s rule \"fresh\" for each subinterval. A little thought shows that re peated calls to Simpson's rule requires re-calculating function values . If we can determine where these function values are being used, and can determine a way to store them, the number of function-evaluations can be dramatically reduced." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 103 "In the example used to generate Table 43 .13, for the two initial integrations, the active interval was " } {XPPEDIT 18 0 "[-1,1]" "6#7$,$\"\"\"!\"\"F%" }{TEXT -1 42 ", so when S impson's rule was applied with " }{XPPEDIT 18 0 "n=2" "6#/%\"nG\"\"#" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 34 " was evaluated at the three nodes " }{XPPEDIT 18 0 "x=-1,0,1" "6%/%\" xG,$\"\"\"!\"\"\"\"!F&" }{TEXT -1 64 ". For that same interval, when \+ Simpson's rule was applied with " }{XPPEDIT 18 0 "n=4" "6#/%\"nG\"\"% " }{TEXT -1 2 ", " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 33 " was evaluated at the five nodes " }{XPPEDIT 18 0 "x=-1,-1/2,0,1/2 ,1" "6'/%\"xG,$\"\"\"!\"\",$*&F&F&\"\"#F'F'\"\"!*&F&F&F*F'F&" }{TEXT -1 45 ". However, only two of these nodes, namely, " }{XPPEDIT 18 0 " x" "6#%\"xG" }{TEXT -1 3 " = " }{TEXT 263 1 "+" }{TEXT -1 1 " " } {XPPEDIT 18 0 "1/2" "6#*&\"\"\"F$\"\"#!\"\"" }{TEXT -1 56 ", are new n odes. Hence, if we had stored the values of " }{XPPEDIT 18 0 "f(x)" " 6#-%\"fG6#%\"xG" }{TEXT -1 60 " at the first three nodes, we would hav e needed to evaluate " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 110 " at just two more nodes to complete the first cycle. The firs t cycle requires just five function-evaluations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 123 "The integrations in the \+ first cycle were not accurate enough, so the initial interval was spli t into the two subintervals, " }{XPPEDIT 18 0 "[-1,0]" "6#7$,$\"\"\"! \"\"\"\"!" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "[0,1]" "6#7$\"\"!\"\"\" " }{TEXT -1 72 ". Two new integrations were then performed in the new active interval, " }{XPPEDIT 18 0 "[-1,0]" "6#7$,$\"\"\"!\"\"\"\"!" } {TEXT -1 7 ". The " }{XPPEDIT 18 0 "n=2" "6#/%\"nG\"\"#" }{TEXT -1 51 " application of Simpson's rule required evaluating " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 20 " at the three nodes " } {XPPEDIT 18 0 "x=-1,-1/2,0" "6%/%\"xG,$\"\"\"!\"\",$*&F&F&\"\"#F'F'\" \"!" }{TEXT -1 163 ". Had we stored all function values computed in c ycle 1, we could have obtained this new Simpson's rule approximation w ithout computing new function values. The " }{XPPEDIT 18 0 "n=4" "6#/ %\"nG\"\"%" }{TEXT -1 51 " application of Simpson's rule required eval uating " }{XPPEDIT 18 0 "f(x)" "6#-%\"fG6#%\"xG" }{TEXT -1 19 " at the five nodes " }{XPPEDIT 18 0 "x=-1,-3/4,-1/2,-1/4,0" "6'/%\"xG,$\"\"\" !\"\",$*&\"\"$F&\"\"%F'F',$*&F&F&\"\"#F'F',$*&F&F&F+F'F'\"\"!" }{TEXT -1 50 ". However, only two of these five nodes, namely, " }{XPPEDIT 18 0 "x=-3/4,-1/4" "6$/%\"xG,$*&\"\"$\"\"\"\"\"%!\"\"F*,$*&F(F(F)F*F* " }{TEXT -1 94 " are new. It takes just two new function-evaluations \+ to complete the integrations in cycle 2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 229 "A similar analysis shows that aft er cycle 1 (which requires five function-evaluations), all subsequent \+ cycles can be completed with just two more function-evaluations each. \+ Thus, the 17 cycles we executed should have taken just " }{XPPEDIT 18 0 "5+2*x*16=37" "6#/,&\"\"&\"\"\"*(\"\"#F&%\"xGF&\"#;F&F&\"#P" } {TEXT -1 56 " function-evaluations. Had we used Simpson's rule with \+ " }{XPPEDIT 18 0 "n=36" "6#/%\"nG\"#O" }{TEXT -1 90 ", we would have e xpended the equivalent computational energy, and would have approximat ed " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 17 " with an erro r of" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "evalf(simpson(f,x=-1..1,36)-Lambda);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "50% more that the adaptive version's 0.2 x " }{XPPEDIT 18 0 "10 ^(-8)" "6#)\"#5,$\"\")!\"\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "However, for the function" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f := 1/x+x^2/(1+x^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 12 "the integral" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Lamb da := Int(f,x=1/10..5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "whose value is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "lambda :=evalf(Lambda);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "would require more cycles to obtai n " }{XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 28 " to within an \+ error of only " }{XPPEDIT 18 0 "10^(-4)" "6#)\"#5,$\"\"%!\"\"" }{TEXT -1 63 ". Indeed, modifying and re-executing our Maple code, we obtain " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 495 "A := 1/10:\nB := 5:\nH := B-A:\nE := 10^(-4):\nSigma := 0:\nm := 0:\nL := [NULL]:\nP := [A,B]:\nPseq := Pseq,P:\nLseq := L seq,L:\nN := 1:\nwhile N>0 do\nm := m+1:\nOUT := INT(f,P):\nif errorch eck(OUT) then Sigma := Sigma+OUT[1]:\n N := nop s(L):\n if N>0 then P := L[N]; \n L := [seq(L[k],k=1 ..N-1)];\n fi;\nelse\n C := (P[1]+P[2])/2:\n L := [op(L),[C,P[2]] ]:\n P := [P[1],C];\n N := nops([L]):\nfi;\nod:\nprint(`value of int egral = `,Sigma);\nprint(`number of cycles = `,m);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Thi s value for the integral is supposed to be accurate to within " } {XPPEDIT 18 0 "10^(-4)" "6#)\"#5,$\"\"%!\"\"" }{TEXT -1 28 ". The act ual error made is " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Sigma-lambda;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "which is with in the allowed tolerance." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 40 "With 27 cycles, we would need, at most, " } {XPPEDIT 18 0 "5+2*x*26=57" "6#/,&\"\"&\"\"\"*(\"\"#F&%\"xGF&\"#EF&F& \"#d" }{TEXT -1 110 " function-evaluations. If Simpson's rule were us ed with a uniform distribution of 57 nodes, we would compute " } {XPPEDIT 18 0 "Lambda" "6#%'LambdaG" }{TEXT -1 17 " with an error of" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "evalf(simpson(f,x=1/10..5,56)-lambda);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 258 "which is considerable less accurate than the value obtained by the adaptive version of Simpson's rule. In fact, to obtain a comparable accuracy \+ with a uniform Simpson's rule, we would need 205 function-evaluations, as verified by the following calculations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "evalf(simpson(f,x =1/10..5,202)-lambda);\nevalf(simpson(f,x=1/10..5,204)-lambda);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 34 "Adaptive Quadrature as a Procedure" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 107 "The following Map le code captures the adaptive quadrature algorithm as the unsophistica ted Maple procedure " }{TEXT 265 5 "adapt" }{TEXT -1 320 ". The input to the procedure is an expression representing the integrand of the d efinite integral being evaluated, the limits of integration, and an er ror tolerance. The output is a numeric approximation of the integral \+ with less than the prescribed error, the number of cycles, and the num ber of function-evaluations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 707 "adapt := proc(f,A,B,E)\nloc al H,Sigma,m,L,P,Pseq,Lseq,N,C,k,S2,S4,OUT;\nH := B-A:\nSigma := 0:\nm := 0:\nL := [NULL]:\nPseq:=NULL:\nLseq:=NULL:\nP := [A,B]:\nPseq := P seq,P:\nLseq := Lseq,L:\nN := 1:\nwhile N>0 do\nm := m+1:\nS2 := evalf (simpson(f,x=P[1]..P[2],2));\nS4 := evalf(simpson(f,x=P[1]..P[2],4)); \nOUT:=[S4,(S4-S2)/15,P[2]-P[1]];\nif abs(OUT[2]) < abs(evalf(OUT[3]*E /H)) then \nSigma := Sigma+OUT[1]:N := nops(L):\n if N>0 then P := \+ L[N]; \n L := [seq(L[k],k=1..N-1)];\n fi;\nelse\n C := (P[1]+P[2])/2:\n L := [op(L),[C,P[2]]]:\n P := [P[1],C];\n N := nops([L]):\nfi;\nod:\nprint(`value of integral = `,Sigma);\nprint(`nu mber of cycles = `,m);\nprint(`number of function-evaluations = `,(m-1 )*2+5);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Applying the procedure adapt to th e definite integral " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Lambda;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "via the synta x" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "adapt(f,1/10,5,10^(-4));" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "gives the s ame results obtained earlier." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "1" 0 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }