Численные методы
Численные (вычислительные) методы — методы решения математических задач в численном виде[1].
Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.
Многие численные методы являются частью библиотек математических программ[2]. В системе подготовки инженеров технических специальностей являются важной составляющей.
Основами для вычислительных методов являются:
- решение систем линейных уравнений;
- интерполирование и приближённое вычисление функций;
- численное интегрирование;
- численное решение системы нелинейных уравнений;
- численное решение обыкновенных дифференциальных уравнений;
- численное решение уравнений в частных производных (уравнений математической физики);
- решение задач оптимизации.
Методология
Все задачи вычислительной математики решаются в следующей последовательности[3]:
- Исходная математическая задача заменяется другой задачей — вычислительным алгоритмом. Основными требованиями к вычислительному алгоритму являются: высокая точность, устойчивость и экономичность. При переходе к дискретной модели появляется погрешность аппроксимации, а при реализации вычислений — погрешность округления, поэтому для реальных вычислительных алгоритмов проводится анализ погрешностей и устойчивости вычислительного алгоритма[2]. В современной науке для решения задач прикладной математики формулируется математическая модель в терминах интегральных и дифференциальных уравнений функций непрерывного аргумента. Переход от континуальной к дискретной математической модели осуществляется заменой функций непрерывного аргумента функциями дискретного аргумента. В получившихся конечно-разностных уравнениях интеграл и производная представлены конечной суммой и разностным отношением, соответственно[2]. Получившаяся модель представляет собой систему алгебраических уравнений, для решения которой с определённой точностью составляется вычислительный алгоритм, который реализуется на вычислительных машинах[2][4]. При решении больших систем необходимо вычислять собственные значения и вектора матриц, сводить нелинейные системы уравнений к линейным. Для некоторых задач (нейронная физика, физика плазмы, экономика) модель строится непосредственно на статистической выборке или на крупных объектах. Кроме того, строятся нерегулярные системы, для которых численные методы сочетаются с теорией графов. Отдельный класс представляют некорректно поставленные задачи[2].
- Вычислительный алгоритм содержит параметр , которого нет в исходной задаче;
- Выбором этого параметра можно добиться любой близости решения второй задачи к решению первой. Для многих важных классов задач разработаны разнообразные численные методы решения. По способу дискретизации численные методы делятся на проекционные и конечно-разностные, по способу решения — на прямые и итерационные. В методах конечных разностей ставится задача определить значения функции на дискретном множестве точек, в то время как в проекционных методах функция представлена линейной комбинацией элементов. При этом дискретная функция также может рассматриваться как линейная комбинация полиномов. Прямые методы решения обладают слабой устойчивостью, в то время как итерационные методы более устойчивы и обеспечивают быструю сходимость[2].
- Неточная реализация алгоритма, вызванная округлениями при вычислениях, не меняет существенно его свойств. Необходимо помнить, что вычислительная машина выполняет только четыре основных арифметических операции[5]. Точность решения при этом должна быть несколько выше ожидаемой точности физического эксперимента[6]. При определении критериев и условий роста погрешности долгое время не принималась во внимание погрешность округления. Необходимость гарантированных оценок точности реальных вычислений привела к возникновению интервального анализа. Оптимальным алгоритмом считается алгоритм с минимальной погрешностью или с минимальным числом операций при заданной погрешности. При этом разрабатывается теория параллельных вычислительных алгоритмов[2].
Математический аппарат
Символически задача поиска неизвестной величины записывается в виде . Для отыскания в вычислительной математике используют одну или несколько замен пространств, в которых определены величины , , или функции , чтобы сделать вычисления более удобными. Получившаяся новая задача должна иметь решение, близкое к решению исходной задачи. Например, при вычислении интеграла , непрерывную функцию на отрезке можно всегда заменить полиномом , для которого интеграл легко определяется; или же заменить интеграл конечной суммой и решать получившуюся задачу. Для того чтобы осуществить подобную замену, необходимо отыскать конечное множество элементов, хорошо аппроксимирующих основное пространство. Последнее условие накладывает ограничения на метрическое пространство. Основным ограничением является наличие -сети, из которого вытекает компактность пространства в себе и сепарабельность. Вместе с тем, это ограничение не является обязательным. Современные методы функционального анализа позволяют выбрать метрические пространства, наиболее подходящие условиям задачи[7].
При использовании численных методов возникает несколько видов погрешностей. При приближении одного числа другим возникает погрешность округления, погрешность связанная с неточными начальными данными называется неустранимой, кроме того, в связи с заменой исходной задачи на приближённую существует погрешность метода. Полная погрешность при этом складывается из погрешности метода и погрешности вычислений, иными словами, вместо уравнения решается уравнения , точность решения которого определяется по формуле[8]
Для определения величины погрешности пользуются понятиями абсолютной и относительной погрешности, а также предельной абсолютной и относительной погрешности, при этом теория погрешностей определяет изменение величин погрешностей при различных арифметических действиях[9]. Наряду с методами точной оценки погрешностей, в результате которых определяются предельные величины погрешностей, используют статистические методы, позволяющие определить возможность достижения отдельных погрешностей[10], а также учитывают математические характеристики случайных ошибок, связанных с отклонением от заданных условий опыта, когда по нескольким результатам измерения физической величины определяется её приближённое значение[11].
Основные способы приближения функций
Интерполяция
Для получения значения функции , заданной таблицей значений, на промежуточных значениях аргумента строят приближённую функцию , которая в заданных точках , которые называются узлами интерполирования, принимает значения , а в остальных точках принадлежат области определения функции. Чаще всего приближённая функция строится в виде алгебраического многочлена, включающего первые элементов линейно независимой системы. На практике в качестве элементов линейно независимой системы используют последовательность степеней : , тригонометрических функций: , показательных функций: [12].
Для построения интерполирующей функции в таком случае необходимо решить систему из уравнений с неизвестными. На получившуюся матрицу системы накладываются определённые условия: ранг матрицы должен быть равен , а — чтобы гарантировать условие линейной независимости, — чтобы решение задачи было однозначным, определитель матрицы — чтобы существовало решение и притом единственное[13]. Построение интерполяционного многочлена Лагранжа является базовым методом решения подобного рода задач, очень ресурсоёмким и трудно расширяемым[14].
Следующим шагом является введение понятия разделённой разности -го порядка на базе отношений разности значения функции в соседних узлах к расстоянию между узлами, которая в силу своего определения обладает рядом полезных свойств, в частности разделённые разности порядка от многочлена степени имеют степень , то есть разности порядка постоянны, а разности более высокого порядка равны [15]. Разделённые разности позволяют переписать интерполяционный многочлен Лагранжа в виде, более удобном для вычислений. Новая формула носит название интерполяционного многочлена Ньютона[16], в случае равных промежутков формула значительно упрощается[17]. С использованием разделённых разностей строятся интерполяционные формулы Гаусса, Стирлинга, Бесселя, Эверетта[18]. В общем случае разделённые разности сначала убывают с повышением порядка, а затем начинают снова расти, иными словами, нет смысла использовать разности высоких порядков в вычислениях[19]. При этом возникает вопрос сходимости интерполяционного процесса, для решения которого привлекаются различные методы математического анализа[20].
Равномерные приближения
При решении практических задач необходимо многократно вычислять значения заданной функции, что в общем случае является ресурсоёмкой операцией. Возникает необходимость нахождения функции наилучшего равномерного приближения[21]. Для приближения функции в линейном нормированном пространстве образуют подпространство размерности всевозможных линейных комбинаций, для которых опеределена норма и существует её точная нижняя грань. Элемент, в котором эта грань достигается называют элементом наилучшего приближения, или проекцией[22]. Можно доказать что в подпространстве всегда существует элемент наилучшего приближения[23], а при условии строгой нормированности пространства такой элемент является единственным[24]. В пространстве непрерывных функций с нормой
также существует элемент наилучшего приближения[25], но условием его единственности является наличие не более различных нулей обобщённого многочлена на отрезке (Многочлены Чебышёва)[26].
Теория функций применима к системе степенных функций, так как она является системой Чебышёва на любом отрезке[27]. Согласно теореме Вейерштрасса, при увеличении размерности подпространства () разность между проекцией и заданной функцией стремится к нулю[28]. Порядок этого приближения зависит от структурных особенностей функции, его можно определить с помощью многочленов Бернштейна[29]. Система тригонометрических функций также обладает свойствами системы Чебышёва на отрезке , для неё также разность между проекцией и заданной функцией стремится к нулю[30].
Несмотря на показанное существование многочлена наилучшего приближения, способов его точного построения не существует. Вместо этого используют несколько способов приближённого построения многочленов наилучшего равномерного приближения[31].
Среднеквадратичные приближения
Во многих случаях требование равномерного приближения является избыточным и достаточно «интегральной» близости функций, кроме того значения приближённых функций, полученные из эксперимента, несут на себе случайные погрешности, а требовать совпадения приближающей и приближаемой функции, если последняя содержит неточности, нецелесообразно. Метод среднеквадратичного приближения принимает за меру близости следующую величину
что позволяет отказаться от интерполяции подынтегральной функции и требования непрерывности, сохранив только требования интегрируемости с квадратом[32].
Численное дифференцирование и интегрирование
Уравнение вида , определённое на функциональном пространстве, может содержать операторы дифференцирования и интегрирования, для которых невозможно найти точное решение. Методы численного дифференцирования и интегрирования основаны на интерполяции[33].
Производную основной функции считают приближённо равной производной интерполирующей функции, при этом производная остаточного члена интерполяционной формулы может быть велика, особенно для производных высших порядков[34]. Формулы численного дифференцирования во многом основаны на непосредственном дифференцировании интерполяционных формул Ньютона[35], Гаусса, Стирлинга и Бесселя[36], построенных на распределённых разностях, но есть и безразностные формулы. В частности, когда для численного дифференциала используется непосредственно формула Лагранжа для равных промежутков[37], метод неопределённых коэффициентов и другие[38].
В случае интегрирования, само определение интеграла говорит о возможности его замены интегральной суммой, но этот приём обладает медленной сходимостью и мало пригоден. Интеграл от основной функции считают приближённо равным интегралу от интерполирующей функции и в дальнейшем используют интерполяционные формулы с кратными узлами[39]. Использование в качестве подынтегрального выражения интерполяционного многочлена Лагранжа для равных промежутков приводит к формулам Ньютона — Котеса[40] и её частным случаям, формуле трапеций, когда кривая подынтегрального выражения заменяется хордой и интеграл равен площади трапеции, и формуле Симпсона, когда кривая подынтегрального выражения заменяется параболой, проходящей через три точки[41]. Отказавшись от требования равных промежутков с помощью интерполяционного многочлена Лагранжа можно получить более точные формулы численного интегрирования, в частности формулы Гаусса[42], формулы Эрмита[43], формулы Маркова[44], формулы Чебышёва[45]. Квадратурные процессы, построенные на интерполяционных формулах Гаусса, всегда сходятся, в то время как формулы Ньютона — Котеса этим свойствам в общем случае не обладают[46].
Существуют и другие способы численного интегрирования, основным из которых является использование формул Эйлера, в которых замена переменных и последующее интегрирование по частям приводят к формуле численного интегрирования трапецией и поправочного члена, к которому повторно применяется замена переменных и интегрирование по частям. В общем случае формула Эйлера использует в качестве коэффициентов числа и многочлены Бернулли[47]. Вопрос применения того или иного метода численного интегрирования зависит от таких факторов, как вычислительные средства, требуемая точность, способ задания подынтегральной функции. Для ручных вычислений рекомендуется использовать формулы, содержащие разности, в то время как при автоматических вычислениях — безразностные формулы, в особенности формулы Гаусса[48].
Для приближённого вычисления кратных интегралов повторно применяют формулы численного интегрирования однократных интегралов, при этом в зависимости от особенностей функции для разных интегралов можно использовать разные формулы. При использовании данного метода необходимо вычислять подынтегральную функцию в большом числе точек, поэтому целесообразно использовать формулы Гаусса и Чебышёва, которые являются более точными[49]. Другим способом является замена подынтегральной функции интерполяционным многочленом от двух или несколько переменных[50]. Люстерник и Диткин предложили использовать формулы Маклорена для приближённого вычисления кратного интеграла[51]. Вместе с тем, при увеличении кратности интеграла резко растёт число точек, для которых необходимо знать значения подынтегральной функции, чтобы пользоваться методами, основанными на интерполяции. Для вычисления кратных интегралов чаще пользуются вероятностными методами Монте-Карло, при этом необходимость получения равновозможных последовательностей создаёт дополнительные погрешности, которые трудно оценить[52].
Решение систем линейных алгебраических уравнений
Существует две группы методов решения систем линейных алгебраических уравнений: точные методы позволяют с помощью конечного числа операций получить точные значения неизвестных и включают преобразование системы к простому виду и решение упрощённой системы; методы последовательных приближений на основе начальных приближений позволяют получить «улучшенные» приближённые значения, для которых следует последовательно повторить операцию «улучшения»; методы Монте-Карло позволяют на основании математического ожидания случайных величин получить решение системы[53].
Известный из школьного курса алгебры метод исключения позволяет свести матрицу системы к диагональному или треугольному виду[54]. Схема исключения Гаусса с выбором главного элемента, который необходим чтобы уменьшить вычислительную погрешность, включает прямой ход (собственно процесс исключения) и обратный ход (решение системы с треугольной матрицей)[55]. Её компактный вариант используется для определения обратной матрицы, что может быть полезно если в системе линейных уравнений меняется только правая часть[56] и для вычисления определителей[57]. Схема Жордана позволяет облегчить обратный ход[58], а в схеме без обратного хода, которая основана на преобразовании клеточной матрицы , последний и не требуется[59]. Условие симметричности матрицы позволяет сделать ряд упрощений и воспользоваться методом квадратного корня, в котором матрица системы представляется как произведение нижней треугольной матрицы на транспонированную по отношению к ней матрицу, в котором элементы треугольных матриц определяются по формулам через произведения элементы первоначальной матрицы (при отсутствии условия положительно определённой матрицы некоторые формулы могут содержать мнимые элементы), а система затем решается в два этапа через решение вспомогательных систем построенных на треугольных матрицах[60]. Существуют также метод ортогонализации, основанный на свойствах скалярного произведения[61], метод сопряжённых градиентов, при котором строится вспомогательная функция, которая образует семейство эллипсоидов с общим центром и для которой необходимо найти вектор, при котором она принимает минимальное значение[62]. Для матриц высокого порядка применяют метод разбиения на клетки, когда задачу сводят к решению задач для матриц низших порядков[63].
В случае последовательных приближений используется рекуррентная формула
где — функция, которая зависит от матрицы системы, правой части, номера приближения и предыдущих приближений , где — начальный вектор. При этом считается, что метод имеет первый порядок, если функция зависит только от последнего из предыдущих приближений. В этом случае формула может быть записана в виде , где . Для удобства вычислений желательно использовать диагональную или треугольную матрицу , которую будет удобно обратить. В зависимости от выбора этой матрицы методы называют полношаговыми и одношаговыми, соответственно[64]. К линейным полношаговым методам относят простую итерацию[65], метод Ричардсона[66]; к линейным одношаговым методам — метод Зейделя[67], релаксационный метод[68]; к нелинейным методам — метод скорейшего спуска[69].
Решение алгебраических уравнений высших степеней и трансцендентных уравнений
Решения алгебраического уравнения , где в левой части находится функция действительного или комплексного аргумента, лежит в комплексной плоскости[70]. Для его определения в первую очередь необходимо заключить каждый корень в достаточно малую область, то есть отделить его, для чего часто используют графические методы[71]. Для действительных корней используют также обобщённое правило Декарта, теорему Штурма[72], метод Фурье[73]. Широкое применение нашёл метод квадратного корня, или метод Лобачевского[74]. В его основной формулировке он применим к действительным корням[75], далеко отстоящим друг от друга, но существуют обобщения как на комплексные[76], так и на действительные равные или близкие корни[77].
Итерационные методы решения алгебраических уравнений делятся на стационарные, когда функции ставится в соответствие другая функция с теми же корнями, не зависящая от номера итерации[78], и нестационарные, когда функция может зависеть от номера итерации. К простейшим стационарным итерационным методам относят метод секущих (или метод линейного интерполирования) и метод касательных (или метод Ньютона), которые являются методами первого и второго порядка, соответственно. Комбинация этих методов, при которой последовательные приближения лежат по разные стороны от корня, позволяет достичь более быстрой сходимости[79]. Метод Чебышева, основанный на разложении обратной функции по формуле Тейлора, позволяет построить методы более высоких порядков, обладающие очень быстрой сходимостью[80]. Существуют также метод, основанный на теореме Кёнига[81], и метод Эйткена[82]. Для доказательства сходимости итерационных методов используется принцип сжатых отображений[83].
См. также
Примечания
- Муха В. С. Вычислительные методы и компьютерная алгебра: учеб.-метод. пособие. — 2-е изд., испр. и доп. — Минск: БГУИР, 2010. — 148 с.: ил, ISBN 978-985-488-522-3, УДК 519.6 (075.8), ББК 22.19я73, М92
- Энциклопедия кибернетики / Глушков В. М., Амосов Н. М., Артеменко И. А.. — Киев, 1974. — Т. 2. — С. 530—532.
- Дьяченко В. Ф. Основные понятия вычислительной математики. — М., Наука, 1972. — Тираж 45000 экз. — С. 10
- Калиткин, 1978, с. 3.
- Березин, Жидков, т.1, 1962, с. 33.
- Калиткин, 1978, с. 2.
- Березин, Жидков, т.1, 1962, с. 13—16.
- Березин, Жидков, т.1, 1962, с. 57—58.
- Березин, Жидков, т.1, 1962, с. 53.
- Березин, Жидков, т.1, 1962, с. 63.
- Березин, Жидков, т.1, 1962, с. 65.
- Березин, Жидков, т.1, 1962, с. 77—79.
- Березин, Жидков, т.1, 1962, с. 79—80.
- Березин, Жидков, т.1, 1962, с. 84—87.
- Березин, Жидков, т.1, 1962, с. 102—106.
- Березин, Жидков, т.1, 1962, с. 106—109.
- Березин, Жидков, т.1, 1962, с. 112.
- Березин, Жидков, т.1, 1962, с. 125—135.
- Березин, Жидков, т.1, 1962, с. 111—112.
- Березин, Жидков, т.1, 1962, с. 149—150.
- Березин, Жидков, т.1, 1962, с. 331—333.
- Березин, Жидков, т.1, 1962, с. 333—334.
- Березин, Жидков, т.1, 1962, с. 334—336.
- Березин, Жидков, т.1, 1962, с. 336—337.
- Березин, Жидков, т.1, 1962, с. 337.
- Березин, Жидков, т.1, 1962, с. 337—342.
- Березин, Жидков, т.1, 1962, с. 347—348.
- Березин, Жидков, т.1, 1962, с. 349—352.
- Березин, Жидков, т.1, 1962, с. 352—355.
- Березин, Жидков, т.1, 1962, с. 355—357.
- Березин, Жидков, т.1, 1962, с. 364—365.
- Березин, Жидков, т.1, 1962, с. 386—387.
- Березин, Жидков, т.1, 1962, с. 217.
- Березин, Жидков, т.1, 1962, с. 217—220.
- Березин, Жидков, т.1, 1962, с. 220—226.
- Березин, Жидков, т.1, 1962, с. 226—228.
- Березин, Жидков, т.1, 1962, с. 230—234.
- Березин, Жидков, т.1, 1962, с. 234—236.
- Березин, Жидков, т.1, 1962, с. 237—240.
- Березин, Жидков, т.1, 1962, с. 240—243.
- Березин, Жидков, т.1, 1962, с. 243—254.
- Березин, Жидков, т.1, 1962, с. 254—258.
- Березин, Жидков, т.1, 1962, с. 264—266.
- Березин, Жидков, т.1, 1962, с. 266—269.
- Березин, Жидков, т.1, 1962, с. 269—276.
- Березин, Жидков, т.1, 1962, с. 279—284.
- Березин, Жидков, т.1, 1962, с. 289—297.
- Березин, Жидков, т.1, 1962, с. 305—306.
- Березин, Жидков, т.1, 1962, с. 315—318.
- Березин, Жидков, т.1, 1962, с. 318—320.
- Березин, Жидков, т.1, 1962, с. 320—324.
- Березин, Жидков, т.1, 1962, с. 324—325.
- Березин, Жидков, т.2, 1959, с. 9—10.
- Березин, Жидков, т.2, 1959, с. 10.
- Березин, Жидков, т.2, 1959, с. 10—13.
- Березин, Жидков, т.2, 1959, с. 17—18.
- Березин, Жидков, т.2, 1959, с. 18—19.
- Березин, Жидков, т.2, 1959, с. 19—20.
- Березин, Жидков, т.2, 1959, с. 20—23.
- Березин, Жидков, т.2, 1959, с. 23—25.
- Березин, Жидков, т.2, 1959, с. 25—30.
- Березин, Жидков, т.2, 1959, с. 30—31.
- Березин, Жидков, т.2, 1959, с. 41.
- Березин, Жидков, т.2, 1959, с. 54—56.
- Березин, Жидков, т.2, 1959, с. 56—59.
- Березин, Жидков, т.2, 1959, с. 59—61.
- Березин, Жидков, т.2, 1959, с. 61—62.
- Березин, Жидков, т.2, 1959, с. 66—67.
- Березин, Жидков, т.2, 1959, с. 67—73.
- Березин, Жидков, т.2, 1959, с. 76.
- Березин, Жидков, т.2, 1959, с. 76—79.
- Березин, Жидков, т.2, 1959, с. 83—88.
- Березин, Жидков, т.2, 1959, с. 88—94.
- Березин, Жидков, т.2, 1959, с. 103.
- Березин, Жидков, т.2, 1959, с. 103—107.
- Березин, Жидков, т.2, 1959, с. 107—114.
- Березин, Жидков, т.2, 1959, с. 115.
- Березин, Жидков, т.2, 1959, с. 128—129.
- Березин, Жидков, т.2, 1959, с. 135—140.
- Березин, Жидков, т.2, 1959, с. 140—143.
- Березин, Жидков, т.2, 1959, с. 143—146.
- Березин, Жидков, т.2, 1959, с. 146—148.
- Березин, Жидков, т.2, 1959, с. 129—134.
Литература
- Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. — 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