§ 2. Метод А. Н. Крылова

1. Отыскание собственных значений матрицы.

Академик А. Н. Крылов одним из первых предложил довольно удобный метод раскрытия определителя (2) § 1.

Суть метода А. Н. Крылова состоит в преобразовании определителя к виду

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

Преобразование к виду (1) будем осуществлять следующим образом. Возьмем первое из уравнений (1) § 1:

и умножим его на . Появившиеся в левой части выражения заменим на равные им в силу системы (1) § 1 выражения:

Получим новое уравнение:

где

С уравнением (4) поступаем так же, как и с уравнением (2). При этом получим новое уравнение:

где

Этот процесс продолжаем до тех пор, пока не придем к уравнению

Для единообразия обозначений условимся считать

Будем рассматривать вместо системы (1) § 1 систему

Определитель этой системы как раз и равен Покажем, что

Действительно, произведение если воспользоваться формулой

и условием может быть записано в виде

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

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

Процесс получения коэффициентов можно интерпретировать как последовательное получение из вектора

векторов

при помощи соотношения

где А — транспонированная по отношению к А матрица. При любом

Естественно напрашивается следующее обобщение. Возьмем вместо того частного вектора вида (13) произвольный вектор

и получим с помощью его по формулам (16) векторы Это соответствует преобразованию уравнения

в систему

таким же процессом, которым преобразовывалось уравнение (2). Определитель системы (19) имеет вид

Так же как и ранее, нетрудно убедиться, что

Может оказаться, что но

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

где коэффициенты характеристического многочлена

Умножая равенство (22) на получим:

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

могли бы с таким же успехом использовать теорему Гамильтона — Кэли для матрицы А и пришли бы тогда к системе

где произвольный начальный вектор. Рассмотрим пример. Пусть матрица А имеет вид

В качестве вектора возьмем

Тогда:

и система для определения коэффициентов характеристического многочлена будет такова:

Решая систему (29), найдем:

Таким образом, характеристический многочлен примет вид

В приведенном примере мы пришли к характеристическому многочлену. Это оказалось возможным благодаря тому, что Исследуем теперь подробнее причины, по которым может оказаться равным нулю. Как уже упоминалось, матрица А (и транспонированная матрица А) удовлетворяет своему характеристическому уравнению Но может оказаться, что существуют

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

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

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

то

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

и

не может быть более независимых. Более того, для любых векторов и со наверняка имеет место линейная зависимость

Таким образом, если степень меньше то как бы мы ни выбирали и системы (24) и (25) будут иметь нулевые определители.

Посмотрим теперь, что может дать метод А. Н. Крылова в этом случае. Все рассуждения будем проводить с матрицей А. Для произвольного вектора найдется многочлен минимальной степени со старшим коэффициентом 1 такой, что

Назовем его минимальным многочленом вектора Любой другой многочлен обладающий свойством

должен делиться на Следовательно, минимальный многочлен матрицы А, для которого равенство (40) выполнено при любом векторе должен делиться на минимальный многочлен любого вектора

Итак, мы приходим к выводу, что если в последовательности является наибольшим индексом, для которого векторы

линейно независимы, а вектор линейно зависит от них:

то многочлен

будет являться или минимальным многочленом матрицы А или его делителем. Этот многочлен мы и получим по методу А. Н. Крылова.

Проиллюстрируем последний случай на следующем примере. В качестве матрицы А возьмем

Если снова взять , то получим: ,

Вычисления дают

Таким образом, многочлен

будет минимальным для вектора

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

Рассмотрим матрицу

где

Задача об отыскании коэффициентов в (42) эквивалентна задаче об отыскании такой линейной комбинации первых строк матрицы (48), которая в сумме с строкой обращает первые элементов последней в нули. При этом в последнем столбце получится минимальный многочлен вектора Поэтому целесообразно для получения нужной линейной комбинации применить метод исключения Гаусса. Процесс исключения можно осуществлять и до того, как будет получена полная матрица (48). Так, получив мы можем обратить в нуль какой-либо из элементов прибавив ко второй строке (48) первую, умноженную на подходящий множитель При этом в последнем столбце второй строки будет стоять вместо X выражение После такого преобразования вторая строка (48) примет вид

Теперь будем умножать на А вектор

Получим вместо прежней третьей строки (48) новую строку:

Подберем постоянные так, чтобы при прибавлении первой строки (48), умноженной на и строки (50), умноженной на к строке (51) в последней обратились в нули элементы, стоящие на месте, где Продолжая этот процесс, мы придем в конце концов к строке, все элементы которой, кроме крайнего правого, равны нулю. Это показывает нам, что мы уже получили линейно зависимые векторы. Правый крайний элемент последней строки и даст нам минимальный многочлен вектора Преимущество такого метода исключения на каждом шаге состоит в том, что на А будут умножаться векторы, имеющие все больше и больше нулевых компонент. Благодаря этому сокращается число необходимых операций умножения.

Проиллюстрируем это на примере той же матрицы А (44). Возьмем прежний вектор Получив такое же, как и в (45), исключим При этом строка (50) примет вид

После следующего умножения на А получим строку

Вычтем отсюда первую строку (48), умноженную на 2, и (52), умноженную на 3. При этом получим:

Следующее умножение на А даст

Вычтем отсюда первую строку (48), умноженную на 2, и (54), умноженную на 4. Это даст

Отсюда мы заключаем, что минимальным многочленом вектора является

Этот же многочлен мы получили и ранее.

Многочлен (57) имеет третью степень. Следовательно, он не совпадает с характеристическим многочленом, имеющим четвертую степень, В данном случае мы можем найти недостающий корень характеристического уравнения. Действительно, след матрицы, т. е. сумма ее диагональных элементов, должен равняться сумме корней характеристического многочлена матрицы. В нашем случае он равен 15. С другой стороны, сумма корней многочлена (57) равна 12. Следовательно, недостающее собственное значение равно 3. Нетрудно видеть, что многочлен (57) можно записать в виде

Таким образом, собственные значения матрицы А равны

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

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

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

операций умножения и деления.

При этом подсчете мы не учитывали действий с последним столбцом матрицы (48). Для этих действий потребуется дополнительно

операций умножения.

Таким образом, если все шагов осуществимы, то метод Крылова раскрытия векового определителя потребует

операций умножения и деления.