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

Рассмотрим общую задачу численного интегрирования с весовой функцией . При построении квадратурных формул интерполяционного типа необходимо ввести дополнительно условие на весовую функцию: (1) Запишем квадратурную формулу для произвольного, но фиксированного распределения узлов :

. (2)

При построении квадратурных формул Ньютона-Котеса узлы распределялись равномерно по отрезку [ a,b ]. Очевидно, что такой способ выбора узлов становится невозможным для несобственных интегралов с бесконечными пределами.

Возникает вопрос: как выбрать систему узлов квадратурной формулы, чтобы формула (2) имела наивысшую возможную алгебраическую степень точности?

Напомним, что квадратурная формула имеет алгебраическую степень точности , если она точна для многочленов степени меньшей или равной .

Заметим, что формула (2) содержит всего 2n неизвестных параметров (n узлов и n весовых коэффициентов). Столько же коэффициентов содержит и произвольный многочлен степени 2n-1.

Таким образом, наивысшая алгебраическая степень точности формулы (2) не может быть больше 2n-1.

19. Запишем квадратурную формулу для произвольного, но фиксированного распределения узлов :

. (2)

Опр 1. Квадратурная формула (2), обеспечивающая условие:

называется квадратурной формулой наивысшей алгебраической степени точности.

Теорема 1. Пусть {P_k(x)}, k=0,1,…, - система ортогональных с весом многочленов на [ a,b ]. Для того чтобы формула (2) была квадратурной формулой наивысшей алгебраической степени точности, необходимо и достаточно, чтобы узлы совпадали с нулями многочлена P_n(x). При этом такая квадратурная формула - единственная.

Необходимость. Из теории ортогональных многочленов известно, что при выполнении условия (1) на весовую функцию, существует полная ортогональная на [ a,b ] c весом система алгебраических многочленов : , (3) где - символ Кронекера.

При этом все нули многочлена P_n(x) при действительны и расположены на [ a,b ].

Как и при выводе интерполяционных формул, обозначим - полином n- ой степени, нули которого совпадают с узлами интерполяции. Рассмотрим функцию . Так как - алгебраический многочлен степени , то по условию теоремы формула (2) - точна, т.е. . Но т.к. то из (2)

ортогональна системе лишь коэффициентом при старшей степени отличается от многочлена - являются нулями полинома P_n(x).

Достаточность. Пусть - нули полинома P_n(x), и - полином степени . Требуется доказать, что для .Достаточно рассмотреть случай (если формула точна для многочлена степени , то она автоматически точна и для многочлена любой меньшей степени).Пусть . Представим этот многочлен в виде: , (4)где - многочлен -ой степени (частное от деления на ), , - многочлен р- ой степени (остаток от деления).Т.к. - нули полинома , то из (4) следует, что ,т.е. является интерполяционным многочленом для : , (5)где - фундаментальный многочлен Лагранжа - степени.Учитывая (4) и (5), распишем интеграл:

(6) Формула (6) - квадратурная формула интерполяционного типа, причем для и, значит, и для любого многочлена степени, меньшей или равной . Единственность квадратурной формулы (2) следует из единственности выражений для нулей ортогонального полинома P_n(x).

20.

(6) Формула (6) - квадратурная формула интерполяционного типа, причем для и, значит, и для любого многочлена степени, меньшей или равной .

Определение 2. Квадратурная формула (6) наивысшей алгебраической степени точности носит название формулы Гаусса-Кристоффеля, а весовые коэффициенты - коэффициенты Кристоффеля.

Теорема 2. Весовые коэффициенты Кристоффеля удовлетворяют следующим условиям:

1) , 2) 3) . (7) По доказанному в теореме (в-19), формула (6) точна для многочленов порядка , в частности, для - свойство (2). Возьмем в качестве полином степени : , где - произвольный номер, а - фундаментальный многочлен Лагранжа, построенный по нулям многочлена . Учитывая свойства многочленов , получим из (6): .

Из последнего равенства следует, в частности, что (свойство 1)). Кроме того заметим, что , т.к. эти два полинома имеют одну и ту же степень, коэффициент при старшей степени равен 1, и имеют одни и те же нули на отрезке формула (7), т.е. свойство 3) доказано.

Замечание 1. Для остаточного члена квадратурной формулы Гаусса-Кристоффеля справедливо представление:

(8) где , - нули полинома , xÎ(a,b). Без доказательства.

Замечание 2. Классические ортогональные многочлены обычно строятся для канонических промежутков: с соответствующими весами . Если - конечный промежуток, то его с помощью линейного преобразования .приводим к отрезку (). При этом:

. Приведем основную сводку квадратурных формул Гаусса-Кристоффеля для основных канонических промежутков.

1) , - нули полиномов Лежандра Рекуррентные соотношения:

; или ,
, .

2) , , - нули полинома Чебышева Рекуррентные соотношения:

,

,

3) ,

- нули полинома Лагерра .

Рекуррентные соотношения:

,
,

4) , ; - нули полинома Эрмита
. Рекуррентные соотношения:

, .

21.Принцип сжатых отображений.

Пусть Х – полное метрическое пространство, - расстояние между элементами х и у. Пусть, кроме того, S – замкнутое ограниченное множество (компакт): S X и Т – оператор (вообще говоря, – нелинейный), действующий из S в S, то есть отображающий множество S в себя: . Назовем точку неподвижной точкой оператора Т, если х*=Тх* (1)Таким образом, неподвижные точки оператора Т являются решениями уравнения (1). Наиболее простой способ решения этого уравнения – итерационный, начиная с некоторого значения х⁰ ,хⁿ⁺¹=Txⁿ, х⁰ (2)

При этом важно, чтобы такая последовательность { xⁿ } сходилась к единственной точке х*. Следующая теорема формулирует достаточные условия сходимости итерационного процесса (2).

Теорема 1. (Принцип сжатых отображений). Пусть Т – оператор сжатия на S, то есть и (3)Тогда в S существует единственная неподвижная точка оператора Т, являющаяся пределом последовательности { xⁿ }, определяемой процедурой итераций, начиная с . При этом скорость сходимости оценивается неравенствами: (4)

(5)

Докажем, что последовательность { xⁿ } – фундаментальная. Рассмотрим

(6) Далее при p>1 имеем

{неравенство треугольника: вставим точку } {продолжая вставлять точки} {на основании (6)} {геометр. прогрессия} . (7) Отсюда следует, что

, следовательно, последовательность { xⁿ } – фундаментальная, и согласно критерию Коши-Вейерштрасса последовательность { xⁿ } сходится к элементу (так как S - компакт). Таким образом, имеем . Далее . Следовательно, .

Докажем единственность неподвижной точки х*. От противного. Пусть : х*=Тх*, у*=Ту*. Тогда

. Но это противоречие. Формула (4) следует из формулы (7) при р : , т.к. правая часть неравенства (7) не зависит от р. Докажем (5): {неравенство треугольника} . Отсюда .Если разделить обе части этого неравенства на (1-α), то получим (5).

Замечание 1. Неравенство (4) показывает, что последовательность { xⁿ } сходится к х* со скоростью геометрической прогрессии (такая скорость называется линейной: каждый шаг в раз приближает к х*). Кроме того, неравенство (4) позволяет определить, сколько итераций (шагов) необходимо сделать для достижения заданной точности . Для этого нужно решить неравенство:

Ясно, что для хорошей оценки числа итераций необходимо точнее оценивать константу сжатия , что на практике не всегда просто сделать. При реализации алгоритма полезно также использовать неравенство (5), позволяющее контролировать каждый шаг итерации и установить следующий критерий останова:

.