3. Метод интерполяции.

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

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

Простейшим прямым методом является метод интерполяции (предложенный, по-видимому, Ш. Е. Микеладзе в 1948 г.) Известно, что многочлен степени однозначно определяется своими значениями в узле. Произвольно выберем значение в качестве таких узлов. Вычислим в них значение и построим по этим значениям интерполяционный многочлен Ньютона при помощи формул (2.6) и (2.8). В силу единственности этот многочлен будет характеристическим. Он при этом получается в форме многочлена с заданными коэффициентами, так что дальнейшие вычисления для нахождения его корней потребуют малого числа действий.

Описанный алгоритм несложен и легко программируется на ЭВМ. В нем следует использовать стандартную программу вычисления определителя методом исключения (глава V, § 1, п. 3). При этом характеристический многочлен определяется примерно за арифметических действий, из которых половину составляют сложения и половину — умножения.

Видно, что для матриц невысокого порядка 10 нахождение характеристического многочлена методом интерполяции требует не более 0,5 сек на ЭВМ БЭСМ-4, что вполне приемлемо.

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

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

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

Существуют прямые методы Леверье, А. Н. Крылова, А. М. Данилевского, Самуэльсона и Ланцоша, позволяющие вычислить все коэффициенты характеристического многочлена произвольной матрицы примерно за арифметических действий. Они экономичней метода интерполяции.

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