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

-maxlbaui].

\ ~ k, I

Здесь через обозначен так называемый t-й коэффициент перекоса матрицы

Van, Xj) (yt, yi) 1 (Xi, yi) cos cpi

где (pi есть угол между соответствующими векторами данной матрицы и эрмитово сопряженной к ней.

Заметим, что для эрмитовой матрицы все коэффициенты перекоса равны единице, поскольку соответствующие векторы ортогональны. А для типичной жордановой клетки

Л=--

а Г

л:, =

выполняется условие (Xi, yi) = 0, т. е. коэффициент перекоса обращается в бесконечность. Очевидно, что для любых матриц I >£; I 1 •

Выводы из оценки (7) можно сформулировать следующим образом. Собственное значение устойчиво относительно вариации матричных элементов, если соответствующий ему коэффициент перекоса мал; если этот коэффициент перекоса очень велик, то устойчивость может быть плохой. Собственный вектор устойчив по матричным элементам, если все коэффициенты перекоса матрицы невелики, а данное собственное значение - простое.

Значит, все собственные значения эрмитовых матриц мало чувствительнык погрешностям матричных элементов. А собственные значения жордановых подматриц могут бЬ!ть очень чувствительны к погрешностям. Проиллюстрируем последнее на примере неэрмитовой матрицы 20-го порядка:

20 20 О О ... 0 0" О 19 20 О ... 0 0 О О 18 20 ... 0 0

2 20

где через е обозначено малое возмущение нулевого углового элемента. Характеристическое уравнение этой матрицы имеет вид

det (Л-kE) = ]J (k-X)-20"е = 0. (10)

При 6 = 0 младший коэффициент характеристического многочлена есть Оо = 20! 2,5х 10*, а наименьшее по модулю собственное значение Я2о=1- Если же положить е = 20ix20! я«5х 10", то коэффициент щ обращается в нуль, а тогда >V3(, = 0. Таким образом, и коэффициенты и сами корни характеристического многочлена могут быть очень чувствительны к малым погрешностям матричных элементов, что означает слабую устойчивость задачи. Это согласуется со сделанным в § 2 главы V замечанием о том, что корни многочлена высокой степени нередко чувствительны к погрешностям коэффициентов.

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

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

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

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

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

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

Если известны границы, в которых расположены собственные значения, то целесообразно размещать узлы интерполяции Я*** в этих границах, причем лриблизительно равномерно. Это уменьшает ошибки округления, возникающие при нахождении разделенных разностей в формуле Ньютона, т. е. улучшает устойчивость алгоритма. Для определения границ спектра можно воспользоваться оценкой \Ki I II Л II, справедливой для любой нормы матрицы (это следует из того, что спектральная норма Л Ц; = = max\ki\ есть наименьшая из норм матрицы). Хотя эта оценка в среднем завышена, но она достаточно разумна для тех матриц, с которыми приходится встречаться на практике, и тех норм (см. § 2 главы I), которые просто вычисляются.

Метод интерполяции прост и применим для матриц произвольной структуры, а также для более сложных проблем. Например, общую задачу det [р,- (А)] = 0, где каждый элемент матрицы есть некоторый многочлен от Я, решают практически только этим методом; разумеется, число узлов по Я выбирают в соответствии со степенью результирующего многочлена. Лишь в частном случае этой задачи - так называемой обобщенной проблемы собственных значений det(Л-ЯВ) = 0, разработаны более экономичные методы.

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

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

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