ПРОГРАММИРОВАНИЕ, 2010, No 2, с. 55-63
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.92+004.94
АЛГОРИТМ ВЫЧИСЛЕНИЯ СТЕПЕННЫХ СУММ КОРНЕЙ ДЛЯ КЛАССА СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ*
© 2010 г. А. А. Кытманов
* Сибирский федеральный университет, 660041 Красноярск, пр. Свободный, 79 E-mail: aakytm@gmail.com Поступила в редакцию 15.06.2009 г.
В настоящей работе приводится алгоритм вычисления степенных сумм корней для класса систем нелинейных неалгебраических уравнений, основанный на многомерных рекуррентных формулах, полученных автором ранее.
ВВЕДЕНИЕ
Рассмотрим систему функций ¡2 (г),...,
/п(^), аналитических в окрестности точки 0 £ € Сп, г = (г\, г2,..., гп), и имеющих вид
¡3 (г) = + (г), 3 = 1,2,...,п, (1)
где в = , в ,...,вП) - мультииндекс с целыми неотрицательными координатами, гв =
= гв ■ гв2 и || = /3{ + + ... + =
= kj, 3 = 1, 2,...,п. Функции Qj разлагаются в окрестности нуля в ряд Тейлора, сходящийся абсолютно и равномерно, вида
Qj (z)= E
(2)
а >0
где а = (ai, а2 ,■■■, an), aj > 0, aj Е Z, а za = zЩ". В дальнейшем будем считать,
= z
а 1
~«2
что степени всех мономов (по совокупности переменных), входящих в Qj, строго больше, чем
kj, j = 1, 2,
,n ( a
= ai + a2 + ... + an > kj).
Рассмотрим циклы j(r) = y(r1,r2, ■ ■■,in), ляющиеся остовами поликругов:
Y(r) = {z Е Cn : |Zs| = rs,s = 1, n}, ri > 0,...,rn > 0^
яв-
* Работа поддержана грантом Президента РФ для ведущих научных школ НШ-2427.2008.1 и грантом программы "Развитие научного потенциала высшей школы" 2.1.1/4620.
При достаточно малых rj циклы 7(г) лежат в области аналитичности функций fj, поэтому ряды
Е кк1
К\ГГ •••Гnn
laii >0
сходятся, j = 1, 2,„,n. Тогда на цикле j(t ■ r) = = Y(t ■ r1,t ■ r2,^^,t ■ rn), t > 0, имеем:
|z|в = tk> ■ rfj ■ rej ■■■rj = tk> ■ rej,
\Qj (z)\ =
E
< tkj+1
||a||>0
E K\ra.
liai >0
< E t^K\ra <
a >0
Поэтому при достаточно малых положительных Ь на цикле 7(í ■ г) выполняются неравенства
, п.
(3)
\гГ > ^(г)|, 3 = 1,2,
Таким образом,
fj (г) = 0 на 7(Ь ■ г), 3 = 1,2,...,п.
В частности, в некоторой достаточно малой окрестности нуля система
fj (z) = 0, j = 1,
,п,
(4)
может иметь корни только на координатных плоскостях {г : г3 = 0}, 8 = 1, 2,...,п (по принципу максимума для аналитических функций).
а
Из (3) следует, что при достаточно малых т^ определены интегралы вида
1
Т(т)
/
¿Л Л ¿/2 /п
/1 ¡2 /п
где 5з € Ъ. Следует отметить, что в случае, когда 5 = в + I, I = (1,1,..., 1), т. е. 5у = вз + 1,
, п, аналогичные ин-
ву > 0, вз € Ъ, 3 = 1, тегралы были рассмотрены в статье [1].
По теореме Коши-Пуанкаре эти интегралы не зависят от (п,..., тп). Обозначим
1
1
=
(2пг)п
7(г)
Sk = + ... + г.
Теорема (Рекуррентные формулы Ньютона). Степенные суммы Sк связаны с коэффициентами З следующими соотношениями:
Sj + Sj-lbl +... + SlЬ.,— 1 + ]Ъз = 0, при 1 < 3 < п, и Sj + Sj-1 Ъ1 + ... + Sj-nbn = 0, при з > п.
Многомерные аналоги для систем полиномиальных уравнений были рассмотрены в [3].
Для формулировки основных результатов работы [4] введем следующие обозначения. Пусть
Если /з - полиномы (т.е. система (4) есть система алгебраических уравнений), то известны формулы для вычисления степенных сумм корней этой системы через коэффициенты /з (см., например, [2]). На этих формулах основан модифицированный метод исключения неизвестных, предложенный Л.А. Айзенбергом в [2] и развитый затем в [3].
В работах [1, 4] описаны классы систем, для которых эти интегралы являются степенными суммами корней (во всем пространстве, за исключением координатных подпространств) в отрицательных степенях. В случае, когда число корней бесконечно, эти суммы являются суммами кратных рядов.
В работе [4] были получены аналоги рекуррентных формул Ньютона для систем уравнений
(4).
Напомним, что рекуррентные формулы Ньютона (в их классическом виде) связывают коэффициенты полинома со степенными суммами его нулей.
Пусть многочлен Р(г) имеет вид
Р (г) = гп + Ъ1гп-1 + ... + Ъп-1г + Ъп.
Через г1,.. . ,гп обозначим его нули (которые, вообще говоря, могут иметь кратность, большую 1). Тогда степенными суммами Sk называются выражения
Дв
в1 ... вп
вп ... вп
Через Да 1 ап обозначим определитель
Да1...ап =
а1
а1
а
= (1еЛ(а1 ...ап),
где аз = (а1,..., ап), 3 = 1,...,п. Напомним, что ^ = 1 = в1 + в2 + ... + в1, 3 = 1, 2,...,п.
Теорема 1. Для системы уравнений (4), где функции /з(г) определены равенствами (1) и (2), справедливы следующие рекуррентные формулы Ньютона:
Яё-р1-...-^ +
+ Е
к1+...+к^<^а1+...+а! ||<||ё||
+ Е аа ...ааДв =
1 з
аа1 . . . аа0 ^ё-а1-...-а1 +
ё=а1+...+а1
= К
У! ... а1 ...П-а Да1...ап х
||а"||>0
Е
{(-1)Р1+1+...+Рп х
\р1+1+...+Рп^||ё||+п-к1-...-к,
х з1 ...япг}/
/{гё+1+^+1(рз+1 + 1)+...+Р"(рп + 1)-а1-...а"
где К - линейный функционал, сопоставляющий многочлену Лорана его свободный член по переменным г1,... ,гп, а р^ > 0, г = 3 + 1, ...,п.
а
г
1
а
а
а
2
г
г
г
1
2
п
ё
г
X
PowerSum := procedure(lst_func, lst-var) if число уравнений = число неизвестных then n := число уравнений else return end if
N := наименьшая из степеней полиномов из lst-func ß = (ß\,... ,ßn) := набор векторов-степеней младших мономов lst-func sum-ß := сумма элементов ß Aß := определитель матрицы из векторов ß K := (Ki,..., Kn), где Kj — сумма элементов ßj k := сумма элементов K index := range_leq(n, 0, k) m := число элементов в index lst-a := пустое множество for i from 1 to m do a[index[i] — sum-ß] := 0
добавить в lst-a элемент a[index[i] — sum-ß] end do
index := range_eq(n, k + 1) m := число элементов в index for i from 1 to m do a[index[i] — sumß] := summa2(lst_func, lst.var, n, index[i], Aß) добавить в lst-a элемент a[index[i] — sum-ß] end do
for j from k + 2 to N + 1 do index := range_eq(n, j) m := число элементов в index for i from 1 to m do
a[index[i] — sum-ß] := summa2(lst_func, lst-var, n, index[i], Aß) —
— summa1 (lstfunc, lst-var, n, index[i], lst-a, k, j) добавить в lst-a элемент a [index [i] — sum-ß] end do end do
index := range_leq(n, 0, N + 1) return a[index] end procedure
Рис. 1.
В работе [4] показано, что отличными от нуля будут только такие суммы
Е
xQ/+i ...Qn'
( — 1)Pj + 1 + ...+Pn X
yS+I+ßj+1(pj+l + 1)+...+ßn(pn+1)-a1-...-an
Следствие 1. Для системы уравнений (4), где функции /(г) определены равенствами (1) и (2), справедливы следующие рекуррентные формулы Ньютона:
aS-ß1-...-ßn +
+ Е
fci + ... + fcn<||a1 + ... + an||<||A|| Xa6 — a1— ...—an +
aa1 . . . aan X
(5)
E
a
al . . .aJ^n (Aß — Aa1.
0.
S=a1+...+an
в которых рз+1 + ...+ рп < \\5\\ + п — к1 — ...- кз, Если функции /з (г) имеют вид /з (г) = 1+ и, следовательно, эти суммы конечны. +Яз (г), 3 = 1, 2,...,п, где Яз (г) определены ра-
/
/
summal := procedure(lst_func, let-var, n, 5, lst.a, k, l) abs.5 := сумма элементов 5 expr := пустое множество a := range_alpha_less(n, k, abs-5) m := число элементов a for i from 1 to m do
добавить в expr элемент sumexpl(lstfunc, lst.var, n, a[i], 5, lst.a, l) end do
slag := сумма элементов expr return slag end procedure
Рис. 2.
sumexpl := procedure(lst_func, lst.var, n, a, 5, lst-a, l) index := range_leq(n, 0, l — 1) for i from 1 to число элементов index do
a[index[i\] := lst.a[i] end do
A := пустое множество for i from 1 to n do
monomial[i] := произведение элементов lst.var, возведенных
в соответствующие степени a[i] a[i] := свободный член выражения f [i]/monomial[i] добавить в A элемент a[i] end do
da := 5 — (сумма элементов a) t := 1
for i from 1 to n do
if da[i] < 0 then t := 0 end if end do
if t = 1 then a-da := a [da] else a-da := 0 end if expr := произведение элементов A, умноженное на a .da return expr end procedure
Рис. 3.
венствами (2), то для них формула (5) запишется в виде
as +
Е
aa1 • • • aan aS—a1 — ...-с
0<ya1+...+any<y
V -
/ j a
S=a1+...+an
a11 • • • aCn ^a1...an =
Цель данной работы состоит в построении алгоритма, реализующего формулу (5), т.е. вычисляющего степенные суммы по заданной системе уравнений (1), (2).
1. ОПИСАНИЕ АЛГОРИТМА
Рассмотрим формулу (5) и опишем процедуру PowerSum, вычисляющую степенные суммы £1 ___рп. Входными данными основной процедуры PowerSum являются набор функций кОипс = } и набор переменных М_уаг = {г 1,...,гп}, от которых зависят заданные функции (см. рис. 1).
Процедура 8итта1 вычисляет выражение
Е
fc1+...+fcn<||a1+...+an||<||
(см. рис. 2).
aa1 •
п' /-т
• • aan aS—a1 — ...-с
n
summa2 := procedure(lst_func, let-var, n, 5, Ар) expr := пустое множество а := range_alpha(n, 5) m := число элементов а for i from 1 to m do
добавить в expr элемент sumexp2(lst_func, lst-var, n, a[i], Ад) end do
slag := сумма элементов expr return slag end procedure
Рис. 4.
sumexp2 := procedure(lst_func, lst.var, n, а, Ад) A := пустое множество for i from 1 to n do
monomial[i] := произведение элементов lst.var, возведенных
в соответствующие степени a[i] a[i] := свободный член выражения f [i]/monomial[i] добавить в A элемент a[i] end do
Аа := определитель матрицы векторов из списка а expr := произведение элементов A, умноженных на (Аа — Ар) return expr end procedure
Рис. 5.
range_alpha := procedure(n, 5)
а := пустое множество A := range_leq_delta(n, 5) m := число элементов A B := perebor(n, m) for i from 1 to число элементов B do C := пустое множество for j from 1 to n do
добавить в C элемент A[B[i][j]] end do
if (сумма элементов C) = 5 then добавить в а элемент C end if end do return а end procedure
Рис. 6.
Процедура sumexpl рекуррентно вычисляет выражение ala1 ...a^n&¿-a1-...-an для заданных а1 ...an и вычисленных ранее &¿-ai-..-а™ (см. рис. 3).
Процедура summa2 вычисляет выражение
Е aa ...^(А«1...«™ - Ар)
5=a1+...+an (см. рис. 4).
Процедура 8ишехр2 вычисляет выражение а1а1 ...а^п(Да1...ап — Ар) для заданных а1 ...ап и в (см. рис. 5).
Процедура гап§е_а1рЬа(п, 5) получает на входе неотрицательное целое число п и вектор 5 длины п и выдает всевозможные комбинации векторов а1,...,ап с неотрицательными координатами, таких, что а1+.. .+ап = 5, где п - длина вектора 5 (см. рис. 6).
range_eq := procedure(n, K)
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.