Решение систем нелинейных алгебраических уравнений

Общие сведения

Система нелинейных алгебраических уравнений может быть записана в следующем виде:

f₁(x₁,x₂,...,x_n)=0
f₂(x₁,x₂,...,x_n)=0
...
f_n(x₁,x₂,...,x_n)=0

В общем случае система уравнений может вообще не иметь решений, или иметь бесконечное множество решений. На рис. 12.1 приведен пример системы уравнений, имеющих от 0 до 4 решений в зависимости от величины входящего в нее параметра t.

Рис. 12.1. Решения системы уравнений а) t = -2 - решений нет; б) t = -1 - одно решение; в) t = 0 - два решения; г) t = 1 - три решения; д) t = 2 - четыре решения.

Метод итераций

Перепишем заданную систему уравнений в следующем виде: x1=φ1(x1,x2,...,xn) x2=φ2(x1,x2,...,xn)... xn=φn(x1,x2,...,xn) Пусть начальное приближение задано. Подставляя его в правую часть этой системы, получим первое приближение. Повторяя процедуру, находим (k+1) приближение   В некоторых случаях для ускорения сходимости полезно использовать следующую модификацию метода простой итерации

Метод Ньютона

Обозначим вектор начального приближения как   Если разложить функции fi(x1,x2,...,xn) в ряд Тейлора вблизи начального приближения, получим, ограничиваясь первыми двумя членами

где значения производных ∂f_i/∂_j берутся в точке начального приближения. Если матрица Якоби, составленная из этих частных производных, невырождена, полученная система уравнений имеет единственное решение

 

Если разложить функции f_i(x₁,x₂,...,x_n) в ряд Тейлора вблизи найденного решения, можно получить второе приближение. Повторяя описанную выше процедуру, получим систему

 

или, в векторной форме

 

Отсюда вытекает следующая итерационнаяп формула метода Ньютона для решения системы нелинейных уравнений

 

Метод Ньютона обладает квадратичной сходимостью, что позволяет использовать простой практический критерий окончания счета:

 

В методических целях и для ясности изложения полезно расписать приведенную выше общую схему метода Ньютона для частного случая системы из двух нелинейных уравнений:

f₁(x₁,x₂)=0
f₂(x₁,x₂)=0

Тогда, раскаладывая функции f₁(x₁,x₂ и f₂(x₁,x₂ в ряд Ньютона вблизи точки i-того приближения и ограничиваясь в этих разложениях двумя первыми членами, получим:

 

Перепишем эту систему в следующем виде:

 

Легко видеть, что это система из двух линейных алгебраических уравнений относительно неизвестных приращений

 

которая может быть решена, например, методом Гаусса, по формулам Крамера или любым другим известным методом. Тогда очередное, (i+1)-е приближение, найдется из условия:

 

Критерий окончания счета

 

В программе можно использовать, например, следующие обозначения:

Система уравнений
f₁(x₁,x₂)=0
f₂(x₁,x₂)=0
Основные соотношения метода Ньютона:
f₁₁Δx₁ + f₁₂Δx₂ = –f₁
f₂₁Δx₁ + f₂₂Δx₂ = –f₂
где f₁₁,f₁₂,f₂₁,f₂₂ – компоненты матрицы Якоби, f₁,f₂ – значения функции в точке i-того приближения, Δx₁, Δx₂ – приращения аргументов на i-той итерации. Решение полученной в итоге системы двух линейных алгебраических уравнений может быть получено любым известным методом, например, по формулам Крамера:
Δx₁ = –(f₁f₂₂ – f₂f₁₂)/ (f₁₁f₂₂ – f₁₂f₂₁)
Δx₂ = –(f₂f₁₁ – f₁f₂₁)/ (f₁₁f₂₂ – f₁₂f₂₁)
и тогда на очередной итерации x₁=x₁+Δx₁; x₂=x₂+Δx₂

Метод многомерной минимизации

Метод заключается в минимизации функции многих переменных, которую можно составить из заданной системы, например, следующим образом:   Методы минимизации функции многих переменных описаны ниже в разделе 12.4.

Сведение к задаче одномерной минимизации

Если исключить из заданной системы двух уравнений одну из переменных, получим в итоге одно уравнение относительно одной неизвестной, которое можно решать любым методом одномерной минимизации, описанным в разделе 12.3.

Методы одномерной минимизации

Общие сведения

Пусть f(x) - действительная функция одной переменной, определенная на множестве x∈X=(−∞;+∞). Точка x*∈X называется точкой глобального минимума функции f на множестве X, если для всех x∈X выполняется неравенство f(x)≤f(x). Точка x*∈X называется точкой глобального минимума функции f, если существует такая δ-окрестность Uδ этой точки, что для всех x∈Xδ=X∩Uδ выполняется неравенство f(x)≤f(x). Если же для всех x∈Xδ=X∩Uδ (x≠x*) выполняется неравенство f(x)<f(x), то x* называется точкой строгого локального минимума. Если точка x* является внутренней для множества X, то f´(x*)=0. Число x*, удовлетворяющее этому условию, называется стационарной точкой функции f(x). Это условие необходимое, но недостаточное. Для того чтобы точка x* была точкой локального минимума функции f(x), достаточно, чтобы ее вторая производная в этой точке была положительной: f´´(x*)>0. На практике обычно требуется найти точку локального минимума заданной функции, хотя в более широкой постановке требуется найти все точки локального минимума заданной функции f(x) и отвечающие им значения самой функции в этих точках. Предположим, что на некотором отрезке [a,b] заданная функция f(x) имеет только один локальный минимум, причем она строго убывает при x≤x* и строго возрастает при x≥x*. Такие функции называют унимодальными. Точка x* может лежать внутри отрезка [a,b] или же совпадать с одним из его концов.

Оптимальный пассивный поиск