► 22. [20] (P. В. Хемминг (R. W. Hamming).) Докажите, что

Igilni + logioi

с погрешностью, не превышающей 1%! (Таким образом, таблицы натуральных и десятичных логарифмов можно использовать и для получения приближенных значений двоичных логарифмов.)

23. [М25] С помощью рис. 6 дайте геометрическое доказательство того, что

\пху = 1пх + In у.

24. [15] Объясните, как нужно модифицировать метод вычисления логарифмов по основанию 10, приведенный в конце раздела, чтобы его можно было применить для вычисления логарифмов по основанию 2.

25. [22] Предположим, что у нас есть двоичный компьютер (т. е. компьютер, в котором используется двоичная система счисления. - Прим. перев.) и имеется некоторое число х, 1 < X < 2. Покажите, что следующий алгоритм, в котором используются Только операции сдвига, сложения и вычитания в объеме, пропорциональном числу разрядов, которое определяется требуемой степенью точности, можно применить для приближенного вычисления у = logb X.

Ll. [Инициализация.] Присвоить у О, z х с помощью сдвига вправо на 1, к <- 1.

L2. [Проверка окончания.] Если х = 1, то прекратить выполнение.

L3. [Сравнение.] Если ж - г < 1, то присвоить z z с помощью сдвига вправо на 1, к -i- к + I, и повторить этот шаг.

L4. [Замещение значений.] Присвоить х х - z, z <- х с помощью сдвига вправо на к, у <- у + logj(2/(2 - 1)) и перейти к шагу L2.

[Замечание. Описанный метод очень похож на тот метод, который используется в компьютерах для выполнения операции деления. Эта идея, в сущности, принадлежит Генри Бриггсу (Henry Briggs); он применял данный метод (только не к двоичным, а к десятичным операциям) для вычисления таблиц логарифмов, опубликованныз в 1624 году. Нам нужна дополнительная таблица констант logj 2, logj(4/3), logb(8/7) и т. д. до значения, равного точности компьютера. В данном алгоритме преднамеренно делается ошибка, так как числа сдвигаются вправо с тем, чтобы в конечном счете х свелось к 1 и выполнение алгоритма прекратилось. В этом упражнении вы должны показать, что алгоритм конечен и вычисляет приближенное значение logji.]

26. [М27] Определите верхние границы точности алгоритма из предыдущего упражнения, взяв за основу точность, используемую в арифметических операциях.

► 27. [М25] Рассмотрим метод вычисления logigi, описанный в этом разделе. Пусть х.- вычисленное приближенное значение Xk, причем хо определяется из соотношения х(1 - 5) < 10"Хо < х{1 + б), а xfc-из соотношений (18), где выражение (xi) нужно заменить на ук и (xfc i)(l - S) < ук < {xk-i)il + б), где 1 < Ук < ЮО. В этих формулах 6 и б - малые константы, соответствующие верхней и нижней грЕшицам погрешностей округления. Покажите, что если результат вычислений обозначить log х, то через к шагов мы получим

logio х + 2 logio(l - (5) - 1/2 < log X < logio х -Ь 2 log,o(l + б).

28. [МЗО] (Р. Фейнман (R. Feynman).) Придумайте метод вычисления 6", где О < х < 1, используя только операции сдвига, сложения и вычитания (аналогично алгоритму из упр. 25), и проанализируйте его точность.

29. [НМ20] Пусть х-действительное число, большее, чем 1. (а) При каком действительном 6 > 1 величина 6 logj х минимальна? (Ь) При каком целом b > 1 эта величина минимальна? (с) При каком целом Ь > 1 величина (6 + 1) logj х минимальна?

1.2.3. Суммы и произведения

Пусть 01,02,. -. - произвольная последовательность чисел. Часто возникает необходимость в изучении сумм вида oi + ог -Ь----h о„. Такую сумму более компактно

можно записать следующим образом:

Oj или aj. (1)

i=l l<j<n

Если n равно нулю, то по определению значение суммы тоже равно нулю. Наше определение суммы можно обобщить. Если R{j)-это любое соотношение, зависящее от j, то запись

обозначает сумму всех qj, где j - целое число, удовлетворяющее условию Rij)-Если таких целых чисел не существует, то значение суммы (2) по определению принимается равным нулю. Буква j в (1) и (2) -это так называемый немой индекс {шш индексная переменная), который вводится только для удобства записи. Для обозначения индексов суммирования обычно используются буквы г, j, к, т, п, г, s, t (иногда с надстрочными индексами или штрихами). Занимающие много места обозначения сумм, как в (1) и (2), можно заменить более компактной записью Uj или Qj. Знак и немые индексы для обозначения операции суммирования в конечных пределах были введены Ж. Фурье (J. Fourier) в 1820 году.

Строго говоря, обозначение Y.i<j<nj является недостаточно четким, так как не совсем ясно, по какому индексу выполняется суммирование - по j или по п. В данном конкретном случае было бы неразумно считать это суммой значений, для которых п > j. Но можно привести более сложные примеры, в которых индекс суммирования определен недостаточно четко, как в случае < {2k) подобных ситуациях отличить немые индексы от индексов, имеющих самостоятельное значение (т. е. таких, которые фигурируют не только в записи суммы), можно только по контексту. Запись из приведенного выше примера будет иметь смысл, только если либо j, либо к (но не оба) не является немым индексом, т. е. имеет самостоятельное значение.

В основном, мы будем использовать запись (2) только тогда, когда сумма конечна, т. е. когда только конечное число значений j удовлетворяет R{j) и Oj 0. Чтобы найти бесконечную сумму, например

Е °> Е °J = Ol -Ь 02 -h 03 -h • • •, j = l j>l

которая содержит бесконечно много ненулевых слагаемых, неооходимо применить методы вычислений. В этом случае выражению (2) мы будем придавать следующей

смысл:

п-оо

0<j<n

-n<j<0

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

Если под знаком "J]" содержится несколько условий (больше одного), как в формуле (3), значит, должны выполняться все условия одновременно.

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

а) Распределительный закон для произведений сумм: Чтобы понять этот закон, рассмотрим частный случай:

= (oi + a2){bi +b2 + Ьз)

- {aibi + 0162 + 0163) + (0261 + 0262 + 0263)

2 / 3

i=i \j=i

Обычно скобки в правой части равенства (4) опускают и двойную сумму, например T,R(i) (Eso) "ii) записывают в виде 2д(г) T,su) "и-Ь) Замена индекса:

Е° Е"> = Е СД)

R(i) R(j) R(p(j))

В этом равенстве представлены два вида преобразований. В первом случае просто происходит замена индекса суммирования i на j. Второй случай представляет больший интерес. Здесь p{j)-это функция от j, задающая некоторую перестановку на области суммирования; точнее - для каждого целого г, удовлетворяющего соотношению Д(г), должно существовать единственное целое число j, удовлетворяющее соотношению p{j) = i. Данное условие всегда выполняется в следующих важных случаях: p{j) = с + j и p{j) = с - j, где с - целое число, не зависящее от j. Эти случаи важны потому, что на практике они встречаются чаще всего, например

Е Е = Е "j-i- (6)

l<j<n l<J-l<n 2<j<n+l

Советую читателю внимательно изучить этот пример.

Замену j на p{j) можно выполнить не для всех бесконечных-сумм. Такая замена всегда возможна, ecлиp(j) = c±j (как в примере, приведенном выше), но в других