♾️ ТФДП

Принцип сжимающих отображений

Q: Почему в теореме Банаха нужна полнота пространства?

Итерации фундаментальны: расстояния между соседними приближениями тают геометрически, и ряд из них сходится. Но фундаментальность даёт предел лишь в полном пространстве — иначе приближения подбираются к «дырке». Пример: рациональные числа неполны, и итерации $x_{n+1} = \frac{1}{2}(x_n + 2/x_n)$ из $x_0 = 1$ дают $1{,}5$, $1{,}4167$, $1{,}4142$ — подбираются к $\sqrt{2}$, которого среди рациональных чисел нет. Пополнение до действительных чисел всё чинит: предел существует и неподвижен.

Q: Как выбрать константу сжатия и оценить число итераций?

Константа сжатия — оценка сверху производной: для $x = \varphi(x)$ берут $q = \max|\varphi'| < 1$. Чем ближе $q$ к единице, тем вязнут итерации: ошибка делится на $q$ за шаг, и порядок точности при $q = 0{,}99$ стоит около двухсот тридцати шагов, при $q = 0{,}5$ — четыре. Критерий останова апостериорный: до решения не больше $\frac{q}{1-q}\, d(x_n, x_{n-1})$, останавливаются, когда соседние приближения разошлись меньше допуска. Так работают решатели уравнений, итерации Якоби и Зейделя.

англ. Banach fixed-point theorem (contraction principle)

Отображение, укорачивающее все расстояния в q раз (q < 1), на полном пространстве имеет ровно одну неподвижную точку, и итерации приходят к ней из любой точки — с готовой оценкой погрешности.

Итерация — приём древний: подставь приближение в формулу и получи следующее. Когда процесс сходится и к чему? Принцип сжимающих отображений (Банах, 1922) отвечает исчерпывающе. Пусть полное метрическое пространство отображается в себя с условием $d (T x, T y) \leq q d (x, y)$ при постоянном $q < 1$ — расстояния сжимаются, как карта уменьшает территорию. Тогда у отображения ровно одна неподвижная точка $x^{*} = T (x^{*})$ , и последовательность $x_{n + 1} = T (x_{n})$ сходится к ней из любой точки. Доказательство — арифметика геометрической прогрессии: расстояния между соседними приближениями тают как $q^{n}$ , ряд сходится, фундаментальная последовательность в полном пространстве имеет предел, а сжатие переводит предел в неподвижную точку. Рамка принципа — урок метрические пространства, теория с доказательством — в уроке принцип сжимающих отображений.

Скорость сходимости управляется константой $q$ . Возьмём $T (x) = 0, 5 x$ на прямой с обычной метрикой: $q = 0, 5$ , и из $x_{0} = 1$ выходят $x_{1} = 0, 5$ , $x_{2} = 0, 25$ , $x_{3} = 0, 125 = q^{3}$ — расстояние до неподвижной точки $x^{*} = 0$ каждый шаг режется вдвое. Апостериорная оценка гарантирует $∣ x_{n} - x^{*} ∣ \leq \frac{q ^{n}}{1 - q} ∣ x_{1} - x_{0} ∣$ ; здесь $\frac{0 , 5 ^{3}}{0 , 5} \cdot 0, 5 = 0, 125$ — граница достигается точно. Она же отвечает на главный практический вопрос — сколько шагов нужно: для точности $1 0^{- 6}$ требуется $\frac{0 , 5 ^{n}}{0 , 5} \cdot 0, 5 = 0, 5^{n} \leq 1 0^{- 6}$ , то есть $n \geq 20$ , ведь $0, 5^{20} \approx 9, 5 \cdot 1 0^{- 7}$ . На этом стоит метод простой итерации для уравнения $x = φ (x)$ : условие $∣ φ^{'} ∣ \leq q < 1$ превращает уравнение в сжатие, а теорема Пикара тем же приёмом доказывает существование решения задачи Коши.

d (T x, T y) \leq q d (x, y), q < 1, d (x_{n}, x^{*}) \leq \frac{q ^{n}}{1 - q} d (x_{1}, x_{0})

сжатие и априорная оценка погрешности; для

T (x) = 0, 5 x

q = 0, 5

x_{0} = 1

x_{3} = 0, 125 = q^{3}

, оценка даёт

\frac{0 , 5 ^{3}}{0 , 5} \cdot 0, 5 = 0, 125

— совпадает точно; до точности

1 0^{- 6}

хватает

n = 20

(

0, 5^{20} \approx 9, 5 \cdot 1 0^{- 7}

)

Частые вопросы

Почему в теореме Банаха нужна полнота пространства?

Итерации фундаментальны: расстояния между соседними приближениями тают геометрически, и ряд из них сходится. Но фундаментальность даёт предел лишь в полном пространстве — иначе приближения подбираются к «дырке». Пример: рациональные числа неполны, и итерации $x_{n + 1} = \frac{1}{2} (x_{n} + 2/ x_{n})$ из $x_{0} = 1$ дают $1, 5$ , $1, 4167$ , $1, 4142$ — подбираются к $2$ , которого среди рациональных чисел нет. Пополнение до действительных чисел всё чинит: предел существует и неподвижен.

Как выбрать константу сжатия и оценить число итераций?

Константа сжатия — оценка сверху производной: для $x = φ (x)$ берут $q = max ∣ φ^{'} ∣ < 1$ . Чем ближе $q$ к единице, тем вязнут итерации: ошибка делится на $q$ за шаг, и порядок точности при $q = 0, 99$ стоит около двухсот тридцати шагов, при $q = 0, 5$ — четыре. Критерий останова апостериорный: до решения не больше $\frac{q}{1 - q} d (x_{n}, x_{n - 1})$ , останавливаются, когда соседние приближения разошлись меньше допуска. Так работают решатели уравнений, итерации Якоби и Зейделя.