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

Мы будем называть эту процедуру симметрическим коротко-шаговым методом со взятием пересечения после каждой компо­ненты (SSIC).

Метод (SSIC) можно выполнять таким образом, что он бу­дет требовать на каждом шаге (за исключением самого пер­вого) того же количества интервальных умножений, что и ме­тод (SIC). В обоих случаях требуется п2 — п умножений (в пред­положении, что диагональные элементы обращаются в 0). При этом используются следующие соображения. Допустим, что для некоторого k>0 известны суммы

Вычисление векторов по методу (SSIC) требует

умножений. Если запоминается п — 1 сумма

то вычислениеизтребует еще умножений. Таким образом, всего для вычисления приближения исходя из нам требуется п2 — п умножений, как и в методе (SIC). Если при вычислении иззапоминаются суммы

то все эти рассуждения проходят для индекса, увеличенного на 1.

Следующее утверждение показывает, что итерационные ме­тоды (TI), (SI), (SIC) и (SSIC) сходятся к неподвижной точ­ке

Теорема 1. Пусть —интервальная матрица и

Если — неподвижная точка уравнения

то итерационные методы (TI), (SI), (SIC) и (SSIC) сходятся к

Доказательство. Докажем теорему для метода (TI). Так как мы берем пересечения, полученная последовательность прибли­жений удовлетворяет условию

В силу следствия 8 из микромодуля 29 эта последовательность сходится к не­которому пределу и этот предел удовлетворяет условию Операция взятия пересечения также непрерывна (если пересечение непусто), поэтому примы имеем

откуда следует, что

Мы рассматриваем полношаговый метод

где Из сказанного следует, что

и вообще

Последовательность вычисленная с помощью рассматриваемого итерационного метода, сходится к в силу тео­ремы 1 из микромодуля 31 . Последнее из доказанных включений дает при соотношение

т. е.Для остальных методов доказательство анало-

гично.

Сравним методы (Т), (S), (TI), (SI), (SIC) и (SSIC) по скорости сходимости для случая, когда итерации на­чинаются с интервального вектора, содержащего неподвижную точку

В первой теореме метод (Т) сравнивается с (TI), а мегод (S) - c (SI).

Теорема 2. Пусть последовательностивы-

числены согласно итерационным методам (Т) и (TI) в предпо­ложении, что Тогда имеет место

Такое же утверждение справедливо для последовательностей, вычисленных согласно итерационным методам (S) и (SI).

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

Для k = 0 это верно ввиду нашего исходного допущения. Используя монотонность включения, получаем

что завершает доказательство по индукции.

Доказательство для методов (S) и (SI) можно провести ана­логичным образом.

Теорема 3. Пусть последовательности вы-

числены согласно итерационным методам (TI) и (SIC) в пред­положении, чтоТогда имеет место

Такое же утверждение справедливо для последовательно­стей, вычисленных согласно итерационным методам (S) и (SIC).

Доказательство. Нам нужно доказать лишь соотношение Мы проведем доказательство для последовательно­стей, вычисленных согласно итерационным методам (TI) и (SIC). Допустим, что для некотороговерно

Для k =0 это верно в силу нашего исходного допущения.

Тогда в обозначениях

мы имеем

Изи монотонности включения следует, что

а потому

Ввидуотсюда следует, что

а ввиду

получаем

Таким же образом мы показываем, что

что завершает доказательство по

индукции. Доказательство для последовательностей, вычислен­ных согласно итерационным методам (SI) и (SIC), можно про­вести аналогичным образом.

Теорема 4. Пусть последовательности вычис-

лены согласно итерационным методам (SIC) и (SSIC) в пред­положении Тогда имеет место

Доказательство. Допустим, что для некоторого k≥0 верно Для k = 0 это верно в силу нашего исходного допущения. Из формул для (SSIC) и первой формулы для (SIC) получаем с помощью математической индукции по ин­дексам компонент, что

С помощью второй формулы для (SSIC) получаем, еще раз применяя индукцию по индексам компонент, что

Сочетание этих включений дает

Используя доказанные выше утверждения, мы можем теперь указать оптимальный метод. Пусть (М) обозначает любой ме­тод из множества