To obtain m_k, k=0,….(n+1), we differentiate S_k (x):

4)

Evaluating this at x=x_k:

=

=   Now, let d_k=

5)

Evaluating S_k`(x) using 4) (substitute k=k-1):

We evaluate S_k-1`(x) at x=x_k:

6)

From property IV, we can make 5) and 6) equal: S_k-1`(x<sub>k</sub>)=S<sub>k</sub>`(x_k):

=

=

7)

We have n-1 equations and m₀,m₁,m₂,…m_n=n+1 unknowns, so we need two more equations.  These equations are needed to eliminate m₀ and m_n.  For that we use different criteria.

From 7) we can tell that the system of equations to determine m_k is diagonal.  This system is strictly diagonal dominant.

How to obtain m₀ and m_n:

There are several criteria:

1) Clamped Spline-The first derivatives at the ends are given.

S`(a) and S`(b) are given

2)Natural Spline-The second derivatives at the ends are zero.

S``(a)=0, S``(b)=0

3)Extrapolated Spline-

S₀ and S_k are part of the same cubic polynomial.  Also, S_n-2 and S_n-1 are the same cubic polynomial.

4)Parabolic Terminated Spline

S₀ and S_n-1 will be quadratic polynomials instead of cubic polynomials.

5)Endpoint Curvature Adjusted Spline

S``(a) and S``(b) are given.

Note: 2) is a subcase of 5)

7/22/2003

Solving a Spline

-Input a set of points (x₀,y₀),…(x_n,y_n)

-Choose the criteria for the constraints at the endpoints

-Solve the system of linear equations to determine m₀…..m_n

-Find the coefficients:

Numerical Differentiation

-In some methods, we need to know the derivative of a function

Example: Newton-Raphson Method

Limit of the Difference Quotient

Approximate the limit to zero of ∆x by using a small value.

How small should h be to compute the limit numerically?  The value of h depends on the function.  We can start with a large h and make it increasingly small until the division cannot be made (or the numerator is equal to zero) or you lose precision.

7/23

Example:

At x=1:

f’(1)=e=2.7183…(exact solution)

H	Dk
.1	2.8588
.01	2.7319
.001	2.7196
.0001	2.7184
.00001	2.7183
.000001	2.7183

Then, ∆D_k=0.

Central Difference Equation

-Centered formula of O(h²) (error term is of (h²))

1) Using Taylor expansion:

Do the same for f(x-h):

2)

Subtracting 2) from 1) and simplifying:

So,

Centered Formula of O(h⁴)

Taylor expansion:

3)

4)

5)

Using a step size of 2h in 3):

From 5), do the same for 2h instead of h:

Multiply 5) by 8 and subtract 6) from it and solve for f’(x) to obtain:

Then, the formula for the centered formula of O(h⁴) is:

For comparison, let f(x)=sin(x) and h=.001.  Here are the results from the methods covered so far:

Centered Formula of O(h⁴):sin(π/3)=.5

Centered Formula of O(h²):sin(π/3)=.499999917

Difference Quotient: sin(π/3)=.499566904

7/24

Numerical Integration

Obtaining the area under the curve using numerical methods.

Trapezoidal Rule:

In general,

Example:

, X=[-1, -.5, 0, .5, 1], h=.5

Example:

Exact solution: cos(π/2)+cos(0)=1

Simpson’s Rule

Approximate f(x) using quadratic polynomials every 3 points.

Find the quadratic polynomial that passes through (x₀, f₀), (x₁, f₁), and (x₂, f₂).

Using Lagrange polynomials:

The area below P₂(x) is:

; changing variables:

;;

=

At t=0, all terms are 0, so we need only to evaluate at h=2:

To add all of these areas up, for x₀ to x_n,

7/25/2003

Numerical Optimization

Find a maximum or minimum of an equation.

Global maximum/minimum-Maximum or minimum of a function over .

Local maximum/minimum-maximum or minimum over [a.b].

Unimodal function-only one maximum or minimum exists over [a,b].

The maximization of a function f(x) can me reduced to minimizing –f(x)

Minimization of an equation

-Local maximum value at x=p in the interval I

-Local minimum value at x=p in the interval I

A function is increasing in I if

A function is decreasing in I if

Suppose that f(x) is continuous in I-[a.b] and is differentiable:

-If f’(x)>0 for all x=[a,b], the f(x) is increasing in I.

-If f’(x)<0 for all x=[a,b], the f(x) is decreasing in I.

-If there is a maximum of minimum value at x=p, then f’(p)=0.

-If f’’(p)>0, then f(p) is a minimum.

-If f’’(p)>0, then f(p) is a maximum.

Search Methods

The Golden Ratio

Assume that f(x) is unimodal.  We choose two more points such that c=a+(1-r)(b-a) and d=a+r(b-a).  There are two cases that can result:

-If f(c) < f(d), then make the new search interval [a,d] because the maximum is between a and d.

-If f(c) > f(d), then make the new search interval [c,b] because the maximum is between a and d.

Stop when the length of the interval is less than some epsilon.

We can choose r in such a way that the new c or d can be a previous c or d.

If f(c) < f(d), then [a,d] becomes [a,b] for the next iteration, and we just need to calculate c and f(c).

What is the values of r that allows us to do this?

using the quadratic formula,