ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

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

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

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

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

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

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

или, в более общей форме,

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

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

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

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

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

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

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

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

Числ. методы решения дифф. ур-ний составляют важнейший раздел вычисл. математики. Задачи механики, физики и хим. кинетики — это, в подавляющем числе случаев, задачи теории дифф. (иногда интегро-дифф.) ур-ний. Если числ. методы решения обыкновенных дифф. ур-ний начали разрабатываться почти одновременно с возникновением понятия дифф. ур-ний и ведут свое начало от Л. Эйлера (1707—83), то числ. методы решения ур-ний в частных производных, по существу, начали

развиваться только после создания ЭВМ. Причиной этого является т. н. «барьер многомерности» — резкий рост необходимого к-ва арифм. операций с возрастанием числа независимых переменных. Если для решения одномерного (т. е. обыкновенного) дифф. ур-ния с заданной точностью нужно определять решения в узловых точках, то для получения решения с той же точностью для -мерного ур-ния в частных производных потребуется уже узловых точек. Поскольку при числ. решениях дифф. ур-ний часто приходится решать системы линейных алгебр, ур-ний относительно неизвестных значений ф-ции в узловых точках, то это значит, что в одномерном случае необходимо выполнить арифм. операций, а в А-мерном — операций. Практическая невозможность проведения такого рода вычислений «ручным» способом делала бессмысленной разработку числ. методов решения ур-ний в частных производных до появления ЭВМ. Лишь самые элементарные подходы были предложены в «домашинную ару», которые могли применяться только для простейших, как правило, линейных задач на ур-ния в частных производных.

В общем можно отметить два главных подхода к решению дифф. ур-ний: 1) представление решения в виде рядов по некоторой полной системе ф-ций (обычно ортогональной) и нахождение коэфф. этих рядов и 2) замена производных их конечноразностными приближениями (или интегралов — конечными суммами). Первый подход имеет ограниченное применение — он эффективен только в применении к линейным ур-ниям или в некоторых методах последовательных приближений, когда на каждой итерации решается линейное ур-ние. Именно этот подход чаще всего использовали до создания ЭВМ. В наст, время наибольшее применение имеют конечноразностные методы (в широком смысле этого слова); метод прямых или метод интегр. соотношений и метод характеристик мы также относим к конечноразностным. Важнейшей проблемой конечноразностных методов является устойчивость вычисл. процесса.

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

или

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

Общее решение первой формы

второй формы

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

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

где Ф — некоторый оператор, содержащий дифференцирование лдшь по пространственным переменным, можно аппроксимировать конечноразностной формой:

и т. о. свести задачу определения искомой ф-ции (системы ф-ций — в общем случае) в момент по известным ее значениям в момент t к элементарным вычислениям. Но такой метод в общем случае является неустойчивым пли устойчивым лишь при очень малых значениях Однако и в последнем случае, когда устойчивости все же можно достигнуть, общий объем вычислений превосходит практические возможности. Для корректно поставленных задач (см. Некорректно поставленные задачи) всегда можно добиться устойчивости вычисл. процесса применением неявных схем

при этом существенно в неявной форме записывать старшие производные по координатам.

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

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

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

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

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

Лит.: Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М.- Л., 1963 [библиогр. с. 677—734]; Ремез Е. Я. Основы численных методов чебышевского приближения. К., 1969 [библиогр. с. 613—623]; Самарский А. А. Введение в теорию разностных схем. М., 1971 [библиогр. с. 538—550]; Моисеев Н. Н. Численные методы в теории оптимальных систем. М., 1971; Уиттекер Э., Робинсон Г. Математическая обработка результатов наблюдений. Пер. с англ. Л.- М., 1935; Уилкинсон Дж. X. Алгебраическая проблема собственных значений. Пер. с англ. М.. 1970 [библиогр. с. 559 — 564].

А. А. Дородницын.