szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lis 2011, o 17:49 
Gość Specjalny
Avatar użytkownika

Posty: 17291
Lokalizacja: Cieszyn
Konstruowanie kwadratur interpolacyjnych


Poniższy tekst powstał w związku z wątkiem 270679.htm i moją odopwiedzią na jedno z zadanych pytań. POnieważ jest długi, na pewno wkradły się do niego pewne nieścisłości, błędy w rachunkach, oznaczeniach itp. Bardzo proszę o ich sygnalizowanie na PW oraz o wszelkie uwagi krytyczne.


Przypuśćmy, że dana jest całkowalna funkcja nieujemna p:[a,b]\to\mathbb{R}, dodatnia prawie wszędzie (tzn. p(x)>0 dla prawie wszystkich x\in[a,b], inaczej, zbiór \left\{x:p(x)\le 0\right\} ma miarę Lebesgue'a zero). Wtedy \int_a^bp(x)\text{d}x>0. Funkcję p nazywamy funkcją wagową.

W praktycznej realizacji wystarczy myśleć, że p jest funkcją ciągłą, dodatnią, dopuszczając ewentualnie p(a)=0 czy p(b)=0, choć niekoniecznie.

Naszym zadaniem będzie przybliżenie całki

\int_a^bf(x)\cdot p(x)\text{d}x

za pomocą kwadratury interpolacyjnej postaci

\sum_{k=1}^n\lambda_kf(x_k)\,,

gdzie x_1,\dots,x_n\in[a,b] są ustalonymi punktami, zwanymi węzłami kwadratury, a liczby \lambda_1,\dots,\lambda_n są ustalonymi współczynnikami. Ponieważ powyższa kwadratura zawiera n węzłów, nazwiemy ją kwadraturą n-punktową.

Kwadratury interpolacyjne projektuje się w ten sposób, aby były dokładne na wielomianach określonego rzędu (wielomian jest rzędu m, jeśli jest stopnia co najwyżej m). Oznacza to, że równość

\int_a^bw(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\lambda_kw(x_k)

zachodzi dla każdego wielomianu z góry ustalonego rzędu.

Rozpocznijmy od wykazania, że kwadratura n-punktowa może być dokładna na wielomianach rzędu maksymalnie 2n-1. W tym celu podamy wielomian w stopnia 2n, dla którego nie zachodzi powyższa równość.

Niech

p_n(x)=(x-x_1)\cdots(x-x_n)\,,

a w(x)=p_n^2(x).

Mamy z jednej strony

\int_a^bw(x)\cdot p(x)\text{d}x>0\,,

co wynika z własności funkcji wagowej i z tego, że w(x)>0 dla prawie wszystkich x, a z drugiej strony

\sum_{k=1}^n\lambda_kw(x_k)=0\,,

gdyż x_1,\dots,x_n są pierwiastkami wielomianu w. Nasza kwadratura nie jest więc dokładna na tym wielomianie.

Skonstruujemy teraz kwadraturę w pewnym sensie optymalną, tj. n-punktową dokładną na wielomianach rzędu 2n-1, bo wyższego rzędu dokładności nie uzyskamy. Niech ma ona postać

\int_a^b f(x)p(x)\text{d}x\approx \sum_{k=1}^n\lambda_kf(x_k)\,.

Na razie węzły x_1,\dots,x_n\in[a,b] i współczynniki \lambda_1,\dots,\lambda_n są bliżej nieokreślone. Spróbujemy dowiedzieć się o nich czegoś więcej.

Najpierw załóżmy, że kwadratura po prawej stronie powyższego wzoru jest dokładna na wielomianach rzędu 2n-1.

W tym miejscu należy wprowadzić parę pojęć.

Rozpocznijmy od całkowego iloczynu skalarnego z funkcją wagową p. Jest to funkcjonał postaci

\langle f,g\rangle=\int_a^bf(x)g(x)\cdot p(x)\text{d}x

określony na (rzeczywistej) przestrzeni liniowej wszystkich funkcji całkowalnych w przedziale [a,b]. Czytelnikowi pozostawiam sprawdzenie, jest to rzeczywiście iloczyn skalarny. Wystarczy sprawdzić aksjomaty tego iloczynu.

Powiemy, że funkcje całkowalne f,g:[a,b]\to\mathbb{R}ortogonalne, jeśli \langle f,g\rangle=0.

Dalej, ciąg wielomianów (Q_1,Q_2,\dots,Q_n,\dots), gdzie każdy wielomian Q_k jest stopnia k, jest ortogonalny, jeśli wielomiany Q_i,Q_j są ortogonalne dla wszystkich i\ne j. Można zauważyć, że wielomian Q_k jest wtedy ortogonalny do każdego wielomianu stopnia niższego niż k. Będziemy mówili krótko, że wielomiany Q_1,Q_2,\dots są ortogonalne w [a,b] z funkcją wagową p.

Teoria wielomianów ortogonalnych mówi, że wszystkie wielomiany ortogonalne są wyznaczone jednoznacznie z dokładnością do współczynnika wiodącego (tego przy najwyższej potędze), każdy z nich ma tyle pierwiastków, ile wynosi jego stopień, pierwiastki te są rzeczywiste, jednokrotne i leżą wewnątrz przedziału [a,b], czyli w przedziale (a,b).

Weźmy teraz dowolny wielomian q rzędu n-1. Zatem iloczyn p_nq jest wielomianem rzędu 2n-1, skąd otrzymujemy

\langle p_n,q\rangle=\int_a^b p_n(x)q(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\lambda_kp_n(x_k)q(x_k)=0\,,

skąd wynika, że p_n jest wielomianem ortogonalnym stopnia n w rodzinie wielomianów ortogonalnych. Wynika stąd, że węzły x_1,\dots,x_n są pierwiastkami wielomianu ortogonalnego stopnia n.

Wiemy już dużo o węzłach kwadratury n-punktowej dokładnej na wielomianach rzędu 2n-1. Są one bardzo konkretne. Maksymalny rząd dokładności kwadratury spowodował, że węzły muszą być pierwiastkami wielomianu ortogonalnego.

A co ze współczynnikami \lambda_1,\dots,\lambda_n?

Żeby je wyznaczyć, konieczne jest następne pojęcie.

Wielomianami podstawowymi Lagrange'a nazywamy wielomiany

\ell_k(x)=\frac{p_n(x)}{(x-x_k)p_n'(x_k)}\,,\quad k=1,\dots,n\,.

Są one stopnia n-1. Mają bardzo ważną własność:

\ell_k(x_k)=1,\,\quad\ell_k(x_i)=0\,,\;k\ne i\,,\;k,i=1,\dots,n\,.

Ponadto dla każdej funkcji f:[a,b]\to\mathbb{R} wielomian w rzędu n-1 interpolujący tę funkcję w węzłach x_1,\dots,x_n, tj. spełniający warunki interpolacyjne

w(x_k)=f(x_k)\,,\quad k=1,\dots,n\,,

ma postać

w(x)=\sum_{k=1}^n\ell_k(x)f(x_k)\,.

Taki wielomian jest wyznaczony jednoznacznie.

Skoro wielomiany podstawowe Lagrange'a są stopnia n-1, to są też rzędu 2n-1. Rozważana przez nas kwadratura jest dokładna na takich wielomianach. Zatem, dla j=1,\dots,n\,, mamy

\int_a^b\ell_j(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\lambda_k\ell_j(x_k)=\lambda_k\,.

Dalej, wielomiany \ell_j^2 są stopnia 2n-2, a więc także rzędu 2n-1. Dlatego

0<\int_a^b\ell_j^2(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\lambda_k\ell_j^2(x_k)=\lambda_k\,,

co dowodzi dodatniości współczynników \lambda_1,\dots,\lambda_n.

Podsumowując tę część rozumowania stwierdzamy, że jeśli

\int_a^bf(x)\cdot p(x)\text{d}x\approx\sum_{k=1}^n\lambda_kf(x_k)

jest n-punktową kwadraturą dokładną na wielomianach rzędu 2n-1, to węzły x_1,\dots,x_n są pierwiastkami wielomianu ortogonalnego n-tego stopnia w ciągu wielomianów ortogonalnych w [a,b] z funkcją wagową p, a współczynniki \lambda_1,\dots,\lambda_n są dodatnie i wyrażają się wzorami

\lambda_k=\int_a^b\ell_k(x)\cdot p(x)\text{d}x\,,\quad k=1,\dots,n\,.

Wykażemy, teraz że jeśli x_1,\dots,x_n,\lambda_1,\dots,\lambda_n są określone jak powyżej, to kwadratura

\int_a^bf(x)\cdot p(x)\text{d}x\approx\sum_{k=1}^n\lambda_kf(x_k)

jest dokładna na wielomianach rzędu 2n-1. W tym celu ustalmy dowolny wielomian w rzędu 2n-1. Dzieląc go z resztą przez p_n(x)=(x-x_1)\cdots(x-x_n) otrzymujemy istnienie wielomianów q (ilorazu) oraz r (reszty) rzędu n-1 takich, że

w(x)=p_n(x)q(x)+r(x)\,.

Ale ponieważ węzły kwadratury są pierwiastkami wielomianu ortogonalnego stopnia n, to p_n(x) jest, z dokładnością do współczynnika wiodącego, tym właśnie wielomianem. Jest on w szczególności ortogonalny do każdego wielomianu stopnia niższego niż n. Dlatego

\int_a^bp_n(x)q(x)\cdot p(x)\text{d}x=0\,.

Zatem

\int_a^bw(x)\cdot p(x)\text{d}x=\int_a^bp_n(x)q(x)\cdot p(x)\text{d}x+\int_a^br(x)\cdot p(x)\text{d}x=\int_a^br(x)\cdot p(x)\text{d}x\,.

Ale r, jako wielomian rzędu n-1, jest równy swojemu wielomianowi interpolacyjnemu Lagrange'a:

r(x)=\sum_{k=1}^n\ell_k(x)r(x_k)\,.

Dochodzimy więc do

\begin{aligned}
 \int_a^br(x)\cdot p(x)\text{d}x
 &=\int_a^b\sum_{k=1}^n\ell_k(x)r(x_k)\cdot p(x)\text{d}x=\\
 &=\sum_{k=1}^nr(x_k)\int_a^b\ell_k(x)\cdot p(x)\text{d}x
 =\sum_{k=1}^nr(x_k)\lambda_k\,.
\end{aligned}

Biorąc teraz pod uwagę dzielenie wielomianu w przez p_n oraz to, że p_n(x_k)=0, k=1,\dots,n\,, dostajemy

w(x_k)=p_n(x_k)q(x_k)+r(x_k)=r(x_k)\,,\quad k=1,\dots,n

oraz

\int_a^br(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\lambda_kr(x_k)=\sum_{k=1}^n\lambda_kw(x_k)

Ostatecznie

\int_a^bw(x)\cdot p(x)\text{d}x
=\int_a^br(x)\cdot p(x)\text{d}x
=\sum_{k=1}^n\lambda_kw(x_k)\,,

skąd wynika dokładność naszej kwadratury na wielomianach rzędu 2n-1.

Skonstruowana kwadratura nazywa się kwadraturą Gaussa. Dla przedziału [-1,1] i funkcji wagowej p(x)=1 otrzymujemy kwadraturę Gaussa-Legendre'a.

Jednopunktowa kwadratura Gaussa-Legendre'a

\int_{-1}^1f(x)\text{d}x\approx 2f(0)

Dwupunktowa kwadratura Gaussa-Legendre'a

\int_{-1}^1f(x)\text{d}x\approx f\biggl(-\frac{\sqrt{3}}{3}\biggr)+f\biggl(\frac{\sqrt{3}}{3}\biggr)

Trzypunktowa kwadratura Gaussa-Legendre'a

\int_{-1}^1f(x)\text{d}x\approx \frac{5}{9}f\biggl(-\frac{\sqrt{15}}{5}\biggr)+\frac{8}{9}f(0)+\frac{5}{9}f\biggl(\frac{\sqrt{15}}{5}\biggr)

Czteropunktowa kwadratura Gaussa-Legendre'a

\begin{aligned}
 \int_{-1}^1f(x)\text{d}x&\approx
  \frac{18+\sqrt{{30}}}{36}
   \left[
     f\left(-\frac{\sqrt{525-70\sqrt{{30}}}}{35}\right)
    +f\left(\frac{\sqrt{525-70\sqrt{{30}}}}{35}\right)
   \right]+\\[2ex]
  &+\frac{18-\sqrt{{30}}}{36}
   \left[
     f\left(-\frac{\sqrt{525+70\sqrt{{30}}}}{35}\right)
    +f\left(\frac{\sqrt{525+70\sqrt{{30}}}}{35}\right)
   \right] 
\end{aligned}

Pięciopunktowa kwadratura Gaussa-Legendre'a

\begin{aligned}
 \int_{-1}^1f(x)\text{d}x&\approx
  \frac{128}{225}f(0)+
  \frac{322+13\sqrt{{70}}}{900}
   \left[
     f\left(-\frac{\sqrt{245-14\sqrt{{70}}}}{21}\right)
    +f\left(\frac{\sqrt{245-14\sqrt{{70}}}}{21}\right)
   \right]+\\[2ex]
  &+\frac{322-13\sqrt{{70}}}{900}
    \left[
      f\left(-\frac{\sqrt{245+14\sqrt{{70}}}}{21}\right)
     +f\left(\frac{\sqrt{245+14\sqrt{{70}}}}{21}\right)
    \right]
\end{aligned}

Węzły x_k kwadratur Gaussa-Legendre'a więcej niż pięciopunktowych (tj. pierwiastki odpowienich wielomianów ortogonalnych zwanych wielomianami Legendre'a) nie wyrażają się przez pierwiastniki, tzn. w formie podobnej do powyższych wzorów. Występuje tu tzw. casus irreducibilis. Podobnie jest ze współczynnikami \lambda_k, gdyż wzory na te współczynniki zawierają węzły x_k.

Na zakończenie odpowiedź na pytanie dlaczego omawiana kwadratura nazywa się interpolacyjną. Wartość tej kwadratury dla funkcji f, czyli wielkość

\sum_{k=1}^n\lambda_kf(x_k)\,,

jest równa całce wielomianu w rzędu n-1 interpolującego funkcję f w węzłach x_1,\dots,x_n\,. Można to łatwo sprawdzić. Zapiszmy w tym celu wspomniany wielomian stosując wzór interpolacyjny Lagrange'a:

w(x)=\sum_{k=1}^n\ell_k(x)f(x_k)

i scałkujmy go:

\int_a^bw(x)\cdot p(x)\text{d}x=\sum_{k=1}^n\int_a^b\ell_k(x)\cdot p(x)\text{d}x\cdot f(x_k)=\sum_{k=1}^n\lambda_kf(x_k)\,.

Zatem

\int_a^bf(x)\cdot p(x)\text{d}x
\approx\sum_{k=1}^n\lambda_kf(x_k)=\int_a^bw(x)\cdot p(x)\text{d}x\,.


Można wykazać jeszcze więcej. Tak naprawdę wielkość

\sum_{k=1}^n\lambda_kf(x_k)\,,

jest równa całce wielomianu w rzędu 2n-1 interpolującego funkcję f w węzłach x_1,\dots,x_n wraz z wartościami pochodnych, tzn. spełniającego warunki interpolacyjne

w(x_k)=f(x_k)\,,\quad w'(x_k)=f'(x_k)\,,\quad k=1,\dots,n\,.

Wielomian w zapisujemy stosując wzór interpolacyjny Hermite'a i rozumując analogicznie jak powyżej. Pozwolę sobie pominąć szczegółowe rachunki, które są dość żmudne.
Góra
Instytut Matematyczny, Uniwersytet Wrocławski
Utwórz nowy temat Ten temat jest zamknięty. Nie możesz w nim pisać ani edytować postów.  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kwadratury Interpolacyjne - zadanie 2  arus512  4
 rząd kwadratury newtona-cotesa  angelst  3
 [C++] Kwadratury Gausa-Hermite  pag15  0
 Rząd kwadratury  Octothorp  3
 Kwadratury złożone.  ext  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com