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

т. е. Тепепь нужное соотноше-

ние следует из теоремы 2 приложения А.

В методе (12) интервальные операции не используются. Не­смотря на это, он порождает, подобно методу (9), монотонную последовательность границ для матрицы Был дан также

необходимый и достаточный критерий сходимости, аналогичный критерию для метода (5). Однако применимость метода (12) ограничивается требованием

Для определенных классов матриц можно указать вполне общие начальные значения при которых (12) всегда будет сходиться. Если матрицаудовлетворяет условиям

то является М-матрицсй. Начальные матрицы и такие что

удовлетворяют условиям теоремы 3.

Рассмотрим теперь невырожденную вещественную матрицу размерности п × п, строки которой были перестав­лены, чтобы стало возможным разложение

(15)

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

(16)

Предположим сначала, что— произвольные, но фик-

сированные треугольные матрицы, причем — строго нижняя, а '—верхняя. Тогда мы имеем из (15)

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

получаем тогда

Полагая

получаем тогда соотношения

Выделенные жирным шрифтом выражения происходят из множителя который мы предположили известным. Если

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

Систематическое повторение этой процедуры приводит к сле­дующему итерационному методу:

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

Теорема 4. Пусть матрица имеет разложение

Пусть Если то для всех т≥0 верно

(18)

Мы отметим, что метод (17) может быть выполнен при на­чальных интервалах произвольной, но конечной ширины, если выполнено предположение (16). Единственное деление встре­чается при вычислении Так как мы всегда можем выбрать так, чтобы

Покажем теперь, что метод (17) при отсутствии ошибок округления дает точное треугольное разложение за конечное число шагов.

Теорема 5. В условиях предыдущей теоремы метод (17) вычис­ляет точное разложение матрицыразмерности п×п самое большее за 2п— 1 шагов.

Доказательство. При т = 0 мы получаем из (17) для і=l, что

Это значит, что для произвольных начальных матриц, удов­летворяющих условиям локализации (16), матрицаимеет в первой строке значения, нужные для треугольного разложения. Матрица имеет нужные значения в первой строке точно так же, как . Поэтому для первою столбца матрицы мы получаем из (17) при т= 1, і= 1, что

Поэтому после второго шага итерации нужные значения имеют и первый столбец матрицыи первая строка матрицы Покажем теперь, что если первые i строк матрицы и первые i столбцов матрицыуже имеют нужные значения, то не менее чем і+1 строк матрицы (и i столбцов матрицы имеют нужные значения. Предыдущее рассуждение показывает, что это верно при і = 0. Для і>0 при­меним математическую индукцию.

Заметим прежде всего, что имеют те же элементы, что в первых i строках и столбцах. Таким образом эти элементы все еще имеют нужные значения. Это не­посредственно следует из (17). Из (17) мы получаем также сле­дующее соотношение для (i + 1)-й строки матрицы

Чтобы завершить доказательство по индукции, мы должны показать, что если для некоторого т ≥ 0 первые і строк ма­трицыи первые i—1 столбцов матрицы имеют нуж­ные значения, то имеют нужные значения в первых столб­цах (а — в первых i строках).