Численное решение систем нелинейных уравнений: локализация решения

Методы вычислительной математики Слайды к видеолекциям для слушателей курса «Методы вычислительной математики» на Национальной платформе открытого образования Доцент Высшей школы искусственного интеллекта СПбПУ Петра Великого, канд. физ.-мат. наук В.Г. Пак Доцент Высшей школы интеллектуальных систем и суперкомпьютерных технологий СПбПУ Петра Великого, канд. физ.-мат. наук Т.Х. Черкасова Методы вычислительной математики Решение нелинейных систем. Метод Ньютона Лекция 13.1 Численное решение систем нелинейных уравнений. Локализация решения. Метод Ньютона 2 Решение нелинейных систем. Метод Ньютона 1. Постановка задачи 1. Постановка задачи Надо решить систему уравнений 𝑓1 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 0, 𝑓2 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 0, ⋮ 𝑓𝑛 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 0, где 𝑓1 , 𝑓2 , … , 𝑓𝑛 – заданные нелинейные функции. Систему можно записать в векторном виде 𝐹 𝑥 = 0, где 𝑥1 𝑓1 𝑥1 , 𝑥2 , … , 𝑥𝑛 𝑥2 𝑓 𝑥 , 𝑥 , … , 𝑥𝑛 𝑥 = ⋮ ,𝐹 𝑥 = 2 1 2 ,0 = 0 , ⋮ ⋮ 𝑥𝑛 𝑓𝑛 𝑥1 , 𝑥2 , … , 𝑥𝑛 𝑥 – вектор неизвестных, 𝐹 – вектор-функция от вектора 𝑥 . Решением системы называется вектор 𝑥 , при подстановке которого в систему она превращается в тождество: 𝐹 𝑥 = 0. Точное решение обозначается 𝑥 , приближённое 𝑥 ∗ : 𝐹 𝑥 ∗ ≈ 0 в пределах заданной точности. Задача состоит в вычислении 𝑥 ∗ . 3 Решение нелинейных систем. Метод Ньютона 2. Локализация решения 2. Локализация решения На предварительном определяется область локализации решения. Она осуществляется исследованием многомерной функции 𝐹 . Область локализации (отделения решения) в данном случае – это область n-мерного векторного пространства. Чаще всего это n-мерный шар 𝑆𝑎 𝑟 векторного пространства ℝ𝑛 с центром в точке 𝑎 радиуса 𝑟: 𝑆𝑎 𝑟 = 𝑥 ∈ ℝ𝑛 𝑥 − 𝑎 ≤ 𝑟 . Или же это n-мерный прямоугольный параллелепипед 𝑃𝑎 𝑑1 ; … ; 𝑑𝑛 с центром в точке 𝑎 размером 2𝑑𝑖 по i-й оси: 𝑃𝑎 𝑑1 ; … ; 𝑑𝑛 = 𝑥 ∈ ℝ𝑛 𝑥𝑖 − 𝑎𝑖 ≤ 𝑑𝑖 , 𝑖 ∈ 1, … , 𝑛 . 4 Решение нелинейных систем. Метод Ньютона 3. Метод Ньютона 3. Метод Ньютона Пусть решение 𝑥 изолировано в некоторой области локализации и в ней имеется приближение 𝑥 (𝑘) к 𝑥 . Разложим функции 𝑓𝑖 в ряды Тейлора в точке 𝑥 в окрестности 𝑥 (𝑘) : 𝑛 𝑓1 𝑥 = 𝑓1 𝑥 𝑘 + 𝑗=1 1 + 2 𝑛 𝑖,𝑗=1 𝜕2 𝑓 𝑥 𝜕𝑥𝑖 𝜕𝑥𝑗 1 𝑘 𝑥𝑖 − 𝑥𝑖 𝑛 𝑓2 𝑥 = 𝑓2 𝑥 𝑘 + 𝑗=1 1 + 2 𝑛 𝑖,𝑗=1 𝜕2 𝑓 𝑥 𝜕𝑥𝑖 𝜕𝑥𝑗 2 𝑘 𝑘 𝑛 + 𝑖,𝑗=1 𝜕2 𝑓 𝑥 𝜕𝑥𝑖 𝜕𝑥𝑗 𝑛 𝑘 𝑘 𝑥𝑗 − 𝑥𝑗 𝑥𝑗 − 𝑥𝑗 𝑘 𝑥𝑗 − 𝑥𝑗 𝑥𝑗 − 𝑥𝑗 𝑘 + +⋯, 𝑘 𝑘 + + ⋯, ⋮ 𝑗=1 1 + 2 𝑘 𝜕 𝑓 𝑥 𝜕𝑥𝑗 2 𝑘 𝑥𝑖 − 𝑥𝑖 𝑛 𝑓𝑛 𝑥 = 𝑓𝑛 𝑥 𝜕 𝑓 𝑥 𝜕𝑥𝑗 1 𝑘 𝜕 𝑓 𝑥 𝜕𝑥𝑗 𝑛 𝑘 𝑥𝑖 − 𝑥𝑖 5 𝑘 𝑥𝑗 − 𝑥𝑗 𝑥𝑗 − 𝑥𝑗 𝑘 𝑘 + + ⋯. Решение нелинейных систем. Метод Ньютона 3. Метод Ньютона Предполагаем, что функции 𝑓𝑖 непрерывно дифференцируемы по всем аргументам в некоторой области, содержащей 𝑥 и 𝑥 (𝑘) . Для вторых частных производных достаточно потребовать их существования в точке 𝑥 (𝑘) . Если 𝑥 и 𝑥 (𝑘) достаточно близки, то эту систему можно линеаризовать: 𝑛 𝜕 𝑘 𝑘 𝑓1 𝑥 ≈ 𝑓1 𝑥 + 𝑓1 𝑥𝑘 𝑥𝑗 − 𝑥𝑗 , 𝜕𝑥𝑗 𝑗=1 𝑛 𝑓2 𝑥 ≈ 𝑓2 𝑥 𝑘 + 𝑗=1 𝑛 𝑓𝑛 𝑥 ≈ 𝑓𝑛 𝑥 𝑘 𝜕 𝑓2 𝑥𝑘 𝜕𝑥𝑗 𝑥𝑗 − 𝑥𝑗 𝑘 , 𝑥𝑗 − 𝑥𝑗 𝑘 . ⋮ + 𝑗=1 𝜕 𝑓𝑛 𝑥𝑘 𝜕𝑥𝑗 Поскольку 𝑓𝑖 𝑥 = 0 (𝑥 – точное решение системы), то: 6 Решение нелинейных систем. Метод Ньютона 3. Метод Ньютона 𝑛 𝑓1 𝑥 𝑘 + 𝑗=1 𝑛 𝑓2 𝑥 𝑘 + 𝑗=1 𝑛 𝑓𝑛 𝑥 𝑘 + 𝑗=1 𝜕 𝑓 𝑥 𝜕𝑥𝑗 1 𝑘 𝑥𝑗 − 𝑥𝑗 𝑘 = 0, 𝜕 𝑓 𝑥 𝜕𝑥𝑗 2 𝑘 𝑥𝑗 − 𝑥𝑗 𝑘 = 0, 𝑥𝑗 − 𝑥𝑗 𝑘 = 0. ⋮ 𝜕 𝑓 𝑥 𝜕𝑥𝑗 𝑛 𝑘 Получили систему уравнений для нахождения компонент 𝑥𝑗 точного вектора решения 𝑥 . В матричной форме она имеет вид 𝐹 𝑥 (𝑘) + 𝐹 ′ 𝑥 𝑘 𝑥 − 𝑥 𝑘 = 0, 𝜕 𝜕 𝜕 𝑓 𝑥 𝑓 𝑥 𝑓 𝑥 ⋯ 𝜕𝑥𝑛 1 𝜕𝑥1 1 𝜕𝑥2 1 𝜕 𝜕 𝜕 𝐹 ′ 𝑥 = 𝜕𝑥1 𝑓2 𝑥 𝜕𝑥2 𝑓2 𝑥 ⋯ 𝜕𝑥𝑛 𝑓2 𝑥 . ⋮ ⋮ ⋮ ⋱ 𝜕 𝜕 𝜕 𝑓 𝑥 𝑓 𝑥 ⋯ 𝑓 𝑥 𝜕𝑥1 𝑛 𝜕𝑥2 𝑛 𝜕𝑥𝑛 𝑛 7 Решение нелинейных систем. Метод Ньютона 3. Метод Ньютона Здесь 𝐹 ′ - функциональная матрица частных производных вектор-функции 𝐹 , которая называется матрицей Якоби, 𝐹 ′ 𝑥 𝑘 – матрица Якоби в точке 𝑥 𝑘 . Решая эту систему относительно 𝑥 , получаем этот вектор: 𝑥−𝑥 𝑘 = − 𝐹′ 𝑥 𝑘 −1 ⋅𝐹 𝑥 𝑘 ⇒ 𝑥≈𝑥 𝑘 − 𝐹′ 𝑥 −1 𝑘 ∙𝐹 𝑥 𝑘 ⇒ −1 ⇒ 𝑥 (𝑘+1) = 𝑥 𝑘 − 𝐹 ′ 𝑥 𝑘 ∙𝐹 𝑥 𝑘 . Тут мы вспоминаем, что вычислили 𝑥 на самом деле приближѐнно, и этот вектор принимаем за следующее приближение к корню 𝑥 (𝑘+1) . Итак, получили расчѐтную формулу метода Ньютона 𝑥 (𝑘+1) = 𝑥 𝑘 − 𝐹′ 𝑥 𝑘 −1 ∙𝐹 𝑥 𝑘 , 𝑘 = 0, 1, 2, … . Для уменьшения трудоѐмкости метода можно не считать 𝑥 (𝑘+1) по явной формуле, а решать на каждом шаге систему линейных уравнений. Обозначим 𝑦 (𝑘) = 𝑥 (𝑘+1) − 𝑥 𝑘 . Вектор 𝑦 (𝑘) находится как решение линейной системы 𝐹 ′ 𝑥 𝑘 𝑦 (𝑘) = −𝐹 𝑥 𝑘 . Новая итерация 𝑥 (𝑘+1) тогда равна 𝑥 (𝑘+1) = 𝑦 (𝑘) + 𝑥 𝑘 , 𝑘 = 0, 1, 2, … . 8 Решение нелинейных систем. Метод Ньютона 4. Упрощѐнный метод Ньютона 3. Упрощѐнный метод Ньютона Вычисления можно немного упростить, используя на каждом шаге одну и ту же матрицу Якоби. Это значит, что она вычисляется один раз в начале для итерации 𝑥 0 и подставляется в расчѐтную формулу на каждом шаге. Это и есть упрощѐнный метод Ньютона. Его расчѐтная формула: 𝑥 (𝑘+1) = 𝑥 𝑘 − 𝐹0′ ∙ 𝐹 𝑥 𝑘 , 𝐹0′ 𝐹′ −1 𝑘 = 0, 1, 2, … , где = 𝑥 . Можно вычислять 𝑥 (𝑘+1) неявно, решая систему уравнений 𝐴𝑦 (𝑘) = −𝐹 𝑥 𝑘 , где 𝐴 = 𝐹 ′ 𝑥 0 , 𝑦 (𝑘) = 𝑥 (𝑘+1) − 𝑥 𝑘 , 𝑘 = 0, 1, 2, … . Новая итерация 𝑥 (𝑘+1) равна 𝑥 (𝑘+1) = 𝑦 (𝑘) + 𝑥 𝑘 . 9 Решение нелинейных систем. Метод Ньютона 5. Сходимость и оценка погрешности 5. Сходимость и оценка погрешности Теорема 1. Пусть в некоторой окрестности решения 𝑥 системы функции 𝑓𝑖 (𝑖 = = 1, … , 𝑛) дважды непрерывно дифференцируемы по всем аргументам и матрица Якоби 𝐹 ′ не вырождена. Тогда найдѐтся такая малая -окрестность решения 𝑥 , что при произвольном выборе начального приближения 𝑥 0 в ней итерационная последовательность метода Ньютона не выходит за пределы этой окрестности, сходится к 𝑥 и верна оценка 1 2 𝑘+1 𝑘+1 𝑘 ∆𝑥 = 𝑥 −𝑥 ≤ 𝑥 −𝑥 , 𝛿 𝑘 = 0, 1, 2, … . Из теоремы следует важный вывод: метод Ньютона имеет квадратичную скорость сходимости. Это позволяет использовать простой критерий останова итерационного процесса: 𝑥 𝑘 − 𝑥 𝑘−1 < 𝜀 , где 𝜀 > 0 – заданная точность. Упрощѐнный метод Ньютона сходится со скоростью геометрической прогрессии, если начальное приближение 𝑥 0 достаточно близко к решению 𝑥 . В качестве критерия останова можно взять выполнение неравенств (𝑘) (𝑘−1) 𝑥𝑖 − 𝑥𝑖 𝑖 = 1, … , 𝑛, 𝜀 > 0 – заданная точность. 10 < 𝜀,