Вычисление определителей с помощью рекуррентных уравнений

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

Основное

Навигация

Информация

Действия

Содержание

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

Видео:Рекуррентное вычисление определителя порядка nСкачать

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

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

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

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

Видео:Семинар №13 "Определители n го порядка"Скачать

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

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

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

$$left|begin 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 endright|.$$

Решение. Ответом в этой задаче должен быть полином по $ 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 1cdot (2-x)times dots times (n+1-x) + dots , $$ где многоточия скрывают все оставшиеся слагаемые полного разложения определителя и имеют степени меньшие степени выделенного слагаемого. Выделяем из этого слагаемого степень $ x_ $: $$ F(x) equiv (-1)^n x^n + dots . $$ Мы получили оценку степени $ F(x)_ $ вместе с выражением для его старшего коэффициента.

Ответ. $ (-1)^ (x-1)times dots times (x-n) $.

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

Решение. Если к первому столбцу прибавить остальные, то обнаружится, что определитель делится на $ 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 . $$

Видео:5 способов вычисления определителя ★ Какой способ лучше?Скачать

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

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

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

$$D_n=left|begin 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 endright|.$$

Решение. Представив элемент в правом нижнем углу в виде $ a_n=x+(a_n-x) $, можем определитель $ D_n $ разбить на сумму двух определителей: $$D_n=left|begin 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 endright|+left|begin 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 endright|.$$ В первом определителе последний столбец вычтем из остальных, а второй определитель разложим по последнему столбцу: $$D_n=x(a_1-x)(a_2-x)timesdotstimes(a_-x)+(a_n-x)D_ .$$ Это и есть рекуррентное соотношение. Подставляя в него аналогичное выражение для $ D_ $, найдем $$begin D_n=x(a_1-x)(a_2-x)timesdotstimes(a_-x)+\ +x(a_1-x)(a_2-x)timesdotstimes(a_-x)(a_n-x)+D_(a_-x)(a_n-x). end$$ Повторяя то же рассуждение $ n-1 $ раз и замечая, что $ D_1=a_1=x+(a_1-x) $, найдем $$begin D_n=x(a_1-x)(a_2-x)dots(a_-x)+x(a_1-x)timesdotstimes(a_-x)(a_n-x)+dots+\ +x(a_2-x)timesdotstimes(a_n-x)+(a_1-x)(a_2-x)timesdotstimes(a_n-x)=\ displaystyle =x(a_1-x)(a_2-x)timesdotstimes(a_n-x)left( frac+frac+dots+fracright). end$$

$$left|begin 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 endright|.$$

Ответ. $ displaystyle a_1b_nprod_^(a_b_j-a_jb_) $ .

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

$$D_n=left|begin 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 endright|.$$

Решение начинается тем же приемом, что и в предыдущем примере: $$ D_n= left|begin 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 endright|+(a_n-x)D_=x(a_1-y)(a_2-y)times dots times (a_-y)+(a_n-x)D_ . $$ Можно было бы идти по проторенному пути и «разделывать» определитель $ D_ $ с использованием уже полученной формулы. Имеется, однако, более эффективный прием. Заметим, что начальный определитель симметричен относительно вхождения параметров $ x_ $ и $ y_ $, и эта симметрия должна проявляться в окончательном ответе. Следовательно, наряду с полученным выражением, будет справедливо и следующее: $$ D_n=y(a_1-x)(a_2-x)times dots times (a_-x)+(a_n-y)D_ , $$ произведенное перестановкой параметров $ x leftrightarrow y $. В результате мы получаем систему уравнений для определения двух неизвестных величин $ D_ $ и $ D_ $. Решаем эту систему относительно $ D_n $ (например, по формулам Крамера): $$ D_n = frac<displaystyle yprod_^n(a_k-x)-xprod_^n(a_k-y)> . $$ ♦

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

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

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

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

$$ V(x_1,dots,x_n)= left|begin 1 &x_1&x_1^2&ldots&x_1^\ 1 &x_2&x_2^2&ldots&x_2^\ vdots& &&& vdots\ 1 &x_n&x_n^2&ldots&x_n^ endright|_ $$

Решение. Поясним идею для случая $ n=4 $. Выражение для $ V(x_1,x_2,x_3,x_4) $ — если его формально разложить по общей формуле — будет полиномом относительно своих переменных. Рассмотрим его как полином от переменной $ x_4 $, которую — для удобства — временно переобозначим через $ x $: $$ tilde V(x)=left|begin 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\ endright| ; $$ оставшиеся переменные будем считать параметрами. Если подставить в этот определитель $ 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 1 &x_1&x_1^2\ 1 &x_2&x_2^2\ 1 &x_3&x_3^2 endright| . $$ Но этот определитель — тот же определитель Вандермонда, только порядка меньшего исходного. Возвращая переменной $ 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 1 &x_1\ 1 &x_2 endright| (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_<1le j ♦

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

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

$$ _n = left|begin 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_ & b_\ 0 &0&0&0& dots & -c_n & a_ endright|_ . $$ Формальное вычисление этого определителя (в соответствии с определением) даст полином по $ a_1,dots,a_n,b_1,dots,b_,c_2,dots,c_n $, линейный по каждой из этих переменных. Если разложить $ _n $ по последней строке, то получим: $$ begin _n&=&a_n_+b_c_n_ =a_n(a__+b_c__)+ b_c_n_= \ &=&(a_na_+b_c_n)_+a_nb_c__= dots end $$

Пример.

$ _2=a_1a_2+b_1c_2 $ , $ _3=a_1a_2a_3+a_1b_2c_3+b_1c_2a_3 $, $$ _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 . $$

Теорема. Значение $ _n $ равно сумме главного члена $ a_1a_2times dots times a_ $ и всевозможных произведений, получающихся из него заменой одной или нескольких пар соседних множителей $ a_ja_ $ на $ b_jc_ $.

Частный случай определителя Якоби — континуант: $$ Q_n(x_1,x_2,dots,x_) = left|begin 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_ & 1\ 0 &0&0&0& dots & -1 & x_ endright|_ $$

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

Пример.

$$ begin 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 $$

Исследуем еще один частный случай определителя Якоби — при одинаковых элементах на диагоналях $$a_1=dots=a_n = a, b_1=dots=b_ = b, c_2=dots=c_n = c ; $$ таким образом: $$ _n= left|begin 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 endright|_ . $$ В этом случае уравнение, связывающее определители трех последовательных порядков, принимает вид: $$ _n=a_-bc_ .$$ Оно может быть решено применением общего приема решения линейного разностного уравнения.

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

$$ left|begin 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 endright|_ . $$

Решение. Разностное уравнение имеет вид $ _n=2_-2_ $. Cтроим соответствующее ему характеристическое уравнение и находим его корни: $ lambda_=1 pm mathbf i $. Поскольку они различны, решение разностного уравнения ищем в виде $$ C_1 (1+mathbf i )^n+C_2 (1-mathbf i)^n .$$ Для определения констант $ C_1 $ и $ C_2 $ вычислим определители первого и второго порядков: $ _1=2,_2=2 $. $$ left< begin 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 right. quad Rightarrow quad C_1=frac, C_2=frac $$ Ответ. $ _n=(1+mathbf i)^+(1-mathbf i)^ $.

Видео:Определитель матрицы и все способы его найтиСкачать

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

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

$$D_n=left|begin 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 endright|.$$

Решение. Определитель раскладывается по первой строке на два определителя, каждый из них по второй строке снова раскладывается на два определителя и т.д. Дойдя до последней строки, получим $ 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 a_1&a_1\ b_1&b_2 endright|+left|begin b_1&b_2\ a_2&a_2 endright|=(a_1-a_2)(b_2-b_1).$$

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

$$left|begin 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 endright|.$$

Ответ. $$(x_1-a_1b_1)(x_2-a_2b_2)times dots times (x_n-a_nb_n) times $$ $$ times left(1+frac+frac+dots+fracright) .$$

Видео:Определитель Вандермонда. Метод рекуррентных соотношенийСкачать

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

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

$$ det left[ s_x-s_ right]_^ = left| begin s_0x-s_1&s_1x-s_2&dots& s_x-s_ \ s_1x-s_2&s_2x-s_3&dots& s_x-s_ \ dots & & & dots \ s_x-s_ & s_x-s_ & dots & s_x-s_ end right|_ $$ при заданных числовых значениях $ s_0,s_1,dots,s_ $.

Видео:Вычислить определитель n-го порядка.Скачать

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

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

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

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

$$ det A(alpha)= left| begin 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 right| . $$

Решение. Поскольку каждый элемент определителя является полиномом, то, на основании определения определителя как суммы произведений его элементов, величина определителя также должна быть полиномом по $ alpha_ $. Обозначим этот полином через $ F(alpha) $. Таким образом, задача сводится к вычислению степени $ deg F $ этого полинома и его коэффициентов. Для решения первой задачи формируем новый определитель, путем вытаскивания из элементов исходного определителя их старших мономов: $$ left| begin 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 right| . $$ Если этот определитель не равен нулю тождественно по $ alpha_ $, то его старший моном совпадает со старшим мономом $ F(alpha) $. Новый определитель также зависит от $ alpha_ $, но характер этой зависимости становится менее сложным, чем у исходного, и для его вычисления можно использовать различные упрощающие соображения. Например, можно вынести общие множители элементов первого, второго и третьего столбцов (см. свойство 4 ☞ ЗДЕСЬ ) $$ =alphacdot alpha^2 cdot alpha left| begin 1 &1 & alpha &alpha \ alpha & 1 & alpha & 1 \ 2 &1 & 1 & alpha^2 \ 2 & 2 & alpha & alpha end right| = $$ Далее, вычитаем из последней строки первую, умноженную на $ 2_ $: $$ =alpha^4 left| begin 1 &1 & alpha &alpha \ alpha & 1 & alpha & 1 \ 2 &1 & 1 & alpha^2 \ 0 & 0 & -alpha & -alpha end right| =-alpha^5 left| begin 1 &1 & alpha &alpha \ alpha & 1 & alpha & 1 \ 2 &1 & 1 & alpha^2 \ 0 & 0 & 1 & 1 end right| $$ Теперь вычтем из четвертого столбца третий: $$ =-alpha^5 left| begin 1 &1 & alpha & 0 \ alpha & 1 & alpha & 1-alpha \ 2 &1 & 1 & alpha^2 -1 \ 0 & 0 & 1 & 0 end right| $$ и разложим определитель по последней строке: $$ = alpha^5 left| begin 1 &1 & 0 \ alpha & 1 & 1-alpha \ 2 &1 & alpha^2 -1 \ end right| . $$ Поскольку нас интересует только лишь старший моном этого определителя, в элементах последнего столбца оставляем старшие мономы: $$ alpha^5 left| begin 1 &1 & 0 \ alpha & 1 & -alpha \ 2 &1 & alpha^2 end right| = alpha^6 left| begin 1 &1 & 0 \ alpha & 1 & -1 \ 2 &1 & alpha end right| . $$ Этот определитель можно вычислить «вручную» (при этом, повторюсь, нас интересуют только лишь максимальные по степени $ alpha_ $ члены его разложения), получаем: $ — alpha^8 $.

Итак, неизвестный полином $ F(alpha) $ имеет степень $ 8_ $. Для его определения у нас имеется представление этого полинома в форме определителя. При этом считается, что числовые определители мы вычислять умеем. Будем искать полином $ F(alpha) $ как решение задачи интерполяции. Зададим произвольные числовые значения для $ alpha_ $ — в количестве $ 9_ $ штук (по числу коэффициентов полинома, требующих определения), вычислим соответствующие числовые определители, составим интерполяционную таблицу: $$ begin alpha & alpha_1 & alpha_2 & dots & alpha_9 \ hline F & det A (alpha_1) &det A (alpha_2) & dots & det A (alpha_9) end $$ и вычислим $ F(alpha) $ по одному из методов вычисления интерполяционного полинома.

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

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

2. поскольку мы уже знаем величину одного из коэффициентов, имеет смысл выбрать — из двух стандартных представлений интерполяционного полинома — форму Ньютона (последнее вычисление делать не придется, можно сократить число узлов интерполяции). Для настоящего примера: $$ begin alpha & 0 & 1 & -1 & 2 & -2 & 3 & -3 & 4 \ hline F & -4 & -4 & 24 &-222 & 734 & -9616 & 4388 & -98176 end $$

Ответ. $ -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 1 &2 &2 &1 \ 2 &2 &2 & 0 \ 1 &2 &1 & 2 \ 1 & 2 & 2 & 1 end right) . $$ Требуется выбрать по одному элементу из каждой строки и каждого столбца этой матрицы, так, чтобы получившаяся сумма стала максимальной: $$ b_+b_+b_+b_ quad mbox quad subset . $$ Иными словами, после выбора какого-то кандидата в сумму, из матрицы вычеркиваются строка и столбец его содержащие, и дальнейший выбор осуществляется в оставшейся подматрице. Задача оказывается нетривиальной уже хотя бы потому, что «жадная стратегия» выбора — когда на каждом шаге выбирается максимальный из оставшихся элементов — не приводит к правильному ответу: $$ B=left( begin 4 &3 \ 3 &1 end right) quad Rightarrow quad 4+1 1) .

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

Видео:7. Вычисление определителей 3, 4 порядков. Разложение определителя по элементам строки (столбца)Скачать

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

Видео:7. Вычисление определителя методом разложения по строке или столбцуСкачать

04.10. Некоторые приемы вычисления определителей NГО порядка

1. Метод приведения к треугольному виду.

А) Вычислить определитель: .

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

. В итоге Dn = (–1)N–1.

Б) Вычислить определитель:.

Вычитаем первую строку из всех остальных, а затем, из столбцов определителя выносим: из первого А1 – Х; из второго А2 – Х; …..; из N го Аn – Х. Получим:

D = (A1 – X) (A2 – x)… (An – x).

Запишем первый элемент первого столбца в виде: = 1 + , и все столбцы полученного определителя прибавим к первому столбцу. Получим определитель треугольного вида, который равен произведению диагональных элементов. Следовательно:

D = (A1– X) (A2 – X)…(An – X)X+++ … +.

2. Метод выделения линейных множителей.

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

1. Прибавляя к первому столбцу определителя остальные три, обнаружим, что в первом столбце есть общий множитель, который равен Х + У + Z. Следовательно, определитель делится на Х + У + Z.

2. Аналогично, прибавляя к первому столбцу второй и вычитая из него третий и четвертый столбцы, получаем, что определитель делится на Х – У – Z.

3. Если первый столбец сложить с третьим и вычесть второй и четвертый, то получим, что определитель делится на Х – У + Z.

4. Если к первому столбцу прибавить четвертый и вычесть второй и третий столбцы, то обнаружим, что определитель имеет множитель Х – У + Z. Итак:

= .

Ясно, что определитель является многочленом 4й степени по X, по Y и по Z. Справа тоже многочлен той же степени. Поэтому V = const. В определитель X4 входит в слагаемом:

A12A21A34A43 = (–1)2×Х×Х×Х×Х = Х4.

В правой части старший член по Х: Vx4, т. е. V = 1. Получаем результат:

= (X + Y + Z)(X – Y – Z)(X – Y + Z)(X + Y – Z) = X4 + Y4 + Z4 – 2X2Y2 – 2X2Z2 – 2У2Z2.

Б) Вычислить определитель N-го порядка: .

Этот определитель Называется определителем Вандермонда. Рассматривая его как многочлен (N –1)й степени относительно Xn увидим, что он обращается в 0 при Xn = X1, Xn = X2, … Xn = Xn – 1. Тогда Dn = An – 1(Xn – X1)(Xn – X2) … (Xn – xn–1), причем An–1 = = Dn–1. Повторяя эту процедуру, получим: Dn = (X2 – X1)(X3 – X2)(X3 – X1)(X4 – X3)(X4 – X2)(X4 – –X1)… = .

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

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

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

.

Теперь каждый из полученных определителей разложим в сумму двух определителей, воспользовавшись тем, что элементы вторых столбцов у них также представлены в виде сумм, и т. д. Проделав это, получим (N > 2), что строки полученных определителей будут такими: Ai, ai, … , ai Или B1, B2, … ,bn . Строки 1го типа пропорциональны, 2го типа равны и, следовательно, все слагаемые равны нулю. Следовательно: Dn = 0 («N > 2).

Для определителей такого же типа, но первого и второго порядков получим:

D1 = | A1+ b1 | = A1+ b1; D2 = =

4. Метод рекуррентных (возвратных) соотношений.

Вычислить определитель N–го порядка: .

Разлагая определитель по элементам первой строки, получим рекурентное соотношение: Dn=.

Разложив определитель в правой части соотношения по первому столбцу, запишем новое рекурентное соотношение: Dn = 5Dn–1 – 6Dn–2.

Представляя это соотношение в виде: Dn – 2Dn–1 = 3(Dn–1 – 2Dn–2) и вводя обозначение:

Аналогично, записав рекурентное соотношение в виде: Dn – 3Dn–1 = 2(Dn–1 – 3Dn–2) и обозначая: Vn = Dn – 3Dn–1 получим Vn = 2Vn=1 = 22Vn–2=…= 2N .

т. е. Dn = 3N + 1 – 2N + 1.

В общем случае, для рекуррентных соотношений типа: Dn = PDn – 1 + QDn – 2 .можно проделать следующее: пусть a и b корни уравнения X2 – Px – Q = 0, т. е. P = a + b,

Q = –ab. Тогда Dn = aDn – 1 + bDn –1 – abDN – 2; Dn – aDn -–1 = b(Dn – 1 – aDn – 2), т. е. Sn = bSn – 1 или Dn – bDn -–1 = a(Dn – 1 – bDn – 2), т. е. Vn = bVn – 1 .

Аналогично можно поступить и в более сложных рекуррентных соотношениях.

5. Метод изменения элементов определителя.

19°. Если ко всем элементам определителя D добавить одно и то же число X, то определитель увеличится на произведение числа X на сумму алгебраических дополнений всех элементов определителя D.

◀ Пусть D = | Aij |; D¢ = | Aij + X |. Разложим D¢ в сумму двух определителей относительно первой строки, каждый из них на два относительно второй строки и т. д. Слагаемые, содержащие более одной строки элементов X, равны нулю.

Слагаемые, содержащие одну строку элементов X, разложим по этой строке. Получим D¢ = D + X. ▶

А). . Вычтем из всех элементов определителя число X

. Тогда Dn = (A1 – X)(A2 – X)…(AN – X) + X= (A1 – X)(A2 – X).

…(An – X) + X = (A1 – X) (A2 – X) … (An – X) + X= (A1 – X )( A2 – X )…( An– X ) +

+ X =

= x(A1 – X) (A2 – X) … (An – x) .

Видео:Определитель порядка nСкачать

Методы вычисления определителей

При вычислении определителей высокого порядка (больше 3-го) определение, как правило, не используется, так как это приводит к громоздким выражениям и требует большого количества арифметических операций. Гораздо эффективнее использовать свойства определителей . Наиболее важными для вычисления определителей являются свойства 3, 6, 9. Эти свойства можно назвать элементарными преобразованиями определителя , что соответствует элементарным преобразованиям матрицы.

I. Перестановка двух столбцов (строк) определителя приводит к изменению его знака на противоположный.

II. Умножение всех элементов одного столбца (строки) определителя на одно и то же число, отличное от нуля, приводит к умножению определителя на это число.

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

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

Видео:Свойства определителя - bezbotvyСкачать

Метод приведения определителя к треугольному виду

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

Итак, метод состоит из двух шагов.

1. При помощи элементарных преобразований привести определитель к треугольному виду.

2. Вычислить определитель треугольного вида, перемножая его элементы, стоящие на главной диагонали.

Пример 2.12. Вычислить определитель четвёртого порядка

Решение. 1. При помощи элементарных преобразований приведем матрицу к треугольному виду. Взяв элемент первой строки в качестве ведущего, все остальные элементы первого столбца сделаем равными нулю. Для этого ко второй строке прибавим первую, умноженную на (-2), к третьей строке прибавим первую, умноженную на (-3), а к четвертой строке прибавим первую, умноженную на (-4):

Заметим, что при использовании этих элементарных преобразований III типа определитель не изменяется.

Умножим элементы второй строки на (-1), а элементы третьей строки — на 0,5, при этом, чтобы не нарушить равенство, надо полученный определитель разделить на , т.е. умножить на (-2):

В полученной матрице нужно сделать равными нулю элементы и второго столбца, стоящие ниже главной диагонали. Для этого берем в качестве ведущего элемента и прибавляем к третьей и четвертой строкам вторую строку, умноженную на 1 и на 7 соответственно:

Осталось сделать равным нулю элемент . К четвертой строке прибавим третью, умноженную на 2 (определитель при этом не изменится):

Получили определитель треугольного вида.

2. Вычислим определитель верхней треугольной матрицы, перемножая элементы, стоящие на главной диагонали :

Видео:21.04 - дискра, рекуррентные соотношенияСкачать

Метод понижения порядка определителя

Этот метод также основан на элементарных преобразованиях определителя.

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

2. Разложить определитель по этому столбцу (строке) и получить определитель меньшего порядка, чем исходный. Если его порядок больше 1, то следует перейти к п. 1, иначе вычисления закончить.

Пример 2.13. Вычислить определитель четвёртого порядка методом понижения порядка.

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

2. Разложим определитель по второй строке

Получили определитель третьего порядка.

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

Прибавим ко второму столбцу первый

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

Получили определитель 2-го порядка.

Прибавим ко второй строке первую, умноженную на (-2)

Разложим определитель по второй строке и заменим определитель первого порядка единственным его элементом

Результат совпадает с полученным в примере 2.7.

Видео:Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Метод изменения всех элементов определителя

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

Пусть дана квадратная матрица n-го порядка. Из свойства 6 следует, что при умножении всех элементов определителя n-го порядка на число определитель умножается на число .

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

Применяя свойство 7 к первому столбцу этого определителя, получаем сумму определителей

То же свойство применяем к каждому определителю («раскладывая» второй столбец) и т.д. В итоге получим сумму определителей n-го порядка, причем определители, имеющие по два и более столбцов из элементов, равных , равны нулю (по свойству 4). Поэтому в сумме остаются только слагаемых: определитель матрицы и определителей вида

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

Следовательно, сумма всех таких определителей равна сумме алгебраических дополнений всех элементов матрицы , умноженной на

Окончательно получаем, что при увеличении всех элементов определителя на число , определитель увеличивается на сумму всех алгебраических дополнений, умноженную на число

Пример 2.14. Вычислить определитель n-го порядка

Решение. Рассмотрим определитель диагональной матрицы

Искомый определитель получается прибавлением к каждому элементу определителя матрицы числа . Поэтому

Определитель диагональной матрицы равен произведению диагональных элементов:

Осталось вычислить сумму алгебраических дополнений всех элементов матрицы . Заметим, что алгебраическое дополнение недиагонального элемента равно нулю ( при , так как дополнительный минор содержит нулевой столбец). Дополнительный минор диагонального элемента — это определитель диагональной матрицы, т.е.

Видео:Вычисление определителя четвертого порядка по теореме ЛапласаСкачать

Вычисление определителей с помощью рекуррентных уравнений

Этот метод заключается в том, что исходный определитель n-го порядка выражается через определители того же вида, но меньшего порядка. Получается рекуррентное уравнение

Решая это уравнение, находим формулу, выражающую определитель через определители и порядок

В последнюю формулу подставляем определители невысокого порядка, которые нетрудно вычислить каким-либо другим способом.

Замечание 2.6. Рекуррентным уравнением называется равенство вида , выражающее n-й член искомой числовой последовательности через её предыдущих членов . Методы решения таких уравнений рассматриваются в разд.

Пример 2.15. Вычислить определитель n-го порядка

Решение. Разложим определитель по первой строке

Первый из полученных определителей (n-l)-ro порядка обозначим , так как он имеет такой же вид, что и . Разложив последний определитель по первому столбцу, получим определитель того же вида, что и , но (n-2)-го порядка

Следовательно, искомый определитель удовлетворяет рекуррентному уравнению

Решение этого уравнения будем искать в виде , где и — неизвестные коэффициенты. Заметим, что эта формула дает решение рекуррентного уравнения при любых коэффициентах и . В самом деле, подставляя в уравнение, получаем тождество

Подберем теперь коэффициенты и в формуле так, чтобы при и она давала правильные результаты, т.е.

Решая систему уравнений получаем . Следовательно, искомый определитель равен

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

Решение. Рассмотрим определитель

который отличается от определителя Вандермонда последним столбцом, но совпадает с ним при . Раскладывая определитель по последнему столбцу, получаем многочлен (n-1)-й степени действительной переменной

где старший коэффициент равен алгебраическому дополнению элемента

т.е. определителю — определителю Вандермонда (n-l)-ro порядка. Заметим, что при определитель равен нулю, так как он имеет два одинаковых столбца (свойство 4). Следовательно, — корень многочлена . То же самое можно сказать про числа . Все они являются корнями многочлена . Следовательно, этот многочлен имеет вид:

Подставляя в это равенство и учитывая, что , получаем рекуррентное уравнение

Записывая аналогичным образом и учитывая, что , получаем

Таким образом, определитель Вандермонда равен произведению всех разностей при .

🔍 Видео

6. Вычисление определителя 2 и 3 порядка.Скачать

Решение рекуррентных уравненийСкачать

Как вычислить определитель матрицы четвертого порядка | Высшая математикаСкачать

Вычислить определитель 3 порядка. Правило треугольникаСкачать

Определитель 5 порядкаСкачать

Как найти определитель матрицы 2х2, 3х3 и 4х4Скачать

Рекуррентные уравненияСкачать