Численный анализ — это изучение алгоритмов , которые используют численное приближение (в отличие от символьных манипуляций ) для задач математического анализа (в отличие от дискретной математики ). Это изучение численных методов, которые пытаются найти приближенные решения проблем, а не точные. Численный анализ находит применение во всех областях техники и физических наук, а в 21 веке также в естественных и социальных науках, таких как экономика, медицина, бизнес и даже искусство. Текущий рост вычислительной мощности позволил использовать более сложный численный анализ, предоставляя подробные и реалистичные математические модели в науке и технике. Примерами численного анализа являются: обыкновенные дифференциальные уравнения , которые встречаются в небесной механике (предсказание движений планет, звезд и галактик), численная линейная алгебра в анализе данных, [2] [3] [4] и стохастические дифференциальные уравнения и цепи Маркова для моделирования живых клеток в медицине и биологии.
До появления современных компьютеров численные методы часто полагались на формулы ручной интерполяции , используя данные из больших печатных таблиц. С середины 20-го века компьютеры вычисляют требуемые функции вместо этого, но многие из тех же формул продолжают использоваться в программных алгоритмах. [5]
Числовая точка зрения восходит к самым ранним математическим сочинениям. Табличка из Йельской вавилонской коллекции ( YBC 7289 ) дает шестидесятеричное числовое приближение квадратного корня из 2 , длины диагонали в единичном квадрате .
Численный анализ продолжает эту давнюю традицию: вместо того, чтобы давать точные символьные ответы, переведенные в цифры и применимые только к реальным измерениям, используются приближенные решения в пределах указанных погрешностей.
Общей целью области численного анализа является разработка и анализ методов, позволяющих получить приблизительные, но точные решения для широкого круга сложных задач, многие из которых невозможно решить символически:
Область численного анализа появилась на много столетий раньше изобретения современных компьютеров. Линейная интерполяция использовалась уже более 2000 лет назад. Многие великие математики прошлого были заняты численным анализом, [5] как это очевидно из названий важных алгоритмов, таких как метод Ньютона , интерполяционный полином Лагранжа , исключение Гаусса или метод Эйлера . Истоки современного численного анализа часто связывают со статьей Джона фон Неймана и Германа Голдстайна 1947 года , [7] [8] но другие считают, что современный численный анализ восходит к работе Э. Т. Уиттекера 1912 года. [7]
Для облегчения вычислений вручную были выпущены большие книги с формулами и таблицами данных, такими как точки интерполяции и коэффициенты функций. Используя эти таблицы, часто рассчитанные до 16 знаков после запятой или более для некоторых функций, можно было искать значения, чтобы вставлять их в приведенные формулы и получать очень хорошие числовые оценки некоторых функций. Канонической работой в этой области является публикация NIST под редакцией Абрамовица и Стегана , книга объемом более 1000 страниц с очень большим количеством часто используемых формул и функций и их значений во многих точках. Значения функций больше не очень полезны, когда доступен компьютер, но большой список формул все еще может быть очень удобным.
Механический калькулятор также был разработан как инструмент для ручных вычислений. Эти калькуляторы эволюционировали в электронные компьютеры в 1940-х годах, и тогда было обнаружено, что эти компьютеры также полезны для административных целей. Но изобретение компьютера также повлияло на область численного анализа, [5] поскольку теперь можно было выполнять более длинные и сложные вычисления.
Премия Лесли Фокса по численному анализу была учреждена в 1985 году Институтом математики и ее приложений .
Прямые методы вычисляют решение задачи за конечное число шагов. Эти методы дали бы точный ответ, если бы они были выполнены в арифметике бесконечной точности . Примерами являются исключение Гаусса , метод QR-факторизации для решения систем линейных уравнений и симплексный метод линейного программирования . На практике используется конечная точность , и результатом является приближение истинного решения (предполагая устойчивость ).
В отличие от прямых методов, итерационные методы не должны заканчиваться за конечное число шагов, даже если бы была возможна бесконечная точность. Начиная с начальной догадки, итерационные методы формируют последовательные приближения, которые сходятся к точному решению только в пределе. Тест сходимости, часто включающий остаток , указывается для того, чтобы решить, когда достаточно точное решение (надеюсь) было найдено. Даже используя арифметику бесконечной точности, эти методы не достигли бы решения за конечное число шагов (в общем случае). Примерами являются метод Ньютона, метод бисекции и итерация Якоби . В вычислительной матричной алгебре итерационные методы обычно необходимы для больших задач. [9] [10] [11] [12]
Итерационные методы более распространены, чем прямые методы в численном анализе. Некоторые методы являются прямыми в принципе, но обычно используются так, как будто они таковыми не являются, например GMRES и метод сопряженных градиентов . Для этих методов число шагов, необходимых для получения точного решения, настолько велико, что приближение принимается так же, как и для итерационного метода.
В качестве примера рассмотрим задачу решения
для неизвестной величины x .
Для итерационного метода применим метод деления пополам к f ( x ) = 3 x 3 − 24. Начальные значения: a = 0, b = 3, f ( a ) = −24, f ( b ) = 57.
Из этой таблицы можно сделать вывод, что решение находится между 1,875 и 2,0625. Алгоритм может вернуть любое число в этом диапазоне с ошибкой менее 0,2.
Плохо обусловленная задача: Возьмем функцию f ( x ) = 1/( x − 1) . Обратите внимание, что f (1,1) = 10 и f (1,001) = 1000: изменение x менее чем на 0,1 превращается в изменение f ( x ) почти на 1000. Оценка f ( x ) вблизи x = 1 является плохо обусловленной задачей.
Хорошо обусловленная задача: Напротив, оценка той же функции f ( x ) = 1/( x − 1) вблизи x = 10 является хорошо обусловленной задачей. Например, f (10) = 1/9 ≈ 0,111 и f (11) = 0,1: скромное изменение x приводит к скромному изменению f ( x ).
Более того, непрерывные задачи иногда должны быть заменены дискретной задачей, решение которой, как известно, приближает решение непрерывной задачи; этот процесс называется « дискретизацией ». Например, решение дифференциального уравнения является функцией . Эта функция должна быть представлена конечным количеством данных, например, ее значением в конечном числе точек в ее области определения, даже если эта область является континуумом .
Изучение ошибок является важной частью численного анализа. Существует несколько способов, с помощью которых ошибка может быть внесена в решение задачи.
Ошибки округления возникают из-за того, что невозможно точно представить все действительные числа на машине с конечной памятью (какой является вся практическая цифровая вычислительная машина ).
Ошибки усечения совершаются, когда итерационный метод прекращается или математическая процедура аппроксимируется, и приближенное решение отличается от точного решения. Аналогично, дискретизация вызывает ошибку дискретизации , поскольку решение дискретной задачи не совпадает с решением непрерывной задачи. В приведенном выше примере для вычисления решения после десяти итераций вычисленный корень составляет примерно 1,99. Следовательно, ошибка усечения составляет примерно 0,01.
После возникновения ошибки она распространяется по всему вычислению. Например, операция + на компьютере неточна. Вычисление типа еще более неточно.
Ошибка усечения возникает, когда математическая процедура аппроксимируется. Чтобы точно проинтегрировать функцию, необходимо найти бесконечную сумму областей, но численно можно найти только конечную сумму областей, а значит, и аппроксимацию точного решения. Аналогично, чтобы дифференцировать функцию, дифференциальный элемент стремится к нулю, но численно можно выбрать только ненулевое значение дифференциального элемента.
Алгоритм называется численно устойчивым, если ошибка, независимо от ее причины, не становится намного больше во время вычислений. [13] Это происходит, если задача хорошо обусловлена , то есть решение изменяется лишь на небольшую величину, если данные задачи изменяются на небольшую величину. [13] Напротив, если задача «плохо обусловлена», то любая небольшая ошибка в данных вырастет до большой ошибки. [13] Как исходная задача, так и алгоритм, используемый для ее решения, могут быть хорошо обусловленными или плохо обусловленными, и возможна любая комбинация. Таким образом, алгоритм, решающий хорошо обусловленную задачу, может быть либо численно устойчивым, либо численно неустойчивым. Искусство численного анализа заключается в поиске устойчивого алгоритма для решения хорошо поставленной математической задачи.
Область численного анализа включает в себя множество субдисциплин. Вот некоторые из основных:
Одной из самых простых задач является оценка функции в заданной точке. Самый простой подход, просто подставляя число в формулу, иногда не очень эффективен. Для полиномов лучшим подходом является использование схемы Горнера , поскольку она сокращает необходимое количество умножений и сложений. Как правило, важно оценивать и контролировать ошибки округления, возникающие при использовании арифметики с плавающей точкой .
Интерполяция решает следующую задачу: если дано значение некоторой неизвестной функции в ряде точек, какое значение эта функция имеет в некоторой другой точке между заданными точками?
Экстраполяция очень похожа на интерполяцию, за исключением того, что теперь необходимо найти значение неизвестной функции в точке, которая находится за пределами заданных точек. [14]
Регрессия также похожа, но она учитывает, что данные неточны. Имея некоторые точки и измерение значения некоторой функции в этих точках (с ошибкой), можно найти неизвестную функцию. Метод наименьших квадратов является одним из способов достижения этого.
Другая фундаментальная проблема — вычисление решения некоторого заданного уравнения. Обычно различают два случая, в зависимости от того, является ли уравнение линейным или нет. Например, уравнение является линейным, а не является.
Много усилий было вложено в разработку методов решения систем линейных уравнений . Стандартные прямые методы, т. е. методы, которые используют некоторое разложение матриц , — это исключение Гаусса , LU-разложение , разложение Холецкого для симметричных (или эрмитовых ) и положительно определенных матриц , а также QR-разложение для неквадратных матриц. Итерационные методы, такие как метод Якоби , метод Гаусса–Зейделя , последовательная сверхрелаксация и метод сопряженных градиентов [15] , обычно предпочтительны для больших систем. Общие итерационные методы могут быть разработаны с использованием разбиения матриц .
Алгоритмы поиска корня используются для решения нелинейных уравнений (они так названы, потому что корень функции — это аргумент, для которого функция дает ноль). Если функция дифференцируема и производная известна, то метод Ньютона является популярным выбором. [16] [17] Линеаризация — еще один метод решения нелинейных уравнений.
Несколько важных проблем можно сформулировать в терминах разложений собственных значений или разложений сингулярных значений . Например, алгоритм сжатия спектральных изображений [18] основан на разложении сингулярных значений. Соответствующий инструмент в статистике называется анализом главных компонент .
Задачи оптимизации требуют точки, в которой заданная функция максимизируется (или минимизируется). Часто точка также должна удовлетворять некоторым ограничениям .
Область оптимизации далее делится на несколько подобластей в зависимости от формы целевой функции и ограничения. Например, линейное программирование имеет дело со случаем, когда и целевая функция, и ограничения являются линейными. Известным методом в линейном программировании является симплекс-метод .
Метод множителей Лагранжа можно использовать для сведения задач оптимизации с ограничениями к задачам оптимизации без ограничений.
Численное интегрирование, в некоторых случаях также известное как численная квадратура , требует значения определенного интеграла . [19] Популярные методы используют одну из формул Ньютона-Котеса (например, правило средней точки или правило Симпсона ) или квадратуру Гаусса . [20] Эти методы основаны на стратегии «разделяй и властвуй», при которой интеграл на относительно большом множестве разбивается на интегралы на меньших множествах. В более высоких размерностях, где эти методы становятся чрезмерно дорогими с точки зрения вычислительных усилий, можно использовать методы Монте-Карло или квази-Монте-Карло (см. Интеграция Монте-Карло [21] ), или, в умеренно больших размерностях, метод разреженных сеток .
Численный анализ также связан с вычислением (приближенным способом) решения дифференциальных уравнений , как обыкновенных дифференциальных уравнений , так и уравнений в частных производных . [22]
Уравнения с частными производными решаются путем предварительной дискретизации уравнения, приводящей его в конечномерное подпространство. [23] Это можно сделать методом конечных элементов , [24] [25] [26] методом конечных разностей , [27] или (особенно в инженерии) методом конечных объемов . [28] Теоретическое обоснование этих методов часто включает теоремы из функционального анализа . Это сводит задачу к решению алгебраического уравнения.
С конца двадцатого века большинство алгоритмов реализуется на различных языках программирования. Репозиторий Netlib содержит различные коллекции программных процедур для численных задач, в основном на Fortran и C. Коммерческие продукты, реализующие множество различных численных алгоритмов, включают библиотеки IMSL и NAG ; альтернативой свободного программного обеспечения является GNU Scientific Library .
На протяжении многих лет Королевское статистическое общество публиковало многочисленные алгоритмы в своей книге «Прикладная статистика» (код этих функций «AS» находится здесь); ACM аналогичным образом в своих трудах по математическому программному обеспечению (код «TOMS» находится здесь). Центр надводных боевых действий ВМС несколько раз публиковал свою библиотеку математических подпрограмм (код здесь).
Существует несколько популярных приложений для численных вычислений, таких как MATLAB , [29] [30] [31] TK Solver , S-PLUS и IDL [32], а также бесплатные и открытые альтернативы, такие как FreeMat , Scilab , [33] [34] GNU Octave (похож на Matlab) и IT++ (библиотека C++). Существуют также языки программирования, такие как R [35] (похож на S-PLUS), Julia , [36] и Python с библиотеками, такими как NumPy , SciPy [37] [38] [39] и SymPy . Производительность сильно различается: в то время как векторные и матричные операции обычно быстры, скалярные циклы могут различаться по скорости более чем на порядок. [40] [41]
Многие системы компьютерной алгебры , такие как Mathematica, также выигрывают от наличия арифметики произвольной точности , которая может обеспечить более точные результаты. [42] [43] [44] [45]
Кроме того, любое программное обеспечение для работы с электронными таблицами может быть использовано для решения простых задач, связанных с численным анализом. Например, Excel имеет сотни доступных функций , в том числе для матриц, которые могут использоваться в сочетании со встроенным «решателем» .
Медиа из Commons
Цитаты из Викицитатника
Учебники из Wikibooks
