Численные методы

Численные (вычислительные) методы — методы решения математических задач в численном виде.

Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.

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

Основами для вычислительных методов являются:

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

История

Вавилонская глиняная табличка YBC 7289 с пометками. Диагональ отображает приближение ${\sqrt {2}}$ четырьмя 60-ричными цифрами, 1 24 51 10

Вавилонские математики (II тысячелетие до н. э.) разработали для извлечения квадратного корня особый численный метод.

Вавилонская глиняная табличка YBC 7289 из вавилонской коллекции Йельского университета была создана между 1800 и 1600 годами до н. э. и демонстрирует √2 и √2/2 соответственно в шестидесятиричной системе счисления: 1;24,51,10 и 0;42,25,35 на квадрате, пересечённом двумя диагоналями. (1;24,51,10) по основанию 60 соответствует 1,41421296, что является правильным значением с точностью до 5 десятичных знаков: $1+24/60+51/60^{2}+10/60^{3}=1{,}41421296.$

Сложные проценты вычислялись с помощью метода линейной интерполяции.

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

В древнем Китае использовался метод ложных положений , а также применялся метод фан-чен аналогичный методу Гаусса.

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

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

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

В Новое время численные методы продолжали развиваться: Николай Кузанский нашел формулу приближенного спрямления окружност, Рене Декарт решая задачу по преломлению света нашел овалы Декарта, Бернулли предложил метод изоклин. Исаак Ньютон предложил метод решения алгебраических уравнений (метод Ньютона).

Методология

См. также: Вычислительная математика

Все задачи вычислительной математики решаются в следующей последовательности:

1. Исходная математическая задача заменяется другой задачей — вычислительным алгоритмом. Основными требованиями к вычислительному алгоритму являются: высокая точность, устойчивость и экономичность. При переходе к дискретной модели появляется погрешность аппроксимации, а при реализации вычислений — погрешность округления, поэтому для реальных вычислительных алгоритмов проводится анализ погрешностей и устойчивости вычислительного алгоритма. В современной науке для решения задач прикладной математики формулируется математическая модель в терминах интегральных и дифференциальных уравнений функций непрерывного аргумента. Переход от континуальной к дискретной математической модели осуществляется заменой функций непрерывного аргумента функциями дискретного аргумента. В получившихся конечно-разностных уравнениях интеграл и производная представлены конечной суммой и разностным отношением, соответственно. Получившаяся модель представляет собой систему алгебраических уравнений, для решения которой с определённой точностью составляется вычислительный алгоритм, который реализуется на вычислительных машинах. При решении больших систем необходимо вычислять собственные значения и вектора матриц, сводить нелинейные системы уравнений к линейным. Для некоторых задач (нейронная физика, физика плазмы, экономика) модель строится непосредственно на статистической выборке или на крупных объектах. Кроме того, строятся нерегулярные системы, для которых численные методы сочетаются с теорией графов. Отдельный класс представляют некорректно поставленные задачи.
2. Вычислительный алгоритм содержит параметр $N$, которого нет в исходной задаче;
3. Выбором этого параметра $N$ можно добиться любой близости решения второй задачи к решению первой. Для многих важных классов задач разработаны разнообразные численные методы решения. По способу дискретизации численные методы делятся на проекционные и конечно-разностные, по способу решения — на прямые и итерационные. В методах конечных разностей ставится задача определить значения функции на дискретном множестве точек, в то время как в проекционных методах функция представлена линейной комбинацией элементов. При этом дискретная функция также может рассматриваться как линейная комбинация полиномов. Прямые методы решения обладают слабой устойчивостью, в то время как итерационные методы более устойчивы и обеспечивают быструю сходимость.
4. Неточная реализация алгоритма, вызванная округлениями при вычислениях, не меняет существенно его свойств. Необходимо помнить, что вычислительная машина выполняет только четыре основных арифметических операции. Точность решения при этом должна быть несколько выше ожидаемой точности физического эксперимента. При определении критериев и условий роста погрешности долгое время не принималась во внимание погрешность округления. Необходимость гарантированных оценок точности реальных вычислений привела к возникновению интервального анализа. Оптимальным алгоритмом считается алгоритм с минимальной погрешностью или с минимальным числом операций при заданной погрешности. При этом разрабатывается теория параллельных вычислительных алгоритмов.

Математический аппарат

Символически задача поиска неизвестной величины записывается в виде $y=A(x)$. Для отыскания $y$ в вычислительной математике используют одну или несколько замен пространств, в которых определены величины $x$, $y$, или функции $A$, чтобы сделать вычисления более удобными. Получившаяся новая задача ${\bar {y}}={\bar {A}}({\bar {x}})$ должна иметь решение, близкое к решению исходной задачи. Например, при вычислении интеграла $\int _{a}^{b}f(x)dx$, непрерывную функцию на отрезке $[a,b]$ можно всегда заменить полиномом $P(x)$, для которого интеграл легко определяется; или же заменить интеграл конечной суммой $\sum _{i=1}^{n}{f(x_{i})\Delta x_{i}}$ и решать получившуюся задачу. Для того чтобы осуществить подобную замену, необходимо отыскать конечное множество элементов, хорошо аппроксимирующих основное пространство. Последнее условие накладывает ограничения на метрическое пространство. Основным ограничением является наличие $\epsilon$-сети, из которого вытекает компактность пространства в себе и сепарабельность. Вместе с тем, это ограничение не является обязательным. Современные методы функционального анализа позволяют выбрать метрические пространства, наиболее подходящие условиям задачи.

При использовании численных методов возникает несколько видов погрешностей. При приближении одного числа другим возникает погрешность округления, погрешность связанная с неточными начальными данными называется неустранимой, кроме того, в связи с заменой исходной задачи на приближённую существует погрешность метода. Полная погрешность при этом складывается из погрешности метода и погрешности вычислений, иными словами, вместо уравнения $y=A(x)$ решается уравнения ${\bar {\bar {y}}}={\bar {\bar {A}}}({\bar {\bar {x}}})$, точность решения которого определяется по формуле

$y-{\bar {\bar {y}}}=(y-{\bar {y}})+({\bar {y}}-{\bar {\bar {y}}})$

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

Основные способы приближения функций

Интерполяция

Основная статья: Интерполяция

Для получения значения функции $f(x)$, заданной таблицей значений, на промежуточных значениях аргумента строят приближённую функцию $\varphi (x)$, которая в заданных точках $x_{0},\dots ,x_{m}$, которые называются узлами интерполирования, принимает значения $f(x_{0}),\dots ,f(x_{m})$, а в остальных точках принадлежат области определения функции. Чаще всего приближённая функция строится в виде алгебраического многочлена, включающего первые $n+1$ элементов линейно независимой системы. На практике в качестве элементов линейно независимой системы используют последовательность степеней $x$: $1,x,x^{2},\dots$, тригонометрических функций: $1,\sin x,\cos x,\sin 2x,\dots$, показательных функций: $1,e^{\alpha _{1}x},e^{\alpha _{2}x},\dots$.

Для построения интерполирующей функции в таком случае необходимо решить систему из $m+1$ уравнений с $n+1$ неизвестными. На получившуюся матрицу системы накладываются определённые условия: ранг матрицы должен быть равен $m+1$, а $n\geq m$ — чтобы гарантировать условие линейной независимости, $n=m$ — чтобы решение задачи было однозначным, определитель матрицы $\Delta \neq 0$ — чтобы существовало решение и притом единственное. Построение интерполяционного многочлена Лагранжа $L_{n}(x)$ является базовым методом решения подобного рода задач, очень ресурсоёмким и трудно расширяемым.

Следующим шагом является введение понятия разделённой разности $k$-го порядка на базе отношений разности значения функции в соседних узлах к расстоянию между узлами, которая в силу своего определения обладает рядом полезных свойств, в частности разделённые разности порядка $k$ от многочлена степени $n$ имеют степень $n-k$, то есть разности порядка $n$ постоянны, а разности более высокого порядка равны $0$. Разделённые разности позволяют переписать интерполяционный многочлен Лагранжа в виде, более удобном для вычислений. Новая формула носит название интерполяционного многочлена Ньютона, в случае равных промежутков формула значительно упрощается. С использованием разделённых разностей строятся интерполяционные формулы Гаусса, Стирлинга, Бесселя, Эверетта. В общем случае разделённые разности сначала убывают с повышением порядка, а затем начинают снова расти, иными словами, нет смысла использовать разности высоких порядков в вычислениях. При этом возникает вопрос сходимости интерполяционного процесса, для решения которого привлекаются различные методы математического анализа.

Разделённые разности для функции у=2х³-2х²+3х-1

Равномерные приближения

При решении практических задач необходимо многократно вычислять значения заданной функции, что в общем случае является ресурсоёмкой операцией. Возникает необходимость нахождения функции наилучшего равномерного приближения. Для приближения функции в линейном нормированном пространстве образуют подпространство размерности $n+1$ всевозможных линейных комбинаций, для которых опеределена норма и существует её точная нижняя грань. Элемент, в котором эта грань достигается называют элементом наилучшего приближения, или проекцией. Можно доказать что в подпространстве всегда существует элемент наилучшего приближения, а при условии строгой нормированности пространства такой элемент является единственным. В пространстве непрерывных функций с нормой

$\lVert f\rVert =\sup _{x\in {[a,b)}}|f(x)|$

также существует элемент наилучшего приближения, но условием его единственности является наличие не более $n$ различных нулей обобщённого многочлена на отрезке (Многочлены Чебышёва).

Многочлены Чебышёва

Теория функций применима к системе степенных функций, так как она является системой Чебышёва на любом отрезке. Согласно теореме Вейерштрасса, при увеличении размерности подпространства ($n\to \infty$) разность между проекцией и заданной функцией стремится к нулю. Порядок этого приближения зависит от структурных особенностей функции, его можно определить с помощью многочленов Бернштейна. Система тригонометрических функций также обладает свойствами системы Чебышёва на отрезке $[0,2\pi )$, для неё также разность между проекцией и заданной функцией стремится к нулю.

Несмотря на показанное существование многочлена наилучшего приближения, способов его точного построения не существует. Вместо этого используют несколько способов приближённого построения многочленов наилучшего равномерного приближения.

Среднеквадратичные приближения

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

$\delta ={\sqrt {\int _{a}^{b}p(x)[f(x)-\phi (x)]^{2}dx}},$

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

Численное дифференцирование и интегрирование

Уравнение вида $y=A(x)$, определённое на функциональном пространстве, может содержать операторы дифференцирования и интегрирования, для которых невозможно найти точное решение. Методы численного дифференцирования и интегрирования основаны на интерполяции.

Производную основной функции считают приближённо равной производной интерполирующей функции, при этом производная остаточного члена интерполяционной формулы может быть велика, особенно для производных высших порядков. Формулы численного дифференцирования во многом основаны на непосредственном дифференцировании интерполяционных формул Ньютона, Гаусса, Стирлинга и Бесселя, построенных на распределённых разностях, но есть и безразностные формулы. В частности, когда для численного дифференциала используется непосредственно формула Лагранжа для равных промежутков, метод неопределённых коэффициентов и другие.

Численное интегрирование по формуле Симпсона

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

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

Численное интегрирование методами Монте-Карло

Для приближённого вычисления кратных интегралов повторно применяют формулы численного интегрирования однократных интегралов, при этом в зависимости от особенностей функции для разных интегралов можно использовать разные формулы. При использовании данного метода необходимо вычислять подынтегральную функцию в большом числе точек, поэтому целесообразно использовать формулы Гаусса и Чебышёва, которые являются более точными. Другим способом является замена подынтегральной функции интерполяционным многочленом от двух или несколько переменных. Люстерник и Диткин предложили использовать формулы Маклорена для приближённого вычисления кратного интеграла. Вместе с тем, при увеличении кратности интеграла резко растёт число точек, для которых необходимо знать значения подынтегральной функции, чтобы пользоваться методами, основанными на интерполяции. Для вычисления кратных интегралов чаще пользуются вероятностными методами Монте-Карло, при этом необходимость получения равновозможных последовательностей создаёт дополнительные погрешности, которые трудно оценить.

Решение систем линейных алгебраических уравнений

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

Известный из школьного курса алгебры метод исключения позволяет свести матрицу системы к диагональному или треугольному виду. Схема исключения Гаусса с выбором главного элемента, который необходим чтобы уменьшить вычислительную погрешность, включает прямой ход (собственно процесс исключения) и обратный ход (решение системы с треугольной матрицей). Её компактный вариант используется для определения обратной матрицы, что может быть полезно если в системе линейных уравнений меняется только правая часть и для вычисления определителей. Схема Жордана позволяет облегчить обратный ход, а в схеме без обратного хода, которая основана на преобразовании клеточной матрицы ${\begin{pmatrix}A&b\\-I&0\end{pmatrix}}$, последний и не требуется. Условие симметричности матрицы позволяет сделать ряд упрощений и воспользоваться методом квадратного корня, в котором матрица системы представляется как произведение нижней треугольной матрицы на транспонированную по отношению к ней матрицу, в котором элементы треугольных матриц определяются по формулам через произведения элементы первоначальной матрицы (при отсутствии условия положительно определённой матрицы некоторые формулы могут содержать мнимые элементы), а система затем решается в два этапа через решение вспомогательных систем построенных на треугольных матрицах. Существуют также метод ортогонализации, основанный на свойствах скалярного произведения, метод сопряжённых градиентов, при котором строится вспомогательная функция, которая образует семейство эллипсоидов с общим центром и для которой необходимо найти вектор, при котором она принимает минимальное значение. Для матриц высокого порядка применяют метод разбиения на клетки, когда задачу сводят к решению задач для матриц низших порядков.

В случае последовательных приближений используется рекуррентная формула

${\overline {x}}_{k+1}=F_{k}({\overline {x}}_{0},\dots ,{\overline {x}}_{k}),$

где $F_{k}$ — функция, которая зависит от матрицы системы, правой части, номера приближения и предыдущих приближений ${\overline {x}}_{0},\dots ,{\overline {x}}_{k}$, где ${\overline {x}}_{0}$ — начальный вектор. При этом считается, что метод имеет первый порядок, если функция зависит только от последнего из предыдущих приближений. В этом случае формула ${\overline {x}}_{k+1}=B_{k}{\overline {x}}_{k}+{\overline {c}}_{k}$ может быть записана в виде $D_{k}{\overline {x}}_{k+1}+E_{k}{\overline {x}}_{k}={\overline {b}}$, где $D_{k}+E_{k}=A$. Для удобства вычислений желательно использовать диагональную или треугольную матрицу $D_{k}$, которую будет удобно обратить. В зависимости от выбора этой матрицы методы называют полношаговыми и одношаговыми, соответственно. К линейным полношаговым методам относят простую итерацию, метод Ричардсона; к линейным одношаговым методам — метод Зейделя, релаксационный метод; к нелинейным методам — метод скорейшего спуска.

Решение алгебраических уравнений высших степеней и трансцендентных уравнений

Решения алгебраического уравнения $f(z)=0$, где в левой части находится функция действительного или комплексного аргумента, лежит в комплексной плоскости. Для его определения в первую очередь необходимо заключить каждый корень в достаточно малую область, то есть отделить его, для чего часто используют графические методы. Для действительных корней используют также обобщённое правило Декарта, теорему Штурма, метод Фурье. Широкое применение нашёл метод квадратного корня, или метод Лобачевского. В его основной формулировке он применим к действительным корням, далеко отстоящим друг от друга, но существуют обобщения как на комплексные, так и на действительные равные или близкие корни.

Итерационные методы решения алгебраических уравнений делятся на стационарные, когда функции ставится в соответствие другая функция с теми же корнями, не зависящая от номера итерации, и нестационарные, когда функция может зависеть от номера итерации. К простейшим стационарным итерационным методам относят метод секущих (или метод линейного интерполирования) и метод касательных (или метод Ньютона), которые являются методами первого и второго порядка, соответственно. Комбинация этих методов, при которой последовательные приближения лежат по разные стороны от корня, позволяет достичь более быстрой сходимости. Метод Чебышева, основанный на разложении обратной функции по формуле Тейлора, позволяет построить методы более высоких порядков, обладающие очень быстрой сходимостью. Существуют также метод, основанный на теореме Кёнига, и метод Эйткена. Для доказательства сходимости итерационных методов используется принцип сжатых отображений.

См. также

• Метод конечных элементов

Литература

• Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. — 1994.
• История математики, в трёх томах / Под редакцией А. П. Юшкевича. — М.: Наука, 1970—1972.
• Березин И. С., Жидков Н. П. Методы вычислений. — М.: Наука, 1962. — Т. 1.
• Березин И. С., Жидков Н. П. Методы вычислений. — М.: Наука, 1959. — Т. 2.
• Калиткин Н. Н. Численные методы. — М.: Наука, 1978.
• Численные методы : теория и практика : учебное пособие для бакалавров, для студентов высших учебных заведений, обучающихся по направлению подготовки «Математика. Прикладная математика» / У. Г. Пирумов, Гидаспов В.Ю., Иванов И.Э., Ревизников Д. Л., Стрельцов В.Ю., Формалев В.Ф.; Московский авиационный ин-т-нац. исслед. ун-т. — 5-е изд., перераб. и доп. — Москва : Юрайт, 2012. — 421 с. : ил., табл.; 22 см. — (Бакалавр. Базовый курс).; ISBN 978-5-9916-1867-0
• Рыжиков Ю. Вычислительные методы. — СПб.: BHV, 2007. — 400 с. — ISBN 978-5-9775-0137-8

Ссылки

• Научный журнал «Вычислительные методы и программирование. Новые вычислительные технологии»
• Материалы по численным методам
• Численные методы
• Вычислительные методы в прикладной математике, Международный журнал, ISSN 1609-4840