Метод простой итерации для нелинейных уравнений: теорема о сжимающих отображениях

Фундамент итерационной математики

В самых первых статьях нашего цикла мы рассматривали метод дихотомии и метод Ньютона для поиска корней нелинейных уравнений вида f(x) = 0. Метод Ньютона быстр, но требует вычисления производных и часто расходится при плохом выборе начального приближения. Существует еще один, невероятно элегантный и концептуально прозрачный класс алгоритмов — метод простой итерации (или метод последовательных приближений). Его глубокая математическая суть базируется не на геометрии касательных, а на фундаментальных понятиях топологии и функционального анализа.

Чтобы применить этот метод, исходное уравнение f(x) = 0 необходимо алгебраически преобразовать к эквивалентному виду: x = phi(x). Это можно сделать бесконечным числом способов (например, просто прибавив x к обеим частям, или выразив x из сложного логарифма). Теперь наша задача поиска корня превратилась в задачу поиска неподвижной точки отображения phi (fixed point). Неподвижная точка — это такое значение x, которое при подстановке в функцию phi выдает на выходе в точности то же самое значение x. Вычислительный алгоритм становится тривиальным: мы берем начальное случайное приближение x0, вычисляем x1 = phi(x0), затем x2 = phi(x1) и так далее до бесконечности.

Сжимающие отображения и теорема Банаха

Главный вопрос вычислительной математики: при каких условиях эта бесконечная последовательность x_n действительно сойдется к истинному корню, а не улетит в бесконечность и не зациклится? Ответ дает знаменитая теорема Банаха о неподвижной точке (принцип сжимающих отображений), доказанная польским математиком Стефаном Банахом в 1922 году.

Теорема гласит: если функция phi(x) является сжимающим отображением на замкнутом интервале (то есть расстояние между любыми двумя точками после применения функции строго уменьшается с коэффициентом сжатия q < 1), то на этом интервале существует ровно одна неподвижная точка, и метод простой итерации гарантированно сойдется к ней из абсолютно любого начального приближения! С точки зрения дифференциального исчисления, условие сжатия означает, что модуль производной функции phi(x) в окрестности корня должен быть строго меньше единицы. Чем ближе производная к нулю, тем меньше коэффициент сжатия q, и тем феноменально быстрее алгоритм будет сходиться. Если же производная по модулю больше единицы (отображение растягивающее), алгоритм неминуемо разойдется, как бы близко к корню мы ни стартовали. Искусство применения метода простой итерации заключается именно в таком хитром алгебраическом преобразовании f(x) = 0 в x = phi(x), чтобы искусственно сделать производную phi(x) максимально близкой к нулю.