Анализ ошибок методов, основанных на элементарных неунитарных преобразованиях

15. Соображения, рассматриваемые в общем анализе, различны в зависимости от того, являются ли матрицы унитарными или неунитарными элементарными матрицами. Мы рассмотрим сначала неунитарный случай.

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

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

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

(iii) Элементы, которые получаются вычислением Определим матрицу соотношением

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

Уравнения (15.1) могут быть скомбинированы так:

где

Если мы определим равенством

то (15.2) дает

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

то (15.2) дает

Это показывает, что точно подобна и, следовательно, мы получили выражение для возмущения в которое эквивалентно ошибкам, сделанным при вычислении. Из (15.3), (15.4) и (15.6) имеем

где

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

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

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

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

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