Численный анализ — это исследование алгоритмов , использующих численную аппроксимацию (в отличие от символьных манипуляций ) для задач математического анализа (в отличие от дискретной математики ). Это исследование численных методов, которые пытаются найти приближенные решения проблем, а не точные. Численный анализ находит применение во всех областях техники и физических наук, а в 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 содержит различные коллекции программных процедур для числовых задач, в основном на Фортране и C. Коммерческие продукты, реализующие множество различных численных алгоритмов, включают библиотеки IMSL и NAG ; Альтернативой бесплатному программному обеспечению является Научная библиотека GNU .
На протяжении многих лет Королевское статистическое общество опубликовало множество алгоритмов в своей книге «Прикладная статистика» (код этих функций «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
Цитаты из Wikiquote
Учебники из Wikibooks
