Вычислительная математика

Вавилонская глиняная табличка примерно 1800—1600 года до н. э. с современными аннотациями. Надписи на табличке дают приближение значения квадратного корня из 2 как суммы четырёх шестидесятеричных чисел^[1]: ${\sqrt {2}}\approx 1+{\frac {24}{60}}+{\frac {51}{60^{2}}}+{\frac {10}{60^{3}}}\approx 1{,}41421296$

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

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

История

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

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

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

Основные направления

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

Анализ выбранных математических моделей для поставленной задачи начинается с анализа и обработки входной информации, что очень важно для более точных входных данных. Для такой обработки зачастую применяются методы математической статистики. Следующим шагом является численное решение математических задач и анализ результатов вычислений. Степень достоверности результатов анализа должна соответствовать точности входных данных. Появление более точных входных данных может потребовать усовершенствования построенной модели или даже её замены^[2].

Методы и алгоритмы решения типовых математических задач с применением вычислительной техники носят название численных методов. К типовым задачам относят^[2]:

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

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

Постоянно увеличивающийся круг типовых задач и рост числа пользователей определили повышение требований к автоматизации. В условиях, когда знание конкретных численных методов является несущественным для пользователя, возрастают требования к стандартным программам решения. С их использованием не требуется программирование методов решения, а достаточно задать исходную информацию^[2].

Особенности представления чисел в компьютере

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

Программное обеспечение

Алгоритмы решения множества стандартных задач вычислительной математики реализованы на различных языках программирования. Чаще всего для этих целей используются языки Julia, Фортран и C, библиотеки для которых можно найти в репозитории Netlib^[англ.]. Кроме того, большую популярность имеют коммерческие библиотеки IMSL и NAG^[англ.], а также свободная GNU Scientific Library.

Программные пакеты MATLAB, Mathematica, Maple, S-PLUS^[англ.], LabVIEW и IDL^[англ.], а также их свободные альтернативы FreeMat, Scilab, GNU Octave (похожа на Matlab), IT++^[англ.] (библиотека C++), R (похож на S-PLUS) имеет различные численные методы, а также средства для визуализации и отображения результатов.

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

Вычислительные методы

Вычислительные (численные) методы — это методы решения математических задач в численном виде^[3]

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

Основами для вычислительных методов являются:

решение систем линейных уравнений;
интерполирование и приближённое вычисление функций;
численное интегрирование;
численное решение системы нелинейных уравнений;
численное решение обыкновенных дифференциальных уравнений;
численное решение уравнений в частных производных (уравнений математической физики);
решение задач оптимизации.

Система линейных алгебраических уравнений

Система m линейных алгебраических уравнений с n неизвестными (или, линейная система, также употребляется аббревиатура СЛА́У) в линейной алгебре — это система уравнений вида

{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}\\\dots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}=b_{m}\\\end{cases}}

(1)

Система линейных уравнений от трёх переменных определяет набор плоскостей. Точка пересечения является решением.

Здесь $m$ — количество уравнений, а $n$ — количество неизвестных. x₁, x₂, …, x_n — неизвестные, которые надо определить. a₁₁, a₁₂, …, a_mn — коэффициенты системы — и b₁, b₂, … b_m — свободные члены — предполагаются известными^[4]. Индексы коэффициентов (a_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно^[5].

Система (1) называется однородной, если все её свободные члены равны нулю (b₁ = b₂ = … = b_m = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел c₁, c₂, …, c_n, таких что подстановка каждого c_i вместо x_i в систему (1) обращает все её уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (1) может иметь одно или более решений.

Решения c₁⁽¹⁾, c₂⁽¹⁾, …, c_n⁽¹⁾ и c₁⁽²⁾, c₂⁽²⁾, …, c_n⁽²⁾ совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c₁⁽¹⁾ = c₁⁽²⁾, c₂⁽¹⁾ = c₂⁽²⁾, …, c_n⁽¹⁾ = c_n⁽²⁾.

Совместная система вида (1) называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой. Если уравнений больше, чем неизвестных, она называется переопределённой.

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

Прямые методы

Метод Гаусса
Метод Гаусса — Жордана
Метод Крамера
Матричный метод
Метод прогонки (для трёхдиагональных матриц)
Разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц)
Метод вращений^[6]

Итерационные методы

Интерполяция

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

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

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

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина и теорема Марцинкевича^[англ.], являющиеся основой для множества других работ.

Способы интерполяции

Интерполяция методом ближайшего соседа.
Линейная интерполяция
Интерполяционная формула Ньютона
Метод конечных разностей
ИМН-1 и ИМН-2
Многочлен Лагранжа (интерполяционный многочлен)
По схеме Эйткена
Сплайн-функция
Кубический сплайн
Полином Лагранжа
Обратное интерполирование по формуле Ньютона
Обратное интерполирование по формуле Гаусса
Билинейная интерполяция
Бикубическая интерполяция
Рациональная интерполяция
Тригонометрическая интерполяция
Аппроксимация — методы построения приближённых кривых
Экстраполяция — методы нахождения точек за пределами заданного интервала (продление кривой)

Аппроксимация

Аппроксима́ция, или приближе́ние — научный метод, состоящий в замене одних объектов другими, в том или ином смысле близкими к исходным, но более простыми.

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

Экстраполяция

Экстраполя́ция, экстраполи́рование (от лат. extrā — вне, снаружи, за, кроме и лат. polire — приглаживаю, выправляю, изменяю, меняю^[7]) — особый тип аппроксимации, при котором функция аппроксимируется вне заданного интервала, а не между заданными значениями.

Иными словами, экстраполяция — приближённое определение значений функции $f(x)$ в точках $x$ , лежащих вне отрезка $[x_{0},x_{n}]$ , по её значениям в точках $x_{0}<x_{1}<...<x_{n}$ .

Методы экстраполяции во многих случаях сходны с методами интерполяции. Наиболее распространённым методом экстраполяции является полиномиальная экстраполяция, при которой в качестве значения $f(x)$ в точке $x$ берётся значение многочлена $P_{n}(x)$ степени $n$ , принимающего в $n+1$ точке $x_{n}$ заданные значения $y_{i}=f(x_{i})$ . Для полиномиальной экстраполяции пользуются интерполяционными формулами.

Численное интегрирование

Численное интегрирование — вычисление значения определённого интеграла (как правило, приближённое). Под численным интегрированием понимают набор численных методов отыскания значения определённого интеграла.

Численное интегрирование применяется, когда:

Сама подынтегральная функция не задана аналитически. Например, она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки.
Аналитическое представление подынтегральной функции известно, но её первообразная не выражается через аналитические функции. Например, $f(x)=\exp(-x^{2})$ .

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

Одномерный случай

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

I\approx \sum _{i=1}^{n}w_{i}\,f(x_{i}),

где $n$ — число точек, в которых вычисляется значение подынтегральной функции. Точки $x_{i}$ называются узлами метода, числа $w_{i}$ — весами узлов. При замене подынтегральной функции на полином нулевой, первой и второй степени получаются соответственно методы прямоугольников, трапеций и парабол (Симпсона). Часто формулы для оценки значения интеграла называют квадратурными формулами.

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

\int \limits _{a}^{b}f(x)\,dx=\sum _{i=0}^{n}H_{i}\,f(x_{i})+r_{n}(f),

где числа $H_{i}$ называются коэффициентами Котеса и вычисляются как интегралы от соответствующих многочленов, стоящих в исходном интерполяционном многочлене для подынтегральной функции при значении функции в узле $x_{i}=a+ih$ ( $h=(b-a)/n$ — шаг сетки; $n$ — число узлов сетки, а индекс узлов $i=0\ldots n$ ). Слагаемое $r_{n}(f)$ — погрешность метода, которая может быть найдена разными способами. Для нечетных $n\geqslant 1$ погрешность может быть найдена интегрированием погрешности интерполяционного полинома подынтегральной функции.

Частными случаями формул Котеса являются: формулы прямоугольников (n=0), формулы трапеций (n=1), формула Симпсона (n=2), формула Ньютона (n=3) и т. д.

Дифференциальное уравнение в частных производных

Дифференциальное уравнение в частных производных (частные случаи также известны как уравнения математической физики, УМФ) — дифференциальное уравнение, содержащее неизвестные функции нескольких переменных и их частные производные.

Первое уравнение в частных производных историки обнаружили в статьях Эйлера по теории поверхностей, относящихся к 1734—1735 годам (опубликованы в 1740 году). В современных обозначениях оно имело вид:

{\frac {\partial z}{\partial x}}=f(x,y)

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

Второй этап в развитии данной темы можно датировать 1770—1830 годами. К этому периоду относятся глубокие исследования Лагранжа, Коши и Якоби. Первые систематические исследования уравнений в частных производных начал проводить Фурье. Он применил новый метод к решению уравнения струны — метод разделения переменных, позднее получивший его имя.

Новый общий подход к теме, основанный на теории непрерывных групп преобразований, предложил в 1870-х годах Софус Ли.

Существует два вида методов решения данного типа уравнений:

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

Математическая статистика

Математическая статистика — раздел математики, разрабатывающий методы регистрации, описания и анализа данных наблюдений и экспериментов с целью построения вероятностных моделей массовых случайных явлений^[8]. В зависимости от математической природы конкретных результатов наблюдений статистика математическая делится на статистику чисел, многомерный статистический анализ, анализ функций (процессов) и временных рядов, статистику объектов нечисловой природы.

Выделяют описательную статистику, теорию оценивания и теорию проверки гипотез.

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

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

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

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

См. также

Примечания

↑ Duncan J. Melville, Photograph, illustration, and description of the ${\sqrt {2}}$ tablet from the Yale Babylonian Collection, Mesopotamian Mathematics, St. Lawrence University, 18 September 2006. (неопр.) Дата обращения: 18 марта 2012. Архивировано 13 августа 2012 года.
↑ ¹ ² ³ ⁴ ⁵ Вычислительная математика / А. Н. Тихонов // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
↑ Муха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010.- 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92
↑ В рамках данной статьи коэффициенты системы, свободные члены и неизвестные считаются действительными числами, хотя они могут быть комплексными или даже сложными математическими объектами с условием, что для них определены операции умножения и сложения.
↑ Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.
↑ Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — С. 80—84. — 840 с. — ISBN 9785060061239.
↑ Extrapolation: ethymology Архивная копия от 17 июня 2013 на Wayback Machine
Interpolate: ethymology
↑ Вероятностные разделы математики / Под ред. Ю. Д. Максимова. — СПб.: «Иван Фёдоров», 2001. — С. 400. — 592 с. — ISBN 5-81940-050-X.

Литература

Вычислительная математика / Н. С. Бахвалов // Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов. — М. : Большая российская энциклопедия, 2004—2017.
Вычислительная математика / А. Н. Тихонов // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
Марчук Г. И. Методы вычислительной математики. — Новосибирск: Наука, 1973.
Бабенко К. И. Основы численного анализа. — М.: Наука, 1986.
Бахвалов Н. С. Численные методы. 3-е изд. — М., 2003.
Воеводин В. В. Математические основы параллельных вычислений. — М.: Изд-во МГУ, 1991. — 345 с.
Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — 608 с.
Демидович Б. П., Марон И. А. Основы вычислительной математики. — 2-е изд. — М.: Государственное издательство физико-математической литературы, 1963.
Дьяченко В. Ф. Основные понятия вычислительной математики. — М.: Наука, 1972.
Вычислительные методы для анализа моделей сложных динамических систем : Учеб. пособие для студентов вузов по напр. «Прикладные математика и физика» / А. И. Лобанов, И. Б. Петров; М-во образования Рос. Федерации. МФТИ (гос. ун-т). — М. : МФТИ, 2000. — 21 см.
- Ч. 1. — 2000. — 168 с. : ил., табл.; ISBN 5-7417-0149-3
- Ч. 2. — 2002. — 154 с. : ил.; ISBN 5-7417-0199-X
Вычислительная математика : курс лекций / А. И. Лобанов, И. Б. Петров. — Москва : Физматкнига, 2021. — 475 с. : ил.; 22 см. — (Физтеховские курсы).; ISBN 978-5-89155-341-5 : 300 экз.
Канторович Л. В., Крылов В. И. Приближённые методы высшего анализа. — М.—Л.: ГИИТЛ, 1949.

Ссылки

[1] Duncan J. Melville, Photograph, illustration, and description of the ${\sqrt {2}}$ tablet from the Yale Babylonian Collection, Mesopotamian Mathematics, St. Lawrence University, 18 September 2006. (неопр.) Дата обращения: 18 марта 2012. Архивировано 13 августа 2012 года.

[bse-2] ¹ ² ³ ⁴ ⁵ Вычислительная математика / А. Н. Тихонов // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

[3] Муха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010.- 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92

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

[ilin-5] Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.

[6] Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — С. 80—84. — 840 с. — ISBN 9785060061239.

[onlineethymology-7] Extrapolation: ethymology Архивная копия от 17 июня 2013 на Wayback Machine
Interpolate: ethymology

[8] Вероятностные разделы математики / Под ред. Ю. Д. Максимова. — СПб.: «Иван Фёдоров», 2001. — С. 400. — 592 с. — ISBN 5-81940-050-X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]