ENCYCLOPAEDIA OF MA THEMA TICS Supplement Volume I ENCYCLOP AEDIA OF MATHEMATICS Supplement Volume I .. KLUWER ACADEMIC PUBLISHERS Dordrecht / Boston / London Library of Congress Cataloging-in-PubHcation Data ISBN 978-90-481-4896-7 ISBN 978-94-015-1288-6 (eBook) DOl 10.1007/978-94-015-1288-6 Published by Kluwer Academic Publishers, P.O. Box 17, 3300 AA Dordrecht, The Netherlands Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers, 141 Philip Drive, Norwell, MA 02061, U.S.A. In all other countries, sold and distributed by Kluwer Academic Publishers, P.O. Box 322, 3300 AH Dordrecht, The Netherlands Printed on acid-free paper All Rights Reserved © 1997 Kluwer Academic Publishers Softcover reprint of the hardcover 1s t edition 1997 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. ENCYCLOPAEDIA OF MATHEMATICS Managing Editor M. Hazewinkel List of Authors M. Ablowitz, L. Accardi, P. N. Agrawal, R. Aharoni, F. Altomare, S. S. Antman, P. L. Antonelli, F. Argoul, A. Arneodo, H. Attouch, T. Aubin, W. Auzinger, D. Aze, G. Bachman, E. Bach, N. Balakrishnan, A. Banyaga, A. Baragar, V. Barbu, O. E. Barndorff-Nielsen, L. M. Barreira, Ph. Barry, N. L. Bassily, K. J. Bathe, L. M. Batten, W. Beckner, A. Bejancu, D. Benson, W. Benz, E. E. M. van Berkum, A. J. Berrick, F. Beukers, A. Bialostocki, H. Bieri, K. Binder, N. H. Bingham, Ch. Birkenhake, P. Bhesild, T. S. Blyth, I. M. Bomze, C. Bonotto, C. de Boor, P. Borwein, A. Bottcher, F. Bouchut, N. Bouleau, O. 1. Boxma, F. Brackx, P. Brandi, A. Brandstadt, M. Braverman, E. Briem, R. W. Bruggeman, N. G. de Bruijn, B. Buchberger, F. Buekenhout, P. Bullen, A. Bundy, G. Buskes, M. Campanino, L. M. B. C. Campos, C. Cannings, J. Carlson, J. M. F. Castillo, C. Y. Chan, G. Chaudhuri, Qingming Cheng, A. Childs, K. Ciesielski, C. J. S. Clarke, A. M. Cohen, M. Coornaert, C. Corduneanu, G. Crombez, M. Cwikel, A. Davydov, A. S. Deif, W. J. M. Dekkers, F. M. Dekking, M. Denker, J. Desarmenien, H. Diamond, Y. Diers, K. Doets, H. Doss, R. M. Dudley, R. Duduchava, R. Eddy, J. H. J. Einmahl, E. F. Eisele, P. C. Eklof, U. Elias, R. L. Ellis, H. Endo, T. Erdelyi, F. H. L. Essler, B. Fine, P. C. Fishburn, R. W. Fitzgerald, Ph. Flajolet, G. B. Folland, A. T. Fomenko, E. Formanek, J. E. Fornress, R. Frank, A. E. Frazho, R. Fritsch, L. Fuchs, M. Fujii, J. Galambos, A. Garcia-Olivares, M. Gasca, M. O. Gebuhrer, A. Geroldinger, A. A. Giannopoulos, A. P. Godbole, I. Gohberg, R. Goldblatt, S. W. Golomb, R. Gompf, D. H. Gottlieb, J. Grandell, B. Green, B. Grigelionis, L. Gross, K. Gustafson, H. Gzyl, W. J. Haboush, Y. O. Harnidoune, M. E. Harris, H. Hauser, M. Hazewinkel, H. J. A. M. Heijmans, L. Heinrich, J. L. van Hemmen, B. M. Herbst, W. A. Hereman, C. Herrmann, A. Herzer, K. Hess, C. C. Heyde, T. Hida, A. Hildebrand, T. Hill, J. Hinz, J. W. P. Hirschfeld, W. van der Hoek, K. H. Hofmann, H. Holden, C. S. Hoo, C. B. Huijsmans, W. W. J. Hulsbergen, J. Hurrelbrink, D. Iagolnitzer, N. H. Ibragimov, M. Ikle, A. Hehman, J. R. Isbell, A. N. Iusem, A. O. Ivanov, K. R. Jackson, B. Jansen, G. W. Johnson, N. J. Johnson, D. Jungnickel, P. E. Jupp, D. V. Juriev (D. V. Yur'ev), M. A. Kaashoek, J.-P. Kahane, V. A. Kaimanovich, V. Kalashnikov, W. C. M. Kallenberg, PI. Kannappan, H. G. Kaper, H. Kargupta, G. Karpilovsky, K. Keimel, R. Kerman, M. Kibler, T. Kimura, A. U. Klimyk, H.-B. Knoop, S. O. Kochman, H. T. Koelink, J. N. Kok, Yu. S. Kolesov, V. Kolmanovskil, M. Kolster, T. H. Koornwinder, V. M. Kopytov, V. E. Korepin, V. S. Korolyuk, Y. Kosmann-Schwarzbach, A. M. Krall, A. M. Krasnosel'skil, M. A. Krasnosel'skil, A. Krebsz, E Kreimer, E-V. Kuhlmann, S. Kuhlmann, Yu. A. Kuznetsov, I. S. Labouriau, J. C. Lagarias, E. R. Lamken, E. Lanckau, E. Landvogt, S. Lang, M. A. A. van Leeuwen, K. S. Lim, J. H. van Lint, G. L. Litvinov, E. K. Lloyd, G. Longo, J. D. Louck, E. Lutwak, W. Luxemburg, S. N. MacEachern, J. Madden, J. Magnen, M. Mahowald, S. Majid, E. Malkowsky, M. Masumoto, A. Mateescu, S. V. Matveev, G. A. Maugin, T. D. Mavridou, J. C. van der Meer, G. Melan~on, A. Micali, Ch. Micchelli, H. Mikawa, J. S. Milne, M. Mitrea, I. M. Mladenov, P. van Moerbeke, J. M. M~ller, O. Moreno, A. Muravitsky, O. R. Musin, C. Nash, J. van Neerven, V. Nesterov, R. Nest, I. Netuka, Siu-Ah Ng, E Nielson, H. R. Nielson, R. Nishii, R. Norberg, E. Novak, K. Nowak, D. Nualart, S. Ochanine, G. J. Olsder, P. Orlik, L. Ornea, J. O'Rourke, T. W. Palmer, A. Papadopoulos, P. M. Pardalos, R. G. Parker, K. R. Parthasarathy, A. Pasini, V. D. Pathak, I. R. Petersen, R. Phelps, A. Pietsch, A. Pillay, I. Pinelis, Z. Piotrowski, V. Pless, A. V. Pokrovskil, L. Polkowski, A. J. van der Poorten, A. Pott, B. L. S. Prakasa Rao, E. Previato, G. Priest, K. Przeslawski, D. Przeworska-Rolewicz, Gh. Paun, J. M. Rassias, B. D. Reddy, R. A. Renaut, E. Renshaw, J. W. Rice, P. Richetti, M. de Rijke, G. R. Robinson, A. C. M. van Rooy, M. R~rdam, I. Ro~ca, W. Roth, J. Rovnyak, R. Roychoudhury, A. L. Rukhin, A. M. Rushdi, E Ruskey, D. Saari, A. Salomaa, N. W. Sauer, M. Scafati Tallini, A. R. Schep, Ch. Schlindwein, C. P. Schnorr, B. S. W. Schroder, W. Schwarz, B. Schweizer, S.-Y. Shaw, L. A. Shepp, R. T. Shield, B. K. Shivamoggi, T. A. K. Sinha, A. Sklar, N. J. A. Sloane, J. Slominska, P. Sole, B. Solomon, A. J. Sommese, G. Starke, W.-H. Steeb, F. W. Steutel, H. Stichtenoth, M. Stoll, P. Stovicek, E. Straume, S. van Strien, S. J. Summers, L. Takacs, D. Talay, T. Tanino, R. Tolimieri, A. A. Tuzhilin, C. Udri~te, R. G. Underwood, A. S. Ustiinel, M. van de Vel, A. Venkov, J. Verwer, R. Viertl, P. Vopenka, W. R. Wade, M. Waldschmidt, W. D. Wallis, E. Wattel, G. Weaver, H. Wehlan, R. Weiner, D. West, J. Wiegerinck, S. D. R. Wilson, W. S. Wilson, J. A. Winn, H. J. Woerdeman, M. Yor, A. E. Zalesskil, W. Zelazko, R. Zivaljevic PREFACE TO THE FIRST SUPPLEMENT VOLUME The present volume of the ENCYCLOPAEDIA OF MATHEMATICS is the first of several (planned are three) supplementary volumes. In the prefaces to the original first ten volumes I wrote: 'Ideally, an encyclopaedia should be complete up to a certain more-or-Iess well defined level of detail. In the present case I would like to aim at a completeness level whereby every theorem, concept, definition, lemma, construction, which has a more-or-Iess constant and accepted name by which it is referred to by a recognizable group of mathematicians occurs somewhere and can be found via the index.' With these three supplementary volumes we go some steps further in this direction. I will try to say a few words about how much further. The first source of (titles of) articles was the collective of users of the original 10 volume ENCY CLOPAEDIA OF MATHEMATICS. Many users transmitted suggestions for additional material to be covered. These suggestions were taken seriously and checked against the 3.5M keyword list of the FIZISTN database MATH in Karlsruhe. If the hit rate was 10 or better, the suggestion was usually accepted. For the second source I checked the index of volumes 1-9 against that same key phrase list (normal ized). Everything with a hit frequency in the normalized list of 40 or better was checked and, if not really present-a casual mention did not suffice-resulted in an invitation to an expert to contribute something on it. This 'top 40' supplementary list already involves more articles than would fit in a single volume alone and the simple expedient was followed of processing first what came in first (while being carefull about groups of articles that refer heavily to each other and other matters such as timelyness). However, the three supplementary volumes together will surely cover the whole 'top 40' and actually go one step deeper, roughly to the level of the 'top 20' . For the final (as far as I can see at the moment only electronic) version of the ENCYCLOPAEDIA OF MATHEMATICS (WEB and CDROM both) I hope and expect to go as far as the 'top 6'. This means an estimated 32000 articles and an 120K standard key phrase list, a four-fold increase over the printed 13-volume version. It should be noted that if one actually checks one of these 'top 6' standard key phrases in the database MATH, the number of hits is likely to be quite a bit higher; such a search will also pick mentions in title and abstract (and not only those in the key-phrase field). The present volume has its own index. This index is structured exactly like Volume 10, the index to Volumes 1-9. For details I refer to the Introduction to that index volume. The number of authors involved in this volume is substantial and in a sense this ENCYCLOPAEDIA is more and more a community effort of the whole mathematical world. These authors are listed collectively on one of the preliminary pages, and individually below their contributions in the main body vii PRERFACE TO THE SUPPLEMENT VOLUME of this volume. I thank all of them most cordially for their considerable efforts. The final responsability for what to include and what not, etc., however, is mine. The steps from electronic file to printed copy can involve more work than is sometimes realized. For one important step in this process we used to rely on Teun de Graaf of KAP. Regretfully he died a few months ago, just before he was to retire. I thank him gratefully for his work. As is clear from the above, I have made heavy use of that invaluable resource the FIZiSTN MATH database in Karlsruhe. I thank that institution, in particular Dr. Olaf Ninnemann and the 'MATH group', for their assistance and the facilities put at my disposal. As in the case of the original 10 volumes, this one would not have existed without the very considerable efforts of Rob Hoksbergen, who took care of all coordination and administration, and an awful lot of other detail work besides. Bussum, May 1997 PROF. DR. MICHIEL HAZEWINKEL email: [email protected] CWI P.O.Box 94079 1090GB Amsterdam The Netherlands Telephone: +31 - 20 - 5924204 Fax: +31 - 20 - 5924199 viii ________ A _______ _ A PRIORI AND A POSTERIORI BOUNDS IN MA- which implies that under the conditions IIA-18AII < 1, TRIX COMPUTATIONS - Three sources of errors are behind the lack of accuracy in numerical computations: 118xll < IIA-18AII + IIAI~:lfbll (4) data errors associated with the physical model, trun Ilxll - 1 - IIA-18AII cation errors when series are truncated to a number of terms, and rounding errors resulting from finite ma- Setting k(A) IIA -lIIIIAII, from Ilbll :::; IIAllllxl1 one chine precision. Therefore, for the equation f (a, x) = 0 finds in which a is a parameter, if an error occurs in a, the al gorithm returns x and not x. How much the computed W8x :::; 1 - kk((AA)) 11.lAII (1l1f8AAIlII + l1I18bblll)I ' (5) solution x differs from x is an indication of the com IIAII putational accuracy of the result. Since x is unknown, which measures the relative error in the solution x re xl, the norm Ix - taken as an indication of the accu sulting from the errors 8A and 8b in the data. Thus, racy, cannot be calculated, and numerical analysts have the factor k(A), called the condition number of A is the devised bounds for the latter in terms of the variation main factor affecting computational accuracy, since by 8a in a. These bounds are of two types: a priori bounds setting 118AII :::; EIIAII, 118bll :::; Ellbll, where E is the rela and a posteriori bounds. The first are applied prior to tive error in the data, it follows that computation and are usually poor in nature, whereas the second use information extracted from a computa k(A) = lim ~ 118xll (6) tion, and are more indicative. In this article, attention €-tO E Ilxll ' is focussed on the most widely available bounds which i.e., representing the sensitivity of the solution to rel can be implemented to estimate the accuracy of results ative changes E in either A or b, that is, 118xll Illxll ~ and to check the stability of numerical algorithms (cf. E' k(A). So, if k(A) = lOP and E = 5· lO-t, where t is also Stability of a computational process). the machine mantissa, the number of significant digits Linear matrix equations Ax = b, A E Rnxn, x x in becomes t - p. det(A) =I- O. Assuming that the computed solution is equal to x + 8x, where x = A-I band 8x is the error The above analysis lacks accuracy, for the error in IIAII is not equal to EIIAII, since other factors intervene, in the solution resulting from a perturbation 8A in A one of which is the growth factor in the elements as and 8b in b, the perturbed problem sociated with the interchange strategy as well as the size of IIAII, yet it provides an a priori estimate for the (A + 8A)(x + 8x) = b + 8b (1) expected accuracy. Before the late J. Wilkinson it was thought that rounding errors can ruin the solution com implies, by cancelling equal terms, pletely; he showed than an upper bound exists for 118AII 8x = A-1( -8Ax - 8A8x + 8b). (2) and that fear of obtaining poor results is unwarranted [14]. On the contrary, one can also reach total machine It follows that for a consistent matrix-vector norm [4] accuracy. Consider, for example, the matrix 118xll :::; IIA-18Allllxll + IIA-18A11118xll + IIA-18bll ' (10 0) A = 05 (3) 10-5 ' A PRIORI AND A POSTERIORI BOUNDS IN MATRIX COMPUTATIONS IIAII = 105, IIA-lil = 105, and k(A) = 1010, so one c) xnew = X - 8x, re-do from a). expects to loose all significant digits on a lO-digit ma x The algorithm converges very rapidly and -+ x. chine, contrary to the fact that for any right-hand side x Finally, accuracy of is not the only issue which mat b, full accuracy in this situation is reached. This led R. ters to users. There is also the question of stability of the Skeel [10] to consider componentwise estimates of 8x. algorithms. By the stability of x one means that it sat For 18AI ~ EIAI, 18bl ~ Elbl, where 1·1 stands for the isfies the perturbed problem modulus of the vector taken componentwise, one obtains from (2): (A+8A)x=b+8b, (13) 18xl ~ IA-18Allxl + IA-18A118xl + IA-18bl ' (7) in which 8A and 8b are of the order of the machine al giving for p(IA-18AI) < 1, where p is the spectral ra lowed uncertainty. An algorithm which returns x such dius, that that its backward errors 8A and 8b are larger than what 18xl ~ (I -IA-18AI)-1 (IA-18Allxl + IA-18bl)· (8) is anticipated in terms of the machine eps, is unstable. This is checked using the Oettli-Prager criterion [9] For relative perturbations E in A and b, this implies that _I8 Ix _1I < _2_EIc...,:II,--,-A_-l..:.,.;1I c....,.A-,--,:I1 ~I lAx - bl ~ ~A Ixl + ~b, (14) (9) Ilxll - 1 - Ell lA-II lAlli' which has been derived for interval equations [A ± giving ~A]x = [b ± ~b] but is also suitable for systems subject k(A) = IliA-II lAlli, (10) to uncertainties of the form ~A = EIAI and ~b = Elbl. which is a better sensitivity criterion. For the above Thus follows the stability criterion Irl ~ E(IAllxl +Ibl); a (2 x 2)-matrix one has k(A) = 1, as expected. result implemented in most available packages by what However, a practical bound for the error in x re is called a performance index. (For instance, in the IMSL lies on information extracted from computation, since it is given by it shows the true state of affairs. If r = Ax - b is trh =e rAes(ixd u+a l8 xe)r r-or bo =f t hAe8 xtr uoen es ofilnudtiso nIS,x th=e nA -blyr ,w hrietnincge p = l:mS,a:Sxn BN + A N· "L,..nJj =l IX A j I' (15) the a posteriori bound where BN = maxl:Si:Sn Ibil, AN = maxl:Si,j:Sn laijl.) Illf~:1 ~ -111 ~ ::~:: If p < machine eps, the solution is stable [2]. The back IIA :11:1111 k(A) . (11) ward error can be given by 8A = -H ·IAI·diag(sgn(xi)), This shows that k(A) intervenes also here and that Ilrll 8b = H . Ibl, where H is a diagonal matrix and hii = x can be found very small, yet is totally inaccurate as a r;j(IAllxl + Ibl)i, with Ihiil < machine eps. result of the large k( A), [2]. The above bound can still Linear equations Ax = b, A E Rmxn. Independent of be improved by noticing that since A-I is unknown and whether the equations have a unique solution (as in the only an approximate inverse matrix B of A is known, it previous section), more than one solution or no solution can be written in the practical form (only a least-squares solution), the general solution x is 118xll = IIA-l B-1 Brll = (12) given by = II(I - (I - BA))-lBrll < (16) < IIBrl1 where c is an arbitrary vector and A + is the Penrose - 1 - III - BAil' Moore inverse of A, satisfying AA+ A = A, A+ AA+ = provided that III - BAil < 1. A +, (A + A) T = A + A and (AA +) T = AA+ . For a consis Although scientists have elaborated on various tent set of equations the residual Ax - b = (AA + - I)b = bounds for estimating the accuracy of their results, the 0, is a special case. The minimal least-squares solution situation is not so bleak, for the above bounds are not x becomes, therefore, x = A + b. Unlike in the previous the end of the story. After all, can be ameliorated by section, if A undergoes a perturbation EAll in general a technique called the method of iterative refinement, (A + EAd+ cannot be expanded into a Taylor series in very similar to Newton's method for solving non-linear E; it does have a Laurent expansion [2]. For acute per equations (cf. Newton method). Today it is an avail turbations (rank(A) = rank(A + EAl)), from [13] one able facility in most packages (Linpack, Lapack, etc.) finds that and runs as follows: a) compute r = Ax - b; (17) b) solve A8x = r; 2 A PRIORI AND A POSTERIORI BOUNDS IN MATRIX COMPUTATIONS if c) A;t"ew = B - 8A+. II (A + 8A)+ 112 = ar(A ~ 8A)' The algorithm converges and B --+ (AT A)-lAT. = The eigenvalue problem Ax AX, A E Rnxn. Un ar~A)' like in the previous sections, a perturbation 8A in A af IIA+112 = fects both the eigenvalue A and its corresponding eigen ai(A) - al(8A) ::::: ai(A + 8A) ::::: ai(A) + ai(8A), vector x. One of the earliest a priori bounds for I). - AI, i = 1, ... ,r, where)' is the eigenvalue of A + 8A, is the Bauer-Fike theorem [1]. It states that the eigenvalues of A + 8A lie with al ~ ... ~ ar the singular values of A. P. Wedin in the union of the discs also showed that for any A and 8A, Mi = {z: Iz - Ail::::: IIT-lIIIITIII18AII}, (23) (18) i = 1, ... ,n, where J-l has tabulated values for various cases of where T is the modal matrix of A (T-l AT = A) as rank(A) in relation to m and n. It therefore follows that suming A to be non-defective. The bound follows upon the bound for the relative error in A + is given by noticing that since II(A + 8A)+ - A+II < k(A) IIIIMAII1122 ).1 - A - 8A = ().1 - A) [I - ().1 - A)-18A] (19) IIA+112 -J-l1_k(A)~' IIAI12 is singular, one has 11()'1 - A)-18AII > 1. Writing where k(A) = IIA11211A+112 is the spectral condition num ().1 - A)-l = T()'1 - A)-IT-I, ber, which measures the sensitivity of A+ to acute per one finds that turbations in A. To obtain a bound for 118xll/llxli one starts with x + 8x = (A + 8A)+(b + 8b) to find that 1 ::::: IIT()'1 - A)-lT-18AII ::::: 8x= [(A+8A)+-A+]b+(A+8A)+8b. (20) ~ ::::: IITII liT-III 118AII . , Using a decomposition theorem [13] for (A+8A)+ -A+, mIni IA - Ail one finds that [8] which implies (23). The condition number to the prob lem is therefore of the order of k(T) = IITIIIIT-lil. In ::::: l:f:rI~2 k [(2 + 17k)a + (J,] , (21) deed, if the above discs are isolated, then mini I). - Ai I = 18Ail and 18Ail ::::: k(T)118AII. However, unless A is a nor where mal matrix (11T112 = IIT-1112 = 1), the bound in (23) is known to yield pessimistic results. A more realistic cri terion can be obtained. As 1-().1 - A)-18A is singular, then for a vector z =I- 0, z::::: I( ).1 - A)-11IT-1118AIITllzl , Note that the error is dominated by k2(A), unlike the bound in (19), which is dominated by k(A) only. For implying that [3] the special case rank(A) = n < m the above expression min I). - Ail::::: p(IT-1118AIITI), (24) becomes k[(l + 17k)a + (J,]. For rank(A) = m < n it becomes k(2a + (J). Finally, for rank(A) = m = n it which is tighter than (23) for non-normal matrices. reduces to k(a + (J), which is the situation of the previ Moreover, (24) is scale-invariant under the transforma ous section. It should be noted that the above bounds tion A = DBD-l , where D is diagonal. are valid for acute perturbations and that the situation Both the Bauer-Fike bound and the above are valid worsens if 8A increases the rank of A, in which case the for the whole spectrum; thus, a group of ill-conditioned accuracy of A + deteriorates further as eigenvalues affects the bound for the well-conditioned II ones. This led Wilkinson to introduce his Si factors, measuring the sensitivity of the ith eigenvalue alone. From first-order perturbation theory one finds, [4], Again one can follow an iterative scheme of refinement similar to the one mentioned in the previous section to (25) improve on A +. It runs as follows for the full rank situ ation: where xi and yi' are the eigenvector and eigenrow asso a) R = AT - AT AB; ciated with a simple Ai. So, normalizing both of them, b) 8A+ = -BBT R; 1/1yi' xii becomes the Wilkinson factor and is equal 3