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

жения определенного формулой

то fр имеет нуль в интервале х.

Простое доказательство этого утверждения использует тео­рему Брауэра о неподвижной точке. Действительно, отобра­жает выпуклое компактное множество в себя и поэтому имеет неподвижную точку. Так как не­сингулярно, отображение fр имеет нуль в х.

Замечания. Лемма 10 сформулирована и доказана Алефельдом. Она обобщает утверждение для постоянного дока­занное Муром.

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

Подробности такой проверки описаны в последующих микромодулях,.

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

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

Системы линейных уравнений, поддающиеся методу итерации

Мы предполагаем, что рассматриваемая здесь система ли­нейных уравнений уже имеет вид

(1)

где

Пусть известно, что элементы аij матрицы лежат в ин­тервалах Aij, а компоненты bi вектора b Р лежат в интервалах Вi. Нас интересует множество решений, получающихся, когда входные данные изменяются в данных интервалах. Поэтому мы вводим интервальную матрицу размерности п × п, содержащую интервальные коэффициенты системы, и интерваль­ный вектор содержащий интервальные правые части. Рассмотрим теперь отображение

определяемое формулой

Прежде всего мы имеем следующее утверждение.

Теорема 1. Метод последовательных приближений

(2)

сходится к единственной неподвижной точке х* уравнения

Для любого тогда и только тогда, когда

Доказательство. Покажем, что fР есть -сжатие. Пусть

Применяя (23, микромодуль 29) и (25, микромодуль 29), получаем

Из теоремы 4 микромодуля 30 следует, что условие достаточно для сходимости метода и единственности неподвижной точки. Для доказательства обратного утверждения допустим, что по­следовательные приближения схо­дятся для каждогок неподвижной точке х*. Мы должны показать, что Из теоремы Перрона и Фробениуса следует, что вещественная неотрицательная матрица имеет неотрицательный собственный вектор, соот­ветствующий собственному числу Из сходимости приближений к х* при любом началь­ном векторе следует, что последовательностьсхо­дится к d(x*). Выберем теперьтаким образом, чтобы был собственным вектором, соответствующим собственному числуматрицы , причем хотя бы одна компо­нента вектора d(x(0)) была строго больше, чем соответствующая компонента вектора d(x*). Тогда из (2) следует в силу (12, микромодуль 29) и (18, микромодуль 29), что в предположении верно

Для произвольного k получаем

Переходя к пределу приполучаем

что противоречит выбору x(0). Поэтому верно .

Установим связь этой теоремы с задачей, сформулированной во введении к этому микромодулю. (См. также след­ствие 6, микромодуль 30)

Теорема 2. Пусть — интервальная матрица, такая что Тогда для неподвижной точки х* уравнения (которая существует и единственна в силу теоремы 1) верно со­отношение

Если и неравенство

справедливо для Аij=[i(Аij), s(Аij)], то х* оптимальна в следующем смысле. Не существует интервального век­торатакого, чтоно

Доказательство. Покажем сначала, что система линей­ных уравнений

имеет решение

для Так как верно имеем и из теоремы Перрона и Фробениуса получаем

Отсюда следует, что матрицанесингулярна, что и

требовалось.

Рассмотрим теперь последовательные приближения

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

и для произвольного k

Изследует, что а потому и

Так как х* не зависит от начального вектора, мы получаем пер­вую часть теоремы.

Для доказательства второй части теоремы построим вектор из п нижних границ компонент вектора х*. Из верх­них границ аналогичным образом строится вектор Тогда из следует по правилам интервальной арифметики, что