ville_vaananen.tex

%% Käytä näitä, jos kirjoitat suomeksi
\documentclass[finnish,12pt]{article}
\usepackage{aaltothesis}
\usepackage[pdftex]{graphicx} 
\usepackage{topcapt} % taulukon otsikot toimivat myös taulukon päällä komennolla \topcaption
%% Saat pdf-tiedoston viittaukset ja linkit kuntoon seuraavalla paketilla.
%% Paketti toimii erityisen hyvin pdflatexin kanssa. 
\usepackage[pdfpagemode=UseNone, colorlinks=true, urlcolor=black,
linkcolor=black, citecolor=black, pdfstartview=FitH]{hyperref}


%% Matematiikan fontteja, symboleja ja muotoiluja lisää, näitä tarvitaan usein 
\usepackage{amsmath,amsfonts,amssymb,amsbsy}  
%% Viitteet suomeksi
\usepackage[fixlanguage]{babelbib}
\usepackage{booktabs} % paremman näköiset taulukot
\usepackage[framed,numbered]{mcode}
%% Vaakasuunnan mitat, ÄLÄ KOSKE!
\setlength{\hoffset}{-1in}
\setlength{\oddsidemargin}{35mm}
\setlength{\evensidemargin}{25mm}
\setlength{\textwidth}{15cm}
%% Pystysuunnan mitat, ÄLÄ KOSKE!
\setlength{\voffset}{-1in}
\setlength{\headsep}{7mm}
\setlength{\headheight}{1em}
\setlength{\topmargin}{25mm-\headheight-\headsep}
\setlength{\textheight}{23cm}


%%%%%%%% OMAT KOMENNOT %%%%%%%%%%%%

% infinitesimaalinen muutos
\newcommand{\ds}{\mathrm{d}}
\newcommand{\measure}[2]{\ds#1(#2)}
\newcommand{\dd}{\;\ds}
% määrätty integraali
\newcommand{\defint}[4]{
\int_{#1}^{#2}#3\dd#4
}

% reaaliluvut, kompleksiluvut..
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\R}{\field{R}}
\newcommand{\C}{\field{C}}
\newcommand{\Deg}{\mathrm{Deg}}
\newcommand{\iprod}[2]{\langle{}#1,#2\rangle}
\renewcommand{\v}[1]{\boldsymbol{#1}} % vektorit ja matriisit


% kuvat
\newcommand{\scalefig}[3]{
  \begin{figure}[ht!]
    % Requires \usepackage{graphicx}
    \centering
    \includegraphics[width=#2\columnwidth]{#1}
    %%% I think \captionwidth (see above) can go away as long as
    %%% \centering is above
    %\captionwidth{#2\columnwidth}%
    \caption{#3}
    \label{#1}
  \end{figure}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%% Kaikki mikä paperille tulostuu, on tämän jälkeen
\begin{document}

%% Korjaa vastaamaan korkeakouluasia
\university{aalto university}{aalto-yliopisto}
\school{school of science and technology}{teknillinen korkeakoulu}

%% Korjaa seuraavat vastaamaan omaa tiedekuntaasi
\faculty{Faculty of Electronics, Communications and Automation}%
{Elektroniikan, tietoliikenteen ja automaation tiedekunta}%
%%

%% Vain kandityölle: Korjaa seuraavat vastaamaan tutkinto-ohjelmaasi 
\degreeprogram{Bioinformation technology}{Bioinformaatioteknologia}
%%

%% Vain DI/M.Sc.- ja lisensiaatintyölle
%\department{Department of Radio Science and Technology}{Radiotieteen ja -tekniikan laitos}
%\professorship{Circuit theory}{Piiriteoria}
%\code{S-55}
%%

%% Valitse yksi näistä kolmesta
\univdegree{BSc}
%\univdegree{MSc}
%\univdegree{Lic}

%% Oma nimi
\author{Ville Väänänen}

%% Opinnäytteen otsikko tulee vain tähän. Älä tavuta otsikkoa ja
%% vältä liian pitkää otsikkotekstiä. Jos latex ryhmittelee otsikon
%% huonosti, voit joutua pakottamaan rivinvaihdon \\ kontrollimerkillä.
%% Muista että otsikkoja ei tavuteta! 
%% Jos otsikossa on ja-sana, se ei jää rivin viimeiseksi sanaksi 
%% vaan aloittaa uuden rivin.
\thesistitle{Numerical integration: From quadratures to cubatures}{Numeerinen integrointi: kvadratuureista kubatuureihin}

\place{Espoo}
%% Kandidaatintyön päivämäärä on sen esityspäivämäärä! 
\date{\today}

%% Kandidaattiseminaarin vastuuopettaja TAI
%% Diplomityön valvoja
\supervisor{D.Sc.(Tech.) Markus Turunen}{TkT Markus Turunen}

%% Kandidaatintyön ohjaaja(t) TAI
%% Diplomityön ohjaaja(t)
\instructor{D.Sc.(Tech.) Simo Särkkä}{TkT Simo Särkkä}
%% Aaltologo: syntaksi: \uselogo{red|blue|yellow}{?|!|''}
%% Logon kieli on sama kuin dokumentin kieli
\uselogo{red}{''}{tkk}

%% Tehdään kansilehti
\makecoverpage
% Suomenkielinen tiivistelmä
%
% Tiivistelmän avainsanat
\keywords{kvadratuuri, kubatuuri, gaussinen kvadratuuri, numeerinen integrointi, polynomiapproksimaatio}
% Tiivistelmän tekstiosa
\begin{abstractpage}[finnish]
Tässä kandidaatintyössä kartoitetaan numeerisia integroimismenetelmiä, eli
kvadratuureja, joita kutsutaan usean ulottuvuuden tapauksessa kubatuureiksi.
Työssä esitetään erilaisia keinoja integraalien
approksimointiin, rajoittuen interpolatorisiin kvadratuureihin
ja kubatuureihin, jotka ovat tarkkoja tietyn asteluvun polynomeille.

Työn kokeellisessa osiossa vertaillaan neljää eri kubatuuria
kaksiulotteisten integraalien ratkaisemiseksi. Interpolatoristen
kubatuurien eduiksi esitetään vaadittavien funktioevaluaatioiden
pientä määrää ja suurta tarkkuutta verrattuna kilpaileviin menetelmiin.
Tällaisten integrointisääntöjen muodostaminen havaitaan
kuitenkin ongelmalliseksi, mikä johtuu muun muassa 
moniulotteisten ortogonaalpolynomien monimutkaisuudesta
ja puutteellisesta teoriasta.

\end{abstractpage}

% Pakotetaan uusi sivu varmuuden vuoksi, jotta
% mahdollinen suomenkielinen ja englanninkielinen tiivistelmä
% eivät tule vahingossakaan samalle sivulle
\newpage

%
%% English abstract, uncomment if you need one. 
%% 
%% Abstract keywords
%\keywords{Resistor, Resistance,\\ Temperature}
%% Abstract text
%\begin{abstractpage}[english]
% Your abstract in English 
%
%\end{abstractpage}
%% Note that 
%% if you are writting your master's thesis in English place the English
%% abstract first followed by the possible Finnish abstract

%% Esipuhe
\mysection{Esipuhe}
Haluan kiittää ohjaajaani Simo Särkkää 
saamastani hyvästä ohjauksesta työn eri vaiheissa.\\
\vspace{5cm}
\dateandplace

\vspace{5mm}
{\hfill Ville Väänänen \hspace{1cm}}

%% Pakotetaan varmuuden vuoksi esipuheen jälkeinen osa
%% alkamaan uudelta sivulta
\newpage


%% Sisällysluettelo
%% addcontentsline tekee pdf-tiedostoon viitteen sisällysluetteloa varten
\addcontentsline{toc}{section}{Sisällysluettelo}
%% Tehdään sisällysluettelo
\tableofcontents


%% Symbolit ja lyhenteet
%%
%% Symbols and abbreviations
%\mysection{Symbolit ja lyhenteet}
%\subsection*{Symbolit}

%\begin{tabular}{ll}
%$\mathbf{B}$  & magneettivuon tiheys  \\
%$c$              & valon nopeus tyhjössä $\approx 3\times10^8$ [m/s]\\
%$\omega_{\mathrm{D}}$    & Debye-taajuus \\
%$\omega_{\mathrm{latt}}$ & hilan keskimääräinen fononitaajuus \\
%$\uparrow$       & elektronin spinin suunta ylöspäin\\
%$\downarrow$     & elektronin spinin suunta alaspäin
%\end{tabular}

%\subsection*{Operaattorit}

%\begin{tabular}{ll}
%$\nabla \times \mathbf{A}$              & vektorin $\mathbf{A}$ roottori\\
%$\displaystyle\frac{\mbox{d}}{\mbox{d} t}$ & derivaatta muuttujan $t$ suhteen\\
%[3mm]
%$\displaystyle\frac{\partial}{\partial t}$  & osittaisderivaatta muuttujan $t$ suhteen \\[3mm]
%$\sum_i $                       & Summa indeksin $i$ yli\\
%$\mathbf{A} \cdot \mathbf{B}$    & vektorien $\mathbf{A}$ ja $\mathbf{B}$ pistetulo
%\end{tabular}

%\subsection*{Lyhenteet}

%\begin{tabular}{ll}
%AC         & vaihtovirta \\
%APLAC      & an object-oriented analog circuit simulator and design tool \\
%           & (originally Analysis Program for Linear Active Circuits) \\
%BCS        & Bardeen-Cooper-Schrieffer \\ %% tavuviiva - nimien välissä 
%DC         & tasavirta \\
%TEM        & transverse eletromagnetic
%\end{tabular}


%% Sivulaskurin viilausta opinnäytteen vaatimusten mukaan:
%% Aloitetaan sivunumerointi arabialaisilla numeroilla (ja jätetään
%% leipätekstin ensimmäinen sivu tyhjäksi, 
%% ks. alla \thispagestyle{empty}).
%% Pakotetaan lisäksi ensimmäinen varsinainen tekstisivu alkamaan 
%% uudelta sivulta clearpage-komennolla. 
%% clearpage on melkein samanlainen kuin newpage, mutta 
%% flushaa myös LaTeX:n floatit 
\cleardoublepage
\storeinipagenumber
\pagenumbering{arabic}
\setcounter{page}{1}


%% Leipäteksti alkaa
\section{Johdanto}

%% Ensimmäisen sivun ylä- ja alatunnisteet tyhjiksi
\thispagestyle{empty}

Pinta-alojen ja tilavuuksien määrittäminen on yleisesti kohdattu ongelma matematiikan ja fysiikan sovelluksissa. 
Ei siis ole yllättävää, että jo kauan on tiedetty keinoja muuntaa pinta-aloja \emph{kvadratuureiksi}, 
samansuuruisiksi suorakulmioiksi. \emph{Integraali} on matemaattinen konstruktio, jolla on läheinen yhteys tähän ongelmaan· 
Tänä päivänä tekniikan alan ammattilaiset arkkitehdeistä tilastotieteilijöihin 
tarvitsevat työssään tarkkoja ja tehokkaita keinoja integraalien määrittämiseen, sillä niitä
joudutaan laskemaan esimerkiksi paljon käytetyssä elementtimenetelmässä sekä Bayes-mallinnuksen yhteydessä \cite{Zienkiewicz2005,Arasaratnam2009}. 

Joillekin yksinkertaisille \emph{integrandeille} $f(x)$ voidaan määrittää \emph{integraalifunktio}
$F(x)$, niin että se on ilmaistu algebrallisina lauseina sekä tunnettujen 
transkendenttisten funktioiden avulla \cite{Stoer1993}. Tällöin integraali
voidaan laskea helposti integraalifunktion saamien arvojen erotuksena.
Valitettavasti integraalifunktion määrittäminen suljetussa muodossa ei 
aina onnistu yhden muuttujan integrandien tapauksessa ja se on vielä vaikeampaa
jos muuttujia on enemmän.

Numeerinen integrointi on sovelletun matematiikan alalaji ja nimensä mukaisesti se tarjoaa työkaluja, joiden avulla integraaleille
voidaan määrittää numeerisia likiarvoja. Alalta on 
aikojen saatossa julkaistu suunnaton määrä tutkimustuloksia ja kirjallisuutta, joten minkä tahansa käytännössä 
esiintyvän integraalin ratkaisemiseen voisi olettaa löytyvän laskennallisesti tehokas ratkaisualgoritmi \cite{Ueberhuber1997}. 
Näin todennäköisesti onkin, mikäli ongelmallinen integraali on määritelty ainoastaan yhdessä ulottuvuudessa, jolloin 
myös usein on mahdollista saavuttaa miltein mikä tahansa haluttu tarkkuus. 
Jos kuitenkin dimensioita on enemmän kuin yksi, jolloin puhutuaan \emph{kubatuureista}, 
on ongelma, ehkä hieman yllättäen, kaikkea muuta kuin ratkaistu.

Numeerisen integroinnin menetelmät, joihin tässä työssä keskitytään, ovat muotoa
\begin{equation}
	\begin{array}{rll}
	I[f]&:=&\defint{\Omega}{}{f(\v{x})w(\v{x})}{\v{x}} \approx Q[f]:=\sum_{i=1}^Nw_if(\v{x}_i)\\
	E[f]&:=&I[f]-Q[f]	
	\end{array}
	\label{eq_cubature} 
\end{equation}
jossa $I[f]$ on integraali (lineaarinen funktionaali), $f$ on \emph{integrandi}, $\Omega\subset\R^n$ on integroimisalue (yhdessä ulottuvuudessa integroimisväli),
$Q[f]$ on kvadratuuri jos $n=1$ ja kubatuuri jos $n\geq 2$,
$w(\v{x})$ on \emph{painofunktio}, pisteet $\{\v{x}_i\}\in\R^n$ ovat \emph{solmut} tai \emph{tukipisteet}, 
$\{w_i\}\in\R$ ovat \emph{painot} ja $E$ on integrointimenetelmän virhe. Toisin sanoen,
annettua integraalia approksimoidaan integrandin evaluaatioiden lineaarikombinaationa. 
Vuonna 1814 saksalainen matemaatikko Carl Friedrich Gauss julkaisi merkittävän
kaavan \eqref{eq_cubature} mukaisen tuloksensa (tapaukselle $n=1$ ja $w(x)=1$), joka tunnetaan hänen mukaansa 
nimellä \emph{Gaussin kvadratuuri} \cite{Gauss1814,Gautschi1997}. Kyseessä on elegantti 
integrointimenetelmä, jossa hyödynnetään \emph{ortogonaalisiapolynomeja} ja saavutetaan suuri 
tarkkuus pienellä funktio-evaluaatioiden määrällä. Tästä vaikuttuneena kirjoitti aikalaisensa
Friedrich Bessel, myöskin tunnustettu matemaatikko, hänelle seuraavasti:
\begin{quote} 
``Nyt kun olen saanut haltuuni numeerista integrointia käsittelevän paperinne, en enää voinut pidättäytyä kiittämästä teitä siitä mielihyvästä, jonka olette minulle suoneet''\cite{Ueberhuber1997}
\end{quote}

Valitettavasti integrointisääntöjen yleistäminen moneen ulottuvuuteen on ongelmallista. Kuitenkin  
Vuonna 1877 James Clerk Maxwell julkaisi 27-pisteisen, muotoa \ref{eq_cubature} olevan kubatuurin
ja tätä pidetään ensimmäisenä varsinaisena esimerkkinä kubatuurista sellaisena, kuin se tässä 
työssä ymmärretään \cite{Cools1997}. Tämän jälkeen ei juurikaan tapahtunut edistystä ennen vuotta 1948, 
jolloin Radon julkaisi sitä seuranneen tutkimuksen kannalta perustavanlaatuisen artikkelinsa \cite{Radon1948}.
Radonin artikkeli on ilmeisesti myös ensimmäinen, jossa sanaa ``kubatuurisääntö'' (saksaksi ``Kubaturformel'') 
käytettiin viittaamaan kaavan \eqref{eq_cubature} mukaisiin menetelmiin \cite{Cools2001}.

Useampiulotteisten integraalien likimääräiseen ratkaisemiseen on täysin eri tyyppisiäkin menetelmiä,
joista tärkeimpänä mainittakoon erilaiset \emph{Monte Carlo} -menetelmät. Näissä integrandin arvo lasketaan 
suuressa määrässä satunnaisia pisteitä, jolloin integraalia voidaan approksimoida niiden keskiarvon
avulla. Etuna on, että näin päästään, ainakin teoriassa, eroon niin sanotusta \emph{dimensionaalisuuden kirouksesta},
jonka vuoksi useissa muissa integroimismenetelmissä tarvittavien funktio-evaluaatioiden määrä riippuu 
eksponentiaalisesti dimensioiden määrästä. Hyväksyttävään tarkkuuteen pääseminen vaatii kuitenkin suurta 
määrää satunnaispisteitä ja funktio-evaluaatioita jo yhdessä dimensiossa. Dimensioiden määrän lähestyessä 
useita satoja, mikä on mahdollista esimerkikisi joissain finanssimatematiikan sovelluksissa, 
ovat Monte Carlo -menetelmät usein ainoa vaihtoehto \cite{Kuo2005}. 

Tässä työssä käydään ensin  läpi tarvittavat esitiedot, kuten Riemannin integraali ja polynomiapproksimaatio, 
jotta voidaan esittää Gaussin kvadratuurien idea. Tämän jälkeen keskitytään integrointiin useammassa kuin yhdessä
dimensiossa ja käydään läpi erilaisia keinoja kubatuuri-sääntöjen muodostamiseksi. Teoreettisen selvityksen jälkeen vertaillaan 
eräitä kiinnostavia menetelmiä keskenään soveltamalla niitä esimerkki-integraaleihin kahdessa dimensioissa. 
Lopuksi saatujen tulosten ja esitellyn teorian perusteellä tehdään päätelmiä menetelmien soveltuvuudesta 
erilaisiin tilanteisiin.


%% Opinnäytteessä jokainen osa alkaa uudelta sivulta, joten \clearpage
\clearpage

\section{Riemannin integraali}
Integraalille on olemassa useita kehittäjiensä mukaan nimettyjä määritelmiä, joista Riemannin integraali 
lienee yksinkertaisin ja intuitiivisin. Usein kun puhutaan integraalista tarkoitetaan nimenomaan 
Riemannin integraalia, mikä pätee myös tähän työhön. Jos reaaliarvoinen funktio $f(x)$ on jatkuva 
(lukuunottamatta äärellistä määrää epäjatkuvuuspisteitä) ja rajoitettu integroimisalueessa $[a,b]$,  
on sille määritelty Riemannin integraali, jota merkitään $\defint{a}{b}{f(x)}{x}$ ja  
jota kutsutaan myös \emph{määrätyksi integraaliksi}. Määrätyllä integraalilla ja integraalifunktiolla $F(x)$ 
(ja sitä kautta derivoinnilla) on läheinen yhteys, joka tunnetaan \emph{analyysin ensimmäisenä peruslauseena}:

\begin{equation}
	\label{fundamental_theorem}
	\defint{a}{b}{f(x)}{x}=\defint{a}{b}{F'(x)}{x}=F(b)-F(a)
\end{equation}
Huomionarvoista on se, että määrätyn integraalin \emph{olemassaolo} ei ole millään tavalla riippuvainen 
integraalifunktion $F(x)$ olemassaolosta.\cite{Cheney2007}

\subsection{Määritelmä}

Olkoon $f(x)\geq 0$ välillä $[a,b]$. Tällöin geometrisesti tarkasteltuna luku 
$\defint{a}{b}{f(x)}{x}$ tarkoittaa kuvaajan $y=f(x)$, $x$-akselin ja 
suorien $x=a$ ja $x=b$ rajaamaa pinta-alaa. Tämä on suora seuraus Riemannin integraalin määritelmästä. 
Olkoon \[ P=\{a=x_{0}<x_{1}<\dots{}<x_{n-1}<x_{n}=b\} \] välin $[a,b]$ $n$-intervallinen jako, 
$\vert P \vert=max_i\{x_i-x_{i-1}\}$ sen pisimmän intervallin pituus ja olkoon $\zeta_i\in[x_{i-1},x_i]$ 
mikä tahansa piste intervallilla $i$. Tällöin summaa \[ \sum_{i=1}^{n}f(\zeta_i)(x_i-x_{i-1}) \] kutsutaan Riemannin summaksi.
Tarkastellaan Riemannin summien $S_k$ muodostamaa sarjaa, jonka jaoille $P_k$ pätee
$\lim_{k\to\infty}\vert P_k \vert = 0$. Nyt jos mikä tahansa näin muodostettu Riemannin summien sarja suppenee, eli \emph{konvergoituu},
\emph{yhteiseen} raja-arvoon 
$S$, eli $\lim_{k\to\infty}S_k = S$, niin   
\begin{equation}		
		 \defint{a}{b}{f(x)}{x} = S\in\R.	
\end{equation}
Eräitä Riemannin summia intervallilla $[-2,2]$, tarkemmin sanottuna ala- ja yläsummia, on havainnollistettu 
kuvassa \ref{fig_lusums} (jaon ei välttämättä tarvitse olla tasavälinen). Kuvasta \ref{fig_lusums} on 
helppo nähdä, että jaon tihentyessä Riemannin summat suppenevat samaan arvoon, joka vastaa kuvaajan $y=f(x)$ ja $x$-akselin 
rajaamaa pinta-alaa välillä $[-2,2]$.\cite{Davis1975}

Jos integrandi tai integroimisväli on rajoittamaton, jolloin integraalia kutsutaan \emph{epäoleelliseksi}, voidaan
integraali määritellä tavallisten integraalien raja-arvoina, mikäli nämä ovat olemassa. Esimerkiksi 
\[ \defint{a}{\infty}{f(x)}{x}=\lim_{r\to\infty}\defint{a}{r}{f(x)}{x}, \]  
\[ \defint{-\infty}{\infty}{f(x)}{x}=\defint{\R}{}{f(x)}{x}=\defint{-\infty}{0}{f(x)}{x}+\defint{0}{\infty}{f(x)}{x} \] 
ja jos $\lim_{x\to a}f(x)=\infty$, niin \[ \defint{a}{b}{f(x)}{x} = \lim_{r\to a^{+}}\defint{r}{b}{f(x)}{x}. \]

Kuten jo kaavasta \eqref{eq_cubature} voidaan päätellä, usein yksinkertaisen integraalin $\defint{a}{b}{f(x)}{x}$ sijaan
käsitellään \emph{painotettuja} integraaleja $\defint{a}{b}{f(x)w(x)}{x}$. Jos integroimissääntö $Q[f]$ on määritelty jonkin
painofunktion $w(x)$ suhteen, on painofunktio ``lukittu'' ja ainoastaan funktiota $f(x)$ varioidaan. Tässä työssä $w(x)$ oletetaan
aina ei-negatiiviseksi ja rajoitetuksi integromisalueessa. Jos painofunktio on normalisoitu siten, että $\defint{\R}{}{w(x)}{x}=1$, 
painofunktiota kutsutaan \emph{jakaumaksi} ja $\defint{a}{b}{f(x)w(x)}{x}$ on tällöin $f(x)$:n painotettu keskiarvo välillä
$[a,b]$.



\scalefig{fig_lusums}{0.8}{Ala- ja yläsummat $20$-välisellä jaolla}

\section{Kvadratuurit}

Käyttämällä tasavälistä jakoa, edellä esitellyistä ala- tai yläsummista saadaan suoraan eräs, melkoisen epätarkka, numeerinen 
integraaliapproksimaatio, \emph{suorakaidemenetelmä} \cite{Ueberhuber1997}. Jos tasavälistä alasummaa 
(valitaan jokaiselta väliltä integrandin pienin arvo) merkitään nyt $L$ ja vastaavasti yläsummaa
 (valitaan jokaiselta väliltä integrandin suurin arvo) $U$, niin kuvan \ref{fig_lusums} esittämässä tapauksessa 
saadaan $L[e^{-x^2}]\approx 1.57$ ja $U[e^{-x^2}]\approx 1.96$, todellisen arvon 
ollessa $\defint{-2}{2}{e^{-x^2}}{x}\approx 1.76$. Tulosta voidaan hiukan parantaa valitsemalla suorakulmion $i$
korkeudeksi $f(\frac{x_i+x_{i+1}}{2})$.

Selkeä parannus saadaan aikaiseksi \emph{puolisuunnikasmenetelmällä}, jossa myös käytetään 
tasavälistä jakoa $P_n=\{x_i\;\vert\;x_i=a+hi,\;i=0,\dots,n\}$, mutta 
suorakulmiot on korvattu puolisuunnikkailla:

\begin{align} 
	\defint{x_{k}}{x_{k+1}}{f(x)}{x} \approx \frac{h}{2}\left(f(x_k)+f(x_{k+1})\right)	
	\label{eq_trapezoid}
\end{align}
Puolisuunnikasmenetelmää on havainnollistettu kuvassa \ref{fig_trapezoid}.\cite{Gautschi1997}
\scalefig{fig_trapezoid}{0.8}{Puolisuunnikasmenetelmä}

Sekä suorakulmiomenetelmä, että puolisuunnikasmenetelmä voidaan tulkita siten, että integrandia 
approksimoidaan jokaisella välillä vakiofunktiolla (0:nnen asteen polynomi) tai vastaavasti
ensimmäisen asteen polynomilla. Tällaisen tulkinnan siivittämänä näille 
menetelmille löytyy ilmeinen parannusehdotus: käytetään 
approksimointiin korkeamman asteen polynomia.\cite{Gautschi1997}

\subsection{Polynomiapproksimaatio}

Yleinen \emph{approksimaatio-ongelma} voidaan muotoilla seuraavasti: olkoon $f$ approksimoitava
funktio ja $\|\cdot\|$ normi, joka on määritelty halutunlaisia funktioita sisältävän vektorivaruuden, eli funktioavaruuden, $\Phi$
funktioille $\varphi$. Etsi $\hat{\varphi}\in\Phi$ siten että
\begin{equation}
	 \label{eq_general_approximation}
	 \|f-\hat\varphi\|\leq\|f-\varphi\|\quad\forall\varphi\in\Phi .\cite{Gautschi1997}
\end{equation}
Normin valinta määrää, missä mielessä mikäkin approksimaatio on optimaalinen. Yleisesti käytetty normi on 
funktioavaruuden $L_2$ (välillä $[a,b]$ Lebesgue mitalliset funktiot,
joiden neliö on integroituva), normi
\begin{equation}
	\label{eq_l2norm}
	\|f(x)\|_{2,w}=\sqrt{\defint{a}{b}{w(x)\vert f(x) \vert^2}{x}}, 
\end{equation}
jolloin puhutaan \emph{pienimmän neliösumman} menetelmästä. Diskreetissä tapauksessa 
\begin{equation}
	\label{eq_l2norm_discrete}
	\|f(x)\|_{2,w}=\sqrt{\sum_{i=1}{N}w_i\vert f(x_i) \vert^2}. 
\end{equation}
Jos approksimaatioalue on diskreetti (tiedetään pisteet, jotka approksimaation on toteutettava) ja 
approksimaatiolle $\hat\varphi$ pätee $\|f-\hat\varphi\|=0$,
niin silloin $\hat\varphi(t_i)=f(t_i)\quad\forall i = 1,\dots,N$ ja sanotaan että $\hat\varphi$ \emph{interpoloi} funktiota $f$
pisteissä $t_i$.\cite{Gautschi1997} 

\emph{Polynomit} \[ p(x)=a_mx^m+\dots+a_1x+a_0=\sum_{i=0}^ma_ix^i, \] eli \emph{monomien} $a_ix^i$ lineaarikombinaatiot, ovat yleisimmin 
käytettyjä approksimointifunktioita ja ylivoimaisesti suurin osa numeerisista integroimismenetelmistä
perustuu integrandin approksimointiin polynomilla \cite{Davis1975}. Tämä johtuu muun muassa siitä, että polynomien 
käyttäytyminen tunnetaan hyvin perinpohjaisesti sekä \emph{Weierstrassin teoreemasta}, jonka mukaan mitä tahansa jatkuvaa
funktiota voidaan approksimoida äärellisellä välillä mielivaltaisen tarkasti tarpeeksi korkea-asteisella 
polynomilla \cite{Davis1975,Gautschi1997}. Toisin sanoen, jos kaavassa \eqref{eq_general_approximation} korvataan
$\hat\varphi$ $n$-asteisella polynomilla $\hat{p}_n$ ja $f$ on jatkuva äärellisellä approksimointivälillä, niin
\begin{equation} 
	\label{eq_approximation_convergence}
	n\to\infty\implies\|f-\hat{p}_n\|\to 0.
\end{equation}
Konvergenssin nopeus riippuu $f$:n \emph{sileydestä}, eli sen jatkuvien derivaattojen \\$f',f'',\dots,f^{(k)}$ 
lukumäärästä \cite[s. 74]{Trefethen2008}. Jos funktiolla on ääretön määrä jatkuvia derivaattoja,
kuten esimerkiksi funktiolla $f(x)=e^{x}$, sitä kutsutaan \emph{sileäksi}.

Polynomisessa interpolaatiossa $\Phi=\mathbb{P}_m$, eli vektoriavaruus, johon kuuluvat kaikki polynomit joiden asteluku $\Deg[p]\leq m$.
Halutaan siis löytää sellainen polynomi $p$, jolle pätee $p(x_i) = f(x_i)\quad\forall i$, kun $\{x_i\}$ on $n+1$ 
erillistä pistettä ja $\{f(x_i)\}\subset R$ niitä vastaavat mielivaltaiset arvot. Osoittautuu, että 
$p$ on aina muodostettavissa siten, että $m\leq n$ ja se on tällöin ainutkertainen.\cite[s. 128]{Cheney2007}

Interpoloiva polynomi $p$ voidaan konstruoida \emph{Lagrange} muodossaan Lagrangen \emph{kantapolynomien} $\ell_i$ avulla:
\begin{align*}
	&\ell_i(x)=\prod_{\substack{j\neq i\\j=0}}^{n}\left(\frac{x-x_j}{x_i-x_j}\right)\\
	\implies & \ell_i(x_j)=\delta_{ij}=
	\begin{cases}
    	0 & i \neq j \\
    	1 & i = j
    \end{cases}.
\end{align*}
Nyt jos $p$ määritellään $\ell_i$:n lineaarikombinaationa 
\[
	p(x)=\sum_{i=0}^{n}\ell_i(x)y_i,
\]
niin selvästi pätee 
\[
	p(x_i)=\ell_i(x_i)y_i=y_i.
\]
ja koska $\text{Deg}(\ell_i)=n$, niin myös $\text{Deg}(p)=n$.

\subsection{Newton--Cotes menetelmät}

Aiemmin esitellyssä puolisuunnikasmenetelmässä 
integrointiväli oli jaettu osaväleihin ja integrandia approksimoitiin 
ensimmäisen asteen polynomilla jokaisella osavälillä. 
Menetelmää, jossa samaa sääntöä käytetään toistuvasti usealla 
osavälillä, kutsutaan \emph{paloittaiseksi} (eng. \emph{compound} tai \emph{composite}) 
\cite{Davis1975}. Seuraavassa keskitytään tilanteeseen, jossa sääntöä
käytetään vain kerran. Muistetaan kuitenkin, että interpolatorisen säännön
tarkkuuttaa voidaan aina parantaa käyttämällä sitä paloittain.
 
Jos nyt tasavälisellä jaolla $\{a=x_0,x_1=a+h,\dots,x_{n-1}=a+(n-1)h,x_n=a+nh=b\}$ käytetään $f$:n 
tilalla edellä määriteltyä interpoloivaa polynomia $p$, saadaan
\begin{align} 
	\defint{a}{b}{f(x)}{x} = \defint{a}{b}{p(x)}{x}+E_n[p] 
	=&\defint{a}{b}{\sum_{i=0}^{n}\ell_{i}(x)f(x_{i})}{x}+E_n[p] \nonumber \\ 
	=&\sum_{i=0}^{n}\left(f(x_{i})\defint{a}{b}{\ell_{i}(x)}{x}\right)+E_n[p] \nonumber \\  
	=&\sum_{i=0}^{n}f(x_{k+i})w_i+E_n[p] \label{eq_newton_cotes} \\
	w_i=&\defint{a}{b}{\prod_{\substack{j\neq i\\j=0}}^{n}\left(\frac{x-x_j}{x_i-x_j}\right)}{x}. \label{eq_nc_weights}  
\end{align}
Tällä tavalla muodostetut menetelmät tunnetaan nimellä \emph{Newton--Cotes} menetelmät ja ne poikkeavat toisistaan interpolaatiopisteiden
lukumäärässä. Jos välin päätepisteet kuuluvat interpolaatiopisteiden joukkoon, menetelmää kutsutaan suljetuksi 
ja jos eivät, niin avoimeksi. \cite{Gautschi1997}

Havaitaan, että mikäli kaavassa \eqref{eq_newton_cotes} valitaan $n=1$, ja sovelletaan sitä paloittain,
saadaan edellä esitelty puolisuunnikasmenetelmä (\ref{eq_trapezoid}).
Jos taas valitaan $n=2$, eli interpolaatioon käytetään kolmea pistettä, saadaan laajalti käytetty 
\emph{Simpsonin} menetelmä:
\begin{equation} 
	\label{eq_simpson}
	\defint{a}{b}{f(x)}{x} \approx \frac{h}{3}\left(f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right)\cite{Gautschi1997}.
\end{equation}

Virheen $E_n[p]$ pienentämiseksi voidaan nähdä kaksi eri lähestymistapaa: joko käytetään pienen $n$:n 
Newton--Cotes kaavaa paloittain aina vain lyhyemmillä osaväleillä tai käytetään pidempiä 
osavälejä mutta kasvatetaa $n$:ää. Ensimmäisessä tapauksessa evaluointipisteiden määrä 
kasvaa nopeasti epäkäytännöllisen suureksi. 
Kuitenkin sekä puolisuunnikasmenetelmä että Simpsonin menetelmä ovat erittäin laajalti käytettyjä 
ja voidaan näyttää, että kun osavälien määrä $N\to\infty$, niin $E_n[p]\to 0$ kaikille integrointivälillä 
jatkuville integrandeille. Toisessa tapauksessa $n$:n kasvaessa suureksi, voivat painot $w_i$ olla 
joko positiivisia tai negatiivisiä ja absoluuttiselta arvoltaan mielivaltaisen suuria, jolloin 
nämä menetelmät eivät enää ole numeerisessa mielessä stabiileja. Tämän vuoksi korkean tarkkuusasteen Newton--Cotes
menetelmiä ei juurikaan käytetä.\cite{Krylov1962}

Sanotaan että kvadratuurisäännön (polynominen) \emph{tarkkuusaste} on $d$, jos se antaa tarkan tuloksen kaikille polynomeille, jotka ovat 
korkeintaan astetta $d$, eli $E_n[p]=0$, jos $\Deg[p]\leq d$, mutta ei yhdellekään polynomille jonka $\Deg[p]\geq d+1$. Koska Newton--Cotes 
menetelmissä integrandia interpoloidaan $n+1$:ssä pisteessä astetta $n$ olevalla polynomilla, niin $d_{NC}=n-1$ ja Newton--Cotes kaavoja kutsutaan \emph{interpolatorisiksi}.
Tästä seuraa luonnollisesti kysymys, onko tarkkuuastetta mahdollista parantaa interpolatorista paremmaksi? 
Osoittautuu, että jos solmupisteet $x_i$ ovat ennalta määrätyt, 
on interpolatorinen tarkkuusaste paras mahdollinen, 
mutta jos solmupisteet saadaan valita vapaasti, voidaan tarkkuusastetta kasvattaa.

\subsection{Gaussin kvadratuuri}

Tarkastellaan nyt kaavan \eqref{eq_cubature} mukaista integroimissääntöä yhdessä ulottuvuudessa
\begin{equation}
	\defint{a}{b}{f(x)w(x)}{x}=\sum_{i=1}^nf(x_i)w_i+E_n[f].
	\label{eq_weighted_quadrature}
\end{equation} ja oletetaan että painot $w_i$ on määritelty kuten aiemminkin, mutta painotettuna versiona
\begin{equation}
	w_i=\defint{a}{b}{w(x)\ell_i(x)}{x}
	\label{eq_weights}
\end{equation}

Väli $(a,b)$ voi olla ääretön, kunhan kaavan \eqref{eq_weighted_quadrature} integraali on määritelty ainakin
jos $f(x)$ on polynomi. Integroinnin lineaarisuudesta johtuen, riittää että integraali on määritelty
kaikille monomeille, eli että painofunktion kaikki \emph{momentit} $\mu_s$

\begin{equation}
	\mu_s=\defint{a}{b}{x^i}{x},\forall i\in\field{N}_0 
\end{equation}
ovat määritellyt \cite{Gautschi1997}. Newton--Cotes kaavojen perusteella tiedetään, että mikäli on 
annetut mitkä tahansa $n$ pistettä, niin voidaan
määrittää kaava \eqref{eq_weighted_quadrature}, jonka tarkkuusaste on $d=n-1$. Voidaan kuitenkin
osoittaa, että muotoa \eqref{eq_weighted_quadrature} olevan kvadratuurin maksimaalinen tarkkuusaste
on $d=2n-1$, mikäli jokainen $n$:stä solmusta saadaan valita vapaasti \cite{Gautschi1997}.

Kuinka solmut ${x_i}$ tulisi sitten valita? Tämän osoittamiseksi määritellään ensin \emph{solmupolynomi}
\begin{equation}
	\omega_n(x)=\prod_{i=1}^n(x-x_i)\in\field{P}_n.
	\label{eq_knot_polynomial} 
\end{equation}
Nyt jos ja vain jos solmupolynomille pätee
\begin{equation}
	\defint{a}{b}{\omega_n(x)p_{n-1}(x)w(x)}{x}=0\:,\quad\forall p_{n-1}\in\field{P}_{n-1}
	\label{eq_orthogonal_polynomials} 
\end{equation}
niin kaavan \eqref{eq_weighted_quadrature} mukaisen kvadratuurin, jonka painot on laskettu kaavan \eqref{eq_weights} mukaisesti, 
tarkkuusaste on $d=2n-1$. Tämän todistamiseksi osoitetaan ensin ehdon \eqref{eq_orthogonal_polynomials} 
välttämättömyys, eli oletetaan että $d=2n-1$. 
Selvästi $\omega_np_{n-1}\in\field{P}_{2n-1}\quad\forall p\in\field{P}_{n-1}$,
jolloin
\begin{equation}
	 \defint{a}{b}{\omega_n(x)p_{n-1}(x)w(x)}{x}=\sum_{i=1}^np_{n-1}(x_i)w_i=0.
\end{equation} 
Toisaalta jos otetaan mikä tahansa $p\in\field{P}_{2n-1}$ ja oletetaan ehto \eqref{eq_orthogonal_polynomials}, 
niin tällöin
$p/\omega_n=q+r/\omega_n$ niin että $q,r\in\field{P}_{n-1}$ ja
\begin{equation}
	\defint{a}{b}{p(x)w(x)}{x}=\defint{a}{b}{q(x)\omega_n(x)w(x)}{x}+\defint{a}{b}{r(x)w(x)}{x}. 
\end{equation}
Koska $q\in\field{P}_{n-1}$ niin ehdon \eqref{eq_orthogonal_polynomials} nojalla
\begin{equation}
	 \defint{a}{b}{q(x)\omega_n(x)w(x)}{x}=0,
\end{equation}
kun taas 
\begin{align*}
	 &\defint{a}{b}{r(x)w(x)}{x}=\sum_{i=1}^{n}w_ir(x_i)\\
	 =&\sum_{i=1}^{n}w_i\left(p(x_i)-q(x_i)\omega_n(x_i)\right)=\sum_{i=1}^{n}w_ip(x_i),
\end{align*}
joten
\begin{align*}
	 &\defint{a}{b}{p(x)w(x)}{x}=\sum_{i=1}^{n}w_ip(x_i)\\
	 \implies&E_n[p]=0.
\end{align*}
Eli sääntö on tarkka polynomeille, jotka ovat korkeintaan astetta $d=2n-1$. Toisaalta jos tarkastellaan
esimerkiksi polynomia $\omega_n^2(x)\in\field{P}_{2n}$ niin selvästi (muistetaan että $w(x)\geq 0$)
\[ \defint{a}{b}{\omega_n^2(x)w(x)}{x} > 0, \] mutta \[ \sum_{i=0}^nw_i\omega_n^2(x_i)=0, \] 
joten sääntö ei ole tarkka polynomeille astetta $2n$ \cite{Krylov1962}.

\subsubsection{Ortogonaalipolynomit}

Keskitytään nyt tarkastelemaan ehtoa \eqref{eq_orthogonal_polynomials}. Sanotaan, että $f$ ja $g$ ovat 
\emph{ortogonaaliset} $w$:n suhteen välillä $[a,b]$, jos
\begin{equation}
	\label{eq_inner_product}
	\defint{a}{b}{f(x)g(x)w(x)}{x}=0, 
\end{equation} eli niiden \emph{sisätulo} $\iprod{f}{g}_w=0$. Joukko $\{f_1,\dots,f_n\}$ on ortogonaalinen, mikäli kaikki sen jäsenet ovat keskenään
ortogonaalisia, eli \[ \iprod{f_i}{f_j}_w=0\;\forall i\neq j \] ja \emph{ortonormaali} mikäli lisäksi pätee
\[ \iprod{f_i}{f_i}_w=1\;\forall i \]. 

Kaavasta \eqref{eq_knot_polynomial} nähdään selvästi, että mikäli solmupolynomin määritelmä tunnettaisiin, saataisiin
solmut $x_i$ laskettua sen nollakohdista. Sisätulon ja ortogonaalisuuden määritelmien perusteella ehto \eqref{eq_orthogonal_polynomials}
tarkoittaa solmupolynomin olevan sellainen polynomi $\omega_n\in\field{P}_n$, joka on ortogonaalinen $w$:n suhteen 
kaikkia polynomeja $p_{n-1}\in\field{P}_{n-1}$ kohtaan. Koska sisätulo on lineaarinen ja jos 
$\{e_0,\dots,e_{n-1}\}$ on jokin $\field{P}_{n-1}$ \emph{kanta}, riittää että $\omega_n$ on ortogonaalinen
kaikkia kantapolynomeja $e_i$ kohtaan. Yleisesti käytettyjä kantapolynomeja ovat monomit $x^i$, joiden avulla
eräs $\field{P}_{n-1}$:n kanta on  $\{1,x,\dots,x^{n-1}\}$.

Mikä tahansa lineaarisesti riippumaton joukko, kuten esimerkiksi edellä esitelty monomikanta, on mahdollista ortogonalisoida
\emph{Gram--Schmidt}-proseduurin avulla \cite[s.65]{Gautschi1997}. Näin jokaista, edellä mainitut ehdot täyttävää, 
painofunktiota kohti on olemassa oma ortogonaalisten polynomien joukkonsa ${\pi_{j,w}}$ ($\Deg[\pi_j]=j,\;j=0,1,2,\dots$)
ja $\omega_n=\pi_{n,w}$. Joitakin painofunktioita vastaavat ortogonaalipolynomit tunnetaan \emph{klassisina} ja ne on 
esitelty taulukossa \ref{table_classical_orthogonal_polynomials}. Solmupolynomin muodostaminen Gram--Schmidt-proseduurin avulla 
on työlästä ja monimutkaista. Lisäksi kun solmupolynomi on saatu
selville, joudutaan vielä ratkaisemaan sen nollakohdat. Polynomin nollakohtien ratkaiseminen taas on tunnetusti
laskennalliseti vaativaa ja siihen liittyvät algoritmit epästabiileja \cite{Trefethen1997}. 

Tiedetään kuitenkin, että peräkkäiset ortogonaalipolynomit $\pi_k(x)$ toteuttavat kolmiaskelisen rekursiokaavan:

\begin{align} 
	&\pi_{k+1}(x)=(x-\alpha_k)\pi_k(x)-\beta_k\pi_{k-1},\quad k=0,1,2,\dots, \label{eq_orthogonal_recursion} \\
	&\pi_0(x)=1,\:\pi_{-1}(x)=0 \nonumber	
\end{align} missä $\alpha_k\in\R$ ja $\beta_k>0\in\R$ riippuvat painofunktiosta. 

Rekursiokaavasta \eqref{eq_orthogonal_recursion} päästään suoraan tulokseen, jonka perusteella
solmut $x_i$ ja painot $w_i$ saadaan laskettua tietyn Jacobin--matriisin ominaisarvojen ja -vektorien
avulla. Numeerisesta lineaarialgebrasta taas tunnetaan tehokkaita ratkaisualgoritmeja (kuten Lanczos-algoritmi) 
tällaisten ominaisarvo-ongelmien ratkaisemiseksi, joten myös Gaussin kvadratuureja
voidaan laskea tehokkaasti, mikäli $\alpha_k$ ja $\beta_k$ tunnetaan.\cite{Trefethen1997}

\begin{table}[h!]
	\centering
	\topcaption{Klassiset ortogonaalipolynomit}
	\begin{tabular}{cccc}
		\toprule
		Merkintä & Nimi & $w(x)$ & $[a,b]$ \\
		\midrule
		$P_n$ & Legendre &$1$ & $[-1,1]$ \\
		$P_n^{(\alpha,\beta)}$ & Jacob & $(1-x)^\alpha(1+x)^\beta$ & $[-1,1]$ \\
		$T_n$ & Tsebysev 1 & $(1-x^2)^{-\frac{1}{2}}$ & $[-1,1]$ \\
		$U_n$ & Tsebysev 2 & $(1-x^2)^{\frac{1}{2}}$ & $[-1,1]$ \\		
		$L_n^{(\alpha)}$ & Laguerre & $t^\alpha e^{-x}$ & $[0,\infty]$  \\
		$H_n$ & Hermite & $e^{-x^2}$ & $[-\infty,\infty]$ \\
		\bottomrule
	\end{tabular}	
	\label{table_classical_orthogonal_polynomials}
\end{table}

  
\subsubsection{Ominaisuuksia}

Gaussin kvadratuurisääntö on optimaalinen kaavan \eqref{eq_weighted_quadrature} mukainen sääntö siinä
mielessä, että sen polynominen tarkkuus on suurin mahdollinen. Tämän lisäksi sillä on muitakin haluttavia
ominaisuuksia, kuten: 
\begin{enumerate}
  \item kaikki solmut $x_i$ kuuluvat integroimisvälille $[a,b]$
 \item kaikki painot $w_i$ ovat positiivisia, koska
 \[ 0 < \defint{a}{b}{\ell_i^2(x)w(x)}{x} = \sum_{k=1}^nw_k\ell_i^2(x_k) = w_i \quad \forall i=1,\dots,n\;,\] joka tarkoittaa
 että Gaussin kvadratuuri on numeerisesti stabiili
 \item jos integrandi on jatkuva ja integroimisväli on äärellinen, niin $E_n[f]\to 0$, kun $n\to\infty$.
\end{enumerate}

Painojen $w_i$ positiivisuus on tärkeä ominaisuus kaikkien muotoa \eqref{eq_weighted_quadrature} olevien
kvadratuurien konvergenssin kannalta, sillä voidaan osoittaa, että tässä tapauksessa
kaikille integroimisvälillä jatkuville integrandeille $f$, ääretön-normin kannalta parhaalle
maksimissaan $n$-asteiselle polynomiapproksimaatiolle $\hat{p}_n(x)$ ja kaikille $n>0$ pätee
\begin{equation}
	\label{eq_quadrature_convergence}
	\left\vert \defint{a}{b}{f(x)w(x)}{x}-\sum_{i=1}^nf(x_i)w_i \right\vert < 4\|f(x)-\hat{p}_n(x)\|_{\infty}.
\end{equation}
Kaava \eqref{eq_quadrature_convergence} tarkoittaa siis, että mikäli kvadratuurin painot ovat positiiviset,
niin kvadratuurin konvergenssi on nopea, jos parhaan polynomiapproksimaation konvergenssi on nopea \cite{Trefethen2008}.
Gaussin kvadratuurien tapauksessa kaavassa \eqref{eq_quadrature_convergence} voidaan $\hat{p}_n(x)$
korvata $\hat{p}_{2n+1}(x)$:llä.

Kaavan \eqref{eq_quadrature_convergence} ja polynomiapproksimoinnin teorian avulla voidaan
Gaussin kvadratuureille johtaa virhearvio \cite{Trefethen2008}. Olkoon $\|f\|_T=\left\|\frac{f'(x)}{\sqrt{1-x^2}}\right\|_1$.
Olkoon f jatkuva integroimisvälillä $[-1,1]$,
olkoon sillä jatkuvat $k-1$ derivaattaa jollakin $k\geq 1$ ja olkoon $\|f^{(k)}\|_T<\infty$. 
Tällöin Gaussin kvadratuurin virheelle pätee kaikilla $n\geq\frac{k}{2}$
\begin{equation}
	\vert E_n[f] \vert \leq \frac{32\|f^{(k)}\|_T}{15\pi k(2n+1-k)^k}. 
\end{equation}
Numeerisessa integroinnissa syntyvän virheen arvioiminen on välttämätöntä, jos halutaan
pystyä varmistumaan saadun tuloksen laadusta. Lisäksi, jos numeeriselle integroimismenetelmälle
on olemassa virhearvio, sen konvergenssia voidaan yleensä nopeuttaa tämän arvion avulla.
Esimerkkinä tästä on \emph{Romberg}-kvadratuuri, jossa paloittaisen puolisuunnikassäännön
konvergenssia nopeutetaan Richardson-ekstrapolaation avulla \cite[s. 204]{Cheney2007}.


On tavallista että Gaussin kvadratuurisääntö on annettu jollekin äärelliselle integrointivälille $[c,d]$ (usein $[-1,1]$), 
mutta sitä halutaan soveltaa toisella äärellisellä välillä $[a,b]$. 
Olkoon annettu sääntö $\sum_{i=0}^nw_if(t_i)$, joka on määritelty välillä $[c,d]$. Käyttämällä muuttujanvaihdosta (affiinimuunnos) \[ x=\left(\frac{b-a}{d-c}\right)t+\left(\frac{ad-bc}{d-c}\right), \] saadaan uusi sääntö \[\left(\frac{b-a}{d-c}\right)\sum_{i=0}^nw_if\left(\left(\frac{b-a}{d-c}\right)t+\left(\frac{ad-bc}{d-c}\right)\right),\] joka on määritelty välillä $[a,b]$. Toisin sanoen, on riittävää määritellä Gaussin kvadratuurisääntö mille tahansa vapaavalintaiselle välille. 
Tavallisesti valitaan väli $[-1,1]$. \cite[s.231]{Cheney2007}



\subsubsection{Laskeminen}

Näiden tietojen perusteella voimme esimerkinomaisesti laskea kolmipisteisen Gaussin kvadratuurin 
vakiopainofunktiolle $w(x)=1$ ja välille $[-1,1]$:
\begin{align*}
	\defint{-1}{1}{f(x)}{x}\approx &w_0f(x_0)+w_1f(x_1)+w_2f(x_2)\\
	\omega_3=&(x-x_0)(x-x_1)(x-x_2)=x^3+a_2x^2+a_1x+a_0. 
\end{align*}  
Nyt siis $\omega_3\in\field{P}_3$:n täytyy olla ortogonaalinen kaikkia $p(x)\in\field{P}_2$ kohtaan. 
Sisätulon \eqref{eq_inner_product} lineaarisuudesta johtuen näin on, mikäli $\omega_3$ on ortogonaalinen 
kannan $\{1,x,x^2\}$ jokaisen monomin kanssa, joten saadaan yhtälöryhmä
\begin{equation*} 
	\begin{cases}
		0=&\defint{-1}{1}{x^3+a_2x^2+a_1x+a_0}{x}\\
		0=&\defint{-1}{1}{x(x^3+a_2x^2+a_1x+a_0)}{x}\\
		0=&\defint{-1}{1}{x^2(x^3+a_2x^2+a_1x+a_0)}{x} 
	\end{cases},
\end{equation*}
jonka ratkaisu on $a_0=a_2=0$ ja $a_1=-\frac{3}{5}$, jolloin $x_0=-\sqrt{\frac{3}{5}},x_1=0,x_2=\sqrt{\frac{3}{5}}$.

Vaihtoehtoisesti olisimme voineet käyttää hyväksi tietoa, että $\omega_3=\frac{1}{l_3}P_3$, missä $P_3$ on kolmas
Legendren ortogonaalipolynomi ja $l_3$ on $P_3$:n kolmannen asteen termin kerroin. Kaavasta \eqref{eq_orthogonal_polynomials}
nähdään, että jos $\iprod{f}{g}=0$ ja $c\in\R$, niin myös $\iprod{cf}{g}=0$, eli ortogonaalipolynomi on määrätty
skalaarikerrointa vaille. Legendren polynomit on standardoitu siten, että $P_n(1)=1$, kun taas solmupolynomin
korkeimman asteen termin kerroin on aina $1$. Tästä johtuen on $\omega_n=\frac{1}{l_n}P_n$. Legendren polynomien rekursiokaava on
\begin{equation}
	(n+1)P_{n+1}=(2n+1)xP_n-nP_{n-1},\quad P_0=1,\;P_1=x, 
\end{equation}
josta saadaan
\begin{align*}
	P_2=&\frac{3}{2}x^2-\frac{3}{2} \\
	P_3=&\frac{5}{3}xP_2-\frac{2}{3}P_1=\frac{5}{2}x^3-\frac{3}{2}x \\
	\frac{2}{5}P_3=&x^3-\frac{3}{5}x=\omega_3,  
\end{align*}
kuten pitikin \cite[s.27]{Davis1975}.

Painot $w_i$ voitaisiin laskea kaavasta \eqref{eq_weights}, mutta ne saadaan helpommin käyttämällä hyväksi tietoa, että 
etsimämme kvadratuuri on tarkka monomeille ${1,x,x^2}$. Näin saadaan toinen yhtälöryhmä painoille $w_i$:
\begin{equation*} 
	\begin{cases}
		\defint{-1}{1}{}{x}=2&=w_0+w_1+w_2\\
		\defint{-1}{1}{x}{x}=0&=-\sqrt{\frac{3}{5}}w_0+\sqrt{\frac{3}{5}}w_2\\
		\defint{-1}{1}{x^2}{x}=\frac{2}{3}&=\frac{3}{5}w_0+\frac{3}{5}w_2 
	\end{cases},
\end{equation*}
jonka ratkaisu on $w_0=w_2=\frac{5}{9}$ ja $w_1=\frac{8}{9}$. Etsimämme kvadratuuri on siis
\begin{equation*}
	 \defint{-1}{1}{f(x)}{x}\approx G_3(f(x))=\frac{5}{9}f\left(-\sqrt{\frac{3}{5}}\right)+\frac{8}{9}f(0)+\frac{5}{9}f\left(\sqrt{\frac{3}{5}}\right).
\end{equation*}
Muuttujanvaihdoksen $t=x+1$ avulla voidaan edellä laskettua kvadratuuria käyttää välillä $[0,2]$, jolloin soveltamalla 
sitä jo aiemmin tutkimaamme esimerkki-integrandiin $f(x)=e^{-x^2}$ ja hyödyntällä integrandin symmetrisyyttä $y$-akselin suhteen, 
saadaan tulokseksi
\begin{align*}
	 \defint{-2}{2}{e^{-x^2}}{x}=2\defint{0}{2}{e^{-x^2}}{x}\approx 2G_3(e^{-(x+1)^2})\approx& 1.7577\\
	 2E_{G_3}(e^{-(x+1)^2})\approx& 0.0064.
\end{align*}
Vastaavasti käyttämällä Simpsonin menetelmää \eqref{eq_simpson} samassa tilanteessa, saadaan virheeksi
\begin{align*}
	 2E_S(e^{-x^2})\approx& 0.1043,
\end{align*}
joka on yli $16$ kertaa suurempi kuin Gaussin kvadratuurin virhe.

Käytännössä Gaussin kvadratuurin laskemisessa hyödynnetään jo aiemmin mainittua
mahdollisuutta muuntaa ongelma tridiagonaalisen matriisin
ominaisarvojen ja -vektoreiden selvittämiseksi. Tämä on mahdollista
tehdä algoritmisessa suoritusajassa $O(n^2)$ \cite{Trefethen2008}.
Trefethen esittää artikkelissaan \cite{Trefethen2008} seitsemän
rivisen MATLAB-funktion, joka laskee Gaussin kvadratuurin valitulla
mielivaltaisella tarkkuusteella (vakiopainofunktiolle). Tähän perustuva
kaksiulotteinen tulosääntö on esitetty liitteessä \ref{appendixA}.

\section{Kubatuurit}

Kaiken kaikkiaan tähän mennessä on havaittu, että numeerinen integrointi yhdessä ulottuvuudessa on
hyvin tunnettu ongelma, johon on tarjolla tehokkaita ratkaisuja. Ulottuvuuksissa $d \geq 2$ tilanne
muuttuu ratkaisevasti. Ensinnäkin, yhdessä ulottuvuudessa on integrointisääntöjen kannalta
vain yksi rajoitettu integroimisalue, koska kaikki viivasegmentit ovat yhteneviä affiinimuunnokella. 
Useammassa ulottuvuudessa erilaisia
integroimisalueita (joita ei voi muuntaa toisikseen affiinimuunnoksella) on ääretön määrä. 
Toiseksi, yhdessä ulottuvuudessa ortogonaalipolynomien teoria on hyvin tunnettu ja siitä
on huomattavaa apua kvadratuurien määrittämisessä. Usean muuttujan tapauksessa tilanne on kuitenkin toinen, 
sillä moniulotteisten ortogonaalipolynomien teoria on huomattavasti monimutkaisempi 
ja heikommin tunnettu, eikä sen avulla ole onnistuttu muodostamaan kubatuurisääntöjä kuin
harvoissa tapauksissa. \cite[s.6-7]{Stroud1971}

Olkoon $\v{\alpha}=(\alpha_1,\dots,\alpha_n)\in\field{N}^n$ ja $\v{x^\alpha}=\prod_{i=1}^nx_i^{\alpha_i}$. 
Monen $n$:n muuttujan polynomi $p(\v{x})\in\field{P}_d^n$ on monomien $\v{x^\alpha}$ äärellinen lineaarikombinaatio
\begin{equation} 
	p(\v{x})=\sum_{\v{\alpha}\in\field{N}^n}a_{\v{\alpha}}\v{x^\alpha}
\end{equation}
ja sen \emph{algebrallinen asteluku} (myöhemmin pelkkä aste) on $d$, jos
\begin{equation}
	\Deg[p]=d=\max\left\{ \sum_{i=1}^n \vert \alpha_i \vert \; \Big\vert \; a_{\v{\alpha}}\neq 0 \right\}.  
\end{equation}
Kuten aiemminkin, sanotaan että kubatuurisäännön tarkkuusaste on $d$ jos se on tarkka
kaikille polynomeille astetta $d$, mutta ei ainakaan yhdelle astetta $d+1$. Määritellään lisäksi polynomin $p$ \emph{yleinen asteluku}
\begin{equation}
	\hat{\Deg[p]}=\max\left\{\max\left\{\vert \alpha_i \vert \; \Big\vert \; i=1,\dots,n \right\} \; \Big\vert \; a_{\v{\alpha}}\neq 0 \right\}  
\end{equation}
ja sanotaan että kubatuurisäännön yleinen tarkkuusaste on $b$ jos se on tarkka
kaikille polynomeille yleistä astetta $b$, mutta ei ainakaan yhdelle yleistä astetta $b+1$.
Esimerkiksi polynomille $p(x,y)=x^3y^4+y^5$ pätee $\Deg[p(x,y)]=\max\{3+4,5+0\}=7$ ja $\hat{\Deg}[p(x,y)]=\max\{\max\{3,4\},\max\{5,0\}\}=\max\{4,5\}=5$.   
Tämä tarkoittaa myös, että jos $\field{P}_1=\{p \mid \Deg[p]\leq d\}$ ja $\field{P}_2=\{p \mid \hat{\Deg[p]}\leq d\}$, niin $\field{P}_1\subset\field{P}_2$. 

\subsection{Integroimisalueet}

Kubatuurisäännöt on määritelty koskemaan tiettyä pintaa tai tilavuutta $\Omega\subset\R^n$. Yleisimmin
käytetyille alueille on omat merkintänsä \cite[s.219]{Stroud1971} ja alueet joita tässä
työssä käsitellään esitelty taulukossa \ref{table_regions}. Äärettömän suurille alueille
myös painofunktion ajatellaan olevan osa alueen määritelmää, joten näissä 
tapauksissa taulukossa \ref{table_regions} on ilmoitettu myös painofunktio.
\begin{table}[h!t]
	\topcaption{Yleisimmät integroimisalueet}
	\centering
	\begin{tabular}{cccc}
		\toprule
		Merkintä & Nimi & Määritelmä & $w(\v{x})$ \\
		\midrule
		$C_n$ & $n$-kuutio & $-1 \leq x_i \leq 1$ & \\
		%$C_n^{\text{shell}}$ & $n$-kuution pinta $-K_1 \leq x_i \leq K_2\;0<K_1<K_2<\infty$ & \\
		$S_n$ & $n$-pallo & $\v{x}^T\v{x} \leq 1$ & \\
		$U_n$ & $n$-pallon pinta & $\v{x}^T\v{x} = 1$ & \\
		$T_n$ & $n$-simpleksi & $x_1+\dots+x_n \leq 1$ & \\
		$E_n^{r^2}$ & n-avaruus & $-\infty < x_i < \infty$ & $e^{-\v{x}^T\v{x}}$ \\
		$E_n^{r}$ & n-avaruus & $-\infty < x_i < \infty$ & $e^{-\sqrt{\v{x}^T\v{x}}}$ \\
		\bottomrule
	\end{tabular}	
	\label{table_regions}
\end{table} Mielivaltaiselle integroimisalueelle joudutaan joko kehittämään täysin oma kubatuurinsa tai
se voidaan yrittää ositella ali-alueisiin, joille kubatuurisäännöt tunnetaan, jonka jälkeen
alkuperäistä integraalia voidaan approksimoida ali-alueiden integraalien summana \cite[s.14]{Stroud1971}.

\subsection{Tulosäännöt}

Tulosäännöissä ideana on muodostaa kubatuurisääntö ulottuvuudessa $n=r+s$ $r$-ulotteisen
ja $s$-ulotteisen kubatuurisäännön tulona. Oletetaan, että integroimisalue $\Omega_r\times\Omega_s\subset\R^n$
on integroimisalueiden $\Omega_r\subset\R^r$ ja $\Omega_s\subset\R^s$ \emph{karteesinen tulo}, eli
\[ \Omega_r \times \Omega_s=\{(x_1,\dots,x_n) \mid (x_1,\dots,x_r) \in \Omega_r,\: (x_{r+1},\dots,x_n) \in \Omega_s\}. \]
Olkoot $\v{x}_r=(x_1,\dots,x_r)$, $\v{x}_s=(x_{r+1},\dots,x_n)$ ja $\v{x}_n=(x_1,\dots,x_n)$. Oletetaan lisäksi, 
että $w(\v{x}_r,\v{x}_s)=w_r(\v{x}_r)w_s(\v{x}_s)$ ja olkoot annettuna
kubatuurisäännöt 
\begin{equation*} 
	\defint{\Omega_r}{}{w_r(\v{x}_r)f(\v{x}_r)}{\v{x}_r} \approx \sum_{i=1}^{N_r}w_{r,i}f(\v{x}_{r,i}),  
\end{equation*} 
jonka tarkkuusaste on $d_r$ sekä
\begin{equation*} 
	\defint{\Omega_s}{}{w_s(\v{x}_s)f(\v{x}_s)}{\v{x}_s} \approx \sum_{j=1}^{N_s}w_{s,j}f(\v{x}_{s,j}),  
\end{equation*} 
jonka tarkkuusaste on $d_s$.
Näiden avulla voidaan muodostaa $N_rN_s$ pisteinen tulosääntö
\begin{equation}
	\iint _{\Omega_r\times\Omega_s}w(\v{x}_r,\v{x}_s)f(\v{x}_r,\v{x}_s) \dd\v{x}_r\ds\v{x}_s
	\approx \sum_{\substack{i=1\\j=1}}^{\substack{N_r\\N_s}}w_{s,j}w_{r,i}f(\v{x}_{r,i},\v{x}_{s,j})
\end{equation}
ja sen \emph{yleinen} tarkkuusaste $d$ on $\min\left\{d_r,d_s\right\}$ \cite{Davis1975}.


Tulosääntöjä voidaan muodostaa tarpeeksi säännöllisille integroimisalueille, kuten $C_n$ tai $T_n$.
Lisäksi painofunktion on oltava jaettavissa tekijöihinsä kuten edellä esitettiin. Mikäli tulosääntö on mahdollista muodostaa, on sen löytäminen helppoa ja virhearviokin
on saatavilla. Kuitenkin, jos tarkastellaan esimerkiksi $p$-pisteistä
kvadratuuria välillä $[0,1]$, jonka avulla muodostetaan tulosääntö $n$-kuutiolle, saadaan
pisteiden määräksi $p^n$, joka kasvaa äkkiä epäkäytännöllisen suureksi. Tarvitaan siis parempia ratkaisuja.

\subsection{Interpolatoriset kubatuurit}

Interpolatoriset kvadratuurisäännöt voitiin muodostaa
helposti integroimalla interpolaatiopolynomia, joka on aina olemassa. 
Interpolaatiopolynomille ei valitettavasti
ole olemassa suoraa yleistystä useammassa ulottuvuudessa, toisin sanoen, jos on annettu mielivaltaiset
pisteet $\{\v{x}_i\mid i=1,\dots,N\;\v{x}_i\in\R^n\}$ ja niitä vastaavat arvot
$\{y_i\mid i=1,\dots,N\;y_i\in\R\}$, ei välttämättä voida muodostaa polynomia $p(\v{x})$
jolle pätisi $p(\v{x}_i)=y_i\;\forall i$ \cite[s.275]{Davis1975}. 

%Yleistys on mahdollinen,
%mikäli annetut pisteet $\v{x_i}$ muodostavat tulomuotoisen hilan. Näin voidaan muodostaa
%integrointikaavojakin, mutta koska vaadittavien pisteiden määrä kasvaa jälleen eksponentiaalisesti
%dimension suhteen, ne eivät ole kovin hyödyllisiä \cite[s.276]{Davis1975}.

Yksiulotteisessa tapauksessa huomasimme, että kvadratuuri, joka muodostetaan
integroimalla interpoloivaa polynomia, on sama kuin se, joka saadaan jos
vaaditaan että integraalin on oltava tarkka valitun polynomiavaruuden $\field{P}_d^1$ kannalle. 
Tämä idea voidaan yleistää myös moniulotteiseen tapaukseen. Vaaditaan siis nyt,
että kubatuurin on oltava tarkka kaikille  $\{f_i\},\;span\{f_i\}=\field{P}_d^n$. 
Saadaan epälineaarinen yhtälöryhmä
\begin{equation}
	\sum_{k=1}^Nw_kf_i(\v{x}_k)=\defint{\Omega}{}{f_i(\v{x})w(\v{x})}{\v{x}},\quad i=1,\dots,\dim[\field{P}_d^n]=\binom{n+d}{d},
	\label{eq_nonlinear_equations} 
\end{equation}
jossa $f_i$:t muodostavat $\field{P}_n^d$:n kannan, ja jos pisteet $x_i$ on annettu (tai päätetty), 
muuttujina ovat $N=\binom{n+d}{d}$ painoa $w_k$. 
Nyt jos painot $w_k$ määräytyvät yksiselitteisesti pisteiden $x_i$ perusteella,
kutsutaan näin saatua kubatuuria \emph{interpolatoriseksi}.
Jos $f_i$:t ovat monomeja, voidaan yhtälöiden \eqref{eq_nonlinear_equations}
oikealle puolelle laskea numeroarvot (painofunkion kaikkien momenttien tuli olla määritelty).
Tarkastellaan esimerkkiä, jossa halutaan muodostaa kubatuuri, joka on tarkka kaikille
$p(x,y)\in\field{P}_2^2$ alueessa $C_2$. Tällöin monomikanta on $\{1,x,y,xy,x^2,y^2\}$ ja kaavan \eqref{eq_nonlinear_equations} mukaiseksi
systeemiksi saadaan

\begin{equation}
	 \begin{array}{ll}
	 	w_1+\dots+w_6&=4 \\
	 	w_1x_1+\dots+w_6x_6&=0 \\
	 	w_1y_1+\dots+w_6y_6&=0 \\
	 	w_1x_1y_1+\dots+w_6x_6y_6&=0 \\
	 	w_1x_1^2+\dots+w_6x_6^2&=\frac{4}{3} \\
	 	w_1y_1^2+\dots+w_6y_6^2&=\frac{4}{3}.
	 \end{array}
\end{equation} Jos pisteet $(x_i,y_i),\;i=1,\dots,6$ tiedetään, \eqref{eq_nonlinear_equations}
on lineaarinen kuuden yhtälön yhtälöryhmä, jossa muuttujina ovat painot $\{w_1,\dots,w_6\}$.
Jos myös pisteitä pidetään muuttujina, on kyseessä epälineaarinen yhtälöryhmä kahdeksantoista
muuttujan $\{x_1,\dots,x_6,y_1,\dots,y_6,w_1,\dots,w_6\}$ suhteen. 

Yleisesti ottaen, 
jokainen piste $\v{x}_k$ tuo yhtälöryhmään $n+1$ muuttujaa:
koordinaatit $x_{1,k},\dots,x_{n,k}$ ja painon $w_k$, joten $N$-pisteisen
kubatuurin yhtälöryhmässä on $N(n+1)$ muuttujaa.

Kubatuurisääntöjen
olemassaolosta voidaan osoittaa muun muassa seuraavaa: aina voidaan valita $N=\dim[\field{P}_d^n]$
pistettä $\v{x}_i$ siten, että yhtälöryhmä \eqref{eq_nonlinear_equations}, ja sitä kautta painot $w_i$,
on ratkaistavissa \cite[s. 54]{Stroud1971}. Nämä säännöt ovat analogisia yhden 
ulottuvuuden Newton--Cotes säännöille \cite[s. 54]{Stroud1971}. 
Voidaan itse asiassa osoittaa vielä paljon enemmänkin.
Niin sanotun Tchakaloffin teoreeman mukaan jos $N\leq \dim[\field{P}_d^n]$ ja $w(\v{x}) > 0 \; \forall \v{x}\in\Omega$,
niin yhtälöryhmä \eqref{eq_nonlinear_equations} ei ole ainoastaan ratkaistavissa,
vaan vieläpä siten että kaikki painot ovat positiivisia ja kaikki pisteet ovat
integrointialueen $\Omega$ sisällä \cite[s. 26]{Cools1997}. Tchakaloffin
teoreeman ylärajan $N= \dim[\field{P}_d^n]$ voidaan osoittaa olevan
pienin yleispätevä yläraja, sillä on mahdollista konstruoida $n$
-ulotteinen integroimisalue, jolle ei ole olemassa kubatuurisääntöä
jossa olisi tätä vähemmän pisteitä \cite[s. 26]{Cools1997}. 

Yksiulotteisessa interpolatorisessa tapauksessa havaittiin, että valitsemalla
pisteet tiettyjen ortogonaalisten polynomien nollakohdiksi, voitiin vaadittavien pisteiden määrää pienentää. 
Päästiin myös selkeään lopputulokseen: säilyttääkseen tarkkuusasteen
$m$, kvadratuurin painoista voitiin ``hävittää'' maksimissaan puolet ja saatiin Gaussin kvadratuuri.
Kuinka siis pisteet $\v{x}_1,\dots,\v{x}_N$ tulisi valita, jotta
$N$ olisi pienempi kuin $\dim[\field{P}_d^n]$? Tästä päästään monen muuttujan ortogonaalisiin polynomeihin.

\subsubsection{Moniulotteiset ortogonaalipolynomit}

Ensinnäkin, jokaista astelukua $d$ kohti on olemassa useampia
moniulotteisia ortogonaalipolynomeja. Yleensä ne normalisoidaan siten,
että asteluvultaan $d$ olevia termejä on vain yksi ja sen
kerroin on $1$. Gaussin kvadratuurien
yleistystä koskee seuraava Mysovskikhin teoreema: välttämätön
ehto sellaisen $N= \dim[\field{P}_k^n]$ pisteisen kubatuurisäännön
olemassaololle, jonka tarkkkuusaste on $d=2k+1$, on se että normalisoiduilla
$n$-ulotteisilla ja $k+1$ asteisilla ortogonaalisilla polynomeilla on $N$
\emph{yhteistä} nollakohtaa. Valitettavasti tiedetään, että tämä ehto
ei täyty esimerkiksi silloin, kun integroimisalueena on neliö tai kolmio
ja painofunktio on vakio.\cite[s. 5]{Cools2002}. 

% Joka tapauksessa, jos
% tiedetään joukko normalisoituja ortogonaalisia polynomeja ja niiden yhteiset
% nollakohdat, pelkästään tutkimalla näitä polynomeja ja nollakohtia on 
% aina mahdollista selvittää voidaanko niitä käyttää kubatuurisäännön pisteinä.
% Vastaavasti jokaiseen kubatuurisääntöön, jolle $N< \dim[\field{P}_d^n]$,
% voidaan yhdistää ortogonaalisten polynomien joukko, jonka yhteiset nollakohdat
% ovat kyseisen kubatuurisäännön pisteet \cite{Stroud1971}.

Tarkastellaan kaikkien sellaisten ortogonaalisten polynomien joukkoa, jotka ``häviävät''
(eli joilla on yhteiset nollakohdat) annetussa pistejoukossa. Selvästikin
tällaisten polynomien joukko on enemmän kuin pelkästään vektoriavaruus. Sitä kutsutaankin
\emph{polynomiseksi ideaaliksi}. Ideaaliteorian avulla voidaan todistaa useita
kubatuureja koskevia teoreemoja, kuten esimerkiksi aiemmin mainittu Tchakaloffin teoreema
sekä edellä mainittu Mysovskikhin teoreema \cite{Cools1997}. 
Polynomisten ideaalien ja kubatuurien välinen yhteys voidaan muotoilla seuraavasti:
olkoon $I$ $n$-ulotteinen integraali, $\{\v{x}_1,\ldots,\v{x}_N\}\subset \field{C}^n$ ja $U:=\{p\in \field{P}^n \mid p(\v{x_i}) \forall \v{x}_i\}$.
Tällöin seuraavat lauseet ovat yhtenevät:
\begin{itemize}
  \item $p\in U\cap\field{P}_d^n\implies I[p]=0$
  \item on olemassa kubatuurisääntö $Q$, jolle pätee $I[p]=Q[p]\forall p\in\field{P}_d^n$ ja jonka 
  pisteiden määrä on maksimissaan $N=\dim[\field{P}_d^n]-\dim[U\cap\field{P}_d^n]$ 
\end{itemize}
Ideaaliteoriaan perustuen on mahdollista muodostaa joitakin kubatuureja myös käytännössä.
Tällöin ongelmaksi tulee polynomi-ideaalin kannan löytäminen \cite[s. 39]{Cools1997}.
Lisätietoa ideaaliteoriasta ja kubatuureista löytyy esimerkiksi lähteistä
\cite[kpl. 6.3 ja 9]{Cools1997} ja \cite{Schmid1980}.


\subsubsection{Symmetriasta}

% Palataan hetkeksi yksiulotteiseen tilanteeseen, ja mietitään integrandia $f(x)=x^3$.
% Jos integrointialue on symmetrinen $y$-koordinaattiakselin suhteen, niin saadaan
% $\defint{-a}{a}{x^3}{x}=0$. Selvästi tämä pätee kaikille integrandeille $f(x)=cx^{(2k+1)}$,
% jossa $c\in\R$ ja $k\in\field{N}$, koska tällöin $f(x)=-f(-x)$.
% 
% Integraalin symmetrian määrää sen \emph{symmetriaryhmä}. Olkoon $G$ jokin sellaisten lineaaristen ortogonaalikuvausten
% joukko, jotka pitävät origon muuttumattomana. Sanotaan, että joukko $\Omega\subset\R^n$ on \emph{invariantti}
% joukon $G$ suhteen, eli G-invariantti, jos pätee $g\Omega=\Omega$ kaikille $g\in G$. Vastaavasti funktion $f$ sanotaan olevan
% invariantti joukon $G$ suhteen, jos pätee $f(\v{x})=f(g\v{x})$ kaikille $g\in G$. Integraalin sanotaan olevan  
% invariantti joukon $G$ suhteen, mikäli sen integroimisalue ja painofunktio ovat invariantteja joukon $G$
% suhteen. Jos nyt määritellään vielä pisteen $\v{x}$ \emph{G-kehä}:ksi joukko $\{g(\v{x}) \mid g\in G\}$, niin
% kubatuurisäännön sanotaan olevan G-invariantti jos sillä approksimoidaan G-invarianttia integraalia ja
% jos sen tukipisteiden joukko on G-kehien unioni. Lisäksi kaikilla tukipisteillä jotka kuuluvat samalle
% G-kehälle on sama paino. 
% 	Tarkastellaan esimerkiksi neliötä $\Omega=\{(x,y) \mid \vert x \vert \leq 1,\;\vert y \vert \leq 1\}$. Tällöin
% $\Omega$ on invariantti ortogonaalikuvausten
% \begin{align*}
% 	 G=&
% 	 \bigg\{\begin{pmatrix} 1&0\\0&1 \end{pmatrix},\;
% 	 \begin{pmatrix} 0&1\\-1&0 \end{pmatrix},\;
% 	 \begin{pmatrix} -1&0\\0&-1 \end{pmatrix},\;
% 	 \begin{pmatrix} 0&-1\\1&0 \end{pmatrix}, \\
% 	 &\begin{pmatrix} 1&0\\0&-1 \end{pmatrix},\;
% 	 \begin{pmatrix} 0&1\\1&0 \end{pmatrix},\;
% 	 \begin{pmatrix} -1&0\\0&1 \end{pmatrix},\;
% 	 \begin{pmatrix} 0&-1\\-1&0 \end{pmatrix}\bigg\}
% \end{align*}
% suhteen ja mielivaltaisen pisteen $(a,b)\in\Omega$ G-kehä on joukko
% \begin{equation*}
% 	\{(a,b),\;(b,-a),\;(-a,-b),\;(-b,-a),\;(a,-b),\;(b,a),\;(-a,b),\;(-b,-a)\}.	 
% \end{equation*}
% 
% 
% Kaiken tämän määrittelyn hyöty kubatuurisääntöjen löytämiselle tulee ilmeiseksi niin
% sanotun Sobolevin teoreeman myötä. Funktioavaruuden $\field{P}_d^n$ G-invariantit polynomit muodostavat
% aliavaruuden $\field{P}_d^n(G):=\{p(\v{x})\in\field{P} \mid p(g\v{x})=p(\v{x})\; \forall g \in G\}$.  
% Sobolevin teoreeman mukaan G-invariantin kubatuurisäännön tarkkuusaste on $d$,
% jos se on tarkka kaikille \emph{G-invarianteille} polynomeille korkeintaan astetta $d$.
% Toisin sanoen $\field{P}_n^d$:ssä tarkalle G-invariantille kubatuurisäännölle riittää, että ratkaisemme
% sellaisen yhtälöryhmän \eqref{eq_nonlinear_equations}, jossa $f_i$:t ovat aliavaruuden $\field{P}_d^n(G)$ kanta. 

Hyödyntämällä Sobolevin \emph{invarianttiteoriaa} \cite[s. 17]{Cools1997}, voidaan yhtälöryhmän \eqref{eq_nonlinear_equations}
yhtälöiden määrää joissakin tapauksissa radikaalisti pienentää. Tämä tarkoittaa käytännössä sitä, että etsittävälle
kubatuurisäännölle määrätään tietty rakenne, joka perustuu integroimisalueen ja painofunktion
symmetriaan. Arasatnamin \emph{et al.} \cite[s. 5]{Arasaratnam2009} esimerkkiä mukaillen tarkastellaan
kubatuurisääntöä, jossa $n=20$ ja $d=3$. Tällöin yhtälöryhmässä \eqref{eq_nonlinear_equations} on
$\frac{23!}{20!3!}=1771$ yhtälöä. Mutta mikäli rajoitutaan tarkastelemaan \emph{täysin symmetristä}
kubatuurisääntöä, saadaan $N=2n=40$ pisteinen kubatuurisääntö ratkaistuksi ainoastaan
\emph{kahden} yhtälön avulla. 

Olkoon $X$ kubatuurisäännön $Q$ tukipisteiden joukko. 
$Q$:n sanotaan olevan täysin symmetrinen, jos
pätee \[ \v{a}=(a_1,\ldots,a_n)\in X \implies \v{b}=(s_1a_{p_1},\ldots,s_na_{p_n})\in X, \] jossa
$s_i\in\{-1,1\}$ ja $\{p_1,\ldots,p_n\}$ on mikä tahansa indeksien ${1,\ldots,n}$
permutaatio \cite{Arasaratnam2009,Cools1997}. Lisäksi kaikilla näin saaduilla pisteillä $\v{a}$ ja $\v{b}$ on oltava
samat painot. Kubatuuria sanotaan \emph{keskipisteensä suhteen symmetriseksi} jos pätee
\[
	Q[\v{x^\alpha}]=0\quad\forall \v{\alpha}\in\field{N}_0^n,\;\sum_{i=1}^n\alpha_i=\text{pariton}\;\cite{Lu2005}.
\] 



On olennaista huomata, että ratkaisun helpottumista lukuunottamatta ei ole mitään erityistä syytä
miksi kubatuurisäännön symmetrian pitäsi olla sama kuin integroimisalueen tai painofunktion.
Päinvastoin, pakottamalla kubatuurisääntö noudattamaan tiettyä rakennetta voidaan
estyä löytämästä sääntöä, jonka pistemäärä on pienin mahdollinen. Hyvä esimerkki tästä
on tarkkuusastetta 9 oleva sääntö neliölle ($C_2$). Tällöin täysin symmetrisessä
säännössä on 20 pistettä, mutta \emph{minimisäännössä}, joka on invariantti rotaation suhteen, on 17 \cite{Cools1997}. 


\subsubsection{Alarajoista}

Erittäin olennaista kubatuurisääntöjen löytämiselle on arvio
pienimmälle mahdolliselle tukipisteiden määrälle $N$.
Jotta yhtälöryhmää \eqref{eq_nonlinear_equations} voitaisiin lähteä
ratkaisemaan, olisi $N$:lle saatava jokin arvio, mieluiten
tietysti pienin mahdollinen \cite[s. 27]{Cools1997}. 
Myös edellä esitellyn polynomisen ideaalin kannan löytäminen
on vahvasti riippuvainen $N$:stä \cite[s. 141]{Cools2001},
jopa siinä määrin että Coolsin mielestä kubatuurisääntöjen
ja ortogonaalisten polynomien tutkiminen ei kannata
ennen kuin alarajoista osataan sanoa enemmän \cite[s. 2]{Cools2002}.

Polynomisten ideaalien ja kubatuurien välisestä yhteydestä on
vain pieni matka erääseen hyvin yleiseen alarajaan. Tarkastellaan
ensin $\field{P}_{k}^n$:n dimensiota, jos rajoitutaan pelkästään
tietylle integroimiasalueelle $\Omega$. Jos alue on esimerkiksi
$n$-pallon pinta $\Omega=\{\v{x}\mid \sum_{i=1}^nx_i^2=1\}$, niin kaikki
$\left(\sum_{i=1}^nx_i^2=1\right)^p,\;p\in\field{N}$ ovat yhteneväisiä
vakiopolynomin $1$ kanssa ja merkitään
\[ 
\dim[\field{P}_{k\vert\Omega}^n] = \binom{n+d}{n}-\binom{n+d-2}{n}.
\] 
Nyt jos kubatuuri on tarkka kaikille $\field{P}_{2k}^n$, niin saadaan alaraja 
\begin{equation} 
	N\geq \dim[\field{P}_{k\vert \Omega}^n].
	\label{eq_general_lower_bound}
\end{equation}

Kaavan \eqref{eq_general_lower_bound} ongelma on, että useimmissa tapauksissa
sitä ei ole mahdollista saavuttaa. Ne harvat tapaukset joissa tämä alaraja on saavutettu
on listattu lähteessä \cite[s. 29]{Cools1997}. Yhtä tapausta lukuunottamatta
niiden kaikkien tarkkuusaste on parillinen. Tämä ei ole yllättävää, sillä
kaavan \eqref{eq_general_lower_bound} alaraja on sama tarkkuusasteille $d=2k$ ja $d=2k+1$.

Toinen yleinen alaraja koskee keskipisteensä suhteen symmetrisiä kubatuureja.
Niiden tarkkuusaste on pariton ja niitä koskevan alarajan osoitti yleisesti
Möller \cite{Moller1976}. Olkoon keskipisteensä suhteen symmetrisen
kubatuurisäännön tarkkuusaste $d=2s+1,\;s\in\field{N}_0$ ja olkoon
$R_{2k}^n$ polynomiavaruus, johon kuuluu kaikki tarkkuusasteen $2k$ parilliset
polynomit ja  $R_{2k+1}^n$ polynomiavaruus, johon kuuluu kaikki tarkkuusasteen $2k+1$ parittomat
polynomit. Tällöin pisteiden määrälle $N$ pätee
\begin{equation}
	N\geq 2\dim[R_{s-1}^n]-
	\begin{cases}
		1& \text{jos s on parillinen,}\\
	 	0& \text{jos s on pariton.}
	\end{cases}
	\label{eq_moller1}	 
\end{equation}
Ilmaistuna eksplisiittisemmin kaavasta \eqref{eq_moller1} saadaan:
\begin{equation}
	N\geq \binom{n+s-1}{n}+
	\begin{cases}
		\sum_{k=1}^{n-1}2^{k-n}\binom{k+s-1}{k}& \text{jos s on parillinen,}\\
	 	\sum_{k=1}^{n-1}(1-2^{k-n})\binom{k+s-2}{k}& \text{jos s on pariton \cite{Lu2005}.}
	\end{cases}
	\label{eq_moller2}	 
\end{equation}
Möllerin alarajaa on havainnollistettu kuvassa \ref{fig_mollerpoints},
jossa alarajan mukainen pistemäärä on kuvattu ulottuvuuden $n$
ja tarkkuusasteen $d=2s-1$ funktiona.
\scalefig{fig_mollerpoints}{1.0}{Möllerin alaraja keskipisteensä
suhteen symmetrisille kubatuureille ulottuvuuden ja tarkkuusasteen funktiona}
Kuten kuvasta \ref{fig_mollerpoints} nähdään, lähtee
vaadittavien pisteiden määrä jyrkkään nousuun suurin piirtein 
kun tarkkuusaste ja ulottuvuuksien määrä on ylittänyt kymmenen.
Jos tarkkuusaste pidetään melko matalana, niin pisteiden
määrä ei kasva liian suureksi edes suurilla $n$:än arvoilla.
Esimerkiksi kun $n=100$, saadaan pisteiden
vähimmäismääräksi tarkkuusasteilla $d=5$ ja $d=7$
vastaavasti $N=10101$ ja $N=343600$. Hinrichs \emph{et al} ovat
vastikään johtaneet kubatuurit, jotka saavuttavat
näissä tilanteissa arvot $N=10701$ ja $N=404001$ 
(integroimisalueena $n$-kuutio ja vaatimuksena symmetrinen 
tulomuotoinen painofunktio) \cite{Hinrichs2007}. 
Nämä ovat ovat jo hyvin lähellä minimiä.
Möllerin alarajan perusteella voidaan joka tapauksessa päätellä,
että suuren dimension ja tarkkuusasteen ongelmissa ratkaisua
täytyy etsiä muualta kuin interpolatorisista kubatuureista.  





% Ortogonaalisiin polynomeihin päädytään tarkastelemalla
% yhtälöryhmää \eqref{eq_nonlinear_equations}. Oletetaan, että olemme
% hakemassa $N<\dim[\field{P}_d^n]$ pisteistä kubatuuria $Q$ integraalille $I$. Tällöin on löydyttävä
% $N$ lineaarisesti riippumatonta polynomia $U_1,\dots,U_N\in\field{P}_d^n$,
% jotka eivät häviä kaikissa pisteissä $\v{x_i}$. Vastaavasti löytyy myös
% $t=\dim[\field{P}_d^n]-N$ lineaarisesti riippumatonta polynomia $R_1,\dots,R_t\in\field{P}_d^n$
% jotka häviävät jokaisessa pisteessä $\v{x_i}$ ja nyt $\{U_1,\dots,U_N,R_1,R_t\}$ muodostavat
% $\field{P}_d^n$:n kannan.
% 	
% Sanotaan, että polynomi $f\in\field{P}^n$ on \emph{d-ortogonaalinen} integraalin $I$ suhteen,
% jos $I[fg]=0,\; fg\in\field{P}_d^n$. Selvästi, koska $Q$:n tarkkuusaste on $d$, on oltava \[ I[R_ip]=Q[R_ip]=0,\;\forall R_ip\in\field{P}_d^n. \]
% ja tällöin $R_i$:t ovat d-ortogonaalisia. Ortogonaalisten 


\subsection{Radonin 7 pisteinen kaava tasoalueille}

Seuraavaksi käydään läpi eräs klassinen esimerkki
kubatuurisäännöstä, jonka johtamisessa on hyödynnetty
moniulotteisia ortogonaalisia polynomeja. Tuloksena saatava
sääntö sisältää lisäksi todistettavasti pienimmän mahdollisen
määrän tukipisteitä kyseiselle tarkkuusasteelle, mikäli 
integroimisalue täyttää erään myöhemmin näytettävän ehdon \cite[s. 133]{Cools2001}.

Oletetaan siis nyt, että ollaan etsimässä approksimaatiota
kaksiulotteiselle integraalille $I$.
Ensinnäkin, kahdessa ulottuvuudessa voidaan muodostaa neljä
normalisoitua kolmannen asteen ortogonaalista polynomia. Merkitään
$P^3$:lla normalisoitua polynomia jonka asteluku on täsmälleen $3$ ja $Q$:lla
kaikkia kaksiulotteisia polynomeja joiden asteluku $\leq$ 2. Tällöin saadaan
kolmannen asteen ortogonaalisten polynomien kanta

\begin{equation}
	\begin{array}{rclrcl}
		P^{3}_0&=&x^3+Q_0,\;&
		P^{3}_1&=&x^2y+Q_1\\
		P^{3}_2&=&xy^2+Q_2,\;&
		P^{3}_3&=&y^3+Q_3
	\end{array} 
\end{equation}

Voidaan näyttää, että maksimissaan kolmella kolmannen
asteen ortogonaalisella polynomilla, olkoot ne $K_1$,$K_2$ ja $K_3$,  
on seitsemän yhteistä nollakohtaa ja nämä nollakohdat
ovat sellaisen kubatuurin pisteet, jonka tarkkuusaste on $5$. 
Ortogonaalisten polynomien välille
voidaan muodostaa riippuvuus $xK_1+yK_2=K_3$ \cite[s. 103]{Stroud1971}. 
Kahdelle ensimmäiselle saadaan
saadaan edellä esitellyn kannan avulla muodot
\[
K_1=\alpha P^3_1+\beta P^3_2+\gamma P_3^3,\;K_2=-\alpha P^3_0-\beta P^3_1+\gamma P_2^3,
\]
jossa $\alpha$,$\beta$ ja $\gamma$ täytyy valita siten, että myös $K_3$ on kolmannen
asteen ortogonaalipolynomi. Jos nyt määritellään vakiot
\[ 
	\begin{array}{rcl}
		A&=&\int_{\Omega}\left(P_0^3P_2^3-P_1^3P_1^3\right)\dd x \ds y  \\
		B&=&\int_{\Omega}\left(P_0^3P_3^3-P_1^3P_2^3\right)\dd x \ds y \\
		C&=&\int_{\Omega}\left(P_1^3P_3^3-P_2^3P_2^3\right)\dd x \ds y ,
	\end{array}
\]
niin parametrien $\alpha$,$\beta$ ja $\gamma$ ratkaisemiseksi saadaan yhtälöryhmä

\[
	\begin{bmatrix}
		0&A&B\\
		-A&0&C\\
		-B&-C&0
	\end{bmatrix}
	\begin{bmatrix}
		\alpha\\
		\beta\\
		\gamma
	\end{bmatrix}.
\]

Nyt jos pätee 
\begin{equation} 
	\label{eq_radon_constraint}
	A^2+B^2+C^2 >0,
\end{equation}
niin parametrit voidaan määrittää skalaarikerrointa vaille. Muutoin parametrit voidaan
valita vapaasti. Ehto \eqref{eq_radon_constraint} on selvästikin riippuvainen vain
integrointialueesta ja painofunktiosta. Sellainen alue, jolle ehto \eqref{eq_radon_constraint}
ei päde on onnistuttu muodostamaan ja tällöin on mahdollista muodostaa kubatuurisääntö
jossa on vain $6$ pistettä. Yleisille integroimisalueille, kuten neliölle ja vakiopainofunktiolle, 
ehto \eqref{eq_radon_constraint} kuitenkin pätee. Kun parametrit on laskettu matriisiyhtälön avulla,
saadaan selville $K_1$ ja $K_2$. $K_3$ saatiin ehdosta $xK_1+yK_2=K_3$.

Jos valitaan integroimisalueeksi neliö $C_2=\{(x,y)\mid \vert x \vert \leq 1,\;\vert y \vert \leq 1\}$
ja painofunktioksi vakio $1$, niin ratkaisemalla edellä esitellyt yhtälöt saadaan ortogonaalisiksi
polynomeiksi lopulta 
\begin{align*}
	K_1=&x^3-\frac{3}{5}x\\
	K_2=&xy^2-\frac{1}{3}x\\
	K_3=&x^2y+y^3-\frac{14}{15}y.
\end{align*}
Näiden nollakohdista saadaan ratkaistua kubatuurin pisteet, jonka jälkeen
painot saadaan pisteiden sijoittamisen jälkeen lineaarisesta yhtälöryhmästä \eqref{eq_nonlinear_equations}.
Lopullinen kubatuuri on \cite[s. 246]{Stroud1971}:

\begin{equation}
	\begin{array}{rl}
		\int_{C_2}f(x,y)\dd x \ds y \approx& \frac{8}{7}f(0,0)+\frac{5}{9}\sum_{i=1}^4f\left(\pm\sqrt{\frac{1}{3}},\pm\sqrt{\frac{3}{5}}\right)+\\
		&\frac{20}{63}\left(f\left(\sqrt{\frac{14}{15}},0\right)+f\left(-\sqrt{\frac{14}{15}},0\right)\right)
	\end{array}
	\label{eq_radon_square} 
\end{equation}
 
\section{Koeasetelma}

Koeasetelmassa keskitytään approksimoimaan kahden muuttujan
funktion integraalia
\begin{equation}
	I_1[f(x,y)]=\int_{C_2}f(x,y)\dd x \ds y, 
\end{equation} 
jossa siis integroimisalueena on neliö ja painofunktio $w(x)=1$.
Integrandeina käytetään funktioita
\begin{align*}
	F_1(x,y)=&e^{-\frac{1}{2(1-0.7^2)}\left(x^2+y^2-1.4xy)\right)}\\
	F_2(x,y)=&\sqrt{\vert xy \vert},
\end{align*}
joita on havainnollistettu kuvassa \ref{fig_3dfunc}. $F_1$ on skalaarikerrointa
lukuunottamatta kaksiulotteinen normaalijakauma, jonka odotusarvo on origo ja jonka
muuttujien välinen korrelaatio on $0.7$. Se on sileä funktio, joten polynomiapproksimaatioihin
perustuvien kubatuurien konvergenssin pitäisi olla nopea. Mikäli muuttujien välillä ei olisi
korrelaatiota, voisi tällaisen integrandin integroida yksiulotteisten integraalien tulona.
 
$F_2$ taas on valittu siten, että sen osittaisderivaatoilla on epäjatkuvuuskohtia. Tällaisen
integrandin polynomiapproksimaation konvergenssi on huomattavasti hitaampi kuin sileän
funktion tapauksessa. Todellisuudessa tässä tilanteessa kannattaisi hyödyntää
integraalin symmetriaa jakamalla integraali neljään identtiseen osaan, jolloin osittaisderivaattojen 
epäjatkuvuuskohtien yli ei tarvitsisi integroida
lainkaan. Nyt on kuitenkin pyritty konstruoimaan kubatuurien kannalta
haastava tilanne ja integraalia ei jaeta osiin.

\scalefig{fig_3dfunc}{1.00}{Ensimmäisen koetilanteen testifunktioiden kuvaajat. Integroimisaluetta $[-1,1]^2$ 
on pyritty havainnollistamaan läpinäkyvällä suorakulmaisella särmiöllä. Integraalin arvo
on särmiön ja funktion kuvaajan rajaama tilavuus. }


Kubatuureiksi valitaan seuraavat menetelmät:
\begin{itemize}
  \item $Q_{3^2}:=9$-pisteinen tulosääntö, joka perustuu aiemmin
  johdettuun $3$-pisteiseen Gaussin kvadratuuriin
  \item $Q_{7}:=7$-pisteinen Radonin minimisääntö
  \item $Q_{10^2}:=100$-pisteinen tulosääntö, joka perustuu $10$-pisteiseen Gaussin kvadratuuriin
  \item $Q_{68}:=68$-pisteinen rotaatioinvariantti korkean tarkkuusasteen kubatuuri.
\end{itemize}
$Q_{3^2}$:n yleinen tarkkuusaste on $5$, kuten myös $Q_{7}$:n tarkkuusaste. 
$Q_{10^2}$:n yleinen tarkkuusaste on $19$. $Q_{68}$:n tarkkuusaste on $19$ 
ja se on johdettu aiemmin esiteltyä invarianttimenetelmää käyttäen \cite{Omelyan2006}. 
Sen tukipisteiden määrä on myös pienin tunnettu sarjassaan. $Q_{3^2}$:n ja
$Q_{10^2}$ laskemiseksi käytettiin jo aiemmin mainittua MATLAB-funktiota,
jonka perusteella muodostettiin kaksiulotteinen tulosääntö. 
Funktio on esitetty liitteessä \ref{appendixA}.    

Kunkin kubatuurin käyttämät tukipisteet on merkitty kuvaan \ref{fig_points}, jossa pisteen
tummuus vastaa sen saamaa painoa (mitä tummempi, sitä suurempi paino). 
$Q_{10^2}$:n ja $Q_{10^2}$:n pisteiden jakaumat 
heijastavat niiden tulomuotoa. Selvästi on myös havaittavissa, että
pisteiden jakauma on tiheämpi ja painot suuremmat alueen reunoilla kuin sen keskellä.




\scalefig{fig_points}{0.7}{Koasetelmassa käytettyjen kubatuurien tukipisteet integroimisalueessa $C_2$. Pisteen tummuus vastaa
sen saamaa painoa.}

\section{Tulokset}

Koeasetelman tulokset on esitetty taulukossa \ref{table_results1}.
Siihen on lisäksi laskettu suhteellinen virhe $E[f]$, joka on saatu vertaamalla
kubatuurin tulosta oikeaan tulokseen. Ensimmäisen integrandin tapauksessa
on hyödynnetty MATLAB:in $mvncdf$ funktiota, joka pystyy takaamaan
annetun virhetoleranssin. Toiselle integrandille taas
on käytetty MATLAB:in funktiota $dblquad$, joka on tulomenetelmä ja 
perustuu kvadratuurifunktioon $quad$ \cite{MatlabQuad}. Myös $dblquad$ pystyy
takaamaan annetun virhetoleranssin.

\begin{table}[h!]
	\centering
	\topcaption{Koeasetelman tulokset}
	\input{matlab/results1.tex}
	\label{table_results1}
\end{table}

Tulosten perusteella kaikki neljä kubatuurisääntöä suoriutuivat
$F_1$:n integroimisesta hyväksyttävästi. $Q_7$:n $2.6\%$:n virhe on tosin
melkein $9$ kertaa suurempi kuin toiseksi suurin virhe. Tämä johtuu
todennäköisesti siitä, että $Q_{3^2}$ integroi tarkasti
hieman suuremman joukon polynomeja kuin $Q_7$ ($Q_{3^2}$:n \emph{yleinen} tarkkuusaste
on sama kuin $Q_7$:n tarkkuusaste). Esimerkiksi $E\big[Q_{3^2}[x^5y^5]\big]=0$, mutta
$E\big[Q_{7}[x^5y^5]\big]\neq 0$. Kuten oli odotettavissa, $Q_{10^2}$ ja $Q_{68}$ saavuttivat
erittäin tarkan tuloksen.  Se, että $Q_{10^2}$:n absoluuttinen virhe oli
luokkaa $10^{-13}$ ja $Q_{68}$:n luokkaa $10^{-9}$ johtunee myös tässä
tapauksessa tulosäännön yleisestä tarkkuusasteesta.

$F_2$ tuotti alhaisen tarkkuusasteen kubatuureille $Q_{3^2}$ ja $Q_7$
huomattavia ongelmia. Kummankaan tulos ei ole käyttökelpoinen, mutta
$Q_{3^2}$:n virhe on todella suuri. Tämän täytyy johtua tukipisteiden
sijoittumisesta epäedullisesti $F_2$:n integroinnin suhteen.
Korkean tarkkuusasteen säännöt saavuttavat hankalasta integrandista 
huolimatta melko hyvän tuloksen ja tulosäännön hiukan pienempi 
virhe johtunee jälleen sen yleisestä tarkkuusasteesta. 
Kuten aiemmin jo todettiin, parempiin
tuloksiin pääsemiseksi tulisi hyödyntää integraalin symmetriaa.

\section{Yhteenveto}

Yhden muuttujan funktioiden numeerinen integrointi on ongelma,
jonka ratkaisemiseksi on tarjolla tehokkaita menetelmiä. 
Annetulla tukipisteiden määrällä ovat
Gaussin kvadratuurit näistä polynomiapproksimaation
kannalta tarkimpia. Niiden käyttäminen vaatii kuitenkin
painojen selvittämisen lisäksi myös tukipisteiden laskemisen, joka
kuitenkin onnistuu ratkaisemalla tiettyjen ortogonaalisten
polynomien nollakohtia.
Useimmissa tapauksissa riittää niinkin yksinkertainen
keino kuin Simpsonin menetelmä, jonka adaptiivista versiota
käyttää esimerkiksi MATLAB:in kvadratuurifunktio $quad$ \cite{MatlabQuad}.
Konvergenssi on taattu, jos integroimisväli vain jaetaan tarpeeksi
pieniin osiin ja huomioidaan mahdolliset derivataan epäjatkuvuuskohdat.

Tilanne muodostuu huomattavasti ongelmallisemmaksi muuttujien määrän,
eli integraalin dimension, kasvaessa. Tällöin erilaisia
integroimisalueita on ääretön määrä. Mikäli integroimisalue 
(ja painofunktio) on mahdollista
saattaa tulomuotoon, voidaan ainakin kahdessa ja
kolmessa dimensiossa hyvin käyttää yhden dimension
menetelmään, yleensä Gaussin kvadratuuriin, perustuvaa tulosääntöä.
Tulosääntöjä käytettäessa tarvittavien pisteiden, ja siis funktioevaluaatioiden,
määrä kasvaa eksponentiaalisesti dimension suhteen. Tätä kutsutaan
dimensionaalisuuden kiroukseksi.

Dimensionaalisuuden kirousta on mahdollista paeta käyttämällä
interpolatorisia kubatuureja. Tällöin vaadittavien funktioevaluaatioiden
määrä ei enää riipu eksponentiaalisesti dimensiosta. Näiden menetelmien
suurin ongelma on kuitenkin niiden määrittäminen. Gaussin kvadratuurin idea
voidaan muotoilla myös monessa ulottuvuudessa, mutta analogisen
kubatuurin olemassaolo vaatii, että integroimisalueesta ja painofunktiosta
riippuvilla moniulotteisilla ortogonaalisilla polynomeilla
on tarpeeksi suuri määrä yhteisiä nollakohtia. Tiedetään, että näin
ei ole tavallisten integroimisalueiden, kuten neliön tai kolmion,
ja vakiopainofunktion tapauksessa.

Vaikka tavallisesti ei voidakaan saavuttaa Gaussin kvadratuurien
mielessä optimaalista pisteiden määrää, interpolatorinen kubatuuri
on kuitenkin olemassa jokaiselle integraalille. Sen määrittäminen
voi kuitenkin olla äärimmäisen vaikeaa, sillä se vaatii
suuren epälineaarisen yhtälöryhmän ratkaisemista. Vaikeutta lisää myös 
se, että yleisessä tapauksessa vaadittavien pisteiden vähimmäismäärää ei tiedetä
ja jotta yhtälöryhmä voitaisiin edes muodostaa, täytyisi pistemäärälle
saada jokin arvio. Tilannetta voidaan helpottaa hyödyntämällä approksimoitavan
integraalin symmetriaa. Pakottamalla etsittävälle kubatuurisäännölle tietty
symmetria voidaan yhtälöryhmää huomattavasti pienentää ja sen jälkeen
se voidaan yrittää ratkaista hyödyntämällä tietokoneiden suurta
laskentatehoa \cite[s. 6]{Cools2002}. Tyypillinen esimerkki tällaisesta
proseduurista löytyy lähteestä \cite{Stoyanova2009}. Kattava tietokanta
julkaistuista interpolatorisista kubatuureista on pyritty muodostamaan lähteessä \cite{Cools2003}. 

Vaikka interpolatoristen kubatuurien ratkaiseminen olisi helpompaa,
on selvää että joka tapauksessa vaadittavien pisteiden
määrä nousee liian suureksi jos dimensioita on muutamaa
kymmentä enemmän. Tällöin täytyy turvautua täysin eri typpisiin
menetelmiin, kuten erilaisiin Monte-Carlo menetelmiin. Suuridimensioisia
integraaleja käsitellään esimerkiksi lähteissä \cite{Cools2009,Cools2010}. 

\clearpage{}

\addcontentsline{toc}{section}{Viitteet}
\bibliographystyle{bababbrv-fl}
\bibliography{kandi}

%% Liitteet 
\appendix 
\clearpage
%\addcontentsline{toc}{section}{Liite A}

\section[Liite]{MATLAB-funktio\label{appendixA}}


\lstinputlisting[label=fun_trefethen2D]{/Users/dennari/Documents/MATLAB/gauss2D.m}



\end{document}