náhled|upright=2|alt=Porovnání dvoubodové Gaussovy kvadratury s lichoběžníkovou metodou.|Porovnání dvoubodové Gaussovy kvadratury s lichoběžníkovou metodou. Modrá křivka je graf funkce jejíž určitý integrál na intervalu se má vypočítat. Lichoběžníková metoda aproximuje funkci oranžovou čárkovanou úsečkou „Trap“, která spojuje funkční hodnoty na okrajích intervalu. Z obrázku je patrné, že tato aproximace není dobrá, takže chyba spočítané hodnoty integrálu je velká (lichoběžníková metoda dává hodnotu , zatímco správná hodnota je 2/3). Aby se lichoběžníkovou metodou dosáhlo přesnějšího výsledku, bylo by nutné rozdělit integrační interval na mnoho podintervalů, funkci nahradit v každém podintervalu lineární funkcí a počítat mnoho funkčních hodnot funkce Naproti tomu Gaussova metoda vybírá vhodnější body integrace, takže jediná lineární funkce (znázorněná černou čárkovanou úsečkou „Gauss 2“) aproximuje funkci mnohem lépe. Výsledek integrace dvoubodovou Gaussovou metodou je Tato hodnota je dokonce přesný výsledek, protože zelená oblast má stejnou plochu jako součet ploch červených oblastí. Důvodem je, že integrovaná funkce je ve skutečnosti polynom stupně 3, který je dvoubodovou Gaussovou kvadraturou aproximován přesně.
Numerické metody integrace jsou v numerické matematice metody výpočtu přibližných hodnot určitých integrálů funkcí. Při numerickém výpočtu určitého integrálu nějaké funkce se obvykle používá vážený součet hodnot této funkce v určitých bodech integračního intervalu – viz články Numerická integrace a Kvadratura (matematika).
Gaussova kvadratura, přesněji n-bodová Gaussova metoda numerické integrace, pojmenovaná po Carlu Friedrichu Gaussovi je metoda numerické integrace, která díky vhodné volbě uzlů a vah pro dává pro polynomy do stupně přesné výsledky. Moderní formulaci, v níž se používají ortogonální polynomy vyvinul Carl Gustav Jacob Jacobi v roce 1826. Nejobvyklejším integračním intervalem pro tuto metodu je , na kterém se pro výpočet určitého integrálu používá vzorec
který poskytuje přesné výsledky pro polynomy do stupně . Tato numerická metoda se nazývá Gaussova-Legendreova metoda numerické integrace. Metoda numerické integrace bude přesnou aproximací integrálu uvedeného výše pouze v případě, když funkci lze na intervalu dobře aproximovat polynomem stupně nejvýše .
Gaussova-Legendreova metoda numerické integrace se zpravidla nepoužívá pro integraci funkcí se singularitami v koncových bodech. V takovém případě se snažíme integrand zapsat jako
kde je funkce, kterou lze dobře aproximovat polynomem nízkého stupně. Pak použití alternativních uzlů a vah obvykle dává přesnější metody numerické integrace, které jsou známy jako Gaussova-Jacobiho kvadraturní pravidla:
Jako váhy se často používají hodnoty (Čebyševova–Gaussova kvadratura) a . Můžeme také chtít integrovat na intervalech neomezených z jedné (Gaussova-Laguerrova kvadratura) nebo obou stran (Gaussova–Hermitova kvadratura).
Lze ukázat (viz Press, et al. nebo Stoer a Bulirsch), že kvadraturní uzly jsou kořeny polynomu patřícího do třídy ortogonálních polynomů (třída ortogonální vůči váženému vnitřnímu součinu). To je klíčové pozorování pro výpočet uzlů a vah pro Gaussovu kvadraturu.
Gaussova–Legendreova kvadratura náhled|Grafy Legendrových polynomů (do stupně
Pro nejjednodušší případ numerické integrace uvedený výše je funkce aproximována polynomy na intervalu a přidružené ortogonální polynomy jsou Legendreovy polynomy označované . Zde je -tý polynom normalizovaný tak, aby , -tý Gaussův uzel je -tým kořenem polynomu a váhy jsou dané vzorcem
Integrační body a váhy pro Gaussovu–Legendreovu kvadraturu několika nižších řádů na intervalu jsou uvedeny v následující tabulce:
Počet bodů, n Body, Váhy, 1 0 2 2 ±0.57735… 1 3 0 0.888889… ±0.774597… 0.555556… 4 ±0.339981… 0.652145… ±0.861136… 0.347855… 5 0 0.568889… ±0.538469… 0.478629… ±0.90618… 0.236927…
Jiné integrační intervaly Pro výpočet integrálu na obecném intervalu je třeba před použitím Gaussovy metody numerické integrace úlohu převést na integrál na intervalu pomocí vzorce
kde
Použití -bodového Gaussova kvadraturního pravidla pak dává následující aproximaci:
Příklad dvoubodového Gaussova kvadraturního pravidla Použijeme dvoubodovou Gaussovu metodu numerické integrace pro výpočet vzdálenosti, kterou uletí raketa v čase až s použitím vzorce
Změníme meze integračního intervalu, abychom mohli použít váhy a x-ové souřadnice uvedené v Tabulce 1. Také najdeme absolutní hodnotu relativní skutečné chyby. Přesný výsledek je 11061,34 metrů
Řešení:
provedeme změnu mezí integračního intervalu z na :
Použijeme váhy a hodnoty argumentu z Tabulky 1 pro dvoubodové pravidlo:
Načež můžeme použít Gaussův vzorec pro numerickou integraci
dostáváme
Pokud přesný výsledek je 11061,34 m, absolutní hodnota relativní skutečné chyby, je
Zobecnění Problém integrace lze vyjádřit poněkud obecnějším způsobem tak, že do integrandu vneseme kladnou váhovou funkci a povolíme jiné integrační intervaly než . Obecně tedy počítáme
pro určité , a . Pro , a jde o stejný problém, jaký je popsán výše. Jiné volby vedou k jiným integračním pravidlům, z nichž některá jsou tabelována níže. Čísla rovnic ve sloupci „A & S“ jsou podle Abramowitz a Stegun
Interval Ortogonální polynomy A & S Pro více informací, viz … Legendreovy polynomy 25.4.29 Gaussova–Legendreova kvadratura Jacobiho polynomy 25.4.33 () Gaussova–Jacobiho kvadratura Čebyševovy polynomy (prvního druhu) 25.4.38 Čebyševova–Gaussova kvadratura Čebyševovy polynomy (druhého druhu) 25.4.40 Čebyševova–Gaussova kvadratura Laguerrovy polynomy 25.4.45 Gaussova–Laguerre kvadratura Zobecněné Laguerrovy polynomy Gaussova–Laguerre kvadratura Hermitovy polynomy 25.4.46 Gaussova–Hermitova kvadratura
Základní věta Nechť je netriviální polynom stupně , takový, že
Všimněte si, že toto bude splněno pro všechny ortogonální polynomy výše, protože každý polynom je zkonstruován tak, aby byl ortogonální k ostatním polynomům pro , a je v rozsahu této množiny.
Pokud vybereme uzlů tak, aby to byly kořeny polynomu , pak existuje vah , pro které je integrál vypočítaný Gaussovou kvadraturou přesný pro všechny polynomy stupně nejvýše . Všechny tyto uzly budou navíc ležet v otevřeném intervalu .
Pro důkaz první části tohoto tvrzení budeme předpokládat, že je jakýkoli polynom stupně nejvýše . Pokud jej vydělíme ortogonálním polynomem dostaneme
kde je podíl stupně nejvýše (protože součet jeho stupně a stupně dělitele musí být roven stupni ), a je zbytek také stupně nejvýše (protože stupeň zbytku je vždy menší než stupeň dělitele). Protože je podle předpokladu ortogonální ke všem jednočlenům stupně menšího než , musí být ortogonální také s podílem . Proto
Protože zbytek má stupeň nejvýše , můžeme jej přesně interpolovat pomocí Lagrangeovy interpolace s interpolačními body, kde
tedy
Jeho integrál pak bude roven
kde váha přiřazená uzlu je definována, aby vyrovnala vážený integrál (další vzorce pro váhy jsou uvedeny níže). Protože však všechny jsou kořeny polynomu , podle vzorce pro dělení uvedeného výše platí
pro všechna . Tím dostáváme
Tím jsme dokázali, že pro jakýkoli polynom stupně nejvýše je integrál přesně roven hodnotě spočítané Gaussovou kvadraturou.
Pro důkaz druhé části tvrzení použijeme polynom ve tvaru součinu kořenových činitelů . Komplexně sdružené kořeny tvoří kvadratické členy, které jsou na celé reálné ose buď kladné nebo záporné. Členy odpovídající kořenům ležícím mimo interval nemění na tomto intervalu znaménko. A členy odpovídající kořenům z intervalu které jsou liché násobnosti, násobí jedním dalším členem, který tvoří nový polynom
Tento polynom nemůže na intervalu měnit znaménko, protože všechny jeho kořeny mají sudou násobnost. Proto integrál
protože váhová funkce je vždy nezáporná. Protože však je ortogonální ke všem polynomům stupně nejvýše , bude stupeň součinu
alespoň . Proto má různých reálných kořenů v intervalu
Obecný vzorec pro váhy Váhy je možné vyjádřit vzorcem
kde je koeficient u v . Pro důkaz je třeba si všimnout, že při použití Lagrangeovy interpolace můžeme vyjádřit pomocí jako
protože má stupeň menší než a je proto určen hodnotami, kterých nabývá v různých bodech. Když znásobíme obě strany a zintegrujeme je na intervalu dostaneme
Váhy jsou tedy dány vzorcem
Tento integrální výraz pro lze vyjádřit pomocí ortogonálních polynomů a takto: Můžeme psát
kde je koeficient u v . Pokud se limitně blíží dostaneme pomocí L'Hôpitalova pravidla
Můžeme tedy napsat výraz pro váhy s použitím integrálu ve tvaru
Jmenovatel v integrandu můžeme zapsat
což dává
pokud , protože
je polynom stupně , který je tedy ortogonální k . Pokud tedy je polynom nejvýše n-tého stupně, můžeme napsat
Integrál na pravé straně můžeme pro vyhodnotit takto: Protože je polynom stupně , máme
kde je polynom stupně . Protože je ortogonální s platí
Pak můžeme psát
Člen v závorkách je polynom stupně , který je proto ortogonální s . Integrál tedy můžeme vyjádřit jako
Podle rovnice () se váhy získají vydělením tohoto výrazu výrazem , což dává výraz v rovnici ().
Váhy mohou být také vyjádřeny pomocí ortogonálních polynomů a . V trojčlenném rekurentním vztahu bude mít člen s nulovou hodnotu, takže v () lze nahradit .
Důkaz, že váhy jsou kladné Uvažujme následující polynom stupně :
kde, jak je uvedeno výše, jsou kořeny polynomu . Je zřejmé, že . Protože stupeň je menší než , platí Gaussův vzorec pro numerickou integraci obsahující váhy a uzly získané z . Protože , pokud j není rovno i, máme
Protože jak tak jsou nezáporné funkce. Odtud plyne, že .
Numerická integrace Gaussovou metodou Existuje mnoho algoritmů pro výpočet uzlů a vah v Gaussově metodě numerické integrace. Nejoblíbenější jsou Golubův-Welschův algoritmus vyžadující operací, Newtonova metoda pro řešení s pomocí trojčlenného rekurentního vztahu pro vyhodnocování, která vyžaduje operací, a asymptotické vzorce pro velká n, které vyžadují operací.
Rekurentní vztah Ortogonální polynomy , pro které platí, že pro kde je skalární součin, stupeň a koeficient u nejvyššího členu je jedna (tj. jde o monické ortogonální polynomy) vyhovují rekurentnímu vztah
a skalární součin definovaný vzorcem
pro , kde je nejvyšší stupeň, který může jít k nekonečnu, a kde . Především polynomy, definované rekurentním vztahem začínajícím , mají úvodní koeficient jedna a jsou správného stupně. Je-li dán počáteční bod , lze ortogonalitu dokázat indukcí. Pro máme
Pokud jsou ortogonální, pak také , protože ve výrazu
jsou všechny skalární součiny nulové kromě prvního a toho, kde je stejný ortogonální polynom. Proto
Pokud však pro skalární součin platí (což je v případě Gaussovy kvadratury splněno), rekurentní vztah lze zjednodušit na vztah obsahující tři členy: Pro je polynom stupně nejvýše . Na druhou stranu, je ortogonální ke každému polynomu stupně nejvýše . Proto máme a pro . Rekurentní vztah se pak zjednoduší na
nebo
(s konvencí ), kde
(poslední vztah platí, protože , protože se liší od ve stupni menším než ).
Golubův-Welschův algoritmus Trojčlenný rekurentní vztah lze zapsat v maticovém tvaru , kde , je -tý vektor standardní báze, tj. , a je tak zvaná Jacobiho matice:
Nulové body polynomů do stupně , které se používají jako uzly pro Gaussovu kvadraturu, lze nalézt výpočtem vlastních hodnot této třídiagonální matice. Tento postup je znám jako Golubův–Welschův algoritmus.
Pro výpočet vah a uzlů je vhodnější uvažovat symetrickou třídiagonální matici s prvky
a jsou podobné matice a proto mají stejná vlastní čísla (uzly). Váhy lze vypočítat z odpovídajících vlastních vektorů: Pokud je normalizovaný vlastní vektor (tj. vlastní vektor s Eukleidovskou normou rovné jedné) příslušný k vlastní hodnotě , lze odpovídající váhu vypočítat z první složky tohoto vlastního vektoru, jmenovitě:
kde je integrál váhové funkce
Další detaily lze nalézt v monografii Numerical Methods for Special Function.
Odhady chyby