### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Special Topics CS 4803

GPA 3.81

### View Full Document

## 15

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4803 at Georgia Institute of Technology - Main Campus taught by Haesun Park in Fall. Since its upload, it has received 15 views. For similar materials see /class/234052/cs-4803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Special Topics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

Lecture Notes to Accompany Scientific Computing An Introductory Survey Second Edition by Michael T Heath Chapter 7 Interpolation Copyright 2001 Reproduction permitted only for noncommercial educational use in conjunction with the book Interpolation Basic interpolation problem for given data tiayi7 izla39uama with 251 lt 232 lt lt tm determine function fR gt R such that izla39uam f is interpolating function or interpolant for given data Additional data might be prescribed such as slope of interpolant at given points Additional constraints might be imposed such as smoothness monotonicity or convexity of interpolant f could be function of more than one variable but we will consider only one dimensional case 2 Purposes for Interpolation Plotting smooth curve through discrete data points Reading between lines of table Differentiating or integrating tabular data Quick and easy evaluation of mathematical function Replacing complicated function by simple one Interpolation vs Approximation By definition interpolating function fits given data points exactly Interpolation inappropriate if data points sub ject to significant errors Usually preferable to smooth noisy data for example by least squares approximation Approximation also appropriate for special func tion libraries Issues in Interpolation Arbitrarily many functions interpolate given data points 0 What form should function have 0 How should function behave between data points 0 Should function inherit properties of data such as monotonicity convexity or period icity o Are parameters that define interpolating function meaningful o If function and data are plotted should re sults be visually pleasing Choosing Interpolant Choice of function for interpolation based on o How easy function is to work with determining its parameters evaluating function differentiating or integrating function 0 How well properties of function match prop erties of data to be fit smoothness mono tonicity convexity periodicity etc Functions for Interpolation Families of functions commonly used for inter polation include o Polynomials o Piecewise polynomials o Trigonometric functions 0 Exponential functions Rational functions We will focus on interpolation by polynomials and piecewise polynomials for now Will consider trigonometric interpolation DFT later Basis Functions Family of functions for interpolating given data points is spanned by set of basis functions 105 nt Interpolating function f chosen as linear com bination of basis functions 75 Z xjcb t i1 Requiring f to interpolate data thyi means 31 which is system of linear equations A910 2 y for n vector as of parameters xj where entries of m x n matrix A are given by azj gb ti 8 Existence Uniqueness and Conditioning Existence and uniqueness of interpolant de pend on number of data points m and number of basis functions n If m gt n interpolant usually doesn t exist If m lt n interpolant not unique If m n then basis matrix A nonsingular provided data points ti distinct so data can be fit exactly Sensitivity of parameters as to perturbations in data depends on condA which depends in turn on choice of basis functions Polynomial Interpolation Simplest and most common type of interpola tion uses polynomials Unique polynomial of degree at most n 1 passes through n data points tbyi z 1 n where ti are distinct There are many ways to represent or compute polynomial but in theory all must give same result 10 Monomial Basis Monomial basis functions ltt4 j1VWm give interpolating polynomial of form pn 1t 1 215 Min 1 with coefficients as given by n x n linear system 1 1 t1 t 131 yl 1 t tn1 x 14 2 39 2 2 y2 y Matrix of this form called Vandermonde matrix 11 Example Monomial Basis Find polynomial of degree two interpolating three data points 2 27 0 1 10 Using monomial basis linear system is 1 t1 t 131 yl 14 1 t2 t3 132 y2 y 1 t3 g 133 y3 For these particular data system is 1 2 4 211 27 1 o 0 5132 1 1 1 1 133 0 whose solution is 1 1 5 4T so in terpolating polynomial is 1921 1 5t 422 12 Monomial Basis continued Solving system A13 2 y using standard linear equation solver to determine coefficients as of interpolating polynomial requires 9013 work For monomial basis matrix A often ill conditioned especially for high degree polynomials 10 13 Monomial Basis continued Ill conditioning does not prevent fitting data points well since residual for linear system so lution will be small But it does mean that values of coefficients may be poorly determined Both conditioning of linear system and amount of computational work required to solve it can be improved by using different basis Change of basis still gives same interpolating polynomial for given data but representation of polynomial will be different 14 Monomial Basis continued Conditioning with monomial basis can be im proved by shifting and scaling independent vari able t W t CH where c t1 tn2 is midpoint and d tn t12 is half of range of data New independent variable lies in interval 11 which also helps avoid overflow or harmful un derflow Even with optimal shifting and scaling mono mial basis usually still poorly conditioned and we seek better alternatives 15 Evaluating Polynomials When represented in monomial basis polyno mial pn 1t 1 215 I Min 1 can be evaluated efficiently using Horner s nested evaluation scheme pn 1t x1tx2t3t mm 1Wn 9 which requires only n additions and n multipli cations For example 1 4t5t2 2t33t4 1t 4t5t 23t Other manipulations of interpolating polyno mial such as differentiation or integration are also relatively easy with monomial basis repre sentation 16 Lagrange Interpolation For given set of data points thyi z 1 n Lagrange basis functions given by TL TL 4715 H ttk H tj tk j 1n For Lagrange basis 1 if z j 73 17quot397n so matrix of linear system A13 2 y is identity Thus Lagrange polynomial interpolating data points thyi given by pn 1t y1 1t y2 2t ynEnO 17 Lagrange Basis Functions Lagrange interpolant is easy to determine but more expensive to evaluate for given argument compared with monomial basis representation Lagrangian form is also more difficult to dif ferentiate integrate etc 18 Example Lagrange Interpolation Use Lagrange interpolation to find interpolat ing polynomial for three data points 2 27 07 11 17 Lagrange polynomial of degree two interpolat ing three points tbyl t27y2 15393 is t 752W t3 t 751W t3 p2 9101 t2t1 t3 39 2t2 t1t2 2amp3 M y3t3 t1t3 132 For these particular data this becomes tt 1 1t 2t 1 p2 27 2 2 1 2 1 19 Newton Interpolation For given set of data points thyi z 1 n Newton basis functions given by j l k2 where value of product taken to be 1 when limits make it vacuous Newton interpolating polynomial has form pit 105 x1x2t t13t t1t t2 xnt 751W t2 t tn l For 139 lt j 7902 0 so basis matrix A is lower triangular where azj 2 792 20 Newton Interpolation continued Hence solution as to system A13 2 y can be computed by forward substitution in 9012 arith metic operations Moreover resulting interpolant can be eval uated efficiently for any argument by nested evaluation scheme similar to Homer s method Newton interpolation has better balance be tween cost of computing interpolant and cost of evaluating it 30 Illl z 20 r 5quot 739 aquot 39 x 10 m quot 71392 l quot7l393 71394 7T5 39 quotquot39 3939 ni3939I I 00 05 10 15 20 Example Newton Interpolation Use Newton interpolation to find interpolat ing polynomial for three data points 2 27 07 1 Using Newton basis linear system is 1 O 0 131 yl 1 t2 t1 0 132 2 y2 1 t3 t1 t3 t1t3 t2 3 y3 For these particular data system is 1 o 0 131 27 1 2 o 5132 1 1 3 3 133 0 whose solution by forward substitution is 1 27 13 4T so interpolating polynomial is pt 27 130 2 4t 2t 22 Newton Interpolation continued If p705 is polynomial of degree j 1 interpolat ing j given points then for any constant 51341 1934 105 12705 j17Tj1t is polynomial of degree j that also interpolates same j points Free parameter xj1 can then be chosen so that pj1t interpolates yj1 Specifically x 1 yj1 pjtj1 7 7Tj1tj1 Newton interpolation begins with constant poly nomial p1t yl interpolating first data point and then successively incorporates remaining data points into interpolaht 23 Divided Differences Given data points thyi i 1n divided differences denoted by f defined recursively by ft27t37 397tk ft17t27quot wig 1 fitlat27quot397tk tk t1 where recursion begins with ftk yk k 1n Coefficient of jth basis function in Newton in terpolant given by Recursion requires 9012 arithmetic operations to compute coefficients of Newton interpolant but is less prone to overflow or underflow than direct formation of triangular Newton basis ma trix 24 7 Orthogonal Polynomials Inner product can be defined on space of poly nomials on interval a b by taking b ltpqgt ptqtwtdt where 11105 is nonnegative weight function Two polynomials p and q are orthogonal if p qgt 0 Set of polynomials pi is orthonormal if 1 if i j pi p 0 otherwise Given set of polynomials Gram Schmidt or thogonalization can be used to generate or thonormal set spanning same space 25 Orthogonal Polynomials continued For example with inner product given by weight function wt E 1 on interval 11 apply ing Gram Schmidt process to set of monomials 1tt2t3 yields Legendre polynomials 1 t 372 12 573 302 3574 3022 38 63t5 7073 1508 first n of which form an orthogonal basis for space of polynomials of degree at most n 1 Other choices of weight functions and inter vals yield other orthogonal polynomials such as Chebyshev Jacobi Laguerre and Hermite 26 Orthogonal Polynomials continued Orthogonal polynomials have many useful prop erties They satisfy three term recurrence relation of form pk1t 04kt kpkt VkPk t which makes them very efficient to generate and evaluate Orthogonality makes them very natural for least squares approximation and they are also useful for generating Gaussian quadrature rules 27 Chebyshev Polynomials kth Chebyshev polynomial of first kind defined on interval 11 by Tkt cosk arccost are orthogonal with respect to weight function 1 t2 12 First few Chebyshev polynomials given by 1 t 272 1 473 3t 814 8t2 1 1amp5 2073 5t Equi oscilation property successive extrema of Tk are equal in magnitude and alternate in sign which distributes error uniformly when approximating arbitrary continuous function 28 Chebyshev Points Chebyshev points are zeros of Tk given by 239 1 tizcos M i 1k 21 or extrema of Tk given by i7r tizcos i01k Chebyshev points are abscissas of points equally spaced around unit circle in plane R2 Chebyshev points have attractive properties for interpolation and other problems 29 Interpolating Continuous Functions If data points are discrete sample of continu ous function how well does interpolant approx imate that function between sample points If f is smooth function and pn1 is polynomial of degree at most n 1 interpolating f at n points t1tn then 14709 ft Pn 1t Tt t1t t2 ls tn where 9 is some unknown point in interval tlatn Since point 0 unknown result not particularly useful unless bound on appropriate derivative of f is known 30 Interpolating Continuous Functions cont If fnt g M for all t e t1tn and h maxti1 ti 139 1n 1 then Mhn max ft pn1ti tet1tn 4n Error diminishes with increasing n and decreas ing h but only if f t does not grow too rapidly with n 31 High Degree Polynomial Interpolation Interpolating polynomials of high degree are expensive to determine and evaluate In some bases coefficients of polynomial may be poorly determined due to ill conditioning of linear system to be solved High degree polynomial necessarily has lots of wiggles which may bear no relation to data to be fit Polynomial goes through required data points but it may oscillate wildly between data points 32 Nonconvergence Polynomial interpolating continuous function at equally spaced points may not converge to function as number of data points and polyno mial degree increases Example Polynomial interpolants of Runge s function at equally spaced points 20 A fa 11 25t2 quot P505 a 15 mg 10 05 00 33 Placement Of Interpolation Points Equally spaced interpolation points often yield unsatisfactory results near ends of interval If points are bunched near ends of interval more satisfactory results likely to be obtained with polynomial interpolation For example use of Chebyshev points distributes error evenly and yields convergence throughout interval for any sufficiently smooth function 34 Placement Of Points continued Example Polynomial interpolants of Runge s function at Chebyshev points 20 fa 11 25 p5lttgt 15 19100 10 05 00 Illraw quotW J 39l quotquotquotquotquot quot 10 O5 35 Taylor Polynomial Another useful form of polynomial interpola tion for smooth function f is polynomial given by truncated Taylor series wt 2 fa fat a f 90 692 fna t a n Polynomial interpolates f in that values of pm and its first n derivatives match those of f and its first n derivatives evaluated at t a so pnt is good approximation to ft for 75 near a We have already seen examples in Newton s method for nonlinear equations and optimiza tion 36 Piecewise Polynomial Interpolation Fitting single polynomial to large number of data points is likely to yield unsatisfactory os cillating behavior in interpolant Piecewise polynomials provide alternative to practical and theoretical difficulties with high degree polynomial interpolation Main advantage of piecewise polynomial inter polation is that large number of data points can be fit with low degree polynomials In piecewise interpolation of given data points tbyi different function is used in each subin terval tbt l Abscissas ti are called knots or breakpoints at which interpolant changes from one function to another 37 Piecewise Interpolation continued Simplest example is piecewise linear interpola tion in which successive pairs of data points are connected by straight lines Although piecewise interpolation eliminates ex cessive oscillation and nonconvergence it ap pears to sacrifice smoothness of interpolating function We have many degrees of freedom in choos ing piecewise polynomial interpolant however which can be exploited to obtain smooth inter polating function despite its piecewise nature 38 Hermite Interpolation In Hermite interpolation derivatives as well as values of interpolating function are specified at data points Specifying derivative values adds more equa tions to linear system that determines param eters of interpolating function To have unique solution number of equations must equal number of parameters to be deter mined Piecewise cubic polynomials are typical choice Hermite interpolation providing flexibility sim plicity and efficiency 39 Hermite Cubic Interpolation Hermite cubic interpolant is piecewise cubic polynomial interpolant with continuous first deriva tive Piecewise cubic polynomial with n knots has 401 1 parameters to be determined Requiring that it interpolate given data gives 2n 1 equations Requiring that it have one continuous deriva tive gives n 2 additional equations or total of 371 4 which still leaves n free parameters Thus Hermite cubic interpolant is not unique and remaining free parameters can be chosen so that result satisfies additional constraints 40 Cubic Spline Interpolation Spline is piecewise polynomial of degree is that is k 1 times continuously differentiable For example linear spline is of degree 1 and has 0 continuous derivatives ie it is continuous but not smooth and could be described as broken line Cubic spline is piecewise cubic polynomial that is twice continuously differentiable As with Hermite cubic interpolating given data and requiring one continuous derivative imposes 3n 4 constraints on cubic spline Requiring continuous second derivative imposes n 2 additional constraints leaving 2 remain ing free parameters 41 Cubic Splines continued Final two parameters can be fixed in various ways a Specifying first derivative at endpoints t1 and tn 0 Forcing second derivative to be zero at endpoints which gives natural spline o Enforcing not a knot condition forcing two consecutive cubic pieces to be same 0 Forcing first derivatives as well as second derivatives to match at endpoints t1 and tn if spline is to be periodic 42 Example Cubic Spline Interpolation Determine natural cubic spline interpolating three data points thyi 139 123 Required interpolant is piecewise cubic func tion defined by separate cubic polynomials in each of two intervals 251252 and 252253 Denote these two polynomials by 19105 041 042t 043t2 044153 192 t 51 3215 53752 54753 Eight parameters are to be determined so we need eight equations Requiring first cubic to interpolate data at end points of first interval gives two equations 041 042151 04315 04415 y1 43 Example Continued 041 042152 043153 044153 y2 Requiring second cubic to interpolate data at end points of second interval gives two equa tions 51 52752 53153 54153 92 51 52753 531 54153 93 Requiring first derivative of interpolant to be continuous at 252 gives equation 042 2043152 3044753 52 253152 354153 44 Example Continued Requiring second derivative of interpolant func tion to be continuous at 252 gives equation 2043 6044752 253 654152 Finally by definition natural spline has second derivative equal to zero at endpoints which gives two equations 2043 I 6044t1 O 253 654153 0 When particular data values are substituted for ti and yi System of eight linear equations can be solved for eight unknown parameters 04 and 52 45 Hermite Cubic VS Spline Interpolation Choice between Hermite cubic and spline in terpolation depends on data to be fit and on purpose for doing interpolation If smoothness is of paramount importance then spline interpolation may be most appropriate But Hermite cubic interpolant may have more pleasing visual appearance and allows flexibility to preserve monotonicity if original data are monotonic In any case it is advisable to plot interpolant and data to help assess how well interpolating function captures behavior of original data 46 Hermite Cubic VS Spline Interpolation 8 6 monotone Hermite cubic 4 2 quotquotquotquot quot O I I I I I O 2 4 6 8 10 8 6 39 cubic spline 4 2 quotquot O I I I39 I I O 2 4 6 8 10 47 B splines B spines form basis for family of spline func tions of given degree B splines can be defined in various ways in cluding recursion convolution and divided dif ferences Here we will define them recursively Although in practice we use only finite set of knots t1tn for notational convenience we will assume infinite set of knots 39ltt2ltt1ltt0ltt1ltt2lt Additional knots can be taken as arbitrarily de fined points outside interval t1tn We will also use linear functions 11505 75 titz k 752 48 B splines continued To start recursion define B splines of degree 0 by 1 if tigtltti1 0 otherwise B905 and then for k gt 0 define B splines of degree is by Bra vfrtBf 1t 1 vf1tBf 11t Since B is piecewise constant and 225 is linear B11 is piecewise linear Similarly B3 is in turn piecewise quadratic and in general Bf is piecewise polynomial of degree is 49 B splines 10 B 05 O 39 0 ti 751 1 ti2 ti3 t 4 10 Bi 05 Z O 39 0 ti 751 1 ti2 ti3 t 4 10 0395 Bi2 I I I I O 39 0 ti 751 1 ti2 ti3 t 4 10 05 st I O 39 0 ti 751 1 ti2 ti3 t 4 B splines continued Important properties of B spline functions Bf 1 For t lt ti or t gt tik1 B503 2 O 2 For ti lt t lt tik1 B503 gt O 3 For all t 3OOB 25 1 4 For k 2 1 Bf has k 1 continuous derivatives 5 Set of functions B fk bel is linearly independent on interval t1tn and spans space of all splines of degree is having knots 75 51 B splines continued Properties 1 and 2 together say that B spline functions have local support Property 3 gives normalization Property 4 says that they are indeed splines Property 5 says that for given is these functions form basis for set of all splines of degree is 52

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.