С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 47
Текст из файла (страница 47)
При k > 1 уравнение (H.) имеет k различныхкорней. При этом в точности один из них — мы будем называть егоглавным корнем уравнения (H.) и обозначать через αk — по модулюпревосходит единицу. Главный корень — вещественное число, удовле1творяющее условию 2 − ¶ αk < 2.kДоказательство. Поскольку предстоит использовать некоторуютехнику теории аналитических функций, мы перейдем к привычномуобозначению z для комплексной переменной и будем рассматриватьуравнение z k − z k−1 − ... − z − 1 = 0, левую часть которого обозначимчерез vk (z).
Положим Vk (z) = (z − 1)vk (z) = z k+1 − 2z k + 1.Уравнение Vk (z) = 0 в сравнении с vk (z) = 0 имеет дополнительныйкорень z = 1; мы докажем утверждение предложения для Vk (z) = 0,См. [, гл. , пп. —], [], [, разд. .., упр. ]. В [] доказано также, чтовсе корни, отличные от главного корня αk , по модулю не превосходят αk − 1 < 1.Об одном семействе алгебраических уравненийk > 1, откуда будет следовать требуемое. Доказательство мы проведемв три этапа, установив справедливость следующих утверждений:(i) для любого k > 1 все корни уравнения Vk (x) = 0 простые (т.
е.имеют кратность 1);1(ii) круг любого радиуса r, 1 < r < 2 − , с центром в z = 0 содерkжит ровно k корней уравнения Vk (z) = 0;(iii) уравнение Vk (z) = 0 имеетмере один вещественh по меньшей1ный корень на полуинтервале 2 − , 2 .kДля доказательства утверждения (i) заметим, прежде всего, чтоíîä(Vk (z), Vk′ (z)) = íîä(Vk (z), z k−1((k + 1)z − 2k)).2kНо Vk (z) не обращается в при z = 0 и при z =. Отсюда следует,k+1что íîä(Vk (z), Vk′ (z)) = 1. Это говорит о том, что корни Vk (z) простые.Для доказательства утверждения (ii) положим Wk (z) = z k+1 − 2z k .Если на некоторой окружности выполняется неравенство | Wk (z) | > 1,то внутри этой окружности полиномы Vk (z) и Wk (z) по теореме Руше имеют одинаковое число корней.
Рассмотрим окружность Sσ радиуса1 + σ, 0 < σ < 1, с центром в z = 0. Так как| Wk (z) | = | z k+1 − 2z k | ¾ | 2z k | − | z k+1 |,то на окружности Sσ выполняется | Wk (z) | ¾ (1 + σ)k (1 − σ). Далее,очевидно, (1 + σ)k ¾ 1 + k σ, и мы получаем, что если σ удовлетворяетнеравенству(1 + k σ)(1 − σ) > 1,(H.)то условия теоремы Руше выполнены, и полином Vk (z) имеет внутри Sσ столько же корней, сколько их имеет Wk (x), т. е.
k. Неравенство (H.) выполнено для всех значений σ, принадлежащих интервалу с концами, являющимися корнями квадратного уравнения1k σ2 − (k − 1)σ = 0, — эти корни суть 0 и 1 − . Это доказывает утверkждение (ii).Наконец, утверждение (iii) следует из того, что vk (1) < 0, vk (2) > 0иприэтомуравнение vk (z) = 0 не имеет корней на интервале11, 2 −.kСм., например, [, гл. , § ] или [, п. .].
Применительно к полиномиальномуслучаю эта теорема допускает следующую формулировку. Пусть полином V (z) предeставлен в виде суммы W(z) + W(z)двух полиномов, и на контуре некоторой областиeзначение | W(z)| меньше значения | W(z) |. Тогда внутри этой области число корнейполиномов V (z) и W(z) одинаково.Приложение HРекуррентное уравнение (H.) имеет, таким образом, общее решение1y(n) = Ck αnk + Ck−1 αnk−1 + ... + C1 α1n −k−1(αk — главный корень характеристического уравнения (H.), всеостальные корни α1 , α2 , ..., αk−1 по модулю не превосходят единицу).
Нас интересует частное решение, удовлетворяющее условиюy(0) = y(1) = ... = y(k − 1) = 0. И без нахождения всех Ci ясно, чтоCk 6= 0, — иначе последовательность y(k), y(k + 1), ... была бы ограниченной.На рис. показано расположение корней уравнений Vk (z) = 0,k = 2, 3, 4.Im zIm z11Re z−101Re z−120−112−1а) z2 − z − 1 = 0б) z3 − z2 − z − 1 = 0Im z1Re z−1012−1в) z4 − z3 − z2 − z − 1 = 0Рис. .Итак, нам удалось обойтись без фактического нахождения корнейхарактеристического уравнения. Более того, речь шла не об одномконкретном уравнении, а о семействе, в которое входят уравнениясколь угодно высоких степеней.Мы получили доказательство предложения . из § .Литература[] С.
А. Абрамов. Исследование алгоритмов одновременного нахождения наибольшего и наименьшего элементов массива // ЖВМи МФ. . Т. , № . С. — .[] С. А. Абрамов. Элементы анализа программ. Частичные функциина множестве состояний. М.: Наука, .[] С. А. Абрамов, Г. Г. Гнездилова. Алгоритм управления вопросником в автоматизированной обучающей системе // Вестн. Моск.ун-та. Сер. . Вычисл. мат. и киб. . № . С. — .[] В.
Б. Алексеев. Введение в теорию сложности алгоритмов: Учебное пособие для студентов. М.: Издательский отдел ф-та ВМиКМГУ, .[] А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, .[] Н. Г. де Брейн. Асимптотические методы в анализе. М.: ИЛ, .[] А. А. Васин, В. В. Морозов. Теория игр и модели математическойэкономики. Учебное пособие. М.: МАКС Пресс, .[] Введение в криптографию / Под общей редакцией В. В.
Ященко.М.: МЦНМО: ЧеРо, .[] Н. К. Верещагин, А. Шень. Начала теории множеств. М.: МЦНМО,.[] М. Н. Вялый. Сложность вычислительных задач // Математическое просвещение, вып. . M.: МЦНМО, . С. —.[] С. Б. Гашков, В. Н. Чубариков. Арифметика. Алгоритмы. Сложность вычислений.
М.: Высшая школа, .[] А. О. Гельфонд. Исчисление конечных разностей. М.: Наука, .Литература[] М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, .[] В. А. Ильин, Г. Д. Ким. Линейная алгебра и аналитическая геометрия. М.: Изд-во Моск. ун-та, .[] А. А. Карацуба, Ю. П. Офман. Умножение многозначных чисел наавтоматах // Докл. АН СССР. . Т.
, № . С. —.[] А. А. Карацуба. Основы аналитической теории чисел. М.: Наука,.[] А. А. Карацуба. Сложность вычислений // Труды Математического института РАН. . Т. . С. —.[] Д. Кнут. Искусство программирования для ЭВМ. Т. . Основныеалгоритмы. М.—СПб.—Киев: ИД «Вильямс», .[] Д.
Кнут. Искусство программирования для ЭВМ. Т. . Получисленные алгоритмы. М.—СПб.—Киев: ИД «Вильямс», .[] Д. Кнут. Искусство программирования для ЭВМ. Т. . Сортировка и поиск. М.—СПб.—Киев: ИД «Вильямс», .[] Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, .[] А. И. Кострикин. Введение в алгебру. М.: Наука, .[] В.
H. Крупский. Введение в сложность вычислений. М.: Факториал-Пресс, .[] С. С. Лавров. Программирование. Математические основы, средства, теория. СПб: БХВ-Петербург, .[] В. H. Латышев. Комбинаторная теория колец: сложность алгебраических алгоритмов. М.: Изд-во Моск.
ун-та, .[] Дж. Макконелл. Анализ алгоритмов. Вводный курс. М.: Техносфера, .[] Ф. Мостеллер. занимательных вероятностных задач с решениями. М.: URSS, .[] А. М. Островский. Решение уравнений и систем уравнений. М.:ИЛ, .Литература[] В. В. Прасолов. Многочлены. М.: МЦНМО, .[] Ф. Препарата, М.
Шеймос. Вычислительная геометрия: введение.М.: Мир, .[] Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы.Теория и практика. М.: Мир, .[] В. К. Романко. Разностные уравнения. М.: БИНОМ. Лабораториязнаний, .[] А. А. Сапоженко. Некоторые вопросы сложности алгоритмов:учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, .[] А. Г.
Свешников, А. Н. Тихонов. Теория функций комплексной переменной. М.: Физматлит, .[] В. Серпинский. задач по теории чисел. Москва—Ижевск: Регулярная и хаотическая динамика, .[] А. Л. Тоом. О сложности схемы из функциональных элементов,реализующей умножение целых чисел // Докл. АН СССР.
.Т. , № . С. — .[] Дж. Хартманис, Дж. Э. Хопкрофт. Обзор теории сложности //Кибернетический сборник. . Вып. . С. —.[] П. Л. Чебышев. Полное собрание сочинений. Т. . М.—Л.: АНСССР, .[] И. Р. Шафаревич. Избранные главы алгебры. М.: Журнал «Математическое образование», .[] Математическая энциклопедия. Т. . М.: Издательство «Советская энциклопедия», .[] S. A. Abramov, M. Bronstein. Hypergeometric dispersion and the orbitproblem // Proceedings of the International Symposiumon Symbolic and Algebraic Computation.
New York: ACM, .P. —.[] M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P // Ann. of Math.(). . V. , № . P. —.[] S. Baase, A. van Gelder. Computer algorithms: introduction to designand analysis. Boston, MA: Addison-Wesley, .Литература[] E. Bach, J. Shallit. Algorithmic number theory. V. . Efficientalgorithms.
Cambridge, MA: MIT Press, .[] P. E. Blanksby, H. L. Montgomery. Algebraic integers near the unitcircle // Acta Arith. . V. . P. —.[] G. Brassard, P. Bratley. Fundamentals of algorithms. EnglewoodCliffs, NJ: Prentice Hall, .[] D. Coppersmith, S. Winograd. Matrix multiplication via arithmeticprogressions // J. Symbolic Comput.
. V. , № . P. —.[] M. J. Fischer, M. O. Rabin. Super-exponential complexity of Presburgerarithmetic // Complexity of computation (Proc. SIAM-AMS Sympos.,New York, ). Providence, RI: AMS, . (SIAM-AMS Proc.;Vol. VII). P. — .[] N. Friedman. Some results on the effect of arithmetics on comparisonproblems // Proc. th IEEE Ann. Symp. on Switching and AutomataTheory. Los Alamitos, CA: IEEE Computer Society, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
