\subsection{Свойства QR-алгоритма} \begin{myUnnumberedStatement} Пусть матрица \( B \) -- ВТФ, а матрица \( A \) -- ВПТФ. Тогда \( Q = BA \) -- ВПТФ. \end{myUnnumberedStatement} \begin{proof} По формуле умножения матриц: \[ c_{ij} = \sum_{\alpha=1}^{n}b_{i \alpha}c_{\alpha j}. \] Так как \( B \) -- ВТФ, то все \( b_{i \alpha} \) при \( i > \alpha \) равны нулю, так как \( A \) -- ВПТФ, то все \( a_{\alpha j} \) при \( \alpha > j + 1 \) равны нулю. Модифицируем формулу согласно этим утверждениям: \[ c_{ij} = \sum_{\alpha=i}^{j + 1}b_{i \alpha}c_{\alpha j}. \] То есть если i > j + 1, то \( c_{ij} = 0 \). А это и значит, что \( C \) -- верхняя почти треугольная матрица. \end{proof} \begin{myUnnumberedStatement} Пусть матрица \( B \) -- ВПТФ, а матрица \( A \) -- ВТФ. Тогда \( Q = BA \) -- ВПТФ. \end{myUnnumberedStatement} \begin{proof} Доказательство полностью аналогично предыдущему утверждению. \end{proof} Используя данные утверждения, можно значительно ускорить QR-разложение матрицы. QR-алгоритм преобразует матрицу \( A \xrightarrow{} A_0 \) -- ВПТФ: \[ A_0 = Q_0R_0 \] \[ Q_0 = A_0R_)^{-1} \text{ -- ВПТФ по доказанному утверждению} \] \[ A_1 = R_0Q_0 \text{ -- ВПТФ по доказанному утверждению} \] То есть форма матрицы \( A_n (n \in \textbf{N} ) \) не ухудшается, следовательно, очередная матрица может быть выполнена не более чем за \( n^2 \) действий. Если же матрица \( A_0 \) - симметричная, то один шаг потребует всего \( n \) действий. \chapter{Интерполирование и приближение функций} \section{Постановка задачи интерполирования} Пусть \( f(x) \) -- дискретная функция аргумента \( x, x \in [a, b], a,b \in \mathbf{R} \). Функция \( f(x) \) определена в точках \(x_0, x_1, \ldots, x_n, n \in \mathbf{N}; a \leq x_0 < x_1 < \ldots < x_n \leq b = \{X_i\}_0^n \) -- узлах функции. Во всех узлах заданы значения \( f(x_i) = y_i, \forall i = \overline{0,n}\). Требуется найти значение функции \( f(x) \) в произвольной точке. \begin{myUnnumberedNote} В указанной формулировке решений задачи бесконечно много. Для уточнения дополнительно указывают класс функций, которые будут использоваться для построения значений \( f(x) \) в произвольной точке. \end{myUnnumberedNote} \subsection{Интерполирование алгебраическими полиномами} \begin{myUnnumberedDefinition} Назовем интерполяционным полиномом Лагранжа функции \( f(x) \) по узлам \( \{X_i\}_0^n \) полином степени \(n \): \begin{equation} \label{eq_2_1_1} P_n(x) = a_0 + a_1x + \ldots + a_nx^n, \end{equation} при этом значения коэффициентов \( a_0 \ldots a_n \) выбираются таким образом, чтобы при любых значениях \(i = \overline{1, n}\) было выполнено: \begin{equation} \label{eq_2_1_2} P_n(x_i) = f(x_i) \end{equation} \end{myUnnumberedDefinition} \begin{myUnnumberedStatement} Покажем, что интерполяционный полином \(P_n(x)\) для функции \( f(x) \) по узлам \( \{X_i\}_0^n \) существует и единственен. \end{myUnnumberedStatement} \begin{proof} Распишем \(n+1\) уравнение из условия \eqref{eq_2_1_2}. Получим систему линейных уравнений: \[ a_0 + a_1x_0 + \ldots + a_nx_0^n = f_0, a_0 + a_1x_1 + \ldots + a_nx_1^n = f_1, \ldots a_0 + a_1x_n + \ldots + a_nx_n^n = f_n, \] Теперь посмотрим на определитель этой системы: \[ \Delta = \begin{bmatrix} 1 & x_0 & x_0^2 & \ldots & x_0^n \\ 1 & x_1 & x_1^2 & \ldots & x_1^n \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 1 & x_n & x_n^2 & \ldots & x_n^n \end{bmatrix} \] Из курса линейной алгебры известно, что данный определитель (определитель Вандермонда) равен произведению разности всех пар \( (x_i,x_j), i \neq j \). По условию никакие два различных узла не могут дать нам нулевую разность, следовательно, определитель системы не равен нулю. А это и означает, что решение (т.е. \( P_n(x) \) ) существует и единственно. \end{proof} \begin{myUnnumberedNote} Поскольку мы доказали существование и единственность интерполирующего полинома, то при его поиске, в какой бы форме мы его не получили, он будет тожественно равен всем своим представлениям в иных формах, полученных с помощью других методов. \end{myUnnumberedNote} \section{Интерполяционная формула Лагранжа} Будем искать интерполяционный полином в виде \begin{equation} \label{eq_2_2_1} L_n(x) = \sum_{k=0}^nc_k(x)f(x_k) \text{ , где: } \end{equation} \( c_k(x) \) -- полином \(n\)-й степени, \( f(x_k) \) -- известные значения функции в узлах. \begin{myUnnumberedNote} По определению \(L_n(x_i) = f(x_i), \forall i = \overline{1, n}\). \end{myUnnumberedNote} Будем строить полином следующим образом: \\ Пусть \(\omega(x) = (x-x_0)(x-x_1) \cdot \ldots \cdot (x-x_n) = \Pi_{i=0}^n(x-x_i) \). \\ Тогда: \[ \omega'(k) = ([\ldots](x-x_k)) = [\ldots] + [\ldots]'(x-x_k) = \Pi_{\substack{ i=0 \\ i \neq k }}^n(x-x_i) \]. ( \( \omega(k) \) -- значение функции в точке \( x_k \) ). \\ Полиномы \( c_k(x) \) вользмем равными \( \frac{\omega(x)}{ (x - x_k) \omega'(x)} \). Определим погрешность метода как разность между значением полинома Лагранжа и значением функции: \begin{equation} \label{eq_2_2_2} \psi_n(x) = f(x) - L_n(x) \end{equation} \begin{myUnnumberedNote} Для оценки погрешности метода мы требуем \( f(x) \in C^{n+1}[a, b]\). \end{myUnnumberedNote} \begin{myUnnumberedStatement} \[ \forall x^* \in [a, b]: r_n(x^*) = \frac{ f^{(n+1)} (\xi) }{ (n+1)! } \cdot \omega_{n+1} (x^*), \xi \in (a, b) \] \end{myUnnumberedStatement} \begin{proof} Пусть \( g(s) = f(s) - L_n(s) - k \omega(s) \), где \( k \) - константа. \\ Очевидно, что \(g(s)\) имеет \(n+2\) нуля: \(n+1\) за счет обращения в ноль в узлах и последний ноль за счет совпадения \( f(s) - L_n(s) = k \omega \). В этом случае \( k \) и есть искомая оценка. По теореме Ролля \( g^{(n+1)}(\xi) = 0 \). Найдем эту производную: \[ g^{(n+1)}(s) = (f(s) - L_n(s) - k \omega(s))^{(n+1)} = \] \[ f^{(n+1)}(\xi) - 0 - k \cdot n! \] Откуда и получаем: \[ f(x) - L_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega(x) \] \end{proof} \begin{myUnnumberedNote} Полином Лагранжа, вообще говоря, не сходится к \( f(x) \). \end{myUnnumberedNote}