Квадратурные формулы Гаусса

Рассмотрим вычисление интеграла вида

где a, b и W(x) известны заранее. Существует два способа вычислить этот интеграл. Первый способ - это применение одного из общих алгоритмов интегрирования (метода Симпсона, Ромберга и т.д.). Второй способ состоит в оптимальном выборе расположения узлов и значений весовых коэффициентов квадратурной формулы (с учетом интервала интегрирования и функции W(x)), чтобы в результате добиться максимально возможной точности при заданном числе узлов N. Квадратурная формула, построенная таким способом, носит название квадратурной формулы Гаусса. В случае, если f является полиномом степени не выше 2·N-1, квадратурная формула Гаусса позволит получить точное значение интеграла.

Типы задач

Вычислительные задачи, связанные с построением квадратурных формул Гаусса, можно разделить на три категории: 1) важные частные случаи (квадратуры Гаусса-Лежандра, Гаусса-Якоби, Гаусса-Эрмита, Гаусса-Лагерра); 2) задачи с произвольной весовой функцией W(x); 3) задачи с произвольной весовой функцией W(x) и заранее заданным расположением одного или двух узлов (обычно - на границах области интегрирования).

При решении задач первого типа требуется указать только класс, к которому относится весовая функция, и её параметры (если они есть). Задачи второго и третьего типа сложнее, потому что весовая функция имеет общий вид, и требуется как-то выразить её свойства в числовом виде. Традиционно для этого используются коэффициенты рекуррентной формулы, порождающей последовательность ортогональных полиномов (если вы не знакомы с терминологией, можно обратиться например к главе 4.5 "Numerical Recipes").

Алгоритм

Для вычисления узлов и весовых коэффициентов используется алгоритм, сводящий задачу построения квадратурной формулы к задаче поиска собственных чисел и векторов трехдиагональной матрицы. На основе коэффициентов рекуррентной формулы строится трехдиагональная матрица. Узлами квадратурной формулы являются её собственные числа, весовыми коэффициентами - первая строка матрицы собственных векторов. Более подробно алгоритм и структура матриц для каждого из типов квадратур (Гаусса, Гаусса-Радау и Гаусса-Лобатто) описаны в статье "Orthogonal polynomials and quadrature", W. Gautschi, 1999.

Ограничения

Построение квадратурной формулы Гаусса имеет трудоемкость O(N²) (здесь N - число узлов квадратурной формулы), т.е. с ростом N растет время, требующееся для построения квадратуры. Также с увеличением N возрастает погрешность, с которой находятся узлы/коэффициенты. Наконец, квадратурные формулы с большим количеством узлов предъявляют высокие требования к гладкости функции f(x) (функция W(x) может быть негладкой). Поэтому квадратурные формулы с числом узлов более 100-1000 редко используются. Чаще всего используются формулы с небольшим числом узлов (3-50 узлов).