Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры
У роботi побудовано алгебраїчний алгоритм для обчислення в системах комп’ютерної алгебри алгебраїчного многочлену yn порядку n e N. Цей многочлен – апроксимацiя розв’язку y = y(x), x e [a,b] iнтегрального рiвняння Гаммерштейна. Ця апроксимацiя оптимальна в просторi C[a,b]. We constructed the algeb...
Saved in:
| Date: | 2009 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/7848 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 1. — С. 149-157. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859642494680039424 |
|---|---|
| author | Денисенко, П.Н. |
| author_facet | Денисенко, П.Н. |
| citation_txt | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 1. — С. 149-157. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| description | У роботi побудовано алгебраїчний алгоритм для обчислення в системах комп’ютерної алгебри алгебраїчного
многочлену yn порядку n e N. Цей многочлен – апроксимацiя розв’язку y = y(x), x e [a,b]
iнтегрального рiвняння Гаммерштейна. Ця апроксимацiя оптимальна в просторi C[a,b].
We constructed the algebraic algorithm for computing in the computer algebra systems the algebraic polynomial yn of
order n e N. This polynomial is the optimal approximation for the Hammerstein integral equation solution
y = y(x), x e [a,b] in C[a,b].
В работе построен алгебраический алгоритм для вычисления алгебраического многочлена yn порядка
n e N в системах компьютерной алгебры. Этот многочлен аппроксимирует решение y=y(x), x e [a,b]
интегрального уравнения Гаммерштейна. Эта аппроксимация оптимальна в пространстве C[a,b].
|
| first_indexed | 2025-12-07T13:23:02Z |
| format | Article |
| fulltext |
«Штучний інтелект» 1’2009 149
4Д
УДК 681.142.2/518.3
П.Н. Денисенко
Кибернетико-технический колледж, Учебно-научный комплекс, КННПК, г. Кировоград,
Украина
pnden_osvita@yahoo.com
Оптимальный алгоритм для решения
интегральных уравнений Гаммерштейна
в системах компьютерной алгебры
В работе построен алгебраический алгоритм для вычисления алгебраического многочлена yn порядка
n N в системах компьютерной алгебры. Этот многочлен аппроксимирует решение y(x), x [a,b]
интегрального уравнения Гаммерштейна. Эта аппроксимация оптимальна в пространстве C[a,b].
Актуальность темы исследования. Обыкновенные дифференциальные и инте-
гральные уравнения являются классическим аппаратом математического моделирова-
ния [1]. Уравнения Гаммерштейна вида
L[y] + g = H[f(y)], L , H : polynomial polynomial , g polynomial (1)
используют в математических моделях более часто, чем интегральные уравнения дру-
гих типов. Maple, Mathematica, Mathcad, Matlab, APS и другие компьютерные системы
стали естественной средой математического моделирования. Эти системы выполняют
символьные (аналитические) преобразования композиции специальных математических
функций и решают обыкновенные дифференциальные уравнения, являются система-
ми компьютерной алгебры (СКА).
Задача работы. Построить алгебраический алгоритм для вычисления в СКА
алгебраического многочлена yn порядка n N. Этот многочлен аппроксимирует
решение y = y(x), x [a,b] интегрального уравнения Гаммерштейна вида (1). Эта
аппроксимация оптимальна в пространстве C[a,b], в этом пространстве ограничен
коэффициент оптимальности алгоритма
Cn( algorithm, (1), C[a,b] ) = || y – yn ||C[a,b] / infc_0,…,c_n || y(x) – (c0 +…+ cn xn) ||C[a,b].
Актуальность задачи. СКА не решают интегральные уравнения вида (1).
1. Алгоритм 1
Вход. Уравнение (1) – task (1), отрезок [a,b], параметр n.
Преобразования.
1. Вычислить начальное приближение к решению уравнения (1) yn,0 = 0 .
2. Для s = 1, 2,… вычислить:
– преобразование fs = f( x, yn,s-1 ) многочлена yn,s-1 функцией f (1),
– алгебраический многочлен, интерполирующий функцию fs в узлах Чебышева на от-
резке [a,b]
Fs = Un[ fs ] = U_n[{ fs( a + (b – a) (1 – cos(i /n ))/2), i = 0,…,n }], (2)
– преобразование многочлена (2) интегральным оператором H[y] уравнения (1),
– алгебраический многочлен
gs = H[ Fs ], (3)
Денисенко П.Н.
«Искусственный интеллект» 1’2009 150
4Д
– линейное интегральное уравнение с многочленными коэффициентами (ЛИУМК)
L[y] + g = gs, (4)
– решение ЛИУМК (4) на отрезке [a,b] по алгоритму [2] с параметром n – алгебраи-
ческий многочлен
yn,s = algorithm_[2] ( L[y] + g = gs, [a,b], n). (5)
Вычислить предел последовательности алгебраических многочленов (5).
Выход. Искомая аппроксимация решения y уравнения (1)
yn = algorithm_1 ( task (1) , [a,b] , n) = c0 + c1 x +…+ cn xn = lims yn,s. (6)
Замечание 1. Алгоритм 1 с итерационным методом Ньютона или методом более
высокого порядка преобразуют уравнение (1) в последовательность ЛИУМК вида
L[y] + g = H[ E(f,g,yn,s-1) y ] + G( H,f,g,yn,s-1 ), s = 1,2,… .
Решать их по алгоритму [2], как правило, более сложно, чем ЛИУМК (4).
2. Алгоритм 1 и метод квазилинеаризации на задаче
y'' = exp(y), y( 0 ) = 0, y(1) = 0.
Эта краевая задача является одномерным аналогом уравнения гидродинамики
y'x,x + y''t,t = exp(y).
Она является модельной для метода [1] и эквивалентна интегральному уравнению
y = K[ exp(y) ], K[y] = 0x (1 – x) t y(t) dt + x1 (1 – t) x y(t) dt. (7)
Уравнение (7) и эта краевая задача имеют единственное решение – аналитическую в
окрестности отрезка [0,1] комплексной плоскости функцию
y = – \ln(2) + 2 \ln(c sec(c (x-1/2)/2), c = solve( sqrt(2) = c sec( c/4 )). (8)
Отличные от нуля коэффициенты Фуpье – Чебышева функции y (8) на отрезке [0,1]
только четные. С возрастанием параметра n = 2i они монотонно убывают к нулю a2 i(y,
[0,1]) = o(qi), q < 0.01 и принимают следующие значения:
{ a2 i(y, [0,1]) }i = 0
9 = { -0.057, 0.057, 0.00027, 2.1 10-6, 1.8 10-8,
1.66 10-10, 1.6 10-12, 1.6 10-14, 1.6 10-16, 2.1 10-18 }. (9)
Следовательно, для величины наилучшего приближения функции y (8) алгебраичес-
кими многочленами порядка n в пространстве C[0,1] справедливо тождество
infc_0,…,c_n || y(x) – (c0 +…+ cn xn) ||C[0,1] = (1 + o(1)) | a2 [n/2] + 2(y , [0,1]) |. (10)
Вычислительный эксперимент с алгоритмом 1. С возрастанием параметра n
алгоритма 1, норма погрешности решения уравнения (7) по алгоритму 1 в простран-
стве C[0,1] монотонно убывает к нулю, удовлетворяет тождества
{ || y – y2 i ||C[0,1] }i =1
5 = { 0.00034, 3.1 10-6, 2 10-8, 1.8 10-10, 9.7 10-12 } (11)
и скорость убывания тождественна скорости убывания четных коэффициентов Фуpье –
Чебышева (9) функции y (8) на отрезке [0,1] имеют место тождества
|| y – yn ||C[0,1] / | a2 [n/2] + 2(y, [0,1]) | = 1 + 2 [n/2], { 2 i }i =1
4 = { 0.3, 0.5, 0.1, 0.07 }.
Коэффициент оптимальности метода решения задачи Cn ( method, task, C[a,b] ) 1.
Поэтому из этих тождеств и тождества (10) можно сделать следующее заключение.
Вывод 1. Коэффициент оптимальности решения по алгоритму 1 уравнения
(7) в пространстве C[0,1] асимптотически минимальный
Cn(algorithm_1, task (7), C[0,1]) = (1 + o(1)) (1 + 2 [n/2]). (12)
Коэффициент оптимальности метода квазилинеаризации [1]. По методу [1]
решают (не линейные) функциональные уравнения (task) на отрезке [a,b] и вычисляют
сеточную функцию с равноотстоящими узлами
yh = {yh=(b-a)/q(xi, task ) }i = 0
q = method_[1](task , [a,b] , q ) { y(xi)}i = 0
q,
x0 = a, x1 = a + h,…,xq = b , h = (b – a)/q .
Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна...
«Штучний інтелект» 1’2009 151
4Д
Композиция метода квазилинеаризации и интерполяции алгебраическим многочленом
сеточной функции yh (вычисленной по методу квазилинеаризации) является методом
вычисления алгебраического многочлена порядка q
Pq[ yh ] = Pq[ method_[1](task, [a,b], q)]. (13)
Этот многочлен аппроксимирует решение y функционального уравнения task на отрез-
ке [a,b]. Норма погрешности метода (13) в пространстве C[a,b] не меньше соответст-
вующей сеточной нормы. Сеточная норма погрешности метода (13) тождественна
сеточной норме погрешности метода квазилинеаризации
maxx [a,b] | y – Pq[yh] | maxi=0,…,q| (y – Pq[yh]) |x = x_i | = maxi=0,…,q| y(xi) – yh(xi, task)|.
Следовательно, коэффициент оптимальности метода (13) в пространстве C = C[a,b] не
меньше
Cq(Pq[yh], task, C) maxi=0,…,q| y(xi) – yh(xi) | / infc_0,…,c_q || y(x) – (c0 +…+ cq xq) ||C .
Сравнение алгоритма 1 с методом квазилинеаризации [1]. На краевой зада-
че, эквивалентной уравнению (7), погрешность метода квазилинеаризации [1, c. 42]
maxi=0,…,10 | y(i/10) – yh=1/10(i/10, task (7) ) | = 3 10-7.
Из этого тождества и тождеств (9) – (12) можно сделать следующее заключение.
Вывод 2. Коэффициент оптимальности метода (13) на краевой задаче, экви-
валентной уравнению (7), в 100 000 раз больше коэффициента оптимальности алго-
ритма 1 на уравнении (7)
C10(P10[yh =1/10], task (7), C[0,1]) 3 10-7/ 1.6 10-12 > 100 000 .
Сравнение алгоритма 1 и методов с насыщением. Метод квазилинеаризации
и другие сеточные методы решения функциональных уравнений являются методами
с насыщением. Скорость убывания, с ростом числа узлов, погрешности решения по
методу с насыщением функционального уравнения с решением аналитической функ-
цией полиномиальная
maxi=0,…,n| y(xi) – yh=(b-a)/n(xi) | = O(n-p), p = p(method) = Const .
Скорость убывания (с возрастанием параметра n) величины наилучшего прибли-
жения функции y (8) алгебраическими многочленами порядка n в пространстве C[0,1]
оценивает тождество (10). Поэтому коэффициент оптимальности метода (13) и дру-
гих методов интерполяции сеточного решения yh многочленами возрастает с ростом
числа узлов сетки q и скорость роста
Cq(Pq[yh], task , C[0,1]) = O(zq), z 2 \ .
Коэффициент оптимальности метода ряда Тейлора имеет такую же скорость роста.
Из этих тождеств и вывода 1 можно сделать следующее заключение.
Вывод 3. Согласно критерию, минимум коэффициента оптимальности, на
краевой задаче, эквивалентной уравнению (7), композиция алгоритма преобразования
этой задачи в интегральное уравнение и алгоритма 1 предпочтительнее метода (13)
и метода ряда Тейлора.
3. Алгоритм 2 – метод Галеркина с возмущением
Вход. Уравнение (1), отрезок [a,b], параметр n.
Преобразования.
1. Вычислить аппроксимацию уравнения (1) по методу Галеркина
Sn[ L[ yn Hn[a,b]] ] = Sn[ H[ Un[ f(yn Hn[a,b]) ] ] + g ], (14)
где оператор проектирования Sn вычисляет частную сумму порядка n ряда Фурье –
Чебышева функции y на отрезке [a,b] – Sn: L2(a,b;) Hn[a,b] – с возмущением
интерполированием Un[ f ] (2) по узлам Чебышева.
Денисенко П.Н.
«Искусственный интеллект» 1’2009 152
4Д
2. Вычислить начальное приближение к решению уравнения (14) yn,0 = 0 .
3. Решить уравнение (14) по методу простой итерации для s = 1,2,…:
– вычислить преобразование многочлена yn,s-1 функцией f (1) – fs = f(x, yn,s-1),
– вычислить многочлены вида (2), (3) – Fs = Un[ fs ], gs = H[ Fs ],
– вычислить ЛИУМК вида (4)
L[ y ] + g = gs, (15)
– вычислить решение ЛИУМК (15) на отрезке [a,b] по методу Галеркина (14) – ал-
гебраический многочлен
yn,s = solve( Sn[ L[ yn Pn ] + g – gs ] = 0 ), Sn : L2(a,b;) Hn[a,b]. (16)
4. Вычислить предел последовательности многочленов (16).
Выход. Искомая аппроксимация решения уравнения (1) yn = lims yn,s.
Теорема 1. На интегральных уравнениях Гаммерштейна вида (1) алгоритм 1 экви-
валентен алгоритму 2.
Доказательство. Начальные приближения yn,0 = 0 алгоритмов 1 и 2 тождествен-
ны. Следовательно, на первой итерации (s = 1) алгоритм 1 вычисляет:
– функцию f1, тождественную функции f1 алгоритма 2,
– многочлен F1 (2), тождественный многочлену F1 уравнения (15),
– многочлен g1 (3), тождественный многочлену g1 уравнения (15),
– уравнение (4), тождественное уравнению (15),
– многочлен yn,1 (6).
Согласно теореме 1 [2], многочлен yn,1 (6) тождественен многочлену yn,1 (16).
На следующих итерациях эти тождества сохраняются.
4. Сходимость алгоритма 1
Из теоремы 1, оптимальности операторов Sn и Un как аппарата аппроксимации
в пространстве L2(a,b,) и C[a,b] [3, c. 77-95]
|| y – Sn[ y ] ||L2(a,b,) = infc_0,…,c_n || y(x) – (c0 +…+ cn xn) || L2(a,b,) ,
|| Sn ||L2(a,b,) = 1 , || Sn ||C[a,b] = (4 / 2) ln(n) + O(1), O(1) < 3, n > 0,
|| Un ||C[a,b] = (2 / ) ln(n) + O(1), O(1) < 1, n > 0
можно сделать следующее заключение.
Вывод 4. Результаты исследования метода Галёркина [4, гл. 4] на достаточ-
но широком классе уравнений Гаммерштейна (1) доказывают:
– существование многочлена yn (6) – аппроксимации искомого решения,
– сходимость последовательности многочленов (6) к точному решению уравнения
y = limn yn ,
– ограниченность коэффициента оптимальности алгоритма 1.
5. Оценки погрешности алгоритма 1
Апостериорные оценки. Теорема 3 [2] устанавливает точные и конструктив-
ные апостериорные оценки нормы в пространстве C[a,b] погрешности решения
ЛИУМК (4) по алгоритму [2]. Если последовательность этих оценок для s = 1,2,…
сходится, то ее предел естественно принять за оценку погрешности алгоритма 1 на
уравнении Гаммерштейна (1).
Пример 1. Для решения уравнения (7) по алгоритму 1 мы преобразовали это
уравнение в уравнение
y – K[ y ] = K[ exp(y) – y ], (17)
Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна...
«Штучний інтелект» 1’2009 153
4Д
где K[ y ] – линейный интегральный оператор уравнения (7). ЛИУМК (4) для уравне-
ния (17) имеет вид
y – K[ y ] = K[ Un[ exp(yn,s-1) – yn,s-1 ] ]. (18)
Оценка по теореме 3 [2] нормы в пространстве C[0,1] погрешности решения по алго-
ритму [2] ЛИУМК (18) на отрезке [0,1] с параметром n имеет вид
|| W2 [n/2] +2(x) ||C[0,1] | (n,s) |, s = 1,2,…, (19)
где (n,s) = (2 [n/2],s) – отличный от нуля коэффициент дополнительного многочле-
на решения ЛИУМК (18) по алгоритму 1 с параметром n. Если s > 2, то элементы
последовательности (n,1), (n,2),… не изменяются. Для n = 6 эта последовательность
имеет значения 6.8 10-10, 1.839 10-10, 1.83857 10-10,…, 1.83857 10-10,…. Эти последо-
вательности имеют пределы
{ (2), (4),…, (10) } = { 0.00028, 2.1 10-6, 1.8 10-8, 1.7 10-10, 1.6 10-12 }.
Для оператора L[ y ] = y – K[ y ] ЛИУМК (18) норма функции
Wn(x) = L-1[ cheb(n, 2 x – 1) ] = cheb(n,2 x – 1) +…+ Ki[ cheb(n,2 x – 1) ] +…
в пространстве C[0,1] принимает следующие значения:
|| W2 i(x) ||C[0,1] = || L-1[ cheb(2 i ,2 x – 1) ] ||C[0,1] = 1, i = 0, 1,… . (20)
Следовательно, предел полученных по теореме 1.2 оценок (19) погрешности алго-
ритма [2] на ЛИУМК (18) при s является эффективной оценкой погрешности
алгоритма 1 на уравнении Гаммерштейна (7).
Априорные оценки. Теорема 4 [2] устанавливает точные и конструктивные
априорные оценки нормы в пространстве C[a,b] погрешности решения ЛИУМК (4) по
алгоритму [2] и доказывает ограниченность коэффициента оптимальности алгоритма [2].
Этот коэффициент зависит только от оператора L[ y ]. Если линейная часть функции f
уравнения Гаммерштейна (1) мала, то оценка коэффициента оптимальности решения
ЛИУМК (4) по алгоритму [2] достаточно точно оценивает коэффициент оптималь-
ности решения этого уравнения по алгоритму 1.
Пример 2. Оценка по теореме 4 [2] коэффициента оптимальности в простран-
стве C = C[0,1] решения по алгоритму [2] ЛИУМК (18) на отрезке [0,1] с параметром
n = 2 i + 1 или n = 2 i имеет вид
Cn( algorithm_[2], (18), C ) || W2 i+2(x) ||C / a2 i+2( W2 i+2}(x), [0,1]). (21)
Мы вычислили составляющие оценки (21): || W2 i+2(x) ||C[0,1] = 1 (20) и
1/a2 i( W2 i(x), [0,1] ) = 1 + 2 i, (22)
{ 2 i}i=0
6 = { 0.06, 0.04, 0.008, 0.0036, 0.0022, 0.0013, 0.00087 } .
Следовательно, полученные по теореме 4 [2] оценки (21) коэффициента оптималь-
ности алгоритма [2] на ЛИУМК (18) являются эффективной оценкой коэффициента
оптимальности алгоритма 1 на уравнении Гаммерштейна (7) и (17) в пространстве C[0,1].
6. Вычисление оценки погрешности алгоритма 1
На основании оценок [2], мы построили алгоритмы 2 и 3 вычисления апосте-
риорных и априорных оценок погрешности решения ЛИУМК (4) по алгоритму [2] в
пространстве C[a,b]. Для ЛИУМК (18) по этим алгоритмам с параметром q вычисляют
многочлен
Wn,q(x) Wn(x), || Wn,q(x) – Wn(x) ||C[0,1] | (n, q) |
и один отличный от нуля коэффициент дополнительного многочлена (n, q). Этот ко-
эффициент убывает к нулю (с ростом параметра q)
| (n, q) | = o(uq - n), u < 0.1. (23)
Денисенко П.Н.
«Искусственный интеллект» 1’2009 154
4Д
Поведение коэффициента (n, q) хорошо иллюстрируют его значения
{ (2 i, 10) }i = 0
6 = { 2 10-16, 3 10-15, 8 10-13, 4 10-10, 3 10-7, 5 10-4, 1 } .
Следовательно, в случае ЛИУМК (18) отрезка [0,1] и параметра n:
– вычисленная по алгоритму 2 аппроксимация
|| W2 [n/2]+2,q(x) ||C[0,1] | (n, s) | , s = 1,2,…
оценки (19) имеет погрешность
| || W2 [n/2]+2(x) ||C[0,1] – || W2 [n/2]+2,q(x) ||C[0,1] | | (n, s) | | (2[n/2]+2, q) | | (n, s) |,
– коэффициент Фурье – Чебышева порядка n многочлена Wn,q(x) аппроксимирует ко-
эффициент Фурье – Чебышева порядка n функции Wn(x) с погрешностью
| an( Wn,q(x) , [0,1] ) – an( Wn(x) , [0,1] ) | | (n, q) | ,
– вычисленная по алгоритму 3 аппроксимация
|| W2 [n/2]+2,q(x) ||C[0,1] 1/a2 [n/2]+2( W2 [n/2]+2,q(x),[0,1] )
оценки (21) коэффициента оптимальности алгоритма [2] имеет погрешность
O( | (2 [n/2]+2, q) | ),
– коэффициент (n, q) удовлетворяет тождество (23).
7. Программирование алгоритма 1 в APS
Структура данных на входе.
1. Уравнение (1) определяют операторы L, H, функция f и многочлен g.
2. Линейные интегральные операторы L = L[ y ], H = H[ y ] являются суммой
операторов вида
A y , c(x)
d(x) K(x,t) y(t) dt , x [a,b] [c(x),d(x)] [a,b] ,
где ядра, пределы интегрирования и коэффициент A являются алгебраическими
многочленами. Эти операторы имеют вид
A * y + int_op(c_1, d_1, K_1 * y, t) +
+ . . . + int_op(c_s, d_s, K_s * y, t).
Искомая функция y является атомом.
Многочлены A, c_1,..., c_s, d_1,..., d_s являются термами.
Они имеют естественный для математики вид. Их аргумент x является атомом x.
Ядра – многочлены K_1, ..., K_s являются термами.
Они имеют естественный для математики вид.
Их аргументы x, t являются атомами x, t.
3. Функция f(y) = f(x,y) – нелинейность уравнения (1) – имеет естественный для
математики вид и её аргументы x, y являются атомами x, t.
4. Многочлен g является термом и имеет естественный для математики вид. Его
аргумент x является атомом x.
5. Отрезок [a, b] определяет список (a, b) ".
6. Параметр n алгоритма является целым числом.
Структура данных на выходе. Многочлен yn (6) имеет числовые коэффи-
циенты и естественный для математики вид d + ... + f * x ^ n .
APLAN-процедура 1. Алгебраическая спецификация п. 2 алгоритма 1.
f_s := subs( y = y_n, fy ); /* f_s */
F_s := Cheb_interpol(f_s , interval , n); /* U_n[f_s] */
g_s := sub_i_u(Hy , F_s); /* g_s */
LIUMK := ( Ly + g + (-1) * g_s = 0 ); /* ЛИУМК */
APLAN-процедура – реализация алгоритма [2].
Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна...
«Штучний інтелект» 1’2009 155
4Д
Структура выхода операторов APLAN-процедуры.
На каждой итерации процедура вычисляет:
– функцию fs = f(x,yn,s-1) естественного для математики вида,
– многочлен Fs = Un[ fs ] (2) естественного для математики вида,
– многочлен gs = H[ Fs ] (3) естественного для математики вида,
– ЛИУМК (4) вида, принятого в процедуре, реализующей алгоритм [2]
A * y + int_op(c_1 , d_1 , K_1 * y , t) + ...
+ int_op(c_s , d_s , K_s * y , t) + g + -1 * g_s = 0 ,
– решение ЛИУМК (4) процедурой, реализующей алгоритм [2], – многочлен yn с
числовыми коэффициентами естественного для математики вида.
8. Исследование APLAN-процедуры
Теорема 2. APLAN-процедура на каждой итерации имеет по параметру n поли-
номиальную сложность
(m+1) Q( canplf , m ) + O( n3 ),
m max { deg( L[ yn Pn ] ), deg( H[ yn Pn ] + g ) } = n + O(1),
где Q( canplf , m ) – сложность преобразования оператором canplf многочлена P.
Многочлен canplf( P ) является суммой мономов вида
c( i ) * x ^ j $ b, i = 0,…,m , j = 0,…,m.
Доказательство. APLAN-процедура – линейная. Следовательно, вычислительная
сложность процедуры тождественна сумме вычислительной сложности операторов
этой процедуры. Вычислительная сложность процедуры, реализующей алгоритм [2],
является доминирующей. Остальные операторы процедуры имеют по параметру n
полиномиальную сложность O(ns) , s 3 .
9. Вычислительный эксперимент с процедурой
Описание уравнения (17) на языке APLAN.
process[1] := (fy := exp(y) + -1 * y ; g := 0 ;
Ly := y + int_op(0, x, (-1 * ((x + -1) * t)) * y, t) +
int_op(x, 1, (-1 * (x * (t + -1))) * y, t) ;
Hy := int_op(0, x, ((x + -1) * t) * y, t) +
int_op(x, 1, (x * (t + -1)) * y, t) ; interval := (0 , 1) ;...).
Результаты решения процедурой уравнения (17) ( n = 2 ).
f_s := subs(y = y_n, fy) = 1;
F_s := Cheb_interpol(fy_n , interval , n) = 1;
g_s := sub_i_u(Hy , F_s) + g = 0.5 * x ^ 2 + -0.5 * x ;
LIUMK := ( Ly + g + -1 * F_s = 0 ) = y +
int_op(0, x, (-1 * ((x + -1) * t)) * y, t) + int_op(x, 1,
(-1 * (x * (t + -1))) * y, t) + -0.5 * x ^ 2 + 0.5 * x ;
... y_n = 0.452697 * x ^ 2 + -0.452697 * x + -0.000294724;
... F_s := Cheb_interpol(fy_n , interval , n) =
-0.0248033 * x ^ 2 + 0.0248033 * x + 1 ;
... y_n = 0.455043 * x ^ 2 + -0.455043 * x + -0.000280104;
... y_n = 0.455067 * x ^ 2 + -0.455067 * x + -0.000279958.
Вывод 5. Результаты вычислительного эксперимента – иллюстрация эффек-
тивности теоремы 2.
Денисенко П.Н.
«Искусственный интеллект» 1’2009 156
4Д
10. Программирование алгоритма 1 в СКА
Построенная выше APLAN-процедура доказывает возможность реализации алго-
ритма 1 в других СКА. Результаты исследования этой процедуры доказывают эффек-
тивность такой реализации.
11. Практическая задача
Конечные деформации упругой струны под действием поперечной нагрузки
хорошо моделирует краевая задача
y'' = 1 + a2 (y')2, y( 0 ) = 0 , y(1) = 0. (24)
Эта задача предложена В. Прагером [1, c. 43]. Задача (25) эквивалентна уравнению
y = K[ 1 + a2 (y')2 ], K[ y ] = 0x (1 – x) t y(t) dt + x1 (1 – t) x y(t) dt. (25)
Задача (24) и уравнение (25) имеют единственное решение – аналитическую в
окрестности отрезка [0,1] комплексной плоскости функцию
y = 1/a2 ln( cos(a (x – 1/2)) / cos(a/2) ). (26)
Отличные от нуля коэффициенты Фуpье – Чебышева функции y (26) на отрезке [0,1]
только четные. С возрастанием параметра n = 2 i эти коэффициенты регулярно убы-
вают к нулю | a2 i( y, [0,1] ) | = o(qi) , q < 0.01 и, в случае параметра a = 0.7, при-
нимают следующие значения:
{ a2 i( y , [0,1] ) }i = 0
9 = { 0.064, -0.064 , -0.00034, -2.8 10-6, -2.7 10-8,
-2.7 10-10, -2.9 10-12, -3.2 10-14, -4.6 10-16, 6.2 10-18 }. (27)
Следовательно, для величины наилучшего приближения функции y (26) (a = 0.7) алгеб-
раическими многочленами порядка n в пространстве C[0,1] справедливо тождество (10).
Вычислительный эксперимент с алгоритмом 1. С возрастанием параметра n
алгоритма 1, норма погрешности решения уравнения (25) с параметром a = 0.7 по
алгоритму 1 в пространстве C[0,1] убывает к нулю и удовлетворяет тождества
{ || y - y2 i ||C[0,1] }i =1
5 = { 0.00036, 3.4 10-6, 3.1 10-8, 2.9 10-10, 6.6 10-12 }. (28)
Скорость убывания тождественна скорости убывания четных коэффициентов Фуpье –
Чебышева (27) функции y (26) на отрезке [0,1] имеют место тождества
|| y – yn ||C[0,1] / | a2 [n/2] + 2( y , [0,1] ) | = 1 + 2 [n/2], { 2 i }i =1
4 = { 0.063, 0.21, 0.17, 0.08 }.
Коэффициент оптимальности метода решения задачи Cn ( method, task, C[a,b] ) 1 .
Поэтому из этих тождеств и тождества (10) можно сделать следующее заключение.
Вывод 6. Коэффициент оптимальности решения по алгоритму 1 уравнения (25)
с параметром a = 0.7 в пространстве C[0,1] – асимптотически минимальный
Cn(algorithm_1, task (25) ( a = 0.7 ), C[0,1]) = ( 1 + o(1) ) ( 1 + 2 [n/2] ).
Сравнение алгоритма 1 с методом квазилинеаризации [1]. На краевой зада-
че (24), эквивалентной уравнению (25), согласно [1, c. 42], метод квазилинеаризации
имеет погрешность maxi=0,…,10| y(i/10) – yh=1/10(i/10, task (24) ) | = 3 10-6.
Из этого тождества и тождеств (27) – (29) можно сделать следующее заключение.
Вывод 7. Коэффициент оптимальности метода (13) на краевой задаче (24) с
параметром a = 0.7 в пространстве C[0,1] (эквивалентной уравнению (25)) в
1 000 000 раз больше коэффициента оптимальности алгоритма 1 на уравнении (25)
C10( P10[ yh=1/10 ], task (24), C[0,1] ) 3 10-6 / 2.9 10-12 > 1 000 000.
Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна...
«Штучний інтелект» 1’2009 157
4Д
Заключение
Алгоритм 1 решает в СКА интегральные уравнения Гаммерштейна вида (1) на
отрезке [a,b] и вычисляет алгебраический многочлен yn (6) порядка n N. Эта ап-
проксимация решения уравнения Гаммерштейна (1) оптимальна для символьных
преобразований в СКА – коэффициент оптимальности алгоритма в пространстве
C[a,b] ограничен на широком классе уравнений Гаммерштейна.
Алгоритм 1 на уравнениях Гаммерштейна реализует идею В.К. Дзядыка.
На основании a-метода построить эффективные численные методы решения
функциональных уравнений.
Дополнение
1. Алгоритм 1' – модификация алгоритма 1. Алгоритм [2] заменен алгоритмом
a-метода, где базис дополнительного многочлена является ортогональным базисом
пространства Гильберта H[a,b]..
2. Для алгоритма 1' имеют место аналог теоремы 1 и аналоги применения тео-
рем 1 – 4 [2]. В них пространство L2(a,b;) заменено пространством H[a,b]..
3. APLAN-процедура 1’ – модификация процедуры 1. Процедура, реализую-
щая алгоритм [2], заменена реализацией алгоритма a-метода с ортогональным бази-
сом пространства Гильберта H[a,b].
Литература
1. Беллман Р. и Калаба Р. Квазилинеаризация и нелинейные краевые задачи. – М.: Мир, 1968. – 183 c.
2. Денисенко П.Н. Оптимальный метод решения интегральных уравнений с ядрами типа функции
Грина // Hауковi записки Кipовогpадського деpжавного педагогiчного унiвеpситету. – Сеpiя:
Математичнi науки. – Вип. 65. – 2006. – С. 38-49.
3. Пашковский С. Вычислительные применения многочленов и рядов Чебышева. – М.: Наука, 1983. – 384 с.
4. Красносельский М.А., Вайникко Г.М. и др. Приближенное решение операторных уравнений. – М.:
Наука, 1969. – 456 c.
П.М. Денисенко
Оптимальний алгоритм для розв’язування iнтегральних рiвнянь Гаммерштейна в системах
комп’ютерної алгебри
У роботi побудовано алгебраїчний алгоритм для обчислення в системах комп’ютерної алгебри алгебраїчного
многочлену yn порядку n N. Цей многочлен – апроксимацiя розв’язку y = y(x), x [a,b]
iнтегрального рiвняння Гаммерштейна. Ця апроксимацiя оптимальна в просторi C[a,b].
P.N. Denisenko
Оptimal Algorithm of Solving the Hammerstein Integral Equations in the Computer Algebra Systems
We constructed the algebraic algorithm for computing in the computer algebra systems the algebraic polynomial yn of
order n N. This polynomial is the optimal approximation for the Hammerstein integral equation solution
y = y(x), x [a,b] in C[a,b].
Статья поступила в редакцию 07.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-7848 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T13:23:02Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Денисенко, П.Н. 2010-04-19T12:35:33Z 2010-04-19T12:35:33Z 2009 Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 1. — С. 149-157. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7848 681.142.2/518.3 У роботi побудовано алгебраїчний алгоритм для обчислення в системах комп’ютерної алгебри алгебраїчного многочлену yn порядку n e N. Цей многочлен – апроксимацiя розв’язку y = y(x), x e [a,b] iнтегрального рiвняння Гаммерштейна. Ця апроксимацiя оптимальна в просторi C[a,b]. We constructed the algebraic algorithm for computing in the computer algebra systems the algebraic polynomial yn of order n e N. This polynomial is the optimal approximation for the Hammerstein integral equation solution y = y(x), x e [a,b] in C[a,b]. В работе построен алгебраический алгоритм для вычисления алгебраического многочлена yn порядка n e N в системах компьютерной алгебры. Этот многочлен аппроксимирует решение y=y(x), x e [a,b] интегрального уравнения Гаммерштейна. Эта аппроксимация оптимальна в пространстве C[a,b]. ru Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры Оптимальний алгоритм для розв’язування iнтегральних рiвнянь Гаммерштейна в системах комп’ютерної алгебри Оptimal Algorithm of Solving the Hammerstein Integral Equations in the Computer Algebra Systems Article published earlier |
| spellingShingle | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры Денисенко, П.Н. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| title | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры |
| title_alt | Оптимальний алгоритм для розв’язування iнтегральних рiвнянь Гаммерштейна в системах комп’ютерної алгебри Оptimal Algorithm of Solving the Hammerstein Integral Equations in the Computer Algebra Systems |
| title_full | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры |
| title_fullStr | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры |
| title_full_unstemmed | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры |
| title_short | Оптимальный алгоритм для решения интегральных уравнений Гаммерштейна в системах компьютерной алгебры |
| title_sort | оптимальный алгоритм для решения интегральных уравнений гаммерштейна в системах компьютерной алгебры |
| topic | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| topic_facet | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7848 |
| work_keys_str_mv | AT denisenkopn optimalʹnyialgoritmdlârešeniâintegralʹnyhuravneniigammeršteinavsistemahkompʹûternoialgebry AT denisenkopn optimalʹniialgoritmdlârozvâzuvannâintegralʹnihrivnânʹgammeršteinavsistemahkompûternoíalgebri AT denisenkopn optimalalgorithmofsolvingthehammersteinintegralequationsinthecomputeralgebrasystems |