Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Упражнение. Если Вы внимательно прочитали предыдущую фразу, ска- жите, что произойдет, если попытаться вычислить D[Pi,Pi]? Ответ. А ничего, система просто ответит, что по Pi дифференцировать нельзя: General: Pi is not a valid variable. § 12. Непрерывные дроби и рациональные приближения В настоящем параграфе мы рассматриваем еще один способ задания ве- щественных чисел и операции, превращающие приближенное вещественное число в точное рациональное число. Содержание этого параграфа носит чисто развлекательный характер и не используется в дальнейшем. Rationalize[x,d] хорошее рациональное приближение к x ContinuedFraction[x,n] разложение x в непрерывную дробь FromContinuedFraction[x] восстановление x по непрерывной дроби Функция Rationalize[x] строит хорошее рациональное приближение к приближенному вещественному числу x. Попытка вычислить Rational- ize[Pi] вернет π, потому что система не знает, приближение какой точно- сти нас интересует. Не приведет к успеху и попытка вычисления Ratio- nalize[N[Pi]]. Дело в том, что по используемому функцией Rationalize критерию у вычисленного с машинной точностью числа N[Pi] нет хороших рациональных приближений. А именно, рациональное число p/q рассмат- ривается в качестве хорошего приближения вещественного числа x, если |x − p/q| < c/q 2 , где по умолчанию c = 10 −4 Правильная форма состоит в том, чтобы спросить Rationalize[Pi,10^- n], явно задав допуск (tolerance). Вот построение рациональных прибли- жений числа π с точностью до 1, 2, . . . , 10 десятичных знаков после запятой: In[29]:=Map[Rationalize[Pi,10^(-#)]&,Range[10]] Out[29]= {22/7, 22/7, 201/64, 333/106, 355/113, 355/113, 75948/24175, 100798/32085, 103993/33102, 312689/99532 } А вот, что такое на самом деле используемое машинное приближение числа π. Вычисление Rationalize[N[Pi],0] с нулевым допуском дает 245850922/78256779. 174 Функция ContinuedFraction[x,n] выдает список первых n членов в раз- ложении x в непрерывную дробь. Функция ContinuedFraction[x], вызван- ная с одним аргументом порождает список всех членов, которые можно получить исходя из заданной точности x. Список {n1,...,ns} истолковы- вается обычным образом: [n 1 , . . . , n s ] = n 1 + 1 n 2 + 1 n 3 + 1 n4+... В случае квадратичных иррациональностей ответ имеет вид {m1,...,ms,{n1,...,nt}} где m 1 , . . . , m s — начальные члены непрерывной дроби, а n 1 , . . . , n t — период. Вычислим для примера выражения нескольких важнейших квадратич- ных иррациональностей: In[30]:=Map[ContinuedFraction, {GoldenRatio,GoldenRatio^-1,Sqrt[2],Sqrt[3]}] Out[30]= {{1,{1}},{0,{1}},{1,{2}},{1,{1,2}}} Функция FromContinuedFraction является обратной к функции Contin- uedFraction. Она действует обычным образом, восстанавливая исходное рациональное число — или при наличии периода, исходную квадратич- ную иррациональность!! — по его/ее разложению в непрерывную дробь. Например, вычисление FromContinuedFraction[ {1,{1,2,3}}] дает (−1 + √ 37)/3. Хорошее рациональное приближение к вещественному числу x можно построить также применив к числу x функцию ContinuedFraction[x,n] с большим значением n, а потом применив к результату функцию FromCon- tinuedFraction[x]. Вот, для примера, первые 24 знака разложения e в непрерывную дробь: In[31]:=ContinuedFraction[E,24] Out[31]= {2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,14,1,1,16} Если Вы не видели этого раньше (например, не читали Кнута!), это долж- но произвести впечатление и Вы, конечно, тут же попытаетесь вычислить ContinuedFraction[E,1000]. Результат будет поучителен во всех отноше- ниях — как с точки зрения рациональных приближений, так и с точки зрения работы системы. Итак, вот эта дробь в традиционной математиче- ской форме: 2 + 1 1 + 1 2+ 1 1+ 1 1+ 1 4+ 1 1+ 1 1+ 1 6+ 1 1+ 1 1+ 1 8+ 1 1+ 1 1+ 1 10+ 1 1+ 1 1+ 1 12+ 1 1+ 1 1+ 1 14+ 1 1+ 1 1+ 1 16+1 175 Несложное вычисление с использованием функции FromContinuedFraction показывает, что значение этой непрерывной дроби равно In[32]:=FromContinuedFraction[ {2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1, 12,1,1,14,1,1,16 }] Out[32]=14013652689/5155334720 Это рациональное число, для записи которого требуется 21 цифра, совпа- дает с e с точностью до 20 десятичных знаков. § 13. Комплексные числа В системе Mathematica комплексное число тоже может быть точным или приближенным. Обычно комплексное число представляется в алгебраиче- ской форме z = x + yi, причем оно считается точным в том и только том случае, когда как его вещественная часть x = re(z), так и его мнимая часть y = im(z) точные. I i мнимая единица z=x+I*y z = x + iy комплексное число z, где x, y ∈ R Re[z] re(z) вещественная часть z Im[x] im(z) мнимая часть z Abs[z] |z| модуль x Arg[z] arg(z) аргумент z Conjugate[z] z = x − iy сопряженное к z ComplexExpand[z] выделение re(z) и im(z) Использование большинства этих функций совершенно ясно из названия. Так, I обозначает мнимую единицу i, а Re[z] и Im[z] дают вещественную и мнимую часть комплексного числа z, соответственно. Функция Conju- gate[z] сопоставляет числу z = x + yi комплексно сопряженное z = x − yi. • Вопрос от точности или приближенности решается отдельно для ве- щественной и мнимой частей. Например, у комплексного числа 1.+1*I вещественная часть приближенная, но мнимая часть точная. Тем самым, вычисление Re[1.+1*I] даст приближенное вещественное число 1., но вы- числение мнимого числа Im[1.+1*I] дает точное целое число 1 — несмотря на то, что число 1.+1*I приближенное!! Функция N обычным образом дей- ствует на комплексных числах. Так, например, вычисление N[1+I] дает 1.+1.*I. • Если мнимая часть комплексного числа точно равна 0, то оно автома- тически упрощается до вещественного числа. Так, например, вычисление Head[1+0*I] дает Integer, а вычисление Head[1.+0*I] дает Real. В то же время, если мнимая часть комплексного числа приближенно равна 0, то оно все равно считается комплексным!!! Так, в частности, вычисление Head[1+0.*I] дает Complex. Это различие становится весьма существен- ным, когда мы начинаем реально использовать многозначные функции. • Следующий в высшей степени поучительный диалог иллюстрирует раз- ницу между Simplify и FullSimplify: 176 In[33]:=Simplify[Re[z]+I*Im[z]] Out[33]=I*Im[z]+Re[z] In[34]:=FullSimplify[Re[z]+I*Im[z]] Out[34]=z Кроме алгебраической формы комплексное число можно задавать и в полярной форме Abs[z]*Exp[I*Arg[z]], которую в русской учебной лите- ратуре принято называть тригонометрической. В этой форме используется две другие функции: • Модуль Abs[z] комплексного числа z = x + yi, равный p x 2 + y 2 • Аргумент Arg[z], т.е. такое число ϕ ∈ [−π, π], что tg(ϕ) = y/x. В тех случаях, когда это возможно, Arg возвращает точные значения. Так, например, Arg[-1/2+Sqrt[3]*I/2] дает 2π/3, Arg[-1/2-Sqrt[3]*I/2] дает −2π/3. Особенно интересна функция ComplexExpand, которая явным образом выделяет из комплексного числа вещественную и мнимую часть, считая, что все входящие в выражение этого числа переменные являются веще- ственными. In[35]:=ComplexExpand[Exp[x+y*I]] Out[35]=e^x Cos[y]+Ie^x Sin[y] In[36]:=ComplexExpand[Log[x+y*I]] Out[36]=I*Arg[x+I*y]+1/2*Log[x^2+y^2] In[37]:=ComplexExpand[Cos[x+y*I]] Out[37]=Cos[x]*Cosh[y]-I*Sin[x]*Sinh[y] In[38]:=ComplexExpand[Sin[x+y*I]] Out[38]=Cosh[y]*Sin[x]+I*Cos[x]*Sinh[y] § 14. Генерация случайных чисел Для многих целей, например для тестирования программ, полезно уметь генерировать (псевдо)-случайные числа, которые можно вводить в каче- стве данных в вычисления для проверки корректности и скорости рабо- ты используемых алгоритмов. В дальнейшем мы будем опускать префикс псевдо- и говорить просто о случайных числах. В системе Mathematica случайные числа генерируются при помощи следующих программ. Random[] случайное вещественное число на отрезке [0, 1] Random[Integer] 0 или 1 с вероятностью 1/2 Random[Integer, {m,n}] случайное целое число между m и n Random[Real,x] случайное вещественное число на отрезке [0, x] Random[Real, {x,y}] случайное вещественное число на отрезке [x, y] Random[Complex] случайное комплексное число в [0, 1] 2 Random[Complex, {z,w}] случайное комплексное число в прямоугольнике SeedRandom[] перезапустить генератор случайных чисел $RandomState текущее состояние генератора случайных чисел 177 Функцию Random можно вызвать вообще без аргументов, с одним или двумя аргументами, причем первый аргумент обязан быть типом числа (Integer, Real или Complex), а второй аргумент может быть числом или списком из двух чисел. • По умолчанию функция Random[], вызванная без аргументов, или, что то же самое, Random[Real], дает равномерно распределенное случайное вещественное число на отрезке [0, 1]. • Функция Random, вызванная в формате Random[Real,x] дает случай- ное число на отрезке [0, x], при этом x не обязано быть положительным! Наконец, функция Random, вызванная в формате Random[Real, {x,y}] дает случайное число на отрезке [x, y]. • То же самое относится к целым числам. Функция Random[Integer] случайным образом генерирует 0 или 1 с вероятностью 1/2. Функция Ran- dom[Integer,n] генерирует случайное целое между 0 и n включительно. Наконец, функция Random[Integer, {m,n}] порождает случайное целое на отрезке [m, n] ∩ Z — включая концы!! • Чуть труднее приноровиться к вызову функции Random в комплексной области. В этом случае функция Random[Complex, {z,w}] порождает слу- чайное комплексное число в прямоугольнике на комплексной плоскости с углами w и z. Этот прямоугольник имеет вид {x + yi | a ≤ x ≤ b, c ≤ y ≤ d}, где мы для краткости положили a = min(re(z), re(w)), b = max(re(z), re(w)), c = min(im(z), im(w)), d = max(im(z), im(w)). Конечно, этот прямоугольник может быть и вырожденным. Так, скажем, Random[Complex, {-1+I,-1+3*I}] даст случайное число на отрезке длины 2, параллельном мнимой оси. Разумеется, того же эффекта можно до- биться посредством -1+I*Random[Real, {1,3}]. То же, конечно, относится и к общему случаю. Из общих соображений совершенно ясно, что ника- ких особых алгоритмов для генерации комплексных чисел не применяется, а отдельно генерируются вещественная и мнимая части в нужных преде- лах. В том, что это фактически так и есть, можно убедиться, например, следующим непритязательным образом: In[39]:=SeedRandom[117]; Random[Complex] Out[39]=0.85043+0.266285*I In[40]:=SeedRandom[117]; Random[]+I*Random[] Out[40]=0.85043+0.266285*I Таким образом, для генерации комплексных чисел в прямоугольнике мы могли бы точно с таким же успехом пользоваться, например, такой коман- дой: 178 Random[Real, {a,b}]+I*Random[Real,{c,d}] Упражнение. Тип случайной переменной может быть только целым, ве- щественным или комплексным числом. Попытка задать случайное рацио- нальное число посредством Random[Rational] немедленно приведет к сле- дующему сообщению об ошибке: Random: Type specification Rational in Random[Rational] should be Real, Integer, or Complex. Как можно породить случайное рациональное число? Упражнение. Как породить случайное комплексное число в единичном круге? В действительности, как должно быть ясно уже из приведенного выше примера, когда мы дважды разными командами породили одно и то же “случайное” комплексное число, функция Random является точной функ- цией, хотя случайному наблюдателю это не должно быть видно. Например, вызвав функцию Table[Random[Integer, {0,9}],{i,1,50}] Вы получите случайную последовательность из 50 цифр. Вызвав эту функцию еще раз, Вы получите уже совершенно другую после- довательность. Это связано с тем, что каждый вызов функции Random меняет текущее значение системной переменной $RandomState. Однако ча- сто при отладке или сравнении программ желательно несколько раз вызы- вать одно и то же случайное число. Это делается одним из двух способов: • Функция SeedRandom[n] перезапускает генератор случайных чисел, ис- пользуя n в качестве затравки. Эта функция позволяет несколько раз по- лучать одну и ту же последовательность случайных чисел!!! Например, вызвав функцию SeedRandom[123]; Table[Random[Integer, {0,9}],{i,1,50}] Вы как и раньше получите случайную последовательность из 50 цифр. Вы- звав эту функцию еще раз, Вы получите ту же самую последо- вательность. Чтобы получить другую последовательность, Вам теперь нужно изменить аргумент SeedRandom!!! Функция SeedRandom[ ], вызван- ная вообще без аргументов, перезапускает генератор случайных чисел, ис- пользуя в качестве затравки время суток. Другой народный способ, смысл которого состоит в том, чтобы ослабить роль человеческого фактора, со- стоит в том, чтобы вначале исполнить команду seed=Random[Integer, {2000,3000}], а уже потом подставлять SeedRandom[seed]. • Еще один способ получить ту же самую последовательность таков. Мы уже упоминали, что значение системной переменной $RandomState ме- няется при каждом обращении к команде Random. Например, исполнив несколько раз программу Random[]; Total[IntegerDigits[$RandomState]] 179 можно убедиться в том, что $RandomState представляет собой целое число в котором от 2400 до 2800 цифр. В любой момент сессии выполнив присваи- вание state=$RandomState; можно записать текущее состояние генератора случайных чисел. В дальнейшем можно восстановить это значение посред- ством $RandomState=state; для последующего получения тех же самых случайных чисел. Предостережение. Наивная точка зрения состоит в том, что мы могли бы снова явно породить state=Random[Integer, {10^2400,10^2800}] в нужных пределах. Однако в отличие от затравки RandomSeed, которую можно порождать произвольно, далеко не все что угодно может быть значением $RandomState!!! Скорее всего, результатом попытки исполнить команду $RandomState=state будет сообщение об ошибке $RandomState: blabla< § 15. Бесконечность и неопределенность Есть еще несколько очень важных вещественных/комплексных не-чи- сел (not-numbers), которые могут возникать в вычислениях, как арифме- тических, так и аналитических, в особенности при вычислении пределов, бесконечных сумм и произведений, интегралов и пр. Infinity вещественная бесконечность Indeterminate неопределенность ComplexInfinity комплексная бесконечность DirectedInfinity направленная комплексная бесконечность При попытке вычислить 1/0 выдается сообщение об ошибке Power: Infinite expression 1/0 encountered. Тем не менее, Mathematica знает ответ ComplexInfinity. Как мы сейчас убедимся, при попытке вычислить 0/0 мы получим сразу два сообщения об ошибке. Вот четыре классических неопределенности: In[41]:= {0/0,0*Infinity,Infinity/Infinity,Infinity-Infinity} Power: Infinite expression 1/0 encountered. Infinity: Indeterminate expression 0*ComplexInfinity encountered. Infinity: Indeterminate expression 0*Infinity encountered. Infinity: Indeterminate expression 0*Infinity encountered. Infinity: Indeterminate expression -Infinity+Infinity encountered. Out[41]= {Indeterminate,Indeterminate,Indeterminate,Indeterminate} Кроме того, в соответствии с аналитическими традициями, Mathematica ве- рит, что 0^0 тоже является неопределенностью. Алгебраисты знают, что на самом деле 0 0 = 1. В действительности, в это должен верить каждый, 180 кто верит в справедливость формулы (x + y) 2 = x 2 y 0 + 2x 1 y 1 + x 0 y 2 . Од- нако принятое в Mathematica соглашение весьма обычно при вычислении пределов и других аналитических вычислениях. Неопределенность действует следующим образом. Если в процессе вы- числений встретился неопределенный результат, то действие обычных пра- вил арифметики прекращается и все последующие содержашие его резуль- таты тоже автоматически становятся неопределенными. Что касается бесконечностей, то они точное соотношение между ними следующее. Самой общей из них является функция DirectedInfinity. А именно, DirectedInfinity[z] порождает бесконечность в направлении комплексного числа z. С внутренней точки зрения остальные перечислен- ные разновидности бесконечностей являются просто сокращениями: • Комплексная бесконечность ComplexInfinity является просто сокра- щением для DirectedInfinity[], т.е. для направленной бесконечности вы- званной вообще без направления (= с неопределенным направлением). • Вещественная бесконечность Infinity рассматривается как сокраще- ние для DirectedInfinity[1], т.е. для направленной бесконечности вы- званной в направлении положительной вещественной полуоси • Вещественная бесконечность -Infinity рассматривается как сокраще- ние для DirectedInfinity[-1], т.е. для направленной бесконечности вы- званной в направлении отрицательной вещественной полуоси • Для многих аналитических вычислений, скажем, при вычислении кон- турных интегралов, нужна бесконечность в других направлениях, ну, ска- жем, DirectedInfinity[I] направленная вдоль положительной мнимой полуоси. В ответе такая бесконечность будет выводиться как I*Infinity, но ее полная внутренняя форма, все-таки DirectedInfinity[I]. Вещественные бесконечности Infinity и -Infinity можно использовать при задании итераторов в суммах и произведениях, при вычислении пре- делов, задании пределов интегрирования и всех других аналогичных мани- пуляциях. В подавляющем большинстве случаев Mathematica верно истол- ковывает Ваши намерения. Лет 25 назад злопыхатели широко распростра- няли слухи о мнимых ошибках в Mathematica и Maple, однако, как выясни- лось, в действительности, ошибки содержались в (составленных людьми!!!) таблицах рядов и интегралов, использовавшихся в библиотеках этих си- стем! В действительности, вычисление Sum[1/i^2, {i,1,Infinity}] дает точное значение π 2 /6, как и задумано. Вероятность наткнуться на ошибку во всех обычных вычислениях такого рода меньше, чем вероятность на- ткнуться на ошибку в печатных версиях таблиц рядов и интегралов. 181 Глава 5. ПЕРЕМЕННЫЕ И ИХ ЗНАЧЕНИЯ Язык их ясен и конкретен. Для простоты дела все животные, ракушки, птицы, рыбы, ягоды, мох и змеи, кроме самых ядовитых, называются у них одинаково. Александр и Ольга Флоренские. Движение в сторону Йые Osborn's Law: Variables won't; constants aren't. В этой главе мы начинаем обсуждать ключевые понятия, которые по сво- ей сути относятся к программированию и требуют уточнения традиционно- го математического языка посредством введения в него (не на лексическом, а на грамматическом уровне!!!) идеи времени. Математика не знает идеи времени, в то время как для фактического вычисления последовательность выполнения операций (flow of calculation) становится исключительно важным, а часто решающим обстоятельством. Однако при этом традици- онное программирование имело дело с весьма ограниченным набором вы- числений с достаточно примитивными типами объектов. Иными словами, математики проводили нетривиальные вычисления с интересными объек- тами, но делали это плохо — по крайней мере с точки зрения возможности перенести их вычисления на компьютер!!! Основным, чтобы не сказать единственным, инструментом математиков всегда было понимание, так что вопрос о воспроизводимости, не говоря уже об эффективности, вы- числения их не интересовал. В то же время программисты традиционно проводили бессодержательные вычисления с лишенными интереса объек- тами, но всегда делали это правильно и систематически. В этом смысле точка зрения компьютерной алгебры является эффективным синтезом ма- тематической и программистской точек зрения. Как и в математике, мы проводим любые вычисления с любыми объектами, доступными нашему умозрению, но как и в программировании делаем это эффективно перено- симыми методами, такими методами, которые опираются не на медитацию и непосредственный контакт с миром идей, в мистических и практических аспектах, а лишь на четко описанные простые, явные и действенные алго- ритмы. § 1. Математика как неточная наука The problem with you mathematicians is that you are so imprecise. Real Programmer Люди, не имеющие отношения к математике, обычно характеризуют ее как точную науку . В этой фразе верно все, кроме слов точная и наука. Как говорит само ее название, математика является учением, доктриной и областью знания. Кроме того, в настоящее время она организационно, а отчасти идеологически и психологически, близка к некоторым областям науки. В то же время математика, конечно, не является наукой, так как ее цели, метод и критерии ценности гораздо ближе к искусству или религии 182 и имеют мало общего с целями, методами и установками, характерными для естествознания. С другой стороны, и точность в математике важна только как инструмент, или побочный продукт, а вовсе не как самоцель. Более того, чем лучше мы понимаем, что говорится, тем менее точными мы можем позволить себе быть. По стандартам многих других видов деятельности, скажем, программи- рования, математика является весьма неточным занятием. В предыдущей главе мы уже упоминали, что обычные математические обозначения крайне неоднозначны. Как отмечает Виктор Анатольевич Уфнаровский 50 , все три минуса, встречающихся в выражении −(−1 − 2), использованы в трех со- вершенно разных смыслах: ◦ первый минус обозначает унарную операцию x 7→ −x; ◦ второй минус является частью имени числа −1; ◦ третий минус обозначает бинарную операцию (x, y) 7→ x − y. Причина, по которой это мало кого волнует и практически никогда не со- здает серьезных неудобств, состоит в том, что пользующийся этими обо- значениями человек иногда до некоторой степени понимает смысл текста. Но, вероятно, самым сомнительным математическим знаком является знак =. Вот простенький текст, подтверждающий эту декларацию: “Пусть f = x 2 − ax + 1. Положим a = 2. Тогда f = (x − 1) 2 и, значит, уравнение x 2 − ax + 1 = 0 имеет единственный корень x = 1 кратности 2”. Что мы подразумеваем, когда пишем f (x) = g(x)? Предлагаем ли мы положить значение неизвестной функции f в точке x равным g(x)? Или мы пред- лагаем положить его равным g(x) в любой точке x? Утверждаем ли, что значения известных нам функций f и g равны при любом 51 x из области определения? Или из какого-то содержащегося в ней множества? Или при каком-то/каких-то x, который/которые предлагается найти? Ясно, что все это абсолютно различные смыслы и читающий математический текст че- ловек, который в состоянии следить за происходящим, обычно в состоянии истолковать, какой из этих смыслов имеется в виду: конечно, это зависит от степени его квалификации, сомнительная ситуация легко поставит на- чинающего в тупик, но зрелый читатель, скорее всего, решит, что либо в тексте допущена опечатка, либо автор сам не понимает, о чем говорит. С точки зрения языка Mathematica знак равенства в математическом тексте может обозначать любую из (по крайней мере!!!) восьми абсолютно различных вещей: ◦ шесть операторов =, :=, ->, :>, ^=, ^:=; ◦ два отношения ==, ===. 50 В.А.Уфнаровский, Математический аквариум. — Кишинев, Штиинца, 1987, с.1– 215; стр.30. 51 Мы совершенно оставляем в стороне структурные вопросы, которые с таким трудом усваиваются начинающими, например, чем равенство семейств отличается от равенства функций, и почему это из того, что f (x) = g(x) для любого x из области определения еще не следует, что f = g? 183 Как смысл этих вещей, так и — тем более!!! — их использование, настоль- ко отличаются между собой, что непоколебимое упорство математиков в желании обозначать все эти понятия одним и тем же символом = служит еще одним парадоксальным подтверждением сакраментальной дефиниции Пуанкаре: математика — это искусство называть разные вещи одним именем. В частности, в предыдущем тексте употреблено пять совершенно разных знаков равенства: :=, =, ===, ==, ->. А ведь до сих пор мы практически не упоминали того, что известно в Computer Science как ход вычисления (flow of calculation), иными словами, то, что сами значения f , g и x меняются в процессе вычисления — математик использовал бы в этом смысле тысячу индексов, что было бы, конечно, чуть точнее, чем принятое в программировании понятие пере- менной, но гораздо менее удобно!!! Например, когда мы говорим, `положим a = 2', то совершенно неясно, имеем ли мы в виду • присваивание: a становится навсегда равным 2, на языке Mathema- tica a=2, или • подстановку: a становится равным 2 только в этом вычислении, на языке Mathematica a->2. Но ведь если мы сами этого не понимаем, нам вряд ли удастся объяснить это даже такой интеллигентной системе, как Mathematica. § 2. Переменные и их значения Переменная — это область в памяти компьютера, где может хра- ниться некоторое значение для использования его в программе. Харви Дейтел, Пол Дейтел, “Как программировать на C++”, С точки зрения математика переменная — например, буковка x в запи- си многочлена f = a n x n + . . . + a 1 x + a 0 ∈ K[x] над полем K — является некоторым новым трансцендентным объектом. Этот объект не принад- лежит основному полю K и сам не имеет никакого значения, но именно поэтому его можно без противоречия специализировать в различные эле- менты поля K — или, на классическом языке, придавать ему различные значения. В этом случае математик напишет x 7→ x 1 , x 7→ x 2 , . . . , но са- ма переменная никогда не меняется — ее можно только заменить, но в ней нет ничего, что можно было бы изменить. Для традиционно- го программиста, который имел дело только с численными вычислениями, переменная это нечто совсем иное. Это не какой-то потусторонний объ- ект, а просто метка или ярлык, вроде номера ячейки, которая обозначает конкретное число, получающееся из каких-то других данных в программе и/или хранящееся где-то в памяти компьютера. Число, хранящееся под этим ярлыком, может меняться, но программист ссылается на эти разные значения как на одну и ту же переменную, он считает, что сама пере- менная x равна x 1 , x 2 , . . . в разные моменты времени. Точка зрения компьютерной алгебры представляет собой соединение двух этих противо- положных точек зрения. С точки зрения flow of calculation переменная 184 компьютерной алгебры — это переменная традиционного программирова- ния, но только теперь ее значения совсем не обязательно являются числами! В действительности, то, что делает компьютерную алгебру столь мощным инструментом, это как раз полиномиальные вычисления, т.е. способ- ность истолковывать значения переменных (в компьютерном смысле) как переменные (в математическом смысле)!! Основой любых символьных вычислений является способность системы рассматривать символы как переменные и присваивать им значения, которые могут быть любыми допустимыми в контексте проводимого вы- числения выражениями, например, числами или другими символами. При этом, как и в традиционном программировании, в разные моменты вычис- ления один и тот же символ может иметь различные значения. То значение, которое символ имеет в данный момент вычисления, называется текущим значением. В следующих параграфах мы обсудим основные способы при- сваивания, временного присваивания (подстановки) и модификации значе- ний переменных. Сделаем пока несколько общих замечаний: • Если какому-то символу не присваивалось никаких значений, значени- ем этого символа является он сам, рассматриваемый как независимая полиномиальная переменная. В частности, до дальнейших инструк- ций числа Pi, E – и даже GoldenRatio!!! – рассматриваются как независи- мые переменные. • Все переменные сохраняют свои значения на протяжении сес- сии, до тех пор, пока эти значения не были модифицированы или вычи- щены. Основной причиной ошибок при вычислениях является использование в них переменных, которым уже присвоены зна- чения, в §§ 7–10 мы обсудим несколько способов избежать этого (исполь- зование подстановок вместо присваиваний, чистка и создание локальных переменных). Однако самое простое — давать переменным говорящие име- на. • Некоторые вещи, не являющиеся символами, (целые и рациональные числа, стринги и объекты некоторых других специальных форматов) с точки зрения подавляющего большинства команд считаются имеющими постоянное значение, и их текущее значение в любом выражении все- гда равно этому постоянному значению. Такие вещи называются сырыми объектами (raw objects) в том смысле, что перед употреблением в пищу их не обрабатывают. Предостережение. Из приведенных выше примеров можно сделать поспешный вывод, что сырыми бывают только атомарные объекты. Однако в действительности сырой объ- ект может быть устроен сколь угодно сложно, например, подавляющее большинство команд рассматривает разреженные объекты типа SparseArray как сырые, это делает- ся для того, чтобы избежать вычислений с матрицами с миллиардами или десятками миллиардов коэффициентов. Ясно, что вычисления с такими матрицами на бытовом компьютере по обычным алгоритмам работы над списками, когда каждая компонента занимает собственный сектор памяти, физически невозможны. Поэтому их можно об- рабатывать только при помощи небольшого количества специальных команд, которые правильно учитывают их структуру и специфику (некоторые из этих команд называ- 185 ются обычными именами, но работают совсем иначе). Точно также стринги являются сырыми объектами только с точки зрения обычных математических вычислений. Спе- циальные текстовые команды работы над стрингами позволяют сливать, изменять и редактировать стринги, подставлять в них результаты математических вычислений и прочее и прочее и прочее. Все правильно составленные выражения, в которые входят сырые объ- екты и символы, тоже приобретают текущие значения, которые определя- ются текущими значениями символов с учетом определений всех входящих в эти выражения функций и всех определенных для них правил преобра- зования, как тех, которые встроены в систему, так и (в первую очередь!!!) тех, которые определены пользователем. Вычисление текущего значения выражения называется просто вычислением или эвалюацией (evalua- tion) этого выражения. Текущим значением выражения является другое — либо то же самое!!! — выражение, причем система вычисляет значение выражение f[x,y,...z] следующим образом: • вычисляется заголовок f выражения; • поочередно вычисляются все элементы x, y, . . . , z — кроме тех, вычис- ление которых явным образом запрещено специальной командой Hold или ее вариантами и/или родственниками HoldFirst, HoldRest, HoldAll, HoldPattern, HoldSequence и т.д.; • используются ассоциативность, дистрибутивность и коммутативность — именно в таком порядке!!! — если f обладает этими свойствами. • используются все правила и подстановки, определенные пользователем для функций, входящих в определение x, y, . . . , z; • используются все внутренние правила и подстановки, для функций, входящих в определение x, y, . . . , z; • используются все правила и подстановки, определенные пользователем для функции f ; • используются все внутренние правила и подстановки, для функций, входящих в определение f . В некоторых случаях применение всех этих правил не упрощает выраже- ния, тогда система оставляет его в первоначальном виде (unevaluated). Иными словами, текущим значением такого выражения является само это выражение. § 3. Многочлены Как мы уже обсуждали, основой системы Mathematica, как и других систем компьютерной алгебры, являются полиномиальные вычисления. В Главе 3 мы видели, как выделить компоненты многочлена, рассмат- риваемого как выражение, при помощи команд работы с выражениями и списками Part и Level. В языке Mathematica для этой цели есть и специ- альные команды. Мы будем обсуждать их главным образом для многочле- нов от одной переменной, но в действительности все они работают и для 186 многочленов от нескольких переменных. Variables[f] список переменных многочлена f Exponent[f,x] наибольшая степень с которой x входит в f Coefficient[f,x,n] коэффициент при x n в f CoefficientList[f,x] список коэффициентов f как многочлена от x PolynomialQ[f,x] является ли f многочленом от x? Прежде всего заметим, что многочлен небольшой степени можно задать явным образом, как a+b*x+c*x^2+d*x^3. Однако, для многочленов высо- кой степени нужны какие-то более интеллигентные способы. Простейший состоит, конечно, в том, чтобы использовать итератор, например так: poly[n ,a ][x ]:=Sum[a[i]*x^i, {i,0,n}] С другой стороны, конечно, как всегда в Mathematica существуют десятки других способов добиться того же результата, скажем, poly[n ,a ][x ]:=Dot[Table[a[i], {i,0,n}],Table[x^i,{i,0,n}]] Теперь вычисление poly[5,a][x] даст a[0]+x*a[1]+x^2a[2]+x^2a[3]+x^4a[4]+x^5a[5]. Для тестирования программ полезно выбирать многочлены со случайными коэффициентами, в этом случае мы просто напишем Random[] вместо a[i]. Команда Variables[f] говорит нам, что именно в данный момент рас- сматривается в качестве входящих в f независимых переменных. Напри- мер, когда мы пишем f=a+b*v+c*x^2 мы, скорее всего, имеем в виду, что f является многочленом от переменной x с коэффициентами a, b, c. Од- нако система думает несколько иначе. Вычисление Variables[f] дает {a,b,c,x} (конечно, если переменным a, b, c до этого не присваивалось ни- каких значений!) Тоньше всего использование этой команды с точными ве- щественными или комплексными числами. Поскольку для чисел E, Pi и т.д. тест NumericQ[x] дает значение True, они не рассматриваются в качестве независимых переменных!! Таким образом, вычисление Variables[E+Pi] дает {}. В этом месте мы предлагаем тому, кто раньше не задумывался над работой систем компьютерной алгебры, сделать глубокий вдох и немного помедитировать. С точки зрения всех точных вычислений E и Pi явля- ются независимыми полиномиальными переменными. В то же время они рассматриваются как числа, а не как независимые переменные. Подоб- ный моральный релятивизм и постоянная смена фокуса типичны скорее для чистой математики, чем для программирования! Команда Exponent[f,x] вызванная с двумя аргументами возвращает степень многочлена f по переменной x. Например, для f=a+b*v+c*x^2 вычисление Exponent[f,x] даст 2, а вычисление Exponent[f,a] даст 1. В действительности, в полном формате команда Exponent вызывается с тре- мя аргументами как Exponent[f,x,g], где g — функция, которую следует применить к списку всех показателей степени, с которыми x входит в f . По умолчанию параметр g полагается равным Max, но, конечно, в качестве 187 g можно взять много других функций, скажем Min, List, Sequence, Plus, etc., etc. Ну, например, при вычислениях с многочленами Лорана f = a −l x −l + . . . + a −1 x −1 + a 0 + a 1 x 1 + . . . + a n x n ∈ K[x, x −1 ] естественно одновременно рассматривать порядок, т.е. наименьшее m та- кое, что a m 6= 0 и степень, т.е. наибольшее n такое, что a n 6= 0. Это де- лается при помощи команды Exponent[f,x, {Min[##],Max[##]}&]. В этой команде мы вызываем функцию, сопоставляющую списку пару, состоящую из его наименьшего и наибольшего элементов в формате чистой функции. Обращение к элементам списка в формате последовательности аргумен- тов ## необходимо потому, что мы априори не знаем, сколько элементов в этом списке. Последовательность ## вызывает их все. Точно так же Ex- ponent[f,x,List] породит список всех показателей степени, с которыми x входит в f и т.д. Упражнение. Что мы получим при вычислении Exponent[0,x, {Min[##],Max[##]}&]? Ответ. Да уж, конечно, правильный ответ {Infinity,-Infinity}. Как и принято в математике, функция Min[], вызванная вообще без аргументов, дает Infinity, а функция Max[], естественно, -Infinity. Функции Coefficient и CoefficientList служат тому, чтобы породить индивидуальный коэффициент и список коэффициентов многочлена f , со- ответственно. Их использование абсолютно понятно исходя из названий. А именно, Coefficient[f,x,i] возвращает коэффициент с которым x i вхо- дит в f . С другой стороны, CoefficientList[f,x] возвращает список всех коэффициентов от степени 0 до Exponent[f,x]. Mожет показаться, что функции Coefficient и CoefficientList дуб- лируют друг друга. Действительно, функция CoefficientList легко вы- ражается через Coefficient, например, так clist[f ,x ]:=Table[Coefficient[f,x,i], {i,0,Exponent[f,x]}] Естественно, функция clist всегда возвращает тот же результат, что и CoefficientList. Но для случайных многочленов степени несколько тысяч она делает это раз в 100 медленнее!! В этом можно убедиться, например, определив случайный многочлен rapo=Sum[Random[]*x^i, {i,0,1000}]; — кстати, почему мы написали здесь =, а не :=?? — и вычислив TrueQ[clist[rapo,x]==CoefficientList[rapo,x]]. Точно так же, если f проходит тест PolynomialQ[f,x], т.е. если f дей- ствительно является многочленом от x, то Coefficient[f,x,i] даст тот же результат, что CoefficientList[f,x][[i+1]], хотя, конечно, снова го- раздо быстрее! Обратите внимание на сдвиг номера, список коэффициен- тов начинается с нулевой степени, однако соответствующий коэффициент является первой компонентой списка!!! Таким образом для многочленов функции Coefficient и CoefficientList действительно выражаются друг через друга. 188 Однако в действительности функция Coefficient является значитель- но более общей! Для того, чтобы к выражению f можно было применить функцию CoefficientList, оно действительно должно быть многочленом. В частности, оно не может содержать отрицательных или дробных степе- ней x, не говоря уже о трансцендентных функциях от x. Попытка вы- числить что-нибудь в духе CoefficientList[x^-3+a+b*x+c*x^2,x] момен- тально приведет к сообщению об ошибке General: a+1/x^3+b*x+c*x^2 is not a polynomial. В то же время, функция Coefficient знает, что делать в подобных случаях. Вычисление Map[Coefficient[a*x^-3+b*Sqrt[x]+c*Sin[x],x,#]&, {-3,1/2}] дает {a,b}, как и задумано. § 4. Немедленное и отложенное присваивание: = Set versus := SetDelayed Символ нуля — 0. А символ ноля — О. Даниил Хармс, Нуль и ноль Вот две основные команды, которые придают значения переменным: немедленное присваивание = Set и отложенное присваивание := SetDelayed. Уяснение различия между ними имеет ключевое значение для того, кто никогда раньше не занимался программированием!!! Собственно именно с этого места программирование начинает отличаться от матема- тики! x=y Set[x,y] немедленное присваивание x:=y SetDelayed[x,y] отложенное присваивание Еще раз объясним основное различие между двумя этими командами, или как принято говорить в программировании, операторами присваи- вания: • Когда мы выполняем непосредственное присваивание lhs=rhs, его правая часть rhs вычисляется один раз в тот момент, когда мы вы- полняем присваивание; • Когда мы выполняем отложенное присваивание lhs:=rhs, его правая часть rhs заново вычисляется каждый раз, когда мы обращаемся к значению его левой части lhs. В качестве иллюстрации этого рассмотрим следующий диалог: In[1]:=x=1; y=x; x=2; y Out[1]=1 In[2]:=x=1; y:=x; x=2; y Out[2]=2 In[3]:=ClearAll[x,y] 189 Хорошо видно, что в первом случае мы придаем переменной y текущее значение переменной x на момент присваивания. В то же время в случае отложенного присваивания значение переменной y вычисляется исходя из текущего значения переменной x на момент обращения. Еще раз поясним два момента, фигурирующих в этом вычислении. Во первых, в нем использована точка с запятой. Вместо этого мы могли бы просто напечатать присвоения x=1, y=x, x=2 в трех отдельных строках, а x — в четвертой строке. Однако нас интересует только значение x в конце вычисления, поэтому мы помещаем все четыре шага в одну строку, разде- ляя их точками с запятой. В этом случае все эти вычисления выполняются, но на экран выводится только результат последнего из них. , разделение аргументов функции или компонент списка ; разделение команд или частей аргумента Постановка ; в конце инпута интерпретируется как выполнение пустой операции. Тем самым, предшествующая операция производится, но ее результат не выводится. Во-вторых, в конце вычисления использована команда ClearAll. Она нужна, чтобы убрать определения и текущие значения переменных x и y, иначе на протяжении всей сессии программа будет считать, что x = y = 2. Мы уже упоминали, что давать всем используемым переменным такие имена, как x или y — это не слишком хорошая идея. Критическое различие между Set и SetDelayed особенно хорошо видно в следующем диалоге: In[4]:=xxx=Random[]; Table[xxx, {5}] Out[4]= {0.325926,0.325926,0.325926,0.325926,0.325926} In[5]:=yyy:=Random[]; Table[yyy, {5}] Out[5]= {0.116906,0.216847,0.821755,0.754748,0.485576} В первом случае функция Random вызывается один раз, а во втором — каждый раз заново при каждом обращении к ней. Обозвать перемен- ные xxx и yyy — это еще один грязный трюк, позволяющий избежать ис- пользования присвоенных xxx и yyy значений в дальнейших вычислениях, в следующий раз мы просто назовем переменные funx и funy или xbis, ybis, или еще как-нибудь в таком духе. • Не всякое присваивание фактически удается осуществить: написав 2=x, Вы получите сообщение об ошибке cannot assign to raw object 2. Предостережение. Обычно сопротивление системы удается преодолеть и в таких слу- чаях, но не пытайтесь это сделать!!! Вот, что по этому поводу говорится в The Mathe- matica Book: Raw should be only used under very special circumstances. Присваивание 2 значения 3 является одним из самых надежных способов уронить ядро Mathematica и потерять все несохраненные во время сессии результаты. • Mathematica помнит только последнее по времени присваивание, кото- рое удалось осуществить: x=y; x=z даст нам x равное z, а не y. 190 • Некоторым системным переменным (таким как $RecursionLimit и т.д.) нельзя присваивать произвольные значения. Не думайте об этом, пока не столкнетесь с сообщением recursion limit exceeded, после этого положи- те $RecursionLimit=Infinity. § 5. Секунды, такты и шаги Допустим, нам требуется переименовать переменные x и y. Мы не можем просто присвоить x=y, так как при этом старое значение x будет утрачено. По той же причине мы не можем и присвоить y=x. Основные традиционные способы сделать это таковы 52 : ◦ Ввести новую переменную z и выполнить следующую последователь- ность присваиваний: z=x; x=y; y=z. ◦ Рассмотреть (x, y) как вектор и выполнить следующую последователь- ность присваиваний: x=x+y; y=x-y; x=x-y. С точки зрения линейной ал- гебры речь здесь идет, конечно же, о том, что перестановка двух координат вектора может быть реализована как цепочка операций, каждая из кото- рых меняет не более одной координаты. Или, как нас учат/мы учим на первом курсе, элементарное преобразование третьего типа можно предста- вить в виде произведения элементарных преобразований первого и второго типов. Однако первый из этих способов требует создания дополнительной пере- менной, а второй — некоторой выдумки (или знания линейной алгебры!) Система Mathematica сконструирована так, чтобы пользователь мог обхо- диться без того и другого 53 . А именно, естественный способ выполнить эту операцию; более того, единственно правильный способ выполнить эту операцию; тот, который задуман для подобных ситуаций творцами систе- мы; тот, под который она оптимизирована; состоит в том, чтобы выполнить оба присваивания одновременно: ◦ Выполнить присваивание списком {x,y}={y,x}. Этот пример должен подготовить начинающего к мысли, что измеряемое шагами течение внутреннего времени в алгоритме отличается не только от математического отсутствия времени, не только от измеряемого секундами физического течения времени, но и от хода тактового времени при фактиче- ском исполнении этого алгоритма процессором!! Фактически, разумеется, при выполнении присваивания {x,y}={y,x} присваивание x=y выполняется на несколько тактов раньше, чем присваивание y=x. Однако с точки зрения алгоритма они происходят за один шаг, поэтому в присваивании y=x ис- пользуется старое, а не новое значение x. В то же время при нашей неудач- 52 А.Шень, Программирование. Теоремы и задачи. — М., МЦНМО, 2004, с.1–296; стр.8. 53 Разумеется, на уровне фактического вычисления компьютер при этом создает но- вые переменные, но это тот уровень вычисления, который спрятан в код на языке C, т.е. сознательно скрыт не только от пользователя, но и от от того уровня, на котором происходит мышление самой системы! 191 ной попытке написать x=y; y=x присваивания происходят последовательно не только с точки зрения процессора, но и с точки зрения алгоритма, т.е. не только в разных тактах, но и на разных шагах!! В качестве метафоры подобного тройного контроля времени секундами, тактами и шагами можно привести съемку фильма. Измерение времени в шагах отвечает внутреннему времени сюжета. Измерение времени в тактах — съемочным дням. Ну и, наконец, процесс производства фильма занима- ет год или два — а то и десять лет!! — физического времени. Ясно, что хотя эти три способа контроля времени подчинены некоторым общим огра- ничениям, устанавливающим связи между ними, это соответствие вовсе не является прямым. В то же время, трудно не заметить, что связь съемоч- ных дней с астрономическими гораздо более тесная, чем с сюжетными!! Нас как зрителей не интересует, снят более ранний по сюжету эпизод до или после последующего. Нам важно только как смонтирован фильм!!! В этой книге в большинстве ситуаций нас интересует исключительно развитие сюжета — и в дальнейшем мы как правило обсуждаем только ас- пекты, связанные с шагами рассматриваемых алгоритмов. Тем не менее в некоторых случаях — ну, например, когда мы сами снимаем фильм — нас может начать волновать и прямой контроль времени, в том числе и физиче- ского. Такой контроль оказывается важным с практической точки зрения в тот момент, когда эффективность используемых алгоритмов становится недостаточной для того, чтобы фактически осуществить интересующее нас вычисление. Следующие команды дают глобальные временные параметры сессии: AbsoluteTime[] время в секундах начиная с 1 января 1900 года SessionTime[] время в секундах с начала текущей сессии TimeUsed[] время работы CPU в секундах с начала сессии Вот например, как выглядят параметры сессии, сопровождавшей написа- ние этого параграфа: In[6]:= {AbsoluteTime[],SessionTime[],TimeUsed[]} Out {3.3062861285750416 10^9, 47872.8077168, 14.479} Обращает на себя внимание, что работа CPU, направленная собственно на вычисление, представляет собой ничтожно малую долю общей продолжи- тельности сессии!! Однако в большинстве случаев нас значительно больше интересует кон- троль времени индивидуального вычисления. Timing[x] время работы CPU при вычислении x AbsoluteTiming[x] полное время вычисления x $TimeUnit минимальный интервал фиксируемый Timing TimeConstrained[x,t] вычисление x с контролем времени t секунд Команда Timing[x] вычисляет x и возвращает время работы CPU, необ- ходимое для этого вычисления и полученное значение x. Вот некоторые особенности ее использования: |