Квадратура Гаусса – Лежандра

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

\int _{-1}^{1}f(x)\,dx\approx \sum _{i=1}^{n}w_{i}f(x_{i})

где

n — количество используемых точек выборки,
w _i — квадратурные веса, а
x _i — корни n- го полинома Лежандра .

Этот выбор квадратурных весов w _i и квадратурных узлов x _i является уникальным выбором, который позволяет правилу квадратур точно интегрировать полиномы степени $2 n - 1$ .

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

История

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

Определение

Для интегрирования f по $[-1,1]$ с квадратурой Гаусса–Лежандра связанные ортогональные полиномы являются полиномами Лежандра , обозначаемыми $P n (x)$ . Когда $n$ -й полином нормализован так, что $P n (1) = 1$ , $i$ -й узел Гаусса, $x i$ , является $корнем i$ -й степени из $P n$ , а веса задаются по формуле ^{[ 5 ]}

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

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

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

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

Алгоритмы

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

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

Голуб–Уэлш

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

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

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

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

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

Гил, Сегура и Темме ^{[ 10 ]} описывают итерационные методы со сходимостью четвертого порядка для вычисления квадратур Гаусса–Якоби (и, в частности, Гаусса–Лежандра). Методы не требуют априорных оценок узлов, чтобы гарантировать сходимость четвертого порядка. Вычисления правил квадратур даже с миллионами узлов и тысячами цифр становятся возможными на обычном ноутбуке.

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

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

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

Квадратура Ньютона-Котеса основана на аппроксимации f полиномиальным интерполянтом в равноотстоящих друг от друга точках в $[-1, 1]$ и, как и Кленшоу-Кертис, также интегрирует полиномы степени до n точно при наличии n выборок. Однако он страдает от феномена Рунге по мере n увеличения ; Ньютона-Котеса не сходится для некоторых непрерывных подынтегральных выражений f , а когда он сходится, он может страдать от числовых ошибок округления. ^{[ 12 ]} Таким образом, и Кленшоу-Кёртис, и Гаусс-Лежандр имеют существенные преимущества перед Ньютоном-Котесом при средних и больших n .

Ссылки

^ Перейти обратно: ^а ^б Голуб, Джин Х.; Уэлш, Джон Х. (1969). «Расчет по правилам квадратур Гаусса». Математика. Комп . 23 : 221–230. дои : 10.1090/S0025-5718-69-99647-1 . JSTOR 2004418 .
^ Перейти обратно: ^а ^б Богерт, И. (2014). «Безытерационное вычисление квадратурных узлов и весов Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 36 : C1008–C1026. дои : 10.1137/140954969 . hdl : 1854/LU-5683230 . S2CID 690538 .
^ Таунсенд, А. (2015). «Гонка за квадратуру Гаусса – Лежандра высокого порядка» . СИАМ Новости . 48 : 1–3.
^ К. Ф. Гаусс, Новый метод нахождения целых значений методом аппроксимации , Комментарий. Соц. Рег. Они узнают. Получение. Недавний., (1814).
^ ( Абрамовиц и Стегун 1983 , стр. 887)
^ Перейти обратно: ^а ^б Хейл, Н.; Таунсенд, А. (2013). «Быстрое и точное вычисление квадратурных узлов и весов Гаусса – Лежандра и Гаусса – Якоби». СИАМ J. Sci. Вычислить . 35 : А652–А674. дои : 10.1137/120889873 .
^ Шварцтраубер, ПН (2003). «О вычислении точек и весов квадратуры Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 24 : 945–954. дои : 10.1137/S2064827500379690 .
^ И. Богерт, Б. Михилс и Дж. Фостиер, O (1) вычисление полиномов Лежандра, узлов и весов Гаусса – Лежандра для параллельных вычислений , SIAM J. Sci. Comput., 34 (2012), стр. 83–101.
^ Йоханссон, Ф.; Меззаробба, М. (2018). «Быстрое и строгое вычисление произвольной точности квадратурных узлов и весов Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 40 : C726–C747. arXiv : 1802.03948 . дои : 10.1137/18M1170133 .
^ Гил, А.; Сегура, Дж.; Темме, ММ (2021). «Быстрое и надежное высокоточное вычисление квадратуры Гаусса – Якоби». Число. Алгоритмы . 87 : 1391–1419. arXiv : 2008.08641 . дои : 10.1007/s00211-019-01066-2 . S2CID 189762478 .
^ Ллойд Н. Трефетен. 2012. Теория приближений и практика приближений . Общество промышленной и прикладной математики, США.
^ Перейти обратно: ^а ^б Трефетен, Л.Н. (2008). «Квадратура Гаусса лучше, чем Кленшоу – Кертис?». СИАМ преп . 50 (1): 67–87. дои : 10.1137/060659831 .

Источники

Абрамовиц, Милтон ; Стегун, Ирен Энн , ред. (1983) [июнь 1964 г.]. «Глава 25.4, Интеграция». Справочник по математическим функциям с формулами, графиками и математическими таблицами . Серия «Прикладная математика». Том. 55 (Девятое переиздание с дополнительными исправлениями десятого оригинального издания с исправлениями (декабрь 1972 г.); первое изд.). Вашингтон, округ Колумбия; Нью-Йорк: Министерство торговли США, Национальное бюро стандартов; Дуврские публикации. ISBN 978-0-486-61272-0 . LCCN 64-60036 . МР 0167642 . LCCN 65-12253 .

[Golub69-1] Перейти обратно: ^а ^б Голуб, Джин Х.; Уэлш, Джон Х. (1969). «Расчет по правилам квадратур Гаусса». Математика. Комп . 23 : 221–230. дои : 10.1090/S0025-5718-69-99647-1 . JSTOR 2004418 .

[Bogaert14-2] Перейти обратно: ^а ^б Богерт, И. (2014). «Безытерационное вычисление квадратурных узлов и весов Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 36 : C1008–C1026. дои : 10.1137/140954969 . hdl : 1854/LU-5683230 . S2CID 690538 .

[Townsend15-3] Таунсенд, А. (2015). «Гонка за квадратуру Гаусса – Лежандра высокого порядка» . СИАМ Новости . 48 : 1–3.

[Gauss14-4] К. Ф. Гаусс, Новый метод нахождения целых значений методом аппроксимации , Комментарий. Соц. Рег. Они узнают. Получение. Недавний., (1814).

[5] ( Абрамовиц и Стегун 1983 , стр. 887)

[Hale13-6] Перейти обратно: ^а ^б Хейл, Н.; Таунсенд, А. (2013). «Быстрое и точное вычисление квадратурных узлов и весов Гаусса – Лежандра и Гаусса – Якоби». СИАМ J. Sci. Вычислить . 35 : А652–А674. дои : 10.1137/120889873 .

[Swartztrauber03-7] Шварцтраубер, ПН (2003). «О вычислении точек и весов квадратуры Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 24 : 945–954. дои : 10.1137/S2064827500379690 .

[Bogaert12-8] И. Богерт, Б. Михилс и Дж. Фостиер, O (1) вычисление полиномов Лежандра, узлов и весов Гаусса – Лежандра для параллельных вычислений , SIAM J. Sci. Comput., 34 (2012), стр. 83–101.

[Johansson18-9] Йоханссон, Ф.; Меззаробба, М. (2018). «Быстрое и строгое вычисление произвольной точности квадратурных узлов и весов Гаусса – Лежандра». СИАМ J. Sci. Вычислить . 40 : C726–C747. arXiv : 1802.03948 . дои : 10.1137/18M1170133 .

[Gil19-10] Гил, А.; Сегура, Дж.; Темме, ММ (2021). «Быстрое и надежное высокоточное вычисление квадратуры Гаусса – Якоби». Число. Алгоритмы . 87 : 1391–1419. arXiv : 2008.08641 . дои : 10.1007/s00211-019-01066-2 . S2CID 189762478 .

[Trefethen12-11] Ллойд Н. Трефетен. 2012. Теория приближений и практика приближений . Общество промышленной и прикладной математики, США.

[Trefethen08-12] Перейти обратно: ^а ^б Трефетен, Л.Н. (2008). «Квадратура Гаусса лучше, чем Кленшоу – Кертис?». СИАМ преп . 50 (1): 67–87. дои : 10.1137/060659831 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

v т и Численное интегрирование
Формулы Ньютона–Котеса	Правило трапеции Правило Симпсона Правило Симпсона 3/8 Адаптивный метод Симпсона правило Буля метод Ромберга
Гауссова квадратура	Квадратура Гаусса – Эрмита Квадратура Гаусса – Якоби Квадратурная формула Гаусса – Кронрода Квадратура Гаусса – Лагерра Квадратура Гаусса – Лежандра Квадратура Чебышева – Гаусса
Другой	Моделирование Барнса – Хата Байесовская квадратура Квадратура Кленшоу – Кертиса Квадратурная вена Квадратура Лебедева Тан-квадратура рождения