MA 2213 Numerical Analysis I: Additional Topics

Newton Hermite Spline Legendre
MA 2213 Numerical Analysis I

Additional Topics
Dr. Andy M. Yip
Department of Mathematics
National University of Singapore
20132014 Semester 1
A M Yip (NUS Math) MA 2213 1 / 22
Outline
1
Newtons Divided Dierence Interpolation Formula
2
Newtons Divided Dierence Interpolation Formula for Hermite
Polynomials
3
Spline: The Function of Minimal Change
4
Legendre Polynomials
Fundamental theorem
Theorem (Newtons divided dierence interpolation formula)
Let x
0
, x
1
, . . . , x
n
be n + 1 distinct nodes in [a, b]. Then the polynomial
P
n
(x) = f [x
0
] +
n
k=1
f [x
0
, x
1
, . . . , x
k
](x x
0
) (x x
k1
)
interpolates f at x
0
, x
1
, . . . , x
n
.
For each n, we dene the polynomial P
n
to be
P
n
(x) = f [x
0
] +
n
k=1
f [x
0
, x
1
, . . . , x
k
](x x
0
) (x x
k1
).
What we need to prove is that P
n
interpolates f at x
0
, x
1
, . . . , x
n
.
Proof (1/6)
Prove by mathematical induction.
When n = 1, we have
P
1
(x) = f [x
0
] + f [x
0
, x
1
](x x
0
).
Next,
P
1
(x
0
) = f [x
0
] + f [x
0
, x
1
](x
0
x
0
) = f (x
0
)
P
1
(x
1
) = f [x
0
] + f [x
0
, x
1
](x
1
x
0
) = f [x
0
] + (f [x
1
] f [x
0
]) = f (x
1
).
Thus, the theorem holds for n = 1.
Proof (2/6)
Assume the theorem holds for n = 1, 2, . . . , n
0
1 for some n
0
, i.e., for
any n + 1 distinct nodes y
0
, y
1
, . . . , y
n
, the polynomial
f [y
0
] +
n
k=1
f [y
0
, y
1
, . . . , y
k
](x y
0
) (x y
k1
)
interpolates f at y
0
, y
1
, . . . , y
n
for any 1 n n
0
1 .
(We will soon choose the nodes to be {x
0
}, {x
0
, x
1
}, . . ., {x
0
, . . . , x
n
0
2
},
{x
0
, . . . , x
n
0
1
}, {x
1
, . . . , x
n
0
}, respectively.)
We aim to show that the theorem holds for n = n
0
, i.e., the polynomial
P
n
0
(x) = f [x
0
] +
n
0
k=1
f [x
0
, x
1
, . . . , x
k
](x x
0
) (x x
k1
)
interpolates f at x
0
, x
1
, . . . , x
n
0
.
Proof (3/6)
For j = 0, 1, 2, . . . , n
0
1, we have
P
n
0
(x
j
) = f [x
0
] +
n
0
k=1
f [x
0
, x
1
, . . . , x
k
](x
j
x
0
) (x
j
x
k1
)
= f [x
0
] +
j
k=1
f [x
0
, x
1
, . . . , x
k
](x
j
x
0
) (x
j
x
k1
)
+ f [x
0
, x
1
, . . . , x
j +1
](x
j
x
0
) (x
j
x
j
) +
= f [x
0
] +
j
k=1
f [x
0
, x
1
, . . . , x
k
](x
j
x
0
) (x
j
x
k1
)
= P
j
(x
j
) (def. of P
j
)
= f (x
j
) (induction hypothesis).
It remains to show P
n
0
(x
n
0
) = f (x
n
0
).
Proof (4/6)
P
n
0
(x
n
0
) = P
n
0
1
(x
n
0
) + f [x
0
, x
1
, x
2
, . . . , x
n
0
](x
n
0
x
0
) (x
n
0
x
n
0
1
)
(def. of P
n
0
)
= P
n
0
1
(x
n
0
) +{f [x
1
, x
2
, . . . , x
n
0
] f [x
0
, x
1
, x
2
, . . . , x
n
0
1
]}
(x
n
0
x
1
) (x
n
0
x
n
0
1
) (def. of divided di.)
= P
n
0
1
(x
n
0
) f [x
1
, x
2
, . . . , x
n
0
1
, x
0
](x
n
0
x
1
) (x
n
0
x
n
0
1
)
+ f [x
1
, x
2
, . . . , x
n
0
](x
n
0
x
1
) (x
n
0
x
n
0
1
)
(permutation invariance of divided di.)
Hence,
P
n
0
(x
n
0
) = P
n
0
1
(x
n
0
) f [x
1
, x
2
, . . . , x
n
0
1
, x
0
](x
n
0
x
1
) (x
n
0
x
n
0
1
)
+ f [x
1
, x
2
, . . . , x
n
0
](x
n
0
x
1
) (x
n
0
x
n
0
1
) (1)
Proof (5/6)
Since P
n
0
1
interpolates f at x
0
, x
1
, . . . , x
n
0
1
, by the divided dierence
interpolation formula w.r.t. the ordering {x
1
, x
2
, . . . , x
n
0
1
, x
0
}, we have
P
n
0
1
(x) = f [x
1
] + f [x
1
, x
2
](x x
1
) +
+ f [x
1
, x
2
, . . . , x
n
0
1
](x x
1
) (x x
n
0
2
)
+ f [x
1
, x
2
, . . . , x
n
0
1
, x
0
](x x
1
) (x x
n
0
1
),
so that
P
n
0
1
(x) f [x
1
, x
2
, . . . , x
n
0
1
, x
0
](x x
1
) (x x
n
0
1
)
= f [x
1
] + f [x
1
, x
2
](x x
1
) +
+ f [x
1
, x
2
, . . . , x
n
0
1
](x x
1
) (x x
n
0
2
). (2)
Proof (6/6).
Hence, by (1) and (2), we have
P
n
0
(x
n
0
) = f [x
1
] + f [x
1
, x
2
](x
n
0
x
1
) +
+ f [x
1
, x
2
, . . . , x
n
0
1
](x
n
0
x
1
) (x
n
0
x
n
0
2
)
+ f [x
1
, x
2
, . . . , x
n
0
](x
n
0
x
1
) (x
n
0
x
n
0
1
).
By induction hypothesis, the RHS is the polynomial that interpolates f on
x
1
, x
2
, . . . , x
n
0
, evaluated at x = x
n
0
. Hence, the RHS equals to f (x
n
0
).
Hence, P
n
0
(x
n
0
) = f (x
n
0
).
Hence, the theorem holds for n = n
0
.
Outline
1
2
Polynomials
3
4
Divided Dierence Form of Hermite Polynomials
Hermite Polynomial: Divided Dierence Form
Let H
2n+1
be the Hermite interpolant. Then,
H
2n+1
(x) = f [z
0
] +
2n+1
k=1
f [z
0
, z
1
, . . . , z
k
](x z
0
) (x z
k1
).
We illustrate the main ideas for the case n = 1. We dene
P
0
(x) = f [z
0
] +
3
k=1
f [z
0
, z
1
, . . . , z
k
](x z
0
) (x z
k1
).
We need to show that P
0
equals to H
3
(the theoretical unique interpolant).
Idea of proof (1/3)
Since P
0
depends only on the data (f (x
i
), f
(x
i
)) and H
3
(x
i
) = f (x
i
)
and H
3
(x
i
) = f
(x
i
), we assume WLOG that f H
3
. Hence, we need
to show that P
0
f .
Let z
0
= x
0
, z
1
() = x
0
+ , z
2
= x
1
, and z
3
() = x
1
+ , where > 0
is a tiny value s.t. z
0
, z
1
, z
2
, z
3
are distinct. (Use x
i
if x
i
= b.)
By Newtons Divided Dierence Interpolation Formula, the
polynomial that interpolates f on z
0
, z
1
, z
2
, z
3
is
P(x) = f (z
0
) +
3
k=1
f [z
0
, . . . , z
k
](x z
0
) (x z
k1
).
Since this polynomial and f are polynomials of degree 3 or less that
agree on 4 distinct nodes, we must have P f .
Idea of proof (2/3)
Thus, P
0
is the polynomial obtained from the Hermite table (left)
and f is the polynomial obtained from the Lagrange table (right):
z
i
f [z
i
] 1st DD 2nd DD 3rd DD
x
0
f (x
0
)
f

(x
0
)
x
0
f (x
0
)
f [x
0
, x
1
]
x
1
f (x
1
)
f

(x
1
)
x
1
f (x
1
)
z
i
f [z
i
] 1st DD 2nd DD 3rd DD
x
0
f (x
0
)
f [x
0
, z
1
]
z
1
f (z
1
)
f [z
1
, x
1
]
x
1
f (x
1
)
f [x
2
, z
3
]
z
3
f (z
3
)
By continuity of f , lim
0
f (z
1
) = f (x
0
) and lim
0
f (z
3
) = f (x
1
).
By MVT, for any x = y, there exists between x, y such that
f [x, y] =
f (x)f (y)
xy
= f
(). Assume f
C[a, b]. Then

lim
0
f [x
0
, z
1
] = f
(x
0
) and lim
0
f [x
2
, z
3
] = f
(x
1
).
Hence, the Lagrange table converges to the Hermite table.
Idea of proof (3/3).
Thus, the coecients f converge to the coecients of P
0
as 0. Since
both f and P
0
are actually independent of , we must have
P
0
f .
Outline
1
2
Polynomials
3
4
Why cubic splines are good?
We motivated the use of piecewise polynomials with the Runge
phenomenon.
That is, it is not good to use one-piece polynomials of high degrees
because of spurious oscillations.
We can justify the use of natural/clamped cubic splines more
precisely.
For any g C
2
[a, b] that interpolates f on x
0
, . . . , x
n
, we have
x
n
x
0
[S
(x)]
2
dx
x
n
x
0
[g
(x)]
2
dx.
For a straight line g, we have
x
n
x
0
[g
(x)]
2
dx = 0. Thus, the natural
or clamped cubic spline S is in a sense the function that is closest to
a straight line, i.e. least oscillations.
Proof
Since
x
n
x
0
[g
(x)]
2
dx =
x
n
x
0
[g
(x) S
(x) + S
(x)]
2
dx
=
x
n
x
0
[g
(x) S
(x)]
2
dx +
x
n
x
0
[S
(x)]
2
dx
+ 2
x
n
x
0
(g S)
(x)S
(x)dx
x
n
x
0
[S
(x)]
2
dx + 2
x
n
x
0
(g S)
(x)S
(x)dx,
it suces to prove that
x
n
x
0
(g S)
(x)S
(x)dx = 0.
Proof (cont.)
Since (g S)
C[x
0
, x
n
], we can apply integration by parts to obtain
x
n
x
0
(g S)
(x)S
(x)dx = [(g S)
(x)S
(x)]
x
n
x
0
x
n
x
0
(g S)
(x)S
(x)dx
=
x
n
x
0
(g S)
(x)S
(x)dx.
Here, we used the facts that S
(x
0
) = S
(x
n
) = 0 for natural splines and
g
(x
0
) = S
(x
0
) = f
(x
0
) and g
(x
n
) = S
(x
n
) = f
(x
n
) for clamped splines,
so that [(g S)
(x)S
(x)]
x
n
x
0
= 0 in any case.
x
n
x
0
(g S)
(x)S
(x)dx =
x
n
x
0
(g S)
(x)S
(x)dx
?
= 0
Proof (cont.)
This time we cannot directly apply integration by parts to
x
n
x
0
(g S)
(x)S
(x)dx because S
is discontinuous. But we have
x
n
x
0
(g S)
(x)S
(x)dx
=
n1
j =0
x
j +1
x
j
(g S)
(x)S
(x)dx
=
n1
j =0
[(g S)S
]
x
j +1
x
+
j
x
j +1
x
j
(g S)(x)S
(x)dx
which is zero because g = S at each node x

j
and S
0 on (x
j
, x
j +1
).
Outline
1
2
Polynomials
3
4
Uniqueness
Legendre polynomials {P
0
, P
1
, . . . , P
n
, . . .} are dened by:
1
For each n, P
n
(x) is a monic (leading coecient = 1) polynomial of
degree n.
2
P, P
n
=
1
1
P(x)P
n
(x)dx = 0 for any polynomial P(x) of degree
n 1 or less.
How do we know P
n
is unique under this denition?
Proof
Let P
n
and Q
n
be two such polynomials. Since P
n
and Q
n
are monic, the
dierence P
n
Q
n
is a polynomial of degree n 1 or less. Thus, by
Property 2,
P
n
Q
n
, P
n
= 0 and P
n
Q
n
, Q
n
= 0.
Hence,
1
1
(P
n
(x) Q
n
(x))
2
dx
=
1
1
(P
n
(x) Q
n
(x))P
n
(x)dx
1
1
(P
n
(x) Q
n
(x))Q
n
(x)dx
= 0 0.
Since (P
n
(x) Q
n
(x))
2
is continuous and non-negative, we must have
P
n
(x) Q
n
(x) 0.

MA 2213 Numerical Analysis I: Additional Topics

Uploaded by

Copyright:

Available Formats

MA 2213 Numerical Analysis I: Additional Topics

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MA 2213 Numerical Analysis I: Additional Topics

Uploaded by

Copyright:

Available Formats

Newton Hermite Spline Legendre

MA 2213 Numerical Analysis I

C[a, b]. Then

is discontinuous. But we have

which is zero because g = S at each node x

You might also like