и d = и + uv, то получаем c/d = с{и - «\/2)/(u - 2г;) = х + у\/2, где х и у - рациональные числа. ПусТь теперь q = и" + v"\/2, где и" и г;" - это ближайшие к х и у целые числа, и положим г = с - qd. Если г = и" + v"\/2, то \и" - 2v"\ < - 2v\. Следовательно, выполнение алгоритма завершится через конечное число шагов. Более подробную информацию об этом можно найти в учебниках по теории чисел, в разделах, посвященных квадратичным евклидовым областям.]

13. Добавьте "Т < 3{n-d) + k" к утверждениям A3, А4, А5, А6, где к принимает значения 2, 3, 3, 1 Соответственно. Добавьте также "d > О" к утверждению А4-

15. (а) Положим А = S в (iii); отсюда следует, что любое непустое вполне упорядоченное множество имеет минимальный (или наименьший) элемент.

(b) Пусть X < у, если а: < \у\ или если а; = г/ и а: < О < у.

(c) Нет, так как подмножество всех действительных положительных чисел не удовлетворяет условию (iii). [Замечание. Пользуясь так называемой аксиомой выбора, можно дать довольно сложное доказательство того, что любое множество можно вполне упорядочить каким-то образом; но до сих пор никто не определил явным образом отношение, которое вполне упорядочивает множество действительных чисел.]

(d) Чтобы доказать для Т„ свойство (iii), воспользуемся индукцией по п. Пусть А - непустое подмножество Г„; рассмотрим Ai, которое представляет собой множество первых компонент элементов А. Так как Ai -это непустое подмножество 5, а 5 вполне упорядочено, то Al содержит наименьший элемент х. Теперь рассмотрим Ах, которое является подмножеством тех элементов из А, первая компонента которых равна х; А можно считать подмножеством T„-i, если у всех его элементов изъять первую компоненту. Поэтому по индукции Ах содержит наименьший элемент {х,Х2, ,х„), который на самом деле является наименьшим элементом А.

(e) Нет, хотя свойства (i) и (ii) выполняются. Если S содержит по меньшей мере два различных элемента, а -< 6, то множество (6), (а, 6), (а, а,Ь), (а,а,а,Ь), {а,а,а,а,Ь),... не имеет наименьшего элемента. С другой стороны, Т можно вполне упорядочить, если определить в Т„ отношение (xi,... ,Хт) < {у1,--,Уп) при т < п или {xi,...,x„) < (У1,--,Уп) прит = п.

(f) Пусть множество 5 вполне упорядочено отношением -<. Если такая бесконечная последовательность существует, то множество А, содержащее члены этой последовательности, не будет удовлетворять свойству (iii), так как ни один элемент этой последовательности не может быть наименьшим. Обратно, пусть -< - отношение, удовлетворяющее условиям (i) и (ii), но не (iii), и пусть А - непустое подмножество S, не имеющее наименьшего элемента. Так как А - непустое, мы можем найти a;i из А; так как a;i не является наименьшим элементом А, то существует Х2 из А, для которого Х2 < xi; так как хг тоже не является наименьшим элементом, мы можем найти хз < Х2 и т. д.

(g) Пусть А - множество всех х, для которых утверждение Р{х) ложно. Если А не пусто, то оно содержит наименьший элемент Xq. Следовательно, Р{у) верно для всех у < Хо. Но отсюда вытекает, что Р{хо) верно, следовательно, Хо не принадлежит А (получаем противоречие). Таким образом, А должно быть пустым, т. е утверждение Р{х) всегда верно.

РАЗДЕЛ 1.2.2

1. Такого числа нет; для любого положительного рационального числа г можно указать меньшее число, например г/2.

2. Нет, если подряд идет бесконечно много девяток; в этом случае согласно соотношению (2) десятичным представлением данного действительного числа будет 1 --.24000000----

3. -\/27, но в тексте раздела операция возведения в степень отрицательных чисел не определена.

4. 4.

6. Для любого действительного числа существует единственное десятичное представление, поэтому х = у тогда и только тогда, когда т = п а di - для всех i > 1. Если х фу, то нужно сравнивать m с п, di с ei, с ег и т. д.; когда обнаружится первое неравенство, большая цифра будет принадлежать большему из чисел {х, у).

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

8. Испытывая последовательно п = 0,1, 2,..., находим значение п, для которого п"* < и < (п + 1)*". Предполагая по индукции, что n,di,... ,dk-i уже определены, находим цифру dk из условия

9. ((ЬР/ч)"/")" = (((b"/)"/")") = ((Ь"/)") = ((Ь"/)")" = следовательно, (5Р/ч)"/" - 5Р"/ч< Таким образом, второе правило доказано. Теперь на основе второго

правила докажем первое: ftP/b"/" = (b/Wyv Jl/qvqu (fl/qvyv+qu +

10. Если logjo 2 = р/д, где р и g положительны, то 2 = Ю*", а это невозможно, так как правая часть уравнения делится на 5, а левая нет.

11. Бесконечно много! Независимо от того, сколько дано цифр десятичного представления числа а:, мы все равно не знаем, будет ли 10" = 1.99999... или 2.00000 ..., если цифры а: соответствуют цифрам logo 2. И в этом нет ничего таинственного или парадоксального; аналогичная ситуация возникает при сложении, например, .444444 ... с .55555 ....

12. Существует единственный набор значений di,...,ds, удовлетворяющий соотношению (7).

13. (а) Сначала докажите по индукции, что если у > О, то 1+пу < (1-(-г/)". Затем положите у = х/п и извлеките из обеих частей неравенства корни п-й степени. (Ь) а: = 6- 1, п = 10*.

14. Во втором равенстве (5) положите а: = log с, а затем прологарифмируйте обе части.

15. Перенесите logj у в другую часть равенства и воспользуйтесь формулой (11).

16. 1па:/1п10.

17. 5; 1; 1; 0; не определен.

18. Нет, logg а: = Ig a:/lg 8 = Ig а:.

19. Да, так как Ig п < (logjo п)/.301 < 14/.301 < 47.

20. Да, это взаимно обратные значения.

21. (1п1па:-1п1пЬ)/1пЬ.

22. Из таблиц приложения А получаем, что Iga: й 1.4426951пх; logjoa: ~ .43429451п а:. Относительная погрешность составляет й (1,442695 - 1.4342945)/1.442695 и 0.582%.

23. Возьмите фигуру площадью 1пг/ и разделите ее высоту на х, в то же время умножив ее длину на а:. В результате этого преобразования площадь не изменится и будет равна площади фигуры, которая останется после удаления 1пх из Inxy, так как высота в точке X + xt на, графике \пху равна 1/(а: + xt) = (1/(1 + t))/x.

24. Везде вместо 10 подставьте 2.

25. Обратите внимание, что z = 2 [2 *а:],гдер - это точность (т. е. количество двоичных цифр после двоичной точки)*.Величина t/+logj а: приблизительно остается постоянной.

27. Докажите индукцией по к, что

и прологарифмируйте все части неравенства.

28. В приведенном ниже алгоритме используются те же вспомогательные таблицы, что и раньше (см. выше).

Е1. [Инициализация.] Если 1 - б - это наибольшее возможное значение х, присвойте у <- (ближайшее приближенное значение Ь), х <- 1 -е, /с <- 1. (При выполнении следующих шагов величина уЬ~ останется приблизительно постоянной.)

Е2. [Проверка окончания.] Если а: = О, то прекратите выполнение.

ЕЗ. [Сравнение.] Если а: < logj(2°/(2* - 1)), то увеличьте /с на 1 и повторите этот шаг.

Е4. [Замещение значений.] Присвойте х х - logj(2*/(2* - 1)), у У - [у сдвигается вправо на к) и перейдите к шагу Е2.

Если на шаге El положить у равным Ь"(1 + бо), то в результате возникает погрешность вычислений при выполнении операций а: <- a:+logj(l-2""*)+Jj и г/ -f- г/(1-2~*)(1+еу) во время j-ro выполнения шага Е4, причем 6j и tj -некоторые малые погрешности. Когда выполнение алгоритма прекратится, будет вычислено значение у = Ь~П>(1 + Дальнейший анализ проводится в зависимости от величины Ь и размера компьютерного слова. Обратите внимание, что и в данном случае, и в упр. 26 можно несколько уточнить оценки ошибок, если рассматривать логарифмы по основанию е. Дело в том, что для большинства значений к табличное значение 1п(2*/(2* - 1)) можно получить с большей точностью: оно равняется 2~* + 12"* + 2"* -)----

Замечание. Аналогичные алгоритмы можно получить и для тригонометрических функций; см. J. Е. Meggitt, IBM J. Res. шд Dev. 6 (1962), 210-226; 7 (1963), 237-245. См. также Т. С. Chen, IBM J. Res. and Dev. 16 (1972), 380-388; V. S. Linsky, Vychisl. Mat. 2 (1957), 90-119 (B. C. Линский, Вычисл. мат. 2 (1957), 90-119); D. E. Knuth, METRFONT: The Program (Reading, Mass.: Addison-Wesley, 1986), §120-147.

29. e; 3; 4.

РАЗДЕЛ 1.2.3

1. ai +a2 + аз.

3. Нарушено условие, налагаемое на p{j); с одной стороны, значение = 3 не принимается ни для одного п, а с другой стороны, значение = 4 принимается для двух п. [См. соотношение (18).]

4. (ац) + (о21 + 022) + (аз1 + 032 + азз) = (an + 021 + 031) + (022 + 032) + (азз).

5. Для доказательства достаточно воспользоваться правилом aXi = 1д(;)(оа:{):

R(i) S(j) / Vs(j) / R(i) \S(J) /

7. Возьмем одну из сумм (например, первую) и запишем по формуле (3). Затем поменяем пределы местами, перенесем из одного в другой члены ао, ..., и по формуле получим вторую сумму.

* Точка, разделяющая целую и дробную части двоичного представления числа, - Прим. перев.