Возведение матрицы в степень

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

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

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

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

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

Например, в случае требуется 15 шагов возведения в квадрат или около шагов простого степенного процесса для уничтожения компонент по с рабочей точностью. Следовательно, возведение в квадрат более выгодно для матриц приблизительно до 2000-го порядка, причем для матрицы 100-го порядка возведение в квадрат выгоднее почти в 20 раз.

Однако такое сравнение методов несколько сомнительно по двум причинам.

(i) Вряд ли мы станем проводить 28 000 шагов простого степенного процесса без применения каких-либо методов ускорения сходимости, а методы ускорения сходимости трудно применимы в процессе возведения матриц в квадрат.

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