Квадратура Гаусса – Лежандра - Gauss–Legendre quadrature

В числовой анализ, Квадратура Гаусса – Лежандра это форма Квадратура Гаусса для приближения определенный интеграл из функция. Для интегрирования по интервалу [−1, 1], правило принимает вид:

${displaystyle int _ {- 1} ^ {1} f (x), dxapprox sum _ {i = 1} ^ {n} w_ {i} f (x_ {i})}$

куда

• п - количество использованных точек выборки,
• ш_я квадратурные веса, и
• Икс_я корни пth Полином Лежандра.

Этот выбор квадратурных весов ш_я и квадратурные узлы Икс_я является единственным выбором, который позволяет квадратурному правилу интегрировать степень 2п − 1 многочлены точно.

Для вычисления квадратурных правил Гаусса – Лежандра было разработано множество алгоритмов. Алгоритм Голуба – Велша, представленный в 1969 году, сводит вычисление узлов и весов к проблеме собственных значений, которая решается с помощью QR-алгоритм.^[1] Этот алгоритм был популярен, но существуют гораздо более эффективные алгоритмы. Алгоритмы на основе Метод Ньютона – Рафсона могут вычислять квадратурные правила для задач значительно большего размера. В 2014 году Игнас Богерт представил явные асимптотические формулы для квадратурных весов и узлов Гаусса – Лежандра, которые имеют точность с точностью до двойной точности. машина эпсилон на любой выбор п ≥ 21. ^[2] Это позволяет вычислять узлы и веса для значений п превышает один миллиард. ^[3]

История

Карл Фридрих Гаусс был первым, кто вывел квадратурное правило Гаусса-Лежандра, сделав это вычислением с непрерывными дробями в 1814 году.^[4] Он рассчитал узлы и веса до 16 знаков на заказ. п= 7 вручную. Карл Густав Джейкоб Якоби обнаружил связь между правилом квадратур и ортогональным семейством Полиномы Лежандра. Поскольку не существует формулы закрытой формы для квадратурных весов и узлов, в течение многих десятилетий люди могли использовать их вручную только для небольших п, и вычисление квадратуры должно было выполняться путем обращения к таблицам, содержащим значения веса и узлов. К 1942 году эти значения были известны только до п=16.

Определение

Графики полиномов Лежандра (до п = 5)

Для интеграции ж над ${displaystyle [-1,1]}$ с квадратурой Гаусса-Лежандра соответствующие ортогональные многочлены равны Полиномы Лежандра, обозначаемый п_п(Икс). С п-й полином, нормированный на монический, т.е. так, чтобы п_п(1) = 1, то я-й узел Гаусса, Икс_я, это я-й корень из п_п а веса задаются формулой (Абрамовиц и Стегун 1972 г., п. 887) ошибка harv: цель отсутствует: CITEREFAbramowitzStegun1972 (Помогите)

${displaystyle w_ {i} = {frac {2} {left (1-x_ {i} ^ {2} ight) left [P '_ {n} (x_ {i}) ight] ^ {2}}}. }$

Некоторые квадратурные правила низкого порядка приведены в таблице ниже для интегрирования по ${displaystyle [-1,1]}$.

Количество баллов, п	Точки, Икся		Вес, шя
1	0		2
2	${displaystyle pm {frac {1} {sqrt {3}}}}$	±0.57735…	1
3	0		${displaystyle {frac {8} {9}}}$	0.888889…
	${displaystyle pm {sqrt {frac {3} {5}}}}$	±0.774597…	${displaystyle {frac {5} {9}}}$	0.555556…
4	${displaystyle pm {sqrt {{frac {3} {7}} - {frac {2} {7}} {sqrt {frac {6} {5}}}}}}$	±0.339981…	${displaystyle {frac {18+ {sqrt {30}}} {36}}}$	0.652145…
	${displaystyle pm {sqrt {{frac {3} {7}} + {frac {2} {7}} {sqrt {frac {6} {5}}}}}}$	±0.861136…	${displaystyle {frac {18- {sqrt {30}}} {36}}}$	0.347855…
5	0		${displaystyle {frac {128} {225}}}$	0.568889…
	${displaystyle pm {frac {1} {3}} {sqrt {5-2 {sqrt {frac {10} {7}}}}}}$	±0.538469…	${displaystyle {frac {322 + 13 {sqrt {70}}} {900}}}$	0.478629…
	${displaystyle pm {frac {1} {3}} {sqrt {5 + 2 {sqrt {frac {10} {7}}}}}}$	±0.90618…	${displaystyle {frac {322-13 {sqrt {70}}} {900}}}$	0.236927…

Для интегрирования по общему действительному интервалу ${displaystyle [a, b]}$, а изменение интервала может применяться для преобразования проблемы в задачу интегрирования по ${displaystyle [-1,1]}$.

Алгоритмы

Методы Ньютона-Рафсона

Несколько исследователей разработали алгоритмы для вычисления узлов квадратур Гаусса-Лежандра и весов на основе Метод Ньютона-Рафсона для нахождения корней функций. Используются различные оптимизации для этой конкретной проблемы. Например, некоторые методы вычисляют ${displaystyle heta _ {i} = arccos x_ {i}}$ чтобы избежать проблем, связанных с кластеризацией корней ${displaystyle x_ {i}}$ ближе к концам интервала ${displaystyle -1}$ и ${displaystyle 1}$.^[5][6] Некоторые методы используют формулы для аппроксимации весов, а затем используют несколько итераций Ньютона-Рафсона для снижения ошибки аппроксимации до точности ниже машинной.^[7][5]

Голуб-Велш

В 1969 году Голуб и Велш опубликовали свой метод вычисления квадратурных правил Гаусса с учетом трехчленного рекуррентного соотношения, которому удовлетворяют лежащие в основе ортогональные многочлены.^[1] Они сводят проблему вычисления узлов квадратурного правила Гаусса к задаче нахождения собственных значений конкретного симметричного трехдиагональная матрица. В QR-алгоритм используется для нахождения собственных значений этой матрицы. Используя преимущества симметричной трехдиагональной структуры, собственные значения могут быть вычислены в ${displaystyle {mathcal {O}} (n ^ {2})}$ время, в отличие от ${displaystyle {mathcal {O}} (n ^ {3})}$ время, ожидаемое для общей задачи на собственные значения.

Асимптотические формулы

Были разработаны различные методы, которые используют приближенные выражения в замкнутой форме для вычисления узлов. Как упоминалось выше, в некоторых методах формулы используются как приближения к узлам, после чего выполняются некоторые итерации Ньютона-Рафсона для уточнения приближения. В статье 2014 года Игнас Богерт выводит асимптотические формулы для узлов, которые являются точными с точностью до машинной точности для ${displaystyle ngeq 21}$ и для гирь с точностью до станка для ${displaystyle ngeq 30}$.^[2] Этот метод не требует каких-либо итераций Ньютона-Рафсона или вычислений функций Бесселя, как это делают другие методы. Как показано в документе, этот метод смог вычислить узлы с размером задачи в один миллиард за 11 секунд. Поскольку узлы около конечных точек ${displaystyle [-1,1]}$ становятся очень близкими друг к другу при таком размере проблемы, этот метод вычисления узлов достаточен практически для любого практического применения с плавающей запятой двойной точности.

Более высокая точность

Йоханссон и Меззаробба ^[8] описать стратегию вычисления квадратурных правил Гаусса-Лежандра в арифметика произвольной точности, позволяя как малым, так и большим ${displaystyle n}$. Правило порядка ${displaystyle n = 1000}$ с точностью до 1000 цифр можно вычислить примерно за одну секунду. Их метод использует итерацию Ньютона-Рафсона вместе с несколькими различными методами вычисления многочленов Лежандра. Алгоритм также обеспечивает сертифицированную границу ошибки.

Сравнение с другими квадратурными правилами

Квадратура Гаусса-Лежандра оптимальна в очень узком смысле для вычисления интегралов от функции ж над [−1, 1], поскольку никакое другое квадратурное правило не интегрирует все степени 2п − 1 полиномы точно при использовании п точки выборки. Однако эта мера точности обычно не очень полезна - многочлены очень просто интегрировать, и этот аргумент сам по себе не гарантирует лучшей точности при интегрировании других функций.

Кленшоу-Кертис квадратура основан на приближении ж полиномиальным интерполянтом при Чебышевские узлы и интегрирует многочлены степени до п точно когда дано п образцы. Несмотря на то, что он не интегрирует многочлены или другие функции, аналитические в большой окрестности [−1, 1] так же как квадратура Гаусса-Лежандра, Кленшоу-Кертис сходится примерно с той же скоростью, что и квадратура Гаусса-Лежандра для большинства (неаналитических) подынтегральных выражений.^[9] Кроме того, Кленшоу-Кертис разделяет свойства квадратур Гаусса-Лежандра: сходимость для всех непрерывных подынтегральных выражений f и устойчивость к ошибкам численного округления.^[10] Clenshaw-Curtis просто реализовать в ${displaystyle {mathcal {O}} (nlog n)}$ время по БПФ -основанные методы.

Квадратура Ньютона-Котеса основан на приближении ж полиномиальным интерполянтом в равноотстоящих точках в [−1, 1], и, как и Кленшоу-Кертис, также интегрирует многочлены степени до п точно когда дано п образцы. Однако он страдает от Феномен Рунге так как п увеличивается; Ньютон-Котес не сходится для некоторых непрерывных интегрантов ж, и когда он сходится, он может страдать от численных ошибок округления.^[10] Таким образом, и Кленшоу-Кертис, и Гаусс-Лежандр обладают существенными преимуществами по сравнению с Ньютон-Котес для средних и крупных п.

Рекомендации