Engineering Analysis ENG 3420 Fall 2009 Dan C Marinescu Office HEC 439 B Office hours Tu Th 11 00 12 00 1 Lecture 24 Attention The last homework HW5 and the last project are due on Tuesday November 24 Last time Lagrange interpolating polynomials Splines Today Cubic splines Searching and sorting Numerical integration chapter 17 Next Time Numerical integration Lecture 24 2 Cubic splines Cubic splines the simplest representation with the appearance of smoothness and without the problems of higher order polynomials Linear splines have discontinuous first derivatives Quadratic splines have discontinuous second derivatives and require setting the second derivative at some point to a pre determined value Quartic or higher order splines tend to exhibit ill conditioning or oscillations The cubic spline function for the ith interval can be written as s i x ai bi x xi ci x xi di x xi 2 3 For n data points there are n 1 intervals and thus 4 n 1 unknowns to evaluate to solve all the spline function coefficients 3 Conditions to determine the spline coefficients The first condition the spline function goes through the first and last point of the interval this leads to 2 n 1 equations s i xi fi ai fi s i xi 1 fi s i xi 1 ai bi xi 1 xi ci xi 1 xi di xi 1 xi fi 2 3 The second condition the first derivative should be continuous at each interior point this leads to n 2 equations si xi 1 si 1 xi 1 bi 2ci xi 1 xi 3di xi 1 xi bi 1 2 The third condition the second derivative should be continuous at each interior point this leads to n 2 equations si xi 1 si 1 xi 1 2ci 6di xi 1 xi 2ci 1 So far we have 4n 6 equations we need 4n 4 equations 4 Two additional equations There are several options for the final two equations Natural end conditions the second derivative at the end knots are zero Clamped end conditions the first derivatives at the first and last knots are known Not a knot end conditions force continuity of the third derivative at the second and penultimate points results in the first two intervals having the same spline function and the last two intervals having the same spline function 5 Built in functions for piecewise interpolation MATLAB has several built in functions to implement piecewise interpolation spline yy spline x y xx Performs cubic spline interpolation generally using not a knot conditions If y contains two more values than x has entries then the first and last value in y are used as the derivatives at the end points i e clamped Example Generate data x linspace 1 1 9 y 1 1 25 x 2 Calculate 100 model points and determine not a knot interpolation xx linspace 1 1 yy spline x y xx Calculate actual function values at model points and data points the 9 point not a knot interpolation solid and the actual function dashed yr 1 1 25 xx 2 plot x y o xx yy xx yr 6 Clamped example Generate data w first derivative information x linspace 1 1 9 y 1 1 25 x 2 yc 1 y 4 Calculate 100 model points and determine not a knot interpolation xx linspace 1 1 yyc spline x yc xx Calculate actual function values at model points and data points the 9 point clamped interpolation solid and the actual function dashed yr 1 1 25 xx 2 plot x y o xx yyc xx yr 7 interp1 built in function interp1 function performs several different kinds of interpolation yi interp1 x y xi method x y contain the original data xi contains the points at which to interpolate method is a string containing the desired method nearest nearest neighbor interpolation linear connects the points with straight lines spline not a knot cubic spline interpolation pchip or cubic piecewise cubic Hermite interpolation 8 Piecewise Polynomial Comparisons 9 Multidimensional Interpolation The interpolation methods for onedimensional problems can be extended to multidimensional interpolation Example bilinear interpolation using Lagrange form equations f xi yi xi x2 yi y2 f x1 y1 L x1 x2 y1 y2 xi x1 yi y2 f x2 y1 L x2 x1 y1 y2 xi x2 yi y1 f x1 y2 L x1 x2 y2 y1 xi x1 yi y1 f x2 y2 x2 x1 y2 y1 10 Built in functions for two and three dimensional piecewise interpolation 2 D interpolation the inputs are vectors or same size matrices zi interp2 x y z xi yi method 3 D interpolation the inputs are vectors or same size 3 D arrays vi interp3 x y z v xi yi zi method method is a string containing the desired method nearest linear spline pchip cubic 11 Search 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 12 Sorting 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 13 Sorting algorithms cont d Merge sort invented by John von Neumann 1 2 3 4 5 Complexity average O n log n worst case O n log n If the list is of length 0 or 1 then it is already sorted Otherwise Divide the unsorted list into two sublists of about half the size Sort each sublist recursively by re applying merge sort 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 14 Integration Integration I f x dx b a is the total …