----- (4)CS 314 Notes
Week 6
7/21/2003
Piecewise Cubic Splines (contd.)
To obtain mk (k = 0,1... N+1), we differentiate Sk(x)
----- (4)
Evaluating (4) S 'k(x) at x = xk
----- (5)
Using (4) we obtain S 'k-1(x) , (substitute k by k-1)
We evaluate S 'k-1(x) at x = xk
----- (6)
from property IV we can make equal
S 'k-1(xk) = S 'k(xk)
Let
----- (7)
We have N-1 equations & we have m0, m1, ..., mN (N unknowns)
Therefore we need two more equations. These equations are needed to eliminate m0, m1, ..., mN & for that we need to use different criteria.
From (7) we can tell that the system of equations to determine mk is
This is a strictly diagonal domimant system.
How to obtain m0
& mN
There are several criterias:
Clamped Spline
The first derivatives at the end are given
-----
1.1
-----
1.2
-----
1.3
Natural Spline
The second derivatives at the ends are 0
S''(a) = 0 & S''(b) = 0
-----
2.1
-----
2.2
-----
2.3
Extrapolated Spline
S0 & S1 are part of the same cubic polynomial. Also, SN-2 and SN-1 are the same cubic polynomials.
-----
3.1
-----
3.2
-----
3.3
Parabolically Terminated Spline
S0 & SN - 1 will be quadratic polynomials instead of cubic.
-----
4.1
-----
4.2
-----
4.3
End-pint Curvative-adjusted Spline
S''(a) and S''(b) are given.
-----
5.1
-----
5.2
-----
5.3
07/22/03
Solving a Spline
Input a set of points (x0 , y0),..., (xN, yN)
Choose the criteria for the constraints at the end points.
Solve the system of linear equations to determine: m0,..., mN
Find the coefficients:
Example:
Find
the natural spline that approximates y=sin(x) in the interval
with
4 points equally spaced.
k x y
0 0 0
1 (π/6) = 0.5236 sin(π/6) = 0.5
2 (π/3) = 1.0472 sin(π/3) = .866
3 (π/2) = 1.5708 sin(π/2) = 1
m0
= S”(0)=0 & m3 = S”(π/2)
= 0
h0 = h1 = h2 = π/2 = .5236
From the equations of natural spline (Criteria 2) we get the following two equations
From
2.1 we get
From
2.3 we get
we do not have equations from 2.2 sinse k here goes from k=2,3,...,N-2 (N-2 = 1)
Solving (a) & (b) using Gaussian elimination and using back substitution we get,
m1 = -.4435 & m2 = -1.1528
we have, m0 = 0, m1 = -.4435, m2 = -1.1528, m3 = 0
we need to obtain the spline coefficients:
k =0,
this spline has to pass through (0,0) & (.5236, .5)
S0(0) = 0
S0(.5236) = .9936 x .5236 - .1412(.5236)3 = 0.5
k = 1
This spline has to pass through the points(.5236,.5) and (1.0472,.8660)
S1 ( .5236) = .5
S1 (1.0472) = .8660
Numerical Differentiation
In some methods we need to know the derivative of a function, e.g.: Newton-Raphson
Limit of the difference Quotient
Approximate the limit to 0 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 smaller and smaller until:
The division cannot be made.
The numerator is 0
You loose precision.
07/23/03
Example:
for x =1,
|
h |
Dk |
|
0.1 |
2.8588 |
|
0.01 |
2.7319 |
|
0.001 |
2.7196 |
|
0.0001 |
2.7184 |
|
0.00001 |
2.7183 |
|
0.000001 |
2.7183 |
---
Exact solution
Centeral Difference Formulas
Centered Formula of order O(h2)
Using Taylor expansion
Substracting (2) from (1) we get,
Example:
Centered Formula of order O(h4)
Do Taylor expansion:
Using step size 2h instead of h in (3) we get,
For (5) do the same, use 2h instead of h
Mutliply (5) by 8 and substract (6)
Example:
Let f(x) = sin(x)
f'(x) = cos(x)
x = π/3
f'( π/3) = cos( π/3) = .5 – Actual solution
Numerical Integration
Obtaining the area under the curve using numerical methods.
Trapezoidal Rule
Example:
Example:
Simpson Rule
Approximate f(x) using quadratic polynomial every 3 points.
Find quadratic polynomial that passes through (x0, f0), (x1, f1), (x2, f2) using Lagrange polynomials.
The area below this P2(x) is
Change variables:
Example:
With 2M = 2
Approximation using Simpson is better than the trapezoidal rule.
7/25/03
Numerical Optimization
Find a maximum or minimum of an equation.
Global maximum / minimum
maximum / minimum is a
function for
Local maximum / minimum
Unimodal function in the range [a,b]
Only one minimum or maximum in the function in the range [a,b]
The maximization problem of f(x) can be reduced to minimizing f(x)
Minimization of an equation
Local maximum value at x = p in the interval I
if
Local minimum value at x = p
if
A function is increasing in I
if
A function is decreasing in I
if
Suppose that f(x) is continuous in I=[a,b] & is differentiable
if f'(x) > 0 for all x=(a,b) then f(x) is increasing in I
if f'(x) < 0 for all x=(a,b) then f(x) is increasing in I
If there is a maximum or minimum value at x=p then f'(p) = 0
If f”(p) < 0 then f(p) is a local maximum.
If f”(p) > 0 then f(p) is a local minimum.
Search Methods
The golden ratio
Assume f(x) is unimodla (one minimum) is the interval a,b
we choose two more points such that
c = a + (1 – r)(b-a)
d = a + r(b-a)
< r < 1
Two cases:
if f(c) < f(d) then make the new interval to be [a,d] because the minimum is between a & d.
if f(c) > f(d) then make the new interval to be [c,b] because the minimum is between c & 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 d or c.
if f(c) < f(d) then make the new b = d[a,b] we just need to compute c and f(c).
What is the value of r that allows us to do this?
--
golden ratio
Example:
f(x) = x2 + 1
i = 1, a = -2, b = 1
c = a + (1-r)(b-a) = -2 + (1 - .61803)(1-(-2))
= -.8541
d = a + r(b-a) = -2 + .61803(1-(-2))
= -.14589
f(a)
= f(-2) = 5
f(b) = f(1) = 2
f(c) = f(-.8541) = 1.72949
f(d)
= f(-.14589) = 1.02128
New search interval: f(c) > f(d) ; [c,b] = [-.8541, 1]
i = 2, a = -.8541 , b = 1 ,
c
= -.14589
d = a+r(b-a) = .297189
f(a)
= f(-.8541) = 1.72949
f(b) = f(1) = 2
f(c) = f(-.14589) =
1.02128
f(d) = f(.291789) = 1.08514
New search interval: f(c) < f(d) ; [a,d] = [-.8541, .297189]
i = 3 , a = -.8541, b = .297189
d = -.14589
c = a+(1-r)(b-a) = .4164