Инструменты сайта


Страница — в разработке. Начало работ — 06.05.2016, окончание — ??.??.????

Ганкелевы матрицы, определители и полиномы

Определения

Ганкелева матрица порядка $ k_{} $ — это квадратная матрица вида $$ \left(\begin{array}{llllll} \color{Brown}c_0 & \color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & \dots & c_{k-1} \\ \color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & c_4 & \dots & c_k \\ \color{Green}c_2 & \color{Violet}c_3 & c_4 & &\dots & c_{k+1} \\ \color{Violet}c_3 & c_4 & & & & \\ \vdots & & & \ddots & \vdots \\ c_{k-1} & c_{k} & c_{k+1} & &\dots & c_{2k-2} \end{array} \right)_{k\times k}= \left[ c_{j+k}\right]_{j,k=0}^{k-1} \ . $$ Это симметричная матрица, на каждой диагонали которой, перпендикулярной главной, стоят одинаковые элементы. Таким образом, ганкелева1) матрица полностью определяется заданием своих крайних элементов — $$ c_0,c_1,\dots, c_{2k-2} $$ — они называются образующими ганкелевой матрицы.

П

Пример. Матрица

$$\left( \begin{array}{lllll} 1 & 1/2 & 1/3 & \dots & 1/n \\ 1/2 & 1/3 & 1/4 & \dots & 1/(n+1) \\ 1/3 & 1/4 & 1/5 & \dots & 1/(n+2) \\ \vdots & & & & \vdots \\ 1/n & 1/(n+1) & 1/(n+2) & \dots & 1/(2n-1) \end{array} \right) =\left[ \frac{1}{j+k+1} \right]_{j,k=0}^{n-1} $$ относится к типу ганкелевых. Она называется матрицей Гильберта.

Наряду с конечными ганкелевыми матрицами, рассматривают также и бесконечные, задаваемые бесконечной последовательностью образующих элементов.

Определитель ганкелевой матрицы порядка $ k_{} $ будем обозначать $ H_{k}(\{c\}) $ или просто $ H_{k} $.

Если в ганкелевой матрице порядка $ k+1 $ заменить последнюю строку на $ \left[ 1,x,x^2,\dots,x^{k} \right] $, то определитель полученной матрицы $$ \mathcal H_k(x; \{c\}) = \left| \begin{array}{lllll} c_0 & c_1 & c_2 & \ldots & c_{k} \\ c_1 & c_2 & c_3 &\ldots & c_{k+1} \\ \vdots & & & \ddots& \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-1} \\ 1 & x & x^2 & \ldots & x^{k} \end{array} \right|_{(k+1) \times (k+1)} $$ будет полиномом по $ x_{} $; он называется ганкелевым полиномом k-го порядка (порожденным последовательностью $ \{c\} $). Его каноническое представление имеет коэффициентами числовые определители $ k_{} $-го порядка: $$ \mathcal H_k(x; \{c\})\equiv x^{k} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-2} \end{array} \right|- x^{k-1} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-1} \end{array} \right|+ $$ $$ + \dots +(-1)^k \left| \begin{array}{lllll} c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ c_2 & c_3 & \ldots & c_{k} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k} & c_{k+1} & \ldots & c_{2k-2} & c_{2k-1} \end{array} \right| \ . $$ Коэффициенты будем обозначать $ h_{kj} $; таким образом $$ \mathcal H_k(x; \{c\})\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad npu \quad h_{k0}= H_k \ ; $$ Коэффициент $ h_{k0} $ может обращаться в нуль, так что степень ганкелевого полинома $ k_{} $-го порядка может оказаться меньшей $ k_{} $.

Т

Теорема. Ганкелев полином $ k $-го порядка можно представить в виде ганкелевого определителя $ k $-го порядка:

$$ \mathcal H_k(x; \{c\}) = (-1)^k \left| \begin{array}{lllll} c_1 -c_0x & c_2-c_1x & \ldots & c_{k}-c_{k-1}x \\ c_2-c_1x & c_3-c_2x &\ldots & c_{k+1}-c_kx \\ \vdots & & \ddots& \vdots \\ c_{k}-c_{k-1}x & c_{k+1}-c_kx & \ldots & c_{2k-1}-c_{2k-2}x \end{array} \right|_{k \times k}=(-1)^k H_k (\{c_{j+1}-c_jx\}_{j=0}^{2\, k-1}) \ . $$

Доказательство. Для простоты рассмотрим случай $ k=4 $: $$ \left| \begin{array}{lllll} c_0 & c_1 & c_2 & c_3 & c_{4} \\ c_1 & c_2 & c_3 & c_4 & c_{5} \\ c_2 & c_3 & c_4 & c_5 & c_{6} \\ c_{3} & c_{4} & c_{5} & c_6 & c_{7} \\ 1 & x & x^2 & x^3 & x^{4} \end{array} \right|= $$ С помощью элементарных преобразований столбцов исключим $ x_{} $ из последней строки. С этой целью вычтем из $ 5_{} $-го столбца $ 4 $-й, домноженный на $ x_{} $, потом из $ 4_{} $-го столбца $ 3_{} $-й, домноженный на $ x_{} $, и т.д. В результате получим $$ = \left| \begin{array}{ccccc} c_0 & c_1 -c_0x & c_2-c_1x & c_3-c_2x & c_{4}-c_{3}x \\ c_1 & c_2-c_1x & c_3-c_2x & c_4-c_3x & c_{5}-c_4x \\ c_2 & c_3-c_2x & c_4-c_3x & c_5-c_4x & c_{6}-c_5x \\ c_3 & c_4-c_3x & c_5-c_4x & c_6-c_5x & c_{7}-c_6x \\ 1 & 0 & 0 & 0 & 0 \end{array} \right|= + \left| \begin{array}{llll} c_1 -c_0x & c_2-c_1x & c_3-c_2x & c_{4}-c_{3}x \\ c_2-c_1x & c_3-c_2x & c_4-c_3x & c_{5}-c_4x \\ c_3-c_2x & c_4-c_3x & c_5-c_4x & c_{6}-c_5x \\ c_4-c_3x & c_5-c_4x & c_6-c_5x & c_{7}-c_6x \end{array} \right|\ . $$

Тождество Якоби

Т

Теорема. Справедливо следующее равенство (тождество) Якоби:

$$ H_k \left| \begin{array}{llll} c_2 & c_3 & \ldots & c_{k-1} \\ c_3 & c_4 & \ldots & c_{k} \\ \vdots & & \ddots & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-4} \end{array} \right|_{(k-2)\times (k-2)} = $$ $$ =H_{k-1} \left|\begin{array}{llll} c_2 & c_3 & \dots & c_{k} \\ c_3 & c_4 & \dots & c_{k+1} \\ \vdots & & \ddots & \vdots \\ c_{k} & c_{k+1} & \dots & c_{2k-2} \end{array} \right|_{(k-1)\times (k-1)} - \left|\begin{array}{llll} c_1 & c_2 & \dots & c_{k-1} \\ c_2 & c_3 & \dots & c_{k} \\ \vdots & & \ddots & \vdots \\ c_{k-1} & c_{k} & \dots & c_{2k-3} \end{array} \right|_{(k-1)\times (k-1)}^2 \ . $$

Это равенство связывает ганкелев определитель $ k_{} $-го порядка с тремя ганкелевыми определителями порядка $ k-1 $ и одним ганкелевым определителем порядка $ k-2 $. Оно является частным случаем тождества Сильвестра.

Обращение ганкелевой матрицы

Рекурсивная формула для ганкелевых полиномов

Рассмотрим последовательность ганкелевых полиномов $ \mathcal H_1(x), \mathcal H_2(x) ,\dots, $, порожденных последовательностью $ \{ \mathbf c \} $. Коэффициенты канонического разложения полинома $ \mathcal H_k(x) $ будем обозначать $ \{h_{kj}\} $: $$ \mathcal H_k(x)\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad npu \quad h_{k0}= H_k \ . $$

П

Пример. Вычислить ганкелевы полиномы $ \{\mathcal H_k(x)\}_{k=1}^5 $, порожденные последовательностью

$$ \{1,1,2,-1,-9,-142,-2051,-29709,-430018,-6224467,\dots \} \, . $$

Решение. Имеем: $$ \mathcal H_1(x)=x-1,\ \mathcal H_2(x)=x^2+3\,x-5,\ \mathcal H_3(x)=-22\,x^3+164\,x^2+316\,x-666,\ $$ $$ \mathcal H_4(x)=19656\,x^4-278356\,x^3-97864\,x^2+93808\,x+468, $$ $$ \mathcal H_5(x)=4638712(x^5-14\,x^4-7\,x^3+2\,x^2-3\,x+8) \ . $$ Легко проверить, что вычисленные полиномы удовлетворяют тождествам: $$ -22\, \mathcal H_1(x)+\left(\frac{115}{11}-x\right)\mathcal H_2(x) -\frac{1}{22} \mathcal H_3(x) \equiv 0, $$ $$ -\frac{9828}{11}\, \mathcal H_2(x) +\left( \frac{27887}{4158}-x \right) \mathcal H_3(x)-\frac{11}{9828} \mathcal H_4(x) \equiv 0, $$ $$ \frac{44603}{189} \mathcal H_3(x)+ \left( -\frac{61}{378}-x \right) \mathcal H_4(x)+\frac{189}{44603} \mathcal H_5(x) \equiv 0 \ . $$

Т

Теорема [Якоби, Йоахимшталь].2) Любые три ганкелевых полинома $ \mathcal H_{k-2}(x), \mathcal H_{k-1}(x), \mathcal H_{k}(x) $ связаны тождеством

$$ H_k^2\mathcal H_{k-2}(x) + \left(H_kh_{k-1,1}-H_{k-1}h_{k1}-H_kH_{k-1}x\right)\mathcal H_{k-1}(x) + H_{k-1}^2 \mathcal H_{k}(x) \equiv 0 \, . $$

§

В литературе после 1910 г. упоминаний этого тождества (и ссылок на него) не нашел. В дальнейшем буду называть его JJ-тождеством.

=>

Если $ H_{k} \ne 0, H_{k-1} \ne 0 $ то JJ-тождество может быть переписано в «более симметричном» виде:

$$ \frac{H_k}{H_{k-1}}\mathcal H_{k-2}(x)- \left(x-\frac{h_{k-1,1}}{H_{k-1}}+\frac{h_{k1}}{H_{k}} \right)\mathcal H_{k-1}(x)+\frac{H_{k-1}}{H_{k}}\mathcal H_{k}(x) \equiv 0 \, . $$

JJ-тождество позволяет организовать рекурсивную процедуру вычисления ганкелевых полиномов. Предположим, что канонические представления полиномов $ \mathcal H_{k-2}(x) $ и $ \mathcal H_{k-1}(x) $ уже известны: $$ \mathcal H_{k-1}(x) \equiv h_{k-1,0} x^{k-1}+h_{k-1,1}x^{k-2}+\dots+ h_{k-1,k-1} \quad npu \ h_{k-1,0}=H_{k-1} \, . $$ Тогда в JJ-тождестве известны значения всех констант, за исключением $ H_k $ и $ h_{k1} $. Для последних имеются лишь детерминантные представления: $$ H_k = \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-3} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-2} \end{array} \right| \ , \ h_{k1} = - \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k+1} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-2} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-1} \end{array} \right| \, . $$ Эти определители отличаются от детерминантного представления $ \mathcal H_{k-1}(x) $ (транспонированного) $$ \left[\mathcal H_{k-1}(x) \right]^{\top} = \left| \begin{array}{llllll} c_0 & c_1 & c_2 & \ldots & c_{k-2} & 1 \\ c_1 & c_2 & c_3 &\ldots & c_{k-1} & x \\ \vdots & & & \ddots & \vdots & \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-3} & x^{k-1} \end{array} \right| $$ только своими последними столбцами. Разложения определителей по элементам этих последних столбцов имеют одинаковые значения для соответствующих алгебраических дополнений, и поэтому следующие формулы $$ \left\{\begin{array}{rcl} h_{k0}=H_k&=&c_{k-1}h_{k-1,k-1}+c_{k}h_{k-1,k-2}+\dots+c_{2k-2}h_{k-1,0}, \\ h_{k1}&=&-(c_{k}h_{k-1,k-1}+c_{k+1}h_{k-1,k-2}+\dots+c_{2k-1}h_{k-1,0}) \end{array} \right. $$ позволяют вычислить $ h_{k0} $ и $ h_{k1} $ посредством уже известных коэффициентов полинома $ \mathcal H_{k-1}(x) $.

Частный случай тождества известен для ортогональных полиномов.

Предложенный алгоритм сведения вычисления $ \mathcal H_{k}(x) $ к вычислению двух ганкелевых полиномов меньших порядков не будет работать в случае $ H_{k-1}=0 $. Существует модификация алгоритма и для этого случая.

Т

Теорема [?]. Пусть $ H_{k-2} \ne 0, H_{k-1}=0 $. Если $ h_{k-1,1}=0 $, то

$$ \mathcal H_{k-1}(x) \equiv 0 $$ и $$ \mathcal H_k(x) \equiv \frac{h_{k2}}{H_{k-2}} \mathcal H_{k-2}(x) \, . $$ В противном случае $$ \mathcal H_{k-1}(x) \equiv \frac{h_{k-1,1}}{H_{k-2}}\mathcal H_{k-2}(x) $$ и $$ \mathcal H_k(x) \equiv \frac{1}{H_{k-2}^3} \left(H_kH_{k-2}h_{k-1,1}\mathcal H_{k-3}(x)- \left|\begin{array}{cccc} H_{k-2} & 0 & 0 & H_k \\ h_{k-2,1} & H_{k-2} & 0 & h_{k1} \\ h_{k-2,2} & h_{k-2,1} & H_{k-2} & h_{k2} \\ x^2 & x & 1 & 0 \end{array} \right| \mathcal H_{k-2}(x) \right) \, . $$

Применения

Линейные рекуррентные последовательности

Т

Теорема. Бесконечная ганкелева матрица $ H=\left[h_{j+k}\right]_{j,k=0}^{\infty} $ имеет конечный ранг $ \mathfrak r $ тогда и только тогда, когда последовательность $ \{h_{j}\}_{j=0}^{\infty} $ является линейной рекуррентной порядка $ \mathfrak r $, т.е. существует $ \mathfrak r $ чисел $ a_1,a_2,\dots,a_{\mathfrak r} $ таких, что $$ h_{\ell}=a_1 h_{\ell-1}+a_2 h_{\ell-2}+\dots+a_{\mathfrak r} h_{\ell-\mathfrak r} \quad npu \quad \ell\in\{\mathfrak r,\mathfrak r+1,\dots\} \, $$ и $ \mathfrak r $ есть наименьшее число, обладающее этим свойством.

Т

Теорема. Бесконечная ганкелева матрица $ H=\left[h_{j+k}\right]_{j,k=0}^{\infty} $ имеет конечный ранг тогда и только тогда, когда сумма ряда Лорана $$ R(x)=\frac{h_0}{x}+\frac{h_1}{x^2}+\frac{h_2}{x^3}+\dots $$ является рациональной функцией от переменной $ x $. В этом случае $ \operatorname{rank} (H) $ совпадает с числом полюсов функции $ R(x) $, с учетом кратности каждого полюса.

Аппроксимация: метод наименьших квадратов

§

Раздел МЕТОД НАИМЕНЬШИХ КВАДРАТОВ

Пусть в заданной таблице экспериментальных значений $$ \begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_m \\ \hline y & y_1 & y_2 &\dots & y_m \end{array} \quad \{ x_j,y_j\}_{j=1}^m \subset \mathbb R $$ величины $ x_{} $ нам известны без искажений, а вот измерения величины $ y_{} $ подвержены случайным погрешностям.

Задача. Построить полином $ f_{}(x) $ такой, чтобы величина $$ \sum_{j=1}^m (f(x_j)-y_j)^2 $$ стала минимальной.

В случае $ \deg f_{} =m-1 $ получаем классическую задачу полиномиальной интерполяции. Практический интерес, однако, представляет случай $ \deg f_{} < m-1 $: экспериментальных данных больше (обычно — много больше) чем значений параметров (коэффициентов полинома $ f_{} $), которые требуется определить.

Т

Теорема. Если $ m\ge n_{} $ и $ x_{1},\dots,x_m $ все различны, то существует единственный набор коэффициентов $ a_{0},\dots,a_{n-1} $, обеспечивающий минимальное значение для

$$ \sum_{j=1}^m (a_0+a_1x_j+\dots+a_{n-1}x_j^{n-1} -y_j)^2 \ . $$ Этот набор определяется как решение системы нормальных уравнений

$$ \underbrace{ \left(\begin{array}{llllll} s_0 &s_1&s_2&\ldots&s_{n-2}& s_{n-1}\\ s_1 &s_2&s_3&\ldots&s_{n-1}& s_{n}\\ s_2 &s_3&s_4&\ldots&s_{n}& s_{n+1}\\ \vdots& & & && \vdots\\ s_{n-1} &s_n&s_{n+1}&\ldots &s_{2n-3}&s_{2n-2} \end{array}\right)}_{\displaystyle S_{n\times n}} \left(\begin{array}{l} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{array} \right)= \left(\begin{array}{l} t_0 \\ t_1 \\ t_2 \\ \vdots \\ t_{n-1} \end{array} \right) $$ при $ s_{k} = x_1^k+\dots+x_m^k, \ t_{k} = x_1^ky_1+\dots+x_m^k y_m $.

Аппроксимация

Задача. Для функции $ f(x_{}) $, непрерывной на $ [0_{},1] $, построить полином $ f_{n-1}(x_{})=a_0+a_1x+\dots+a_{n-1}x^{n-1} $ такой, чтобы величина $$ \int_0^1 \left[f(x)-f_{n-1}(x) \right]^2 d\, x $$ была наименьшей.

Т

Теорема. Коэффициенты полинома $ f_{n-1}(x_{}) $ находятся из системы уравнений

$$ \left( \begin{array}{lllll} 1 & \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n} \\ &&&& \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \dots & \frac{1}{n+1} \\ &&&& \\ \frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \dots & \frac{1}{n+2} \\ &&&& \\ \dots & & & & \dots \\ &&&& \\ \frac{1}{n} & \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n-1} \end{array} \right) \left( \begin{array}{l} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{array} \right)= \left( \begin{array}{l} b_0 \\ b_1 \\ b_2 \\ \vdots \\ b_{n-1} \end{array} \right) \ . $$ Здесь $$ b_{j}=\int_0^1 f(x) x^{j} d\, x \quad npu \quad j\in \{0,\dots,n-1 \} . $$

Матрица $ {\mathfrak H}_{n} $ системы называется матрицей Гильберта. Ее определитель равен $$ \frac{[1!\,2!\, 3! \dots (n-1)!]^3} {n!\, (n+1)!\, (n+2)!\, \dots (2n-1)!} \ , $$ т.е. отличен от нуля, и, следовательно, система имеет единственное решение.

!

Хотя определитель Гильберта и отличен от нуля, но очень близок к нему:

$$ \det {\mathfrak H}_3=\frac{1}{2160},\ \det {\mathfrak H}_4=\frac{1}{6\,048\,000},\ \det {\mathfrak H}_6=\frac{1}{186313420339200000} $$ поэтому при решении линейной системы надо внимательно следить за ошибками округлений [?],[?].

Результант и наибольший общий делитель полиномов

§

Раздел Результант.

Для полиномов $$ f(x)=a_0x^n+a_1x^{n-1}+\ldots+a_n\quad u \quad g(x)=b_0x^m+b_1x^{m-1}+\ldots+b_m $$ ($ a_{0}\ne 0 $) построим сначала формальное разложение дроби $ g_{}(x)/f(x) $ в ряд Лорана по отрицательным степеням $ x_{} $. Для случая $ \deg g < \deg f $ выписываем разложение $$ \frac{g(x)}{f(x)}=\frac{c_0}{x}+\frac{c_1}{x^2}+\dots+\frac{c_j}{x^{j+1}}+\dots \ , $$ домножаем обе части на $ f_{}(x) $ и приравниваем коэффициенты при одинаковых степенях $ x_{} $ в левой и правой частях получившегося равенства. В случае $ m=n-1 $ формулы, выражающие коэффициенты $ c_{j} $ через коэффициенты полиномов $ f_{}(x) $ и $ g_{}(x) $ следующие: $$ \begin{array}{ll} c_0&=b_{0}/a_0,\\ c_1& =(-c_{0}a_1+b_1)/a_0,\\ c_2& =(-c_{0}a_2-c_1a_1+b_2)/a_0, \\ \dots & \dots \\ c_{n-1}&=(-c_0a_{n-1}-c_1a_{n-2}-\dots-c_{n-2}a_1+b_{n-1})/a_0,\\ c_{K+n}&=(-c_{K}a_{n}-c_{K+1}a_{n-1}-\dots-c_{K+n-1}a_1)/a_0 \quad npu \quad \forall K \in \{0,1,2,\dots \} \ . \end{array} $$ В случае $ m<n-1 $ эти же формулы можно применять при дополнительном условии, что полином $ g_{}(x) $ считается записанным в виде $$ g(x) = b_0x^{n-1}+ b_1x^{n-2}+ \dots + b_{n-1} \ , $$ где коэффициенты $ b_0,\dots, b_{n-m} $ считаются равными нулю. Для случая $ \deg f \le \deg g $ сначала вычисляется частное $ q_{}(x) $ и остаток $ g_{1}(x) $ от деления $ g_{}(x) $ на $ f_{}(x) $, а далее правильная дробь $ g_1(x)/f(x) $ раскладывается по отрицательным степеням $ x_{} $ с использованием приведенных выше правил: $$ \frac{g(x)}{f(x)}=q(x)+\frac{g_1(x)}{f(x)}=q(x)+\frac{c_0}{x}+\frac{c_1}{x^2}+\dots+\frac{c_j}{x^{j+1}}+\dots $$ Вычислив величины $ c_{0},\dots,c_{2n-2} $, cоставим из них ганкелеву матрицу $$ C= [c_{j+k}]_{j,k=0}^{n-1}= \left(\begin{array}{lllll} c_0&c_1&c_2&\ldots&c_{n-1}\\ c_1&c_2&c_3&\ldots&c_{n}\\ c_2&c_3&c_4&\ldots&c_{n+1}\\ \dots&&&&\dots\\ c_{n-1}&c_{n}&c_{n+1}&\ldots&c_{2n-2} \end{array}\right)\ . $$ Обозначим $ C_{1},\dots,C_n $ ее главные миноры.

Т

Теорема [Кронекер][?].Имеет место формула $$ {\mathcal R}(f,g)=a_0^{n+m} \det C \ . $$ связывающая определитель матрицы $ C_{} $ с результантом полиномов $ f_{}(x) $ и $ g_{}(x) $. Для того чтобы эти полиномы имели наибольший общий делитель степени $ k>0 $, необходимо и достаточно, чтобы были выполнены условия $$\underbrace{C_n=0,\ C_{n-1}= 0,\ \dots , C_{n-k+1}=0}_k, C_{n-k}\ne 0.$$

Дискриминант и локализация корней полинома

§

Раздел Дискриминант; раздел Локализация корней полинома.

Дискриминант полинома $ f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n, (n>1, a_0\ne 0) $ фактически совпадает с результантом этого полинома и его производной: $$ {\mathcal D}(f)=\frac{(-1)^{n(n-1)/2}}{a_0}{\mathcal R}(f(x),f^{\prime}(x)) \ . $$

Т

Теорема. $ {\mathcal D}(f_{}) = 0 $ тогда и только тогда, когда $ f_{}(x) $ имеет кратный корень.

Существует несколько способов представления дискриминанта в виде определителя матрицы, зависящей от коэффициентов полинома $ f_{}(x) $. Один из них основан на ганкелевой матрице.

Для полинома $ f_{}(x) $ его $ k_{} $-й суммой Ньютона называется сумма $ k_{} $-х степеней его корней $$ s_k=\sum_{j=1}^n\lambda_j^k \ . $$ Суммы Ньютона могут быть формально получены из разложения в ряд Лорана дроби $$ \frac{f^{\prime}(x)}{f(x)}=\frac{s_0}{x}+\frac{s_1}{x^2}+\dots+\frac{s_j}{x^{j+1}}+\dots \ , $$ и выражаются рационально через коэффициенты полинома $ f_{}(x) $ посредством следующих рекуррентных формул Ньютона: $$s_0=n,\ s_1=-a_1/a_0,\ $$ $$ s_k=\left\{\begin{array}{lr} -(a_1s_{k-1}+a_2s_{k-2}+\dots+a_{k-1}s_1+a_kk)/a_0, &npu \ k\le n ;\\ -(a_1s_{k-1}+a_2s_{k-2}+\dots+a_ns_{k-n})/a_0, &npu \ k > n \end{array} \right. $$ Явное выражение сумм Ньютона через $ a_{0}, \dots, a_n $ дается формулой Варинга.

Вычислим суммы Ньютона $ s_{0},s_1,\dots,s_{2n-2} $ полинома $ f_{}(x) $ и составим из них ганкелеву матрицу $$ S=\left[s_{j+k} \right]_{j,k=0}^{n-1} = \left[\begin{array}{llllll} s_0 &s_1&s_2&\dots&s_{n-2}& s_{n-1}\\ s_1 &s_2&s_3&\dots&s_{n-1}& s_{n}\\ s_2 &s_3&s_4&\dots&s_{n}& s_{n+1}\\ \dots& & &&& \dots\\ s_{n-1} &s_n&s_{n+1}&\dots &s_{2n-3}&s_{2n-2} \end{array}\right]_{n\times n} \ . $$ Обозначим $ S_{1},\dots, S_n $ ее главные миноры.

Т

Теорема. Имеет место формула $$ {\mathcal D}_{k}=n^{n-k-2}a_0^{2(n-k-1)}S_{n-k} \ , $$ связывающая миноры матрицы $ S_{} $ с субдискриминантами. В частности, $$ {\mathcal D}(f)=a_0^{2n-2}\det S \ . $$

Доказательство следует из теоремы Кронекера.

Матрицу $ S $ из предыдущей теоремы можно использовать и для локализации вещественных корней полинома $ f_{}(x) $, имеющего вещественные коэффициенты.

Т

Теорема [Якоби]. Число различных корней полинома $ f_{}(x)\in \mathbb R[x] $ равно рангу, а число различных вещественных корней $ f_{}(x) $ сигнатуре матрицы $ S_{} $.

Конструктивное вычисление ранга и сигнатуры симметричной матрицы $ S_{} $ (возможно посредством определения знаков ее главных миноров $ S_{1},\dots,S_n $.

=>

Пусть $$ S_n=0,\dots,S_{{\mathfrak r}+1}=0,S_{\mathfrak r}\ne 0, \dots, S_1 \ne 0 \ .$$ Тогда $ \operatorname{rank} (S)={\mathfrak r} $ и число различных вещественных корней $ f(x) $ равно $${\mathcal P}(1,S_1,\dots,S_{\mathfrak r}) -{\mathcal V}(1,S_1,\dots,S_{\mathfrak r}) \ , $$ где $ {\mathcal P}_{} $ — число знакопостоянств и $ {\mathcal V}_{} $ — число знакоперемен.

Идею, использованную при доказательстве теоремы Якоби можно развить и для задачи отделения (локализации) корней полинома $ f_{}(x) $. Для этого вычислим дополнительно еще одну сумму Ньютона $ s_{2n-1} $ и составим следующую ганкелеву матрицу, зависящую от параметра $ t_{} $: $$ H(t)=\left[ s_{j+k}t-s_{j+k+1} \right]_{j,k=0}^{n-1} =\left[ \begin{array}{llll} s_0t-s_1&s_1t-s_2&\dots& s_{n-1}t-s_{n} \\ s_1t-s_2&s_2t-s_3&\dots& s_{n}t-s_{n+1} \\ \dots & & & \dots \\ s_{n-1}t-s_{n} & s_{n}t-s_{n+1} & \dots & s_{2n-2}t-s_{2n-1} \end{array} \right]_{n\times n} \ . $$ Очевидно, что матрица, составленная из коэффициентов при $ t_{} $ совпадает с матрицей $ S_{} $ из теоремы Якоби. Главный минор матрицы $ H(t) $ порядка $ \ell_{} $ является ганкелевым полиномом того же порядка $$ \mathcal H_{\ell}(t)=\det \left[s_{j+k}t-s_{j+k+1} \right]_{j,k=0}^{{\ell}-1} \equiv \left| \begin{array}{lllll} s_0&s_1&\dots&s_{{\ell}-1}& s_{\ell} \\ s_1&s_2&\dots&s_{\ell}& s_{\ell+1} \\ \vdots & && \vdots & \vdots \\ s_{\ell-1}&s_{\ell}&\dots&s_{2\ell-2}&s_{2\ell-1} \\ 1 & t & \dots & t^{\ell-1} & t^{\ell} \end{array} \right|_{(\ell+1)\times (\ell+1)} \ . $$ Заметим, что $$ \mathcal H_{n}(t)=\det H(t) \equiv S_n f(t)/a_0 \ .$$

Т

Теорема [Йоахимшталь].[?] Пусть $ \operatorname{rank} (S)={\mathfrak r} $. Тогда

$$ \operatorname{nrr} \{ f(x)=0 \mid a <x < b \} ={\mathcal V}(1,\mathcal H_1(a),\dots,\mathcal H_{\mathfrak r}(a))- {\mathcal V}(1, \mathcal H_1(b),\dots, \mathcal H_{\mathfrak r}(b)), \ $$ при условии, что в ряду $$ 1, \mathcal H_1(t),\dots, \mathcal H_{\mathfrak r}(t) $$ нет двух последовательных нулей при $ t=a $ и $ t=b $.

§

В случае, когда в ряду встречаются несколько подряд идущих нулей (например, $ f(x)=x^4-1, a=0 $), то можно воспользоваться правилом Кронекера-Хатендорфа:

$$ \operatorname{nrr} \{ f(x)=0 \mid a <x < b \} =\frac{1}{2}\sum_{k=1}^{\mathfrak r} \{\operatorname{sign} (\mathcal H_{k-1}(b) \mathcal H_{k}(b))- \operatorname{sign} (\mathcal H_{k-1}(a)\mathcal H_{k}(a)) \}. $$

Таким образом система ганкелевых полиномов $ \{\mathcal H_{\ell}(t)\}_{{\ell}=1}^{\mathfrak r} $, порожденная последовательностью сумм Ньютона полинома $ f(x) $, играет роль системы полиномов Штурма для этого полинома. В отличие от традиционной системы полиномов Штурма, построенной с помощью алгоритма Евклида, здесь степени полиномов $ \mathcal H_{\ell}(t) $ возрастают при возрастании $ \ell_{} $.

П

Пример. Локализовать вещественные корни полинома $$f(x)=x^4-x^3-9\,x^2+14\,x-4 \ .$$

Решение. Вычисляем суммы Ньютона: $$ \{s_k\}_{k=0}^{7}=\{4,\ 1,\ 19,\ -14,\ 159,\ -229,\ 1474,\ -2869\} $$ и строим последовательность ганкелевых полиномов из теоремы: $$ \mathcal H_1(t)=4\,t-1,\ \mathcal H_2(t)=75(t^2+t-5),\ \mathcal H_3(t)= 1250(3\,t^3-26\,t+17),\ \mathcal H_4(t)=62500\, f(t) \ . $$ Вычисляем числа знакоперемен в нескольких узлах:

$ t $ $ 1 $ $ \mathcal H_1(t) $ $ \mathcal H_2(t) $ $ \mathcal H_3(t) $ $ \mathcal H_4(t) $ $ {\mathcal V}_t $
$ -\infty $ $ + $ $ - $ $ + $ $ - $ $ + $ 4
$ +\infty $ $ + $ $ + $ $ + $ $ + $ $ + $ 0
0 $ + $ $ - $ $ - $ $ + $ $ - $ 3
$ -4 $ $ + $ $ - $ $ + $ $ - $ $ + $ 4
$ -3 $ $ + $ $ - $ $ + $ $ + $ $ - $ 3
$ 1 $ $ + $ $ + $ $ - $ $ - $ $ + $ 2
$ 2 $ $ + $ $ + $ $ + $ $ - $ $ - $ 1
$ 3 $ $ + $ $ + $ $ + $ $ + $ $ + $ 0

Ответ. Полином $ f_{}(x) $ имеет $ 4_{} $ различных вещественных корня, лежащие на интервалах $ ]-4,-3[,\ ]0,1[,\ ]1,2[, \ ]2,3[ $.

Проверка. $ \lambda_1 \approx -3.2360,\ \lambda_2 \approx 0.3819,\ \lambda_3 \approx 1.2360,\ \lambda_4 \approx 2.6180 $.

$

Как теоремы Йоахимшталя связаны с $ $ $ ? ;-)

§

Фактическое построение ганкелевых полиномов из теоремы производится не непосредственным вычислением соответствующих определителей, зависящих от параметра (эта процедура весьма затратна), а посредством применения рекурсивной формулы — JJ-тождества, приведенного ВЫШЕ.

=>

Матрицу из теоремы Йоахимшталя можно представить в виде комбинации двух ганкелевых матриц: $ H(t)=t\cdot S - \tilde S $, где матрица $ S_{} $ — из теоремы Якоби, а

$$ \tilde S = \left[s_{j+k+1} \right]_{j,k=0}^{n-1} = \left[\begin{array}{llllll} s_1 &s_2&s_3&\dots&s_{n-1}& s_{n}\\ s_2 &s_3&s_4&\dots&s_{n}& s_{n+1}\\ s_3 &s_4&s_5&\dots&s_{n+1}& s_{n+2}\\ \dots& & &&& \dots\\ s_{n} &s_{n+1}&s_{n}&\dots &s_{2n-2}&s_{2n-1} \end{array}\right]_{n\times n} \ . $$ Если обозначить главные миноры матрицы $ \tilde S $ через $ \tilde S_1, \tilde S_2,\dots, \tilde S_n $, то число различных положительных корней полинома $ f_{}(x) $ вычисляется по формуле $$ \operatorname{nrr} \{ f(x)=0 \mid x > 0 \} = {\mathcal P}(1,\tilde S_1,\dots, \tilde S_{\mathfrak r}) -{\mathcal V}(1,S_1,\dots,S_{\mathfrak r}) \ , $$ где $ {\mathfrak r}= \operatorname{rank} (S) $, и дополнительно предполагается, что все числа в рядах — ненулевые. В частности, для того, чтобы все корни полинома $ f_{}(x) $ были различными и положительными необходимо и достаточно, чтобы все главные миноры матриц $ S_{} $ и $ \tilde S $ были положительными.

Коды, исправляющие ошибки

Источники

[?]. Гантмахер Ф.Р. Теория матриц. 4-е изд. М.Наука. 1988.

[?]. Иохвидов И.С. Ганкелевы и теплицевы матрицы и формы. М. Наука. 1974.

[?]. Henrici P. Applied and Computational Complex Analysis. V. 1. 1974. NY. Wiley

[?]. Hilbert D. Ein Beitrag zur Theorie des Legendreschen Polynoms. Acta Math. Bd.18, 1894, S.155-160

[?]. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М. Мир. 1969

[?]. Kronecker L. Zur Theorie der Elimination einer Variabeln aus zwei algebraischen Gleichungen. Werke. Bd. 2. 1897. 113-192, Teubner, Leipzig

[?]. Jacobi C.G.J. De eliminatione variabilis e duabus aequationibus algebraicis. J.reine angew. Math. 1836. Vol. 15, P. 101-124

[?]. Joachimsthal F. Bemerkungen über den Sturm'schen Satz. J.reine angew. Math. 1854. Vol. 48, P. 386-416

[?]. Утешев А.Ю., Боровой И.И. Решение задачи рациональной интерполяции с использованием ганкелевых полиномов. Вестник СПбГУ. Серия 10. 2016. Вып. 4, С. 31-43.

1)
Ганкель Герман (Hankel Hermann, 1839-1873) — немецкий математик. Биография ЗДЕСЬ
2)
Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) — немецкий математик, ученик Якоби. Биография ЗДЕСЬ.
algebra2/hankel.txt · Последние изменения: 2020/06/16 10:39 — au