Числовой анализ

Вавилонская глиняная табличка YBC 7289 (ок. 1800–1600 гг. До н.э.) с аннотациями. Корень квадратный из 2 аппроксимируется четырьмя шестидесятеричными цифрами, то есть примерно шестью десятичными цифрами. 1 + 24/60 + 51/60 ² + 10/60 ³ = 1,41421296 ... ^[1]

Численный анализ - это исследование алгоритмов, которые используют численное приближение (в отличие от символьных манипуляций ) для задач математического анализа (в отличие от дискретной математики ). Численный анализ, естественно, находит применение во всех областях инженерии и физических наук, но в 21 веке также науки о жизни, социальные науки, медицина, бизнес и даже искусство приняли элементы научных вычислений. Рост вычислительной мощности произвел революцию в использовании реалистичных математических моделей в науке и технике, и для реализации этих подробных моделей мира требуется тонкий численный анализ. Например,обыкновенные дифференциальные уравнения появляются в небесной механике (предсказывают движения планет, звезд и галактик); числовая линейная алгебра важна для анализа данных; ^{[2] [3] [4]} стохастические дифференциальные уравнения и цепи Маркова необходимы для моделирования живых клеток в медицине и биологии.

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

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

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

Общее введение [ править ]

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

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

Остальная часть этого раздела описывает несколько важных тем численного анализа.

История [ править ]

Численный анализ появился на много веков раньше, чем были изобретены современные компьютеры. Линейная интерполяция использовалась более 2000 лет назад. Многие великие математики прошлого озаботилась численным анализом ^[5] , как видно из названия важных алгоритмов как метода Ньютона , интерполяционный полином Лагранжа , Гаусс , или метод Эйлера .

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

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

Прямые и итерационные методы [ править ]

Рассмотрим проблему решения

3 х ³ + 4 = 28

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

Для итерационного метода, применить метод деления пополам , чтобы F ( х ) = 3 х ³ - 24. Начальные значения = 0, Ь = 3, е ( ) = -24, е ( б ) = 57.

Из этой таблицы можно сделать вывод, что решение находится между 1,875 и 2,0625. Алгоритм может вернуть любое число в этом диапазоне с ошибкой менее 0,2.

Дискретизация и численное интегрирование [ править ]

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

Дискретизация было бы сказать , что скорость автомобиля была постоянной от 0:00 до 0:40, а затем с 0:40 до 1:20 и , наконец , от 1:20 до 2:00. Например, общее расстояние, пройденное за первые 40 минут, составляет примерно (2/3 ч  × 140 км / ч ) = 93.3 км . Это позволило бы нам оценить общее пройденное расстояние как93,3 км +100 км +120 км =313,3 км , что является примером численного интегрирования (см. Ниже) с использованием суммы Римана , поскольку смещение является интегралом скорости.

Плохо обусловленная задача: возьмем функцию 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 ).

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

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

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

Дискретность [ править ]

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

Генерация и распространение ошибок [ править ]

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

Округление [ править ]

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

Ошибка усечения и дискретизации [ править ]

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

Как только ошибка генерируется, она, как правило, распространяется на все вычисления. Например, уже отмечалось, что операция + на калькуляторе (или компьютере) неточна. Отсюда следует, что расчет типа еще более неточен.${\ displaystyle a + b + c + d + e}$

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

Численная устойчивость и корректные задачи [ править ]

Численная стабильность - это понятие в численном анализе. Алгоритм называется численно стабильным, если ошибка, независимо от ее причины, не становится намного больше во время расчета. ^[10] Это происходит, если проблема « хорошо обусловлена », что означает, что решение изменяется лишь на небольшую величину, если данные проблемы изменяются на небольшую величину. ^[10] Напротив, если проблема «плохо обусловлена», то любая небольшая ошибка в данных перерастет в большую ошибку. ^[10]

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

Таким образом, алгоритм, который решает хорошо обусловленную задачу, может быть численно стабильным или численно нестабильным. Искусство численного анализа - найти устойчивый алгоритм для решения поставленной математической задачи. Например, вычисление квадратного корня из 2 (что составляет примерно 1,41421) - это хорошо поставленная задача. Многие алгоритмы решают эту проблему, начиная с начального приближения x ₀ до , например, x ₀ = 1,4, а затем вычисляя улучшенные предположения x ₁ , x ₂ и т. Д. Одним из таких методов является знаменитый вавилонский метод , который задается как x _{k +1} = х _к / 2 + 1 /${\ displaystyle {\ sqrt {2}}}$х _к . Другой метод, называемый «методом X», задается формулой x _{k +1} = ( x _k ² - 2) ² + x _k . ^{[примечание 1]} Несколько итераций каждой схемы рассчитаны в виде таблицы ниже с начальными предположениями x ₀ = 1,4 и x ₀ = 1,42.

Обратите внимание, что вавилонский метод сходится быстро независимо от первоначального предположения, тогда как метод X сходится чрезвычайно медленно с начальным предположением x ₀ = 1,4 и расходится для исходного предположения x ₀ = 1,42. Следовательно, вавилонский метод численно устойчив, а метод X численно нестабилен.

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

${\ displaystyle f (x) = x \ left ({\ sqrt {x + 1}} - {\ sqrt {x}} \ right) {\ text {and}} g (x) = {\ frac {x} {{\ sqrt {x + 1}} + {\ sqrt {x}}}}.}$

Сравнение результатов

${\displaystyle f(500)=500\left({\sqrt {501}}-{\sqrt {500}}\right)=500\left(22.38-22.36\right)=500(0.02)=10}$

и

${\displaystyle {\begin{alignedat}{3}g(500)&={\frac {500}{{\sqrt {501}}+{\sqrt {500}}}}\\&={\frac {500}{22.38+22.36}}\\&={\frac {500}{44.74}}=11.17\end{alignedat}}}$

сравнивая два приведенных выше результата, становится ясно, что потеря значимости (вызванная здесь катастрофическим отказом от вычитания приближений к ближайшим числам и , несмотря на то, что вычитание вычисляется точно) оказывает огромное влияние на результаты, даже если обе функции эквивалентны , как показано ниже${\displaystyle {\sqrt {501}}}$${\displaystyle {\sqrt {500}}}$

${\displaystyle {\begin{alignedat}{4}f(x)&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)\\&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right){\frac {{\sqrt {x+1}}+{\sqrt {x}}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {({\sqrt {x+1}})^{2}-({\sqrt {x}})^{2}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {x+1-x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {1}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=g(x)\end{alignedat}}}$

Желаемое значение, вычисленное с использованием бесконечной точности, равно 11,174755 ...

• Пример является модификацией примера, взятого у Мэтью; Численные методы с использованием Matlab, 3-е изд.

Направления обучения [ править ]

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

Вычисление значений функций [ править ]

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

Интерполяция, экстраполяция и регрессия [ править ]

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

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

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

Решение уравнений и систем уравнений [ править ]

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

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

Алгоритмы поиска корня используются для решения нелинейных уравнений (они названы так, потому что корень функции является аргументом, для которого функция возвращает ноль). Если функция дифференцируема и производная известна, тогда часто используется метод Ньютона. ^{[13] [14]} Линеаризация - это еще один метод решения нелинейных уравнений.

Решение проблем с собственными или сингулярными значениями [ править ]

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

Оптимизация [ править ]

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

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

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

Вычисление интегралов [ править ]

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

Дифференциальные уравнения [ править ]

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

Уравнения с частными производными решаются путем сначала дискретизации уравнения, переводя его в конечномерное подпространство. ^[20] Это может быть сделано с помощью метода конечных элементов , ^{[21] [22] [23]} разностный метод, ^[24] или ( в частности , в машиностроении) а метод конечных объемов . ^[25] Теоретическое обоснование этих методов часто связано с теоремами функционального анализа . Это сводит проблему к решению алгебраического уравнения.

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

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

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

Существует несколько популярных приложений для численных вычислений, таких как MATLAB , ^{[26] [27] [28]} TK Solver , S-PLUS и IDL ^[29], а также бесплатные альтернативы с открытым исходным кодом, такие как FreeMat , Scilab , ^{[30] [ 31]} GNU Octave (аналог Matlab) и IT ++ (библиотека C ++). Также существуют языки программирования, такие как R ^[32] (аналог S-PLUS) и Python с такими библиотеками, как NumPy , SciPy ^{[33] [34] [35]} и SymPy.. Производительность сильно различается: хотя векторные и матричные операции обычно выполняются быстро, скалярные циклы могут отличаться по скорости более чем на порядок. ^{[36] [37]}

Многие системы компьютерной алгебры, такие как Mathematica, также выигрывают от наличия арифметики произвольной точности, которая может обеспечить более точные результаты. ^{[38] [39] [40] [41]}

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

См. Также [ править ]

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

Заметки [ править ]

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

Цитаты [ править ]

Источники [ править ]

Внешние ссылки [ править ]

Журналы [ править ]

• gdz.sub.uni-goettingen , Numerische Mathematik , тома 1-66, Springer, 1959–1994 (с возможностью поиска; страницы - изображения). (на английском и немецком языках)
• Numerische Mathematik , тома 1–112, Springer, 1959–2009
• Журнал численного анализа , тома 1-47, SIAM, 1964–2009

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

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

Материалы онлайн-курса [ править ]

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