闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS323 LECTURE NOTES - LECTURE 14

1 Cubic Splines

In the cases of polynomial interpolation that we have talked about (Lagrange, Neville, divided dierences) the polynomialwill gothrough each one ofthe given points, but it some times oscillates too much for intermediate points. How could we nd a better interpolation, which is smoother and still goes through each one ofthe given points? The answer cannot be another degree n polynomial that goes through the given n + 1 points, since that polynomial is unique. We are left with trying a lower degree polynomial.

The only way to use lower degree polynomials that go through each one of the n + 1 points is by reducing the number of points, which takes us to a piecewise polynomial. We could, for exam- ple use a rst-degree polynomial going through points x0 and x1, then another polynomial going through points x1 and x2, and so on. The problem with this approach is the lack of smoothness in the unions. We could try degree two polynomials, and ask some bound- ary conditions to obtain a smooth transition from one polynomial to another. In practice the idea that works best (looks smoother) is to use 3rd-degree polynomials. This method is called cubic splines.

1.1 Conditions

1. There will be a 3rd-degree polynomial Si for each interval [xi,xi+1]. Recall that the given points go from x0 to xn, so we will have n polynomials S0(x), . . . ,Sn−1(x)

2. The two polynomials Si(x) and Si+1(x) must agree on point (xi+1,yi+1) (nodal point). In the gure it shown with an oval.

3. The (rst) derivative of both polynomials that share the end of each interval must agree.

4. If we count the number of equations so far, they will be less than the number of unknowns, therefore we will add the extra condition that the second derivative of both polynomials that share the end of each interval must agree.

5. If there is no given external condition outside of the interval [x0,xn], we will require the second derivative of S0(x) in x0 to be equal to zero.

We can write each 3rd-degree polynomial as:

Si(x) = ai + bi(x xi) + ci(x xi)2 + di(x xi)3

Our objective is to nd ai, bi, ci, and di, i = 0, . . . ,n 1. Which suggest that we must solve a system of equations.

We will need the rst and second derivatives of each polynomials that share the point (xi,yi), (xi+1,yi+1):

Si+1(x) =

S (x) =

S+1(x) = S(x) = S(x) =

ai+1 + bi+1(x xi+1) + ci+1(x xi+1)2 + di+1(x xi+1)3 bi + 2ci(x xi) + 3di(x xi)2

bi+1 + 2ci+1(x xi+1) + 3di+1(x xi+1)2

2ci + 6di(x xi)

2ci+1 + 6di+1(x xi+1)

Now we formally write each one of the conditions:

Conditions:

1. Si(xi) = f(xi) ∀i = 0, . . .,n 1

2. Si+1(xi+1) = Si(xi+1) ∀i = 0, . . .,n 1

3. S+1(xi+1) = S (x i+1) ∀i = 0, . . .,n 1

4. S(xi+1) = S(xi+1) ∀i = 0, . . .,n 1

5. S(x0) = 0

We can dene hi as the width of each interval:

hi = xi+1 xi ∀i = 0, . . . ,n 1

If we substitute in each one of the equations we get:

1. ai = f(xi)

2. ai+1 = ai + bihi + cih + dih (5)

3. bi+1 = bi + 2cihi + 3dih (6)

4. ci+1 = ci + 3dihi (7)

5. c0 = 0

solving for di in (7)

di = (ci+1 ci) (11)

now substitute di in (5) and solve for bi

bi = hi (10)

we can compute bi+1 using bi from the previous step

ai+2 ai+1 2ci+1 + ci+2

i+1

substitute bi and bi+1 in (6)

after doing some algebra we get:

hici+2(hi+hi+1)ci+1+hi+1ci+2 = 3 (8)

Notice that for each i = 0 . . .n 1 we have an equation. But if we substitute i = n 1 in (8) we will need cn+1, which does not exist. So we can only use those equations for i = 0, . . .,n 3, but then we only have n 2 equations, and n unknowns: c0, . . . ,cn−1. We can add c0 = 0 obtained from condition 5. We still need one more equation.