Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Q: How many numerical analysts does it take to replace a lightbulb?? A: 3.9967: (after six iterations). 92 В посконных курсах методов вычислений абсолютной погрешностью называлась |x − y|, а ε — предельной абсолютной погрешностью. Однако, если x и y являются точными числами, то никакой необходимости вводить еще одно название для абсолютной величины их разности нет. Если же они не являются точными числами, то выражение |x − y| само по себе просто не имеет никакого смысла, смысл можно придать только неравенству |x − y| ≤ ε. 292 ется в виде x = m · 10 −n , где m и n ≥ 0 целые числа, причем если допол- нительно требовать, чтобы m не делилось на 10, то такое представление единственно. Множество 1 10 n Z = n m 10 n | m ∈ Z o называется множеством приближенных чисел абсолютной точности (Ac- curacy) n. Традиционно числа абсолютной точности n записываются с n знаками после запятой — которая в Computer Science называется десятич- ной точкой — даже если эти знаки нули, однако Mathematica использует совершенно другое соглашение. Однако, в большинстве вычислений важна не абсолютная, а относи- тельная точность (Precision) числа x, равная абсолютной точности не самого числа x, а его мантиссы, т.е. числа x/10 l , где l подобрано так, чтобы 1/10 ≤ x/10 l < 1. Как правило для вещественного числа x существует единственное при- ближенное число y абсолютной точности n такое, что абсолютная погреш- ность приближения x при помощи y равна 10 −n /2. Отображение x 7→ y называется округлением вещественного числа до n разрядов после за- пятой. Единственными исключениями являются приближенные числа x абсолютной точности n + 1, заканчивающиеся на 5. Например, число 0.5 одинаково хорошо приближается как 0, так и 1. В этом случае, чтобы избежать накопления систематической ошибки, используется следующее правило: в качестве округления числа x берется то из чисел точности n, последняя цифра которого четна. Произведение/частное двух чисел фиксированной абсолютной точности не обязательно имеют ту же абсолютную точность. Для чисел фиксирован- ной относительной точности то же самое верно уже для суммы/разности. Поэтому вместо обычных арифметических операций для приближенных чисел используются приближенные арифметические операции, с ма- тематической (но не с вычислительной!!!) точки зрения состоящие в следу- ющем: ◦ выполняется обычная арифметическая операция, ◦ получившийся результат округляется до нужной точности. Обозначим так определенные приближенное сложение и приближен- ное умножение через ⊕ и , соответственно. Строго говоря, следовало бы указывать еще и используемую при округлении абсолютную или отно- сительную точность, но уже введение специальных символов ⊕ и для приближенных операций является огромным прогрессом по сравнению с традиционными текстами по методам вычислений, где приближенные опе- рации обозначались теми же знаками + и ·, что и обычные операции, так что после нескольких страниц становилось вообще непонятно, о чем идет речь. 293 Математически трудности приближенных вычислений объясняются тем, что операции приближенного сложения и умножения не облада- ют никакими из обычных свойств сложения и умножения. В кни- ге Кнута подробнейшим обсуждаются связанные с этим неожиданности, например, почему при (приближенном) сложении чисел столбиком сверху вниз и снизу вверх всегда получаются разные результаты! Отметим еще несколько необычных явлений. • Для чисел относительной точности 2 выполяется точное равенство 10⊕ 0.1 = 10. Таким образом, приближенное сложение не обладает свойством сокращения. • Для чисел абсолютной точности 1 выполняются следующие соотноше- ния: 0.1 · 0.1 = 0.2 · 0.2 = 0, 0.3 · 0.3 = 0.1, 0.4 · 0.4 = 0.5 · 0.5 = 0.2 В частности, произведение двух ненулевых чисел может равняться нулю. Более того, относительно операции приближенного умножения все числа −1 < x < 1 фиксированной абсолютной точности нильпотентны, т.е. дают в некоторой степени 0. • Ассоциативность сложения нарушается — что еще хуже, она может нарушаться сколь угодно сильно! Подгрузка пакета ComputerArithmetic позволяет эмулировать арифме- тику чисел с плавающей запятой с точностью до 8 значащих цифр, обыч- ную для большинства микрокалькуляторов: < 2.1. Приведите примеры нарушения обычных свойств арифметических операций: • нарушения ассоциативности приближенного умножения для чисел аб- солютной точности 8; • нарушения ассоциативности приближенного сложения для чисел отно- сительной точности 8; • нарушения дистрибутивности приближенного умножения относитель- но приближенного сложения для чисел точности 8. В связи с этим еще раз подчеркнем, что использование приближенных вычислений без контроля погрешностей и, в особенности, использование приближенных вычислений в итеративных процедурах, является грубейшей методологической ошибкой. В подавляющем большин- стве случаев использование приближенных вычислений представляет со- бой атавизм, пагубную привычку, злостный пережиток, закрепившиеся в то время, когда все вычисления производились вручную. При сегодняшнем 294 уровне вычислительных возможностей почти все практически возни- кающие вычислительные задачи, в которых фигурируют веще- ственные числа, могут быть решены точно. За исключением задач, связанных с генерацией графика и звука, правильная стратегия состоит в том, чтобы проводить точные вычисления, не округляя никаких промежу- точных результатов — и, тем более, не делая этого многократно!!! Округ- лять — в случае необходимости — можно только окончательный результат. 3. Приближенные вещественные числа: практика. 93 Посмотрим теперь, как описанные в предыдущем параграфе понятия выражаются в системе Mathematica. Accuracy[x] абсолютная точность x Precision[x] относительная точность x В первом приближении можно считать, что абсолютная точность Accu- racy возвращает количество десятичных цифр справа от запятой, в то время как относительная точность Precision — общее количество явно заданных десятичных цифр. В действительности, конечно, дело обстоит гораздо сложнее, так как внутреннее представление чисел в системе двоич- ное, так что для двух чисел одинаковой (десятичной) разрядности команды Accuracy и Precision могут возвращать различные результаты, притом не обязательно даже целые! Абсолютная точность может быть как больше, так и меньше относитель- ной, в зависимости от того, больше или меньше чем 1 абсолютная величина рассматриваемого числа. Перечислим основные соглашения, связанные с точностью приближенных чисел. • Любое рациональное число, а также точные иррациональные числа, такие как e, π, ln(2), cos(1) рассматриваются как имеющие бесконечную точность, infinite precision. • Любое число, имеющее явную десятичную точку, и любое численное выражение, содержащее хотя бы одно приближенное вещественное число, рассматривается как приближенное вещественное число и имеет тип Real. • Приближенное вещественное число может быть либо числом машин- ной точности = machine precision number, либо числом произволь- ной точности = arbitrary precision number, variable precision num- ber. Машинное число имеет 6 отображаемых в ответе десятичных разря- дов и еще около 10 разрядов дополнительной точности, используемых в промежуточных вычислениях. Таким образом, количество значащих раз- рядов машинного числа, MachinePrecision, приблизительно равно 16, в то же время разрядность числа произвольной точности может быть любой и ограничена только конечностью физического мира (о чем подробнее в следующем параграфе). 93 Finagle's Third Law: In any collection of data, the figure most obviously correct, beyond all need of checking, is the mistake. 295 Следующие тесты позволяют узнать, рассматривает ли система x как число, как явно заданное число (рациональное или приближенное веще- ственное), и, наконец, как машинное число. NumericQ[x] x является числом NumberQ[x] x является явно заданным числом MachineNumberQ[x] x является машинным числом • В силу особенностей архитектуры процессора и шины, а также ор- ганизации памяти, вычисления с машинными числами часто значительно эффективнее, чем с числами произвольной точности. С другой стороны, получающаяся при этом точность достаточна для большинства обычных приложений, в частности, для генерации графики. Поэтому по умолча- нию используемая системой рабочая точность равна машинной точности, WorkingPrecision->MachinePrecision. • Приближенное число с общим количеством знаков, меньшим машин- ной точности MachinePrecision, по умолчанию рассматривается как чис- ло машинной точности. Иными словами, 0.1 значит то же самое, что 0.10, 0.100, 0.1000 и т.д., вплоть до машинной точности, что находится в крича- щем противоречии с практикой классической вычислительной математики! Например, вычисление {Accuracy[10^6.+10^-6],Precision[10^6.+10^-6]} даст ответ {9.95459, MachinePrecision} • Численные команды — такие как N, NSolve, NRoots, NSum, NProduct, NIntegrate, NDSolve и т.д. — имеют параметры или опции, явно деклари- рующие точность результата и/или промежуточных значений. Кроме того, точность всех чисел, входящих в некоторое выражение, может быть явно задекларирована посредством команды SetPrecision, установкой значения опции WorkingPrecision и т.д. Перечислим простейшие способы декларирования точности. AccuracyGoal ожидаемая абсолютная точность результата PrecisionGoal ожидаемая относительная точность результата SetAccuracy декларирование абсолютной точности SetPrecision декларирование относительной точности WorkingPrecision количество цифр, сохраняемых во всех промежуточных результатах $MaxExtraPrecision количество дополнительные разрядов, используемых в промежуточных вычислениях, по умолчанию 50 • Точность приближенного числа с количеством знаков, большим ма- шинной точности, равна его декларированной точности, либо, по умолча- нию, количеству явно указанных знаков. При обычных конфигурациях 296 ядра точность приближенного числа произвольной точности ограничена только объемом оперативной памяти используемого компьютера. Основная команда округления в системе Mathematica это N. N[x] приближенное значение x с машинной точностью N[x,m] приближенное значение x с точностью m цифр По умолчанию N возвращает машинные числа, иными словами, она отоб- ражает на экране первые 6 десятичных знаков числа, но при этом все внут- ренние вычисления производятся примерно с 16 знаками. Скажем, вычис- ление {N[Sqrt[2]],N[E],N[Pi]} дает {1.41421,2.71828,3.14159} В то же время вычисление N[Pi,100] дает первые сто знаков π. 3.1. Сколько времени занимает вычисление первого миллиона знаков π, e, √ 2? Сколько времени занимает вычисление первых ста тысяч знаков ln(2), cos(1), e π , π 2 , √ 2 √ 3 ? Ответ. Как говорится в Implementation Notes, π вычисляется по фор- муле Чудновских, но все равно гораздо медленнее, чем e — ряд Тэйло- ра для экспоненты хорошо сходится! Но e, в свою очередь, вычисляется медленнее, чем √ 2, вычисление которого использует быстро сходящиеся итерационные алгоритмы. Вычисление значений экспонент, логарифмов и тригонометрических функций основано непосредственно на рядах Тэйлора + функциональные соотношения + итерационные процедуры. Для таких значений аргументов скорость вычисления определяется главным образом скоростью сходимости соответствующего ряда. Следующий курьезный пример, который мы уже упоминали в нашем курсе, показывает, что в приближенных вычислениях ни одна из цифр ничего не значит! В данном случае, конечно, причина этого явления хо- рошо известна специалистам и связана с тем, что фигурирующие здесь числа 43, 67 и 163 возникают как часть составленного Гауссом списка од- ноклассных мнимых квадратичных полей Q( √ d), d = −1, −2, −3, −7, −11, −19, −43, −67, −163. Просто для маленьких дискриминантов интересующий нас эффект не так заметен. 3.2. Вычислите e π √ 43 с точностью до 12 и 13 знаков, e π √ 67 с точностью до 17, 18 и 19 знаков, и e π √ 163 с точностью до 29, 30 и 31 знака. Ответ. Ограничимся наиболее эффектной частью ответа. Вычисление NumberForm[N[Exp[Pi*Sqrt[163]],29],ExponentFunction->(Null&)] 297 дает 262537412640768744.00000000000 Напомним, что опция ExponentFunction->(Null&) введена здесь только для того, чтобы система не пыталась выразить это число в научной форме, с разделением мантиссы и порядка. То же вычисление с точностью до 30 знаков дает 262537412640768743.999999999999 где все еще неясно, является ли это число целым на самом деле, или всего лишь с точностью до 12 знаков после запятой. Вычисление следующего разряда снимает все сомнения: 262537412640768743.9999999999993 Как показывает следующая задача, все ссылки на использование веще- ственных чисел в естествознании и на их роль в измерении величин, о ко- торой говорит Лебег, являются чистой фикцией. 3.3. Каждый кристаллограф знает 94 , что π/6 = 0, 52, √ 3π/8 = 0, 68 и √ 2π/6 = 0, 74. Найдите π, √ 3 и √ 2. Ответ. Из первого равенства находим π = 3.12, что хорошо согласуется с теоретическим значением. Подставляя это значение во второе равенство, получаем, что в кристаллографии √ 3 = 1.74359, а √ 2 = 1.42308. Следующие две задачи взяты из замечательной книги Гуго Штейнгау- за 95 3.4. Выяснить, верно ли, что x = v u u t 5 + s 3 + r 5 + q 3 + . . . < 3? 3.5. Выяснить, при любом ли n выполняется неравенство x = v u u t 1 + s 2 + r 3 + . . . + q n < 2? 94 Смотри, например, А.Анималу, Квантовая теория кристаллических твердых тел. — М., Мир, 1981, 574с., где все эти формулы именно в таком виде приведены на стра- ницах 15–16 как плотности простой кубической, объемноцентрированной кубической и гранецентрированной кубической упаковок одинаковых шаров! 95 Г.Штейнгауз, Задачи и размышления. — М., Мир, 1974, 400с. 298 4. Машинные числа. 96 В нашем учебнике мы почти не упоминаем системные команды. Тем не менее, при некоторых практических вычислениях полезно понимать огра- ничения, накладываемые используемой операционной системой, а также архитектурой процессора, памятью компьютера и другими подобными внешними по отношению к вычислению обстоятельствами. Перечислим системные команды, которые позволяют узнать параметры приближенных вычислений. Приводимые ниже численные значения системных парамет- ров относятся к системе Windows и бытовым компьютерам 2005–2006 годов. MachinePrecision машинная точность, по умолчанию 53 log 10 (2) $MachinePrecision численное значение машинной точности, 15.9546 $MachineEpsilon машинный эпсилон 2 −52 $MaxMachineNumber наибольшее машинное число 2 1024 $MinMachineNumber наименьшее положительное машинное число 2 −1022 Машинный эпсилон это наименьшее положительное машинное чис- ло ε такое, что 1 + ε 6= 1.000000000000000, где равенство понимается как равенство машинных чисел. Поскольку вычисления в системе производят- ся в двоичной системе, то фактически $MachineEpsilon имеет следующее значение: $MachineEpsilon = 2 −52 ≈ 2.22045 · 10 −16 . Машинный эпсилон является абсолютной версией применяемого в теоре- тической Computer Science ульпа = unit in the last place. А именно, машинный эпсилон ε — это в точности ульп между 1 и 2. Ульп между 2 и 4 равен 2ε, etc. Теоретически приближенные вычисления могут быть органи- зованы так, чтобы ошибка одной операции не превышала половины ульпа, а ошибка при выполнении нескольких операций — одного ульпа. Однако, по причинам упомянутым в § 2, практически при вычислениях с числами разного масштаба уже выполнение двух операций может давать ошибку в миллионы ульпов. Более того, в обычной машинной арифметике контроль ошибки не производится! Наибольшее машинное число $MaxMachineNumber равно 2 1024 = 17976931348623159077293051907890247336179769789423 06572734300811577326758055009631327084773224075360 21120113879871393357658789768814416622492847430639 47412437776789342486548527630221960124609411945308 29520850057688381506823424628814739131105408272371 63350510684586298239947245938479716304835356329624 224137216 ≈ 1.79769 · 10 308 . 96 Sometimes it is useful to know how large your zero is. — The Tao of Real Programming 299 С другой стороны, наименьшее положительное машинное $MinMachineNum- ber число равно 2 −1022 ≈ 2.22507 · 10 −308 . Таким образом, операции над машинными числами такие, как сложение и умножение, не только не удовлетворяют обычным свойствам наподобие ассоциативности и коммутативности, но и вообще не являются всюду опре- деленными алгебраическими операциями! Фактически, однако, в силу физических ограничений, накладываемых размером оперативной памяти используемого компьютера, среди чисел произвольной точности тоже есть наибольшее и наименьшее число. Узнать, чему именно они равны для Вашей системы, можно при помощи системных команд $MaxNumber и $MinNumber. $MaxNumber наибольшее число произвольное точности $MinNumber наименьшее положительное число произвольное точности Вот типичные значения наибольшего и наименьшего чисел произвольной точности: $MaxNumber = 1.605216761933662 · 10 1355718576299609 $MinNumber = 6.229688249675322 · 10 −1355718576299610 Это значит, что выполнение алгебраических операций над числами произ- вольной точности тоже может привести к переполнению. Например, 2 10 9 можно вычислить точно, в то же время попытка вычислить 2 2 ·10 9 приводит к переполнению. 5. Десятичные цифры. 97 Основными функциями для работы с приближенными вещественными числами являются RealDigits и обратная к ней функция FromDigits. В предыдущей главе мы уже обсуждали, как эти функции работают для ра- циональных чисел. RealDigits[x] список цифр вещественного числа x FromDigits[ {list,m}] восстановление числа по списку цифр Для приближенных вещественных чисел (=десятичных дробей) эти ко- манды в целом действуют без всяких неожиданностей. Однако, непосред- ственная попытка вычислить RealDigits от точного иррационального чис- ла – как алгебраического RealDigits[Sqrt[2]], так и трансцендетного RealDigits[Pi] – приведет к сообщению об ошибке: RealDigits: The number of digits to return cannot be determined. 97 Так, поле “Номер паспорта”, 6 цифр. |