ME 2016 Exam 2

Polynomial Interpolation

determining the nth order polynomial that fits n+1 data points

general form of nth order polynomial

fn(x) = a0 + a1x +a2x²

How many nth order polynomials fit n+1 data points

one but there are a number of mathematical formats in which the polynomial can be expressed

Newton Divided Difference

fn(x) = b0 + b1(x-xo) + b2(x-xo)(x-x1) ….

Newton Divided Difference zeroth coefficient

b0 = f(x0)

Newton Divided Difference 1st coefficient

b1 = f(x1) - f(x0) / (x1-x0)

Newton Divided Difference 2nd coefficient

b2 = ( (f(x2) - f(x1) /(x2-x1)) - b1) / (x2-x0)

When to use Newton interpolating polynomial

when the order of the polynomial is unknown

Use to use Lagrange interpolating polynomial

the order of the polynomial is known

spline interpolation

determining n low order piecewise polynomials through n+1 data points

Why use splines over polynomial interpolation

polynomial interpolation can lead to wild oscillations for high order polynomials or when function of interest has local, abrupt changes

how many knots in spline interpolation

n+1

how many intervals in spline interpolation

n

linear spline formula without solved coefficients

Si(x) = ai + bi(x-xi)

quadratic spline formula without solved coefficients

Si(x) = ai + bi(x-xi) + ci(x-xi)²

linear spline coefficients

ai = fi , bi = (fi+1 - fi)/ (xi+1 - xi)

Disadvantages of linear spline

non-smooth, discontinuous, 1st derivative

Quadratic and Cubic splines impose

higher order smoothness conditions, in addition to the continuity conditions of linear

How many conditions for linear splines

2n

How many conditions for quadratic splines

3n

How many conditions for cubic splines

4n

Spline conditions on function values consist of

function values of adjacent polynomials must be equal at interior knots and first and last polynomials must pass through exterior knots (2n conditions)

function values of adjacent polynomials must be equal at interior knots number of conditions

2(n-1)

first and last polynomials must pass through exterior knots number of conditions

2 conditions

function values of adjacent polynomials must be equal at interior knots condition formulas

Si-1(xi) = f(xi) and Si(xi) = f(xi)

first and last polynomials must pass through exterior knots formulas

So(xo) = f(xo) and Sn-1(xn) = f(xn)

Spline conditions at first derivative at interior knots number of conditions

n-1

Spline conditions at first derivative at interior knots formula

S’i-1(xi) = S’i(x)

Spline conditions at second derivative at interior knots number of conditions

n-1

Spline conditions at second derivative at interior knots formula

S’’i-1(xi) = S’’i(xi)

After first derivative conditions how many more conditions needed for quadratic spline

1

After second derivative conditions how many more conditions needed for cubic spline

2

Natural end conditions

S0’’(xo) = S’’n-1(xn) = 0

Clamped end conditions

S’o(xo) = f’(xo) , S’n-1(xn) = f’(xn)

not-a-knot end conditions

S’’’o(x1) = S’’’1(x1) , S’’’n-2 (xn-1) = S’’’n-1(xn-1)

Newton-Cotes integration formulas

replace a complicated function or tabulate values with an approximating function that is easy to integrate

Newton-Cotes Trapezoid Rule integration formula

(b-a) * f(a)+f(b)/2

Trapezoid Rule error indicates

it is exact for linear function

Multi-application trapezoid rule

divide integration interval into number of segments, apply trapezoid rule to each segment, and then sum them

Multi-application trapezoid rule formula

Multi-application trapezoid rule error

as number of segments doubles error reduced by 1/4

For multi application trapezoid error at some point as the number of segments increase

roundoff error may intrude

Using trapezoid rule is good for

individual applications of nicely behaved functions

For high accuracy multi-application trapezoid rule

can be expensive

Simpsons 1/3 rule requires

an additional point midway between a and b

Simpsons 1/3 rule uses what type of polynomial

2nd-order

Simpsons 1/3 formula

(b-a) * (f(x0) + 4f(x1) + f(x2))/6

Simpsons 1/3 error indicates it is

exact for any cubic polynomial

Multi-application Simpsons 1/3 requires

an even number of segments

Multi-application Simpsons 1/3 formula

Multi-application Simpsons 1/3 error

as number of segments is doubled error reduced by 1/16

Romberg Integration

combine multiple low order estimates to achieve a higher order estimate of the integral

Adaptive Quadrature

Able to generate more efficient estimate with adaptive stepsize

Gauss Quadrature

An improved estimate can come from strategically choosing evaluation point away from end points

n point Gauss-Legendre formula takes the form

I = c0*f(xo) + c1*f(x1) + …+ cn-1*f(n-1)

differential equation

an equation composed of an unknown function and its derivative

An ODE is a differential equation with

one independent variable

In an IVP all

auxiliary conditions are specified at the same value as the independent variable

Eulers method

approximate slope in the interval as the slope of xi

Eulers formula

yi+1 = yi + f(xi,yi)h

Order of Euler’s method global truncation error

O(h), as we halve stepsize error reduces by half

Heun’s method

approximate slope as average over interval

Heun’s method formula

yi+1 = yi + (f(xi,yi) + f(xi+1, y0i+1) )/2 * h

Eulers method reminiscent of

forward finite difference

Heuns method reminiscent of

center finite difference

Heun’s method error is of order

O(h²), as we halve stepsize we quater error

Midpoint method

uses an approximate slope at midpoint of interval

Midpoint method formula

yi+1 = yi + f(xi+1/2, y0 i+1/2) *h

Midpoint method reminiscent of

centered finite difference

Midpoint method order of error

O(h²), as we halve the stepsize we quarter the error

Runge-Kutta method uses an

increment function to represent slope over interval

Increment function form

a1k1 + a2k2 … ankn

When using Runge-Kutta method for low order methods

n dictates the order of the method

3rd order RK error

O(h³), when stepsize half error reduces by 1/9

4th order RK error

O(h^4), when stepsize half error reduces by 1/16