Числовой анализ - Numerical analysis

Вавилонская глиняная табличка 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

для неизвестного количества Икс.

Для итеративного метода примените метод деления пополам к ж(Икс) = 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 км + 146 км = 313,3 км, который является примером численное интегрирование (см. ниже) с помощью Сумма Римана, потому что смещение - это интеграл скорости.

Плохо обусловленная проблема: возьмите функцию ж(Икс) = 1/(Икс − 1). Обратите внимание, что ж(1.1) = 10 и ж(1.001) = 1000: изменение Икс менее 0,1 превращается в изменение ж(Икс) почти 1000. Оценка ж(Икс) возле Икс = 1 - плохо обусловленная задача.

Хорошо обусловленная проблема: напротив, оценка той же функции ж(Икс) = 1/(Икс − 1) возле Икс = 10 - это хорошо сформулированная задача. Например, ж(10) = 1/9 ≈ 0,111 и ж(11) = 0,1: небольшое изменение Икс приводит к скромному изменению ж(Икс).

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

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

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

Дискретность

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

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

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

Округлять

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

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

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

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

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

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

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

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

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

Заметьте, что вавилонский метод сходится быстро независимо от первоначального предположения, тогда как метод X сходится чрезвычайно медленно с первоначальным предположением. Икс₀ = 1,4 и расходится для первоначального предположения Икс₀ = 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 {alignat} {3} g (500) & = { frac {500} {{ sqrt {501}} + { sqrt {500}}}} & = { frac { 500} {22,38 + 22,36}} & = { frac {500} {44,74}} = 11,17 end {alignat}}}$

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

${ displaystyle { begin {alignat} {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 {alignat}}}$

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

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

Направления обучения

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

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

Интерполяция: наблюдая, что температура изменяется от 20 градусов Цельсия в 1:00 до 14 градусов в 3:00, линейная интерполяция этих данных сделает вывод, что она была 17 градусов в 2:00 и 18,5 градусов в 13:30. Экстраполяция: если валовой внутренний продукт страны растет в среднем на 5% в год и составлял 100 миллиардов в прошлом году, можно экстраполировать, что в этом году он составит 105 миллиардов. Регрессия: в линейной регрессии, учитывая п точек, вычисляется линия, которая проходит как можно ближе к тем п точки. Оптимизация: скажем, лимонад продается по подставка для лимонада, по цене 1 197 стаканов лимонада можно продавать в день, и что при каждом увеличении на 0,01 доллара в день будет продаваться на один стакан лимонада меньше. Если бы можно было взимать 1,485 долларов, прибыль была бы максимальной, но из-за ограничений, связанных с необходимостью взимать целую сумму в центах, взимание 1,48 или 1,49 доллара за стакан принесет максимальный доход в 220,52 доллара в день. Дифференциальное уравнение: если 100 вентиляторов настроены так, чтобы продувать воздух из одного конца комнаты в другой, а затем на ветер бросается перо, что произойдет? Перо будет следовать за воздушными потоками, что может быть очень сложным. Одним из приближений является измерение скорости, с которой воздух дует около пера каждую секунду, и продвижение имитируемого пера, как если бы оно двигалось по прямой с той же скоростью в течение одной секунды, прежде чем снова измерить скорость ветра. Это называется Метод Эйлера для решения обыкновенного дифференциального уравнения.

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

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

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

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

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

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

Другой фундаментальной проблемой является вычисление решения некоторого заданного уравнения. Обычно различают два случая, в зависимости от того, является уравнение линейным или нет. Например, уравнение ${ 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 репозиторий содержит различные наборы программных программ для численных задач, в основном в Фортран и C. Коммерческие продукты, реализующие множество различных числовых алгоритмов, включают IMSL и НАГ библиотеки; а бесплатно программное обеспечение альтернатива - это Научная библиотека GNU.

Спустя годы Королевское статистическое общество опубликовал многочисленные алгоритмы в своих Прикладная статистика (код для этих функций "AS": Вот ); ACM аналогично в своем Транзакции по математическому программному обеспечению (Код "TOMS" Вот ). Военно-морской центр надводной войны несколько раз публиковал свои Библиотека математических подпрограмм (код Вот ).

Существует несколько популярных приложений для численных вычислений, таких как MATLAB,^[26][27][28] TK Solver, S-PLUS, и IDL^[29] а также бесплатные альтернативы с открытым исходным кодом, такие как FreeMat, Scilab,^[30][31] GNU Octave (аналогично Matlab) и IT ++ (библиотека C ++). Также существуют языки программирования, такие как р^[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 (предыдущие выпуски можно бесплатно загрузить)
• Первые шаги в численном анализе (в архиве ), Р. Дж. Хоскинг, С. Джо, Д. К. Джойс, Дж. К. Тернер.
• CSEP (Образовательный проект по вычислительным наукам), Министерство энергетики США (архивировано 01.08.2017 )
• Численные методы, ch 3. в Электронная библиотека математических функций

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

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