Вычислительные методы

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Методология[править | править вики-текст]

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

Основными требованиями к вычислительному алгоритму являются: высокая точность, устойчивость и экономичность. При переходе к дискретной модели появляется погрешность аппроксимации, а при реализации вычислений — погрешность округления, поэтому для реальных вычислительных алгоритмов проводится анализ погрешностей и устойчивости вычислительного алгоритма[2]. Необходимо помнить, что вычислительная машина выполняет только четыре основных арифметических операции[4]. Точность решения при этом должна быть несколько выше ожидаемой точности физического эксперимента[5]. При определении критериев и условий роста погрешности долгое время не принималась во внимание погрешность округления. Необходимость гарантированных оценок точности реальных вычислений привела к возникновению интервального анализа. Оптимальным алгоритмом считается алгоритм с минимальной погрешностью или с минимальным числом операций при заданной погрешности. При этом разрабатывается теория параллельных вычислительных алгоритмов[2].

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

При решении больших систем необходимо вычислять собственные значения и вектора матриц, сводить нелинейные системы уравнений к линейным. Для некоторых задач (нейронная физика, физика плазмы, экономика) модель строится непосредственно на статистической выборке или на крупных объектах. Кроме того, строятся нерегулярные системы, для которых численные методы сочетаются с теорией графов. Отдельный класс представляют некорректно поставленные задачи[2].

Математический аппарат[править | править вики-текст]

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

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

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

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

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

Интерполяция[править | править вики-текст]

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

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

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

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

Равномерные приближения[править | править вики-текст]

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

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

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

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

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

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

Среднеквадратичные приближения[править | править вики-текст]

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

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

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

Численное дифференцирование и интегрирование[править | править вики-текст]

Уравнение вида y=A(x), определённое на функциональном пространстве, может содержать операторы дифференцирования и интегрирования, для которых невозможно найти точное решение. Методы численного дифференцирования и интегрирования основаны на интерполяции[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], а в схеме без обратного хода, которая основана на преобразовании клеточной матрицы \begin{pmatrix} A & b \\ -I & 0 \end{pmatrix}, последний и не требуется[58]. Условие симметричности матрицы позволяет сделать ряд упрощений и воспользоваться методом квадратного корня, в котором матрица системы представляется как произведение нижней треугольной матрицы на транспонированную по отношению к ней матрицу, в котором элементы треугольных матриц определяются по формулам через произведения элементы первоначальной матрицы (при отсутствии условия положительно определённой матрицы некоторые формулы могут содержать мнимые элементы), а система затем решается в два этапа через решение вспомогательных систем построенных на треугольных матрицах[59]. Существуют также метод ортогонализации, основанный на свойствах скалярного произведения[60], метод сопряжённых градиентов, при котором строится вспомогательная функция, которая образует семейство эллипсоидов с общим центром и для которой необходимо найти вектор, при котором она принимает минимальное значение[61]. Для матриц высокого порядка применяют метод разбиения на клетки, когда задачу сводят к решению задач для матриц низших порядков[62].

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

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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. Калиткин, 1978, с. 3.
  4. Березин, Жидков, т.1, 1962, с. 33.
  5. Калиткин, 1978, с. 2.
  6. Березин, Жидков, т.1, 1962, с. 13—16.
  7. Березин, Жидков, т.1, 1962, с. 57—58.
  8. Березин, Жидков, т.1, 1962, с. 53.
  9. Березин, Жидков, т.1, 1962, с. 63.
  10. Березин, Жидков, т.1, 1962, с. 65.
  11. Березин, Жидков, т.1, 1962, с. 77—79.
  12. Березин, Жидков, т.1, 1962, с. 79—80.
  13. Березин, Жидков, т.1, 1962, с. 84—87.
  14. Березин, Жидков, т.1, 1962, с. 102—106.
  15. Березин, Жидков, т.1, 1962, с. 106—109.
  16. Березин, Жидков, т.1, 1962, с. 112.
  17. Березин, Жидков, т.1, 1962, с. 125—135.
  18. Березин, Жидков, т.1, 1962, с. 111—112.
  19. Березин, Жидков, т.1, 1962, с. 149—150.
  20. Березин, Жидков, т.1, 1962, с. 331—333.
  21. Березин, Жидков, т.1, 1962, с. 333—334.
  22. Березин, Жидков, т.1, 1962, с. 334—336.
  23. Березин, Жидков, т.1, 1962, с. 336—337.
  24. Березин, Жидков, т.1, 1962, с. 337.
  25. Березин, Жидков, т.1, 1962, с. 337—342.
  26. Березин, Жидков, т.1, 1962, с. 347—348.
  27. Березин, Жидков, т.1, 1962, с. 349—352.
  28. Березин, Жидков, т.1, 1962, с. 352—355.
  29. Березин, Жидков, т.1, 1962, с. 355—357.
  30. Березин, Жидков, т.1, 1962, с. 364—365.
  31. Березин, Жидков, т.1, 1962, с. 386—387.
  32. Березин, Жидков, т.1, 1962, с. 217.
  33. Березин, Жидков, т.1, 1962, с. 217—220.
  34. Березин, Жидков, т.1, 1962, с. 220—226.
  35. Березин, Жидков, т.1, 1962, с. 226—228.
  36. Березин, Жидков, т.1, 1962, с. 230—234.
  37. Березин, Жидков, т.1, 1962, с. 234—236.
  38. Березин, Жидков, т.1, 1962, с. 237—240.
  39. Березин, Жидков, т.1, 1962, с. 240—243.
  40. Березин, Жидков, т.1, 1962, с. 243—254.
  41. Березин, Жидков, т.1, 1962, с. 254—258.
  42. Березин, Жидков, т.1, 1962, с. 264—266.
  43. Березин, Жидков, т.1, 1962, с. 266—269.
  44. Березин, Жидков, т.1, 1962, с. 269—276.
  45. Березин, Жидков, т.1, 1962, с. 279—284.
  46. Березин, Жидков, т.1, 1962, с. 289—297.
  47. Березин, Жидков, т.1, 1962, с. 305—306.
  48. Березин, Жидков, т.1, 1962, с. 315—318.
  49. Березин, Жидков, т.1, 1962, с. 318—320.
  50. Березин, Жидков, т.1, 1962, с. 320—324.
  51. Березин, Жидков, т.1, 1962, с. 324—325.
  52. Березин, Жидков, т.2, 1959, с. 9—10.
  53. Березин, Жидков, т.2, 1959, с. 10.
  54. Березин, Жидков, т.2, 1959, с. 10—13.
  55. Березин, Жидков, т.2, 1959, с. 17—18.
  56. Березин, Жидков, т.2, 1959, с. 18—19.
  57. Березин, Жидков, т.2, 1959, с. 19—20.
  58. Березин, Жидков, т.2, 1959, с. 20—23.
  59. Березин, Жидков, т.2, 1959, с. 23—25.
  60. Березин, Жидков, т.2, 1959, с. 25—30.
  61. Березин, Жидков, т.2, 1959, с. 30—31.
  62. Березин, Жидков, т.2, 1959, с. 41.
  63. Березин, Жидков, т.2, 1959, с. 54—56.
  64. Березин, Жидков, т.2, 1959, с. 56—59.
  65. Березин, Жидков, т.2, 1959, с. 59—61.
  66. Березин, Жидков, т.2, 1959, с. 61—62.
  67. Березин, Жидков, т.2, 1959, с. 66—67.
  68. Березин, Жидков, т.2, 1959, с. 67—73.
  69. Березин, Жидков, т.2, 1959, с. 76.
  70. Березин, Жидков, т.2, 1959, с. 76—79.
  71. Березин, Жидков, т.2, 1959, с. 83—88.
  72. Березин, Жидков, т.2, 1959, с. 88—94.
  73. Березин, Жидков, т.2, 1959, с. 103.
  74. Березин, Жидков, т.2, 1959, с. 103—107.
  75. Березин, Жидков, т.2, 1959, с. 107—114.
  76. Березин, Жидков, т.2, 1959, с. 115.
  77. Березин, Жидков, т.2, 1959, с. 128—129.
  78. Березин, Жидков, т.2, 1959, с. 135—140.
  79. Березин, Жидков, т.2, 1959, с. 140—143.
  80. Березин, Жидков, т.2, 1959, с. 143—146.
  81. Березин, Жидков, т.2, 1959, с. 146—148.
  82. Березин, Жидков, т.2, 1959, с. 129—134.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]