Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
• 9.2. Сжимающие отображения
9.2.1. Определение сжимающего отображения. Рассмотрим линейное «-мерное вещественное пространство Еп\ определим в Еп какую-либо норму ||х|| элемента х = (хг, ..., хп).
Пусть задано, вообще говоря, нелинейное отображение у = ф(х), например, с помощью п функций
71=<Р1(*1> •••>
Д>2 = <Р2(*1> •••> *„)>
Уп = ф„(х1’ -> *»)’
определенное на всем пространстве Еп.
Отображение ф(х) переводит Еп в себя, если для любого элемента х, принадлежащего Еп, элемент у = ф(х) также принадлежит Еп. Например, отображение у — Бтх переводит Е1 в себя, отображение у = у/$тх этим свойством не обладает.
348 X
V.
I
Отображение ф(х), переводящее Еп в себя, называется сжимающим в Еп, если для произвольных двух элементов ххеЕп имеет место неравенство
||ф(*)-ф(*)|| <а||х-*||, (9.2.1)
где коэффициент сжатия а удовлетворяет неравенству
0<ос< 1. (9.2.2)
Например, ф(х) = 0,1 втх—сжимающее отображение в Е1 с нормой ||х||=|х|. Покажем, что ф(х) удовлетворяет (9.2.1), (9.2.2). Действительно,
|ф(х) — ф(х)| = 10,1 ътх—0,1 8тх| =0,1 $тх\.
Но из теоремы о среднем имеем
|8т* —вт*| = |со8^| |х — х|, х <^<х.
Из двух последних соотношений получаем
|ф(х)-ф(*)| <0,1 |х-!|,
т. е. неравенство (9.2.1) с коэффициентом сжатия а = 0,1. Действие сжимающего отображения иллюстрирует рис. 9.6. Для нелинейных функций ф(х) требование, чтобы ф(х) было определено на всем пространстве Еп, оказывается слишком ограничительным. Поэтому отображение ф(х) часто рассматривают локально, только в шаре 5, принадлежащем области определения Б отображения. Шар 5—это совокупность элементов хеЕп таких, что ||х — х°||
5={х: \\х—х° || <г}.
Здесь х°—элемент, Еп—центр шара, г—положительное число — радиус шара (рис. 9.7).
Отображение ф(х) переводит шар 5 в себя, если для любого хеЗ, элемент у = ф(х) также принадлежит шару 5. Например, отображение у = у/ъшх переводит шар |х—я/2|<тс/2 с центром в точке х° = п/2 и радиусом п/2 в себя.
Отображение ф(х), переводящее шар 5 в Еп, называется
сжимающим в ?, если для произвольных двух элементов х, хе5 имеют место неравенства (9.2.1), (9.2.2).
9.2.2. Метод простой итерации. Сжимающие отображения представляют собой замечательный класс отображений, определяющих нелинейные уравнения вида
х = ф(х). (9.2.3)
Для этих уравнений легко ответить на вопрос о существовании
и единственности решения (9.2.3), а также построить последова-
тельность приближений {х(Л)}, сходящихся к решению.
349
Рис. 9.7
Если уравнение имеет вид
/(*)=0, (9.2.4)
то оно предварительно должно быть преобразовано к форме
(9.2.3), причем таким образом, чтобы ф(х) оказалось сжимающим отображением. Общего приема для перехода от (9.2.4) к (9.2.3) не существует, и здесь важен предварительный анализ задачи, например исследбвание линеаризованного уравнения.
Построим последовательность {х{к)} по формуле
*<fc+1) = (p(jc(fc)), к=0, 1, 2, ..., ' (9.2.5)
где х°—начальный элемент, который следует задать. Если последовательность {х{к)} СХОДИТСЯ К X, т. е.
||x(fc)—х || ?“? 0 при к ->оо,
а ф(х)—непрерывное отображение, то, переходя в (9.2.5) к пределу
при к-+ оо, получим, что предел х= lim х{к)—точное решение
к-юо
уравнения (9.2.3). Таким образом, решение нелинейного уравнения
(9.2.3) может быть получено как предел последовательности итераций {x(fc)}.
Приближенное решение (9,2.3) с помощью (9.2.5) называется методом простой итерации.
Сравним (9.2.5) с методом простой интерации в системах линейных уравнений (см. 8.3). Метод простой итерации (9.2.5) является соответствующим методом решения линейных уравнений, если обозначить
Ф [x)=Bx+d,
где В—матрица, х, с1~ векторы соответствующих размерностей. Аналогом достаточного условия сходимости простых итераций в линейном случае (|| В || < 1) оказывается условие сжимаемости (ос < 1) в нелинейных уравнениях. Этот факт устанавливает следующая теорема.
Теорема 9.2^Пусть ф(х) — сжимающее отображение Еп в себя. Тогда существует ' единственное решение уравнения (9.2.3), к которому сходится^поеледовательность {х^}, получаемая методом простой итерации (9.2.5) с любым начальным элементом х(0).
Доказательство. Покажем, что последовательность {х(к)} имеет предел!* Это имеет место, если выполнен критерий Коши
ч/ ||х(»)_х(т)|| -»О при п, т-*0. (9.2.6)
Положим для определенности п>т и оценим ||х(и)—х(т) ||. Имеем (в силу сжимаемости ср)
||Х(">_*(")|= ||ф(х(""1))-ф(х(т"1))|| <ос ||х("_1)—х(т_1) || = = ос ||ф(х(п_2)) —ф(х(т_2))|| <а2 ||х("“2) —х(т_2) || =
V =... ^ост||х(п"т)-х(0)||.
Отсюда следует, что
||х(я)_х(т) || ^ а"1 ||х(и_т)—х(0) ||.
Оценим ||х("Гт)‘— х(0) ||. Имеем следующую цепочку соотношений:
+ х("“т)-х(""т"1)|| ^ ||х(0)-х(1) || + ||х(1)-х(2)||+...+
+ ||х("“т_1) —х(и_т) || < ||х(0) — х(1) || (1+ос + ос2+... +а"“т"1) <
II — х:(1> II
1 —а
Отсюда следует, что
|JC(n)_T.x(m) || .^ ||х(0)_х(1) ||.
1—а
Так как 0<а<1, то при т-уоо получаем .
М|х<")—*(m) II -»О,
т. е. выполняется критерий Коши'(9.2.6), а следовательно, последовательность {*<*>} имеет предел при любом начальном х(0):
'
