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

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

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

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

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

Методология

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

• Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. — 1994.
• Березин И. С. , Жидков Н. П. Методы вычислений. — М. : Наука , 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