ГЛАВА 7. СОБСТВЕННЫЕ ЗНАЧЕНИЯ МАТРИЦ СПЕЦИАЛЬНОГО ВИДА

Введение

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

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

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

(i) алгорифмами для вычисления значений и ее производных,

(ii) процессами получения членов последовательности,

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

Здесь (i) существенно зависит от формы матрицы почти не зависят от нее.

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

Явно заданная полиномиальная форма

2. Самой простой из форм, рассмотренных в главе 6, является форма Фробениуса. Она дает нам либо характеристический полином в чистом виде, либо его факторизацию в два или более полиномов. Коэффициент при старшей степени z равен единице, так что мы рассмотрим вычисление вида

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

Очевидно, что Так как удовлетворяет уравнению

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

Вычисленные значения удовлетворяют соотношениям

где

Объединяя эти результаты, имеем

причем, очевидно,

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

Заметим, однако, что полином с коэффициентами не даст те же самые значения самом деле из (2.4) имеем

что показывает, что полином, дающий все вычисленные имеет коэффициенты, равные

Если изменение от приводит к малому относительному возмущению, то будет того же порядка, что и или меньше при всех Для многих полиномов это далеко не так. Однако если все нули вещественные и имеют один знак, эти условия всегда выполнены для а в окрестности любого нуля. Чтобы доказать это, заметим, что

Из (2.1) имеем

откуда, положив в (2.10) и замечая, что получим

Отсюда видно, что того же знака, что и и не больше его по абсолютной величине. В силу (2.2) это означает, что Следовательно, из (2.9) имеем

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

где

Следовательно, эквивалентное возмущение будет порядка если только не будет

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

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

и можно вычислять первую и вторую производную вместе с самой функцией.

3. Мы иоказали, что во всех случаях вычисленные значения функции удовлетворяют соотношению

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

Если явный полином был получен при помощи приведения матрицы общего вида к форме Фробениуса, то ошибки в коэффициентах, возникающие из-за этого приведения, часто будут значительно больше ошибок, соответствующих (3.2), и фактическое вычисление значений полинома вряд ли будет слабым звеном цепи.

Заметим, что возмущения являются функциями а. Если мы обозначим нули через то

в то время как верное значение равно