Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
BIBLIOGRAPHY
115
been most popular, and further developments of them continue to be made,
as
in
Le (1985). The IMSL and NAG computer libraries include these and other
excellent rootfinding programs.
Finding the roots of polynomials
is
an extremely old area, going back to at
least the ancient Greeks.
7 nere are many methods and a large literature for them,
and many new methods have been developed in the past 2 to 3 decades. As an
introduction to the area, see Dejon and Henrici
(1969), Henrici (1974, chap. 6),
Householder (1970), Traub (1964), and their bibliographies. The article
by
Wilkinson (1984) shows some of the practical difficulties of solving the poly-
nomial rootfinding problem on a computer. Accurate, efficient, automatic, and
reliable computer programs have been produced for finding the roots of poly-
nomials. Among such programs are (a) those
of
Jenkins (1975), Jenkins and
Traub
(1970), (1972), and (b) the program ZERPOL of Smith (1967), based on
Laguerre's method [see Kahan
(1967), Householder (1970, p. 176)]. These auto-
matic programs are much too sophisticated, both mathematically and algorithmi-
cally, to discuss in an introductory text such as this one. Nonetheless, they are
well worth using. Most people would not be able to write a program that would
be as competitive in both speed and accuracy. The latter is especially important,
since the polynomial rootfinding problem can be very sensitive to rounding
errors,
as
was
shown in examples earlier in the chapter.
The study of numerical methods for solving systems of nonlinear equations
and
optimization problems
is
currently a very popular area of research. For
introductions to numerical methods for solving nonlinear systems, see Baker and
Phillips (1981, pt. 1), Ortega and Rheinboldt (1970), and Rheinboldt (1974). For
generalizations of these methods to nonlinear differential and integral equations,
see Baker and
Phillips (1981), Kantorovich (1948)
[~classical
paper in this area],
Kantorovich and Akilov
(1964), and Rail (1969). For a survey of numerical
methods for optimization,
see
Dennis (1984) and Powell (1982). General intro-
ductions are given in Dennis and Schnabel
(1983), Fletcher (1980), (1981), Gill
et al.
(1981), and Luenberger (1984).
As
an example of 'recent research in
optimization theory and in the development of software, see
Boggs
et
al.
(1985).
For
computer programs, see Hiebert (1982) and More et
al.
(1984).
Bibliography
Baker,
C.,
and
C.
Phillips, eds. (1981). The Numerical Solution
of
Nonlinear
Problems. Clarendon Press, Oxford, England.
Boggs,
P.,
R. Byrd, and
R.
Schnabel, eds. (1985). Numerical Optimization 1984.
Society for Industrial and Applied Mathematics, Philadelphia.
Brent,
R.
(1973). Algorithms for Minimization Without Derivatives. Prentice-Hall,
Englewood Cliffs, N.J.
Byrne, G., and
C.
Hall, eds. (1973). Numerical Solution
of
Systems
of
Nonlinear
Algebraic Equations. Academic Press, New York.
Dejon,
B.,
and
P.
Henrici, eds. (1969). Constructive Aspects
of
the Fundamental
Theorem
of
Algebra.
Wiley,
New York.
116
ROOTFINDING
FOR NONLINEAR EQUATIONS
Dekker, T. (1969). Finding a zero
by
means of successive linear interpolation. In
B.
Dejon and
P.
Henrici (eds.), Constructive Aspects
of
the Fundamental
Theorem
of
Algebra, pp. 37-51. Wiley, New York.
Dennis, J. (1984). A user's guide
to
nonlinear optimization algorithms. Proc.
IEEE,
12, 1765-1776.
Dennis, J., and R. Schnabel (1983).
Numerical Methods for Unconstrained Optimi-
zation and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, N.J.
Fletcher,
R.
(1980). Practical Methods
of
Optimization, Vol.
1,
Unconstrained
Optimization. Wiley, New York.
Fletcher, R. (1981).
Practical Methods
of
Optimization, Vol.
2,
Constrained
Optimization. Wiley, New York.
Forsythe, G. (1969). What
is
a satisfactory quadratic equation solver? In
B.
Dejon
and
P. Henrici (eds.), Constructive Aspects
of
the Fundamental
Theorem
of
Algebra, pp. 53-61. Wiley, New York.
Gill, P., W. Murray, and
M.
Wright (1981). Practical Optimization. Academic
Press, New York.
Goldstine, H. (1977).
A History
of
Numerical Analysis. Springer-Verlag, New
York.
Henrici, P. (1974).
Applied and Computational Complex An(llysis, Vol.
1.
Wiley,
New York.
Hiebert,
K.
(1982). An evaluation of mathematical software that solve systems of
nonlinear equations.
ACM
Trans. Math. Softw.,
11,
250-262.
Householder, A.
(1970). The Numerical Treatment
of
a Single Nonlinear Equation.
McGraw-Hill, New York.
Jenkins, M. (1975). Algorithm 493: Zeroes of a real polynomial.
ACM
Trans.
Math. Softw.,
1,
178-189.
Jenkins, M.,
and
J. Traub (1970). A three state algorithm for real polynomials
using quadratic iteration.
SIAM
J.
Numer. Anal.,
7,
545-566.
Jenkins, M.,
and
J. Traub (1972). Algorithm
419-Zeros
of a complex poly-
nomial.
Commun.
ACM,
15, 97-99.
Kahan, W. (1967). Laguerre's method and a circle which contains
at
least one
zero of a polynomial.
SIAM
J. Numer. Anal.,
4,
474-482.
Kantorovich, L. (1948). Functional analysis and applied mathematics.
Usp.
Mat.
Nauk, 3, 89-185.
Kantorovich, L., and G. Akilov (1964).
Functional Analysis
in
Normed Spaces.
Pergamon, London.
Le, D. (1985).
An
efficient derivative-free method for solving nonlinear equations.
ACM
Trans. Math. Softw.,
11,
250-262.
Luenberger, D. (1984). Linear and Nonlinear Programming, 2nd ed. Wiley, New
York.
More, J.,
B.
Garbow, and K. Hillstrom (1980).
User
Guide for
M/NPACK-1.
Argonne
Nat.
Lab. Rep. ANL-80-74.
More,
J.,
and
D. Sorenson. Newton's method. In Studies
in
Numerical Analysis,
G.
Golub (ed.), pp. 29-82. Math. Assoc. America, Washington, D.C.
PROBLEMS
117
More, J., D. Sorenson,
B.
Garbow, and
K.
Hillstrom (1984). The MINPACK
project.
In Sources and Development
of
Mathematical Software, Cowell (ed.),
pp. 88-111.
Prentice-Hall, Englewood Cliffs, N.J.
Neider, A.,
and
R. Mead (1965). A simplex method for function minimization.
Comput.
J.,
7,
308-313.
Ortega, J.,
and
W. Rheinboldt (1970). Iterative Solution
of
Nonlinear Equations
in
Several Variables. Academic Press, New York.
Ostrowski, A. (1973). Solution
of
Equations
in
Euclidean and Banach Spaces.
Academic
Press, New York.
Peters, G.,
and
J. Wilkinson (1971). Practical problems arising in the solution of
polynomial equations.
J. Inst. Math. Its Appl.
8,
16-35.
Petra, F.,
and
V.
Ptak (1984). Nondiscrete Induction and Iterative Processes.
Pitman, Boston.
Powell, M., ed. (1982). Nonlinear Optimization 1981. NATO Conf. Ser. Academic
Press, New York.
Rail, L. (1969). Computational Solution
of
Nonlinear Operator Equations. Wiley,
New
York.
Rheinboldt, W. (1974). Methods for Solving Systems
of
Nonlinear Equations.
Society for Industrial and Applied Mathematics, Philadelphia.
Smith,
B.
(1967). ZERPOL: A zero finding algorithm for polynomials using
Laguerre's method. Dept. of Computer Science,
Univ. Toronto, Toronto,
Ont., Canada.
Traub, J. (1964). Iterative Methods for
the
Solution
of
Equations. Prentice-Hall,
Englewood Cliffs, N.J.
Whitley,
V.
(1968). Certification
of
algorithm 196: Muller's method for finding
roots of
an
arbitrary function. Commun.
ACM
11, 12-14.
Wilkinson, J. (1963). Rounding Errors
in
Algebraic Processes. Prentice-Hall,
Englewood Cliffs, N.J.
Wilkinson, J. (1984). The perfidious polynomial.
In
Studies
in
Numerical Analysis,
G. Golub (ed.). Math. Assoc. America, Washington,
D.C.
Woods, D. (1985). An interactive approach for solving multi-objective optimiza-
tion problems.
Ph.D. dissertation, William Marsh Rice Univ., Houston,
Tex.
Problems
1.
The
introductory examples for
f(x)
=a-
(1/x)
is related to the infinite
product
00
n (1 + r
2
j)
= Limit((1 +
r)(1
+ r
2
)(1 + r
4
)
•••
(1
+ r
2
")]
j-0
n
....
oo
I
J
118
ROOTFINDING
FOR
NONLINEAR
EQUATIONS
By
using formula (2.0.6) and (2.0.9),
we
can calculate the value of the
infinite product. What
is
this value, and what condition on r
is
required for
the infinite product to converge?
Hint: Let r = r
0
,
and write
xn
in terms of
x
0
and r
0
.
2.
Write a program implementing the algorithm Bisect given in Section 2.1.
Use the program to calculate the real roots of the following equations. Use
an error tolerance of € =
10-
5
.
(d) x = 1 +
.3
cos(x)
3. Use the program from Problem 2 to calculate (a) the smallest positive root
of
x-
tan(x)
=
0,
and (b) the root of this equation that
is
closest to
X=
100.
4. Implement the algorithm
Newton
given in Section 2.2. Use it to solve the
equations in
Problem
2.
5. Use Newton's method
to
calculate the roots requested in Problem
3.
Attempt to explain the differences in finding the roots of parts (a) and (b).
6.
Use Newton's method to calculate the unique root of
X +
e-
Bx'
COS
(X
) = 0
with B > 0 a parameter to be set. Use a variety of increasing values of B,
for
example, B =
1,
5,
10,
25,
50.
Among the choices of x
0
used, choose
x
0
= 0
and
explain any anomalous behavior. Theoretically, the Newton
method will converge for any value of
x
0
and B. Compare this with actual
computations for larger values of
B.
7.
An interesting polynomial rootfinding problem occurs in the computation
of
annuities. An amount of P
1
dollars
is
put
into an account
at
the
beginning
of
years
1,
2,
...
, N
1
•
It
is
compounded annually
at
a rate of r
(e.g., r =
.05
means a 5 percent rate of interest). At the beginning of years
N
1
+
1,
...
, N
1
+ N
2
,
a payment of P
2
dollars is removed from the account.
After the last payment, the account
is
exactly zero.
The
relationship of the
variables is
If
N
1
= 30, N
2
=
20,
P
1
= 2000, P
2
= 8000, then what
is
r?
Use a
rootfinding method of your choice.
8. Use the Newton-Fourier method
to
solve the equations in Problems 2
and
6.
PROBLEMS
119
9.
Use the secant method to solve the equations given in Problem
2.
10.
Use the secant method to solve the equation
of
Problem
6.
11. Show the error formula (2.3.2) for the secant method,
f[a,
b,
a]
a-
c
=-(a-
b)(a-
a)-
1
-[-a-, b-]-
12.
Consider Newton's method for finding the positive square root of a >
0.
Derive the following results, assuming x
0
> 0, x
0
=F
Va.
(a)
x =
_:(x
+
~)
n+l 2 n X
n
n
~
0,
and thus xn >
Va
for all n >
0.
(c) The iterates {xn} are a strictly decreasing sequence for n
~
1.
Hint:
Consider the sign
of
xn+l - xn.
with Rei
(xn)
the relative error
in
xn.
(e)
If
x
0
~
.fQ
and
jRel(x
0
)j:::;;
0.1,
bound
Rel(x
4
).
13.
Newton's method
is
the commonly used method for calculating square
roots on a computer. To use Newton's method to calculate
[Q,
an initial
guess
x
0
must be chosen, and it would
be
most convenient
to
use a
fixed
number
of
iterates rather than having
to
test for convergence.
For
definite-
ness, suppose that the computer arithmetic is binary and that the mantissa
contains
48
binary bits. Write
a=
a
0
2'
This can
be
easily modified
to
the form
a=
b.
21
*:::::;
b < 1
with f an even integer. Then
.;a
=
!b
0 2112
and the number
Va
will
be in standard floating-point form, once
!b
is
known.
120 ROOTFINDING FOR NONLINEAR EQUATIONS
This
reduces the problem to that of calculating
fb
for
~
~
b < 1. Use
the linear interpolating formula
x
0
=
t{2b
+
1)
as
an
initial guess for the Newton iteration for calculating
lb.
Bound the
error
fb
- x
0
•
Estimate how many iterates are necessary
in
order
that
which is
the
limit
of
machine precision
for·
b on a particular computer.
[Note
that
the effect
of
rounding errors is being ignored]. How might the
choice
of
x
0
be improved?
14. Numerically calculate the Newton iterates
for
solving x
2
-
1 =
0,
and
use
x
0
= 100,000. Identify
and
explain the resulting speed
of
convergence.
15. (a)
Apply
Newton's method to the function
f(x)
= {
-%-x
x~O
x<O
with
the
root a =
0.
What
is
the behavior
of
the iterates?
Do
they
converge, and if so,
at
what rate?
(b)
Do
the
same as in (a),
but
with
f(x)
= (
~
-P
x~O
x<O
16. A
sequence
{ xn} is said to converge superlinearly
to
a if
n~O
with
en
~
0 as n
~
oo.
Show that in this case,
L
. .
Ia-
xnl
mut
-----
= 1
n-+oo
lxn+l-
xnl
Thus
Ia
-
xnl
=
lxn+l
-
xnl
is increasingly valid as n
~
00.
17.
Newton's
method for finding a root a of
f(x)
= 0 sometimes requires the
initial guess
x
0
to
be
quite close to a in
order
to obtain convergence. Verify
that
this is the case for the root a =
'TT
/2
of
J(x)
=cos
(x) + sin
2
(SOx)
Give
a
rough
estimate of how small !x
0
-
al
should be
in
order to
obtain
convergence to
a.
Hint: Consider (2.2.6).
PROBLEMS
121
18.
Write a program
to
implement Muller's method. Apply it
to
the rootfinding
problems
in
Problems
2,
3,
and
6.
19. Show that x = 1 + tan -
1
(
x)
has a solution a. Find an interval [a, b]
containing a such that for every x
0
E [a, b
],
the iteration
xn+l = 1 + tan -
1
(xJ
n;;:.:O
will
converge to a. Calculate the first
few
iterates and estimate the rate of
convergence.
20. Do the same
as
in
Problem 19, but with the iteration
n;;:.:O
21. To find a root for
f(x)
= 0 by iteration, rewrite the equation
as
x = x +
cf(x)
=
g(x)
for-some-constant c
-=1=
0.
If
a
is
a root of
f(x)
and if
f'(a)
=F-
0,
how should
c be chosen in order that the sequence xn+l =
g(xn)
converges to a?
22. Consider the equation
x=d+hf(x)
with d a given constant and
f(x)
continuous for all
x.
For h =
0,
a root
is
a =
d.
Show that for all sufficiently small h, this equation has a root
a(
h).
What condition
is
needed, if any, in order to ensure the uniqueness of the
root
a(
h)
in some interval about
d?
23. The iteration
xn+l
=
2-
(1
+
c)xn
+ex~
will converge to a = 1 for some
values of
c [provided x
0
is
chosen sufficiently close to a]. Find the values of
c for which this
is
true. For what value of c will the
c~mvergence
be
quadratic?
24. Which
of
the following iterations will converge to the indicated
fixed
point
a (provided x
0
is
sufficiently close to a)?
If
it does converge, give the order
of convergence; for linear convergence, give the rate
oflinear
convergence.
12
(a) xn+l =
-16
+ 6xn
+-
xn
(b)
12
(c)
a=3
a=2
122
ROOTFINDING
FOR NONLINEAR EQUATIONS
25. Show that
xn(x;+3a)
3x;
+a
n~O
is
a third-order method for computing {{i. Calculate
assuming
x
0
has been chosen sufficiently close to
a:.
26. Using Theorem 2.8, show that formula (2.4.11)
is
a cubically convergent
iteration method.
27. Define
an
iteration formula by
Show
that
the order of convergence of { xn} to a
is
at least
3.
Hint: Use
(heorem
2.8, and let
( ) = h( ) _
f(h(x))
g X X
f'(x)
f(x)
h(x)=x---
f'(x)
28. There
is
another modification of Newton's method, similar to the secant
method,
but
using a different approximation to the derivative f'(xn).
Define
n~O
This one-point method
is
called Steffenson's method. Assuming
/'(a)
=F
0,
show
that
this is a second-order method. Hint: Write the iteration as
xn+l = g(xn)· Use
f(x)
=
(x-
a)h(x)
with h(a:)
=I=
0,
and then compute
the formula for
g(x)
in
terms of
h(x).
Having done so, apply Theorem 2.8.
29. Given below
is·
a table of iterates from a linearly convergent iteration
xn+l
= g(xn). Estimate (a) the rate of linear convergence, (b) the fixed
point
a:,
and
(c) the error a - x
5
•
n
xn
0
1.0949242
1
1.2092751
2 1.2807917
3
1.3254943
4 1.3534339
5 1.3708962
PROBLEMS
123
30.
The
algorithm Aitken, given in Section 2.6, can be shown to be second
order in its speed of convergence. Let the original iteration be
x,+
1
=
g(x,),
n
~
0.
The formula (2.6.8).can be rewritten in the equivalent form
{x,_i-
x,_2)2
a =
x,
=
x,_
2
+
-:----·----,-----
{x,_1-
x,_
2
)
-
(x,-
x,_
1
)
n~2
To examine the speed of convergence
of
the Aitken extrapolates,
we
consider the associated sequence
n~O
The values
z,
are the successive values
of
x,
produced in the algorithm
Aitken.
For
g'(
a)
* 0 or
1,
show that
z,
converges to a quadratically. This
is
true even if Jg'(a)J > 1 and the original iteration
is
divergent. Hint: Do
not attempt to use Theorem
2.8
directly, as it will be too complicated.
Instead write
g(x)
= (x
~
a)h(x)
h(a) = g'(a).;,. 0
Use
this to show that
for some function
H(x)
bounded about x =
a.
31. Consider the sequence
n
~
0,
IPI
< 1
with
{3,
y *
0,
which converges to a with a linear rate of p. Let
.X,_
2
be the
Aitken extrapolate:
n~O
Show that
x = a +
ap2"
+ bp4" + c
p6"
n-2
n
where
c,
is bounded
as
n
.-..
oo.
Derive expressions for a and
b.
The
sequence
{.X,}
converges to a with a linear rate
of
p
2
•
32. Let
f(x)
have a multiple root
a,
say of multiplicity m
~
1.
Show that
K(x)
=
f(x)
f'(x)
124
ROOTFINDING
FOR NONLINEAR EQUATIONS
has a as a simple root. Why does this not help with the fundamental
difficulty in numerically calculating multiple roots, namely that of the large
interval
of
uncertainty in
a?
33. Use Newton's method
to
calculate the real roots of the following polynomi-
als
as
accurately
as
possible. Estimate the multiplicity of each root, and
then if necessary, try an alternative
way
of improving your calculated
values.
(a) x
4
- 3.2x
3
+ .96x
2
+ 4.608x - 3.456
(b) x
5
+ .9x
4
-
1.62x
3
- 1.458x
2
+ .6561x + .59049
34. Use the program from Problem 2 to solve the following equations for the
root
a = 1. Use the initial interval [0, 3], and in all cases use € =
10-
5
as
the stopping tolerance. Compare the results with those obtained in Section
2.8 using Brent's algorithm.
(i)
(x-
1)[1 +
(x-
1)
2
]
= 0
(ii) x
2
- 1 = 0
(iii)
-1
+ x(3 +
x(-3
+
x))
= 0
(iv)
(x
- 1) exp (
-1/(x
-
1)
2
)
=.0
35. Prove the lower bound in (2.9.6), using the upper bound
in
(2.9.6) and the
suggestion in
(2.9.7).
36. Let
p(x)
be a polynomial of degree n. Let its distinct roots be denoted by
a
1
,
••.
, ar, of respective multiplicities m
1
,
...
, mr.
(a) Show that
p'(x)
r m
1
-=L-
p(x)
J=l
x-
aJ
(b) Let c be a number for which
p'(c)
*
0.
Show there exists a root a of
p (
x)
satisfying
I
p(c) I
la-cl
~n
p'(c)
37.
For
the polynomial