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

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

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

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

История[править | править вики-текст]

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

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

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

Основные направления[править | править вики-текст]

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

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

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

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

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

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

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

Программное обеспечение[править | править вики-текст]

Численное моделирование аварии автомобиля

Алгоритмы решения множества стандартных задач вычислительной математики реализованы на различных языках программирования. Чаще всего для этих целей используются языки Фортран и 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 — количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными[4]. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно[5].

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

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

Решение системы (1) — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все её уравнения в тождества.

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

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

Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

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

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

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

Интерполяция[править | править вики-текст]

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

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

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

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ.

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

Аппроксимация[править | править вики-текст]

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

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

Экстраполяция[править | править вики-текст]

Экстраполя́ция, экстраполи́рование (от лат. 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). Для полиномиальной экстраполяции пользуются интерполяционными формулами.

Численное интегрирование[править | править вики-текст]

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

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

  1. Сама подынтегральная функция не задана аналитически. Например, она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки.
  2. Аналитическое представление подынтегральной функции известно, но её первообразная не выражается через аналитические функции. Например, 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 + i h (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]. В зависимости от математической природы конкретных результатов наблюдений статистика математическая делится на статистику чисел, многомерный статистический анализ, анализ функций (процессов) и временных рядов, статистику объектов нечисловой природы.

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

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

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

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Бабенко К. И. Основы численного анализа. — М.: Наука, 1986.
  • Воеводин В. В. Математические основы параллельных вычислений. — М.: Изд-во МГУ, 1991. — 345 с.
  • Бахвалов Н. С. Численные методы. 3-е изд. — М, 2003.
  • Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — 608 с.
  • Демидович Б. П., Марон И. А. Основы вычислительной математики. — 2-е изд. — М.: Государственное издательство физико-математической литературы, 1963.
  • Канторович Л. В., Крылов В. И.  Приближённые методы высшего анализа. — М.—Л.: ГИИТЛ, 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.
  2. 1 2 3 4 5 Вычислительная математика — статья из Большой советской энциклопедии. А. Н. Тихонов
  3. Муха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010.- 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92
  4. В рамках данной статьи коэффициенты системы, свободные члены и неизвестные считаются действительными числами, хотя они могут быть комплексными или даже сложными математическими объектами с условием, что для них определены операции умножения и сложения.
  5. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.
  6. Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — С. 80—84. — 840 с. — ISBN 9785060061239
  7. Extrapolation: ethymology
    Interpolate: ethymology
  8. Вероятностные разделы математики / Под ред. Ю. Д. Максимова. — Спб.: «Иван Фёдоров», 2001. — С. 400. — 592 с. — ISBN 5-81940-050-X

Ссылки[править | править вики-текст]