4. РАЗВЕРТЫВАНИЕ ХАРАКТЕРИСТИЧЕСКОГО ОПРЕДЕЛИТЕЛЯ

Характеристический полином матрицы запишем в виде

Рассмотрим некоторые методы вычисления коэффициентов этого полинома.

Метод А. Н. Крылова. Алгебраическая сущность алгоритма метода состоит в следующем [22, 106, 108]. Если вектор есть собственный вектор матрицы то векторы линейно зависимы. Для произвольного вектора существует

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

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

Пусть вектор высоты Тогда векторы в силу теоремы Гамильтона-Кэли удовлетворяют уравнению

где характеристический полином матрицы Уравнение (12) удобно записать в матричной форме

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

Таким образом, развертывание характеристического определителя сводится к решению системы линейных алгебраических уравнений (13). Эту систему удобно решать по методу Гаусса с исключением по столбцам. Для этого требуется умножений и делений. За начальный вектор можно принять любой вектор, не совпадающий с собственным вектором.

Пример. Методом Крылова вычислим коэффициенты характеристического полинома матрицы

Для этого положим Последовательное умножение на матрицу дает: Система (13) принимает вид

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

Метод А. М. Данилевского [108]. Сопровождающей матрицей характеристического полинома называется матрица

где коэффициенты характеристического полинома. Эта матрица является частным случаем канонической формы Фробениуса. Ее характеристический определитель легко раскрывается и совпадает с полиномом (10). В этом методе матрицу приводят к форме (15) путем выполнения неортогональных преобразований подобия.

Геометрическая интерпретация алгоритма такова. Исходной матрице в базисе евклидова пространства соответствует оператор. При этом столбец матрицы — коэффициенты разложения вектора по базису Предположим, что вектор высоты Тогда соотношение (12) можно записать в таком виде.

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

Исходный оператор в новом базисе очевидно, имеет матрицу в форме Фробениуса (15).

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

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

Итак, элементарное преобразование подобия на шаге имеет вид

где

На всех шагах потребуется выполнить умножений и делений.

Пример Вычислим по методу А. М. Данилевского коэффициенты характеристического полинома матрицы (14) из предыдущего примера Необходимо выполнить два шага. Так как Строим матрицы

Матрица отличается от единичной лишь вторым столбцом, который равен первому столбцу матрицы Вычисляем

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

Последний шаг

приводит к же результату

Подпрограмма вычисления коэффициентов характеристического полинома по методу А. М. Данилевского. Оператор обращения имеет вид

Здесь матрица, порядок матрицы, массив коэффициентов полиномз размерности В — массивы размерности Матрица не сохраняется. Если фактическое значение предпоследнего параметра равно 1, то подпрограмма вычисляет дополнительно и корни характеристического уравнения по методу Берстоу [62]. Для этого используется соответствующая подпрограмма

Метод Д. К. Фаддеева [108]. Алгоритм метода сводится к вычислению последовательности матриц по нижеприведенной схеме:

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

Пример. Для матрицы (14) эта схема выглядит так:

Следовательно, имеем

Подпрограмма метода Д. К. Фаддеева. Оператор обращения имеет вид [162]

Здесь матрицы порядка массив коэффициентов характеристического полинома размерности значение определителя матрицы вычисленная матрица если -вычисленная присоединенная матрица.

О методе косвенного вычисления коэффициентов характеристического уравнения. Вычислив значения определителя при некоторых заранее выбранных можно получить систему уравнений относительно коэффициентов характеристического полинома. Здесь вычисленные значения определителя. Возможны другие варианты с использованием интерполяционных полиномов. Подробный анализ [108] показал, что этот метод приводит к большим относительным погрешностям коэффициентов полинома и собственных значений.

Вычисление корней характеристического полинома. Рассмотрим характеристический полином, заданный в явном или неявном виде Метод Мюллера основан на применении квадратичной интерполяции (отсюда происходит

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

Если полином задан в неявном виде, а — вычисленные значения его корней, то для нахождения следующего корня рассматривают функцию

Оператор обращения к подпрограмме вычисления корней характеристического полинома явного вида записывают в форме

Здесь -массив коэффициентов характеристического полинома; рабочий массив размерности порядок полинома ; и массивы размерности содержащие вычисленные значения действительных и мнимых частей корней полинома соответственно.