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

Подождите немного. Документ загружается.

§ 3.6. Аддитивные цепочки 161

Можно считать, что все числа в цепочке разные, так как этого легко

достичь, просто удаляя из нее повторяющиеся числа и располагая числа

в цепочке в порядке возрастания.

Упражнение 66. Докажите, что наименьшее число операций умно

жения, требующихся для возведения числа x в степень n, равно l(n).

Таким образом, вычисление x

требует не 13 умножений, а только 5.

Обозначим λ(n) = ⌊log

n⌋ уменьшенную на единицу длину дво

ичной записи числа n, a ν (n)

––

сумму цифр (другими словами, число

единиц) в ней.

П р и м е р ы. 1. При n = 14, очевидно, λ(14) = 3.

2. Так как 14 = (1110)

, то ν (14) = 3.

Записывая число n в двоичной системе и используя схему Горнера,

можно написать аддитивную цепочку для числа n длины λ(n) + ν (n) −1

следующим образом

n = 2

+ ... + b

= (. .. (2b

+ b

m−1

)2 + ... + b

)2 + b

= b

= 1, a

= 2a

= 2, a

= a

+ b

m−1

, a

= 2a

, ...,

2m−1

= 2a

2m−2

, a

= a

2m−1

+ b

где число удвоений равно m = λ(n), а число прибавлений единицы равно

ν (n) −1.

П р и м е р ы. 1. Так как 14 = (1110)

= 2

+ 2

+ 2 = ((1 ·2 + 1) · 2 +

+ 1) ·2, то получается цепочка 1, 2, 3, 6, 7, 14.

2. Этой цепочке соответствует такой алгоритм возведения в степень:

x, x

, x

= x

·x, x

= (x

)

, x

= x

·x, x

= (x

)

3. Для запоминания последовательности операций в случае ее мно

гократного исполнения можно заменить в двоичной записи показателя

степени 14 = (1110)

каждую единицу, начиная слева (со старших раз

рядов), кроме самой первой, на слог КУ, а каждый нуль

––

на букву K,

тогда получим слово КУКУК, в котором буквы К означают возведение

в квадрат, а буквы У

––

умножение на основание степени.

Тем самым доказана

Теорема 79 (бинарный метод). Справедливо неравенство

l(n) 6 λ(n) + ν (n) −1.

Интересно, что бинарный метод был фактически известен древним

индусам, а задача о нахождении функции l(n) появилась в одном фран

цузском журнале в 1894 г.

11 Гашков

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

В доказательстве следующей теоремы фактически также используется

схема Горнера.

Теорема 80 (А. Брауэр

∗

). При k < log

log

n справедливо нера-

венство

l(n) < (1 + 1

k)⌈log

n⌉+ 2

k−1

−k + 2.

Д о к а з а т е л ь с т в о. Представим n в двоичной записи:

n =

i=0

где α

= 0 или 1, m = ⌈log

n⌉. Разобьем набор (α

, ..., α

) не более чем

на

m + 1

блоков A

, ..., A

, s <

m + 1

, каждый из которых, кро

ме последнего, начинается с 1, состоит из подряд идущих цифр и по

следняя единица в нем отстоит от первой не более чем на k −1 по

зицию, а последний блок состоит ровно из k цифр (несколько подряд

идущих нулей, возможно, стоящих в начале, не входят ни в один из рас

сматриваемых блоков). Числа, двоичными записями которых являют

ся эти блоки, не превосходят 2

−1 и, кроме, возможно, последнего,

нечетны. Пусть эти числа суть a

, ..., a

. Тогда n можно представить

в виде

n = 2

... (2

s−2

s−1

+ a

s−1

) + a

s−2

) + . .. + a

) + a

где l

––

длина блока A

, l

= k и l

+ l

s−1

+ ... + l

= m + 1 −k. Все чис

ла a

, ..., a

s−1

содержатся в аддитивной цепочке 1, 2, 3, 5, 7, ..., 2

−1

длины 2

k−1

+ 1. Поэтому для вычисления n достаточно добавить к ней

последовательность

, 2a

, 4a

, ... , 2

, 2

+ a

s−1

2(2

+ a

s−1

), 4(2

+ a

s−1

), ..., 2

s−1

+ a

s−1

+ a

s−1

) + a

s−2

, ... , 2

s−2

s−1

+ a

s−1

) + a

s−2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(... 2

s−2

s−1

+ a

s−1

) + a

s−2

) + ... + a

) + a

, .. .,

(... 2

s−2

s−1

+ a

s−1

) + a

s−2

) + ... + a

) + a

длина которой равна

+ l

s−1

+ ... + l

+ s + 1 = m + 2 + s −k.

* А. Брауэр доказал эту теорему в 30

х годах XX в.

§ 3.6. Аддитивные цепочки 163

Поэтому

l(n) < (2

k−1

+ 1) + (m + 2 + s −k) < m + 2 +

m + 1

+ 2

k−1

−k.

Можно считать, что n 6= 2

, тогда m + 1 = ⌈log

n⌉ и

l(n) < ⌈log

n⌉(1 + 1

k) + 2

k−1

−k + 2.

Следствие из теоремы 80.

lim

n→∞

l(n)

log

n = 1.

Д о к а з а т е л ь с т в о. Применяем доказанную теорему при

k = λ(λ(n)) − 2λ(λ(λ(n))).

Если нужно быстро вычислить сразу несколько степеней, то можно

построить дерево степеней таким образом. Корнем дерева является 1,

единственная вершина первого уровня, из нее выходит ребро в вершину 2

второго уровня, и когда дерево уже построено до k

го уровня, то, выбрав

любое число n из этого уровня и выписав все числа a

= 1, a

, ..., a

= n,

лежащие на пути из корня до вершины n, соединяем эту вершину с вер

шинами n + a

, .. ., n + a

, которые помещаем на (k + 1)

м уровне. В про

цессе построения повторно одинаковые вершины в дерево, естественно,

не заносятся. Эта процедура называется методом дерева степеней.

Задачи и упражнения к § 3.6

1. Докажите, что ν (n) можно рекуррентно определить следующим об

разом

ν (1) = 1, ν (2n) = ν (n), ν (2n + 1) = ν (n) + 1,

а функцию λ(n) можно рекуррентно определить следующим образом

λ(1) = 0, λ(2n) = λ(2n + 1) = λ(n) + 1.

2. Докажите, что если аддитивная цепочка для числа n имеет длину m,

то n 6 2

3. Докажите неравенство l(n) > log

n и приведите примеры, когда

оно обращается в равенство.

4. Докажите, что если в аддитивной цепочке для числа n имеется k

удвоений и m неудвоений, то n 6 2

k−1

m+3

, где F

––

последовательность

Фибоначчи.

5. Докажите неравенство l(n) 6 2 log

6*. Докажите неравенство l(nm) 6 l(n) + l(m) −1 (метод множи

телей).

11*

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

7*. Докажите следствие из теоремы Брауэра с оценкой

log



1 +

log

C log

log

(log

log



где C > 0

––

некоторая константа.

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

ше, чем бинарный метод, а иногда наоборот. Покажите, что такие приме

ры встречаются бесконечно часто.

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

лучше метода множителей и бинарного метода.

10*. Для быстрого вычисления больших чисел Фибоначчи можно ис

пользовать следующий прием. Если уже вычислена пара чисел (F

, F

k−1

то пару (F

, F

k+1

) находим одним сложением, а пару

, F

2k−1

) = (F

+ 2F

k−1

, F

+ F

k−1

)

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

Докажите, что сложность вычисления F

не превосходит C log

11*. Покажите, что многочлен p

(x) = 1 + x + ... + x

n−1

можно вы

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

12*. Покажите, что многочлен p

(x) можно вычислить с помощью

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

У к а з а н и е. Если x

= x

––

очередной шаг минимальной цепочки

для вычисления x

, то делаем шаг p

= p

+ p

13. Проверьте тождество p

(x) = (x

n−1

+ 1) (x

n−2

+ 1) . . . (x + 1).

14*. Покажите, что l(2

−1) 6 n + 2 log

Гипотеза Шольца о том, что l(2

−1) 6 n + l(n) −1, до сих пор

не доказана.

15. Можно обобщить понятие аддитивных цепочек, добавив операцию

вычитания. Докажите, что для таких цепочек l(2

−1) 6 n + 1. Выполня

ется ли здесь равенство?

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

почти всех n нижняя оценка для l(n) имеет вид

l(n) > log



1 +

1 − ε

log



где ε

стремится к нулю.

16*. Покажите, как с помощью бинарного метода можно на простей

шем калькуляторе с операцией

, но без операции возведения в сте

пень, приближенно вычислять функцию x

, где y

––

двоично

рациональ

ное число.

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

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

17. Найдите последнюю цифру числа 7

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



123456789

451236897



А в следующей задаче без бинарного метода возникнут трудности.

19*. Найдите 10

mod 1999.

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

многочленов

Здесь мы кратко опишем некоторые методы приближенного вычис

ления корней уравнений. Их полезно знать и уметь применять, но знать

доказательства совсем не обязательно, тем более что они скорее отно

сятся к анализу, а не алгебре.

Простейший и наиболее старый метод вычисления называется ино

гда

цифра за цифрой

. В применении к вычислению квадратных корней

он был открыт еще в Древней Индии. Для приближенного поиска корней

произвольных алгебраических уравнений его первым применил Виет. Од

ной из вариаций этого метода является так называемый

метод вилки

названный так артиллеристами. Идея его такова: если при некотором уг

ле наклона орудия зафиксирован недолет, а при большем угле

––

перелет,

то следующий угол наклона выбирают как среднее арифметическое двух

этих углов.

В применении к поиску корней уравнения f(x) = 0 на отрезке [a, b]

это выглядит следующим образом. Положим x

= a, y

= b, и если на n

шаге вычисления мы нашли приближения x

, y

такие, что f(x

) f(y

) < 0,

то вычисляем z

= (x

+ y

)

2, f(z

), и в случае f(z

) f(x

) < 0 полагаем

n+1

, y

n+1

, а в случае f(z

) f(y

) <0 полагаем x

n+1

, y

n+1

Очевидно, что таким путем можно найти все простые корни любого

многочлена с любой заданной точностью. Этот метод хорош еще тем, что

пригоден для поиска корней у любой непрерывной функции, даже в усло

виях, когда нам про нее ничего не известно, но по нашему требованию

вычисляют любые ее значения. В таких условиях этот метод может счи

таться оптимальным.

Если начальные значения x

, y

целые, то указанный метод находит

разложение корня в двоичную дробь. Если мы хотим найти десятичное

приближение, надо каждый отрезок [x

, y

] разбивать на 10 равных ча

стей и искать x

n+1

, y

n+1

такими, что y

n+1

−x

n+1

= (y

−x

)

10. Иногда

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

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

ке [x

, y

] рассматривают уравнение g(y)=0, g(y) = f(x

+ (y

−x

10)

на отрезке [0, 10], и так можно делать на каждом шаге вычисления. При

этом мы избавляемся от дробей, но сталкиваемся с быстрым ростом ко

эффициентов у последовательности уравнений.

Для ускорения работы нет необходимости вычислять при этом все

11 значений g(0), . .., g(10), так как можно, применив метод вилки, сде

лать это за 3 или 4 вычисления значений g(y).

В этом методе для вычисления f(x

) применяется схема Горнера. Ее

использование вдохнуло новую жизнь в этот метод, почему его стали даже

иногда называть методом Горнера *.

Самым эффективным методом приближенного вычисления корней яв

ляется метод Ньютона. К достоинствам этого метода относится то, что

он применим не только к многочленам, но и к любым дифференцируемым

функциям, и то, что он допускает широкие обобщения, например, с его

помощью можно решать системы уравнений, в том числе и в комплексных

числах. Идея, на которой он основан, имеет также важные приложения,

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

алгебраических уравнений.

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

Третье его достоинство

––

то, что он является итерационным мето

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

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

водит к ошибке в ответе.

Ньютонова итерация делается следующим образом: если x

––

полу

ченное приближение к корню уравнения f(x) = 0, то новое приближение

находится по формуле **

n+1

= x

−

f(x

)

′

)

где f

′

)

––

производная функции f в точке x

. Геометрический смысл

этой формулы таков: нужно через точку (x

, f(x

)) графика функции

y = f(x) провести касательную, тогда она пересекает ось Ox в точ

ке x

n+1

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

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

лик, что один из математиков XVII в. назвал приближенное вычисление корней уравнений

работой, недостойной христианина.

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

––

Рафсона.

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

С помощью метода Ньютона очень быстро вычисляются квадратные

корни и корни более высокой степени.

П р и м е р ы. 1. Для квадратного корня

√

N ньютонова итерация *

имеет вид

n+1





2. Для корня m

й степени

√

N ньютонова итерация имеет вид

n+1



(m −1)x

m−1



Упражнение 68. Покажите, что это действительно ньютоновы ите

рации в применении к уравнению x

−N = 0, N > 0.

Можно доказать, что они будут почти всегда сходится к корню неза

висимо от выбора начального значения x

. Для квадратного корня это

можно сделать совсем элементарно.

Упражнение 69. 1. Докажите для ньютоновых приближений к

√

тождество

−

√



−

√



2. Докажите, что если



−

√



< 1, то lim

n→∞

√

N, а если



−

√



> 1, то lim

n→∞

= −

√

Однако для ускорения вычислений лучше взять x

как можно ближе

к корню. Например, если 1

2 6 N < 1, то простейшее наилучшее при

ближение есть 0,5903N + 0,4173. После этого уже две итерации дают

9 десятичных знаков после запятой.

Упражнение 70. Проверьте это.

Если 0,1 6 N 6 10, то в качестве приближения с точностью 1

12 мож

но взять (1 + 4N)

(4 + N).

В общем случае неизвестны удобные необходимые и достаточные

условия сходимости метода Ньютона при данной начальной точке x

Приведем без доказательства некоторые достаточные условия его схо

димости.

Теорема 81 (Фурье

∗∗

). Пусть функция f(x) определена на от-

резке [a, b], на его концах имеет разные знаки (т. е. f(a) f(b) < 0),

* Кажется, известная еще древнегреческом математику Герону Александрийскому.

** Ж. Фурье (Jean Baptiste Joseph Fourier, 1768

–

1830)

––

знаменитый французский ма

тематик. Участник Египетской экспедиции Наполеона.

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

имеет на нем единственный корень и две производные, причем

везде f

′

(x) f

′′

(x) 6= 0, и f(a) f

′′

(a) > 0. Тогда при x

= a ньютоновы ите-

рации x

сходятся к корню, причем если выполнить еще итерации

по формуле

n+1

= y

− f(y

)

′

), y

= b

(похожей на ньютоновы итерации, но вместо y

в одном месте

используется x

), то y

тоже будет сходится к корню, но с другой

стороны. Если f

′′

(x) непрерывна на отрезке [a, b], то

lim

n→∞

n+1

−x

n+1

−x

)



′′

(c)

′

(c)



где c

––

искомый корень.

З а м е ч а н и е. Словами доказанную формулу формулируют так:

расстояние между x

и y

убывает по квадратичному закону. Это очень

быстро, гораздо быстрее, чем в методе вилки. Но последовательность y

дает гораздо худшее приближение к корню, чем x

, а именно, доказа

но, что

lim

n→∞



−c



= +∞.

Поэтому в качестве приближения берут x

, а y

используют только для

контроля достигнутой точности (иногда можно обойтись и без вычисле

ния y

Для ускорения сходимости последовательности y

Данделен * пред

ложил использовать итерации

n+1

= y

− f(y

)

−x

f(y

) − f(x

)

Вычислять их немного сложнее, но зато справедлива

Теорема 82 (Данделен). Если выполнены условия Фурье, то

lim

n→∞



−c



= g(y

где g

––

некоторая монотонная функция, причем

lim

−x

|→0

g(y

) = 0.

В качестве ответа обычно берут среднее арифметическое x

и y

при

последней итерации. При решении алгебраических уравнений для вычис

ления значений f(x) используют схему Горнера.

* Ж. Данделен (Germinal Pierre Dandelin, 1794

–

1847)

––

бельгийский математик и ин

женер.

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

З а м е ч а н и е. При всех его достоинствах метод Ньютона довольно

капризен, он может и не сходится, и пользоваться им нужно умело.

В случае, если уравнение дано в виде f(x) = x (а к этому виду можно

привести любое уравнение), можно для его решения использовать про

стейший итерационный процесс: x

n+1

= f(x

). Очевидно, что если y

––

корень уравнения, то при x

= y последовательность стабильна: x

= y.

Если f(a) > a, a < b, f(b) < b, функция f(x) непрерывна, монотонно

возрастает, и уравнение f(x) = x имеет ровно один корень на отрезке

[a, b], то последовательность x

n+1

= f(x

) при любом начальном значении

сходится к этому корню.

Действительно, если, например, x

таково, что f(x

) > x

, то после

довательность x

n+1

= f(x

) монотонно возрастает, ограничена (почему?)

и поэтому имеет предел, который в силу непрерывности совпадает

с корнем.

Можно доказать, что если в окрестности корня производная функции

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

вательность сходится к корню.

Однако, если, например, в окрестности корня выполняется неравен

ство |f

′

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

П р и м е р ы. 1. Если x

n+1

= sin x

, x

= 1, то x

→0.

2. Если x

n+1

= tg x

, x

= 1, то x

не стремится к нулю.

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

виду по

разному. Иногда после этого метод итераций дает ответ, ино

гда нет.

П р и м е р ы. 1. Если уравнение x

= x + 1, положительный корень

которого (1 +

√

2 является так называем золотым сечением, перепи

сать в виде x

−1 = x, то итерационная последовательность x

n+1

= x

−1

будет либо расходится, либо зацикливаться, так как четная функция

f(x) = x

−1, убывая, переводит отрезок [−1, 0] в себя, меняя местами

его концы, поэтому четный многочлен f

(x) = f(f

n−1

(x)) при четном n

будет, возрастая, отображать этот отрезок в себя, а при нечетном n будет,

убывая, отображать этот отрезок в себя, и в первом случае уравнение

(x) = x имеет на нем корни 0, (1 −

√

2, −1, а во втором случае

––

один

корень внутри отрезка, которым может быть только (1 −

√

2. На от

резке [0, 1] корней нет, а вне отрезка есть только корень (1 +

√

2. Если уравнение x

= x + 1 переписать в виде x = 1 + 1

x, то ите

рационная последовательность x

n+1

= 1 + 1

при x

> 0 будет сходится

к корню (1 +

√

2. Если возьмем x

= 1, то полученная последователь

ность совпадет с уже знакомым нам разложением золотого сечения в цеп

ную дробь.

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

3. Если уравнение x

= x + 1 переписать в виде x =

√

1 + x, то ите

рационная последовательность x

n+1

√

1 + x

при x

> 0 будет сходится

к корню (1 +

√

2. Если возьмем x

= 1, то получим красивую, но бес

полезную с вычислительной точки зрения формулу

1 +

√

1 +

√

1 + ... .

Итерационные последовательности вида f

(x) = f(f

n−1

(x)), в особен

ности не сходящиеся и зацикливающиеся, вызывают в настоящее время

большой интерес. Их исследование нетривиально даже в случае квадрат

ного трехчлена.

Рассмотрим простой пример. Пусть f(x) = 2x

−1, тогда f

(x)

––

чет

ный многочлен степени 2

, совпадающий с многочленом Чебышёва *

(x). Этот многочлен переводит отрезок [−1, 1] в себя, пробегая его 2

раз, точнее, его можно разбить на 2

отрезков монотонности, каждый

из которых отображается на отрезок [−1, 1], многочлен имеет 2

корней

на этом отрезке и на единицу больше чередующихся экстремумов.

Упражнение 71. Докажите это.

Впрочем, то же самое верно и для многочлена Чебышёва любой сте

пени.

Из приведенных фактов следует, что уравнение f

(x) = x имеет 2

корней.

Любой корень y уравнения f

(x) = x, не являющийся корнем подоб

ных уравнений меньшей степени, порождает итерационную последова

тельность периода n.

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

2. Используя формулу T

(x) = cos(n arccos x) и применяя тригономет

рию, найдите все корни уравнения T

(x) = x.

Использование идеи итерации позволяет иногда решать не только

нетривиальные уравнения, но и системы, например, система











f(x

) = x

;

f(x

) = x

;

f(x

) = x

сводится к уравнению f

(x) = f(f(f(x))) = x.

* Общее определение этих многочленов будет дано в § 4.17.