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

(перенаправлено с «Численный метод»)

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

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

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

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

Методология править

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

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

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

Символически задача поиска неизвестной величины записывается в виде  . Для отыскания   в вычислительной математике используют одну или несколько замен пространств, в которых определены величины  ,  , или функции  , чтобы сделать вычисления более удобными. Получившаяся новая задача   должна иметь решение, близкое к решению исходной задачи. Например, при вычислении интеграла  , непрерывную функцию на отрезке   можно всегда заменить полиномом  , для которого интеграл легко определяется; или же заменить интеграл конечной суммой   и решать получившуюся задачу. Для того чтобы осуществить подобную замену, необходимо отыскать конечное множество элементов, хорошо аппроксимирующих основное пространство. Последнее условие накладывает ограничения на метрическое пространство. Основным ограничением является наличие  -сети, из которого вытекает компактность пространства в себе и сепарабельность. Вместе с тем, это ограничение не является обязательным. Современные методы функционального анализа позволяют выбрать метрические пространства, наиболее подходящие условиям задачи[7].

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

 

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

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

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

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

Для построения интерполирующей функции в таком случае необходимо решить систему из   уравнений с   неизвестными. На получившуюся матрицу системы накладываются определённые условия: ранг матрицы должен быть равен  , а   — чтобы гарантировать условие линейной независимости,   — чтобы решение задачи было однозначным, определитель матрицы   — чтобы существовало решение и притом единственное[13]. Построение интерполяционного многочлена Лагранжа   является базовым методом решения подобного рода задач, очень ресурсоёмким и трудно расширяемым[14].

Следующим шагом является введение понятия разделённой разности  -го порядка на базе отношений разности значения функции в соседних узлах к расстоянию между узлами, которая в силу своего определения обладает рядом полезных свойств, в частности разделённые разности порядка   от многочлена степени   имеют степень  , то есть разности порядка   постоянны, а разности более высокого порядка равны  [15]. Разделённые разности позволяют переписать интерполяционный многочлен Лагранжа в виде, более удобном для вычислений. Новая формула носит название интерполяционного многочлена Ньютона[16], в случае равных промежутков формула значительно упрощается[17]. С использованием разделённых разностей строятся интерполяционные формулы Гаусса, Стирлинга, Бесселя, Эверетта[18]. В общем случае разделённые разности сначала убывают с повышением порядка, а затем начинают снова расти, иными словами, нет смысла использовать разности высоких порядков в вычислениях[19]. При этом возникает вопрос сходимости интерполяционного процесса, для решения которого привлекаются различные методы математического анализа[20].

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

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

При решении практических задач необходимо многократно вычислять значения заданной функции, что в общем случае является ресурсоёмкой операцией. Возникает необходимость нахождения функции наилучшего равномерного приближения[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].

См. также править

Примечания править

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

Ссылки править