ГЛАВА 7. ЧИСЛЕННОЕ РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Задача нахождения некоторых или всех решений системы из n нелинейных алгебраических или трансцендентных уравнений с n неизвестными

f 1(x1,...,xn)=0
f 2(x1,...,xn)=0	(7.1)
..........

f (x ,...,x )=0

n 1 n

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

градиент этой функции равен нулю. Полагая F = grad G, получаем нелинейную систему.

Векторная запись нелинейных систем. Введем векторные обозначения:

x1

f 1(x)

f 1(x1,...,xn)

r

=

...

,

r

........

=

.................

x

F(x) =

fn(x1,...,xn)

xn

fn(xr)

где f 1,.., fn - заданные, в общем случае, нелинейные вещественные функции n переменных (x1,x2,...,xn ) и запишем систему уравнений в виде

	F(x) =0
относительно векторной функции F		векторного аргумента xr. Таким
образом, исходная задача может быть		рассмотрена как задача о нулях
нелинейного отображения	F:Rn→Rn .	Фактически это та же задача,
которую рассматривали в	предыдущей	главе, только в пространствах

большей размерности и для ее решения применяются итерационные методы. Например, итерационный процесс, где компоненты приближений определяются из соотношений

154

f 1(x1k +1, x2k,..., xnk ) = 0

f

2

x

k +1

x

k

+1

x

k

1

,

2

,...,

n) = 0

(

....................................

1k +1,

2k +1,...,

nk +1) =

f

n

(

x

x

x

0

является	аналогом		метода Зейделя	в	случае	системы	нелинейных
уравнений.	Нахождение каждого нового значения xik +1 требует в общем
случае решения нелинейного уравнения
			f i(x1k +1, xik−+11, xik +1, xik+1..., xnk ) = 0
с одним неизвестным.
Рассмотрим семейство итерационных методов с матричными
параметрами		Ak .	Пусть (Ak) -	некоторая		последовательность
невырожденных		вещественных матриц			n ×n .	Тогда,	очевидно,
последовательность задач				k =0,1,...
			xr= xr− AkF(xr) ,

имеет те же решения, что и исходное уравнение (7.1), и для приближенного нахождения этих решений можно формально записать итерационный процесс

xr(k +1) = xr(k ) − AkF(xr(k ) )

k =0,1,... .

(7.2)

Эта формула определяет большое семейство итерационных методов. В случае Ak ≡A получают метод простых итераций с линейной сходимостью

r(k )

) .

Если

A

k

=

′

r(k)

)

−1

последовательности (x

F (x

, получим метод

Ньютона (7.7).

7.1. Метод простой итерации

Преобразуем систему уравнений к виду

x1=ϕ1(x1,...,xn)

=ϕ2(x1,...,xn)

x2

......................

(7.3)

n

=ϕ

n

1

n

)

x

(x ,...,x

или иначе, в компактной записи,

x =Φ(xr) ,

(7.4)

где

155

Тогда:

ϕ1(x)

Φ(xr) = ϕ2(xr)M

ϕn(xr)

		ϕ1(x1,...,xn)
		ϕ2(x1,...,xn)
	=		.
	M
		ϕn(x1,...,xn)

Это можно сделать, например, умножив (7.1) на некоторуюr невырожденную

матрицу −A и прибавив затем к тождеству x = x . Получится система x = xr− AF(xr)

эквивалентная исходной, где Φ(x) = xr− AF(xr) . Проблема теперь состоит лишь в подборе матричного параметра A такого, при котором Φ(x)

обладала бы нужными свойствами.

Задача о решении системы нелинейных уравнений в записи (7.4) – это задача о неподвижной точке нелинейного отображения Φ: Rn → Rn .

Запишем рекуррентное равенство r

x(k +1) =Φ(x(k ) ) ,

которое определяет метод простых итераций (или метод последовательных приближений). Если начать процесс построения последовательности (x(k ) ) с некоторого вектора xr(0) =(x1(0) ,..., xn(0) )T и продолжить по формуле

xik +1 =ϕi(x1k,..., xnk), i=1,...,n ,

(7.5)

то при определенных условиях эта последовательность со скоростью геометрической прогрессии будет приближаться к вектору x* - неподвижной точке отображения Φ(x) .

Справедлива следующая теорема:

Теорема: Пусть функция Φ(x) и замкнутое множество M D(Φ) Rn

таковы, что

1. Φ(xr) M xr M ;

2. q <1 : || Φ(xr) −Φ(xr*) ||≤q || xr−xr* ||.

- Φ(xr) имеет в M единственную неподвижную точку xr*;

- последовательность (xr(k ) ) , определяемая методом простых итераций

(7.5) сходится к этой точке; - справедливы следующие оценки:

156

в ряд Тейлора:

J (xrk )

|| xr* −xr(k ) ||≤

q

|| xr(k ) −xr(k −1) ||≤

qk

|| xr(1)

−xr(0) ||

k .

1−q

1−q

Можно вместо (7.5) компоненты приближений xik +1определять из

соотношений

x1(k +1) =ϕ1(x1(k ) ,...,xn(k ) )

(k+1)

(k +1)

(k )

)

x2

=ϕ2(x1

,...,xn

(7.6)

...................................

(k +1)

(k +1)

,...,xn −1

(k+1)

,xn

(k )

)

xn

=ϕn(x1

Этот метод также является аналогом метода Зейделя и наряду с (7.5) широко используется на практике, так как они требуют малого объема памяти и просты в реализации.

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

Основная идея метода Ньютона состоит в выделении из уравнений линейных частей, которые являются главными при малых приращениях аргументов. Это позволяет свести исходную задачу к решению последовательности линейных систем.

Метод Ньютона для n уравнений применим толькоrтогда, когда могут быть вычислены все частные производные функций fi(x) по переменным

	x j . Пусть		обозначает матрицу Якоби и
	значение производной в точке xrk :							∂f 1(xrk )
							∂f 1(xrk )
							∂x1	∂x2
	r	k	′	r	k
	J (x		) = F (x			) = ......		......
							r	r
							∂fn(xk )	∂fn(xk )
							∂x1	∂x2

ее (i, j)-й элемент есть

...	∂f 1(xrk )
	∂xn
...
	......
	r
...	∂fn(xk )
	∂xn

Как и в одномерном случае (n = 1), метод Ньютонаr начинается с

произвольного xr , обозначенного xr0 . Разложим F(x)

F(xr) = F(xr0 ) +F′(xr0 )(xr−xr0 ) +...

и, учитывая лишьr первые члены, получим линейное приближение к уравнению F(x) =0:

157

0

′

r0

r

r0

−x ) =0

F(x ) +F (x )(x

Естественно записать решение в форме

r

r0

′

r0

−1

r0

F(x ),

x = x −F (x )

сильно напоминающей

одномерную

формулу метода

Ньютона. Здесь

F′(xr0)−1 - матрица, обратная матрице Якоби J (x0 ) .

В общем случае, имея xk , можно найти xk +1 по явной формуле метода

Ньютона:

−1

r(k +1)

r(k )

′

r(k )

r(k )

) .

x

= x

− F (x

)

F(x

(7.7)

Новым, по сравнению со скалярным случаем, фактором, осложняющим применение метода Ньютона к решению n - мерной системы, является

необходимость обращения матриц J (xk ) на каждой итерации.

Однако, вычисление обратной матрицы F′(x0)−1 не является необходимым.

Этого можно избежать, если формулу (7.7), требующую обращения матриц на каждой итерации, переписать в неявном виде:

′ r(k )	r(k +1)	r(k )	r(k )	)	(7.8)
F (x	)(x	−x	)=−F(x

Применение метода Ньютона в форме (7.8)r

прибавлением к xrk векторной поправки r(k ) = x

решения линейной алгебраической системы

F′(xr(k ) )rr(k ) =−F(xr(k ) ), т.е. xr(k +1) = xr(k ) +rr(k ) .

позволяет найти xk +1
(k +1)	−xr(k ) , полученной из
	(7.9)
	(7.10)

.

К решению таких линейных систем (7.9) можно привлекать самые разные методы как прямые, так и итерационные в зависимости от размерности n решаемой задачи и особенностей матрицы Якоби.

Сходимость итерационного процесса (7.10) доказывается теоремой, смысл которой сводится к следующему.

Пусть xr* - решение системы F(x) =0 такое, при котором матрица Якоби J (xr*) не вырождена и вторые частные производные функции F(x)

непрерывны вблизи xr*. Тогда, если x0 достаточно близко к xr*, то

итерации по методу Ньютона сходятся. Более того, для er(k ) = xr* −xr(k ) отношение

158

e ( k +1)

er( k ) 2

второго порядка.

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

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

Если матрицу Якоби			′			вычислить и обратить лишь один раз –
		F (x)
для начального приближения					x(0) ,		и использовать на последующих
итерациях, то получим модифицированный метод Ньютона:
r(k+1)	r(k )		−			r(0)	−1	r(k )	)
x	= x			F (x			)	F(x		(7.11)
					′

Этот метод требует значительно меньших вычислительных затрат на один итерационный шаг, но итераций при этом может потребоваться значительно больше для достижения заданной точности.

159