Русская Википедия:Численные методы

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

Методология

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

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

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

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

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

<math>y-\bar{\bar{y}}=(y-\bar{y})+(\bar{y}-\bar{\bar{y}})</math>

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

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

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

Шаблон:Main Для получения значения функции <math>f(x)</math>, заданной таблицей значений, на промежуточных значениях аргумента строят приближённую функцию <math>\varphi(x)</math>, которая в заданных точках <math>x_0,\dots,x_m</math>, которые называются узлами интерполирования, принимает значения <math>f(x_0),\dots,f(x_m)</math>, а в остальных точках принадлежат области определения функции. Чаще всего приближённая функция строится в виде алгебраического многочлена, включающего первые <math>n+1</math> элементов линейно независимой системы. На практике в качестве элементов линейно независимой системы используют последовательность степеней <math>x</math>: <math>1,x,x^2,\dots</math>, тригонометрических функций: <math>1,\sin x, \cos x, \sin 2x, \dots</math>, показательных функций: <math>1, e^{\alpha_1 x}, e^{\alpha_2 x},\dots</math>Шаблон:Sfn.

Для построения интерполирующей функции в таком случае необходимо решить систему из <math>m+1</math> уравнений с <math>n+1</math> неизвестными. На получившуюся матрицу системы накладываются определённые условия: ранг матрицы должен быть равен <math>m+1</math>, а <math>n \ge m</math> — чтобы гарантировать условие линейной независимости, <math>n=m</math> — чтобы решение задачи было однозначным, определитель матрицы <math>\Delta \ne 0</math> — чтобы существовало решение и притом единственноеШаблон:Sfn. Построение интерполяционного многочлена Лагранжа <math>L_n(x)</math> является базовым методом решения подобного рода задач, очень ресурсоёмким и трудно расширяемымШаблон:Sfn.

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

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

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

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

<math>\lVert f \rVert = \sup_{x \in {[a,b)}} |f(x)|</math>

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

Файл:Многочлены Чебышёва U.gif
Многочлены Чебышёва

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

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

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

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

<math>\delta = \sqrt{\int^b_a p(x)[f(x)-\phi (x)]^2 dx},</math>

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

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

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

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

Файл:Simpson rule.png
Численное интегрирование по формуле Симпсона

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

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

Файл:Mc integration.JPG
Численное интегрирование методами Монте-Карло

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

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

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

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

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

<math>\overline x_{k+1}=F_k(\overline x_0,\dots,\overline x_k),</math>

где <math>F_k</math> — функция, которая зависит от матрицы системы, правой части, номера приближения и предыдущих приближений <math>\overline x_0,\dots,\overline x_k</math>, где <math>\overline x_0</math> — начальный вектор. При этом считается, что метод имеет первый порядок, если функция зависит только от последнего из предыдущих приближений. В этом случае формула <math>\overline x_{k+1} =B_k \overline x_k +\overline c_k</math> может быть записана в виде <math>D_k \overline x_{k+1} + E_k \overline x_k = \overline b</math>, где <math>D_k+E_k=A</math>. Для удобства вычислений желательно использовать диагональную или треугольную матрицу <math>D_k</math>, которую будет удобно обратить. В зависимости от выбора этой матрицы методы называют полношаговыми и одношаговыми, соответственноШаблон:Sfn. К линейным полношаговым методам относят простую итерациюШаблон:Sfn, метод РичардсонаШаблон:Sfn; к линейным одношаговым методам — метод ЗейделяШаблон:Sfn, релаксационный методШаблон:Sfn; к нелинейным методам — метод скорейшего спускаШаблон:Sfn.

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

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

Ссылки

Шаблон:Вс Шаблон:Разделы математики

  1. Муха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010. — 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92
  2. 2,0 2,1 2,2 2,3 2,4 2,5 2,6 Ошибка цитирования Неверный тег <ref>; для сносок KibEnc не указан текст
  3. Дьяченко В. Ф. Основные понятия вычислительной математики. — М., Наука, 1972. — Тираж 45000 экз. — С. 10