Численное решение систем нелинейных уравнений: метод простой итерации

Методы вычислительной математики Слайды к видеолекциям для слушателей курса «Методы вычислительной математики» на Национальной платформе открытого образования Доцент Высшей школы искусственного интеллекта СПбПУ Петра Великого, канд. физ.-мат. наук В.Г. Пак Доцент Высшей школы интеллектуальных систем и суперкомпьютерных технологий СПбПУ Петра Великого, канд. физ.-мат. наук Т.Х. Черкасова Методы вычислительной математики Решение нелинейных систем. Метод простой итерации Лекция 13.2 Численное решение систем нелинейных уравнений. Метод простой итерации 2 Решение нелинейных систем. Метод простой итерации 1. Алгоритм метода 1. Алгоритм метода Надо найти приближѐнное решение нелинейной системы 𝐹 𝑥 = 0, 𝑥1 𝑓1 𝑥1 , 𝑥2 , … , 𝑥𝑛 𝑥2 𝑓 𝑥 , 𝑥 , … , 𝑥𝑛 где 𝑥 = ⋮ – вектор неизвестных, 𝐹 𝑥 = 2 1 2 – нелинейная ⋮ 𝑥𝑛 𝑓𝑛 𝑥1 , 𝑥2 , … , 𝑥𝑛 вектор-функция от вектора 𝑥 . Система приводится к эквивалентной 𝑥=𝜑 𝑥 в векторной форме, или в развѐрнутом виде 𝑥1 = 𝜑1 𝑥1 , 𝑥2 , … , 𝑥𝑛 , 𝑥2 = 𝜑2 𝑥1 , 𝑥2 , … , 𝑥𝑛 , ⋮ 𝑥𝑛 = 𝜑n 𝑥1 , 𝑥2 , … , 𝑥𝑛 . Такой переход сам по себе является нетривиальной задачей и требует индивидуального подхода. Очень простой способ - переписать систему как 𝑥 = 𝑥 + 𝐴𝐹 𝑥 , где 𝐴- невырожденная матрица. Тогда 𝜑 𝑥 = 𝑥 + 𝐴𝐹 𝑥 . 3 Решение нелинейных систем. Метод простой итерации 1. Алгоритм метода Итерационный процесс реализуется точно так же, как в одномерном случае. Берѐтся начальная итерация 𝑥 0 из области локализации, подставляется в правую часть уравнения 𝑥 = 𝜑 𝑥 , полученное значение принимается за следующую итерацию 𝑥 1 ; 𝑥 1 опять подставляется в правую часть и т.д. Расчѐтная формула выглядит так: 𝑥 𝑘 = 𝜑 𝑥 𝑘−1 , 𝑘 = 1, 2, … . Если итерационная последовательность 𝑥 𝑘 имеет предел 𝑥 и функция 𝜑 непрерывна области локализации, то этот предел является решением системы. Это доказывается предельным переходом в равенстве 𝑥 𝑘 = = 𝜑 𝑥 𝑘−1 : 𝑥 𝑘 = 𝜑 𝑥 𝑘−1 ⇒ lim 𝑥 𝑘 = lim 𝜑 𝑥 𝑘−1 = = 𝜑 lim 𝑥 𝑘→∞ 𝑘−1 𝑘→∞ 4 𝑘→∞ ⇒ 𝑥 =𝜑 𝑥 . Решение нелинейных систем. Метод простой итерации 2. Сходимость и оценка погрешности 2. Сходимость и оценка погрешности Рассмотрим погрешность итерации 𝑥 𝑘+1 . Записываем расчѐтную формулу для итерации 𝑥 𝑘+1 и уравнение 𝑥 = 𝜑 𝑥 , вычитаем второе из первого: 𝑥 𝑘+1 = 𝜑 𝑥 𝑘 ⇒ 𝑥 𝑘+1 − 𝑥 = 𝜑 𝑥 𝑘 − 𝜑 𝑥 . 𝑥=𝜑 𝑥 Полученное векторное равенство расписываем по компонентно и для разности 𝜑𝑖 𝑥 𝑘 − 𝜑𝑖 𝑥 записываем формулу конечных приращений функции нескольких переменных: 𝑛 𝜕 (𝑘) 𝑘+1 𝑘 𝑘 𝑥𝑖 − 𝑥𝑖 = 𝜑𝑖 𝑥 − 𝜑𝑖 𝑥 = 𝜑𝑖 𝜉 𝑥𝑗 − 𝑥𝑗 , 𝜕𝑥𝑗 𝑗=1 𝑖 = 1, … , 𝑛; 𝜉 𝑘 – некоторая точка на отрезке от 𝑥 5 𝑘 к 𝑥. Решение нелинейных систем. Метод простой итерации 2. Сходимость и оценка погрешности Серию последних 𝑛 равенств запишем в матричной форме: 𝑥 𝑘+1 − 𝑥 = 𝜑′ 𝜉 𝑘 𝑥 𝑘 − 𝑥 , где 𝜕 𝜕 𝜕 𝜑 𝑥 𝜑1 𝑥 𝜑1 𝑥 ⋯ 𝜕𝑥𝑛 1 𝜕𝑥1 𝜕𝑥2 𝜕 𝜕 𝜕 ⋯ 𝜑 𝑥 , 𝜑 𝑥 𝜑 𝑥 𝜑′ 𝑥 = 𝜕𝑥1 2 𝜕𝑥𝑛 2 𝜕𝑥2 2 ⋮ ⋮ ⋮ ⋱ 𝜕 𝜕 𝜕 𝜑 𝑥 𝜑 𝑥 ⋯ 𝜑 𝑥 𝜕𝑥1 𝑛 𝜕𝑥2 𝑛 𝜕𝑥𝑛 𝑛 𝜑′ - функциональная матрица частных производных вектор-функции 𝜑 (Якоби), 𝜑′ 𝜉 𝑘 – матрица Якоби в точке 𝜉 𝑘 . Отсюда следует оценка абсолютной погрешности (k+1)-й итерации: Δ𝑥 𝑘+1 = 𝑥 𝑘+1 − 𝑥 = 𝜑′ ξ 𝑘 𝑥 𝑘 − 𝑥 ≤ 𝜑′ 𝜉 𝑘 ⋅ 𝑥 𝑘 −𝑥 (предполагаем, что применяется согласованная матричная норма, тогда норма произведения матрицы 𝜑′ 𝜉 𝑘 на вектор 𝑥 𝑘 − 𝑥 не превосходит произведения их норм). 6 Решение нелинейных систем. Метод простой итерации 2. Сходимость и оценка погрешности Из оценки Δ𝑥 𝑘+1 можно вывести достаточное условие сходимости. Пусть 𝑀𝑖𝑗 – максимум модуля частной производной 𝜕 𝜑 𝜕𝑥𝑗 𝑖 𝑥 в некоторой замкнутой области 𝐷 пространства ℝ𝑛 , содержащей отрезок, соединяющий точки 𝑥 𝑘 и 𝑥 : 𝜕 𝑀𝑖𝑗 = max 𝜑𝑖 𝑥 . 𝑥∈𝐷 𝜕𝑥𝑗 Составим матрицу 𝑀 из чисел 𝑀𝑖𝑗 : 𝑀11 ⋯ 𝑀1𝑛 ⋮ ⋱ ⋮ . 𝑀= 𝑀𝑛1 ⋯ 𝑀𝑛𝑛 Тогда очевидно, что 𝜑′ 𝜉 𝑘 ≤ 𝑀 и Δ𝑥 𝑘+1 = 𝑥 𝑘+1 − 𝑥 ≤ 𝜑′ 𝜉 𝑘 ⋅ 𝑥 𝑘 −𝑥 ≤ 𝑀 ⋅ 𝑥 𝑘 −𝑥 . Отсюда получаем достаточное условие сходимости. Если 𝑀 ≤ 𝑞 < 1, то в силу последней оценки Δ𝑥 𝑘+1 ≤ 𝑞 𝑥 𝑘 − 𝑥 . 7 Решение нелинейных систем. Метод простой итерации 2. Сходимость и оценка погрешности Последовательно применяем эту оценку: Δ𝑥 𝑘 = 𝑥 𝑘 − 𝑥 ≤ 𝑞 𝑥 𝑘−1 − 𝑥 ≤ ⋯ ≤ 𝑞 𝑘 𝑥 0 − 𝑥 . Приходим к выводу, что Δ𝑥 𝑘 = 𝑥 𝑘 − 𝑥 ≤ 𝑞𝑘 𝑥 0 − 𝑥 . Проверять условие 𝑀 ≤ 𝑞 < 1 можно по любой матричной норме, согласованной с какой-либо векторной. В различных нормах условия сходимости, которые надо проверить для чисел 𝑀𝑖𝑗 , принимают такие формы: 𝑛 𝑀 1 <1 ⇔ 𝑀𝑖𝑗 < 1, 𝑗 = 1, … , 𝑛, 𝑖=1 𝑛 𝑀 ∞ <1 ⇔ 𝑀𝑖𝑗 < 1, 𝑖 = 1, … , 𝑛. 𝑗=1 8