stringtranslate.com

Численный анализ

Вавилонская глиняная табличка YBC 7289 (ок. 1800–1600 гг. до н. э.) с аннотациями. Приближение квадратного корня из 2 составляет четыре шестидесятеричных цифры, что составляет около шести десятичных цифр. 1 + 24/60 + 51/60 2 + 10/60 3 = 1,41421296... [1]

Численный анализ — это изучение алгоритмов , которые используют численное приближение (в отличие от символьных манипуляций ) для задач математического анализа (в отличие от дискретной математики ). Это изучение численных методов, которые пытаются найти приближенные решения проблем, а не точные. Численный анализ находит применение во всех областях техники и физических наук, а в 21 веке также в естественных и социальных науках, таких как экономика, медицина, бизнес и даже искусство. Текущий рост вычислительной мощности позволил использовать более сложный численный анализ, предоставляя подробные и реалистичные математические модели в науке и технике. Примерами численного анализа являются: обыкновенные дифференциальные уравнения , которые встречаются в небесной механике (предсказание движений планет, звезд и галактик), численная линейная алгебра в анализе данных, [2] [3] [4] и стохастические дифференциальные уравнения и цепи Маркова для моделирования живых клеток в медицине и биологии.

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

Числовая точка зрения восходит к самым ранним математическим сочинениям. Табличка из Йельской вавилонской коллекции ( YBC 7289 ) дает шестидесятеричное числовое приближение квадратного корня из 2 , длины диагонали в единичном квадрате .

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

Ключевые аспекты численного анализа включают в себя:

1. Анализ ошибок : понимание и минимизация ошибок, возникающих в числовых расчетах, таких как ошибки округления, ошибки усечения и ошибки аппроксимации.

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

3. Стабильность : гарантия того, что небольшие изменения на входе или промежуточных этапах не приведут к большим изменениям на выходе, что может привести к неверным результатам.

4. Эффективность : разработка алгоритмов, решающих проблемы за разумное время и с управляемыми вычислительными ресурсами.

5. Обусловливание : анализ того, как небольшие изменения входных данных влияют на решение задачи, что помогает оценить надежность численного решения.

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

Приложения

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

История

Область численного анализа появилась на много столетий раньше изобретения современных компьютеров. Линейная интерполяция использовалась уже более 2000 лет назад. Многие великие математики прошлого были заняты численным анализом, [5] как это очевидно из названий важных алгоритмов, таких как метод Ньютона , интерполяционный полином Лагранжа , исключение Гаусса или метод Эйлера . Истоки современного численного анализа часто связывают со статьей Джона фон Неймана и Германа Голдстайна 1947 года , [7] [8] но другие считают, что современный численный анализ восходит к работе Э. Т. Уиттекера 1912 года. [7]

Публикация НИСТ

Для облегчения вычислений вручную были выпущены большие книги с формулами и таблицами данных, такими как точки интерполяции и коэффициенты функций. Используя эти таблицы, часто рассчитанные до 16 знаков после запятой или более для некоторых функций, можно было искать значения, чтобы вставлять их в приведенные формулы и получать очень хорошие числовые оценки некоторых функций. Канонической работой в этой области является публикация NIST под редакцией Абрамовица и Стегана , книга объемом более 1000 страниц с очень большим количеством часто используемых формул и функций и их значений во многих точках. Значения функций больше не очень полезны, когда доступен компьютер, но большой список формул все еще может быть очень удобным.

Механический калькулятор также был разработан как инструмент для ручных вычислений. Эти калькуляторы эволюционировали в электронные компьютеры в 1940-х годах, и тогда было обнаружено, что эти компьютеры также полезны для административных целей. Но изобретение компьютера также повлияло на область численного анализа, [5] поскольку теперь можно было выполнять более длинные и сложные вычисления.

Премия Лесли Фокса по численному анализу была учреждена в 1985 году Институтом математики и ее приложений .

Ключевые понятия

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

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

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

Итерационные методы более распространены, чем прямые методы в численном анализе. Некоторые методы являются прямыми в принципе, но обычно используются так, как будто они таковыми не являются, например GMRES и метод сопряженных градиентов . Для этих методов число шагов, необходимых для получения точного решения, настолько велико, что приближение принимается так же, как и для итерационного метода.

В качестве примера рассмотрим задачу решения

3 х 3 + 4 = 28

для неизвестной величины 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 имеет сотни доступных функций , в том числе для матриц, которые могут использоваться в сочетании со встроенным «решателем» .

Смотрите также

Примечания

Ссылки

Цитаты

  1. ^ "Фотография, иллюстрация и описание таблички root(2) из ​​Йельской вавилонской коллекции". Архивировано из оригинала 13 августа 2012 г. Получено 2 октября 2006 г.
  2. ^ Деммель, Дж. В. (1997). Прикладная численная линейная алгебра. SIAM . doi :10.1137/1.9781611971446. ISBN 978-1-61197-144-6.
  3. ^ Ciarlet, PG; Miara, B.; Thomas, JM (1989). Введение в численную линейную алгебру и оптимизацию . Cambridge University Press. ISBN 9780521327886. OCLC  877155729.
  4. ^ Трефетен, Ллойд; Бау III, Дэвид (1997). Численная линейная алгебра. SIAM. ISBN 978-0-89871-361-9.
  5. ^ abc Brezinski, C.; Wuytack, L. (2012). Численный анализ: Исторические разработки в 20 веке. Elsevier. ISBN 978-0-444-59858-5.
  6. ^ Стивен Блит. «Введение в количественные финансы». 2013. Страница VII.
  7. ^ ab Watson, GA (2010). "История и развитие численного анализа в Шотландии: личная точка зрения" (PDF) . Рождение численного анализа . World Scientific. стр. 161–177. ISBN 9789814469456.
  8. ^ Бултел, Адемар ; Кулс, Рональд, ред. (2010). Рождение численного анализа. Том 10. World Scientific. ISBN 978-981-283-625-0.
  9. ^ Саад, Y. (2003). Итерационные методы для разреженных линейных систем. SIAM. ISBN 978-0-89871-534-7.
  10. ^ Хагеман, LA; Янг, DM (2012). Прикладные итеративные методы (2-е изд.). Courier Corporation. ISBN 978-0-8284-0312-2.
  11. ^ Трауб, Дж. Ф. (1982). Итерационные методы решения уравнений (2-е изд.). Американское математическое общество. ISBN 978-0-8284-0312-2.
  12. ^ Гринбаум, А. (1997). Итерационные методы решения линейных систем. SIAM. ISBN 978-0-89871-396-1.
  13. ^ abc Хайэм 2002
  14. ^ Брезинский, К.; Залья, М. Р. (2013). Методы экстраполяции: теория и практика. Elsevier. ISBN 978-0-08-050622-7.
  15. ^ Хестенес, Магнус Р.; Штифель, Эдуард (декабрь 1952 г.). «Методы сопряженных градиентов для решения линейных систем» (PDF) . Журнал исследований Национального бюро стандартов . 49 (6): 409–. doi :10.6028/jres.049.044.
  16. ^ Эскерро Фернандес, JA; Эрнандес Верон, M.A. (2017). Метод Ньютона: обновленный подход теории Канторовича. Биркхойзер. ISBN 978-3-319-55976-6.
  17. ^ Deuflhard, Peter (2006). Методы Ньютона для нелинейных задач. Аффинная инвариантность и адаптивные алгоритмы. Computational Mathematics. Т. 35 (2-е изд.). Springer. ISBN 978-3-540-21099-3.
  18. ^ Огден, К.Дж.; Хафф, Т. (1997). "Разложение сингулярных значений и его применение в сжатии изображений" (PDF) . Математика 45. Колледж Редвудс. Архивировано из оригинала (PDF) 25 сентября 2006 г.
  19. ^ Дэвис, П. Дж.; Рабинович, П. (2007). Методы численного интегрирования. Courier Corporation. ISBN 978-0-486-45339-2.
  20. ^ Вайсштейн, Эрик В. «Квадратура Гаусса». MathWorld .
  21. ^ Geweke, John (1996). "15. Моделирование Монте-Карло и численное интегрирование". Handbook of Computational Economics . Vol. 1. Elsevier. pp. 731–800. doi :10.1016/S1574-0021(96)01017-9. ISBN 9780444898579.
  22. ^ Исерлес, А. (2009). Первый курс численного анализа дифференциальных уравнений (2-е изд.). Cambridge University Press. ISBN 978-0-521-73490-5.
  23. ^ Эймс, У. Ф. (2014). Численные методы для уравнений с частными производными (3-е изд.). Academic Press. ISBN 978-0-08-057130-0.
  24. ^ Джонсон, К. (2012). Численное решение уравнений в частных производных методом конечных элементов. Courier Corporation. ISBN 978-0-486-46900-3.
  25. ^ Бреннер, С.; Скотт, Р. (2013). Математическая теория методов конечных элементов (2-е изд.). Springer. ISBN 978-1-4757-3658-8.
  26. ^ Strang, G.; Fix, GJ (2018) [1973]. Анализ метода конечных элементов (2-е изд.). Wellesley-Cambridge Press. ISBN 9780980232783. OCLC  1145780513.
  27. ^ Strikwerda, JC (2004). Конечно-разностные схемы и уравнения в частных производных (2-е изд.). SIAM. ISBN 978-0-89871-793-8.
  28. ^ LeVeque, Randall (2002). Методы конечных объемов для гиперболических задач. Cambridge University Press. ISBN 978-1-139-43418-8.
  29. ^ Quarteroni, A.; Saleri, F.; Gervasio, P. (2014). Научные вычисления с MATLAB и Octave (4-е изд.). Springer. ISBN 978-3-642-45367-0.
  30. ^ Гандер, В.; Хребичек, Дж., ред. (2011). Решение проблем в научных вычислениях с использованием Maple и Matlab®. Springer. ISBN 978-3-642-18873-2.
  31. ^ Barnes, B.; Fulford, GR (2011). Математическое моделирование с примерами: подход дифференциальных уравнений с использованием Maple и MATLAB (2-е изд.). CRC Press. ISBN 978-1-4200-8350-7. OCLC  1058138488.
  32. ^ Gumley, LE (2001). Практическое программирование IDL. Elsevier. ISBN 978-0-08-051444-4.
  33. ^ Банкс, К.; Шанселье, Дж. П.; Делебек, Ф.; Гурса, М.; Никуха, Р.; Стир, С. (2012). Инженерные и научные вычисления с помощью Scilab . Springer. ISBN 978-1-4612-7204-5.
  34. ^ Тханки, РМ; Котари, А.М. (2019). Цифровая обработка изображений с использованием SCILAB. Springer. ISBN 978-3-319-89533-8.
  35. ^ Ихака, Р.; Джентльмен, Р. (1996). "R: язык для анализа данных и графики" (PDF) . Журнал вычислительной и графической статистики . 5 (3): 299–314. doi :10.1080/10618600.1996.10474713. S2CID  60206680.
  36. ^ Безансон, Джефф; Эдельман, Алан; Карпински, Стефан; Шах, Вирал Б. (1 января 2017 г.). «Джулия: свежий подход к численным вычислениям». SIAM Review . 59 (1): 65–98. arXiv : 1411.1607 . doi : 10.1137/141000671. hdl : 1721.1/110125 . ISSN  0036-1445. S2CID  13026838.
  37. ^ Джонс, Э., Олифант, Т. и Петерсон, П. (2001). SciPy: Научные инструменты с открытым исходным кодом для Python.
  38. ^ Bressert, E. (2012). SciPy и NumPy: обзор для разработчиков . O'Reilly. ISBN 9781306810395.
  39. ^ Бланко-Силва, Ф.Дж. (2013). Изучение SciPy для численных и научных вычислений . Пакет. ISBN 9781782161639.
  40. ^ Сравнение скорости различных пакетов обработки чисел. Архивировано 5 октября 2006 г. на Wayback Machine.
  41. ^ Сравнение математических программ для анализа данных Архивировано 18 мая 2016 г. в Португальском веб-архиве Стефана Штайнхауса, ScientificWeb.com
  42. ^ Мейдер, Р. Э. (1997). Программирование в Mathematica (3-е изд.). Addison-Wesley. ISBN 9780201854497. OCLC  1311056676.
  43. ^ Вольфрам, Стивен (1999). Книга MATHEMATICA®, версия 4. Cambridge University Press . ISBN 9781579550042.
  44. ^ Шоу, У. Т.; Тигг, Дж. (1993). Прикладная математика: как начать, как сделать (PDF) . Addison-Wesley. ISBN 978-0-201-54217-2. OCLC  28149048.
  45. ^ Мараско, А.; Романо, А. (2001). Научные вычисления с помощью Mathematica: Математические проблемы для обыкновенных дифференциальных уравнений. Springer. ISBN 978-0-8176-4205-1.

Источники

Внешние ссылки

Журналы

Онлайн-тексты

Материалы онлайн-курса