\documentclass[10pt,a4paper]{article}

%% Polonizacja
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

%% Twierdzenia
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{df}{Definicja}[section]

\begin{document}

\newcounter{seria}
\setcounter{seria}{2}
\newcommand*{\preparedby}{Jakub Narębski}
\input{naglowek.tex}

\section{Postacie wielomianów, obliczanie wartości wielomianu 
  w~punkcie, konwersje między różnymi postaciami}
\label{sec:wstep}


\subsection{Postać potęgowa (naturalna) wielomianu}
\label{sec:potegowa}

Najczęściej spotykanym sposobem zapisu wielomianów jest ich zapis
w~bazie jednomianów \(\{1, x, x^2, \dots, x^n, \ldots\}\), czyli tzw.
\textbf{postać potęgowa}.  Nie jest on zawsze najwygodniejszy: drobne
błędy we współczynnikach (w tej bazie) mogą powodować znaczne zmiany
własności wielomianu (np. położenie miejsc zerowych).  Wielomian
$W(x)$ dany jest w~tej postaci wzorem:
\begin{equation}
  \label{eq:potegowa}
  W(x) =  \sum_{k=0}^{n} a_k x^k
\end{equation}

Klasyczny algorytm obliczania wartości wielomianu w~punkcie:
\begin{align*}
  w_0 &= a_0,\\
  w_i &= w_{i-1} + a_i x x^{i-1} ,\quad\text{dla\ }i=1,\dots,n
\end{align*}
wymaga $2 n$ mnożeń i~$n$ dodawań.

Aby policzyć wartość wielomianu możemy zastosować szybszy
\textbf{algorytm Hornera}.  Korzystamy ze wzoru
\begin{equation}
  \label{eq:Horner}
  W(x) = (\ldots(a_n x+ a_{n-1}) x + \dots + a_1) x+a_0.
\end{equation}
Algorytm dany jest wzorem
\begin{subequations}
\label{eq:Horner:alg}
\begin{align}
  w_n &= a_n,\\
  w_i &= w_{n+1} x + a_i,\quad\text{dla\ }i = n-1,n-2,\dots,0.
\end{align}
\end{subequations}
Wymaga on $n$ mnożeń i~$n$ dodawań.

\textbf{Zadanie 1.} Napisać procedurę (program), obliczającą wartość
wielomianu (zadanego za pomocą tablicy współczynników w~bazie
naturalnej $1, x, x^2, x^3,\dots$) w~danym punkcie metodą
\emph{Hornera}.



\subsection{Postać Newtona wielomianu}
\label{sec:Newtona}

W~zagadnieniach związanych z~interpolacją funkcji użyteczna będzie
\textbf{postać Newtona} wielomianu, czyli użycie bazy \(\{1,
x-x_0,(x-x_0)(x-x_1), \dots , (x-x_0)\dots(x-x_n),\ldots\}\), gdzie
\(x_0,x_1,\dots,x_n,\ldots\) są danymi liczbami.  Wielomian
$W(x)$ dany jest w~tej postaci wzorem:
\begin{equation}
  \label{eq:Newtona}
  W(x) 
  = b_0 + \sum_{i=1}^n b_i P_i(x)
  = b_0 + \sum_{i=1}^n b_i (x-x_0) \dots (x-x_{i-1})
\end{equation}

Ponownie od analogu klasycznej metody obliczania wartości wielomianu
w~postaci Newtona (o koszcie $2 n$ mnożeń i~$2 n$ dodawań) szybszy
jest \textbf{uogólniony algorytm Hornera}.  Korzystamy ze wzoru
\begin{equation}
  \label{eq:uog-Horner}
  W(x) = (\ldots(b_n (x-x_{n-1}) + b_{n-1}) (x-x_{n-2} + 
         \dots + a_1) (x-x_0) + a_0.
\end{equation}
Algorytm dany jest wzorem
\begin{subequations}
\label{eq:uog-Horner:alg}
  \begin{align}
    w_n &= b_n,\\
    w_i &= w_{n+1} (x-x_i) + b_i,\quad\text{dla\ }i = n-1,n-2,\dots,0.
  \end{align}
\end{subequations}
Wymaga on $n$ mnożeń i~$2 n$ dodawań.



\subsection{Przejście od postaci Newtona do postaci naturalnej}
\label{sec:Newtona-do-potegowej}

Znając współczynniki wielomianu w~postaci Newtona można wyznaczyć
współczynniki jego postaci naturalnej.  W~tym celu każdy z~wielomianów
pomocniczych $w_i$ zdefiniowanych wzorami~\eqref{eq:uog-Horner:alg}
zapiszmy w~postaci naturalnej:
\begin{equation}
  \label{eq:uog-Horner-potegowa}
  w_i(x) = \sum_{k=i}^n a_k^{(i)} x^{k - i}, 
  \quad\text{dla\ }i = n, n-1, \dots, 0.
\end{equation}
Ze wzoru~\eqref{eq:uog-Horner:alg} otrzymujemy zależności rekurencyjne
na $a_i^{(j)}$:
\begin{subequations}
  \label{eq:Newton-do-potegowej}
  \begin{align}
    a_n^{(i)} &= a_n^{(i+1)} = \dots = a_n^{(n)} = b_n,\\
    a_i^{(i)} &= b_i - a_{i+1}^{(i+1)} x_i,\\
    a_k^{(i)} &= a_k^{(i+1)} - a_{k+1}^{(i+1)} x_i, 
    \quad \text{dla\ }k = i+1, i+2, \ldots, n-1.
  \end{align}
\end{subequations}
%%
\input{podpis.tex}

\end{document}
