Исторические замечания и литература

1а. Мы подробно рассмотрели только методы, разработанные Штурмом и автором, потому что только они могут рассматриваться как классические, поскольку базируются на двух очень старых и связанных между собой теоремах. Существуют еще два метода отделения вещественных корней: (i) при помощи дифференцирования, метод, основанный на теореме Ролля [см. статьи Коллинза и Лооса (Collins, Loos, 1976, 1982)], и (ii) метод Коллинза-Акритаса, который базируется на полной модификации теоремы Винсента. Однако оба этих метода не представляют сколько-нибудь значительного интереса, поскольку они основаны на процедуре бисекции (так же, как метод Штурма), теоретическая и практическая эффективность которых ниже, чем у авторского метода цепных дробей 1978 г.

lb. Авторский метод цепных дробей 1978 г. получил первую премию на конкурсе студенческих работ, когда он был впервые представлен на 16-ю ежегодную юго-восточную региональную конференцию ACM в Атланте, Джорждия (апрель 1978).

1с. Метод Коллинза-Акритаса был разработан немедленно после того, как Акритасом была обнаружена в 1975-1976 гг. теорема Винсента, и описан в статьях Коллинза и Акритаса (Collins, Akritas, 1976), Коллинза и Лооса (Collins, Loos, 1982) и Коллинза [в (Rice, 1977)] под названием «модифицированный метод

Успенского». Относительно этого пункта см. статью Акритаса 1986 г. и историческое замечание 7.

2. В книге (Obreschkoff, 1963), с. 61 87, имеются другие доказательства теоремы Фурье, принадлежащие Гурвицу и Лагерру, а также ее обобщение, принадлежащее Обрешкову.

3. Хайндель получил другую оценку для метода Штурма; а именно, он показал, что если — полиномиальное уравнение с целыми коэффициентами от одной неизвестной степени без кратных корней, то время вычислений в методе Штурма — это

Кроме того, вместо отделения сначала положительных, а затем отрицательных корней, как первоначально предложил Штурм, Хайндель вычисляет верхнюю границу b абсолютных значений корней, так что все они находятся в интервале этот интервал затем делится на части.

4. Правило Коши, несмотря на его значимость, не слишком хорошо известно; мы нашли его формулировку только в книге (Obreschkoff, 1963), с. 50-51. Кроме того, Ван дер Слюс (van der Sluis) доказал теорему (теорема 2.7), из которой можно заключить, что правило Коши — наилучшее.

5. Теорема Винсента не упоминалась какими-либо авторами, за исключением Обрешкова (Obreschkoff, 1963) и Успенского (Uspensky, 1948). Автор обнаружил ее в 1975-1976 гг., пересматривал методы отделения вещественных корней уравнений, представленные Успенским. Имеется также следующее обобщение теоремы Винсента [см. статью (Chen, 1987)]. Теорема Ванга (1960 г.): Пусть — полиномиальное уравнение с целыми коэффициентами степени , и предположим, что оно имеет не менее двух перемен знаков в последовательности своих коэффициентов; кроме того, пусть — наименьшее расстояние между любыми двумя из его корней. Пусть — наименьший положительный индекс, такой, что где есть элемент последовательности Фибоначчи и пусть — наименьшее положительное целое, такое, что Бели положить

то произвольная подстановка цепной дроби

с неотрицательным целым и положительными целыми преобразует в уравнение имеющее перемен знаков в последовательности своих коэффициентов. Если то в интервале с (неупорядоченными) концевыми точками [полученном из (V13)] нет корней полинома ). Если то уравнение имеет единственный положительный вещественный корень кратности в интервале

Несмотря на теоретический интерес, эмпирические результаты показывают, что реализация теоремы Ванга работает плохо, и, следовательно, она не представляет практического интереса для отделения кратных корней полиномиальных уравнений; вместо этого следует пользоваться теоремой Винсента в комбинации с разложением на свободные от квадратов множители.

6. Успенский (Uspensky, 1948, р. 298-304) расширил теорему Винсента, чтобы получать верхнюю границу числа подстановок, которые нужно выполнить. Его работа, однако, содержит определенные ошибки в формулировке и доказательстве, которые были исправлены автором (Akritas, ). В этом тексте мы даем правильную версию расширения теоремы Винсента; для полноты мы также добавляем ее доказательство, которое гораздо короче доказательства Успенского благодаря тому, что мы используем лемму 7.3.7; см. также статьи (Akritas, 1981а) и (Akritas, Danielopoulos, 1985).

7а. В статьях Коллинза и Акритаса (Collins, Akritas, 1976b), Коллинза и Лооса (Collins, Loos, 1982) и Коллинза [в (Rice, 1977)] (экспоненциальный) метод Винсента цепных дробей 1836 г. ошибочно приписывался Успенскому, вследствие чего метод Коллинза-Акритаса появился под названием «модифицированный метод Успенского»; это случилось, вероятно, из-за утверждения Успенского (в предисловии к его книге), что он сам изобрел этот метод. Однако, как было подчеркнуто в работах Акритаса (Akritas, 1978а, р. 85-86, 1981а, и 1986), Успенский, собственно, взял метод Винсента и удвоил его время вычислений, потому что не был знаком с

теоремой Бюдана; а именно, после подстановки примененной к некоторому уравнению Успенский должен был выполнять подстановку чтобы удостовериться, что не имеет корней в интервале . (Винсент, естественно, получает эту информацию, пользуясь теоремой Бюдана.)

Что можно рассматривать как вклад Успенского — это только то, что для выполнения подстановки вида он использовал метод Руффини-Горнера. Винсент, напротив, пользовался теоремой о разложении Тейлора.

7Ь. Теорема о разложении Тейлора довольно утомительна для вычислений вручную, но она давала доступную в то время «технологию». Статья Горнера появилась в 1819 г., но Винсент, очевидно, не знал об этом; также и Горнер не сознавал того, что его опередил Руффини в 1804 г. (Cnjori, 1911). В любом случае Акритас и Даниелопулос (Akritait, Dmiielopoulos, 1980) показали, что и теорема о разложении Тейлора, и метод Руффини-Горнера имеют примерно равные времена вычислений.

8. Штурм в своей статье 1835 г. представил решение проблемы, связанной с методом Лагранжа, а именно, когда число корней между двумя последовательными целыми числами больше одного. Штурм фактически использует как последовательность Штурма, так и теорему Винсента, чтобы отделить и аппроксимировать корни с любой точностью. Подробное об этом написано на с. 292-297 и 299-305 статьи Штурма 1835 г.

9. Это находится в полном соответствии с замечанием Винсента в его статье 1836 г., с. 352-353: «I’our approcher davantage de la valeur de cette racine, nous pourrioiiN continuer le calcul en euivant toujours la meme marche; et nous eerioiiH snrs de n’avoir, dans tout.es les transformees subsequentes, qu’une eeitle variation, et par consequent une seule racine positive, laquelle, de plun, ж-rait toujours necesearernent plus grande que l’unite.» («Чтобы лучше аппроксимировать значение этого корня, мы можем продолжать, вычисления, придерживаясь все время той же процедуры; и мы можем быть уверены, что но всех последующих преобразованных уравнениях имеется только одна перемена знаков, а следовательно, только один положительный корень, который, более того, обязательно всегда будет больше единицы».)

10. Сам Винсент не следует этому подходу, потому что в своей статье (с. 353) он утверждает: «1а reduction en fraction continue ne croissant que tres lentement, changeons maintenant not,re marche»

(«поскольку разложение в цепную дробь осуществляется очень медленно, давайте изменим теперь нашу процедуру»).

Abel N.H. Beweis der XJnmoeglichkeit algebraische Gleichungen von hoeheren Graden als den vierten allgemein aufzuloesen. Journal fur die reine und angewandte Mathematik 1, 65-84, 1826.

Akritas A.G. Vincent’s theorem in algebraic manipulation. Ph.D.Thesis, Operations Research Program, North Carolina State University, Raleigh, North Carolina, 1978a.

Akritas A.G. A correction on a theorem by Uspensky. Bulletin of the Gkeek Mathematical Society 19, 278-285, 1978b.

Akritas A.G. The fastest exact algorithms for the isolation of the real roots of a polynomial equation. Computing 24, 219-313, 1980a.

Akritas A.G. An implementation of Vincent’s theorem. Nvmerische Mathematik 36, 53-62, 1980.

Akritas A.G. Vincent’s forgotten theorem, its extension and applies tion. International Journal of Computers and Mathematics with Applications 7, 309-317, 1981.

Akritas A.G. Exact algorithms for the implementation of Cauchy’s rule. International Journal of Computer Mathematics 9, 323-333, 1981.

Akritas A.G. Reflections on a pair of theorems by Budan and Fourier. Mathematics Magazine 55, 292-298, 1982.

Akritas A.G. There is no «Uspensky’s method». Extended Abstract. Proceedings of the 1986 Symposium on Symbolic and Algebraic Computation, (Waterloo, Ontario, Canada), 1986, pp. 88-90.

Akritas A.G., Danielopoulos S.D. On the forgotten theorem of Mr. Vincent. Historia Mathematica 5, 427-435, 1978.

Akritas A.G., Danielopoulos S.D. On the complexity of algorithms for the translation of polynomials. Computing 24, 51-60, 1980.

Akritas A.G., Danielopoulos S.D. A converse rule of signs for polynomials. Computing 34, 283-286, 1985.

Akritas A.G., Ng K.H. Exact algorithms for polynomial real root approximation using continued fractions. Computing 30, 63-76, 1983.

Bocher M. The published and unpublished work of Charles Sturm on algebraic and differential equations. Bulletin of the American Mathematical Society 18, 1-18, 1911-12.

Burnside W.S., Panton A.W. The theory of equations, Vol. 1, 2nd ed., Dover, New York, 1960.

Cajori F. Horner’s method of approx limit ion anticipated by Ruffini. American Mathematical Society Hullrtm 17, 409-414, 1911.

Cajori F. A history of the arithmeticitl methods of approximation to the roots of numerical equation* of one unknown quantity. Colorado College Publications, General Strtet No 51, Science Series Vol. XII, No. 7, pp. 171-287, Colorado Spring*, Colorado, 1910.

Cantor D.G., Galyean P.H., Zimmer II (J Л continued fraction algorithm for real algebraic numbers. Mathematu я of Computation 26, 785-791, 1972.

Chen J. A new algorithm for the isolation of the real roots of polynomial equations. Second International Conference on Computers and Applications (Beijing, People’s Republic of China), 714-719, 1987.

Collins G.E., Akritas A.G. Polynomial real root isolation using Descartes’ rule of signs. Proceedings of the /.97ft' ACM Symposium on Symbolic and Algebraic Computation, Yorktown Heights, NY, 1976, pp. 272-275.

Collins G.E., Loos R. Polynomial real root isolation by differentiation. Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, Yorktown Heights, NY, 1976, pp. 15-20.

Collins G.E., Loos R. Real zeros of polynomials. In Computer Algebra symbolic and algebraic computation*. H. Buchberger, G.E. Collins, and R. Loos, eds, Springer Verlag, New York, Computing Supplement 4, 83-94, 1982.

Dickson L.E. First course in the theory of equations. Wiley, New York, 1922.

Ileindel L.E. Integer arithmetic algorithms for polynomial real zero determination. Journal of the ACM 18, 533-548, 1971.

Ilurwitz A. Ueber den Satz von Budan-Fourier. Mathematische Annalen 71, 584-591, 1912.

Lagrange J.L. Traite de la resolution des equations numiriques. Paris, (n.p.) 1798.

Lloyd E.K. On the forgotten Mr. Vincent. Historia Mathematica 6, 448-450, 1979.

Mahler K. An inequality for the discriminant of a polynomial. Michigan Mathematical Journal 11, 257-262, 1964.

Marcus М., Mine H. Introduction to linear algebra. MacMillan, New York, 1965.

Mignotte M. Sur la complexite de certains algorithms ou intervient la separation des racines d’unpolynome. Revue Frangaise d’Automatiqve, Informatique et Recherce Operationnelle (RAIRO) 10, 51-55, 1976.

Mignotte М., Payafar M. Distance entre les racines d’un polynome. ftAIRO-Analyse Numerique 13, 181-192, 1979.

Ng K.H. Polynomial real root approximation using continued fractions. M.S. Research Report, University of Kansas, Department of Computer Science, Lawrence, KS, 1980.

Nordgaard M.A. A historical survey of algebraic methods of approximating the roots of numerical higher equations up to the year 1819. Teachers College, Columbia University, New York, 1922.

Obreschkoff N. Verteilung und Berechnung der Nullstellen reeller Polynome. VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

Poggendorff J.C. Biographisch-Literarisches Handwoerterbuch zur Ge-schichte der exacten Wissenschaften. J.A. Barth, Leipzig, 1863.

Rice J. Mathematical software III. Academic Press, New York, 1977, pp. 35-68.

Ruffini P. Sopra la determinazione delle radici nelle equazioni numeriche di qualunque grado.... Societa Italiana delle Scienze, 1804.

Rump S.M. Polynomial minimum root separation. Mathematics of Computation 33, 327-336, 1979.

Specht W. Abschaetzungen der Wurzeln algebraischer Gleichungen. Mathematische Zeitschrift 52, 310-321, 1949.

Sturm C. Memoire sur la resolution des equations numeriques. Memoires des Savants Etrangers 6, 271-318, 1835.

Todhunter I. Theory of equations. MacMillan, London, 1882.

Turnbull H.W. Theory of equations. 5th ed. Oliver & Boyd, Edinburgh and London, 1957.

Uspensky J.V. Theory of equations. McGraw-Hill, New York, 1948.

van der Sluis A. Upperbounds for roots of polynomials. Numerische Mathematik 15, 250-262, 1970.

van der Waerden B.L. Erwachende Wissenschaft. Birkhaeuser Verlag, Basel and Stuttgart, 1956.

Verbaeten P. Computing real zeros of polynomials with SAC-1. ACM-SIGSAM Bulletin 9, 8-10, 1975.

Vincent A.J.H. Sur la resolution des equations numeriques. Journal de Mathematiques Pures et Appliquees 1, 341-372, 1836.

Weisner L. Introduction to the theory of equations. MacMillan, New York, 1938.