Численные (вычислительные) методы — методы решения математических задач в численном видеМуха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010. — 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92.
Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.
Многие численные методы являются частью библиотек математических программ. В системе подготовки инженеров технических специальностей являются важной составляющей.
Основами для вычислительных методов являются: решение систем линейных уравнений; интерполирование и приближённое вычисление функций; численное интегрирование; численное решение системы нелинейных уравнений; численное решение обыкновенных дифференциальных уравнений; численное решение уравнений в частных производных (уравнений математической физики); решение задач оптимизации.
История
Вавилонские математики (II тысячелетие до н. э.) разработали для извлечения квадратного корня особый численный метод.
Вавилонская глиняная табличка YBC 7289 из вавилонской коллекции Йельского университета была создана между 1800 и 1600 годами и демонстрирует √2 и √2/2 соответственно в шестидесятиричной системе счисления: 1;24,51,10 и 0;42,25,35 на квадрате, пересечённом двумя диагоналями. (1;24,51,10) по основанию 60 соответствует 1,41421296, что является правильным значением с точностью до 5 десятичных знаков:
Сложные проценты вычислялись с помощью метода линейной интерполяции.
В древнем Египте для нахождения площади круга разработали особый численный метод. Также использовался итерационный метод.
В древнем Китае использовался метод ложных положений , а также применялся метод фан-чен аналогичный методу Гаусса.
В древней Индии решали системы линейных уравнений методом пропорций. Использовался метод рассеивания, а также вычисляли объемы некоторых тел.
В древней Греции Евдокс (метод исчерпывания Евдокса), Архимед (метод верхних и нижних интегральных сумм ), и Герон Александрийский (правило извлечения кубического корня)применяли численные методы к решению некоторых задач.
В средние века приближенные методы использовались для нахождения уравнений третьей и четвертой степени. В Индии проводилось разложение синуса и косинуса в бесконечные ряды.
В Новое время численные методы продолжали развиваться: Николай Кузанский нашел формулу приближенного спрямления окружностей, Рене Декарт решая задачу по преломлению света нашел овалы Декарта, Бернулли предложил метод изоклин. Исаак Ньютон предложил метод решения алгебраических уравнений (метод Ньютона).
Методология
Все задачи вычислительной математики решаются в следующей последовательностиДьяченко В. Ф. Основные понятия вычислительной математики. — М., Наука, 1972. — Тираж 45000 экз. — С. 10: Исходная математическая задача заменяется другой задачей — вычислительным алгоритмом. Основными требованиями к вычислительному алгоритму являются: высокая точность, устойчивость и экономичность. При переходе к дискретной модели появляется погрешность аппроксимации, а при реализации вычислений — погрешность округления, поэтому для реальных вычислительных алгоритмов проводится анализ погрешностей и устойчивости вычислительного алгоритма. В современной науке для решения задач прикладной математики формулируется математическая модель в терминах интегральных и дифференциальных уравнений функций непрерывного аргумента. Переход от континуальной к дискретной математической модели осуществляется заменой функций непрерывного аргумента функциями дискретного аргумента. В получившихся конечно-разностных уравнениях интеграл и производная представлены конечной суммой и разностным отношением, соответственно. Получившаяся модель представляет собой систему алгебраических уравнений, для решения которой с определённой точностью составляется вычислительный алгоритм, который реализуется на вычислительных машинах. При решении больших систем необходимо вычислять собственные значения и вектора матриц, сводить нелинейные системы уравнений к линейным. Для некоторых задач (нейронная физика, физика плазмы, экономика) модель строится непосредственно на статистической выборке или на крупных объектах. Кроме того, строятся нерегулярные системы, для которых численные методы сочетаются с теорией графов. Отдельный класс представляют некорректно поставленные задачи. Вычислительный алгоритм содержит параметр , которого нет в исходной задаче; Выбором этого параметра можно добиться любой близости решения второй задачи к решению первой. Для многих важных классов задач разработаны разнообразные численные методы решения. По способу дискретизации численные методы делятся на проекционные и конечно-разностные, по способу решения — на прямые и итерационные. В методах конечных разностей ставится задача определить значения функции на дискретном множестве точек, в то время как в проекционных методах функция представлена линейной комбинацией элементов. При этом дискретная функция также может рассматриваться как линейная комбинация полиномов. Прямые методы решения обладают слабой устойчивостью, в то время как итерационные методы более устойчивы и обеспечивают быструю сходимость. Неточная реализация алгоритма, вызванная округлениями при вычислениях, не меняет существенно его свойств. Необходимо помнить, что вычислительная машина выполняет только четыре основных арифметических операции. Точность решения при этом должна быть несколько выше ожидаемой точности физического эксперимента. При определении критериев и условий роста погрешности долгое время не принималась во внимание погрешность округления. Необходимость гарантированных оценок точности реальных вычислений привела к возникновению интервального анализа. Оптимальным алгоритмом считается алгоритм с минимальной погрешностью или с минимальным числом операций при заданной погрешности. При этом разрабатывается теория параллельных вычислительных алгоритмов.
Математический аппарат Символически задача поиска неизвестной величины записывается в виде . Для отыскания в вычислительной математике используют одну или несколько замен пространств, в которых определены величины , , или функции , чтобы сделать вычисления более удобными. Получившаяся новая задача должна иметь решение, близкое к решению исходной задачи. Например, при вычислении интеграла , непрерывную функцию на отрезке можно всегда заменить полиномом , для которого интеграл легко определяется; или же заменить интеграл конечной суммой и решать получившуюся задачу. Для того чтобы осуществить подобную замену, необходимо отыскать конечное множество элементов, хорошо аппроксимирующих основное пространство. Последнее условие накладывает ограничения на метрическое пространство. Основным ограничением является наличие -сети, из которого вытекает компактность пространства в себе и сепарабельность. Вместе с тем, это ограничение не является обязательным. Современные методы функционального анализа позволяют выбрать метрические пространства, наиболее подходящие условиям задачи.
При использовании численных методов возникает несколько видов погрешностей. При приближении одного числа другим возникает погрешность округления, погрешность связанная с неточными начальными данными называется неустранимой, кроме того, в связи с заменой исходной задачи на приближённую существует погрешность метода. Полная погрешность при этом складывается из погрешности метода и погрешности вычислений, иными словами, вместо уравнения решается уравнения , точность решения которого определяется по формуле
Для определения величины погрешности пользуются понятиями абсолютной и относительной погрешности, а также предельной абсолютной и относительной погрешности, при этом теория погрешностей определяет изменение величин погрешностей при различных арифметических действиях. Наряду с методами точной оценки погрешностей, в результате которых определяются предельные величины погрешностей, используют статистические методы, позволяющие определить возможность достижения отдельных погрешностей, а также учитывают математические характеристики случайных ошибок, связанных с отклонением от заданных условий опыта, когда по нескольким результатам измерения физической величины определяется её приближённое значение.
Основные способы приближения функций
Интерполяция
Для получения значения функции , заданной таблицей значений, на промежуточных значениях аргумента строят приближённую функцию , которая в заданных точках , которые называются узлами интерполирования, принимает значения , а в остальных точках принадлежат области определения функции. Чаще всего приближённая функция строится в виде алгебраического многочлена, включающего первые элементов линейно независимой системы. На практике в качестве элементов линейно независимой системы используют последовательность степеней : , тригонометрических функций: , показательных функций: .
Для построения интерполирующей функции в таком случае необходимо решить систему из уравнений с неизвестными. На получившуюся матрицу системы накладываются определённые условия: ранг матрицы должен быть равен , а — чтобы гарантировать условие линейной независимости, — чтобы решение задачи было однозначным, определитель матрицы — чтобы существовало решение и притом единственное. Построение интерполяционного многочлена Лагранжа является базовым методом решения подобного рода задач, очень ресурсоёмким и трудно расширяемым.
Следующим шагом является введение понятия разделённой разности -го порядка на базе отношений разности значения функции в соседних узлах к расстоянию между узлами, которая в силу своего определения обладает рядом полезных свойств, в частности разделённые разности порядка от многочлена степени имеют степень , то есть разности порядка постоянны, а разности более высокого порядка равны . Разделённые разности позволяют переписать интерполяционный многочлен Лагранжа в виде, более удобном для вычислений. Новая формула носит название интерполяционного многочлена Ньютона, в случае равных промежутков формула значительно упрощается. С использованием разделённых разностей строятся интерполяционные формулы Гаусса, Стирлинга, Бесселя, Эверетта. В общем случае разделённые разности сначала убывают с повышением порядка, а затем начинают снова расти, иными словами, нет смысла использовать разности высоких порядков в вычислениях. При этом возникает вопрос сходимости интерполяционного процесса, для решения которого привлекаются различные методы математического анализа.
Равномерные приближения При решении практических задач необходимо многократно вычислять значения заданной функции, что в общем случае является ресурсоёмкой операцией. Возникает необходимость нахождения функции наилучшего равномерного приближения. Для приближения функции в линейном нормированном пространстве образуют подпространство размерности всевозможных линейных комбинаций, для которых опеределена норма и существует её точная нижняя грань. Элемент, в котором эта грань достигается называют элементом наилучшего приближения, или проекцией. Можно доказать что в подпространстве всегда существует элемент наилучшего приближения, а при условии строгой нормированности пространства такой элемент является единственным. В пространстве непрерывных функций с нормой
также существует элемент наилучшего приближения, но условием его единственности является наличие не более различных нулей обобщённого многочлена на отрезке (Многочлены Чебышёва).
Теория функций применима к системе степенных функций, так как она является системой Чебышёва на любом отрезке. Согласно теореме Вейерштрасса, при увеличении размерности подпространства () разность между проекцией и заданной функцией стремится к нулю. Порядок этого приближения зависит от структурных особенностей функции, его можно определить с помощью многочленов Бернштейна. Система тригонометрических функций также обладает свойствами системы Чебышёва на отрезке , для неё также разность между проекцией и заданной функцией стремится к нулю.