Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
PROBLEMS 125
define
Show that every root
x of
p(x)
= 0 satisfies
lxl
:5;
Max {
R,
Vlf}
38. Write a computer program to evaluate the following polynomials
p(x)
for
the given values of
x and to evaluate the noise in the values
p(x).
For
each
x,
evaluate
p(x)
in both single and double precision arithmetic; use their
difference as the noise in the single precision value, due to rounding errors
in the evaluation of
p(x).
Use both the ordinary formula (2.9.1) and
Horner's rule (2.9.8)
to
evaluate each polynomial; this should show that the
noise is different in the two cases.
(a)
p(x)
= x
4
-
5.7x
3
-
.47x
2
+
29.865x-
26.1602
with steps of h =
0.1
for x.
(b)
p(x)
= x
4
-
5.4x
3
+ 10.56x
2
-
8.954x + 2.7951
in steps of
h = .001 for x.
1
:5;
X
:5;
1.2
Note: Smaller or larger values of h may be appropriate on different
computers. Also, before using double precision, enter the coefficients
in single precision, for a more valid comparison.
39.
Use complex arithmetic and Newton's method to
calci.J.ldte
a complex root
of
p(z)
= z
4
-
3z
3
+ 20z
2
+ 44z
+54
located near to z
0
=
2.5
+ 4.5i.
40. Write a program to find the roots of the following polynomials
as
accu-
rately as possible.
(a) 676039x
12
-
1939938x
10
+ 2078505x
8
- 1021020x
6
+ 225225x
4
-18018x
2
+
231
(b) x
4
-
4.096152422706631x
3
+ 3.284232335022705x
2
+4.703847577293368x- 5.715767664977294
41. Use a package rootfinding program for polynomials to find the roots of the
polynomials in Problems
38,
39,
and
40.
42.
For
the example
f(x)
=
(x-
1)(x-
2)
· · ·
(x-
7), (2.9.21) in Section 2.9,
consider perturbing the coefficient of
x;
by
f.;X;,
in which f.; is chosen so
that the relative perturbation in the coefficient
of
x;
is the same as that of
126
ROOTFINDING FOR NONLINEAR EQUATIONS
the example in the text in the coefficient
of
x
6
•
What does the linearized
theory (2.9.19) predict for the perturbations in the roots? A change
in
which
coefficient will lead to the greatest changes in the roots?
43.
The
polynomial
f(x)
= x
5
-
300x
2
-
126x + 5005 has
a=
5
as
a root.
Estimate the effect on a of changing the coefficient of x
5
from 1 to 1 +
€.
44.
The
stability result (2.9.19) for polynomial roots can be generalized to
general functions. Let a
be
a simple root
of
f(x)
=
0,
and let
f(x)
and
g(x)
be
continuously differentiable about a. Define F.(x) =
f(x)
+ £g(x).
Let
a(
t:)
denote a Toot of
F.(
x)
= 0, corresponding to a =
a(O)
for small L
To
see
that
there exists such an a(£), and to prove that it is continuously
differentiable, use the implicit function theorem for functions of one vari-
able.
From
this, generalize (2.9.19) to the present situation.
45. Using the stability result in Problem 44, estimate the root
a(
f)
of
x-tan(x)+£=0
Consider
two cases explicitly for roots a of x - tan
(x)
0:
(1) a E
(.5'1T,
1.5'1T),
(2) a E
(31.5'1T,
32.5'1T).
46. Consider the system
.5
.5
x=
----~
1+(x+y)
2
y=
-----=-
l+(x-y)2
Find
a bounded region D for which the hypotheses of Theorem 2.9 are
satisfied. Hint: What will be the sign
of
the components of the root
a?
Also,
what
are the maximum possible values for x and y in the preceding
formulas?
47. Consider the system
y =
.5
+ h · tan -
1
(x
2
+ yl)
Show
that
if h
is
chosen sufficiently small, then this system has a unique
solution
ex
within some rectangular region. Moreover, show that simple
iteration
of
the form (2.10.4) will converge to this solution.
48. Prove Corollary 2.10. Hint: Use the continuity
of
the partial derivatives
of
the components of g(x).
49. Prove
that
the iterates { x
n}
in Theorem 2.9 will converge to a solution
of
x = g(x). Hint: Consider the infinite sum
00
Xo
+ L
[xn+l-
xnJ
n-o
PROBLEMS 127
Its partial sums are
N-1
Xo + L
[xn+l-
xn]
=
XN
n=O
Thus
if
the infinite series converges, say to
a,
then x N converges to
a.
Show
the infinite series converges absolutely by showing
and
using the result
llxn+l-
xnlloo
:$;
A.llxn-
xn-tlloo
Following this, show that a
is
a fixed point
of
g(x).
50. Using Newton's method for nonlinear systems, solve the nonlinear system
The
true solutions are easily determined
to
be ( ±
fi3,
±
113
).
As
an
initial guess, use
(x
0
,
y
0
)
= (1.6, 1.2).
51. Solve the system
using Newton's method for nonlinear systems.
Use each
of
the initial
guesses
(x
0
,
y
0
)
= (1.2, 2.5),
(-
2,
2.5), (
-1.2,
- 2.5), (2, - 2.5). Observe
which
root
to which the method converges, the
number
of iterates required,
and
the speed of convergence.
52.
Using Newton's method for nonlinear systems, solve for all roots of the
following nonlinear system.
Use graphs to estimate initial guesses.
(a) x
2
+ y
2
-
2x
-
2y
+ 1 = 0 x +
y-
2xy
= 0
(b) x
2
+ 2xy + y
2
-
x +
y-
4 = 0
5x
2
-
6xy +
5y
2
+
16x-
16y +
12
= 0
53. Prove that the Jacobian of
g(x) =
x-
F(x) -
1
f(x)
is zero
at
any
root a of f(x) =
0,
provided
F(
a)
is
nonsingular. Combined
with Corollary
2.10 of Section 2.10, this will prove the convergence
of
Newton's
method.
54.
Use
Newton's method (2.12.4) to find the
minimum
value of the function
Experiment with various initial guesses and observe the pattern
of
conver-
gence.
THREE
' .
INTERPOLATION
THEORY
The concept
of
interpolation is the selection of a function
p(x)
from a given
class of functions in such a way that the graph of
y =
p(x)
passes through a
finite set of giyen data points. In most of this chapter we limit the interpolating
function p (
x)
to
being a polynomial.
Polynomial interpolation theory has a number of important uses. In this text,
its primary use is to furnish some mathematical tools that are used in developing
methods in the areas of approximation theory, numerical integration, and the
numerical solution
of
differential equations. A second use is in developing means
- for working with functions that are stored in tabular form.
For
example, almost
everyone is familiar from high school algebra with linear interpolation in a table
of logarithms. We derive computationally convenient forms for polynomial
interpolation with tabular data and analyze the resulting error. It is recognized
that with the widespread use of calculators and computers, there
is
far less use
for table interpolation than in the recent past. We have included it because the
resulting formulas are still useful in other connections and because table interpo-
lation provides us with convenient examples and exercises.
The
chapter concludes with introductions to two other topics. These are
(1)
piecewise polynomial interpolating functions,
spl_ine
functions in particular; and
(2) interpolation with trigonometric functions. .
3.1 Polynomial Interpolation Theory
Let x
0
,
x
1
,
•••
,
xn
be distinct real or complex numbers, and let y
0
,
y
1
,
•••
,
Yn
be
associated function values.
We
now study the problem of finding a polynomial
p (
x)
that interpolates the given data:
p(x;)
=
Y;
i=O,l,
...
,n
(3.1.1)
Does such a polynomial exist, and if so, what
is
its degree? Is it unique? What is a
formula for producing
p(x)
from the given data?
By
writing
for a general polynomial of degree
m,
we
see there are m + 1 independent
131
132 INTERPOLATION THEORY
parameters a
0
,
a
1
,
•••
, am. Since (3.1.1) imposes n + 1 conditions on
p(x),
it
is
reasonable
to
first consider the case
when
m =
n.
Then
we
want
to
find
a
0
,
a
1
,
•••
, an such that
(3.1.2)
This
is
a system of n + 1 linear equations
in
n + 1·unknowns, and solving
it
is
completely equivalent
to
solving the polynomial interpolation problem.
In
vector
and matrix notation, the system
is
Xa
=y
with
X=
[x{]
i,j=0,1,
...
,n
(3.1.3)
The matrix X
is
called a Vandermonde matrix.
Theorem 3.1 Given n + 1 distinct points x
0
,
••.
, xn and n + 1 ordinates
y
0
,
•••
,
Yn•
there
is
a polynomial
p(x)
of
degree~
n that inter-
polates
Y;
at
X;,
i = 0, 1,
...
, n. This polynomial
p(x)
is
unique
among the set of all polynomials of degree at
most n.
Proof
Three proofs of this important result are given. Each will furnish some
needed information and has important uses
in
other interpolation prob-
lems.
(i)
It
can be shown that for the matrix X in (3.1.3),
det(X)
= n
(X·
-
X·)
Os.j<is.n
1
.I
(3.1.4)
(see Problem
1).
This shows that
det(X)
*
0,
since the points
X;
are distinct. Thus X
is
nonsingular and the system
Xa
= y has a
unique solution
a.
This proves the existence and uniqueness of an
interpolating polynomial of degree
~
n.
(ii)
By
a standard theorem of linear algebra
(see
Theorem
7.2
of
Chapter
7),
the system
Xa
= y has a unique solution if and only if
the homogeneous system
Xb
= 0 has only the trivial solution
b =
0.
Therefore, assume
Xb
= 0 for some
b.
Using
b,
define
p(x)
= b
0
+ b
1
x + · · · +bnxn
POLYNOMIAL INTERPOLATION THEORY 133
From
the system
Xb
= 0, we have
p(x;)
= 0
i=0,1,
...
,n
The
polynomial
p(x)
has n + 1 zeros and degree
p(x)::;;
n.
This
is
not
possible unless
p(x)
=
0.
But then all coefficients
b;
=
0,
i = 0,
1,
...
, n, completing the proof.
(iii) We now exhibit explicitly the interpolating polynomial.
To
begin,
we consider the special interpolation problem in which
Y;
= 1
for j
=F
i
for some i, 0
::;;
i
::;;
n. We want a polynomial of degree
::;;
n with
the n zeros
xj,
j
=F
i.
Then
p(x)
=
c(x-
x
0
) · • •
(x-
X;_
1
)(x-
xi+l) · · ·
(x-
xn)
for some constant
c.
The condition
p(x;)
= 1 implies
This special polynomial is written as
(
X-
X-)
l;(x)=JI
x;-~
i=0,1,
...
,n
(3.1.5)
To
solve the general interpolation problem (3.1.1), write
With the special properties
of
the polynomials
l;(x),
p(x)
easily
satisfies (3.1.1). Also, degree
p(x)::;;
n, since all
l;(x)
have de-
gree n.
To
prove uniqueness, suppose
q(x)
is another polynomial
of
degree
::;;
n that satisfies (3.1.1). Define
r(x)
=
p(x)-
q(x)
Then degree
r(x)
::;;
n, and
r(x;)
=
p(x;)
-
q(x;)
=
Y;-
Y;
= 0
i=0,1,
...
,n
Since
r(x)
has n + 1 zeros, we must have
r(x)
= 0. This proves
p(x)
=
q(x),
completing the proof.
1111
Uniqueness is a property that is
of
practical use in much that follows. We
derive other formulas for the interpolation problem (3.1.1), and uniqueness says
134
INTERPOLATION THEORY
they are the same polynomial. Also, without uniqueness the linear system (3.1.2)
would not
be
uniquely solvable; from results in linear algebra, this would imply
the existence
of
data vectors y for which there is no interpolating polynomial
of
degree~
n.
The formula
n
Pn(x)
=
LY;i;(x)
(3.1.6)
i=O
is
called
Lagrange's
formula for the interpolating polynomial.
Example
x-x
1
x-x
0
(x
1
-x)y
0
+(x-x
0
)y
1
PI(x)=
Yo+
YJ=---------
x0
- x
1
x
1
-
Xo
X
1
-
Xo
The polynomial
of
degree s 2 that passes through the three points
(0,
1), (
-1,
2),
and (1, 3) is
(x
+
1)(x-
1)
(x-
O)(x-
1)
(x-
O)(x +
1)
p(x)-
·1+ ·2+
·3
2
-
(0 +
1)(0-
1) (
-1
- 0)(
-1
-
1)
(1
- 0)(1 +
1)
1 3 2
= 1 +
-x
+
-x
2 2
If
a function
f(x)
is
given, then
we
can form
an
approximation
to
it using the
interpolating polynomial
n
Pn(x;
f)=
Pn(x) = L
f(x;)l;(x)
(3.1.7)
i=O
This interpolates
f(x)
at x
0
,
•••
, xn. For example,
we
later consider
f(x)
=
log
10
x with linear interpolation. The basic result used in analyzing the error of
interpolation
is
the following theorem.
As
a notation,
£'{a,
b,
c,
...
} denotes
the smallest interval containing all of the real numbers
a,
b,
c,
...
.
Theorem 3.2 Let x
0
,
x
1
,
..•
, xn be distinct real numbers, and let f be a given
real valued function with n
+ 1 continuous derivatives
on
the
interval
1
1
=
..n"{t,
x
0
,
•••
, xn}, with t some given real number.
POLYNOMIAL INTERPOLATION THEORY
135
Then. there exists g E I, with
f(
t)-
£
J(x.)/.(t)
=
(t-
x()
...
~~-
xn)
J<n+l)(g)
(3.1.8)
j-O
1
1
n + 1 !
Proof
Note that the result
is
trivially true if t
is
any node point, since then both
sides of (3.1.8) are zero. Assume
t does not equal any node point. Then
define
with
n
E(x)
=
J(x)-
Pn(x)
Pn(x)
= L
f(xj)l/x)
j=O
i'(x)
G(x)
=
E(x)-
i'(t)
E(t)
for all x E /
1
i'(x)
=
(x-
x
0
)
• • •
(x-
xJ
(3.1.9)
The function
G(x)
is
n + 1 times continuously differentiable on the
interval
I,,
as
are E(x) and
i'(x).
Also,
i'(xJ
G(x;) =
E(x;)-
i'(t)
E(t)
= 0
i=0,1,
...
,n
G(t) =
E(t)-
E(t)
= 0
Thus G has n + 2 distinct zeros in
Ir
Using the mean value theorem, G'
has n + 1 distinct zeros. Inductively,
GU>(x)
has n + 2 - j zeros in I,,
for j =
0,
1,
...
, n +
1.
Let
~
be a zero
of
G<n+I>(x),
Since
we
obtain
£(n+ll(x)
=
J<n+ll(x)
.y<n+ll(x) =
(n
+ 1)!
(n
+ 1)!
G(n+ll(x)
=
J(n+l)(x)-
E(t)
i'(
t)
Substituting x = g and solving for E(t),
the desired result.
E(t)
=
i'(t)
•
J(n+l)(g)
(n
+ 1)!
136 INTERPOLATION THEORY
This may seem a
"tricky"
derivation,
but
it
is
a commonly used
technique for obtaining some error formulas.
II
Example
For
n = 1, using x in place
oft,
(x
1
-
x)f(x
0
)
+
(x-
x
0
)j(x
1
)
f(x)-
---------
xl-
Xo
(x-
x
0
~(x-
x
1
)
J"(~J
(3.1.10)
for some
~x
E
£{x
0
,
x
1
,
x}. The subscript x
on
~x
shows explicitly that
~
depends
on
x;
usually we omit the subscript, for convenience.
We now apply the n = 1 case to the common high school technique of linear
interpolation in a logarithm table. Let
Then
j"(x)
=
-log
10
ejx
1
,
log
10
e,;,
0.434. In a table, we generally would have
x
0
< x < x
1
.
Then
(x-
x
0
)(x
1
-
x)
E(x)
=
2
This gives
the
upper and lower bounds
log
10
e
.
-~-2-
log
10
e
(x-x
0
)(x
1
-x)
log
10
e
(x-x
0
)(x
1
-x)
--
. <
E(x)
<
--
·
----=--------
x~
2 - -
x~
2
This shows
that
the error function
E(x)
looks very much like a quadratic
polynomial, especially if the distance h = x
1
- x
0
is reasonably small.
For
a
uniform
bound
on
[x
0
,
xrJ,
h
2
.434 .0542h
2
ilog
10
x-
p
1
(x)l
~
-
8
-
2
=
---=--
~
.0542h
2
Xo
X~
(3.1.11)
for x
0
~
1, as is usual in a logarithm table. Note that the interpolation error in a
standard
table is much less for x near 10 than near
1.
Also, the maximum error
is
near
the
midpoint
of
[x
0
,
xr].
For
a four-place table, h = .01,
1
~
x
0
< x
1
~
10
Since the entries
in
the table are given to four digits (e.g., log
10
2 = .3010), this
result is sufficiently accurate. Why do we need a more accurate five-place table if