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

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

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

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

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

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

Приложения

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

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

История

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

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

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

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

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

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

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

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

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

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

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

33x ³ + 4 = 28

для неизвестной величины x .

Прямой метод

	33x 3 + 4 = 28.
Вычесть 4	33x 3 = 24.
Разделить на 3	х 3 =  8.
Возьмите кубические корни	х = 2.

Для итерационного метода примените метод деления пополам к f ( x ) = 3 x ³ − 24. Начальные значения: a = 0, b = 3, f ( a ) = −24, f ( b ) = 57.

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

а	б	середина	е (средний)
0	3	1.5	−13.875
1.5	3	2.25	10.17...
1.5	2.25	1.875	−4.22...
1.875	2.25	2.0625	2.32...

Из этой таблицы можно сделать вывод, что решение находится между 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 ).

Дискретизация

Более того, непрерывные задачи иногда необходимо заменять дискретной задачей, решение которой, как известно, аппроксимирует решение непрерывной задачи; этот процесс называется « дискретизацией ». Например, решением дифференциального уравнения является функция . Эта функция должна быть представлена ​​конечным количеством данных, например, ее значением в конечном числе точек в ее области определения, даже если эта область является континуумом .

Генерация и распространение ошибок

Дополнительная информация: Распространение ошибок.

Исследование ошибок составляет важную часть численного анализа. Существует несколько способов внесения ошибки в решение задачи.

Округление

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

Ошибка усечения и дискретизации

Ошибки усечения возникают, когда итерационный метод завершается или аппроксимируется математическая процедура, и приближенное решение отличается от точного решения. Точно так же дискретизация вызывает ошибку дискретизации , поскольку решение дискретной задачи не совпадает с решением непрерывной задачи. В приведенном выше примере для вычисления решения $3x^{3}+4=28$, после десяти итераций вычисленный корень составит примерно 1,99. Следовательно, ошибка усечения составляет примерно 0,01.

Как только ошибка генерируется, она распространяется на все вычисления. Например, операция + на компьютере является неточной. Расчет типа $a+b+c+d+e$ еще более неточно.

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

Численная устойчивость

Алгоритм называется численно устойчивым, если ошибка, какова бы ни была ее причина, в ходе расчета не увеличивается значительно. Это происходит, если задача хорошо обусловлена , а это означает, что решение меняется лишь на небольшую величину, если данные задачи изменяются на небольшую величину. Напротив, если проблема «плохо обусловлена», то любая небольшая ошибка в данных превратится в большую ошибку. Как исходная задача, так и алгоритм, используемый для ее решения, могут быть хорошо обусловленными или плохо обусловленными, и возможна любая комбинация.Таким образом, алгоритм, который решает хорошо обусловленную задачу, может быть либо численно устойчивым, либо численно нестабильным. Искусство численного анализа заключается в поиске стабильного алгоритма решения корректной математической задачи.

Области обучения

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

Вычисление значений функций

Интерполяция: учитывая, что температура колеблется от 20 градусов по Цельсию в 1:00 до 14 градусов в 15:00, линейная интерполяция этих данных позволит сделать вывод, что она составляла 17 градусов в 14:00 и 18,5 градусов в 13:30. Экстраполяция: если валовой внутренний продукт страны растет в среднем на 5% в год и в прошлом году составил 100 миллиардов, можно экстраполировать, что в этом году он составит 105 миллиардов. A line through 20 points Регрессия: в линейной регрессии по заданным n точкам вычисляется линия, которая проходит как можно ближе к этим n точкам. How much for a glass of lemonade? Оптимизация: предположим, что лимонад продается в киоске с лимонадом по цене 1,00 доллара за стакан, что в день можно продать 197 стаканов лимонада, и что при каждом увеличении на 0,01 доллара в день будет продаваться на один стакан лимонада меньше. Если бы можно было взимать 1,485 доллара, прибыль была бы максимизирована, но из-за ограничений, связанных с взиманием суммы в целый цент, взимание 1,48 или 1,49 доллара за стакан принесет максимальный доход в размере 220,52 доллара в день. Wind direction in blue, true trajectory in black, Euler method in red Дифференциальное уравнение: если 100 вентиляторов будут продувать воздух из одного конца комнаты в другой, а затем на ветер бросить перо, что произойдет? Перо будет следовать за воздушными потоками, что может быть очень сложным. Одним из приближений является измерение скорости, с которой воздух дует рядом с пером каждую секунду, и в течение одной секунды продвигать моделируемое перо так, как если бы оно двигалось по прямой линии с той же скоростью, прежде чем снова измерить скорость ветра. Это называется методом Эйлера решения обыкновенного дифференциального уравнения.

Одной из простейших задач является вычисление функции в заданной точке. Самый простой подход — просто ввести число в формулу — иногда не очень эффективен. Для полиномов лучшим подходом является использование схемы Горнера , поскольку она уменьшает необходимое количество умножений и сложений. Как правило, важно оценивать и контролировать ошибки округления, возникающие в результате использования арифметики с плавающей запятой .

, экстраполяция

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

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

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

Решение уравнений и систем уравнений

Другая фундаментальная проблема — вычисление решения некоторого заданного уравнения. Обычно различают два случая в зависимости от того, является ли уравнение линейным или нет. Например, уравнение $2x+5=3$ является линейным, в то время как $2x^{2}+5=3$ нет.

Много усилий было вложено в разработку методов решения систем линейных уравнений . Стандартными прямыми методами, т. е. методами, которые используют некоторое матричное разложение , являются исключение Гаусса , LU-разложение , разложение Холецкого для симметричных (или эрмитовых ) и положительно определенных матриц и QR-разложение для неквадратных матриц. Итеративные методы, такие как метод Якоби , метод Гаусса – Зейделя , метод последовательного чрезмерного расслабления и метод сопряженных градиентов. обычно предпочтительнее для больших систем. Общие итерационные методы могут быть разработаны с использованием расщепления матрицы .

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

проблем с собственными или

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

Оптимизация

Основная статья: Математическая оптимизация

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

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

Метод множителей Лагранжа можно использовать для сведения задач оптимизации с ограничениями к задачам неограниченной оптимизации.

Вычисление интегралов

Основная статья: Численное интегрирование

Численное интегрирование, в некоторых случаях также известное как числовая квадратура , требует значения определенного интеграла . Популярные методы используют одну из формул Ньютона-Котеса (например, правило средней точки или правило Симпсона ) или квадратуру Гаусса . Эти методы основаны на стратегии «разделяй и властвуй», при которой интеграл на относительно большом наборе разбивается на интегралы на меньших наборах. В более высоких измерениях, где эти методы становятся непомерно дорогими с точки зрения вычислительных усилий, можно использовать Монте-Карло или методы квази-Монте-Карло (см. Интегрирование Монте-Карло). ), или, в умеренно больших размерностях, метод разреженных сеток .

Дифференциальные уравнения

Основные статьи: Численные обыкновенные дифференциальные уравнения и числовые уравнения в частных производных

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

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

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

Основные статьи: Список программного обеспечения для численного анализа и Сравнение программного обеспечения для численного анализа.

С конца двадцатого века большинство алгоритмов реализовано на различных языках программирования. Репозиторий Netlib содержит различные коллекции программных процедур для числовых задач, в основном Фортране и C. на Коммерческие продукты, реализующие множество различных численных алгоритмов, включают библиотеки IMSL и NAG ; Альтернативой бесплатному программному обеспечению является Научная библиотека GNU .

На протяжении многих лет Королевское статистическое общество опубликовало множество алгоритмов в своей книге «Прикладная статистика» (код этих функций «AS» находится здесь ); Аналогичным образом ACM в своих «Транзакциях по математическому программному обеспечению » (код «TOMS» находится здесь ).Центр надводных боевых действий ВМФ несколько раз публиковал свою Библиотеку математических подпрограмм (код здесь ).

Существует несколько популярных приложений для численных вычислений, таких как MATLAB , TK Solver , S-PLUS и IDL а также бесплатные альтернативы с открытым исходным кодом, такие как FreeMat , Scilab , GNU Octave (аналог Matlab) и IT++ (библиотека C++). Существуют также языки программирования, такие как R. (аналог S-PLUS), Юля , и Python с такими библиотеками, как NumPy , SciPy и СимПи . Производительность варьируется в широких пределах: хотя векторные и матричные операции обычно выполняются быстро, скалярные циклы могут различаться по скорости более чем на порядок.

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

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

См. также

• Категория:Численный аналитик
• Анализ алгоритмов
• Вычислительная наука
• Вычислительная физика
• Премия Гордона Белла
• Интервальная арифметика
• Список тем численного анализа
• Метод локальной линеаризации
• Числовое дифференцирование
• Численные рецепты
• Вероятностные числа
• Символьно-числовое вычисление
• Проверенные цифры

Ссылки

Источники

• Голуб, Джин Х .; Чарльз Ф. Ван Лоан (1986). Матричные вычисления (3-е изд.). Издательство Университета Джонса Хопкинса. ISBN  0-8018-5413-Х .
• Ралстон Энтони; Рабиновиц Филипс (2001). Первый курс численного анализа (2-е изд.). Дуврские публикации. ISBN  978-0486414546 .
• Хайэм, Николас Дж. (2002) [1996]. Точность и устойчивость численных алгоритмов . Общество промышленной и прикладной математики. ISBN  0-89871-355-2 .
• Хильдебранд, ФБ (1974). Введение в численный анализ (2-е изд.). МакГроу-Хилл. ISBN  0-07-028761-9 .
• Лидер Джеффри Дж. (2004 г.). Численный анализ и научные вычисления . Эддисон Уэсли. ISBN  0-201-73499-0 .
• Уилкинсон, Дж. Х. (1988) [1965]. Алгебраическая проблема собственных значений . Кларендон Пресс. ISBN  978-0-19-853418-1 .
• Кахан, В. (1972). Обзор ошибок-анализа . Учеб. 71-й Конгресс ИФИП в Любляне. Информация. Обработка 71 . Том. 2. Северная Голландия. стр. 1214–39. ISBN  978-0-7204-2063-0 . OCLC   25116949 . (примеры важности точной арифметики).
• Трефетен, Ллойд Н. (2008). «IV.21 Численный анализ» (PDF) . В Лидере И.; Гауэрс, Т.; Барроу-Грин, Дж. (ред.). Принстонский спутник математики . Издательство Принстонского университета. стр. 604–614. ISBN  978-0-691-11880-2 .

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

Журналы

• Вычислительная математика , тома 1–..., Springer , 1959–
  • тома 1–66, 1959–1994 гг. (с возможностью поиска; страницы представляют собой изображения). (на английском и немецком языках)
• Журнал численного анализа (SINUM) , тома 1–..., SIAM, 1964–

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

• «Численный анализ» , Энциклопедия математики , EMS Press , 2001 [1994]
• Числовые рецепты , Уильям Х. Пресс (бесплатно, предыдущие издания можно загрузить)
• Первые шаги в численном анализе ( в архиве ), Р.Дж.Хоскинг, С.Джо, Д.С.Джойс и Дж.К.Тернер.
• CSEP (Образовательный проект в области вычислительной техники) , Министерство энергетики США ( архивировано 1 августа 2017 г. )
• Численные методы , глава 3. в Электронной библиотеке математических функций
• Численная интерполяция, дифференцирование и интегрирование , глава 25. в Справочнике математических функций ( Абрамовиц и Стегун )

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

• Численные методы ( архивировано 28 июля 2009 г. в Wayback Machine ), Кембриджский университет Стюарта Далзила.
• Лекции по численному анализу , Деннис Детурк и Герберт С. Уилф, Пенсильванский университет
• Численные методы , Университет Джона Д. Фентона, Карлсруэ
• Численные методы для физиков , Оксфордский университет Энтони О'Хара
• Лекции по численному анализу ( в архиве ), Университет Р. Радока Махидола
• Введение в численный анализ в инженерии , Массачусетский технологический институт Хенрика Шмидта
• Численный анализ в инженерном деле , Д. У. Хардер, Университет Ватерлоо
• Введение в численный анализ , Университет Дорон Леви , Мэриленд
• Численный анализ - Численные методы (в архиве), Джон Х. Мэтьюз, Калифорнийский государственный университет, Фуллертон