Дискретно-непрерывная математика (стр. 116 )

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

для элементов матрицы Для матрицы с элемен-

тами

имеем. Поэтому итерационный метод

(5) сходится к в силу теоремы 1. Если теперь неравенство (11) выполняется после некоторого шага итерации, то процесс можно продолжать дальше по формулам (9).

При практическом выполнении алгоритма (5) встречающиеся выражения вычисляются по аналогии со схемой Горнера.

Это дает формулу

(5′)

где

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

Даже при одной и той же начальной матрице формулы (5) и (5') порождают в общем случае разные последовательности. Однако теорема 1 все же верна и для итераций (5'). Рассмотрим теперь объем вычислений, нужных на каждом шаге (5').

Если— матрица размерности п × п, то (5') требует на каждом шаге

Даже те члены в (5'), которые, как не содержат ничего интервального, приходится вычислять в интервальной ариф­метике, чтобы обеспечить локализацию матрицы Если пре­небречь более низкими степенями п, то мы увидим, что объем вычислений по алгоритму (5') пропорционален r.

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

меньшей, чем заранее предписанная погрешность.

Так же, как в доказательстве теоремы 1, мы получаем для (5') следующее соотношение:

т. е.

Если по-прежнему мы используем монотонную и мультипли­кативную матричную норму и допустим, что то получим, что

Это выражение позволяет нам оценить при сделанных предположениях

Исходя из соотношения

мы определим, при каком значении r итерационный метод тре­бует наименьшего объема вычислений для достижения заданной точности для Согласно предшествующим рассуждениям, этот объем вычислений можно считать пропорциональным величине r. Пусть теперь даны r(1)>1 и r(2)>1, причем r(1)≠r(2). После р(1) (соответственно р(2)) шагов итерации (5') со значением r = r(1) (соответственно r = r(2)) при одном и том же начальном значении мы выполним один и тот же объем вычислений. Иными словами, имеем

Точность, достигнутую при использовании этих методов, можно оценить величиной (соответственно—1).

Мы требуем от «оптимальной» итерационной процедуры r = r(1) чтобы для всех других значений r(2) и количества шагов мы имели бы

что ввиду эквивалентно неравенству

Так как функциядля начальных x имеет максимум при x=3, получаем, что итерация (5') оптимальна в описанном смысле при этом значении.

Заметим еще, что метод (5) можно применять и для комп­лексных матриц, используя арифметику в При этом будет верна теорема 1. Мы упомянем в этой связи более общие исследования. Рассмотрим теперь методы монотонной локализации обратной матрицы, обладающие свойствами, по­хожими на свойства метода (9). Основные вычисления в них вообще не используют интервальной арифметики. Верхняя и нижняя границы вычисляются по отдельным формулам. Этот метод, однако, применим лишь в случае, когда

Итак, пусть —невырожденная матрица и r≥ 2 — нату­ральное число. Рассмотрим итерационную процедуру

(12)

с заданными

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

Теорема 3. Пусть — невырожденная матрица размерности

n×n, причем Пусть далее — две матрицы

размерности п × п, для которых верно

Пусть последовательности вычислены по

формулам (12). Тогда верны следующие утверждения:

(13)

(7') Обе последовательности

сходятся к тогда и только тогда, когда спектральный радиус меньше 1.

Если процедура сходится, то величины

удовлетворяют соотношению (14)

Поэтому, если понимать (12) как метод итераций для вычис­ления интервальных матрицто верно

(см. приложение А, теорема 2).

Доказательство. (13): Докажем соотношение

математической индукцией по k ≥ 0. Эти неравенства выпол­нены для k = 0 по условию теоремы. Из

следует, что

т. е

Из

и

следует, что

Ввиду получаем

(7'): Используя соотношения

установленные при доказательстве неравенства (13), можем показать по индукции, что

откуда и следует нужное утверждение.

(14): Снова используя соотношения, установленные при дока­зательстве (13), получаем

С помощью монотонной матричной нормы эту оценку можно продолжить следующим образом: