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

Рассмотрим систему линейных уравнений

где — вещественная точечная матрица и — вещественный точечный вектор. Мы вводим естественный (т. е. покомпонент­ный) порядок на точечных матрицах и точечных векторах. То­чечная матрица называется изотонной (соответственно анти­тонной), если из следует (соответственно ор). Теперь матрица раскладывается в сумму изотонной и антитонной точечных матриц:

Начиная с пары точечных векторов для которых вернонаш итерационный метод вычисляет две

последовательностипо формулам

(1)

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

Поэтому последовательности сходятся,

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

Рассматривая вместе с методом итераций для

и также итерационный метод

(2)

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

с компонентами последовательностей

Сказанное только что об итерационном методе (2) показы­вает, что в методе (1) можно избавиться от предположения если выполнено условие

которое гарантирует локализацию решения Последователь­ности в этом случае уже не обязательно сходятся монотонно. Монотонность можно восстановить, если брать пересечение после каждого шага.

Замечания. Утверждения, аналогичные тем, которые мы дока­зали для метода релаксации, справедливы и для симметриче­ского метода релаксации (SR)

который при ω = 1 сводится к симметрическому короткошаговому методу (SS), описанному в микромодуле 31. Необходимым и доста­точным условием сходимости этого метода к единственной не­подвижной точке при произвольном начальном интервальном векторе является

Если то предыдущее условие выполняется при

Доказательство можно провести так же, как для метода ре­лаксации.

Если — точечная матрица, то по аналогии с рассужде­нием из теоремы 2 можно показать, что асимптотический фак­тор сходимости, введенный в определении 1, равен

и по аналогии с теоремой 3 имеем

для

Покажем, что имеет место Матрица

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

где λ — спектральный радиус матрицы из левой части и вектор имеет только положительные компоненты. Простое преобра­зование (корректное при и достаточно малой дает

Окончательно получаем

Это неравенство верно и при Х = 0. Применяя теперь известную теорему, получаем, что спектральный радиус матрицы из левой части не превосходит λ. Так как это верно для всех мат­риц делающих матрицу не­приводимой, то мы получаем нужное утверждение, устремляя к нулю, так как собственные числа непрерывно зависят от элементов матрицы.

Микромодуль 33

Оптимальность симметрического короткошагового метода со взятием пересечения на каждом шаге

В этом микромодуле предполагается, что все интервальные матрицы взяты из пространства а все интервальные векторы — из .

Мы собираемся теперь исследовать некоторые модификации полношагового, короткошагового и симметрического корочкошагового методов. Если полношаговый метод

имеет начальный вектор для которого то из монотонности включенияследует, что

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

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

Если провести те же рассмотрения для короткошагового ме­тода, то получится итерационная процедура

которую мы назовем короткошаговым методом со взятием пере­сечения на каждом шаге (SI).

В случае короткошагового метода имеется еще одна воз­можность:

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

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