УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ОПРЕДЕЛИТЕЛЬ


Приемы вычисления определителей, зависящих от параметров

Довольно часто на практике возникает необходимость вычислять определители, элементы которых зависят от параметров. Метод Гаусса оказывается не слишком приспособленным для такой задачи.

П

Пример. Вычислить

\left| \begin{array}{cccc} \alpha+1 &\alpha^2+1 &\alpha^2-1 &\alpha \\ \alpha^2+\alpha+1 & \alpha^2-\alpha+1 & \alpha^2 & 1 \\ 2\,\alpha+1 &\alpha^2+2 & \alpha & \alpha^2-1 \\ 2\,\alpha & 2\, \alpha^2+2\,\alpha+1 & \alpha^2-\alpha-1 & \alpha+1 \end{array} \right| \ .

Решение. Разложение по общей формуле даст величину этого определителя в виде полинома от \alpha_{}. С другой стороны, если для его вычисления мы попытаемся применить метод Гаусса, то на первом же шаге элементы преобразованного определителя окажутся дробно–рациональными функциями от параметра \alpha_{}. Понятно, что после приведения определителя к треугольному виду и перемножения стоящих на диагонали дробей мы, в конце концов, получим тот же ответ полиномиального вида, но сам факт, что для его получения потребовалось «выйти за пределы» множества полиномиальных функций не свидетельствует в пользу метода Гаусса…

!

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

Выделение линейных множителей

Этот прием основан на свойстве полиномиальности определителя как функции его элементов. Если элементы зависят — также полиномиально — от одного параметра, то можно попытаться определить линейные множители «полинома из ответа»: иногда из особенностей определителя очевидно при каких значениях параметра этот определитель обращается в нуль.

П

Пример. Вычислить определитель

\left|\begin{array}{ccccc} 1&1&1&\dots&1\\ 1&2-x&1&\dots&1\\ 1&1&3-x&\dots&1\\ \vdots& & &\ddots&\vdots\\ 1&1&1&\dots&n+1-x \end{array}\right|.

Решение. Ответом в этой задаче должен быть полином по x_{}. Обозначим его F(x)_{} и попробуем догадаться какие корни он может иметь. Обратим внимание на структуру определителя. Если положить x=1_{}, то вторая строка будет одинаковой с первой, на основании свойства 3 определителя, при этом значении x_{} будем иметь F(1)=0. Аналогично убеждаемся, что F(2)=0, \dots, F(n)=0. Итак, на основании теоремы Безу, имеем:

F(x) \equiv F_1(x) (x-1)\times \dots \times (x-n) \ ,

где через F_1(x) обозначен полином, являющийся частным от деления F(x)_{} на произведение линейных множителей. Оценим степень полинома F(x)_{}. Очевидно, что при разложении определителя по общей формуле из определения, каждое слагаемое представляет произведение элементов определителя и будет полиномом по x_{}. В каждом слагаемом максимально возможная степень может быть достигнута если каждый элемент в произведении будет иметь максимально возможную степень — в нашем случае равную 1_{}. Отсюда с неизбежностью следует, что самым «большим» по степени может быть только главный член определителя, т.е. произведение элементов его главной диагонали:

F(x) \equiv 1\cdot (2-x)\times \dots \times (n+1-x) + \dots \ ,

где многоточия скрывают все оставшиеся слагаемые полного разложения определителя и имеют степени меньшие степени выделенного слагаемого. Выделяем из этого слагаемого степень x_{}:

F(x) \equiv (-1)^n x^n + \dots \ .

Мы получили оценку степени F(x)_{} вместе с выражением для его старшего коэффициента.

Ответ. (-1)^{n} (x-1)\times \dots \times (x-n).

П

Пример. Вычислить определитель

D=\left|\begin{array}{cccc} 0&x&y&z\\ x&0&y&z\\ y&z&0&x\\ z&y&x&0 \end{array}\right|.

Решение. Если к первому столбцу прибавить остальные, то обнаружится, что определитель делится на x+y+z; если к первому столбцу прибавить второй и вычесть третий и четвертый, то выделится множитель y+z-x; если к первому столбцу прибавить третий и вычесть второй и четвертый, то выделится множитель x-y+z; наконец, если к первому столбцу прибавить четвертый и вычесть второй и третий, то выделится множитель x+y-z. Считая x,y,z независимыми переменными, заключаем, что все эти четыре множителя попарно взаимно просты, и значит, определитель — как полином от x,y,z — делится на их произведение (x+y+z)(y+z-x)(x-y+z)(x+y-z).

Это произведение содержит член z^4 с коэффициентом (-1), а сам определитель содержит тот же член с коэффициентом +1. Следовательно,

D=-(x+y+z)(y+z-x)(x-y+z)(x+y-z) =x^4+y^4+z^4-2x^2y^2-2x^2z^2-2y^2z^2 \ .

Метод рекуррентных соотношений

§

Для понимания материалов этого пункта желательно просмотреть (хотя бы бегло) раздел "Разностное уравнение и рекуррентная последовательность"

Основная идея метода заключается в том, что некоторые определители можно свести к вычислению определителей, имеющих аналогичный вид, но меньший порядок. Если удается установить вид этой зависимости в виде явной формулы, то эта формула — последовательным ее применением — позволит нам «спуститься» к определителям малых порядков.

П

Пример. Вычислить определитель

D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ x&a_2&x&\dots&x\\ x&x&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&a_n \end{array}\right|.

Решение. Представив элемент в правом нижнем углу в виде a_n=x+(a_n-x), можем определитель D_n разбить на сумму двух определителей:

D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ x&a_2&x&\dots&x\\ x&x&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&x \end{array}\right|+\left|\begin{array}{ccccc} a_1&x&x&\dots&0\\ x&a_2&x&\dots&0\\ x&x&a_3&\dots&0\\ \vdots&&&\ddots&\vdots\\ x&x&x&\dots&a_n-x \end{array}\right|.

В первом определителе последний столбец вычтем из остальных, а второй определитель разложим по последнему столбцу:

D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+(a_n-x)D_{n-1}\ .

Это и есть рекуррентное соотношение. Подставляя в него аналогичное выражение для D_{n-1}, найдем

\begin{array}{l} D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+\\ +x(a_1-x)(a_2-x)\times\dots\times(a_{n-2}-x)(a_n-x)+D_{n-2}(a_{n-1}-x)(a_n-x). \end{array}

Повторяя то же рассуждение n-1 раз и замечая, что D_1=a_1=x+(a_1-x), найдем

\begin{array}{l} D_n=x(a_1-x)(a_2-x)\dots(a_{n-1}-x)+x(a_1-x)\times\dots\times(a_{n-2}-x)(a_n-x)+\dots+\\ +x(a_2-x)\times\dots\times(a_n-x)+(a_1-x)(a_2-x)\times\dots\times(a_n-x)=\\ \displaystyle =x(a_1-x)(a_2-x)\times\dots\times(a_n-x)\left( \frac{1}{x}+\frac{1}{a_1-x}+\dots+\frac{1}{a_n-x}\right). \end{array}

?

Вычислить определитель

\left|\begin{array}{ccccc} a_1b_1&a_1b_2&a_1b_3&\dots&a_1b_n\\ a_1b_2&a_2b_2&a_2b_3&\dots&a_2b_n\\ a_1b_3&a_2b_3&a_3b_3&\dots&a_3b_n\\ \vdots&&&&\vdots\\ a_1b_n&a_2b_n&a_3b_n&\dots&a_nb_n \end{array}\right|.

Ответ. \displaystyle a_1b_n\prod_{j=1}^{n-1}(a_{j+1}b_j-a_jb_{j+1}) .

П

Пример. Вычислить определитель

D_n=\left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ y&a_2&x&\dots&x\\ y&y&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ y&y&y&\dots&a_n \end{array}\right|.

Решение начинается тем же приемом, что и в предыдущем примере:

D_n= \left|\begin{array}{ccccc} a_1&x&x&\dots&x\\ y&a_2&x&\dots&x\\ y&y&a_3&\dots&x\\ \vdots&&&\ddots&\vdots\\ y&y&y&\dots&x \end{array}\right|+(a_n-x)D_{n-1}=x(a_1-y)(a_2-y)\times \dots \times (a_{n-1}-y)+(a_n-x)D_{n-1} \ .

Можно было бы идти по проторенному пути и «разделывать» определитель D_{n-1} с использованием уже полученной формулы. Имеется, однако, более эффективный прием. Заметим, что начальный определитель симметричен относительно вхождения параметров x_{} и y_{}, и эта симметрия должна проявляться в окончательном ответе. Следовательно, наряду с полученным выражением, будет справедливо и следующее:

D_n=y(a_1-x)(a_2-x)\times \dots \times (a_{n-1}-x)+(a_n-y)D_{n-1} \ ,

произведенное перестановкой параметров x \leftrightarrow y. В результате мы получаем систему уравнений для определения двух неизвестных величин D_{n} и D_{n-1}. Решаем эту систему относительно D_n (например, по формулам Крамера):

D_n = \frac{\displaystyle y\prod_{k=1}^n(a_k-x)-x\prod_{k=1}^n(a_k-y)}{y-x} \ .

§

Прием, позволивший решить последний пример, можно отнести к случаю «удачно заметил» (свойство симметрии) — но, повторюсь, универсального способа вычисления определителей, зависящих от параметров, не существует.

В примере следующего пункта метод рекуррентных соотношений комбинируется с методом выделения линейных множителей.

Определитель Вандермонда

§

Подробнее о матрице, определителе Вандермонда и их применении ЗДЕСЬ.

П

Пример. Вычислить определитель Вандермонда

V(x_1,\dots,x_n)= \left|\begin{array}{ccccc} 1 &x_1&x_1^2&\ldots&x_1^{n-1}\\ 1 &x_2&x_2^2&\ldots&x_2^{n-1}\\ \vdots& &&& \vdots\\ 1 &x_n&x_n^2&\ldots&x_n^{n-1} \end{array}\right|_{n\times n}

Решение. Поясним идею для случая n=4. Выражение для V(x_1,x_2,x_3,x_4) — если его формально разложить по общей формуле — будет полиномом относительно своих переменных. Рассмотрим его как полином от переменной x_4, которую — для удобства — временно переобозначим через x:

\tilde V(x)=\left|\begin{array}{llll} 1 &x_1&x_1^2&x_1^3\\ 1 &x_2&x_2^2&x_2^3\\ 1 &x_3&x_3^2&x_3^3\\ 1 &x&x^2&x^3\\ \end{array}\right| \ ;

оставшиеся переменные будем считать параметрами. Если подставить в этот определитель x=x_1, то определитель обратится в нуль (как имеющий одинаковые строки см. свойство 3 ЗДЕСЬ). Аналогичные рассуждения верны для x=x_2 и x=x_3. Таким образом, полином \tilde V(x) имеет корни x_1,x_2,x_3, а его степень — если разложить по последней строке — не превышает 3. Следовательно, этот полином должен иметь следующее разложение на линейные множители:

\tilde V(x) \equiv A(x-x_1)(x-x_2)(x-x_3) \ ;

при этом константа A зависит только от x_1, x_2,x_3. Выражение для нее можно найти, если сообразить, что она является старшим коэффициентом полинома \tilde V(x), т.е. коэффициентом при степени x^3. Этот коэффициент можно «извлечь» из исходного определителя — это алгебраическое дополнение элемента определителя, стоящего в правом нижнем углу, т.е.

\left|\begin{array}{lll} 1 &x_1&x_1^2\\ 1 &x_2&x_2^2\\ 1 &x_3&x_3^2 \end{array}\right| \ .

Но этот определитель — тот же определитель Вандермонда, только порядка меньшего исходного. Возвращая переменной x ее исходное значение, получаем рекуррентное соотношение:

V(x_1,x_2,x_3,x_4)\equiv V(x_1,x_2,x_3) (x_4-x_1)(x_4-x_2)(x_4-x_3) \ .

Раскладываем определитель в правой части по той же схеме:

V(x_1,x_2,x_3) \equiv \left|\begin{array}{ll} 1 &x_1\\ 1 &x_2 \end{array}\right| (x_3-x_1)(x_3-x_2) \equiv (x_3-x_1)(x_3-x_2)(x_2-x_1) \ .

Таким образом,

V(x_1,x_2,x_3,x_4)=
=(x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ .

А в общем случае получаем ответ

V(x_1,\dots,x_n)= \prod_{1\le j < k \le n} (x_k-x_j)\ .

Определитель трёхдиагональной матрицы

Более сложный пример применения метода дает задача вычисления определителя трехдиагональной матрицы, представленного в следующем виде (определитель Якоби):

{\mathfrak J}_n = \left|\begin{array}{ccccccc} a_1 &b_1&0&0& \dots & 0 & 0\\ -c_2 &a_2&b_2&0& \dots & 0 & 0\\ 0 &-c_3&a_3&b_3& \dots & 0 & 0\\ \vdots &&& &\ddots&& \vdots \\ 0 &0&0&0& \dots & a_{n-1} & b_{n-1}\\ 0 &0&0&0& \dots & -c_n & a_{n} \end{array}\right|_{n\times n} \ .

Формальное вычисление этого определителя (в соответствии с определением) даст полином по a_1,\dots,a_n,b_1,\dots,b_{n-1},c_2,\dots,c_n, линейный по каждой из этих переменных. Если разложить {\mathfrak J}_n по последней строке, то получим:

\begin{matrix} {\mathfrak J}_n&=&a_n{\mathfrak J}_{n-1}+b_{n-1}c_n{\mathfrak J}_{n-2} =a_n(a_{n-1}{\mathfrak J}_{n-2}+b_{n-2}c_{n-1}{\mathfrak J}_{n-3})+ b_{n-1}c_n{\mathfrak J}_{n-2}= \\ &=&(a_na_{n-1}+b_{n-1}c_n){\mathfrak J}_{n-2}+a_nb_{n-2}c_{n-1}{\mathfrak J}_{n-3}= \dots \end{matrix}
П

Пример. {\mathfrak J}_2=a_1a_2+b_1c_2 , {\mathfrak J}_3=a_1a_2a_3+a_1b_2c_3+b_1c_2a_3,

{\mathfrak J}_5=a_1a_2a_3a_4a_5+b_1c_2a_3a_4a_5+a_1b_2c_3a_4a_5+a_1a_2b_3c_4a_5 +a_1a_2a_3b_4c_5+b_1c_2b_3c_4a_5+b_1c_2a_3b_4c_5+a_1b_2c_3b_4c_5 \ .

Т

Теорема. Значение {\mathfrak J}_n равно сумме главного члена a_1a_2\times \dots \times a_{n} и всевозможных произведений, получающихся из него заменой одной или нескольких пар соседних множителей a_ja_{j+1} на b_jc_{j+1}.

Частный случай определителя Якоби — континуант:

Q_n(x_1,x_2,\dots,x_{n}) = \left|\begin{array}{ccccccc} x_1 &1&0&0& \dots & 0 & 0\\ -1 &x_2&1&0& \dots & 0 & 0\\ 0 &-1&x_3&1& \dots & 0 & 0\\ \vdots &&& &\ddots&&\vdots \\ 0 &0&0&0& \dots & x_{n-1} & 1\\ 0 &0&0&0& \dots & -1 & x_{n} \end{array}\right|_{n\times n}
Т

Теорема. Континуант равен сумме произведения x_1\cdot x_2 \times \dots \times x_n и всевозможных произведений, получающихся из него вычеркиванием пар соседних множителей (и добавлением 1 в случае четного n).

П

Пример.

\begin{array}{lcl} Q_2(x_1,x_2)&=&x_1x_2+1 \ , \\ Q_3(x_1,x_2,x_3)&=& x_1x_2x_3+x_3+x_1 \ , \\ Q_6(x_1,x_2,x_3,x_4,x_5,x_6)&=&x_1x_2x_3x_4x_5x_6+\\ &&+x_3x_4x_5x_6 +x_1x_4x_5x_6+ x_1x_2x_5x_6+ x_1x_2x_3x_6+x_1x_2x_3x_4+ \\ &&+x_5x_6+x_1x_6+x_1x_2+x_1x_4+x_3x_4+x_3x_6+1 . \end{array}

Исследуем еще один частный случай определителя Якоби — при одинаковых элементах на диагоналях

a_1=\dots=a_n = a, \ b_1=\dots=b_{n-1} = b, \ c_2=\dots=c_n = c \ ;

таким образом:

{\mathfrak J}_n= \left|\begin{array}{ccccccc} a &b&0&0& \dots & 0 & 0\\ c &a&b&0& \dots & 0 & 0\\ 0 &c&a&b& \dots & 0 & 0\\ \vdots &&& &\ddots&& \vdots \\ 0 &0&0&0& \dots & a & b\\ 0 &0&0&0& \dots & c & a \end{array}\right|_{n\times n} \ .

В этом случае уравнение, связывающее определители трех последовательных порядков, принимает вид:

{\mathfrak J}_n=a{\mathfrak J}_{n-1}-bc{\mathfrak J}_{n-2} \ .

Оно может быть решено применением общего приема решения линейного разностного уравнения.

П

Пример. Вычислить

\left|\begin{array}{cccccc} 2 &2&0& \dots & 0 & 0\\ 1 & 2 &2& \dots & 0 & 0\\ 0 &1&2& \dots & 0 & 0\\ \vdots && \ddots &\ddots&& \vdots\\ 0 &0&0& \dots & 2 & 2\\ 0 &0&0& \dots & 1 & 2 \end{array}\right|_{n\times n} \ .

Решение. Разностное уравнение имеет вид {\mathfrak J}_n=2{\mathfrak J}_{n-1}-2{\mathfrak J}_{n-2}. Cтроим соответствующее ему характеристическое уравнение и находим его корни: \lambda_{1,2}=1 \pm \mathbf i. Поскольку они различны, решение разностного уравнения ищем в виде

C_1 (1+\mathbf i )^n+C_2 (1-\mathbf i)^n \ .

Для определения констант C_1 и C_2 вычислим определители первого и второго порядков: {\mathfrak J}_1=2,{\mathfrak J}_2=2.

\left\{ \begin{array}{llll} 2&=&C_1(1+\mathbf i)&+C_2(1+\mathbf i), \\ 2&=&C_1(1+\mathbf i)^2&+C_2(1+\mathbf i)^2 \end{array} \right. \quad \Rightarrow \quad C_1=\frac{1-\mathbf i}{2},\ C_2=\frac{1+\mathbf i}{2}

Ответ. {\mathfrak J}_n=(1+\mathbf i)^{n-1}+(1-\mathbf i)^{n-1}.

§

Хотя исходный определитель имеет явно вещественное значение, ответ, тем не менее, получился мнимым. Объяснение этого «парадокса» ЗДЕСЬ.

Представление определителя в виде суммы определителей

П

Пример. Вычислить определитель

D_n=\left|\begin{array}{cccc} a_1+b_1&a_1+b_2&\dots&a_1+b_n\\ a_2+b_1&a_2+b_2&\dots&a_2+b_n\\ \dots&&&\dots\\ a_n+b_1&a_n+b_2&\dots&a_n+b_n \end{array}\right|.

Решение. Определитель раскладывается по первой строке на два определителя, каждый из них по второй строке снова раскладывается на два определителя и т.д. Дойдя до последней строки, получим 2^n определителей.

Если при каждом разложении за первые слагаемые принимать числа a_i, а за вторые — числа b_j, то строки полученных определителей будут либо вида (a_i,a_i,\dots,a_i), либо вида (b_1,b_2,\dots,b_n). Две строки первого типа пропорциональны, а второго типа равны. При n>2 в каждый получившийся определитель попадут по крайней мере две строки одного типа, и он обратится в нуль. Таким образом,

D_n=0 \ npu \ n>2,\ D_1=a_1+b_1,\quad D_2=\left|\begin{array}{cc} a_1&a_1\\ b_1&b_2 \end{array}\right|+\left|\begin{array}{cc} b_1&b_2\\ a_2&a_2 \end{array}\right|=(a_1-a_2)(b_2-b_1).

?

Вычислить определитель методом представления его в виде суммы определителей

\left|\begin{array}{ccccc} x_1&a_1b_2&a_1b_3&\dots&a_1b_n\\ a_2b_1&x_2&a_2b_3&\dots&a_2b_n\\ a_3b_1&a_3b_2&x_3&\dots&a_3b_n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ a_nb_1&a_nb_2&a_nb_3&\dots&x_n \end{array}\right|.

Ответ.

(x_1-a_1b_1)(x_2-a_2b_2)\times \dots \times (x_n-a_nb_n)\left(1+\frac{a_1b_1}{x_1-a_1b_1}+\frac{a_2b_2}{x_2-a_2b_2}+\dots+\frac{a_nb_n}{x_n-a_nb_n}\right) \ .

Увеличение порядка определителя

П

Пример. Вычислить определитель

\det \left[ s_{j+k}x-s_{j+k+1} \right]_{j,k=0}^{n-1} = \left| \begin{array}{llll} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} \\ \dots & & & \dots \\ s_{n-1}x-s_{n} & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1} \end{array} \right|_{n\times n}

при заданных числовых значениях s_0,s_1,\dots,s_{2n-1}.

Решение. Здесь каждый элемент определителя зависит от переменной x. Как уже отмечалось в начале раздела, применение метода Гаусса к вычислению такого определителя неэффективно. Сформируем новый определитель порядка n+1, дополнив исходный одной строкой и одним столбцом:

\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1}x-s_{n } & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1}& 0 \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ .

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

\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1}x & s_{n}x & \dots & s_{2n-2}x& 1 \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ;

вынесем общий множитель:

x\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ;

предпоследнюю строку прибавим к предыдущей:

x\left| \begin{array}{llllc} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-2}x & s_{n-1}x & \dots & s_{2n-3}x& 1/x \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ;

и снова вынесем общий множитель:

x^2\left| \begin{array}{lllll} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\ \dots & & & \dots & \dots \\ s_{n-2} & s_{n-1} & \dots & s_{2n-3}& 1/x^2 \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ .

Продолжим процесс по аналогии, в конце концов получим

x^n\left| \begin{array}{lllll} s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 1/x^n \\ s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 1/x^{n-1} \\ \dots & & & \dots & \dots \\ s_{n-2}x & s_{n-1}x & \dots & s_{2n-3}x& 1/x^2 \\ s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\ s_n & s_{n+1} & \dots & s_{2n-1}& 1 \end{array} \right|_{(n+1)\times (n+1)} \ ,

и внесем множитель в последний столбец:

\left| \begin{array}{lllll} s_0&s_1&\dots&s_{n-1}&1 \\ s_1&s_2&\dots&s_n& x \\ \vdots & && \vdots & \vdots \\ s_{n}&s_{n+1}&\dots&s_{2n-1}&x^{n} \end{array} \right|_{(n+1)\times (n+1)} \ .

Получившийся определитель имеет порядок больший исходного. Тем не менее, выражения его элементов стали проще с той точки зрения, что переменная оказалась «выметена на край» определителя. Если разложить теперь определитель по последнему столбцу, то коэффициентами при степенях x становятся числовые определители, для вычисления которых уже можно применять метод Гаусса.

§

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

Интерполяция

§

Для понимания материалов этого пункта желательно просмотреть (хотя бы бегло) раздел "ИНТЕРПОЛЯЦИЯ". Впервые о методе прочитал в [1]. В литературе кое-где упоминается — в основном, в связи с вычислением характеристического полинома матрицы.

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

Попробуем решить пример, с которого начинается настоящий раздел.

П

Пример. Вычислить

\det A(\alpha)= \left| \begin{array}{cccc} \alpha+1 &\alpha^2+1 &\alpha^2-1 &\alpha \\ \alpha^2+\alpha+1 & \alpha^2-\alpha+1 & \alpha^2 & 1 \\ 2\,\alpha+1 &\alpha^2+2 & \alpha & \alpha^2-1 \\ 2\,\alpha & 2\, \alpha^2+2\,\alpha+1 & \alpha^2-\alpha-1 & \alpha+1 \end{array} \right| \ .

Решение. Поскольку каждый элемент определителя является полиномом, то, на основании определения определителя как суммы произведений его элементов, величина определителя также должна быть полиномом по \alpha_{}. Обозначим этот полином через F(\alpha). Таким образом, задача сводится к вычислению степени \deg F этого полинома и его коэффициентов. Для решения первой задачи формируем новый определитель, путем вытаскивания из элементов исходного определителя их старших мономов:

\left| \begin{array}{cccc} \alpha &\alpha^2 &\alpha^2 &\alpha \\ \alpha^2 & \alpha^2 & \alpha^2 & 1 \\ 2\,\alpha &\alpha^2 & \alpha & \alpha^2 \\ 2\,\alpha & 2\, \alpha^2 & \alpha^2 & \alpha \end{array} \right| \ .

Если этот определитель не равен нулю тождественно по \alpha_{}, то его старший моном совпадает со старшим мономом F(\alpha). Новый определитель также зависит от \alpha_{}, но характер этой зависимости становится менее сложным, чем у исходного, и для его вычисления можно использовать различные упрощающие соображения. Например, можно вынести общие множители элементов первого, второго и третьего столбцов (см. свойство 4 ЗДЕСЬ )

=\alpha\cdot \alpha^2 \cdot \alpha \left| \begin{array}{cccc} 1 &1 & \alpha &\alpha \\ \alpha & 1 & \alpha & 1 \\ 2 &1 & 1 & \alpha^2 \\ 2 & 2 & \alpha & \alpha \end{array} \right| =

Далее, вычитаем из последней строки первую, умноженную на 2_{}:

=\alpha^4 \left| \begin{array}{cccc} 1 &1 & \alpha &\alpha \\ \alpha & 1 & \alpha & 1 \\ 2 &1 & 1 & \alpha^2 \\ 0 & 0 & -\alpha & -\alpha \end{array} \right| =-\alpha^5 \left| \begin{array}{cccc} 1 &1 & \alpha &\alpha \\ \alpha & 1 & \alpha & 1 \\ 2 &1 & 1 & \alpha^2 \\ 0 & 0 & 1 & 1 \end{array} \right|

Теперь вычтем из четвертого столбца третий:

=-\alpha^5 \left| \begin{array}{cccc} 1 &1 & \alpha & 0 \\ \alpha & 1 & \alpha & 1-\alpha \\ 2 &1 & 1 & \alpha^2 -1 \\ 0 & 0 & 1 & 0 \end{array} \right|

и разложим определитель по последней строке:

= \alpha^5 \left| \begin{array}{ccc} 1 &1 & 0 \\ \alpha & 1 & 1-\alpha \\ 2 &1 & \alpha^2 -1 \\ \end{array} \right| \ .

Поскольку нас интересует только лишь старший моном этого определителя, в элементах последнего столбца оставляем старшие мономы:

\alpha^5 \left| \begin{array}{ccc} 1 &1 & 0 \\ \alpha & 1 & -\alpha \\ 2 &1 & \alpha^2 \end{array} \right| = \alpha^6 \left| \begin{array}{ccc} 1 &1 & 0 \\ \alpha & 1 & -1 \\ 2 &1 & \alpha \end{array} \right| \ .

Этот определитель можно вычислить «вручную» (при этом, повторюсь, нас интересуют только лишь максимальные по степени \alpha_{} члены его разложения), получаем: - \alpha^8.

Итак, неизвестный полином F(\alpha) имеет степень 8_{}. Для его определения у нас имеется представление этого полинома в форме определителя. При этом считается, что числовые определители мы вычислять умеем. Будем искать полином F(\alpha) как решение задачи интерполяции. Зададим произвольные числовые значения для \alpha_{} — в количестве 9_{} штук (по числу коэффициентов полинома, требующих определения), вычислим соответствующие числовые определители, составим интерполяционную таблицу:

\begin{array}{c|cccc} \alpha & \alpha_1 & \alpha_2 & \dots & \alpha_9 \\ \hline F & \det A (\alpha_1) &\det A (\alpha_2) & \dots & \det A (\alpha_9) \end{array}

и вычислим F(\alpha) по одному из методов вычисления интерполяционного полинома.

На виду лежат два соображения:

1. имеет смысл в качестве чисел \alpha_j выбирать возможно минимальные по модулю;

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

\begin{array}{c|rrrccccc} \alpha & 0 & 1 & -1 & 2 & -2 & 3 & -3 & 4 \\ \hline F & -4 & -4 & 24 &-222 & 734 & -9616 & 4388 & -98176 \end{array}

Ответ. -\alpha^8-3\,\alpha^7+3\,\alpha^6-\alpha^5+23\,\alpha^4-7\,\alpha^3-11\,\alpha^2-3\,\alpha-4.

§

При решении примера настоящего пункта мы столкнулись со следующей задачей. Составим матрицу степеней полиномов, содержащихся в матрице A_{}:

B=\left( \begin{array}{cccc} 1 &2 &2 &1 \\ 2 &2 &2 & 0 \\ 1 &2 &1 & 2 \\ 1 & 2 & 2 & 1 \end{array} \right) \ .

Требуется выбрать по одному элементу из каждой строки и каждого столбца этой матрицы, так, чтобы получившаяся сумма стала максимальной:

b_{1j_1}+b_{2j_2}+b_{3j_3}+b_{4j_4} \quad при различных \quad \{ j_1,j_2,j_3,j_4\} \subset \{ 1,2,3,4 \} .

Иными словами, после выбора какого-то кандидата в сумму, из матрицы вычеркиваются строка и столбец его содержащие, и дальнейший выбор осуществляется в оставшейся подматрице. Задача оказывается нетривиальной уже хотя бы потому, что «жадная стратегия» выбора — когда на каждом шаге выбирается максимальный из оставшихся элементов — не приводит к правильному ответу:

B=\left( \begin{array}{cc} 4 &3 \\ 3 &1 \end{array} \right) \quad \Rightarrow \quad 4+1 < 3 + 3 \ .

Оказывается эта задача является примером известной в теории оптимизации задачи о назначениях1).

Задача. Имеется n_{} работ, которые надо поручить n_{} работникам. Каждый работник может быть назначен только на одну работу, и каждая работа может быть поручена только одному работнику. Прибыль от труда работника под номером j_{} при выполнении работы под номером k_{} известна и равна b_{jk}. Как распределить работы между работниками так, чтобы прибыль стала максимальной?

Разные определители, встречающиеся в ресурсе

Определитель Коши

\det \left[\frac{1}{a_j+b_k} \right]_{j,k=1}^n= \left|\begin{array}{cccc} \frac{1}{a_1+b_1} &\frac{1}{a_1+b_2}&\ldots&\frac{1}{a_1+b_n}\\ & & & \\ \frac{1}{a_2+b_1} &\frac{1}{a_2+b_2}&\ldots&\frac{1}{a_2+b_n}\\ & & & \\ \ldots & & & \ldots\\ \frac{1}{a_n+b_1} &\frac{1}{a_n+b_2}&\ldots&\frac{1}{a_n+b_n} \end{array}\right|_{n\times n}\ .

Рассматривается ЗДЕСЬ.

Определитель расстояний

или определитель матрицы расстояний

\det \left[ |P_jP_k|^2 \right]_{j,k=1}^m =\left| \begin{array}{cccc} 0 & |P_1P_2|^2 & \dots & |P_1P_m|^2 \\ |P_1P_2|^2 & 0 & \dots & |P_2P_m|^2 \\ \vdots & & \ddots & \vdots \\ |P_1P_m|^2 & |P_2P_m|^2 & \dots & 0 \end{array} \right| \quad npu \quad \{P_1,\dots,P_m\} \subset \mathbb R^n

Рассматривается ЗДЕСЬ.

Определители безымянные, но полезные

\left|\begin{array}{llllllll} 1 & \cos x_1 & \sin x_1 & \cos \, 2\, x_1 & \sin \, 2\, x_1 & \dots & \cos \, n\, x_1 & \sin \, n\, x_1 \\ 1 & \cos x_2 & \sin x_2 & \cos \, 2\, x_2 & \sin \, 2\, x_2 & \dots & \cos \, n\, x_2 & \sin \, n\, x_2 \\ \dots & & & & & & & \dots \\ 1 & \cos x_{2n+1} & \sin x_{2n+1} & \cos \, 2\, x_{2n+1} & \sin \, 2\, x_{2n+1} & \dots & \cos \, n\, x_{2n+1} & \sin \, n\, x_{2n+1} \end{array} \right| =
= 2^{2n^2} \prod_{0\le k < j \le 2n} \sin \frac{x_k-x_j}{2} \ .

Рассматривается ЗДЕСЬ.

Задачи

ЗДЕСЬ.

Источники

[1]. Микеладзе Ш.Е. Решение численных уравнений. Тбилиси.Мецниереба. 1965

1) assignment problem

2017/03/19 11:08 редактировал au