Алгоритм для решения нелинейных краевых задач по τ-методу Ланцоша в системах компьютерной алгебры
Построен алгебраический алгоритм для преобразования многоточечной линейной краевой задачи для дифференциального уравнения порядка k с линейной частью – линейный дифференциальный оператор многочленными коэффициентами порядка k и нелинейной частью – функция f( y, y',..., y^(k-1) ) в алгебраически...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/8166 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм для решения нелинейных краевых задач по Ʈ-методу Ланцоша в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 4. — С. 119-129. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860106182202490880 |
|---|---|
| author | Денисенко, П.Н. |
| author_facet | Денисенко, П.Н. |
| citation_txt | Алгоритм для решения нелинейных краевых задач по Ʈ-методу Ланцоша в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 4. — С. 119-129. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| description | Построен алгебраический алгоритм для преобразования многоточечной линейной краевой задачи для дифференциального уравнения порядка k с линейной частью – линейный дифференциальный оператор многочленными коэффициентами порядка k и нелинейной частью – функция f( y, y',..., y^(k-1) ) в алгебраический многочлен порядка n (n принадлежит N). Этот многочлен – аппроксимация решения y(x), x принадлежит [a,b], исходной краевой задачи. Эта аппроксимация оптимальна в пространстве C^k[a,b].
Побудовано алгебраїчний алгоритм для перетворення багатоточкової лiнiйної крайової задачi для диференцiального рiвняння порядку k з лiнiйною частиною – лiнiйний диференцiальний оператор з коефiцiєнтами – многочленами та нелiнiйною – функцiя f( y, y',…, y^(k-1) ) на алгебраїчний многочлен порядку n (n належить N). Цей многочлен – апроксимацiя розв’язку y(x), x належить [a,b], оригiнальної крайової задачi. Ця апроксимацiя оптимальна в просторi C^k[a,b].
We constructed the algebraic algorithm for transforming the nonlinear boundary-value problem into the algebraic polynomial of order n (n belongs N). This polynomial is the solution y(x), x e [a,b] approximation for the problem. This approximation is optimal in the space C^k[a,b].
|
| first_indexed | 2025-12-07T17:31:09Z |
| format | Article |
| fulltext |
«Штучний інтелект» 4’2009 119
3Д
УДК 681.142.2/518.3
П.Н. Денисенко
Кировоградский учебно-научный педагогический комплекс МОН Украины,
г. Кировоград, Украина
pnden_osvita@yahoo.com
Алгоритм для решения нелинейных
краевых задач по -методу Ланцоша
в системах компьютерной алгебры
Построен алгебраический алгоритм для преобразования многоточечной линейной краевой задачи для
дифференциального уравнения порядка k с линейной частью – линейный дифференциальный оператор
многочленными коэффициентами порядка k и нелинейной частью – функция f( y, y',..., y(k-1) ) в
алгебраический многочлен порядка n N. Этот многочлен – аппроксимация решения y(x), x [a,b]
исходной краевой задачи. Эта аппроксимация оптимальна в пространстве Ck
[a,b].
Введение
Актуальность темы исследования. Многоточечные краевые задачи для обык-
новенных дифференциальных уравнений являются классическим аппаратом матема-
тического моделирования [1]. Maple, Mathematica, Mathcad, Matlab и другие системы
компьютерной алгебры (СКА) – системы символьных вычислений на компьютерах –
стали естественной средой математического моделирования.
СКА для обыкновенных дифференциальных уравнений символьно вычисляют:
– решение – композицию специальных математических функций (существует редко),
– частную сумму ряда Тейлора решения задачи Коши порядка n. Обычно n < 10.
Этот алгебраический многочлен, как правило, не удовлетворяет основной критерий
эффективности математических моделей – точность.
Возможности классического математического обеспечения ЭВМ. Компьютерные
системы типа Matlab вычисляют сеточную аппроксимацию решения краевых задач для
обыкновенных дифференциальных уравнений по численным методам. Это методы, как
правило, с насыщением. Производные сеточной функции, как правило, являются не
оптимальным аппаратом аппроксимации производных исходной функции.
Цель работы. Построить алгебраический алгоритм для вычисления в СКА ап-
проксимации на отрезке [a,b] решения многоточечных линейных краевых задач для
обыкновенных дифференциальных уравнений порядка k следующего вида
D[y] = f(y, y',..., y(k-1)), D[ y ] = A y(k) + …+ C y, (1)
Cond(y) = { Di[y] |x = d_i + Gi = 0 }i = 1
k, Di[y] = Ai y(k_i) + … + Ci y. (2)
Коэффициенты A,…,C линейного оператора D[y] (1) – алгебраические многочлены.
Точки задания краевых условий (2) принадлежат отрезку [a,b] – di [a,b], i = 1, …, k
и являются регулярными не особыми точками оператора D[y] – A(di) 0, i = 1, …, k .
Денисенко П.Н.
«Искусственный интеллект» 4’2009 120
3Д
По этому алгоритму в СКА вычисляют алгебраический многочлен yn порядка n N
yn = c0 + c1 x + … + cn xn = algorithm_1((1), (2), [a,b], n). (3)
Многочлен yn (3) аппроксимирует решение y = solve( (1), (2) ), y = y(x), x [a,b]
краевой задачи (1), (2). Эта аппроксимация оптимальна для преобразований в СКА
решения y задачи (1), (2) и его производных y', …, y(k) на отрезке [a,b] – коэффициент
оптимальности алгоритма на краевой задаче (1), (2) в пространстве Ck
[a,b] ограничен
Cn(algorithm_1, (1), (2), Ck
[a,b]) = || y – yn ||X / infc_0,…, c_n || y(x) – (c0 + c1 x + …+ cn xn) ||X <.
Актуальность задачи. Уравнения вида (1) применяются в математических мо-
делях более часто, чем дифференциальные уравнения других типов. Если процесс
моделируют дифференциальным уравнением порядка k, то, часто, на отрезке [a,b]
исследуют решение y = y(x) этого уравнения и его производные y', …, y(k) – преобра-
зуют эти функции на отрезке [a,b].
1. Композиция итерации, -метода и интерполяции
Алгоритм 1.
Вход: Уравнение (1), условия (2), отрезок [a,b], параметр n.
Выход: Алгебраический многочлен (3) (порядка n ).
Преобразования:
1. Вычислить начальное приближение к решению краевой задачи (1), (2) – мно-
гочлен порядка k – 1, удовлетворяющий краевые условия (2)
yn,0 = yk-1 = solve( Cond( yk-1 Pk-1 ) ). (4)
2. Для s = 1, 2, … выполнить:
2.1. Вычислить производные y'n,s-1, …, y(k-1)
n,s-1 многочлена yn,s-1.
2.2. Преобразовать функцией f (1) многочлен yn,s-1 и его производные в функцию
fs = fs(x) = f(x, yn,s-1, …, y(k-1)
n,s-1. (5)
2.3. Вычислить алгебраический многочлен
Fs = Un[fs] = Un[{ fs( a + (b – a) (1 – cos(i /n ))/2), i = 0, …, n}] – (6)
интерполяцию функции fs (5) в узлах Чебышева на отрезке [a,b] [2, с. 94].
2.4. Вычислить линейное дифференциальное уравнение с многочленными
коэффициентами (ЛДУМК)
D[y] = Fs. (7)
2.5. Решить по алгоритму [3] -метода Ланцоша [1] с параметром n краевую
задачу (2) для ЛДУМК (7) на отрезке [a,b] и вычислить аппроксимацию точного ре-
шения краевой задачи (7), (2) – y(s,x) = solve( (7), (2) ) – алгебраический многочлен
порядка n
yn,s = algorithm_[3]( D[y] = Fs, Cond(y), [a,b], n ). (8)
3. Вычислить искомую аппроксимацию (3) решения y краевой задачи (1), (2) –
предел последовательности многочленов (8) при s
yn = algorithm_1 ( (1), (2), [a,b], n ) = lim s yn,s.
Алгоритм для решения нелинейных краевых задач по -методу Ланцоша...
«Штучний інтелект» 4’2009 121
3Д
2. Оптимальность алгоритма 1 на модельной задаче
Модельная краевая задача метода квазилинеаризации [4]
y'' = exp(y), y( 0 ) = 0, y( 1 ) = 0. (9)
Эта задача является одномерным аналогом уравнения гидродинамики y''x,x + y''t,t = exp(y)
и имеет единственное решение – функцию аналитическую в окрестности отрезка [0,1]
комплексной плоскости
y = – ln(2) + 2 ln(c sec(c (x – 1/2)/2), c = solve(sqrt(2) = c sec(c/4)). (10)
Свойства функции y (10). Отличные от нуля коэффициенты Фурье – Чебышева
функций y, y'' (10) на отрезке [0,1] только четные и принимают следующие значения
{ 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 } ,
{ a2 i(y'' , [0,1]) }i = 0
10 = { 0.94, 0.053 , 0.001 , 1.6 10-5 , 2.4 10-7 ,
3.5 10-9 , 4.7 10-11 , 6.3 10-13 , 8.2 10-15 , 8.8 10-17 , -5.5 10-18 }. (11)
С ростом параметра n = 2 i они регулярно убывают к нулю
|a2 i + 2(y, [0,1])| / |a2 i(y, [0,1])| = 1, 2 i, 1,0 = 1, 1,2 = 0.005, 1,4 = 0.007, …, 1,14 = 0.01,
|a2 i + 2(y’’, [0,1])| / |a2 i(y’’, [0,1])| = 2, 2 i, 2,0 = 0.06, 2,2 = 0.2, 2,4 = 0.016, …, 2,16 = 0.01.
Следовательно, для величины наилучшего приближения функции y (10) алгебраичес-
кими многочленами порядка n в пространстве C[0,1] и C2
[0,1] справедливы тождества
infc_0, …, c_n || y(x) – (c0 + … + cn xn) ||C[0,1] = (1 + n) | a2 [n/2] + 2(y, [0,1]) |,
infc_0, …, c_n || y(x) – (c0 + … + cn xn) ||C:2_[0,1] = (1 + n) | a2 [n/2] (y’’, [0,1]) |, (12)
где n > 1 | n | 0.01, n > 2 | n | 0.01.
Вычислительный эксперимент с алгоритмом 1. Норма погрешности решения
краевой задачи (9) по алгоритму 1 в пространстве C[0,1] и C2
[0,1] удовлетворяет тож-
дества
{ || y - y2 i ||C[0,1] }i =1
5 = { 0.0043, 2.5 10-5, 1.2 10-7, 1.1 10-9, 6.7 10-11 },
{ || y - y2 i ||C^2_[0,1] }i =1
5 = { 0.056, 0.001, 1.7 10-5, 2.5 10-7, 3.6 10-9 }.
Из тождеств (11) и (12) можно сделать следующее заключение.
Вывод 1. Главной частью коэффициента оптимальности решения по алгорит-
му 1 краевой задачи (9) в пространствах C[0,1] и C2
[0,1] являются отношения
{ || y – yn ||C[0,1] / | a2 [n/2] + 2(y, [0,1]) | = C2 [n/2], { C2 i }i =1
4 = { 16, 12, 7, 6 },
||y – yn||C^2_[0,1]/|a2 [n/2] (y'',[0,1])| = 1 + 2 [n/2], {2 i}i =1
4 = {0.06, 0.000006, 0.05, 0.04}.(13)
Согласно определению, коэффициент оптимальности метода вычисления алгебраи-
ческого многочлена, аппроксимирующего решение задачи (1), (2), не меньше единицы.
Поэтому из этих тождеств и тождеств (12) можно сделать следующее заключение.
Вывод 2. Главная часть коэффициента оптимальности алгоритма 1 на зада-
че (9):
– в пространстве C[0,1] ограничена и справедливо тождество
Cn( algorithm_1, (9), C[0,1] ) = (1 + n) C2 [n/2],
– в пространстве C2
[0,1] асимптотически тождественна минимальному значению коэф-
фициента оптимальности и справедливо тождество
Cn( algorithm_1, (9), C2
[0,1] ) = (1 + n) (1 + 2 [n/2] ).
Денисенко П.Н.
«Искусственный интеллект» 4’2009 122
3Д
3. Алгоритм 1 и метод квазилинеаризации
Метод квазилинеаризации [4]. По этому методу решают двухточечные краевые
задачи для нелинейных дифференциальных уравнений второго порядка, разрешен-
ных относительно старшей производной (task) с точками задания краевых условий a
и b (типа задачи (9)) на отрезке [a,b], и вычисляют сеточную функцию с q + 1 равно-
отстоящими узлами сетки
x0 = a, x1 = a + h, …, xq = b, h = (b – a)/q,
yh = { yh(xi)}i = 0
q = { yh (xi, task )}i = 0
q = method[4]( task, [a,b], q) { y(xi)}i = 0
q.
Композиция метода квазилинеаризации и интерполяции алгебраическим мно-
гочленом сеточной функции yh (вычисленной по методу квазилинеаризации) является
методом вычисления алгебраического многочлена порядка q
Pq[ yh ] = Pq[method[4]( task, [a,b], q)], h = (b – a)/q. (14)
Этот многочлен аппроксимирует решение y исходной задачи task на отрезке [a,b]. Норма
погрешности метода (14) в пространстве C[a,b] не меньше соответствующей сеточной
нормы. Сеточная норма погрешности метода (14) тождественна сеточной норме по-
грешности метода квазилинеаризации
maxx [a,b] | y – Pq[yh] | maxi = 0, …, q| (y – Pq[yh]) |x = x_i | = maxi = 0, …, q| y(xi) – yh(xi )|.
Следовательно, коэффициент оптимальности метода (14) в пространстве X = C[a,b] не
меньше
Cq( Pq[yh], task, C[a,b] ) maxi = 0, …, q| y(xi) – yh(xi) | / infc_0, …, c_q || y(x) – (c0 + … + cq xq) ||C[a,b].
Сравнение алгоритма 1 с методом Pq[yh] (14). На краевой задаче (9), согласно [4,
с. 42], метод квазилинеаризации с параметром q = 10 имеет погрешность 3 10–7. Поэтому
из тождеств (11) – (13) можно сделать следующее заключение.
Вывод 3. Главная часть коэффициента оптимальности в пространстве C[0,1]
метода алгебраической интерполяции сеточного решения метода квазилинеариза-
ции (14) на краевой задаче (9) более чем в 100 000 раз больше 1 + 2 [n/2] (13) – главной
части коэффициента оптимальности алгоритма 1 на этой задаче
C10( P10[yh =1/10] , task (9) , C[0,1] ) 3 10-7/ 1.6 10-12 > 105.
4. Алгоритм 1 и методы с насыщением
Метод квазилинеаризации и другие сеточные методы решения функциональ-
ных уравнений, как правило, являются методами с насыщением. Скорость убывания
с ростом числа узлов погрешностей решения по методу с насыщением краевой зада-
чи с решением – аналитической функцией полиномиальная
maxi=0, …, q| y(xi) – yh(xi)| = O(q-p), h = (b – a) / q, p = p(method) = Const.
Скорость убывания (с возрастанием параметра n) величины наилучшего приближе-
ния функции y (10) алгебраическими многочленами порядка n в пространствах C[0,1]
и C2
[0,1] оценивают тождества (11). Поэтому коэффициент оптимальности метода (14)
и других методов интерполяции сеточного решения yh многочленами возрастает с рос-
том числа узлов сетки q и скорость роста
Cq( Pq[yh], task, C[0,1] ) = O(zq), z 2.
Алгоритм для решения нелинейных краевых задач по -методу Ланцоша...
«Штучний інтелект» 4’2009 123
3Д
Коэффициент оптимальности метода ряда Тейлора имеет такую же скорость роста.
Из этих тождеств и вывода 1 можно сделать следующее заключение.
Вывод 4. На краевой задаче (9) алгоритм 1 предпочтительнее метода (14) и
метода ряда Тейлора, согласно критерию – минимум коэффициента оптимальности.
5. Эквивалентный алгоритм метода Галеркина
Пусть для условий (2) существуют многочлен yk – 1 (4) и линейный интегральный
оператор
K[ f ] = solve( y(k) = f, { Di[ y ] |x = d_i = 0 }i = 1
k ), (15)
где Di[ y ] – линейные дифференциальные операторы условий (2). Тогда результат под-
становки y = K[ u ] + yk – 1 в уравнении (1) является интегральным уравнением отно-
сительно функции u
D[ K[ u ] + yk – 1 ] = f( K[ u ] + yk – 1, ( K[ u ] + yk – 1)', …, ( K[ u ]+yk – 1)(k-1)) ]. (16)
Для решения u уравнения (16) и решения y краевой задачи (1), (2) справедливо тож-
дество
y = K[ u ] + yk – 1.
Метод 1.
1. Преобразовать краевую задачу (1), (2) в интегральное уравнение (16).
2. Вычислить аппроксимацию уравнения (16) по методу Галеркина с оператором
проектирования Sp: L2(a,b;) Hp[a,b] (вычисляет частную сумму порядка p = n – k,
где k – порядок уравнения (1), ряда Фурье – Чебышева функции на отрезке [a,b]) и
возмущением алгебраическим интерполированием правой части уравнения (16) по уз-
лам Чебышева на отрезке [a,b] – Un[ f ] (6)
Sp[D[ K[ up ]+yk – 1 ]] = Sp[ Un[ f( K[ up ]+yk – 1, …, (K[ up ]+yk – 1)(k-1) )]] (up Hp[a,b]).(17)
Неизвестным уравнения (17) является алгебраический многочлен up порядка
p = n – k вида – частная сумма ряда Чебышева на отрезке [a,b] – up Hp[a,b].
3. Решить уравнение (17) по методу простой итерации с начальным приближе-
нием up,0 = 0. Следующие приближения являются решением уравнения
up,s = solve( Sp[ D[ K[ up ] + yk – 1 ] – Fs ] = 0 (up Hp[a,b] ) ), (18)
Fs = Un[ f( K[ up,s – 1 ] + yk – 1, …, ( K[ up,s – 1 ] + yk – 1 )(k – 1) ) ], s = 1, 2, ….
По этому методу вычисляют алгебраический многочлен up = lims up,s.
4. Преобразовать многочлен up в искомую аппроксимацию решения y задачи (1), (2)
yn = K[ up ] + yk – 1.
Замечание 1. Уравнение (18) является аппроксимацией по методу Галеркина ли-
нейного интегрального уравнения с многочленными коэффициентами (ЛИУМК)
D[ K[ u ] + yk – 1 ] = Fs. (19)
Уравнение (19) является результатом подстановки y = K[ u ] + yk-1 (введена в уравне-
нии (16)) в ЛДУМК (7). Следовательно, метод 1 можно реализовать в виде следую-
щего алгоритма.
Алгоритм 2. Алгоритм 1 со следующей модификацией п. 1 и п. 2.5.
1. Вычислить начальное приближение к решению уравнения (17) up,0 = 0, опе-
ратор K (15) и многочлен (4) yn,0 = yk-1 (K[ 0 ] = 0).
2.5. Вычислить:
– ЛИУМК (19) – преобразовать краевую задачу для ЛДУМК (7), (2),
Денисенко П.Н.
«Искусственный интеллект» 4’2009 124
3Д
– решение up,s (18) уравнения (19) по методу Галеркина,
– аппроксимацию решения задачи (7), (2) – преобразовать многочлен up,s (18)
yn,s = K[ up,s ] + yk – 1. (20)
Теорема 1. Пусть:
– для условий (2) существуют многочлен yk-1 (4) и оператор K[ u ] (15),
– оператор K[ u ] (15) преобразует моном xi, i N в полином
K[ xi ] = bi xi+k + … + ei, bi 0,
– параметр алгоритма 1 n 2 k, k = ord_equ( D[ y ] ) – порядок уравнения (1).
Тогда алгоритм 1 эквивалентен алгоритму 2.
Доказательство. Если выполнены условия теоремы, то, согласно [3], многочлен
yn,s (8) тождественен многочлену yn,s (20).
Остальные преобразования алгоритмов 1 и 2 тождественны.
6. Сходимость алгоритма 1
Из оценок оптимальности операторов Sn и Un как аппарата аппроксимации функ-
ций на отрезке [a,b] [2, с. 77-95]
|| y – Sn[ y ] ||L_2(a,b; ) = infc_0, …, c_n || y(x) – (c0 + … + cn xn) || L_2(a,b; ),
|| Sn || L_2(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
можно сделать следующее заключение.
Вывод 5. Результаты исследования метода Галеркина [5] решения операторных
уравнений в пространстве Гильберта L2(a,b; ) на интегральных уравнениях вида (16)
достаточно широкого класса доказывают:
– существование многочлена
up= solve( (17) ), p m, m = m( D[ K[ u ] ], f(x,y,y', …, y(k-1) )|y = K[ u ] + yk – 1 ),
– сходимость последовательности um, …, up, up+1, … u = solve( (16) ) ,
– ограниченность коэффициента оптимальности метода 1 (и алгоритма 2).
Поэтому из теоремы 1 для краевой задачи для обыкновенных дифференциаль-
ных уравнений вида (1), (2) достаточно широкого класса следует:
– существование многочлена yn (3), n m+k,
– сходимость последовательности ym+k, …, yn, yn+1, … y = solve( (1), (2) ).
7. Апостериорные оценки погрешности
Теоретические оценки. Для алгоритма [3] известны точные и конструктивные
апостериорные оценки нормы в пространстве C[a,b] и Ck
[a, b] погрешности решения
y(s, x) краевой задачи для ЛДУМК (7), (2) – || y(s,x) – yn,s(x) ||. Если последовательность
этих оценок ( s = 1, 2, …) сходится, то ее предел естественно принять за оценку по-
грешности алгоритма 1 на краевой задаче (1), (2).
Пример 1. (Иллюстрация эффективности теоретических оценок). Мы решили по
алгоритму 1 краевую задачу (9) и тождественную задачу
y''– y = exp(y) – y, y( 0 ) = 0, y(1) = 0. (21)
Начальное приближение yn,0 = yk-1 = 0. По алгоритму 1 для задачи (21) решают сле-
дующие краевые задачи для ЛДУМК
y''– y = Un[ exp(yn,s-1) – yn,s-1], y(0) = 0, y(1) = 0, s = 1, 2, …. (22)
Алгоритм для решения нелинейных краевых задач по -методу Ланцоша...
«Штучний інтелект» 4’2009 125
3Д
Оценка [3] нормы в пространстве X погрешности решения по алгоритму [3] краевой
задачи (22) на отрезке [0,1] с параметром n имеет вид
|| W2 [n/2] + 2(x) ||X | (n, s) |, s = 1, 2, …, (23)
где (n,s) = (2 [n/2], s) – отличный от нуля коэффициент дополнительного многочле-
на решения задачи (22) по алгоритму [3],
|| W2 i(x) ||C^2_[0,1] = 1, i = 0, 1, ….
Коэффициенты { (6,1), (6,2), …} оценки (23) принимают следующие значения
{ 6 10-7, 1.7 10-5, 1.65326 10-5, 1.65277 10-5,…,1.65277 10-5,…}.
Последовательность (n, 1), (n, 2), … ( n N ) коэффициентов оценки (31) имеет пре-
дел (n) = (2 [n/2]). Этот предел для задач (9) и (21) принимает следующие значения
{ (2), (4),…,(10) } = { 0.056, 0.001 , 1.7 10-5 , 2.5 10-7 , 3.5 10-9 }.
Поэтому из оценок [3] и тождеств (11) – (13) можно сделать следующее заключение.
Вывод 6. Предел оценок [3] погрешностей алгоритма [3] на краевой задаче для
ЛДУМК (7), (2) при s является конструктивной оценкой погрешности алгорит-
ма 1 на краевой задаче (1), (2). На краевой задаче (9) и (21) эта оценка точная.
8. Априорные оценки погрешности
Теоретические оценки. Для решения краевой задачи для ЛДУМК (7), (2) по ал-
горитму [3] известны [3] точные и конструктивные априорные оценки нормы погрешнос-
ти и коэффициента оптимальности в пространстве Ck
[a, b]. Этот коэффициент зависит
от оператора D[ y ] (1) и операторов Di (2). Если линейная часть (по y) функции f
уравнения (1) мала, то коэффициент оптимальности решения краевой задачи для
ЛДУМК (7), (2) по алгоритму [3] достаточно точно аппроксимирует коэффициент оп-
тимальности решения краевой задачи (1), (2) по алгоритму 1.
Пример 2. (Иллюстрация эффективности теоретических оценок). Оценка [3]
коэффициента оптимальности в пространстве C2
[0,1] решения по алгоритму [3] задачи
(22) на отрезке [0,1] имеет вид
Cn(algorithm_[3], (22), C2
[0, 1] ) || W''2 i(x) ||C[0, 1] / a2 i( W''2 i(x), [0,1] ), (24)
где i = [n/2]. Мы вычислили составляющие правой части оценки (24) –
|| W''2 i(x) ||C[0,1] = 1, 1/a2 i(W''2 i(x), [0,1]) = 1 + 2 i,
{ 2 i, i = 0, …, 6 } = { 0,06, 0,04, 0,008, 0,0036, 0,0022, 0,0013, 0,00087 }.
Из этих тождеств и тождеств (13) можно сделать следующее заключение.
Вывод 7. В пространстве C2
[0, 1] оценка (24) коэффициента оптимальности алго-
ритма [3] на краевой задаче для ЛДУМК (22) является эффективной оценкой коэф-
фициента оптимальности (13) алгоритма 1 на краевых задачах (9) и (21).
9. Вычисление оценок погрешности
В работе [3] построены следующие алгоритмы для вычисления оценок погреш-
ности решения краевых задач (2) для ЛДУМК (7) по алгоритму [3]:
– алгоритм 2 оценки нормы погрешности в пространстве Ck
[a, b], …,
– алгоритм 3 оценки коэффициента оптимальности в пространстве Ck
[a, b].
Для задачи (22) по этим алгоритмам с параметром q вычисляют многочлен
Wn,q(x) Wn(x), || Wn,q(x) – Wn(x) ||C^2_[0, 1] |(n, q)|
Денисенко П.Н.
«Искусственный интеллект» 4’2009 126
3Д
и один отличный от нуля коэффициент дополнительного многочлена (n, q). Этот ко-
эффициент убывает к нулю (с ростом параметра q )
(n, q) | = o(uq - n), u < 0.1.
Поведение коэффициента (n, q) хорошо иллюстрируют его значения
{ (2 j, 10) }j = 0
6 = { 2 10-16, 3 10-15, 8 10-13, 4 10-10, 3 10-7, 5 10-4, 1 }.
Из этих тождеств можно сделать следующее заключение.
Вывод 8. В случае задачи (22), отрезка [0, 1] и параметра n:
– по алгоритму 2 [3] с параметром q вычисляют аппроксимацию
|| W2 [n/2]+2, q(x) ||C^2_[0, 1] | (n, s), s = 1, 2, …,
оценки (24) погрешности алгоритма 1 и погрешность этой аппроксимации не больше
| || W2 [n/2] + 2(x) ||C^2_[0,1] – || W2 [n/2]+2, q(x) || C^2_[0,1] | | (n, s) |
| (n, s) | | (2 [n/2] + 2, q) | = | (n, s) | o( uq – 2 [n/2]-2 ) = o(uq – 2 [n/2]-2 ), u < 0.1,
– по алгоритму 3 [3] с параметром q вычисляют аппроксимацию
|| W''2 [n/2]+2, q(x) ||C[0,1] 1/a2 [n/2]+2(W''2 [n/2]+2, q(x),[0,1]),
оценки (24) коэффициента оптимальности алгоритма 1 и погрешность этой аппрок-
симации имеет порядок
O( | ( 2 [n/2]+2, q) | ) = O(uq – 2 [n/2] ), u < 0.1.
10. Программирование алгоритма 1 в APS
Структура данных на входе.
1. Уравнение (1) определяют его правая и левая части – функция f(y, y',…, y(k-1))
и линейный дифференциальный оператор с многочленными коэффициентами D[ y ].
2. Оператор D[ y ] имеет вид A * dif( y, k ) + ... + C * y + G,
где y – атом, многочлены A,..., C, G являются термами, имеют вид, естествен-
ный для математики и аргумент – атом x.
3. Функция f(x, y, y', …, y(k-1)) имеет вид, обычный для СКА, и аргументы – атомы
x, y, y1, y2,..., ys, s = k – 1.
4. Условия (2) имеют вид (...,(x = d_i, Ai*dif(y,k_i)+ ... +Ci*y+Gi = 0),...).
5. Отрезок аппроксимации [a, b] определяет список (a, b).
6. Параметр n алгоритма является целым числом.
Структура данных на выходе. Многочлен yn (3) имеет коэффициенты – числа
и вид, естественный для математики, d + ... + f * x^n.
APLAN-nроцедура. Алгебраическая спецификация п. 2 алгоритма 1.
y1_n := d_x(y_n); /* y'_n */
y2_n := d_x(y1_n); /* y"_n */
....
fy_n := subs((y=y_n, y1=y1_n,...), fy)); /* f(x,y_n,...) */
F_s := Cheb_interpol(fy_n , interval , n); /* U_n[fy_n] */
LDUMK := ( Dy + (-1) * F_s = 0 );
APLAN-процедура – реализация алгоритма [3].
Структура выхода операторов APLAN-процедуры.
Процедура вычисляет начальное приближение yn,0 (4) – многочлен с числовыми
коэффициентами вида, естественного для математики.
Алгоритм для решения нелинейных краевых задач по -методу Ланцоша...
«Штучний інтелект» 4’2009 127
3Д
На каждой итерации (s) процедура вычисляет:
– производные многочлена yn,s-1 вида, естественного для математики,
– функцию fs = f( x, y, y', …, y(k-1) ) |y=y_{n,s-1} естественного вида,
– многочлен Fs = Un[ fs ] естественного вида,
– ЛДУМК (7) вида [3] A*dif(y, k) + ... + C * y + -1 * F_s = 0,
– следующее приближение yn,s к решению исходной краевой задачи (1), (2) – много-
член с числовыми коэффициентами вида, естественного для математики.
11. Исследование APLAN-процедуры
Теорема 2. Сложность выполнения одной итерации алгоритма 1 APLAN-про-
цедурой с ростом параметра n возрастает как полином
(m+1) Q( canplf, m ) + O( n3 ), m = max { deg( D[ yn Pn ] ), n } + k = n + O(1),
где Q( canplf, m ) – сложность преобразования оператором canplf многочлена по-
рядка m к каноническому виду – сумме мономов вида c(i)*x^j$b, i, j = 0, …, m.
Доказательство. Процедура вычисления одной итерации решения линейная. По-
этому вычислительная сложность этой процедуры тождественна сумме вычислительной
сложности операторов этой процедуры. Вычислительная сложность APLAN-процеду-
ры, реализующей алгоритм [3], оценена в работе [3]. Остальные операторы процедуры
имеют по параметру n полиномиальную сложность O(ns), s 3.
12. Вычислительный эксперимент с процедурой
Описание краевой задачи (21) на языке APLAN.
process[1] := ( Dy := dif(y , 2) + -1 * y;
fy := exp(y) + -1 * y;
Cond := ( ( x = 0 , y = 0 ) , ( x = 1 , y = 0 ) );
interval := (0 , 1) ; ...);
Результаты решения задачи (21) процедурой (n = 2).
fy_n := subs((y = y_n, y1 = y1_n,...), fy)) = 1;
F_s := Cheb_interpol(fy_n , interval , n) = 1;
LDUMK := ( Dy + -1 * F_s = 0 ) =
(dif (y , 2) + -1 * y + -1 = 0);
... y_n := ser(n,Coef) = 0.470588 * x ^ 2 + -0.470588 * x ;
F_s := Cheb_interpol(fy_n , interval , n) =
-0.0266273 * x ^ 2 + 0.0266273 * x + 1 ;
LDUMK := ( Dy + -1 * F_s = 0 ) = (dif (y , 2) + -1 * y +
0.0266273 * x ^ 2 + -0.0266273 * x + -1 = 0);
... y_n := ser(n,Coef) = 0.472155 * x ^ 2 + -0.472155 * x ;
... y_n := ser(n,Coef) = 0.472165 * x ^ 2 + -0.472165 * x ;
13. Программирование алгоритма 1 в СКА
Построенная выше APLAN-процедура доказывает – алгоритм 1 имеет алгебраи-
ческие преобразования и его можно реализовать в других СКА. Результаты исследо-
вания этой процедуры доказывают эффективность такой реализации.
Денисенко П.Н.
«Искусственный интеллект» 4’2009 128
3Д
14. Решение практической задачи – задачи Прагера
Задача о деформации упругой струны под действием поперечной нагрузки.
Конечные деформации упругой струны под действием поперечной нагрузки хорошо
моделирует краевая задача
y'' = 1 + a2 (y')2, y(0) = 0 , y(1) = 0. (25)
Эту задачу предложил В. Прагер для оценки эффективности метода квазилинеариза-
ции [4, с. 43]. Задача (25) имеет единственное решение – функцию, аналитическую в
окрестности отрезка [0,1] комплексной плоскости
y = 1/a2 ln( cos( a (x-1/2) ) / cos( a/2 ) ). (26)
Свойства функции y (26). Отличные от нуля коэффициенты Фурье – Чебышева
функции y (26) и функции y'' на отрезке [0,1] только четные. В случае параметра 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 } ,
{ a2 i(y'' , [0,1]) }i = 0
10 = { -1.1 , -0.067 , -0.0014 , 2.5 10-5 , -4 10-7 ,
–6.3 10-9 , -9.5 10-11 , -1.4 10-12 , 2 10-14 , -2.6 10-16 , 4.4 10-17 }. (27)
С возрастанием параметра n = 2 i они регулярно убывают к нулю, аналогично функ-
ции (10). Следовательно, для величины наилучшего приближения функции y (26) с
параметром a = 0.7 алгебраическими многочленами порядка n в пространстве C[0,1] и
в пространстве C2
[0,1] справедливы аналоги тождеств (12).
Вычислительный эксперимент с алгоритмом 1. Норма в пространстве C[0,1]
и C2
[0,1] погрешности решения по алгоритму 1 задачи (25) с параметром a = 0,7 удов-
летворяет тождества
{ || y - y2 i ||C[0,1] }i =1
5 = { 0.006 , 3.7 10-5 , 1.8 10-7 , 1.8 10-9 , 4.8 10-11 } ,
{ || y - y2 i ||C^2_[0,1] }i = 1
5 = { 0.07 , 0.0014 , 2.5 10-5 , 4.1 10-7 , 10-8 }. (28)
Из тождеств (27) и (28) можно сделать следующее заключение.
Вывод 9. Главной частью коэффициента оптимальности решения по алгорит-
му 1 краевой задачи (25) в пространствах C[0,1] и C2
[0,1] являются отношения
|| y – yn ||C[0,1] / | a2 [n/2] + 2(y , [0,1]) | = C2 [n/2], {C2 i }i =1
5 = { 18, 13, 6.(6), 6.(6), 6.2 },
||y – yn||C^2[0,1]/|a2 [n/2](y'', [0,1])| = 1 + 2 [n/2], {2 i}i =1
4 = { 0.05, 0.009, 0.004, 0.002 }. (29)
Согласно определению, коэффициент оптимальности метода вычисления алгебраи-
ческого многочлена, аппроксимирующего решение краевой задачи (1), (2), не меньше
единицы. Поэтому, из этих тождеств и тождества (12) можно сделать следующее зак-
лючение.
Вывод 10. Главная часть коэффициента оптимальности решения по алгорит-
му 1 краевой задачи (25) с параметром a = 0.7 :
– в пространстве C[0,1] ограничена и справедливо тождество
Cn( algorithm_1, (25), a = 0.7, C[0,1] ) = (1 + n) C2 [n/2], n > 1 | n | 0.015,
– в пространстве C2
[0,1] асимптотически тождественна минимальному значению
коэффициента оптимальности и справедливо тождество
Cn( algorithm_1, (36), a = 0,7, C2
[0,1]) = (1 + n) (1 + 2 [n/2]), n > 2 | n | 0.015.
Сравнение алгоритма 1 и метода квазилинеаризации на задаче Прагера.
На краевой задаче (25) с параметром a = 0.7, согласно [4, с. 42], метод квазилинеа-
ризации имеет погрешность 3 10-6. Поэтому из тождеств (27) – (29) можно сделать сле-
дующее заключение.
Вывод 11. На краевой задаче (25) (a = 0.7) главная часть коэффициента опти-
мальности метода алгебраической интерполяции сеточного решения метода квази-
линеаризации (14) (q = 10) более чем в 1 000 000 раз больше 1 + 2 [n/2] (29) – главной
части коэффициента оптимальности алгоритма 1 на этой задаче
C10(P10[ yh ], task (25), a = 0.7, C[0,1]) 3 10–6 / 2.9 10–12 > 106.
Алгоритм для решения нелинейных краевых задач по -методу Ланцоша...
«Штучний інтелект» 4’2009 129
3Д
Заключение
Построенный в работе алгоритм 1 имеет только алгебраические преобразования
и решает весь класс краевых задач для обыкновенных дифференциальных уравнений
порядка k вида (1), (2) с коэффициентами линейного оператора D[ y ] (1) – многочле-
нами и достаточно широким классом функций f( x, y, y',…, y(k-1) ). По этому алгоритму
в СКА вычисляют алгебраический многочлен yn порядка n N – аппроксимацию реше-
ния y = y(x), x [a, b], исходной краевой задачи (1), (2). Эта аппроксимация оптимальна
для символьных преобразований функции y(x), x [a,b] и её производных y', …, y(k) –
в пространстве Ck
[a,b] ограничен коэффициент оптимальности алгоритма 1. Следова-
тельно, на краевой задаче (1), (2) алгоритм 1 реализует идею К. Ланцоша. На основа-
нии -метода построить эффективные алгоритмы для вычисления алгебраических
многочленов – аппроксимации решения функциональных уравнений отдельных типов.
Дополнение
1. Алгоритм 1'. Модификация алгоритма 1. Алгоритм 1 [3] заменен алгоритмом 1' [3].
Это алгоритм -метода c базисом пространства H[a, b].
2. Для алгоритма 1' имеют место аналог теоремы 1 и аналоги применения тео-
рем [3]. В аналогах пространство L2(a,b; ) заменено пространством H[a, b].
3. Модификация APLAN-процедуры. Процедура – реализация алгоритма 1 [3] –
заменена процедурой – реализацией алгоритма 1' [3]. Она реализует алгоритм 1'.
4. Оценка погрешности алгоритма 1 в комплексной плоскости следует из тож-
деств теорем [3].
5. Оценка погрешности алгоритма 1' в комплексной плоскости следует из тож-
деств аналогов теорем [3].
Литература
1. Ланцош К. Практические методы прикладного анализа / Ланцош К. – М. : ФМ., 1957. – 584 c.
2. Пашковский С. Вычислительные применения многочленов и рядов Чебышева / Пашковский С. –
М. : Наука, 1983. – 384 с.
3. Денисенко П.Н. Алгоритм решения краевых задач в системах компьютерной алгебры по -методу
Ланцоша / П.Н. Денисенко // Искусственный интеллект. – 2008. – № 1. – C. 38-48.
4. Беллман Р. Квазилинеаризация и нелинейные краевые задачи / Р. Беллман, Р. Калаба. – М. : Мир,
1968. – 183 c.
5. Красносельский М.А. Приближенное решение операторных уравнений / Красносельский М.А., Вай-
никко Г.М. и др. – М. : Наука, 1969. – 456 c.
П.М. Денисенко
Алгоритм для розв’язування нелiнiйних крайових задач
за -методом Ланцоша в системах комп’ютерної алгебри
Побудовано алгебраїчний алгоритм для перетворення багатоточкової лiнiйної крайової задачi для
диференцiального рiвняння порядку k з лiнiйною частиною – лiнiйний диференцiальний оператор з
коефiцiєнтами – многочленами та нелiнiйною – функцiя f( y, y',…, y(k-1) ) на алгебраїчний многочлен порядку
n N. Цей многочлен – апроксимацiя розв’язку y(x), x [a,b] оригiнальної крайової задачi. Ця апроксимацiя
оптимальна в просторi Ck
[a,b].
P.N. Denisenko
Solving the Nonlinear Boundary-Value Problem Using the Lanczos
-Method in the Computer Algebra Systems
We constructed the algebraic algorithm for transforming the nonlinear boundary-value problem into the algebraic
polynomial of order n N. This polynomial is the solution y(x), x [a,b] approximation for the problem.
This approximation is optimal in the space Ck
[a,b].
Статья поступила в редакцию 16.06.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8166 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T17:31:09Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Денисенко, П.Н. 2010-05-14T08:25:12Z 2010-05-14T08:25:12Z 2009 Алгоритм для решения нелинейных краевых задач по Ʈ-методу Ланцоша в системах компьютерной алгебры / П.Н. Денисенко // Штучний інтелект. — 2009. — № 4. — С. 119-129. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8166 681.142.2/518.3 Построен алгебраический алгоритм для преобразования многоточечной линейной краевой задачи для дифференциального уравнения порядка k с линейной частью – линейный дифференциальный оператор многочленными коэффициентами порядка k и нелинейной частью – функция f( y, y',..., y^(k-1) ) в алгебраический многочлен порядка n (n принадлежит N). Этот многочлен – аппроксимация решения y(x), x принадлежит [a,b], исходной краевой задачи. Эта аппроксимация оптимальна в пространстве C^k[a,b]. Побудовано алгебраїчний алгоритм для перетворення багатоточкової лiнiйної крайової задачi для диференцiального рiвняння порядку k з лiнiйною частиною – лiнiйний диференцiальний оператор з коефiцiєнтами – многочленами та нелiнiйною – функцiя f( y, y',…, y^(k-1) ) на алгебраїчний многочлен порядку n (n належить N). Цей многочлен – апроксимацiя розв’язку y(x), x належить [a,b], оригiнальної крайової задачi. Ця апроксимацiя оптимальна в просторi C^k[a,b]. We constructed the algebraic algorithm for transforming the nonlinear boundary-value problem into the algebraic polynomial of order n (n belongs N). This polynomial is the solution y(x), x e [a,b] approximation for the problem. This approximation is optimal in the space C^k[a,b]. ru Інститут проблем штучного інтелекту МОН України та НАН України Системы принятия решений, планирования и моделирования Алгоритм для решения нелинейных краевых задач по τ-методу Ланцоша в системах компьютерной алгебры Алгоритм для розв’язування нелiнiйних крайових задач за τ-методом Ланцоша в системах комп’ютерної алгебри Solving the Nonlinear Boundary-Value Problem Using the Lanczos τ-Method in the Computer Algebra Systems Article published earlier |
| spellingShingle | Алгоритм для решения нелинейных краевых задач по τ-методу Ланцоша в системах компьютерной алгебры Денисенко, П.Н. Системы принятия решений, планирования и моделирования |
| title | Алгоритм для решения нелинейных краевых задач по τ-методу Ланцоша в системах компьютерной алгебры |
| title_alt | Алгоритм для розв’язування нелiнiйних крайових задач за τ-методом Ланцоша в системах комп’ютерної алгебри Solving the Nonlinear Boundary-Value Problem Using the Lanczos τ-Method 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/8166 |
| work_keys_str_mv | AT denisenkopn algoritmdlârešeniânelineinyhkraevyhzadačpoτmetodulancošavsistemahkompʹûternoialgebry AT denisenkopn algoritmdlârozvâzuvannâneliniinihkraiovihzadačzaτmetodomlancošavsistemahkompûternoíalgebri AT denisenkopn solvingthenonlinearboundaryvalueproblemusingthelanczosτmethodinthecomputeralgebrasystems |