Реферат Вычисление Определителей С Помощью Рекуррентных Уравнений
Реферат Вычисление Определителей С Помощью Рекуррентных Уравнений
Перейти к содержанию
VMath
Универсальных методов вычисления подобных определителей
(отличных, естественно, от определения ) не существует . Успех во многом будет зависеть от искусства
вычислителя. Здесь мы покажем несколько полезных приемов, которые иногда помогают.
Для понимания материалов этого пункта рекомендуется ознакомиться с разделом "Разностное уравнение и рекуррентная последовательность"
.
Прием, позволивший решить последний пример, можно отнести к случаю «удачно заметил» (свойство симметрии) — но, повторюсь, универсального способа вычисления определителей, зависящих от параметров, не существует.
Хотя исходный определитель имеет явно вещественное значение, ответ, тем не менее, получился мнимым . Объяснение этого «парадокса»
☞
ЗДЕСЬ .
Разобранный прием, на первый взгляд, кажется не вполне естественным; он практически не упоминается в литературе. Тем не менее, он неявно используется в двух методах вычисления характеристического полинома матрицы .
Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом "ИНТЕРПОЛЯЦИЯ" .
.
Впервые о методе прочитал в [1] . В литературе кое-где упоминается — в основном, в связи с вычислением характеристического полинома матрицы .
algebra2/dets/special_cases.txt · Последние изменения: 2020/11/23 14:55 — au
Вспомогательная страница к разделу ОПРЕДЕЛИТЕЛЬ
Довольно часто на практике возникает необходимость вычислять определители, элементы которых зависят от параметров. Метод Гаусса оказывается не слишком приспособленным для такой задачи.
$$
\left|
\begin{array}{cccc}
{\color{Red} \alpha } +1 &{\color{Red} \alpha } ^2+1 &{\color{Red} \alpha } ^2-1 & {\color{Red} \alpha } \\
{\color{Red} \alpha } ^2+{\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2- {\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2 & 1 \\
2\,{\color{Red} \alpha } +1 &{\color{Red} \alpha } ^2+2 & {\color{Red} \alpha } & {\color{Red} \alpha } ^2-1 \\
2\,{\color{Red} \alpha } & 2\, {\color{Red} \alpha } ^2+2\,{\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2-{\color{Red} \alpha } -1 & {\color{Red} \alpha } +1
\end{array}
\right| \ .
$$
Решение. Разложение по общей формуле даст величину этого определителя в виде полинома от
$ {\color{Red} \alpha } $. С другой стороны, если для его вычисления мы попытаемся применить
метод Гаусса , то на первом же шаге элементы преобразованного определителя окажутся дробно–рациональными
функциями от параметра $ {\color{Red} \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)
\times
$$
$$
\times \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 $ становятся числовые определители, для вычисления которых уже можно применять метод Гаусса.
♦
Можно считать излагаемый ниже метод обобщением приведенного выше метода выделения линейных множителей : если матрица имеет полиномиальную зависимость от параметра (параметров), то угадать корни ее определителя — также полинома от этого параметра — удается не всегда, а вот его значения при конкретных величинах параметра (параметров) всегда можно вычислить.
Попробуем решить пример, с которого начинается настоящий раздел .
$$ \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 $.
$$
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 \mbox{ при различных } \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
Приемы вычисления определителей , зависящих от параметров
Реферат : Определители Решение систем линейных уравнений
Вычисление определителей методом рекурентных соотношений.
Реферат : Рекуррентно заданные числовые последовательности
Вычисление определителей с помощью рекуррентных ...
Сочинение На Тему Мой Родной Город Ставрополь
Рефераты По Физкультуре 9 Класс Кратко
Контрольная Работа Магнитное Поле 11 Класс
Историческая Память Народа Сочинение
Сочинение В Жанре Дневниковых Записей Пример