Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
4.7. Всегда ли алгоритм Фибоначчи и алгоритм Остроградского дают один и тот же результат? 4.8. Найдите сумму s египетских дробей x = 1 n 1 + 1 n 2 + . . . + 1 n s < 1 такую, что между x и 1 нет никаких других сумм s египетских дробей. Ответ. Это сумма первых s членов ряда 1 2 + 1 3 + 1 7 + 1 43 + 1 1807 + . . . , в котором знаменатель каждого члена равен произведению знаменателей всех предыдущих членов +1. 4.9. Ясно, что 1 n = 1 2n + 1 2n , Утверждается, что при n ≥ 2 египетская дробь 1/n представляется как сумма двух различных египетских дробей: 1 n = 1 x + 1 y , x < y. Например, 1 2 = 1 3 + 1 6 , 1 3 = 1 4 + 1 12 , 1 4 = 1 5 + 1 20 = 1 6 + 1 12 , 1 5 = 1 6 + 1 30 , и так далее. Ясно, что почти все эти разложения являются частными слу- чаями тождества 1 n = 1 n + 1 + 1 n(n + 1) , но вот второе разложение для 1/4 так не получается. Найдите все такие разложения. Следующая задача, предложенная Эрдешем и Штраусом, обсуждается в классической книге Морделла 84 84 L.J.Mordell, Diophantine equations. — Acad. Press, London et al., 1969. 285 4.10. Верно ли, что для любого n > 1 уравнение 4 n = 1 x + 1 y + 1 z , имеет решение в натуральных числах? Ответ. Это верно, по крайней мере для всех n ≤ 10 7 Кроме того, в цитированной книге Морделла доказано, что это вообще всегда так, за ис- ключением, возможно, случая, когда n простое число сравнимое с 1, 121, 169, 289, 361 или 529 по модулю 840. 4.11. Проверьте справедливость утверждения предыдущей задачи для пер- вых нескольких тысяч простых, удовлетворяющих этим сравнениям. Указание. Cоставляя список при помощи команды Select следует ли вы- бирать числа, удовлетворяющие сравнениям, из списка простых или про- стые из списка чисел, удовлетворяющих сравнениям? 4.12. Верно ли, что для любого n > 1 уравнение 5 n = 1 x + 1 y + 1 z , имеет решение в натуральных числах? 4.13. Верно ли, что для любого m существует такое n(m), что для любого n > n(m) уравнение m n = 1 x + 1 y + 1 z , имеет решение в натуральных числах? 4.14. Можно ли в предыдущей задаче утверждать, что всегда n(m) ≤ m? 5. Числа Бернулли. Числа Бернулли B n естественно возникают во многих теоретико-число- вых, алгебраических и комбинаторных результатах, а также в классическом анализе. Вот одно из их простейших определений: t e t − 1 = ∞ X n=0 B n t n n! Числа B n были независимо введены Яковом Бернулли и Такакадзу Секи Кова для вычисления сумм 1 m + 2 m + . . . + n m . Сегодня большинство начи- нающих впервые видят числа Бернулли при вычислении коэффициентов рядов Тэйлора тригонометрических и гиперболических функций. Кроме того, многие алгоритмы используют численные значения B n . Поэтому в системе встроена функция BernoulliB, возвращающая числа Бернулли. BernoulliB[n] число Бернулли B n 286 5.1. Составьте таблицу первых 31 чисел Бернулли. Что Вам сразу броса- ется в глаза? Решение. Простое вычисление Table[BernoulliB[n], {n,0,10}] дает B 0 = 1, B 1 = − 1 2 , B 2 = 1 6 , B 3 = 0, B 4 = − 1 30 , B 5 = 0 B 6 = 1 42 , B 7 = 0, B 8 = − 1 30 , B 9 = 0, B 10 = 5 66 Все дальнейшие числа Бернулли B 2n+1 с нечетными номерами тоже равны 0, поэтому ограничимся значениями чисел B 2n с четными номерами. B 12 = − 691 2730 , B 14 = 7 6 , B 16 = − 3617 510 , B 18 = 43867 798 , B 20 = − 174611 330 , B 22 = 854513 138 , B 24 = − 236364091 2730 , B 26 = 8553103 6 , B 28 = − 23749461029 870 , B 30 = 8615841276005 14322 Трудно не заметить, что знаки чисел Бернулли B 2n чередуются в зави- симости от четности n: числа Бернулли B 4n отрицательны, а B 4n+2 — положительны. Знаменитая теорема фон Штаудта утверждает, что дробная часть чисел ( −1) n B 2n чрезвычайно естественно выражается в терминах суммы египетских дробей, зависящих только от n. В частности, числа Бернулли рациональны. 5.2. Убедитесь, что число B 2n является разностью некоторого целого числа и суммы всех египетских дробей вида 1/p, где p пробегает те простые числа, которые на 1 больше какого-то делителя числа 2n. 287 Ответ. Ограничимся несколькими небольшими примерами 85 : B 2 = 1 6 = 1 − 1 2 − 1 3 B 4 = − 1 30 = 1 − 1 2 − 1 3 − 1 5 B 6 = 1 42 = 1 − 1 2 − 1 3 − 1 7 B 8 = − 1 30 = 1 − 1 2 − 1 3 − 1 5 B 10 = 5 66 = 1 − 1 2 − 1 3 − 1 11 B 12 = − 691 2730 = 1 − 1 2 − 1 3 − 1 5 − 1 7 − 1 13 B 14 = 7 6 = 2 − 1 2 − 1 3 B 16 = − 3617 510 = −6 − 1 2 − 1 3 − 1 5 − 1 17 B 18 = 43867 798 = 56 − 1 2 − 1 3 − 1 7 − 1 19 B 20 = − 174611 330 = −528 − 1 2 − 1 3 − 1 5 − 1 11 B 22 = 854513 138 = 6193 − 1 2 − 1 3 − 1 23 B 24 = − 236364091 2730 = −86579 − 1 2 − 1 3 − 1 5 − 1 7 − 1 11 B 26 = 8553103 6 = 1425518 − 1 2 − 1 3 B 28 = − 23749461029 870 = −27298230 − 1 2 − 1 3 − 1 5 − 1 19 B 30 = 8615841276005 14322 = 601580875 − 1 2 − 1 3 − 1 7 − 1 11 − 1 31 O dear Ophelia, I am ill at these numbers. William Shakespeare, Hamlet 85 Смотри по этому поводу Г.Полиа, Г.Сеге, Задачи и теоремы из анализа, том II. — М., Наука, 1978, с.161. 288 § 3. Вещественные числа Допущение, что над вещественными числами можно производить все операции согласно обычным формальным законам арифмети- ческих действий, считалось само собой разумеющимся вплоть до второй половины XIX века. Поэтому мы будем рассматривать тот факт, что обычные правила вычислений приложимы к веществен- ным числам, как аксиому. Рихард Курант 86 В школе математическими понятиями пользуются, не сомневаясь в их законности и очень часто не задаваясь даже вопросом, что же они, собственно, означают. Не зная, что такое вещественные числа, мы, тем не менее умеем с ними обращаться, т.е. складывать их, умножать и сравнивать по величине. Виктор Петрович Хавин 87 Что уж говорить о мучениях посредством ε/2 и √ δ, которым пре- подаватели математического анализа подвергают студентов перво- го курса из чистого садизма, без всякой необходимости, могущей сыграть роль смягчающего обстоятельства. Анри Лебег 88 Из несчетности множества самих вещественных чисел следует да- же, что не существует языка, в котором каждое веществен- ное число имело бы имя . Такая вещь, как, например, бесконеч- ное десятичное разложение, не может, конечно, рассматриваться как имя соответствующего вещественного числа, поскольку бес- конечное десятичное разложение не может даже быть полностью выписано или включено как часть в какое-нибудь фактически вы- писанное или произнесенное суждение. Алонзо Черч 89 Когда во время партсобрания за окном трижды каркает ворона и члены бюро незаметно сплевывают через левое плечо или крестят под столом животы, это не проявление суеверия, временно омрача- ющего высшую форму человеческой деятельности, а искаженное переплетение древних психических феноменов, из которых самым поздним является крестное знамение. Виктор Пелевин, Зомбификация В настоящем параграфе мы обсуждаем основы вычислений с веществен- ными числами. Среди прочих тем мы рассматриваем алгебраические и трансцендентные числа, десятичное представление вещественного числа, 86 Р.Курант, Курс дифференциального и интегрального исчисления. — М., Наука, 1967, 704с. 87 В.П.Хавин, Дифференциальное и интегральное исчисление функций одной веще- ственной переменной. — Лань, СПб, 1998, 446с. 88 А.Лебег, Об измерении величин, Изд.2. — Учпедгиз, М., 1960, с.1–204; стр.41. 89 А.Черч, Введение в математическую логику. т.I. – ИИЛ, М.,1960, с.1–484, стр.354. 289 непрерывные дроби, основные константы и элементарные функции. Основ- ной пафос систем компьютерной алгебры состоит именно в том, что при по- мощи них можно производить вычисления бесконечной точности. Однако, в некоторых приложениях, а также при дискретизации вывода (графики или звука), приходится пользоваться приближенными вычислениями, так что мы затрагиваем основные связанные с ними понятия. 1. Точные вещественные числа. 90 В настоящей главе мы не будем пытаться объяснять, что такое веще- ственное число. Тем более, что как математики мы знаем, что никакого другого определения вещественного числа, кроме как элемента поля R ве- щественных чисел, не существует. Определить R совсем просто, это (един- ственное с точностью до изоморфизма) полное архимедово линейно упоря- доченное поле — построить R несколько сложнее. Любое индивидуальное трансцендентное число является манифестацией актуальной бесконечно- сти и — в строгом техническом смысле — столь же бесконечно, как мно- жество всех рациональных чисел. Никакая математически последователь- ная трактовка вещественных чисел без признания этого основополагающего факта невозможна. Излагаемая в школе “конструкция” R при помощи бесконечных деся- тичных дробей является, в действительности, чистой профанацией, так как она не позволяет осмысленным образом определить алгебраические операции над вещественными числами. Попробуйте, например, при по- мощи десятичных дробей доказать, что 2/7 + 5/7 = 1 — не говоря уже про гораздо более сложное равенство √ 2 √ 3 = √ 6. Тот факт, что невозмож- но вычислить десятичное разложение суммы двух чисел по десятичным разложениям слагаемых, был замечен еще Дедекиндом, который считал доказательство равенства √ 2 √ 3 = √ 6 как вещественных чисел одним из своих главных математических достижений. Любая попытка определить сумму двух вещественных чисел x и y по их десятичным разложениям сводится к тому, что эти разложения обрезаются до какого-то порядка, берутся суммы получившихся рациональных прибли- жений, и, наконец, x + y определяется как верхняя грань этих сумм. Ясно, что эта процедура не является алгоритмом и ничем не отличается от определения x + y по Дедекинду, как верхней грани множества {a + b | a, b ∈ Q, a ≤ x, b ≤ y}. Тьюринг обратил внимание на то, что при этом, вообще говоря, нель- зя найти ни одной десятичной цифры суммы/произведения, не зная всех цифр слагаемых/сомножителей. Иными словами, невозможность исполь- зовать бесконечные десятичные дроби для реальных вычислений состоит 90 Вредно распространение между людьми мыслей о том, что наша жизнь есть про- изведение вещественных сил и находится в зависимости от этих сил. Но когда такие ложные мысли называются науками и выдаются за святую мудрость человечества, то вред, производимый таким учением, ужасен. c Лев Толстой, Путь жизни 290 не в том, что нахождение всех цифр результата требует бесконечного ко- личества операций, а в том, что уже нахождение первой цифры результата может потребовать бесконечного количества операций! В ниже в пункте 3 мы приводим пример, показывающий, что увеличение точности прибли- женного вычисления на один разряд может изменить любое количество предшествующих цифр. На самом деле бесконечными десятичными дробями можно описать R лишь как упорядоченное множество, но не как поле. Внушаемая школь- ным курсом уверенность, что вещественное число является бес- конечной десятичной дробью, представляет собой опасную ил- люзию. Любая попытка осмысленным образом ввести операции над бес- конечными десятичными дробями приводит к какой-то актуально беско- нечной конструкции (Вейерштрасса, Кантора, Дедекинда), в которой ир- рациональные числа истолковываются как бесконечные множества рацио- нальных чисел, классы таких множеств, или что-то в таком духе. Можно, конечно, пользоваться записью π = 3, 1415 . . . , если понимать, что многоточие здесь не означает ничего сверх того, что 3, 1415 < π < 3, 1416. Запись π ≈ 3, 1416 не означает даже этого. Тем не менее, здесь мы встанем на наивную точку зрения существования каких-то вещественных чисел имеющих какие-то приближения, какие-то десятичные цифры — и даже будем производить над этими десятичными цифрами какие-то арифметические операции. Разумеется, фактически это значит, что в таких случаях мы будем производить вычисления в кольце десятичных дробей Z < Z h 1 10 i = Z h 1 2 , 1 5 i < Q — иными словами, вычисления с рациональными числами — но вычис- ления неограниченной точности. Конечно, вместо десятичных дробей, мы могли бы с тем же успехом пользоваться двоичными дробями Z h 1 2 i , как большинство программистов, троичными дробями Z h 1 3 i , как некото- рые математики, или шестидесятиричными дробями Z h 1 60 i = Z h 1 2 , 1 3 , 1 5 i (градусы, минуты, секунды, терции, . . . ), как астрономы. Однако, принципиальным отличием систем компьютерной алгебры от всех традиционных математических пакетов является не использование вычислений неограниченной точности, а возможность проводить в них без- ошибочные вычисления, известные также под народным названием вы- числений бесконечной точности. Так принято называть вычисления, в которых наряду с целыми и рациональными числами используются точ- ные вещественные или комплексные числа, и при этом не произ- водится никаких округлений и приближений. При этом алгебраиче- ские числа трактуются как корни многочленов с целыми коэффициентами, трансцендентные числа — как полиномиальные переменные, а при вычис- 291 лении значений трансцендентных функций используются только точные функциональные соотношения. Точное вещественное число характеризуется тем, что для него — точно так же, как для целого или рационального числа — как абсолют- ная точность Accuracy, так и относительная точность Precision обе бесконечны. Так, вычисление {Accuracy[Pi],Precision[Pi]} даст ответ {Infinity,Infinity}. Например, ввод Log[3]^Cos[1] будет интерпретирован как точное ве- щественное число log(3) cos(1) . Точно так же Pi, E и Sqrt[2] представляют точные вещественные числа π, e и √ 2. По умолчанию все вычисления с ними — арифметические, логические, вычисления значений функций, etc. — производятся только с бесконечной точностью. 1.1. Что больше, e π или π e ? Что больше, √ 2 √ 3 или √ 3 √ 2 ? Больше ли log(2) cos(1) и log(3) cos(1) , чем 1? Ответ. Конечно, можно посмотреть на какое-то количество десятичных цифр, как мы это делаем в следующем параграфе, но еще проще спросить прямо. Ну, скажем, Log[3]^Cos[1]>1. 2. Приближенные вещественные числа: теория. 91 В настоящем пункте мы обсудим основные понятия, связанные с при- ближенными значениями вещественных чисел. Стоит иметь в виду, что в системах компьютерных вычислений многие понятия и соглашения, свя- занные с приближенными вычислениями, радикально отличаются от тра- диционного численного анализа. Вещественное число y называется при- ближением вещественного числа x с абсолютной погрешностью 92 ε > 0, если |x − y| ≤ ε. Если y — приближение x с абсолютной погрешностью ε, то y − ε ≤ x ≤ y + ε, таким образом, неопределенность x равна 2ε. Таким образом, приближение тем лучше, чем меньше ε. Вещественные числа можно приближать любыми другими вещественны- ми числами, но чаще всего рассматривается приближение рациональными числами. В численном анализе, в отличие от классического анализа и тео- рии чисел, при этом как правило рассматривают не все Q, а лишь кольцо Z h 1 10 i десятичных дробей, которые в этом контексте называются прибли- женными вещественными числами. Каждая такая дробь представля- 91 |