Numerical Methods for Roots of Polynomials - Part II (eBook)

J.M. McNamee, Victor Pan (Autoren)

eBook Download: PDF | EPUB

2013 | 1. Auflage
728 Seiten
Elsevier Reference Monographs (Verlag)
978-0-08-093143-2 (ISBN)

Infos

Numerical Methods for Roots of Polynomials - Part II along with Part I (9780444527295) covers most of the traditional methods for polynomial root-finding such as interpolation and methods due to Graeffe, Laguerre, and Jenkins and Traub. It includes many other methods and topics as well and has a chapter devoted to certain modern virtually optimal methods. Additionally, there are pointers to robust and efficient programs. This book is invaluable to anyone doing research in polynomial roots, or teaching a graduate course on that topic. - First comprehensive treatment of Root-Finding in several decades with a description of high-grade software and where it can be downloaded - Offers a long chapter on matrix methods and includes Parallel methods and errors where appropriate - Proves invaluable for research or graduate course

Textauszug

Introduction

J.M. McNamee and V.Y. Pan

A polynomial is an expression of the form

(1)

If the highest power of is in this equation (1), then the polynomial is said to have degree . According to the Fundamental Theorem of Algebra, proved by Argand in 1814, every polynomial has at least one zero (that is, a value that makes equal to zero), and it follows that a polynomial of degree has zeros (not necessarily distinct). Proving this theorem was attempted by D’Alembert 1746, Euler 1749, de Foncenex 1759, Lagrange 1772, Laplace 1795, Wood 1798, and Gauss 1799, but by modern standards all these attempted proofs were not complete because of some serious flaws (see Smale (1981); Pan (1998)).

Hereafter we often write for a real variable, and for a complex. is a zero of a polynomial and is a “root” of the equation if . A polynomial of degree with any complex “coefficients” has at most complex roots; they can be nonreal even where the are all real. In this case all the nonreal zeros occur in conjugate pairs . The purpose of this book is to describe the numerous known methods that find the zeros (roots) of polynomials.

Actually the calculation of roots of polynomials is the oldest mathematical problem. The solution of quadratics was known to the ancient Babylonians (about 2000 B.C.) and to the Arab and Persian scholars of the early Middle Ages, the most famous of them being Al Khwarismi (c.780–c.850) and Omar Khayyam (1048–1131), both Persians. In 1545 G. Cardano published his opus Ars Magna containing solutions of the cubic and quartic in closed form; the solutions for the cubic had been obtained by his predecessors S. del Ferro and N. Tartaglia and for the quartic by his disciple L. Ferrari. In 1824, however, N.H. Abel proved that polynomials of degree five or more could not be solved by a formula involving rational expressions in the coefficients and radicals as those of degree up to four could be. (P. Ruffini came very close to proving this result in 1799.) Since then (and for some time before in fact), researchers have concentrated on numerical (iterative) methods such as Newton’s famous method of the 17th century, Bernoulli’s method of the 18th, and Graeffe’s method, proposed by Dandelin in 1828. Of course there have been a plethora of new methods in the 20th and early 21st century, especially since the advent of electronic computers. These include the Jenkins-Traub, Larkin and Muller methods, as well as several methods for simultaneous approximation starting with the Durand-Kerner method, actually traced back to Weierstrass. Recently matrix methods have become very popular. A bibliography compiled by the first author J.M. McNamee contains about 8000 entries, of which about 60 were published in the year 2010 alone. For a more detailed account of the rich and exciting history of polynomial root-finding and its greatest impact on the development of mathematics and computational mathematics for four millennia from the Babylonian times and well into the 19th century see, for example, the books Bell (1940) and Boyer (1968) and the surveys Pan (1998, 1997).

Polynomial roots have many applications. For one example, in control theory we are led to the equation

(2)

where is known as the “transfer function” of the system, is the Laplace transform of the input, and is that of the output. usually takes the form where and are polynomials in . Their zeros may be needed, or we may require not the exact values of these zeros, but only the knowledge of whether they lie in the left-half of the complex plane, which indicates stability. This can be decided by the Routh-Hurwitz criterion. Sometimes we need the zeros to be inside the unit circle. See Chapter 14 in Part 2 for details of the Routh-Hurwitz and other stability tests.

Another application arises in certain financial calculations, for example, to compute the rate of return on an investment where a company buys a machine for, (say) $100,000. Assume that they rent it out for 12 months at $5000/month, and for a further 12 months at $4000/month. It is predicted that the machine will be worth $25,000 at the end of this period. The solution goes as follows: the present value of $1 received n months from now is , where i is the monthly interest rate, as yet unknown. Hence

(3)

So

(4)

a polynomial equation in of degree 24. If the term of the lease was many years, as is often the case, the degree of the polynomial could be in the hundreds.

In signal processing one commonly uses a “linear time-invariant discrete” system. Here an input signal at the th time-step produces an output signal at the same instant of time. The latter signal is related to and previous input signals, as well as previous output signals, by the equation

(5)

To solve this equation one often uses the “z-transform” given by:

(6)

A very useful property of this transform is that the transform of is

(7)

Then if we apply (6) to (5) using (7) we obtain

(8)

and hence

(9)

(10)

For stability we must have . We can factorize the denominator polynomial in the above (which is closely linked to computing its zeros ). Then we may expand the right-hand-side of (10) into partial fractions, and finally apply the inverse z-transform to obtain the components of . For example, the inverse tranform of is

(11)

where is the discrete step-function, that is,

(12)

In the common case that the denominator of the partial fraction is a quadratic (for the zeros occur in conjugate complex pairs), we find that the inverse transform is a sin- or cosine- function. For more details, see, for example, van den Emden and Verhoeckx (1989)

The last but not the least application worth mentioning is the computations for algebraic geometry and geometric modelling, in particular the computation of the intersections of algebraic curves and surfaces, which amounts to the solution of systems of multivariate polynomial equations. The most popular current methods (such as elimination based on Gröbner basis computation) reduce the solution to accurate root-finding for high degree univariate polynomial equations.

As mentioned, McNamee has been compiling a bibliography on roots of polynomials since about 1987. Cuurently it consists of three parts: text files bibliog.raw and bibsup.raw, and a Micrsoft ACCESS file BIBLIOG497TEST.mdb; to obtain these files go to the web-site http://www.yorku.ca/mcnamee and click on “Click here to download an ACCESS file”, etc. For furthur details on how to use this database and other web components see McNamee (2002).

We will now briefly review some of the more well-known methods which (along with many variations) are explained in much more detail in later chapters. First we mention the bisection method (for real roots): we start with two values and such that

(13)

(such values can be found, for example, by Sturm sequences -see Chapter 2). For we compute

(14)

then if has the same sign as we set ; otherwise . We continue until

(15)

where is the required accuracy (it should be at least a little larger than the machine precision, usually or ). Alternatively we may use

(16)

Unlike many other methods, we are guaranteed that 15 or 16 will eventually be satisfied. It is called an iterative method, and in that sense is typical of most of the methods considered in this work. That is, we repeat some process over and over again until we are close enough to the required answer (we hardly ever reach it exactly). For more details of the bisection method, see Chapter 7 in this Part.

Next we consider the famous Newton’s method. Here we start with a single initial guess , preferably fairly close to a true root , and apply the iteration:

(17)

Again, we stop when

(18)

or (as in (16)). For more details see Chapter 5 in Part 1.

In Chapter 4 we considered simultaneous methods, such as

(19)

starting with initial guesses . Here the notation is a little different from before, that is is the th approximation to the ith zero .

Another method which dates from the early 19th century, but is still often used, is Graeffe’s. Here (1) is replaced by another polynomial, still of degree n, whose zeros are the squares of those of (1). By iterating this procedure, the zeros (usually) become widely separated, and can then easily be found. Let the roots of be and assume that (we say is “monic”), so that

(20)

Hence

(21)

(22)

with .

We consider this method in detail in Chapter 8 in this Part.

Another popular method is Laguerre’s:

(23)

where the sign of the square root is taken the same as that of (when all the roots are real, so that is real and the expression under the square root sign is positive). A detailed treatment of this method is included in Chapter 9 in this Part.

Next we will briefly describe the Jenkins-Traub method, which is (or was) included in some popular numerical packages. Let

(24)

and find a sequence ...

Produkt-Details

• Erscheint lt. Verlag: 19.7.2013
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Technik
• ISBN-10: 0-08-093143-X / 008093143X
• ISBN-13: 978-0-08-093143-2 / 9780080931432