авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 12 | 13 || 15 |

«Е. М. Левич Математическое моделирование и компьютерная математика. Иерусалим, 2009 1 Содержание ...»

-- [ Страница 14 ] --

Первый работающий компьютер Z 3 был построен К. Цузе в 1941 году. Он монтировался на телефонных реле и управлялся с помощью программы, записанной на перфорированной ленте. Во многих отношениях Z 3 был подобен современным компьютерам, ибо в нем впервые применялась арифметика с плавающей запятой. Кроме того, его работа была основана на двоичной системе представления чисел. Английский специализированный компьютер Coloss был первым полностью электронным устройством.

Созданный в середине 40-х годов американский компьютер ЭНИАК можно назвать первым электронным компьютером общего назначения. Он, в частности, использовался для проведения баллистических расчетов.

Значительное продвижение в этой области связано с появлением отчета Дж. фон Неймана, Г.Г. Гольдстейна, А.В. Беркса «Предварительное рассмотрение логической конструкции электронного вычислительного устройства» (1946), где описывается проект компьютера, в котором программа и данные хранятся в единой универсальной памяти.

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

Принципы устройства компьютера, описанные в проекте, получили название «архитектура Неймана» и стали основой для разработки первых универсальных компьютеров. Среди компьютеров, построенных по этой технологии, отметим английский компьютер LEO 1, который впервые в мире стал использоваться для рутинной офисной работы, и аме-риканский компьютер UNIVAC 1, который был первым массово производимым. Он был установлен, в частности, в Бюро переписи населением США и стал использоваться для обработки макроэкономической информации. Компьютеры этого типа получили название «компьютеры первого поколения». Дальнейшее развитие компьютеров последующих поколений связано с революционными достижениями в развитии различных технологий и технических средств.

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

Одними из при-меров таких компьютеров может служить универсальная компьютерная система IBM System/360. Однако компьютеры второго поколения по-прежнему были довольно дорогими и доступными только университетам, правительственным учреждениям и крупным компаниям.

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

Новая эра наступила в начале 80-х годов с появлением, во-первых, сверхбольших интегральных схем, что позволило на одну плату помещать сначала десятки, затем сотни тысяч, миллионы транзисторов, а во-вторых, персонального компьютера IBM PC. С этого момента началось массовое внедрение компьютеров в повседневную жизнь людей.

С 80-х годов развитие компьютеров шло по двум линиям: персональные компьютеры и большие компьютеры. Производители, с одной стороны, стремились уменьшить размеры компьютеров, а с другой стороны, увеличить производительность и быстродействие этих компьютеров. В то время возникли различные идеи и были сделаны реальные попытки для их реального осуществления, которые должны способствовать увеличению производительности и быстродействия компьютеров. К таким попыткам относятся, например, разработки нейрокомпьютеров и квантовых компьютеров.

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

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

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

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

Поэтому язык верхнего уровня является наиболее сложным, а язык нижнего уровня – наиболее примитивным.

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

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

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

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

Такие языки называются языками высокого уровня. Существуют сотни языков высокого уровня.

До 60-х годов ХХ века программисты работали с машинным языком. Эта работа была малоэффективной. Эффективность работы резко возрасла, когда появилась операционная система. Появление, развитие и усложнение операционной системы позволило перейти в программировании от машинного языка к языкам более высокого уровня.

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

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

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

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

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

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

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

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

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

Существует еще третий вид представления алгоритма – в виде некоего физического устройства (специализированного компьютера или специального чипа), но алгоритм в третьем виде гораздо в меньшей степени интересует компьютерную математику, нежели первые два представления.

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

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

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

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

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

В этот период появились первые символические задачи, которые стали решать с помощью компьютеров. Эти задачи были относительно простые, ибо возможности компьютеров и программного обеспечения были достаточно ограничены.

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

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

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

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

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

Компьютерное моделирование представляет собой направление в компьютерной математике, которое в методологическом плане наиболее далеко отошло от европейской математики.

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

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

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

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

в нем удивительно много интересного.

Д. Кнут 10.2. Компьютерная арифметика.

Настоящий параграф является одним из центральных параграфов в этой книге, ибо понятие компьютерных чисел является одним из основных понятий компьютерной математики. Большое влияние на его написание оказал известный труд Д. Кнута «Искусство программирования», который отличается широтой и глубиной рассматриваемого материала, богатой библиографией. Эта книга отражает ситуацию, сложившуюся в рассматриваемых областях в конце 90-х годов ХХ века, а также господствующие в то время методологические взгляды на взаимоотношения между компьютерным обеспечением и математикой. Наше изложение в этом параграфе тесно связано с главой 4 второго тома упомянутого выше труда, которая посвящена компьютерным числам и компьютерной арифметике. Методологический подход, описанный в этой главе, к компьютерной арифметике принципиально отличается от нашего подхода. Нам будет удобнее изложить наш подход к компьютерным числам и компьютерной арифметики в дискуссии с материалом, изложенным в указанной главе.

Одним из основных методологических отличий между двумя подходами заключается в отношении к понятию компьютерного числа, который в достаточно явной форме Кнут рассматривает как некоторое приближение к математическому числу, т.е. объект той же природы. Этот подход распространен в современной литературе, и компьютерные числа называют «числами конечной точности». С нашей точки зрения компьютерное число имеет совершенно другую природу, что и сказывается не только на наших выводах, но и позволяет по-другому взглянуть на стоящие перед компьютерной математикой проблемы.

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

Компьютерные числа – это тип чисел, который возник только в середине ХХ века и является сегодня одним из самых распространенных типов чисел. Компьютерные числа бывают двух типов.

Под компьютерным числом первого типа будем понимать пару (e, f ), где e - целое положительное или отрицательное число в цифровом позиционном представлении по основанию b, а f - целое число в том же цифровом представлении, что и e, причем общее количество цифр в обоих числах не превышает числа p. Величина числа p постоянна и зависит только от типа компьютера. Каждому компьютерному числу (e, f ) можно сопоставить во взимооднозначное соответствие математическое (или прагматическое) число (e, f ) = e. f, где обозначает соответствие, которое назовем каноническим соответствием. Число e называется целой частью компьютерного числа, а f - дробной частью. Компьютерное число первого типа будем также называть компьютерным числом с постоянной точкой.

Под компьютерным числом второго типа будем понимать пару (e, f ), где e - целое число, представленное в цифровом позиционном представлении по основанию b и изменяющееся в соответствующем интервале значений, а f – дробное число со знаком в той же позиционной системе, что и e, причем общее количество цифр в обоих числах не превышает числа p. Обычно предполагается, что f 1. Величина числа p постояна и зависит только от типа компьютера. Каждому компьютерному числу (e, f ) можно сопоставить во однозначное соответствие математическое (прагматическое) число (e, f ) = fb e q, (1) обозначает соответствие, которое назовем каноническим соответствием, q где целое число, называемое избытком и зависимое только от типа компьютера или стандартной программы. Компьютерное число второго типа будем также называть компьютерным числом с переменной точкой.

В современных компьютерах, в основном, оперируют компьютерными числами с переменной точкой. Поэтому мы все наши дальнейшие рассмотрения мы будим проводить над этими числами. Кроме того, для простоты рассуждений мы будем везде предполагать, что b = 2. Это значит, что рассматриваемые ниже компьютерные числа будут являться двоичными числами.

Исходя из приведенных определений, можно сделать ряд важных замечаний. Во первых, каждому компьютерному числу вне зависимости от его типа однозначно соответствует математическое (или прагматическое) число. Легко видеть, что существует только счетное множество компьютерных чисел. Это означает, что множество всех действительных математических чисел естественным образом разбивается на подмножества, таким образом, что каждому числу из одного и того же подмножества математических чисел соответствует одно и то же компьютерное число. Каждое такое подмножество обладает свойством, что разность любых двух математических чисел из этого подмножества по абсолютной величине меньше некоторого фиксированного числа. Величина этого числа зависит только от длины машинных слов, с которыми работает арифметическое устройство компьютера. Величину можно определить как максимальное по модулю число, лежащее в подмножестве, всем числам которого соответствует компьютерный нуль. Очевидно, что подмножество всех математических чисел, соответствующих конкретному компьютерному числу a, можно рассматривать как размытое множество M (a, ). Таким образом, между всеми компьютерными числами и размытыми множествами математических чисел можно установить взаимооднозначное соответствие.

Во-вторых, компьютерные числа – это объекты другой природы, нежели математические числа или прагматические. Они не являются подмножеством множества математических чисел или прагматических. Поэтому между компьютерными и математическими числами может существовать только отношение «соответствия».

Например, в свете сказанного неправочно говорить, что компьютерное число больше некоторого математического числа или является его приближением, а также говорить о точности. В свете сказанного, называть компьютерные числа «числами конечной точности» вряд ли оправдано (68, с. 665).

Большинство ныне применяемых стандартных программ работают почти исключительно с числами с плавающей точкой, которые заданы в специальной форме, называемой нормализованной, т.е. с нормализованными числами. Число с плавающей точкой (e, f ) является нормализованным, либо если наиболее значимая цифра в представлении f отлична от нуля, так что 1 / b f 1, либо если f = 0, а e принимает наименьшую величину. Существующее соглашение между производителями компьютеров предполагает, что входные значения для подпрограмм нормализованы, а результаты всегда нормализуются.

Определим операцию сложения двух компьютерных чисел (eu, f u ) и (ev, f v ). Эту операцию назовем компьютерным сложением и обозначим через. Она определяется следующим образом: предполагая, что eu ev, положим (eu, f u ) (ev, f v ) = (e w, f w ), e e где e w = eu, f w = f u + f v / b u v.

Прежде всего, заметим, что компьютерное сложение отличается, как от математического сложения, так и от прагматического сложения. Легко привести для примера два компьютерных числа (eu, f u ) и (ev, f v ), для которых выполняется неравенство ((eu, f u ) (ev, f v )) f u b eu q + f v b ev q, где - каноническое соответствие между компьютерными числами и математическими (прагматическими) числами. Это означает, что каноническое соответствие между компьютерными числами и математическими числами не распространяется на операцию сложения этих чисел. Другими словами, множество всех компьютерных чисел, рассматриваемое вместе с операцией сложения, принципиально отличается как математическая (алгебраическая) структура от множества математических чисел с операцией сложения.

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

(eu, f u ) (ev, f v ) = (ev, f v ) (eu, f u ), но не является ассоциативной операцией, т.е.

(eu, f u ) (( ev, f v ) (e z, f z )) (( eu, f u ) (ev, f v )) (e z, f z ).

Этим операция сложения компьютерных чисел отличается от операции сложения математических или прагматических чисел.

В связи с этим, трудно согласиться со следующим утверждением Д. Кнута (45, с.250):

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

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

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

Аналогично определим операцию компьютерного вычитания. Под компьютерным вычитанием понимается операция, которую обозначим через и которая ставит в соотвествие двум компьютерным числам (eu, f u ) и (ev, f v ) компьютерное число (e w, f w ) следующим образом: предполагая, что eu ev, положим ( eu, f u ) ( e v, f v ) = ( e w, f w ), eu ev где e w = eu, f w = f u f v / b. Очевидно, что эта операция не является коммутативной.

Легко привести для примера два компьютерных числа (eu, f u ) и (ev, f v ), для которых выполняется неравенство ((eu, f u ) (ev, f v )) f u b eu q f v b ev q, где - каноническое соответствие между компьютерными числами и математическими (прагматическими) числами. Это означает, что каноническое соответствие между компьютерными числами и математическими числами также не распространяется на операцию вычитания этих чисел.

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

Под компьютерным умножением понимается операция, которую обозначим через и которая ставит в соотвествие двум компьютерным числам (eu, f u ) и (ev, f v ) компьютерное число (e w, f w ) следующим образом: положим (eu, f u ) (ev, f v ) = (e w, f w ), где e w = eu + ev q, f w = f u f v. Так как количество цифр, которые употребляются в записи любого компьютерного числа ограничено сверху числом p, то операция умножения f u f v происходит с округлением.

Легко привести для примера два компьютерных числа (eu, f u ) и (ev, f v ), для которых выполняется неравенство ((eu, f u ) (ev, f v )) f u b eu q f v b ev q, (2) где - каноническое соответствие между компьютерными числами и математическими (прагматическими) числами. Основная причина отличия между правой и левой частью из (2) заключается в округлении результата умножения. Это означает, что каноническое соответствие между компьютерными числами и математическими числами также не распространяется на операцию умножения этих чисел.

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

(eu, f u ) (ev, f v ) = (ev, f v ) (eu, f u ), но не является ассоциативной операцией, т.е.

(eu, f u ) (( ev, f v ) (e z, f z )) (( eu, f u ) (ev, f v )) (e z, f z ).

Кроме того, не имеет место и дистрибутивность компьютерных сложения и умножения, т.е.

(( eu, f u ) (ev, f v )) (e z, f z ) (eu, f u ) (e z, f z ) (ev, f v ) (e z, f z ).

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

Под компьютерным делением понимается операция, которую обозначим через / и которая ставит в соотвествие двум компьютерным числам (eu, f u ) и (ev, f v ) компьютерное число (e w, f w ) следующим образом: положим (eu, f u ) /( ev, f v ) = (e w, f w ), где ew = eu + ev q + 1, f w = (b f u ) : f v. Так как количество цифр, которые употребляются в записи любого компьютерного числа ограничено сверху числом p, то операция деления f u / f v происходит с округлением.

Легко привести для примера два компьютерных числа (eu, f u ) и (ev, f v ), для которых выполняется неравенство ((eu, f u ) /(ev, f v )) f u b eu q : f v b ev q, (3) - каноническое соответствие между компьютерными числами и математическими где (прагматическими) числами. Основная причина отличия между правой и левой частью из (3) заключается в округлении результата деления. Это означает, что каноническое соответствие между компьютерными числами и математическими числами также не распространяется на операцию деление этих чисел.

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

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

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

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

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

«Другой впечатляющий пример нарушения законов традиционной алгебры при работе с числами с плавающей точкой – невыполнение фундаментального неравенства Коши ( x12 +... + x n )( y12 +... + y n ) ( x1 y1 +... + x n y n ) 2.

2 … Программисты – новички имеют привычку использовать для программы вычисления среднего квадратичного отклонения для ряда наблюдений формулу из справочника = (n x k ( x k ) 2 ) / n( n 1) 1k n 1k n и часто при выполнении программы «нарываются» на попытку извлечения квадратного корня из отрицательного числа!» (Д. Кнут, 45, с.267-268).

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

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

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

(Д. Кнут, 45, с.258).

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

Рассмотрение вопроса о доверии к полученным с помощью компьютеров численным результатам является сложным. Стандартный подход к этой проблеме как теории ошибок вычислений, который принят в современной литературе по вычислительной математике, заключается в попытках получить абстрактные оценки возможных погрешностей при выполнении операций. В этом случае путь к оценке точности вычислений заключается в попытках перейти от оценки точности отдельных арифметических операций к точности некоторой совокупности арифметических операций. Другими словами, в основе современного подхода лежит понятия «точность вычисления», «погрешность вычислений» и т.п. Так обычно под «точным» или «правильным» результатом понимается гипотетический или негипотетический результат, получаемый при выполнении аналогичных вычислений над математическими числами. Сама постановка проблемы, в формулировке которой участвует термин «точность», на наш взгляд, является не совсем корректной, ибо она предполагает, во-первых, что существует объект, с которым сравнивается результат вычислений, а, во-вторых, оба объекта сравнения имеют одну и ту же природу. Однако такой подход вызывает определенные возражения.

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

Сложность проблем, стоящих перед компьютерной математикой, хорошо иллюстрируется следующим экспериментом.

Пусть дана система из n линейных уравнений от n переменных. Предположим, что последнее уравнение представляет собой линейную комбинацию всех других уравнений этой системы. Из теории следует, что матрица этой системы A уравнений не является обратимой матрицей и ее определитель det A равен нулю. Проверим выполнение теоретического результата решением такой системы с помощью широко распространенной программы Excel.

Эксперимент 1. Построим квадратную матрицу размера n n следующим путем.

Случайным образом, т.е. с помощью случайных чисел, заключенных между 0 и 1, выберем n 1 строку. В качестве n -ой строки возьмем сумму n 1 строк, деленных на n 1.

Эксперимент проводился для n = 10, 20, 30, 40, 50, 60, 70, причем для каждого размера матрицы проводилась серия из 100 расчетов. Рассчитать определители матриц при n стандартным алгоритмом из Excel не удалось. Для каждого размера матрицы мы рассчитывали серию по 100 определителей случайно построенных матриц. Каждой серии из 100 вычисленных определителей мы поставим в соответствие средний десятичный порядок значений определителя в каждой серии. Результаты получились следующие: при n = 10 средний порядок определителей равен Е-09, при n = 20 – Е-08, при n = 30 – Е-06, при n = 40 – Е-04, при n = 50 – Е+00, при n = 60 – Е+03, при n = 70 – Е+07.

Эксперимент показал, что, во-первых, вычисленные с помощью стандартной подпрограммы определители всех матриц, индуцированных в процессе эксперимента, были отличны от нуля. Легко видеть, что, если мы бы вычисляли значения этих определителей на основе самого определения и свойств определителя, то результат был совершенно другой, т.е. все построенные указанным способом определители равнялись нулю. Это означает, что рассматривая один и тот же определитель в рамках прагматической математики и компьютерной математики, мы имеем совершенно разные объекты. Напомним, что при рассмотрении одного и того же определителя в рамках теоретической математики и прагматической математики получаются разные результаты, если среди элементов определителя встречаются математические числа. Следовательно, такие важные математические понятия, связанные с понятием линейной зависимости векторов, нельзя адекватно перенести в прагматическую и компьютерную математики. В частности, вся математическая теория линейных уравнений не имеет никакой интерпретации ни в рамках прагматической математики, ни в рамках компьютерной.

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

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

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

Однако этот путь до сих пор не привел к нетривиальным результатам. Свидетельство этому опять можно найти в широко цитируемой здесь книге Кнута (45, с. 260-295).

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

Округленные числа всегда лгут.

Самюэль Джонсон (1750) Вычисления над числами в формате с плавающей точкой неточны по самой своей природе, и программисту нетрудно столь неудачно организовать их выполнение, что полученные результаты будут почти полностью состоять из «шума». Одна из главных проблем численного анализа состоит в точности результатов тех или иных численных методов;

сюда относится и проблема «степени доверия»;

мы не знаем, насколько правильны результаты вычислений на компьютере. Пользователи-новички решают эту проблему, доверяя компьютеру, как непогрешимому авторитету;

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

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

Д. Кнут 10.3. Компьютерная математика и моделирование.

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

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

Заключительным аккордом является принятие решения о том, являются ли полученные числа решением задачи. Таким образом, процесс решения распадается на ряд подпроцессов.

Важно отметить, что все эти этапы являются взаимосвязанными;

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

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

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

Здесь рассматриваются вопросы, связанные со сходимостью этих методов, с оценками точности решения задачи (естественно, в рамках теоретической математики), с оценками сложности алгоритмов и т.п. Все исследования в этом направлении проводятся, а их результаты излагаются на языке теоретической математики. Для того, чтобы описать сам процесс вычисления с помощью конкретных формул, необходимо обратиться к прагматическим математическим моделям, в которых используется язык, существенно отличающийся от языка теоретической математики. К сожалению, рассмотрению этого процесса в специальной литературе практически не уделено места. Ученые в области численного решения математических задач обычно не разделяют между собой программную модель и модель на компьютерном языке при процессе вычисления, не учитывают влияние процессов компиляции или интерпретация на этот процесс. Проблемы так называемой «вычислительной точности» их мало волнуют.

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

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

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

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

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

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


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

Пример 1. Рассмотрим задачу численного решения нелинейного уравнения f ( x) = 0 (4) как процесс моделирования. Глобальной целью в этом случае является нахождение хотя бы одного такого конкретного числа x 0, который являлся бы корнем исследуемого уравнения. Глобальным критерием достижения цели является обращение в тождество уравнения при подстановке найденного числа x 0, т.е.

f ( x0 ) = 0 (5) Этот критерий, очевидно, является эффективным, ибо он для любого числа позволяет однозначно определить, является ли это число корнем исследуемого уравнения. Так как результат любого численного решения алгебраического уравнения представляет собой в общем случае набор прагматических или реально существующих математических чисел, то при такой постановке задачи предполагается, что алгебраическое уравнение имеет хотя бы один корень, являющийся реально существуствующим числом. Однако не существует такого математической теоремы, утверждающей, что конкретно заданное уравнение обладает реально существующим математическим корнем. Поэтому на практике глобальной целью является нахождение приближенного значения корня уравнения (4). Но тогда глобальный критерий выглядит обычно иначе f ( x 0 ), (6) где - положительное число, которое задается исследователем, причем его значение может изменяться в процессе моделирования. Очевидно, что и в этом случае измененный критерий является эффективным.

Пример 2. Рассмотрим задачу нахождения численного значения f ( x0 ) функции f ( x ) в точке x = x 0 как процесс моделирования. Эта задача принадлежит к одному из типов задач, которые широко распространены в математике. Естественно, сформулировать глобальную цель, совпадающую с формулировкой самой задачи. Однако здесь мы сталкиваемся с тем, что указанная задача может имееть решение только в рамках теоретической математики. Подобная ситуация возникает тогда, когда f ( x 0 ) является математическим числом, которому нельзя канонически поставить в соответствии прагматическое число, т.е. реально несуществующим числом. Это означает, что так сформулированная задача не имеет решения в рамках прагматической математики. Для того, чтобы задача имела решение, ее обычно формулируют следующим образом: найти f ( x ). В этом случае в вычислительной приближенное значение f ( x 0 ) функции теоретической математике глобальная цель формулируется следующим образом: найти реально существующее значение f ( x 0 ), удовлетворяющее неравенству f ( x ) f ( x ). (7) 0 Однако на практике мы не можем использовать этот критерий, так как в нем неизвестна величина f ( x ), т.е. его нельзя использовать в качестве глобального критерия.

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

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

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

Пример 3. Рассмотрим задачу численного решения системы линейных уравнений XA = B, (8) - квадратная матрица n n и где X = ( x1, x 2,..., x n ) - вектор неизвестных, A = a ij B = (b1, b2,..., b n ) - конкретно заданный вектор. По условию задачи, все числа a ij и bi реально существующие математические числа. В этом случае глобальная цель заключается в поиске приближенного численного решения X 0 = ( x 01, x 02,..., x 0 n ) системы (8), который легко сформулировать, положив b b, (9) i i - положительное число, величину которого выбирает исследователь, и где X 0 A = B = (b1, b2,..., bn ). Очевидно, что этот критерий является эффективным и не зависит от метода решения задачи. Но тогда и цель является эффективно достижимой.

Пример 4. Рассмотрим задачу численного решения обыкновенного дифференциального уравнения от одного переменного при определенных начальных условиях (задача Коши). В этом случае, согласно интуитивному содержанию, глобальной целью исследования обычно объявляется нахождение численного решения этого уравнения. Однако с чисто формальной точки зрения нет четкого определения того объекта, который понимается под словами «численное решение дифференциального уравнения».

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

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

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

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

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

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

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

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

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


Существование эффективного частного критерия не гарантирует существования глобального эффективного критерия. Более того, наличие эффективного метода решения теоретической задачи не дает никакой гарантии того, что можно найти численное решение задачи.

Сам процесс исследования теоретической модели состоит из трех этапов.

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

Задачу решения нелинейного уравнения (пример 1) можно рассматривать двояко: или как задачу нахождения корней уравнения (4), или как задачу нахождения неподвижной точки для уравнения F ( x) = x, где F ( x ) = f ( x ) + x. В теоретической вычислительной математике существует множество алгоритмов, решающих задачу в той или иной постановке. Задача вычисления значения функции в конкретной точке (пример 2) обычно решается с помощью разложения этой функции в бесконечный степенной ряд в окрестности этой точки, хотя имеются и другие подходы, которые зависят от объема начальной информации, используемой при решении задачи. Задача решения системы линейных уравнений (пример 3) может быть сведена к вычислению набора определителей специального вида. Решение обыкновенного дифференциального уравнения в рамках задачи Коши (пример 4) может быть сведено к набору рекуррентных соотношений.

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

Методы решения нелинейных уравнений (пример 1) в своей основе являются итеративными (метод простых итераций, метод Ньютона, метод секущих и т.п.). Это означает, в рамках этих методов строится последовательность чисел, относительно которой при определенных условиях доказывается, что эта последовательность сходится к корню уравнения. Обычно все известные методы решения нелинейных уравнений являются точными только при выполнении определенных условий. Конкретная проверка этих условий на практике часто или невозможна, либо представляет собой не менее сложную задачу, нежели решение самой первоначальной задачи. В подтверждение сказанному можно сказать, что до сих пор не найден конструктивный метод, позволяющий найти действительный корень в случае его существования.

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

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

Для решения задачи Коши (пример 4) существует целый ряд методов (например, метод Эйлера, методы Рунге-Кутта, методы Адамса, метод последовательных приближений Пикара), которые позволяют найти приближенные значения ряда точек на функции, являющейся решением задачи Коши. Только при очень жестких условиях, накладываемых на обыкновенное дифференциальное уравнение, удается доказать, что некий метод решения в пределе позволяет прийти к решению задачи. Обычно выполнение этих условий при решении практических задач невозможно проверить.

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

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

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

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

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

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

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

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

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

Проиллюстрируем сказанное на приведенных выше примерах.

Пусть для нахождения приближенного значения корня нелинейного уравнения (5) выбран метод Ньютона (пример 1). Все другие методы численного решения нелинейных уравнений рассматриваются аналогично. В основе этого метода лежит рекуррентное соотношение, связывающее последующее приближение корня с предыдущим.

Рекуррентное соотношение можно рассматривать как бесконечный набор математических формул, из которого выбирается конечный набор. Так как в каждой формуле участвуют только реально существующие математические числа и арифметические операции, то, как мы уже неоднократно отмечали, ее можно рассматривать и как прагматическую формулу, используя каноническое соответствие. В результате вычисления прагматической формулы получается последовательность прагматических чисел. Эту последовательность вычислений можно оборвать, например, на любом первом члене, для которого выволняется критерий (6). В этом случае частный критерий в этом случае совпадает с глобальным критерием. Соединяя в один процесс частный критерий и выбранную формулу, мы уже получаем вычислительный прагматический алгоритм решения поставленной задачи. Здесь важно отметить, что для нахождения вычислительного прагматического алгоритма мы были вынуждены произвести достаточно много дополнительных вычислений. Результаты этих вычислений и служат необходимым набором информации, с помощью которой и строится алгоритм.

Для нахождения приближенного значения f ( x 0 ) функции f ( x ) в точке x =x (пример 2) используем конструктивный метод, основанный на разложении этой функции в сходящийся в рассматриваемой точке степенной ряд. В этом случае теоретический вычислительный алгоритм, как мы уже отмечали выше, заключается в вычислении набора частный сумм степенного ряда. Каждая частная сумма ряда представляет собой математическую формулу, в которой участвуют только арифметические операции.

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

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

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

Второй случай возникает, когда нельзя указать требуемой частной суммы. Тогда частный критерий можно попытаться построить на том или ином признаке сходимости ряда. Например, в качестве признака сходимости можно взять требование. Пусть y1, y 2,..., y n - набор вычисленных частных сумм. Тогда в качестве частного критерия можно выбрать следующее неравенство y k y l, (10) где k, l N, 0, N - некоторое целое положительное число, что выполняется неравенство (10).

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

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

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

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

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

Первая часть связана с введением конкретных числовых данных в память компьютера.

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

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

Поэтому сформулировать частный критерий в этой ситуации достаточно трудно.

Основная причина этого заключается в том, что не найдены соответствующие язык и методология.

Второй частью программы, существенно влияющей на решение задачи, является описание на языке программирования алгоритма решения вычислительной задачи. Тогда частной целью этой части программной модели является адекватный «перевод»

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

При такой формулировке частной цели возникает сразу несколько принципиальных вопросов. Первым вопросом является вопрос о существовании адекватного «перевода»

вычислительного алгоритма в принципе. Второй вопрос состоит в существовании единственного адекватного «первода», а третий – в существовании способа определения того, что записанный в программе алгоритм является адекватным «переводом»

прагматического вычислительного алгоритма.

Для ответа на первый вопрос, прежде всего, необходимо определить, что понимается под термином «адекватный перевод». Естественно предполагать, что программа содержит «адекватный перевод» прагматического вычислительного алгоритма, если при любом одинаковом наборе данных результаты вычислений, проведенных двумя путями: с помощью программы и в рамках прагматической модели, - совпадают. При такой постановке ответ на этот вопрос будет отрицательным. Отрицательный ответ объясняется тем, что легко привести пример результата сложения двух прагматических чисел, который отличается от результата сложения отвечающих им компьютерных чисел. Это отличие определяется отличием в свойствах между прагматической и компьютерной моделей.

Поэтому изменим наше определение «адекватности перевода» следующим образом:

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

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



Pages:     | 1 |   ...   | 12 | 13 || 15 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.