Гашков С.В. Современная элементарная алгебра в задачах и решениях

где C > 0 – некоторая константа.

8*. Покажите, приведя примеры, что иногда метод множителей лучше, чем бинарный метод, а иногда наоборот. Покажите, что такие примеры встречаются бесконечно часто.

9*. Покажите, приведя примеры, что метод дерева степеней бывает лучше метода множителей и бинарного метода.

10*. Для быстрого вычисления больших чисел Фибоначчи можно использовать следующий прием. Если уже вычислена пара чисел (Fk, Fk−1),

находим еще 6 операциями и применяем бинарный метод.

Докажите, что сложность вычисления Fn не превосходит C log2 n. 11*. Покажите, что многочлен pn (x) = 1 + x + . . . + xn−1 можно вы-

числить с помощью l(n) умножений, одного вычитания и одного деления. 12*. Покажите, что многочлен pn (x) можно вычислить с помощью

2l(n) − 2 умножений и l(n) сложений.

У к а з а н и е. Если xm = xkx j – очередной шаг минимальной цепочки для вычисления xn, то делаем шаг pm = pkx j + pj .

13. Проверьте тождество p2n (x) = (x2n−1 + 1) (x2n−2 + 1) . . . (x + 1). 14*. Покажите, что l(2n − 1) 6 n + 2 log2 n.

Гипотеза Шольца о том, что l(2n − 1) 6 n + l(n) − 1, до сих пор не доказана.

15. Можно обобщить понятие аддитивных цепочек, добавив операцию вычитания. Докажите, что для таких цепочек l(2n − 1) 6 n + 1. Выполняется ли здесь равенство?

Доказано, однако, что при использовании вычитания все равно для

где εn стремится к нулю.

16*. Покажите, как с помощью бинарного метода можно на простейшем калькуляторе с операцией p , но без операции возведения в степень, приближенно вычислять функцию xy , где y – двоично-рациональ- ное число.

В следующих задачах без аддитивных цепочек вполне можно обойтись. 17. Найдите последнюю цифру числа 777 .

18*. Найдите подстановку123456789 1010 .

451236897 А в следующей задаче без бинарного метода возникнут трудности. 19*. Найдите 101010 mod 1999.

§3.7. Приближенное вычисление корней многочленов

Здесь мы кратко опишем некоторые методы приближенного вычисления корней уравнений. Их полезно знать и уметь применять, но знать доказательства совсем не обязательно, тем более что они скорее относятся к анализу, а не алгебре.

Простейший и наиболее старый метод вычисления называется иногда «цифра за цифрой». В применении к вычислению квадратных корней он был открыт еще в Древней Индии. Для приближенного поиска корней произвольных алгебраических уравнений его первым применил Виет. Одной из вариаций этого метода является так называемый «метод вилки», названный так артиллеристами. Идея его такова: если при некотором угле наклона орудия зафиксирован недолет, а при большем угле – перелет, то следующий угол наклона выбирают как среднее арифметическое двух этих углов.

В применении к поиску корней уравнения f(x) = 0 на отрезке [a, b] это выглядит следующим образом. Положим x0 = a, y0 = b, и если на n-м шаге вычисления мы нашли приближения xn, yn такие, что f(xn) f(yn) < 0,

то вычисляем zn = (xn + yn)/2, f(zn), и в случае f(zn) f(xn) < 0 полагаем xn+1 = xn, yn+1 = zn, а в случае f(zn) f(yn) < 0 полагаем xn+1 = zn, yn+1 = yn.

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

Если начальные значения x0, y0 целые, то указанный метод находит разложение корня в двоичную дробь. Если мы хотим найти десятичное приближение, надо каждый отрезок [xn, yn] разбивать на 10 равных частей и искать xn+1, yn+1 такими, что yn+1 − xn+1 = (yn − xn)/10. Иногда

166 Глава III. Многочлены

для поиска очередного приближения вместо уравнения f(x) = 0 на отрез-

ке [xn, yn] рассматривают уравнение g(y) = 0, g(y) = f(xn + (yn −xn)y/10) на отрезке [0, 10], и так можно делать на каждом шаге вычисления. При

этом мы избавляемся от дробей, но сталкиваемся с быстрым ростом коэффициентов у последовательности уравнений.

Для ускорения работы нет необходимости вычислять при этом все 11 значений g(0), . . . , g(10), так как можно, применив метод вилки, сделать это за 3 или 4 вычисления значений g(y).

В этом методе для вычисления f(xn) применяется схема Горнера. Ее использование вдохнуло новую жизнь в этот метод, почему его стали даже иногда называть методом Горнера *.

Самым эффективным методом приближенного вычисления корней является метод Ньютона. К достоинствам этого метода относится то, что он применим не только к многочленам, но и к любым дифференцируемым функциям, и то, что он допускает широкие обобщения, например, с его помощью можно решать системы уравнений, в том числе и в комплексных числах. Идея, на которой он основан, имеет также важные приложения, но мы не будем здесь их рассматривать, а ограничимся только решением алгебраических уравнений.

Другим его достоинством является очень быстрая сходимость. Третье его достоинство – то, что он является итерационным мето-

дом, а эти методы устойчивы относительно ошибок вычислений: если очередная итерация выполнена с ошибкой, то довольно часто это не приводит к ошибке в ответе.

Ньютонова итерация делается следующим образом: если xn – полученное приближение к корню уравнения f(x) = 0, то новое приближение находится по формуле **

f(xn) , xn+1 = xn − f ′ (xn)

где f′ (xn) – производная функции f в точке xn. Геометрический смысл этой формулы таков: нужно через точку (xn, f(xn)) графика функции y = f(x) провести касательную, тогда она пересекает ось Ox в точке xn+1.

Упражнение 67. Докажите предыдущее утверждение.

* До Горнера объем вычислений при использовании этого метода был настолько велик, что один из математиков XVII в. назвал приближенное вычисление корней уравнений работой, недостойной христианина.

** Сама эта формула принадлежит Рафсону и в Англии известна как формула Ньютона– Рафсона.

З а м е ч а н и е. При всех его достоинствах метод Ньютона довольно капризен, он может и не сходится, и пользоваться им нужно умело.

В случае, если уравнение дано в виде f(x) = x (а к этому виду можно привести любое уравнение), можно для его решения использовать простейший итерационный процесс: xn+1 = f(xn). Очевидно, что если y – корень уравнения, то при x0 = y последовательность стабильна: xn = y.

Если f(a) > a, a < b, f(b) < b, функция f(x) непрерывна, монотонно возрастает, и уравнение f(x) = x имеет ровно один корень на отрезке [a, b], то последовательность xn+1 = f(xn) при любом начальном значении сходится к этому корню.

Действительно, если, например, x0 таково, что f(x0) > x0, то последовательность xn+1 = f(xn) монотонно возрастает, ограничена (почему?) и поэтому имеет предел, который в силу непрерывности совпадает с корнем.

Можно доказать, что если в окрестности корня производная функции по модулю меньше единицы, то в этой окрестности указанная последовательность сходится к корню.

Однако, если, например, в окрестности корня выполняется неравенство |f′ (x)| > 1, то эта последовательность удаляется от корня.

П р и м е р ы. 1. Если xn+1 = sin xn, x0 = 1, то xn → 0. 2. Если xn+1 = tg xn, x0 = 1, то xn не стремится к нулю.

Если уравнение не имеет вида f(x) = x, то его можно привести к этому виду по-разному. Иногда после этого метод итераций дает ответ, иногда нет.

П р и м е р ы. 1. Если уравнение x2 = x + 1, положительный корень которого (1 + √5)/2 является так называем золотым сечением, переписать в виде x2 − 1 = x, то итерационная последовательность xn+1 = xn2 − 1 будет либо расходится, либо зацикливаться, так как четная функция f(x) = x2 − 1, убывая, переводит отрезок [−1, 0] в себя, меняя местами его концы, поэтому четный многочлен fn (x) = f(fn−1 (x)) при четном n будет, возрастая, отображать этот отрезок в себя, а при нечетном n будет, убывая, отображать этот отрезок в√себя, и в первом случае уравнение

f (x) = x имеет на нем корни 0, (1 − 5)/2, −1, а во втором случае – один

n √

корень внутри отрезка, которым может быть только (1 − 5)/2. На отрезке [0, 1] корней нет, а вне отрезка есть только корень (1 + √5)/2.

2. Если уравнение x2 = x + 1 переписать в виде x = 1 + 1/x, то ите-

рационная последовательность xn+1 = 1 + 1/xn при x0 > 0 будет сходится

√

к корню (1 + 5)/2. Если возьмем x0 = 1, то полученная последовательность совпадет с уже знакомым нам разложением золотого сечения в цепную дробь.