Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
[ Цыганов ] Системы символьных вычислений (Maple).pdf
Скачиваний:
64
Добавлен:
22.08.2013
Размер:
449.75 Кб
Скачать

Системы символьных вычислений.

А.В. Цыганов

1.Теоретическое занятие

Стех пор, как стали возможными вычисления на ЭВМ, одно из главных применений компьютеров заключалось в численных расчетах. Очень скоро начали доминировать (в смысле объема вычислений) приложения к задачам управления. Однако научные приложения остаются наиболее престижными, особенно если взглянуть на требуемую производительность компьютера: наиболее мощные компьютеры обычно предназначаются для научных исследований.

Важно отметить, что в самом понятии "научные вычисления" содержится двусмысленность: прежде чем на сцене появился компьютер, вычисления представляли смесь численного счета с тем, что будем называть "алгебраическими вычислениями", т.е. с операциями над математическими формулами.

Единственным примером чисто численных расчетов является, повидимому, деятельность неординарных вычислителей, таких, как Иноди: авторы таблиц, в особенности логарифмических, выполняют огромный объем численных расчетов, но даже и этим вычислениям предшествует

доводка алгебраических формул и методов, необходимая для того, чтобы работа оказалась в пределах человеческих возможностей.

Напротив, знаменитые великие вычисления ХIХ века содержат большое количество манипуляций с формулами. Наиболее известным является, несомненно, расчет Леверье орбиты Нептуна, который был основан на возмущениях орбиты Урана и привел к открытию Нептуна. Наиболее впечатляющие вычисления с карандашом и бумагой выполнены также в области астрономии: Делоне потребовалось 10 лет для вычисления орбиты Луны и еще 10 лет для ее проверки. Проверка выявила несколько ошибок в знаках и несколько "потерянных" двоек. Результат не является численным, поскольку он состоит в основном из формулы, которая сама по себе занимает 128 страниц 4-й главы его книги. Заметим, что с использованием пакета Mathematica на

персональном компьютере типа Pentium 166 проверка

данных

вычислений, проведенная по архивам Делоне, занимает

около 10

минут

(не учитывая время на набор формул).

 

 

 

Отмеченная выше двусмысленность заключается в следующем: с

появлением

компьютеров

выполнять

численные

расчеты

стало

значительно проще и сделалось достаточно привычным выполнять огромные вычисления, которые в некоторых случаях давали возможность избежать трудоемких алгебраических выкладок. Это привело к тому, что для широкой публики и даже для большинства научных сотрудников численные расчеты стали синонимом научных вычислений. Когда в заголовках или в списке тем конгресса или конференции содержатся слова "научные вычисления", мы, как правило, можем быть уверены, что речь идет только о численных расчетах, даже если компьютерная алгебра также содержится в этом списке тем.

Очевидно, численные расчеты не исключают алгебраических

1

вычислений: написание простейших программ требует переписывания формул, на которых основан алгоритм. И мощности компьютеров далеко не решают всех проблем: расчет развития атмосферных процессов с точностью, необходимой метеорологам для 48-часового прогноза, на наиболее мощных компьютерах, доступных в настоящее время (типа CRAY), требует гораздо более 48 часов. Увеличение производительности в 10 раз едва ли улучшит ситуацию, поскольку одновременно с уточнением теории потребуется в 2 раза уменьшить размер сетки (чтобы отличить, например, погоду в Петербурге от погоды в Петергофе), а это потребует 8-кратного увеличения объема вычислений.

Компьютерная алгебра.

Алгебраические вычисления не потеряли своей актуальности. Однако чаще всего они выполняются вручную, хотя первые логические устройства для их автоматизации появились достаточно давно (в 1953 году). Очень скоро стало ясно, что программное обеспечение для использования в алгебраических вычислениях должно представлять собой полную систему, включающую метод представления нечисловых данных весьма специальной структуры, язык, позволяющий манипулировать с ними, и библиотеку эффективных функций для выполнения необходимых базисных алгебраических операций.

В настоящее время появились хорошо работающие системы, такие как Maple, Mathematica, Macsyma, Derive, Axiom и некоторые другие.

Все упомянутые выше системы, так же как и большинство неупомянутых систем, являются весьма дружественными по отношению к пользователю. Конечно же, и синтаксис языка пользователя у них различный, и библиотеки доступных функций могут меняться от нескольких сотен до тысяч, и внутренние структуры и даже используемые алгоритмы значительно отличаются друг от друга, но все они обладают общими свойствами. Таких принципиальных общих свойств значительно больше, чем различий и, таким образом, после освоения одной из систем компьютерной алгебры переход к другой системе не является сложной проблемой.

Разработка, развитие и даже использование этих систем постепенно выделились в автономную научную дисциплину, относящуюся, очевидно, к информатике. Ее цели лежат в области искусственного интеллекта, несмотря на то, что методы все более и более удаляются от нее. Кроме того, используемые алгоритмы вводят в действие все менее элементарные математические средства. Таким образом, эта дисциплина лежит на стыке нескольких областей, что одновременно обогащает ее и делает более трудной в исследовательском плане. Наименование этой дисциплины в последнее время стабилизировалось как "Calcul formel" во французском языке и "Computer algebra" - в

английском. В русском языке используют термины "компьютерная алгебра", "символьные и алгебраические вычисления", " аналитические вычисления" и другие.

2

Использование систем компьютерной алгебры.

Для новичка языки систем компьютерной алгебры – одни из наиболее простых для использования. Действительно, сначала ему требуется знать лишь несколько функций, которые позволят ему переписать рассматриваемую проблему в виде, очень похожем на ее математическую формулировку. Даже если переписывание выполняется неуклюже или некорректно, интерактивный режим позволяет после нескольких шагов на ощупь быстро получить результаты, которые нельзя получить с помощью карандаша и бумаги. А для очень многих приложений этого достаточно.

Однако, в отличие от языка программирования типа Фортран, в котором синтаксические тонкости требуют тщательного изучения, в то время как принципы работы компилятора можно полностью игнорировать, здесь пользователь должен очень быстро разобраться, "как это работает", в частности, как представляются и обрабатываются данные.

В действительности, хотя обычно трудно предсказать время вычисления и размер результатов, знание принципов работы может дать представление о порядке их величины и при необходимости оптимизировать их. Эти оценки в действительности существенны: для большинства алгебраических вычислений результаты получаются почти моментально, и все идет отлично. Но если это не так, то требуемое время и память возрастают обычно экспоненциально. Таким образом, выполнимость данных вычислений не всегда очевидна, и глупо жертвовать значительными ресурсами, когда неудачу можно предсказать заранее. Например, если требуется найти собственные значения матрицы, то для программы на Фортране нет принципиальной разницы 100x100 или 500x500 эта матрица, так как время выполнения растет практически линейно. В Maple или , Mathematica вычисления с матрицей 5x5 могут занимать 15 секунд, в то время как те же по сути вычисления с матрицей 6x6 займут 15 минут.

Поэтому владение эффективным стилем программирования и способность предвидеть размер вычислений являются здесь значительно более весомыми, чем в численных расчетах, где возрастание обычно бывает линейным. К сожалению, это в значительной степени приобретается с опытом и трудно передается с помощью учебника. Однако знакомство с методами позволяет легче приобрести этот опыт; именно поэтому некоторая часть лекций будет посвящена описанию математических принципов работы систем компьютерной алгебры.

Обычно, начиная работать с любой из систем символьных вычислений, пользователь достаточно легко решает небольшие и несложные примеры и задачи из учебника. Однако, приступая к решению настоящих проблем, пользователь сталкивается с рядом проблем: то компьютер слишком долго считает, то не хватает памяти, то в ответе получается формула на 5-10 страниц, а то машина выдает и вообще неправильный ответ. После этого встает вопрос - "Стоит ли тратить время на детальное изучение таких "игрушечных" систем и не лучше ли потратить это время на написание самих формул?".

Однако можно считать, что системы символьных вычислений, по сути дела, являются первыми доступными примерами искусственного

3

интеллекта. Данные системы могут, и в будущем, несомненно, будут, использоваться как при обучении, так и при повседневной работе. Главной проблемой при этом является достижение взаимопонимания между человеком и данным воплощением искусственного интеллекта. На данном этапе развития техники именно человек проводит все исследования, максимально точно определяя правила работы для машины, используя ее реальные возможности, понимая и принимая все программные ограничения.

Очевидно, человек уже не может соперничать с машиной при поиске решения по заданным правилам в достаточно полно определенном массиве данных. Например, стоило в шахматах к правилам игры добавить некоторые правила оценки позиций, как машина стала выигрывать у человека. Однако, в практике поиска решения в недетерминированном массиве, машина пока не может соперничать с человеком, который использует память, наблюдательность, комбинаторное, ассоциативное и интуитивное мышление. Заметим, что развитие прообразов систем искусственного интеллекта позволило осознать, насколько много человек знает, умеет и использует в работе.

Во все программы математических символьных вычислений заложена определенная система математических и логических правил. При этом возникает ряд проблем в связи со стремлением к универсальности данных программ. Например, если для человека вполне очевиден переход от ln(2) в арифметике к ln(2) в теории многозначных функций, то для компьютера совмещение этих понятий достаточно сложная проблема. Поэтому пользователь должен не только придерживаться заложенных в компьютер правил, но и осознать, что он хочет сделать и что при этом интуитивно подразумевает. Таки образом пользователь должен как можно более точно определить для компьютера все данные, даже те, которые он использует неосознанно. Кроме этого, в системах символьных вычислений используются особые представления данных, специальные алгоритмы их обработки и, соответственно, достаточно своеобразная логика, навязанная компьютером.

Рассмотрим выражение x^100-1. Вид этого выражения "прост" и для компьютера и для пользователя. Разложим этот полином на множители:

(x-1)*(1+x^4+x^3+x^2+x)*(1+x^20+x^15+x^10+x^5)*(1+x)*(1-x+x^2-x^3+x^4)* (1-x^5+x^10-x^15+x^20)*(1+x^2)*(x^8-x^6+x^4-x^2+1)*(x^40-x^30+x^20-x^10+1).

Это выражение так же "просто" для компьютера, как и прежнее. Но если вы получите это выражение в результате своих вычислений, то вряд ли вид этого выражения удовлетворит вас. Данный пример показывает, что, даже получив правильный ответ с помощью компьютера, вы должны еще уметь представить его в удобном для пользователя виде.

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

4