Wielomiany Czebyszewa

Wielomiany Czebyszewa definiujemy rekurencyjnie: $ T_{-1}\equiv0 $, $ T_0\equiv1 $ oraz
\begin{equation}(#)
T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)
\end{equation}
albo ze wzoru:
\begin{equation}(#)
T_n(x)=\cos(n*\arccos(x)) \qquad x\in[-1,1].
\end{equation}
W tym rozdziale przetestujemy podstawowe własności tych wielomianów.

  1. Napisz rekurencyjną funkcję octave'a obliczającą wartość wielomianu zadanego poprzez współczynniki w bazie Czebyszewa wprost ze wzoru rekurencyjnego ( [link]), tzn. parametrami funkcji będą:
    • $ x $ argument dla którego chcemy obliczyć wartość wielomianu
    • $ a $ - wektor zawierający współczynniki $ a_0,\ldots,a_n $ takie, że $ w(x)=\sum_{k=0}^n a_k T_k(x) $.
    • $ n $ - stopień wielomianu (parametr opcjonalny, można tę wartość uzyskać
      z wektora $ a $)

    Funkcja octave'a ma zwrócić wartość $ w(x) $.

    Przetestuj tę funkcję dla $ w(x)=T_{15}(x) $, tzn. narysuj dwa wykresy
    $ T_{15}(x) $ raz korzystając z tej funkcji oraz drugi raz korzystając wprost ze wzoru ( [link]).

  2. Napisz nierekurencyjną funkcję octave'a

        

     function [Y]=Czebyszew(X,a,n)

    obliczającą wartość wielomianu zadanego poprzez współczynniki w bazie Czebyszewa z wzoru ( [link]), tzn. parametry wejściowe funkcji
    to:

    • macierz $ X=(x_{i j})_{i j} $, wymiaru $ k\times l $
    • wektor współczynników
      $$a=[a_0,\ldots,a_n]$$

      takich, że

      $$w(x)=\sum_{k=0}^n a_k T_k(x).$$
    • $ n $ stopień wielomianu; ten parametr może być opcjonalny, jeśli go nie podamy to funkcja powinna przyjąć, że $ n $ to wymiar wektora współczynników minus jeden.

    Funkcja octave'a powinna zwrócić macierz $ Y=(y_{i j})_{i j} $, wymiaru $ k\times l $ z wartościami $ y_{i j}= w(x_{i j}) $.

    Funkcja ma korzystać z wzoru rekurencyjnego ( [link]), ale jako funkcja octave'a ma być nierekurencyjna. Koszt algorytmu powinien wynosić
    $ k*l*O(n) $.

    Narysuj dwa wykres
    $ T_{3}(x) $ - jeden korzystając z tej funkcji oraz drugi - ze wzoru ( [link]).

  3. Sprawdź obliczeniowo, czy powyższe wzory na wielomiany Czebyszewa: wzór definiujący wielomiany Czebyszewa rekurencyjnie ( [link]) i ( [link]), są zgodne na odcinku $ [-1,1] $. Tzn. dla dużej ilości np. $ 10000 $ losowych punktów na $ [-1,1] $ policz wartości $ T_{32} $ ze wzoru
    $$T_{32}(x)=\cos(32*\arccos(x))$$

    oraz ze wzoru rekurencyjnego ( [link]).

    Policz maksimum wartości absolutnych z różnicy między wartościami wielomianu obliczonymi obiema metodami. Porównaj czas obliczania wartości tego wielomianu obydwoma wzorami.

    Powtórz testy ale dla wielomianów innych stopni, np. $ T_7,T_{50} $.

  4. Narysuj korzystając z wzoru
    $$T_n(x)=\cos(n*\arccos(x))$$

    wykres wielomianów $ T_n $ dla $ n=0,1,2,3,4,5 $. Policz dyskretną normę maksimum na siatce. Czy wynosi jeden? Policz na wykresie zera oraz ekstrema każdego z wielomianów.

  5. Wyznacz zera i ekstrema $ T_{10} $ i $ T_{15} $ ze wzoru $ T_n(x)=\cos(n*\arccos(x)) $. Sprawdź wartości
    tych wielomianów w jego zerach i ekstremach.

  6. Sprawdzenie własności optymalności zer wielomianu Czebyszewa jako węzłów interpolacji Lagrange'a.

    Chcemy eksperymentalnie sprawdzić, czy wielomian $ 2^{-n}T_{N+1}(x) $ ma minimalną normę supremum na $ [-1,1] $ wśród wszystkich wielomianów postaci $ \Pi_{k=0}^N(x-x_k) $.

    Policz dla $ N+1 $ różnych losowych węzłów $ x_k $, $ k=0,\ldots,N $ z odcinka $ [-1,1] $ dla $ N=2,4,8,16,32 $ i kilkuset różnych losowych zestawów
    przybliżoną normę supremum wielomianu $ \Pi_{k=0}^n(x-x_k) $.

    Przeprowadź testy również
    dla węzłów Czebyszewa (czyli zer $ T_{N+1} $) oraz węzłów równoodległych dla tego samego $ N $.

  7. Sprawdzenie własności ekstremalnej wielomianów Czebyszewa.

    Z teorii wiadomo, że wielomian $ 2^{-n}T_{N+1}(x) $ ma minimalną normę supremum na $ [-1,1] $ wśród wszystkich wielomianów postaci

    $$w(x)=x^{n+1}+\sum_{k=0}^na_kx^k.$$

    Chcemy sprawdzić eksperymentalnie, czy ta własność się potwierdzi.

    Policz dla $ N+1 $ losowych współczynników $ a_k $ dla $ k=0,\ldots,N $
    przybliżoną normę supremum wielomianu:

    $$w(x)=x^{n+1}+\sum_{k=0}^na_kx^k.$$

    Przetestuj dla $ N=2,4,8,16,32 $ i co najmniej kilku tysięcy różnych losowych zestawów
    węzłów. Węzły losujemy funkcją randn() zwracającą liczby losowe o rozkładzie normalnym.

  8. Sprawdzenie własności ekstremalnej wielomianów Czebyszewa przyjmujących ustaloną wartość poza $ [-1,1] $.

    Chcemy sprawdzić, czy dla dowolnego punktu $ a=2 $ i $ b\not=1 $ wielomian

    $$w^*(x)=T_n(x)/T_n(2)$$

    ma minimalną normę supremum na $ [-1,1] $ wśród wszystkich wielomianów $ w $ stopnia nie większego od $ n+1 $ przyjmujących wartość $ b $ w punkcie $ a $.

    Policz dla $ n $ losowych współczynników $ a_k $ z $ k=1,\ldots,n $ dla $ n=2,4,8,16,32 $ i co najmniej kilku tysięcy różnych losowych zestawów
    węzłów
    przybliżoną normę supremum wielomianu

    $$w(x)=1+\sum_{k=1}^n a_k(x-2)^k$$

    i porównaj z normą supremum $ w^* $ na $ [-1,1] $ równą $ 1/T_n(2) $ (dlaczego tyle ona wynosi?).

    Węzły losujemy funkcją randn() zwracającą liczby losowe o rozkładzie normalnym.

  9. \textrm{Funkcja octave'a służąca przybliżonemu obliczaniu całek po odcinkach} (zadanie pomocnicze)

    Zapoznaj się z funkcją octave'a quad().

    Policz całkę przy pomocy funkcji quad() z
    $ \sin(x) $ na $ [-\pi,2*\pi] $.

  10. (trudne) Iloczyn skalarny typu $ L^2_w(a,b) $.

    Napisz funkcję octave'a:

     function [nl2]=IlSkL2w(FCN,GCN,a,b,FCNW)

      komendy octave'a

      nl2=....

     endfunction

     

    która oblicza iloczyn skalarny typu $ L^2_w(a,b) $ z wagą $ w(x) $ tzn.:

    $$<br /> (f,g)_{L^2_w(a,b)}=\int_a^b f(x)g(x)w(x) \:dx<br /> $$

    dla danej funkcji wagowej $ w(x) $ i funkcji $ f,g $.

    Parametry funkcji to:

    • wskaźniki do funkcji $ FCN $, $ GCN $ do dwóch funkcji octave'a

      function y=f(x)

        y=......
      endfunction

      function y=g(x)

        y=......
      endfunction

      obliczających odpowiednio wartości funkcji $ f(x) $ i $ g(x) $ dla $ x\in[a,b] $.

    • $ a $, $ b $ - końce odcinka całkowania $ [a,b] $,
    • $ FCNW $ to wskaźnik do funkcji wagowej

      function y=w(x)

        y=......
      endfunction

    Funkcja powinna zwrócić przybliżenie iloczynu skalarnego obliczone za pomocą funkcji octave'a quad().

    W przypadku wywołania funkcji IlSkL2() tylko z czterema pierwszymi argumentami (tzn. bez podania wskaźnika do wagi) funkcja powinna zwrócić iloczyn skalarny z wagą $ w \equiv 1 $.

  11. Ortogonalność wielomianów Czebyszewa w $ L^2_{\frac{1}{\sqrt{1-x^2}}}(-1,1) $.

    Sprawdź eksperymentalnie w octavie, np. za pomocą funkcji quad() lub własnej funkcji z poprzedniego zadania, czy wielomiany Czebyszewa tworzą układ ortogonalny w $ L^2_{\frac{1}{\sqrt{1-x^2}}}(-1,1) $, tzn. czy prawdą jest, że

    $$<br /> \int_{-1}^1 T_n(x)T_m(x)\frac{1}{\sqrt{1-x^2}} \:dx =<br /> \left\{<br /> \begin{array}{lr}<br /> 0 & m\not=n,\\<br /> \frac{\pi}{2} & m=n>0, \\<br /> \pi & \qquad m=n=0.<br /> \end{array}<br /> \right.<br /> $$

    Sprawdź powyższe zależności dla różnych $ m,n $ różnej wielkości np. dla $ m=0,1,2,3,100,1000 $ i $ n=0,3,10,500,1004 $.