AOP_Tom1 (1021736), страница 13
Текст из файла (страница 13)
Следующие два примера, рассматриваемые (х,1/х) в любом учебнике по теории вычислений, проливают свет на то, почему логарифмы Непера за- (1, о) (х, 0) служили название "натуральных". (а) На рис. 6 Рис. б. Натуральный логарифм. площадь заштрихованной области равна 1пх. (Ь) Если банк выплачивает сложные проценты по ставке г, начисляемые каждые полгода, то прибыль на каждый доллар составит (1+г/2)т долларов; если начисление происходит каждый квартал, то вы получите (1+ г/4) 4 долларов; если же начисление происходит каждый день, то вы получите (1+г/365)звв долларов. Если бы проценты начислялись непрерывно, то вы получили бы в точности е" долларов на каждый доллар (если не учитывать ошибку округления). В нашу компьютерную эпоху многие банки уже фактически достигли в своей работе этой предельной формулы. История возникновения и развития понятий "логарифм" и "степень" приводится в ряде интересных статей Ф.
Кэджори (Е. Са)об), АММ 20 (1913), 5-14, Зо — 47, 75-84, 107-117, 148-151, 173-182, 205-210. В заключение этого раздела выясним, квк вычислять логарифмы. Один способ непосредственно вытекает из соотношения (7): если положить 5* = у и возвести все части этого соотношения в степень 104, то для некоторого целого п4 получим 5~ ( ~о (5~и 4 У (16) 1ойло х = и+ Ьл/2+ Ьг/4+ Ьз/8+ Сначала сдвинем десятичную точку в числе х влево или вправо, чтобы получить 1 < х/10" < 10; таким образом мы определим целую часть числа )ойщ х, т.
е. и. Чтобы найти значения 6|, Ьг, ..., положим хо = х/10" и для )с > 1 получим Ь|„. = О, хл =х|,, если х. < 10: г г Ьь = 1, хл = хгл,/10, если хлг, > 10. (18) Корректность этой процедуры следует из того, что 1 < г*/ц)гл)п-лл|/г-|- "~-лл/г~) < ц) для к = О, 1, 2,..., а это можно легко доказать по индукции, На практике мы должны проводить вычисления только с конечной точностью, поэтол|у нельзя считать равенство хл = хл точным.
На самом деле можно считать, г что хл = хлг только приблиолсснно с точностью до некоторого десятичного знака. Например, приведем расчеты для !ойш2, выполненные с точностью до четырех значащих цифр: хо = 2 000' х, = 4.000, 1.000, хг -- 2.500, х„= 6.5о4, хл = 4.295, х~ —— 1.845 Ье = 3404, Ьг хэ —— 1.159, 6л хэ — — 1 343, 6э хш — — 1.804, Ь! е 1; 0; 1; 0; 0 ит.д. ь,=о: Ьг —— 1; ь = о; ь = о; Ь, = 1; Погрешность вычислений приводит к росту и распространению ошибок; так, например, истиняое округленное значение хщ равно 1,798.
Накопление ошибок в конечном счете приведет к.тол|у, что Ьш будет вычислено неточно, и мы получим двоичное представление (0.0100110100010000011...)г, соответствующее десятичнол|у представлению 0.301031..., а не истинному значению, которое дается в равенстве (10), Для каждого подобного метода необходимо оценивать величину погрешности вычислений, возникающей из-за ошибок округления. В упр. 27 устанавливается верхняя граница погрсшности: а если проводить вычисления с точностьк, до четырех чисел после десятичной точки, как было показано в примере выше, то получим гарантию, что значение логарифма будет вычислено с погрешностью, не превышающей 0.00044.
Первоначально полученное значение логарифма является более точным потому, что значения хе, х|, хг и хз были вычислены точно. Таким образол|, все, что нам нужно сделать для получения логарифма у, — возвести у в эту огромную степень и найти такое т, чтобы результат лежал между т- и т + 1-й степенями Ь. Тогда искомый результат будет ранен гп/10" с точностью до )г-го десятичного знака. Если несколько модифицировать этот явно непрактичный метод, получим простую и удобную процедуру.
Сейчас мы покажем, как вычислить 1ой,р х и выразить результат в двоичной системе; Приведенный метод прост и довольно интересен, но, скорее всего, это не самый лучший способ вычисления логарифмов на компьютере. Еще один метод описан в упр. 23 УПРАЖНЕНИЯ 1. [ОО] Чему равно наименьшее положительное рациональное число? 2. [00] Может ли выражение 1+ 0.239999999...
быть десятичным представлением действительного числа? 3. [02] Чему равно ( — 3) г? 4. [05] Чему равно (0.125) ггз? б. [05] Мы определили действительные числа в терминах десятичного представления. Подумайте, как можно определить их в терминах двоичного представления, и приведите аналог соотношения (2). 6. [10] Пусть х = т+00~0г .. и у = и+О е~ег...— действительные числа. Сформулируйте правило, которое на основе десятичного представления позволяет определить, какое из неравенств верно: х = у, х < у или х > у.
7. [М28] Для заданных целых чисел х и у докажите правила возведения в степень на основе определения (4). 9. [25] Пустын — целое положительное число. Докажите, что у любого положительного действительного числа н есть единственный положительный корень т-й степени, описав метод последовательного вычисления элементов десятичного представлении этого корня: н,0н0г, .... 9.
[М28] Для заданных рациональных чисел х и у докажите правила возведения в степень, предполагая, что эти правила выполняются для целых чисел х и у. 10. [18] Докажите, что 1обш 2 не является рациональным числом. ь 11. [10] Если Ь = 10 и х = 1обш 2, то сколько десятичных знаков числа х нужно знать, чтобы определить три первых десятичных знака в десятичном представлении Ь*? [Замечание. Можете использовать результаты упр.
10.] 12. [02] Объясните, почему равенство (10) следует из равенств (8). ь 13. [М28] (а) Пусть х —,положительное действительное число, а и — положительное це- лое числа. Докажите неравенство ~/1+ х — 1 ъ х/и. (Ь) Используйте полученный резуль- тат для доказательства утверждения, следующего за соотношением (7), 14. [15] Докажите равенство (12).
13. [10] Докажите илн опровергните следующее равенство: !обе х/у = !оягх — !обе у при х,у > О. 10. [00] Как можно выразить !об,е х через !и х н 1н 10? ь 17. [05] Чему равны !332, !об з., !не, !обе 1 и !обе(-1)? 19. [10] Докажите или опровергните следующее равенство: !ойэ х = -', !2х. ь 19. [20] Поместится ли целое число и, десятичное представление которого состоит из 14 цифр, в компьютерном слове емкостью 47 бит плюс бит знака? 20. [10] Существует ли простое соотношение, связывающее !об,а 2 и !об 10? 21.
[15] (Логарифмы агн логарифмов.) Выразите !обе !ояг х через !н !их, 1н 1нЬ и 1нЬ. ° 22. [30] (Р. В. Хемминг (К. Ч!. Ншпш!п8).) Докажите, что !8х ш !и х+ !08,а х с погрешностью, не превышающей 1%! (Таким образом, таблицы натуральных и десятичных логарифмов можно использовать и для получения приближенных значений двоичнык логарифмов.) 23.
(М25] С помощью рис. б дайте геометрическое доказательство того, что !Пху = 1пх+ 1пу. 24. [!о] Объясните, как нужно модифицировать метод вычисления логарифмов по основанию 10, приведенный в конце раздела, чтобы его можно было применить для вычисления логарифмов по основанию 2. 28. [88] Предположим, что у нас есть двоичный компьютер (т. е, компьютер, в котором используется двоичная система счисления.— Прим. перев.) и имеется некоторое число х, 1 < х < 2. Покажите, что следующий алгоритм, в котором используются только операции сдвига, сложения и вычитания в объеме, пропорциональном числу разрядов„которое опрецеляетсн требуемой степенью точности, можно применить для приближенного вычисления У = !обэ х. Ь1. [Инициализация.] Присвоить у е- О, х ь- х с помощью сдвига вправо на 1, й е- 1.
Ь2. [Проверка окончания,) Если х = 1, то прекратить выполнение. ЬЗ. [Сравнение.] Если х — х < 1, то присвоить х ь- х с помощью сдвига вправо на 1, !с с — )с+ 1, и повторить этот шаг. Ь4. [Замещение значений.] Присвоить х е- х — х, х е- х с помощью сдвига вправо на й, у е- р+ !оба(2"/(2" — 1)) и перейти к шагу Ь2.
[Замечание. Описанный метод очень похож на тот метод, который используется в компьютерак для выполнения операции деления. Эта идея, в сущности, принадлежит Генри Бриггсу (Непгу ВП88э); он применял данный метод (только не к двоичным, а к десятичным операциям) для вычисления таблиц логарифмов, опубликованных, в 1624 году. Нам нужна дополнительная таблица констант !обэ 2, !обь(4/3), !обэ(8/7) н т.
д. до значения, равного точности компьютера. В данном алгоритме преднамеренно делается ошибка, так как числа сдвигаются вправо с тем, чтобы в конечном счете х свелось к 1 и выполнение алгоритма прекратилось. В этом упражнении вы должны показать, что алгоритм конечен и вычисляет приближенное значение !обэ х.] 26. [М87] Определите верхние границы точности алгоритма из предыдущего упражнения, взяв за основу точность, используемую в арифметических операциях.
° 27. [МЯо] РасслютРим метод вычислениЯ !обьэ х, описанный в этом Разделе. ПУсть х'„— вычисленное приближенное значение хю причем хо определяется нз соотношения х(1 — 4) < 10"хэ < х(1+ е), а хь — из соотношений (18), где выражение (х~ь,) нужно заменить на рь и (хь,) (1 — 4) < уь < (х'„,) (1 + е), где 1 < уь < 100. В этик формулах 4 и е — малые консганты, соответствующие верхней и нижней границам погрешностей округления. Покажите, что если результат вычислений обозначить 1о8' х, то через !с шагов мы получим !обю т+ 2!ой~о(1 б) 1/2" < 1о8' х < 1об о х+ 2 !оя о(1+ е). 28. [МЮО] (Р. Фейнман (К.
Реуншап).) Придумайте метод вычисления Ь*, где 0 < х < 1, используя только операции сдвига, сложения и вычитания (апйдогично алгоритму из упр. 25),и проанализируйте его точность. 29. (НМ20] Пусть т — действительное число, большее, чем 1. (а) При каком действительном Ь > 1 величина Ь!обет минимальна? (Ь) При каком целом Ь > 1 эта величина минимальна? (с) При какам целом Ь > 1 величина (Ь+ 1) 1об! т минимальна? 1.2.3. Суммы и произведения Пусть аг, аг,... — произвольная последовательность чисел. Часто возникает необходимость в изучении сумм вида а! + аг + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
