Engineering Analysis ENG 3420 Fall 2009Lecture 25Search algorithmsSorting algorithmsSorting algorithms (cont’d)IntegrationNewton-Cotes formulasTrapezoidal ruleError of the trapezoidal ruleComposite trapezoidal ruleSimpson’s rulesSimpson’s 1/3 ruleError of Simpson’s 1/3 ruleComposite Simpson’s 1/3 ruleSimpson’s 3/8 ruleHigher-order formulasIntegration with unequal segmentsIntegration with unequal segmentsBuilt-in functionsMultiple Integrals1Engineering Analysis ENG 3420 Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 11:00-12:00222Lecture 25Lecture 25 Attention: The last homework HW5 and the last project are due on Tuesday November 24!! Last time:  Cubic splines Today Searching and sorting Numerical integration (chapter 17) Next Time Numerical integration of functions (chapter 18).3Search algorithms Find an element of a set based upon some search criteria. Linear search: Compare each element of the set with the “target” Requires O(n) operations if the set of n elements is not sorted Binary search: Can be done only when the list is sorted. Requires O(log(n)) comparisons. Algorithm: Check the middle element. If the middle element is equal to the sought value, then the position has been found;  Otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element.4Sorting algorithms Algorithms that puts elements of a list in a certain order, e.g., numerical order and lexicographical order. Input: a list of n unsorted elements.  Output: the list sorted in increasing order. Bubble sort Æ complexity: average O(n2); )); worst case O(n2). Compare each pair of elements; swap them if they are in the wrong order. Go again through the list until no swaps are necessary. Quick sort Æ complexity: average O(n log(n)); worst case O(n2). Pick an element, called a pivot, from the list. Reorder the list so that  all elements which are less than the pivot come before the pivot and  all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.5Sorting algorithms (cont’d) Merge sort – invented by John von Neumann:1. Complexity: average O(n log(n)); worst case O(n log(n)); 2. If the list is of length 0 or 1, then it is already sorted. Otherwise:3. Divide the unsorted list into two sublists of about half the size.4. Sort each sublist recursively by re-applying merge sort.5. Merge the two sublists back into one sorted list. Tournament sort:  Complexity: average O(n log(n)); worst case O(n log(n));  It imitates conducting a tournament in which two players play with each other.  Compare numbers in pairs, then form a temporary array with the winning elements.  Repeat this process until you get the greatest or smallest element based on your choice.6Integration Integration:is the total value, or summation, of f(x) dx over the range from a to b: I = fx()ab∫ dx7Newton-Cotes formulas Replace a function difficult or impossible to integrate analytically or tabulated data with a polynomial easy to integrate:fn(x) is an nthorder interpolating polynomial. The integrating function can be polynomials for any order - for example, (a) straight lines or (b) parabolas. The integral can be approximated in one step or in a series of steps to improve accuracy.I = fx()ab∫ dx ≅ fnx()ab∫ dx8Trapezoidal rule The trapezoidal rule is the first of the Newton-Cotes closed integration formulas; it uses a straight-line approximation for the function:I = fnx()ab∫ dxI = f (a)+fb()− fa()b − ax − a()⎡ ⎣ ⎢ ⎤ ⎦ ⎥ ab∫ dxI = b − a()fa()+ fb()29Error of the trapezoidal rule An estimate for the local truncation error of a single application of the trapezoidal rule is:where ξ is somewhere between aand b. This formula indicates that the error is dependent upon the curvature of the actual function as well as the distance between the points. Error can thus be reduced by breaking the curve into parts.Et=−112′ ′ f ξ()b − a()310Composite trapezoidal rule Assuming n+1 data points are evenly spaced, there will be n intervals over which to integrate. The total integral can be calculated by integrating each subinterval and then adding them together: I = fnx()x0xn∫ dx = fnx()x0x1∫ dx + fnx()x1x2∫ dx +L + fnx()xn−1xn∫ dxI = x1− x0()fx0()+ fx1()2+ x2− x1()fx1()+ fx2()2+L+ xn− xn−1()fxn−1()+ fxn()2I =h2fx0()+ 2 fxi()i =1n−1∑+ fxn()⎡ ⎣ ⎢ ⎤ ⎦ ⎥1112Simpson’s rules The error of the trapezoidal rule is related to the second derivative of the function. To improve the accuracy use (a) 2nd and (b) 3rd order polynomials; the results are called Simpson’s rules.13Simpson’s 1/3 rule Simpson’s 1/3 rule corresponds to using second-order polynomials. Using the Lagrange form for a quadratic fit of three points: Integration over the three points simplifies to:I = fnx()x0x2∫ dxI =h3fx0()+ 4 fx1()+ fx2()[]fnx()=x − x1()x0− x1()x − x2()x0− x2()fx0()+x−x0()x1− x0()x−x2()x1− x2()fx1()+x−x0()x2− x0()x−x1()x2− x1()fx2()14Error of Simpson’s 1/3 rule An estimate for the local truncation error of a single application of Simpson’s 1/3 rule is:where again ξ is somewhere between a and b. This formula indicates that the error is dependent upon the fourth-derivative of the actual function as well as the distance between the points. Note that the error is dependent on the fifth power of the step size (rather than the third for the trapezoidal rule).  Error can thus be reduced by breaking the curve into parts.Et=−12880f4()ξ()b − a()515Composite Simpson’s 1/3 rule Simpson’s 1/3 rule can be used on a set of subintervals in much the same way the trapezoidal rule was, except there must be an odd number of points. Because of the heavy weighting of the internal points, the formula is a little more complicated than for the trapezoidal rule: I = fnx()x0xn∫ dx = fnx()x0x2∫ dx + fnx()x2x4∫ dx +L+ fnx()xn−2xn∫ dxI =h3fx0()+ 4 fx1()+ fx2()[]+h3fx2()+ 4 fx3()+ fx4()[]+L+h3fxn−2()+ 4 fxn−1()+ fxn()[]I =h3fx0()+ 4 fxi()i=1i, oddn−1∑+ 2 fxi()j=2j, evenn−2∑+ fxn()⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥16Simpson’s 3/8 rule