авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«Омский филиал Федерального государственного бюджетного учреждения науки Института математики им. C.Л. Соболева Сибирского отделения Российской Академии Наук ...»

-- [ Страница 2 ] --

Пусть (0, ) = [(0) ]. Существует константа 1 такая, что Лемма 2.10.

) ( (2.31) (, ) [] 1 2 + 1, 0.

Применяя на заданной -ой итерации (2.27) схему (2.25), получим Доказательство.

соотношение:

( ) ( ) (, ) ( ) 1 (, ) + 1+ + 1 + 2 (1 + 1/ ) 2 1 + 1/,, (2.32) ++1 (, ) = (, (1) ) (1) + (, (1) ) ( ), 2 (1 + 1/ ) ( (, (1) ) (1) ) ( ) 1 (, ) (, ) (1) +, =, =, 2 1 + 1/, () где = () ( ).

К схеме (2.32) можно применить теорему 2.2, тогда получим (2.33) (, ) [() ] 2, 0.

Пусть (, ) = (, ) (, ). Поставим задачу относительно (, ) :

(, ) (, ) (2.34) (, ) = (1, ) = 1,..., 1,, 0 = 0, = 0, где соответствует (2.29) и (1, ) = (1 + 1 3 ) (, (1, ) ) (, (1) ) + ( ) ( ) (1, ) (1) ) (+1, +1 ) +2 (+1, + ( ) (1, ) (1) ( (1, ) (1) ) (1 + 1 3 ) 2 +1 +1.

Используя теорему Лагранжа о среднем и учитывая (2.26), получим:

(1, ) (1 + 1 3 + 2 ) ( ) (1, ) [(1) ].

Введём сеточную функцию:

( ) (1, ) [(1) ] ± (, ).

= 1 Несложно убедиться, что = = 0. Следовательно, из 0, 0, 0 принципа максимума, получим 0. Значит, ( ) (, ) (, ) (1, ) [(1) ].

[ ] Используя (2.33), придём к неравенству:

ln ( ) (2.35) (, ) () (1, ) (1) [ ] 1 [ ] + 2.

Так как (0, ) = [(0) ], из (2.35) следует, что для любого 0 :

1 ( ) ln2 ln (, ) () [ ] 2 2.

2 =0 Использование неравенства (2.28) завершает доказательство леммы.

Оценка (2.31) соответствует точности решения задачи (2.1) на основе итераций (2.29), на произвольной -ой итерации.

В (2.29) можно перейти к пределу при, тогда получим разностную схему для нелинейной задачи (2.1):

( ) +1 + +1 + ( ) L =, + +1 1 + 1/+1 +1 1 +, (2.36) (, ) ( ) 1 (, ) (, ) =, =.

= 0, 0 2 (1 + 1/ ) 2 1 + 1/, Пусть — решение схемы (2.36), (, ) — решение на -ой ите Лемма 2.11.

рации метода (2.29) при (0, ) =. Тогда ) ( (2.37) (, ) 1, 0.

Пусть () = (, ). Тогда Доказательство.

() () (2.38) () = (1, ), 0, 0 = 0, = 0, где соответствует (2.29) и (1, ) (1, ) ) (, ) (1, ) + ( ( )) = (1 + 1 3 ) (, ( ) ( ) (1, ) (1, ) ) (+1, +1 ) 2 +1 +1.

+2 (+1, + Из теоремы Лагранжа о среднем следует:

(1, ) (1 + 1 + 2 3 ) ( ) (1, ).

Применяя принцип максимума к задаче (2.38) и используя последнее неравенство, получим: ( ) (2.39) (, ) (1, ).

Требуемое неравенство (2.37) следует из (2.39).

Из лемм 2.10 и 2.11 вытекает следующая теорема.

Пусть () — решение задачи (2.1), — решение схемы (2.36).

Теорема 2.3.

Найдется постоянная 3 такая, что ln [] 3.

Оценим количество арифметических действий, необходимых для нахождения решения схемы (2.36) на основе (2.29). Чтобы погрешность итерационного метода не преобладала над погрешностью схемы (2.36), итерации (2.29) продолжаем до выполнения условия:

ln (2.40) (, ), =.

Учитывая оценку (2.37), заключаем, что для этого потребуется число итераций:

( ) (2.41) ln ln.

На каждой итерации схему (2.29) можно разрешить методом прогонки. Пусть — количество арифметических действий, необходимое для реализации одной итерации. Тогда для выполнения условия (2.41) потребуется количество арифметических действий:

( ) (2.42) ln ln 1.

2.2.3. Линеаризация Ньютона Рассмотрим подход к решению задачи (2.1) на основе линеаризации Ньютона:

() = (() ) + ()(() ) (, (1) )() = (2.43) = (, (1) ) (, (1) )(1), () (0) =, () (1) =.

Введём обозначения = (0), | (, )|.

= max, || 0 + Известно, что метод Ньютона квадратично сходится при достаточно хорошем началь ном приближении. В соответствии с [91] справедлива следующая лемма.

Пусть () — решение задачи (2.1), () () — решение задачи (2.43) Лемма 2.12.

при заданном и выполнено условие 1 1. Тогда (2.44) 1 (1 )2, () 0.

Перейдем от (2.43) к итерациям на разностном уровне, применяя схему (2.25):

( ) (, ) ( (, ) = + +1 (, ) (, (1, ) )+, 1 +, (1, ) 2 (, (1, ) ) ( ) (, )1 ) (, ) = (, (1, ) ) + + 2 (1 + 1/ ) 2 1 + 1/, (2.45) (1, ) ( (, ) (, (1, ) ) (1, ) (, (1, ) ) + 2 (1 + 1/ ) ) (, (1, ) )(1, ) + ( (, (1, ) ) (, (1, ) )(1, ) ) ( ) (, ) (, ) +, 0 =, =.

2(1 + 1/), Пусть в (2.45) (0, ) = [(0) ]. Существуют 0 и 0, не зависящие Лемма 2.13.

от, такие, что для 0 и 0 для некоторой постоянной 4 выполнится:

2 (2.46) + 1 (1 )2, |(, ) [] 4 0.

На произвольной -ой итерации к задаче (2.43) применим схе Доказательство.

му (2.25) и получим:

( ) (, ) (1) )) ( (, ( +1 (, ) (, (1) ) +, + + 1 + 2 (1 + 1/ ), (, (1) ) ( ) 1 ) (, ) = (, (1) ) (, (1) )(1) + + 2 1 + 1/, (2.47) (1) (, ) ( (, (1) ) (, (1) )(1) + ) + 2 (1 + 1/ ) ( (, (1) ) (, (1) )(1) ) ( ) 1 (, ) (, ) +, =, =, 2 1 + 1/, () где = () ( ).

К схеме (2.47) можно применить теорему 2.2, тогда получим:

(2.48) (, ) [() ] 5, 1.

Оценим (, ) (, ). Введём (, ) = (, ) (, ), тогда (, ) (, ) (2.49) (, ) = (1, ) = 1,..., 1,, 0 = 0, = 0, где оператор соответствует (2.45) и [ ( (1, ) (1, ) ) (, (1) ) + 1 (, (1, ) ) = (, ) ( ) (1, ) (1) 2 (, (1) ) + 2 (+1, +1 ) (+1, +1 ) ) ] ( 3 (, (1, ) ) (, (1) ) (, ) + + (, (1, ) ) (, (1) )+ ( +1 (, (1, ) ) (, (1, ) ) (, (1) ) (, (1) ) + ) ) ( (2.50) ( (1,) (1) (1,) +2 (+1, +1 ) (+1, +1 ) 3 (, ) ) ( (, (1) ) (, (1, ) ) (1, ) (, (1) )(1) ) ( 2 (1, ) (1, ) (, (1) )(1) ) 1 (, ) ( ) (1, ) (1, ) (1) (1) 2 (+1, +1 (+1, +1 )+ )+1 + ( +3 (, (1, ) )(1, ) (, (1) )(1).

) Используя теорему Лагранжа, преобразуем слагаемые в (2.50) следующим образом:

(, (1, ) ) (, (1, ) ) (, (1) ) (, (1) ) = (1, ) ( (1, ) (1) ) = (, ) (, ) + (1) ( (1, ) (1) ) + (, ) (, ), (, (1, ) )(1, ) (, (1) )(1) = (1, ) ( (1, ) (1) ( (1, ) (1) (1), ) ) = (, ) + (, ) 2 (, (1, ) )(1, ) (, (1) )(1) = 2 (1, ) ( (1, ) (1) ) = (, ) + ) ( ( (1, ) (1) (1, ) ) + (, (1) ) (1), ) + (, ) (, (1, ) (1, ) (1) (1) (, (+1, +1 )+1 ) = ( +1 +1 )+ (1, ) (1, ) (1) + = (+1, +1 ) +1 + ( ) (1, ) (1) (1) + + (+1, +1 ) +1 +1, (1, ) (1) (1, ) (1) где, [ ] и +1 [+1, +1 ]. Под принадлежностью величины 1 2, интервалу здесь и далее подразумеваем, что эта величина находится в заданных границах, чтобы не писать более сложные логические условия.

Используя полученные выше преобразования и теорему Лагранжа, получим, что после приведения подобных (2.50) будет иметь вид:

( ) ( ) (1) (1, ) (1) (1, ) = 2 (+1, +1 ) (, ) + + +1 + ( ) ( ) (1, ) (1, ) (1) 3 +2 (+1, +1 ) +1 +1 + +1 + (2.51) +5 (, ) (, ) () + () (1) (1, ) (1) + ( ) ( ) + 4 (, )( (1,) )+1 (, (1) ) (, ) (1,) (1), 3 2 ( )( ) (1,) (1) (1,) (1) (1,) где ], +1, +1 [), +1 ], ) 3, 3 2 [, 4 = 1 + 1 (, + ( (1, ) (1) ) 3.

5 = 1 + 1 (, ) + (, (, ) (1) Распишем следующим образом:

+ ) ( () ) (1) (1) (2.52) (, ) +1 (, ) () ) ( () () ( + ( ) (+1 ) + +1 + =.

Учитывая, что для функции () справедливы оценки производных (2.3), получим:

+ + ( () ) ( () ) () () (+1 ) ( ) = () () (2.53) +1( + ) 1 1 4 ln 0 + 1 0 +1 +.

Поясним (2.53). В случае +1 выполнено:

+ 1 +1 4 ln =.

В случае +1 очевидно, что, поэтому + 1 1 ( 1 1 4 ln + ) = 1 =.

Итак, из (2.51) — (2.53) следует:

4 ln () ( (1, ) 2 (, ) [() ] + + (1) + ) + [(1) ] (1, ) (1, ) [(1) ] + ( + 5 (, ) [() ] + 5 () (1) + 4 [(1) ] (1, ) + ) +1 (1, ) [(1) ].

Применяя принцип максимума к задаче (2.49), используя последнее неравен ство, (2.48) и (2.30), в результате получим, что для некоторой постоянной 6 выполнится:

( ln2 ln () (, ) [() ] + (1) + 6 + 2 (2.54) + 5 ln.

) (1, ) (1, ) (1) (1) [ [ + ] ] Выбираем 0 так, чтобы для 0 было выполнено 1 1 и 6 1/16. Учи тывая (2.44), для 1 получим:

6 () (1) 6 () + 6 (1).

Выбираем 0 так, чтобы для 0 было выполнено:

ln ln 1 и (2.55) 2 6 5 6.

8 С учетом ограничений на 0 и 0 из (2.54) для 1 получим:

ln (, ) [() ] 5 + (2.56) ( ) 1 (1, ) (1, ) (1) [(1) ].

[ + + 6 ] Далее, используя метод математической индукции, докажем, что ln (2.57) (, ) () [ ] 2 5, 1.

Пусть = 1. Учитывая условие (0, ) = [(0) ], из (2.56) получаем:

ln (1, ) [(1) ].

Теперь сделаем индуктивное предположение, что для неравенство (2.57) вы полнено. Учитывая ограничения (2.55), докажем, что оно верно и для = :

( ) (, ) () (1, ) (1) ] (1, ) [(1) ] + [ ] + 6 [ ln2 ln2 ln2 ln2 ln ( ) +5 + 25 6 25 + 5 25, 2 2 2 2 что завершает обоснование неравенства (2.57).

Теперь утверждение леммы следует из неравенств (2.44), (2.57).

Переходя в (2.45) к пределу при, получим разностную схему для зада чи (2.1):

+1 (+1, ) ( ) + L +1 (+1 ) = + +, 1 + + +1 1 + 1/+, (2.58) (, ) ( ) 1 (, ) (, ) (, ) = 0, =, =.

0 2 (1 + 1/ ) 2 1 + 1/, Покажем, что итерационный метод (2.45) сходится к решению схемы (2.58).

Пусть — решение задачи (2.58), (, ) — сеточная функция, соот Лемма 2.14.

ветствующая -ой итерации метода (2.45) и = (0, ). Существуют констан ты 0 и 0, не зависящие от, такие что при 0 и 0 выполнится (2.59) 2, (, ) 0.

Пусть (, ) = (, ). Тогда Доказательство.

(, ) (, ) (2.60) (, ) = (1, ), 0, 0 = 0, = 0, где соответствует (2.45) и (1, ) = (1 3 ) (, (1, ) ) (, ) ( ) (1, ) ) (1, ) + ( ) (1 3 ) (, ( +1 (, (1, ) ) (, (1, ) ) (, ) (, ) ) 1 (, (1, ) ) (1, ) + ( ) (2.61) ) ( (1, ) ) (+1, ) +2 (+1, +1 + ( ) (1, ) (1, ) (+1, ) 2 (+1, +1 )+1 +1 +1 + ( ) (1, ) ) (+1, ).

+2 (+1, +1 +1 Используя теорему Лагранжа, преобразуем слагаемые в (2.61):

(, (1, ) ) (, (1, ) ) (, ) (, ) = (1, ) ( (1, ) + (, ) (, ) (1, ), ) ( ) = (, ) (, ) (2.62) (1, ) (1, ) (+1, ) = (+1, +1 )+1 +1 + ( ) ( ) (1,) (1,) (1,) 1 + (+1, ) +1 +1 + = (+1, +1 ) +1 +1, + (1, ) (1, ) где, [, ] и +1 [+1, ].

1 2 + Учитывая (2.62) и применяя теорему Лагранжа, получим, что после приведения по добных (2.61) будет иметь вид:

(1, ) = 4 (, ) (1, ) ( 2 ) ( (1, ) + ) +1 (, ) (, ) (1, ) + ( ) ( (2.63) ) ) (1, ) +2 (+1, +1 ) + ( + + + ( ) ( ) (1, ) (1, ), 2 (+1, +1 ) +1 + +1 (1, ) (1, ) (1, ) где [, ], +1, +1 [+1, ], 4 = 1 + 1 (, ) 3.

3 2 + (1, ) Распишем следующим образом:

+1 (1, ) (1, ) (1) (1) = (+1 (1) ) + ((1) (1, ) ) + ((1, ) ).

+1 ) + (+ +1 Используя (2.63), (2.53), получим, что для некоторой постоянной 7 выполнится:

( ) ln (, ) (1, ) (1, ).

7 + Выбираем 0 и 0 таким образом, чтобы при 0 и 0 имели место нера венства 7 ln / 1 /4 и 7 1 /4.

Используя метод математической индукции, докажем (2.59).

В соответствии с выбором 0 и 0 для 1 выполнено:

( ) (, ) (1, ) (1, ).

7 + Пусть = 1. Учитывая, что 7 1 /4, получаем:

( ) 21.

(1, ) 7 + Теперь сделаем предположение, что неравенство (2.59) выполнено для всех.

Докажем, что это неравенство верно и для = :

( ) 1 7 (1, ) + (, ) (1, ) ( ) 2(1) 2, 7 + что завершает доказательство леммы.

Из лемм 2.13 и 2.14 вытекает следующая теорема.

Пусть () — решение задачи (2.1), — решение схемы (2.58).

Теорема 2.4.

Найдется постоянная 8 такая, что ln (2.64) [] 8.

Оценку (2.46) можно использовать для анализа точности решения исходной зада чи (2.1) на основе применения линеаризации Ньютона и модифицированной схемы А. А. Са марского. В частности, итерации метода Ньютона необходимо продолжать, пока не выпол нится условие:

2 1 (1 ).

Из этого соотношения можно оценить необходимое количество итераций:

ln(1 ) log2.

ln(1 ) По аналогии с реализацией метода Пикара оценим необходимое количество арифме тических действий для решения задачи (2.1):

ln(1 ) log2.

ln(1 ) 2.2.4. Двухсеточная реализация схемы Самарского Количество арифметических действий, необходимых для реализации методов Пикара и Ньютона, можно существенно сократить при использовании двухсеточного метода. При таком подходе исходная задача (2.1) сначала решается на достаточно грубой сетке. Затем найденное сеточное решение необходимо интерполировать на исходную сетку и принять за начальное приближение итерационного метода. Это приведет к уменьшению количества ите раций на исходной сетке и к выигрышу в количестве арифметических действий.

Итак, пусть — сетка Шишкина, соответствующая (2.24) и содержащая сеточных интервалов, где выбираем. Тогда предварительно решаем задачу (2.1) на сетке.

Итерации Пикара или Ньютона на сетке продолжаем до выполнения неравенства:

ln (2.65) (, ), =.

Далее найденное на сетке сеточное решение (, ) интерполируем в узлы ис ходной сетки с помощью кусочно-линейной интерполяции:

( 1 ), ([], ) = 1 + 1, 1.

В соответствии с [21] на сетке Шишкина точность формулы линейной интерполяции равномерна по параметру и для некоторой постоянной 9 выполнено:

ln (2.66) ([], ) () 9.

Интерполяционная формула устойчива к возмущению, поэтому можно интерполи ровать сеточную функцию (, ), при этом [] (, ) 10.

Теперь зададим начальное приближение для итераций на исходной сетке :

(0, ) = [((, ), )].

Тогда для некоторой постоянной 11 имеет место неравенство:

(0, ) 11.

Итак, c помощью итераций на вспомогательной сетке и линейной интерполяции по строено начальное приближение (0, ) для итераций на сетке с точностью ( ). Оста ется осуществить итерации на сетке до достижения точности ( ).

Оценим количество арифметических действий в случае двухсеточного метода Пикара:

ln( /) ln( / ) + +, ln(1 /) ln(1 /) где — количество арифметических действий, необходимое для интерполяции сеточного решения с вспомогательной сетки на исходную.

Учитывая (2.42), оценим выигрыш в количестве арифметических действий при при менении двухсеточного метода Пикара:

( ).

ln ln(1 /) В случае двухсеточного метода Ньютона:

ln(1 ) ln(1 ) log2 + log2 +, ln(1 ) ln(1 ) ln(1 ) ( ) log2.

ln(1 ) 2.2.5. Результаты численных экспериментов Рассмотрим краевую задачу:

() + () () = 0, (0) =, (1) =, где,, () соответствуют решению () = +.

+ Отметим, что выполнены ограничения 1/2 2 при 0 1.

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

max |L (, ) |, которое, в чем можно убедиться, обеспечивает выполнение оценки (2.40).

Норма погрешности = [] схемы (2.58), реализованной на основе односе точного метода Ньютона (2.45), при различных значениях и приведена в табл. 2.7.

Таблица 2. Погрешность метода, основанного на линеаризации Ньютона 6 7 29 210 211 2 2 1 1.44–5 2.70–6 4.37–7 1.16–6 1.35–6 1.59–8 3.98– 2 2.31–4 5.69–5 1.48–5 4.53–6 2.00–6 1.37–6 5.25– 2 1.79–3 4.74–4 1.25–4 3.52–5 7.66–6 1.92–6 4.81– 2 2.53–3 9.29–4 3.23–4 1.11–4 3.19–5 9.71–6 2.68– 2 2.85–3 1.07–3 3.76–4 1.19–4 3.73–5 1.14–5 3.41– 2 2.97–3 1.13–3 4.03–4 1.28–4 4.03–5 1.23–5 3.69– 2 3.00–3 1.16–3 4.14–4 1.32–4 4.18–5 1.28–5 3.84– 2 2.99–3 1.16–3 4.17–4 1.34–4 4.24–5 1.30–5 3.91– 2 2.98–3 1.16–3 4.17–4 1.34–4 4.25–5 1.31–5 3.94– 2 2.98–3 1.16–3 4.16–4 1.33–4 4.24–5 1.31–5 3.95– 2 2.97–3 1.15–3 4.15–4 1.33–4 4.23–5 1.31–5 3.94– 2 2.97–3 1.15–3 4.15–4 1.33–4 4.22–5 1.30–5 3.93– 2 2.97–3 1.15–3 4.15–4 1.33–4 4.21–5 1.30–5 3.91– 2 2.97–3 1.15–3 4.14–4 1.33–4 4.21–5 1.30–5 3.91– Норма погрешности схемы (2.36), реализованной на основе односеточного метода Пикара (2.29) при = 9 2 для различных и приведена в табл. 2.8. Полученные погрешности соответствуют теоремам 2.3 и 2.4.

Теперь остановимся на результатах применения двухсеточного метода.

Результаты численных экспериментов, соответствующих линеаризации Ньюто на (2.45) при = 102 приведены в табл. 2.9.

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

Таблица 2. Погрешность метода, основанного на линеаризации Пикара 6 7 29 210 211 2 2 1 2.15–4 6.13–5 1.75–5 4.97–6 1.41–6 4.01–7 1.13– 2 3.18–4 1.15–4 4.14–5 1.46–5 5.08–6 1.73–6 5.84– 2 1.07–3 2.91–4 7.98–5 2.18–5 5.93–6 1.61–6 4.34– 2 1.91–3 7.61–4 2.47–4 8.55–5 2.53–5 7.39–6 2.16– 2 2.28–3 9.46–4 3.23–4 1.09–4 3.53–5 1.03–5 3.14– 2 2.29–3 9.91–4 3.73–4 1.20–4 3.88–5 1.21–5 3.50– 2 2.18–3 9.23–4 3.54–4 1.23–4 4.02–5 1.26–5 3.81– 2 2.20–3 8.86–4 3.45–4 1.22–4 4.04–5 1.27–5 3.87– 2 2.38–3 8.60–4 3.35–4 1.19–4 3.98–5 1.27–5 3.88– 2 2.64–3 8.44–4 3.28–4 1.16–4 3.89–5 1.25–5 3.85– 2 2.69–3 8.34–4 3.23–4 1.14–4 3.81–5 1.22–5 3.79– 2 2.72–3 8.29–4 3.20–4 1.13–4 3.76–5 1.20–5 3.73– 2 2.73–3 8.27–4 3.19–4 1.12–4 3.73–5 1.19–5 3.68– 2 2.74–3 8.26–4 3.18–4 1.12–4 3.71–5 1.18–5 3.58– Отметим, что в численных экспериментах точность односеточного и двухсеточного методов существенно не отличались.

Таблица 2. Количество итераций односеточного и двухсеточного методов Ньютона, = 64 128 256 512 1024 2048 16 1(3) 2(3) 2(3) 2(3) 2(3) 2(3) 2(3) 32 1(3) 1(3) 2(3) 2(3) 2(3) 2(3) 2(3) 64 1(3) 1(3) 2(3) 2(3) 2(3) 2(3) 128 1(3) 1(3) 1(3) 2(3) 2(3) 256 1(3) 1(3) 1(3) 1(3) 512 1(4) 1(4) 1(4) 1024 1(4) 1(4) 2048 1(4) 3 3 3 4 4 4 Результаты вычислений для двухсеточного метода Пикара при = 102 и = 9 при ведены в табл. 2.10, по аналогии с табл. 2.9.

Отметим, что и при других значениях параметра был получен выигрыш в числе арифметических действий при применении двухсеточного метода.

Таблица 2. Количество итераций односеточного и двухсеточного методов Пикара, = 64 128 256 512 1024 2048 16 6(11) 8(11) 9(11) 11(11) 13(11) 15(11) 16(11) 32 2(13) 4(13) 6(13) 8(13) 10(13) 12(13) 14(13) 64 2(14) 3(14) 5(14) 7(14) 9(14) 11(14) 128 2(15) 3(15) 4(15) 5(15) 7(15) 256 2(17) 3(17) 3(17) 4(17) 512 3(18) 3(18) 4(18) 1024 3(19) 3(19) 2048 3(20) 14 15 17 18 19 20 При реализации двухсеточного метода решение разностной схемы известно на двух сетках, что можно использовать для повышения точности разностной схемы на основе метода экстраполяции Ричардсона. Далее предполагаем, что вспомогательная сетка вложена в исходную, а, значит, имеет то же значение параметра = min {1/2, 4 ln /}, =, где — целое число.

Пусть 1 = =, = =.

1 На основе экстраполяции Ричардсона на сетке построим сеточное решение за дачи (2.1), которое обозначим как, используя и — решения схемы (2.58) на сетках и соответственно.

Сначала зададим эту функцию в узлах вспомогательной сетки :

( ) = ( ) + ( ),.

В узлах исходной сетки, не совпадающих с узлами сетки, зададим, используя формулу квадратичной интерполяции. Тогда для каждого узла из неко торого сеточного интервала (1, ) получим:

( ) =, ([ ], ).

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

Таблица 2. Количество итераций (слева) и норма погрешности (справа) односеточного и двухсеточного методов Ньютона, = 128 512 2048 4096 8192 128 512 2048 4096 64 2(3) 2(3) 2(3) 2(3) 2(3) 64 1.04–3 1.95–4 2.39–5 7.67–6 2.36– 128 2(3) 2(3) 2(3) 2(3) 128 1.04–4 1.42–5 4.70–6 1.48– 256 1(3) 2(3) 2(3) 2(3) 256 4.43–5 7.37–6 2.54–6 8.28– 512 2(4) 2(4) 2(4) 512 3.64–6 1.32–6 4.47– 1024 1(4) 1(4) 1(4) 1024 1.58–6 6.25–7 2.23– 2048 1(4) 1(4) 2048 2.72–7 1.05– 4096 1(4) 4096 4.67– 3 4 4 4 4 4.41–3 5.34–4 5.27–5 1.59–5 4.69– Результаты численных экспериментов в случае метода Пикара при = 104 и = приведены в табл. 2.12 по аналогии с табл. 2.12.

Таблица 2. Количество итераций (слева) и норма погрешности (справа) односеточного и двухсеточного методов Пикара, = 128 512 2048 4096 8192 128 512 2048 4096 64 2(15) 8(15) 12(15) 14(15) 15(15) 64 1.19–3 1.98–4 2.43–5 7.75–6 2.42– 128 6(16) 10(16) 12(16) 14(16) 128 1.09–4 1.48–5 4.88–6 1.53– 256 2(17) 7(17) 10(17) 12(17) 256 6.10–5 8.54–6 2.78–6 8.98– 512 5(18) 7(18) 9(18) 512 4.32–6 1.60–6 5.40– 1024 2(19) 4(19) 6(19) 1024 2.35–6 9.36–7 3.45– 2048 2(20) 4(20) 2048 4.46–7 1.78– 4096 2(21) 4096 7.92– 16 18 20 21 22 4.08–3 5.13–4 5.16–5 1.57–5 4.65– В табл. 2.13 приведена скорость сходимости схемы (2.58) в зависимости от и при её реализации односеточным методом Ньютона:

= [].

= log2, В последней строке табл. 2.13 приведена теоретическая оценка скорости сходимо сти схемы (2.58) в зависимости от, соответствующая оценке погрешности (2.64).

В табл. 2.14 приведена скорость сходимости схемы (2.58) в зависимости от и при её реализации двухсеточным методом Ньютона с использованием экстраполяции Ричардсона при = /2. В последней строке табл. 2.14 приведена теоретическая оценка скорости сходи мости схемы (2.58) с экстраполяцией Ричардсона в зависимости от, соответствующая оценке (ln3 / 3 ).

Таблица 2. Скорость сходимости в случае односеточного метода Ньютона 128 256 512 1024 2048 4096 10 1.461 1.586 1.646 1.696 1.732 1.760 1. 10 1.460 1.586 1.645 1.695 1.731 1.758 1. 10 1.461 1.586 1.646 1.696 1.732 1.759 1. 10 1.461 1.586 1.646 1.696 1.732 1.759 1. 10 1.461 1.586 1.646 1.696 1.732 1.759 1. 10 1.461 1.586 1.646 1.696 1.732 1.759 1. 10 1.461 1.586 1.646 1.696 1.732 1.759 1. 1.555 1.615 1.660 1.696 1.725 1.749 1. Таблица 2. Скорость сходимости в случае двухсеточного метода Ньютона при использовании экстраполяции Ричардсона 128 256 512 1024 2048 4096 10 2.114 2.419 2.290 2.514 2.583 2.637 2. 10 2.117 2.429 2.297 2.510 2.542 2.543 2. 10 2.118 2.432 2.304 2.530 2.583 2.603 2. 10 2.118 2.433 2.305 2.533 2.592 2.629 2. 10 2.118 2.433 2.305 2.533 2.593 2.633 2. 10 2.118 2.433 2.305 2.533 2.593 2.634 2. 10 2.118 2.433 2.305 2.533 2.593 2.635 2. 2.333 2.422 2.490 2.544 2.587 2.623 2. Итак, численные эксперименты подтверждают оценку точности (2 / 2 ) для предложенных алгоритмов решения задачи (2.1). Применение двухсеточного метода приво дит к уменьшению количества итераций на исходной сетке. Использование метода Ричард сона в двухсеточном методе, практически без дополнительных вычислительных затрат, при водит к повышению точности разностной схемы до (3 / 3 ) при = /2.

Таким образом, разработан метод решения сингулярно возмущен во второй главе ной краевой задачи для нелинейного обыкновенного дифференциального уравнения второго порядка на основе двухсеточного метода на сетках Шишкина. Для схемы направленных раз ностей в двухсеточном методе при использовании экстраполяции Ричардсона получена оцен ка погрешности в зависимости от соотношения между шагами исходной и вспомогательной сеток. Построен и обоснован алгоритм повышенной точности на основе линеаризаций Пикара и Ньютона с применением монотонной схемы Самарского. Предложен двухсеточный метод реализации построенных алгоритмов, приводящих к экономии вычислительных затрат. Экс периментально показано, что экстраполяция Ричардсона приводит к повышению точности схемы Самарского. Результаты вычислительного эксперимента подтверждают полученные теоретические оценки.

Глава Двухсеточный метод решения эллиптического уравнения на сетке Шишкина В настоящей главе рассматривается краевая задача для линейного эллиптического уравнения типа реакция-диффузия и краевая задача для линейного эллиптического урав нения типа конвекция-диффузия с преобладающей конвекцией в случае одного регулярного и двух параболических пограничных слоев и в случае двух регулярных пограничных слоев.

Исследуется двухсеточный метод для реализации построенных схем, приводящий к эконо мии вычислительных затрат. Исследуется экстраполяция Ричардсона для повышения точно сти рассматриваемых разностных схем при использовании двухсеточного метода. Численно исследуются реализации рассматриваемых разностных схем на основе явного метода Зей деля, метода последовательной верхней релаксации, метода Писмана-Речфорда (продольно поперечных прогонок), стабилизированных методов сопряженных направлений и градиен тов, метода Зейделя, учитывающего локализацию пограничных слоев. Проведено сравнение по времени выполнения двухсеточного алгоритма с прямым методом пакета Pardiso.

3.1. Задача реакция-диффузия 3.1.1. Постановка задачи Рассмотрим линейную сингулярно возмущенную эллиптическую краевую задачу:

+ (, ) = (, ), (, ) ;

(3.1) (, ), (, ) = (, ), где = (0, 1)2, =, функции,, — достаточно гладкие, (3.2) (, ) 0, 0.

Известно [58], что при выполнении условий (3.2) решение задачи (3.1) является рав номерно ограниченным и имеет пограничные слои у границ = 0, = 1 и = 0, = 1.

Зададим в области кусочно-равномерную сетку [58]:

, = {(, ),, = 0,, = 1, = 1, 0 = 0, = 1, 0 = 0, = 1}, где 2(1 2 ) 4 3 =,1, ;

=,, 4 4 4 2(1 2 ) 4 3 (3.3) =,1, ;

=,, 4 4 4 { } { } 1 2 1 = min, ln, = min, ln, 0.

4 На заданной сетке, выпишем схему центральных разностей:

( ) ( ) 2 +1,,, 1,,+1,,, + + +1 +1 + +1 +1 (3.4) (, ) = (, ), (, ),,, = (, ), (, ), =,.

, Определим норму непрерывной функции и норму сеточной функции соответ ственно:

= max |, |.

= max |(, )|, 0, (,) Пусть [], – проекция функции непрерывного аргумента (, ) на сетку,.

Отметим, что матрица схемы (3.4) является M-матрицей. В соответствии с [1, 65] вы полнено:

(3.5) = ln2 / 2.

[], 5, 3.1.2. Двухсеточный метод Разностную схему (3.4) запишем в общем виде:

(3.6) =.

Схему (3.4) можно разрешить на основе итераций:

(3.7) (+1) = (() ), где (0) — задано. Матрица системы (3.6) является -матрицей, что обеспечивает сходи мость многих итерационных методов [16, 35]. Пусть для решения системы (3.6) применяется сходящийся итерационный метод и справедлива оценка сходимости итераций:

(3.8) (+1) (), 1.

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

(3.9) ().

Пусть = (0), тогда, учитывая (3.8), несложно заключить, что для выпол нения (3.9) потребуется (3.10) 2 log ( / ) арифметических действий в предположении, что для реализации одной итерации необходимо выполнить 2 арифметических действий (пропорциональное числу неизвестных).

Теперь рассмотрим двухсеточный метод для нахождения решения разностной схе мы (3.4). Введём сетку,, такую же по структуре как,, только с намного меньшим количеством узлов. Предварительно, с использованием итерационного метода (3.7), решаем задачу (3.1) на сетке,. Итерации на сетке, продолжаем, пока не выпол нится условие (3.11) ( ), где – необходимое количество итераций.

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

Пусть (,, ) — интерполянт сеточной функции в области и справедлива оценка погрешности:

(3.12) ([],,, ) 2,, где (, ) — решение задачи (3.1), причем,.

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

(3.13) (,, ) (,, ) 3.

Определившись с формулой интерполяции, можно найденное сеточное решение ( ) интерполировать в узлы исходной сетки,. Пусть = [(( ),, )],.

Покажем, что для некоторой постоянной 4 имеет место следующая оценка:

4.

С учетом неравенств (3.5), (3.11) — (3.13), получим:

(( ),, ) (,, ) + (,, ) ([],,, )+ +[([],,, )], [], + [], 3 + 3 1 + +2, + 1 4.

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

Вычислим необходимое количество арифметических действий двухсеточного метода:

(3.14) 2 log + 2 log +, где – количество арифметических действий, необходимых для интерполяции.

Сравнивая (3.10), (3.14), оценим выигрыш в числе арифметических действий при ис пользовании двухсеточного метода:

( ) 2 ( ) log.

3.1.3. Экстраполяция Ричардсона Исследуем экстраполяцию Ричардсона для повышения точности разностной схемы при использовании двухсеточного метода. Метод экстраполяции Ричардсона для сингулярно возмущенных эллиптических задач исследовался, например, в работах [59, 87, 88]. Рассмот рим случай, когда вспомогательная сетка Шишкина имеет вид (3.24) и содержит сеточных интервалов в раз меньше по каждому направлению, чем исходная сетка, где 1 — целое число.

Решение схемы направленных разностей (3.4) вычисляется на сетке,. Для повышения точности будем также использовать решение этой схемы на сетке,, которая содержит сеточных интервалов и имеет те же параметры,, что и сетка,. Эти сетки вложены так, что, = {(, )}, = {(, )}. Очевидно, что сетку, можно получить из, делением каждой ячейки на равных частей по каждому на правлению.

Обозначим решение схемы (3.4) на, как и пусть 2 2 = = 2, = =2.

2 2 2 1 В соответствии с методом экстраполяции Ричардсона зададим функцию на сет ке,, приближающую решение (, ) с более высоким порядком точности, чем.

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

(, ) = (, ) + (, ), (, ),.

В узлах исходной сетки,, не совпадающих с узлами сетки,, зада дим сеточную функцию (, ), используя интерполяцию. Тогда для каждого уз ла (, ),, принадлежащего некоторой ячейке, = [2, +2 ] [2, +2 ], определим:

(3.15) (, ) = ([ ],,, ), где интерполяционную формулу для ячейки, зададим следующим образом [95], предпо лагая, что кратно четырем и не меньше 16:

) ( 1 ) ([ ],,, ) = (, 1 ) + (, ) (, 1 ) ( + ( 1 ) ( 1 ) ( ) + (, +1 ) 2 (, ) + (, 1 ) ( ) + 2 ( 1 ) (+1 ) ( + (, +2 ) 3 (, +1 ) + 3 (, ) (3.16) ( 2 )( 1 )( ) ) (, 1 ) + 3 (1 2 ) ( 1 ) (+1 ) ( +1 2 + + ( 1 ) ( 1 )( )+ 2 ( 1 ) +2 3+1 + 3 1 ) +( ) 1 ( 2 )( 1 )( ), 3 ( 1 ) где ) ( 1 ) (, ) = (1, ) + (, ) (1, ) ( + ( 1 ) ( 1 ) ( ) + (+1, ) 2 (, ) + (1, ) ( ) + 2 ( 1 ) (+1 ) ( + (+2, ) 3 (+1, ) + 3 (, ) ( 2 )( 1 )( ) ) (1, ) + 3 (1 2 ) ( 1 ) (+1 ) 1 +1 2 + ( + ( ) 1 ( 1 ) ( 1 )( ) 2 ( 1 ) +2 3+1 + 3 1 ) ( 2 )( 1 )( ), 3 ( 1 ) (, +2 ) 4 (, +1 ) + 6 (, ) 4 (, 1 ) + (, 2 ) =, +2 4+1 + 6 41 + (+2, ) 4 (+1, ) + 6 (, ) 4 (1, ) + (2, ) =, +2 4+1 + 6 41 + = ( ), = ( ).

Интерполяция (3.16) является точной на функциях () и (), обладает четвер тым порядком точности и будет полиномиальной при задании () = 4, () = 4. Функ ции () и () можно выбирать в соответствии с пограничными слоями задачи (3.1).

3.1.4. Результаты численных экспериментов Рассмотрим краевую задачу:

+ 2 = (, ), (, ), (3.17) (, ), (, ) = 0, где соответствует решению ( ) ( ) ( ) ( ) 1 1 1 1 (, ) = + sin() sin().

( ) ( ) 1 1 В соответствии с (3.17) зададим и в (3.3), используя значение = 1.

Решение задачи (3.17) находим на основе схемы (3.4). Начальное приближение для используемых итерационных методов задаем следующим образом:

(0) (, ) = 0, (, ),.

Итерационный метод (3.7) на сетке, завершаем, если выполнено условие:

( ), тогда будет выполнена оценка ( ).

Исследуем реализацию схемы (3.4) на основе явного метода Зейделя [35].

Пятиточечную схему (3.6) можно представить как, +, +, +,, =,, 0,.

1,,1 +1,,+1, Тогда векторно-матричная запись метода Зейделя будет иметь вид:

() = 1 + () + (1), ( ) где (), =, 1, +,,1, (), =,,, ( ), =, +1, +,,+1.

Результаты численных экспериментов для метода Зейделя при = 104 приведены в табл. 3.1 и табл. 3.2.

Таблица 3. Количество итераций односеточного и двухсеточного методов Зейделя, = 8 16 32 64 128 256 4 3(2) 7(2) 16(2) 43(2) 135(2) 450(3) 1565(3) 8 6(3) 15(3) 40(4) 126(4) 424(4) 1482(4) 16 13(7) 36(7) 113(7) 385(7) 1357(7) 32 30(15) 98(14) 341(13) 1219(13) 64 82(39) 296(35) 1082(33) 128 247(121) 942(108) 256 788(407) 3 7 17 45 139 463 В табл. 3.1 при различных значениях и указано количество итераций двухсеточ ного метода на исходной сетке,, при этом в скобках приведено количество итераций на более редкой вспомогательной сетке,. В нижней строке указано число итераций односеточного метода в зависимости от.

В табл. 3.2 при различных значениях и приведена норма погрешности двухсеточ ного метода с экстраполяцией Ричардсона (3.15). В нижней строке для сравнения приведена норма погрешности односеточного метода в зависимости от.

Таблица 3. Норма погрешности односеточного метода Зейделя и двухсеточного метода Зейделя с экстраполяцией Ричардсона, = 8 16 32 64 128 256 4 1.17–2 2.60–3 5.00–4 7.43–5 8.29–6 8.71–7 1.18– 8 2.47–3 4.61–4 6.41–5 2.07–5 8.43–6 2.57– 16 1.17–3 4.23–4 1.22–4 2.98–5 6.20– 32 2.74–4 1.21–4 4.62–5 1.59– 64 4.16–5 1.75–5 6.71– 128 4.85–6 1.87– 256 5.27– 3.39–2 2.03–2 8.15–3 3.15–3 1.10–3 3.62–4 1.15– Из табл. 3.2 следует, что экстраполяция Ричардсона (3.15) повышает точность схемы до порядка (ln3 / 3 ).

Помимо метода Зейделя в качестве итерационного метода использовались метод по следовательной верхней релаксации [35]:

() = 1 + () + (1) + (1 )(1) ( ) где – итерационный параметр, а также метод Писмана-Речфорда (продольно-поперечных прогонок) [35]:

(1/2) = (1) + 1 (1/2) + 2 (1), ( ) () = (1/2) + 1 (1/2) + 2 (), ( ) где – итерационный параметр и (1 ), =, 1,,, +, +1,, (2 ), =,,1, +,,+1.

, Здесь, =, +, где, соответствует аппроксимации производных по направлению,, а – по направлению.

, Также использованы итерации в подпространствах Крылова [36, 83], а именно стаби лизированный метод бисопряженных градиентов (BiCGSTAB) и стабилизированный метод сопряженных невязок (BiCRSTAB).

0 = 0, 0 = 0, = 0, 1,...

( ), ( ) =, () () () =, (, ( ) 0 ) (, ) +1 = + () +, () =, (, ) [ ( )] +1, ( ) () () = +1 + () (), () () ( ) +1 =.

[ (, ( ) 0 )] Здесь = 0, 1 для методов BiCGSTAB и BiCRSTAB соответственно, номера итераций ука заны в данном случае нижними индексами [36].

Остановимся подробнее на выборе итерационного параметра в методе последова тельной верхней релаксации. Согласно [35], оптимальное значение релаксационного парамет ра есть (3.18) 0 =, 1 + где – коэффициент подавления ошибки метода Зейделя.

В этом случае можно апостериорно выбрать значение 0, используя следующий ал горитм автоматического определения итерационного параметра [35]. Сначала в методе по следовательной верхней релаксации проводятся итерации при значении = 1 и на каждой итерации вычисляется значение:

=, 1 а также проверяется условие (3.19) | | 1, при некоторой заданной малой величине 1. Когда неравенство (3.19) выполняется, величи на принимается за приближенное значение, после чего по формуле (3.18) определя ется 0, используемое в последующих итерациях. При этом предварительные итерации по методу Зейделя служат для получения достаточно приемлемого начального приближения.

В табл. 3.3 приведены результаты численных экспериментов для метода последова тельной верхней релаксации при = 104 аналогично табл. 3.1. Значение итерационного параметра = 2/(1 + 0.7), т. е. = 0.3.

Таблица 3. Количество итераций односеточного и двухсеточного методов последовательной верхней релаксации, = 104, = 0. 8 16 32 64 128 256 4 4(4) 6(4) 13(5) 36(5) 113(6) 377(7) 1309(7) 8 6(4) 12(5) 34(5) 106(6) 355(7) 1241(7) 16 11(7) 30(7) 95(7) 323(7) 1137(8) 32 25(12) 83(11) 286(11) 1022(11) 64 69(33) 249(30) 907(27) 128 208(102) 790(90) 256 661(341) 4 7 14 38 116 388 В табл. 3.4 приведены результаты численных экспериментов для метода последова тельной верхней релаксации при = 104 аналогично табл. 3.1. Значение итерационного параметра = 2/(1 + 0.3), т. е. = 0.7.

Таблица 3. Количество итераций односеточного и двухсеточного методов последовательной верхней релаксации, = 104, = 0. 8 16 32 64 128 256 4 7(7) 9(8) 14(9) 24(10) 74(11) 247(12) 858(14) 8 9(8) 13(9) 23(10) 70(11) 234(12) 815(14) 16 13(11) 21(11) 63(12) 213(13) 748(14) 32 18(16) 56(16) 189(17) 673(17) 64 47(22) 165(22) 597(23) 128 138(67) 521(59) 256 436(224) 7 11 15 25 76 254 В табл. 3.5 приведены результаты численных экспериментов для метода последова тельной верхней релаксации при = 104 аналогично табл. 3.1. Итерационный параметр выбирался в соответствии с описанным выше алгоритмом автоматического определения зна чения.

Сравнивая результаты работы метода последовательной верхней релаксации с раз личными значениями итерационного параметра в табл. 3.3 — 3.5, приходим к выводу, что предпочтительнее всего по количеству итераций использовать автоматический выбор итера ционного параметра.

Таблица 3. Количество итераций односеточного и двухсеточного методов последовательной верхней релаксации с автоматическим выбором значения итерационного параметра, = 8 16 32 64 128 256 4 4(4) 7(4) 14(4) 23(4) 45(4) 181(4) 322(7) 8 6(4) 12(4) 28(5) 43(6) 83(11) 169(6) 16 12(8) 22(8) 46(8) 108(10) 158(12) 32 23(15) 48(15) 136(15) 245(20) 64 58(31) 95(32) 250(32) 128 106(81) 199(71) 256 215(159) 4 8 15 35 95 186 В табл. 3.6 при = 104 проведено сравнение исследуемых итерационных методов.

Двухсеточный метод используем в случае = /2. Для метода последовательной верхней релаксации итерационный параметр выбирался в соответствии с описанным выше алго ритмом автоматического определения значения, для метода Писмана-Речфорда итерацион ный параметр = 8/.

Таблица 3. Сравнение количества итераций, = Метод 8 16 32 64 128 256 Зейделя 3(2) 6(3) 13(7) 30(15) 82(39) 247(121) 788(407) 3 7 17 45 139 463 верхней 4(4) 6(4) 12(8) 23(15) 58(31) 106(81) 215(159) релаксации 4 8 15 35 95 186 Писмана- 2(4) 3(2) 7(5) 14(12) 28(27) 58(60) 118(130) Речфорда 2 5 11 24 54 119 BiCRSTAB 2(1) 3(2) 6(3) 10(6) 20(13) 41(25) 65(60) 2 4 7 15 31 57 BiCGSTAB 2(1) 3(2) 6(3) 11(6) 20(13) 36(26) 58(54) 2 3 7 13 28 58 Применение методов последовательной верхней релаксации, Писмана-Речфорда, ста билизированных методов бисопряженных направлений и градиентов привело к уменьшению количества итераций по сравнению с методом Зейделя. Повышение точности на основе экс траполяции Ричардсона не зависит от конкретного итерационного метода.

В табл. 3.7 при = 104 для стабилизированного метода бисопряженных градиентов приведено количество итераций и время выполнения двухсеточного (ссверху) и односеточ ного (снизу) методов.

Таблица 3. Количество итераций и время выполнения двухсеточного и односеточного методов N 256 512 1024 количество 36(26) 58(54) 108(97) 189(179) итераций 58 93 207 время 0.86 6.48 49.48 387. выполнения 0.84 8.06 75.16 687. Из табл. 3.7 следует, что с увеличением выигрыш от использования двухсеточного метода растет.

В табл. 3.8 приведена скорость сходимости схемы (3.4) в зависимости от и при её реализации односеточным методом Писмана-Речфорда:

(3.20) = [],.

= log2, В последней строке табл. 3.8 приведена теоретическая оценка скорости сходимо сти схемы (3.4) в зависимости от, соответствующая оценке погрешности (3.5).

Таблица 3. Скорость сходимости в случае односеточного метода Писмана-Речфорда 8 16 32 64 128 1 2.007 2.002 2.000 2.000 2.000 2. 10 2.010 2.003 2.001 2.000 2.000 2. 10 1.882 1.960 1.988 1.997 2.000 2. 10 0.770 1.315 1.508 1.965 1.991 1. 10 0.742 1.314 1.370 1.517 1.604 1. 10 0.732 1.314 1.370 1.517 1.604 1. 0.830 1.170 1.356 1.474 1.555 1. В табл. 3.9 приведена скорость сходимости схемы (3.4) в зависимости от и при её реализации двухсеточным методом Писмана-Речфорда с использованием экстраполяции Ричардсона при = /2. В последней строке табл. 3.9 приведена теоретическая оценка скорости сходимости схемы (3.4) с экстраполяцией Ричардсона в зависимости от, соответствующая оценке (ln3 / 3 ).

Таблица 3. Скорость сходимости в случае двухсеточного метода Писмана-Речфорда при использовании экстраполяции Ричардсона 8 16 32 64 128 1 3.552 3.978 4.000 4.000 3.999 3. 10 3.836 3.596 3.722 3.956 3.974 3. 10 0.734 3.305 2.206 2.074 2.288 2. 10 1.625 0.542 2.307 3.491 2.694 2. 10 2.324 1.021 2.069 2.680 2.975 2. 10 2.107 1.506 2.069 2.680 2.975 2. 1.245 1.755 2.034 2.211 2.333 2. Рассмотрим краевую задачу:

+ 2 = sin(), (, ), (3.21) (, ).

(, ) = 0, Для задачи (3.21) точное решение не задается в явном виде, тем самым пограничные слои формируются, исходя из вида задачи.

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

В табл. 3.10 приведено количество итераций метода Зейделя в зависимости от и, когда в качестве начального приближения во внутренних точках (0) (, ) = 0, (, ),.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и для нулевого начального приближения 8 16 32 64 1 28(9) 112(43) 450(203) 1801(941) 7212(4289) 43 203 941 4289 10 17(6) 64(25) 255(112) 1019(516) 4081(2347) 25 112 516 2347 10 5(3) 14(7) 50(24) 196(98) 786(429) 7 24 98 429 10 3(2) 5(3) 10(6) 30(15) 111(52) 4 7 17 52 104 2(1) 4(3) 9(5) 21(12) 63(31) 3 6 14 39 В табл. 3.11 приведено количество итераций метода Зейделя в зависимости от и, когда в качестве начального приближения во внутренних точках взято решение вырожденной задачи (, ), (, ),,, (0) (, ) (, ) = (, ), (, ),.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и для начального приближения, заданного решением вырожденной задачи 8 16 32 64 1 28(13) 111(57) 443(257) 1775(1156) 7108(5149) 57 257 1156 5149 10 17(7) 64(26) 252(113) 1007(515) 4033(2343) 26 113 515 2343 10 5(3) 14(6) 50(18) 195(75) 781(341) 6 18 75 341 103 3(2) 5(3) 10(5) 30(11) 111(37) 3 6 12 37 10 2(2) 4(3) 9(4) 21(8) 63(22) 3 5 10 27 Из табл. 3.10, 3.11 следует, что в начальное приближение, задаваемое во внутренних точках решением вырожденной задачи, приводит к уменьшению количества итераций по сравнению с нулевым начальным приближением.

Итак, применение двухсеточного метода на сетке Шишкина приводит к выигрышу в количестве арифметических действий, а использование экстраполяции Ричардсона повыша ет точность разностной схемы на порядок с (ln2 / 2 ) до (ln3 / 3 ) вне зависимости от используемого итерационного метода. Исследованы методы Зейделя, последовательной верх ней релаксации, Писмана-Речфорда и стабилизированные методы сопряженных градиентов и направлений, наибольшую скорость сходимости среди которых показали два последних.

3.2. Задача конвекции-диффузии в случае параболических пограничных слоев 3.2.1. Постановка задачи Рассмотрим линейную сингулярно возмущенную эллиптическую краевую задачу:

+ + () (, ) = (, ), (, ) ;

(3.22) (, ), (, ) = (, ), где = (0, 1)2, =, функции,,, — достаточно гладкие, (3.23) () 0, (, ) 0, 0.

Известно [58], что при выполнении условий (3.23) решение задачи (3.22) является равномерно ограниченным и имеет регулярный пограничный слой у границы = 0 и пара болические пограничные слои у границ = 0, = 1.

Зададим в области кусочно-равномерную сетку [58]:

, = {(, ),, = 0,, = 1, = 1, 0 = 0, = 1, 0 = 0, = 1}, где 2(1 ) 2 =,1 ;

=,, 2 2(1 2 ) 4 3 (3.24) =,1, ;

=,, 4 4 4 { } { } 1 = min, ln, = min, 2 ln.

2 На заданной сетке, выпишем схему направленных разностей:

( ) ( ) 2 +1,,, 1,,+1,,, + + + +1 +1 + +1 +1 (3.25) +1,, (, ) = (, ), (, ),, +( ), + = (, ), (, ), =,.

, Отметим, что матрица схемы (3.25) является M-матрицей. В соответствии с [58, 82] выполнено:

(3.26) [], 1, = ln /, где под понимаем положительные постоянные, не зависящие от и.

3.2.2. Экстраполяция Ричардсона Исследуем экстраполяцию Ричардсона для повышения точности разностной схемы при использовании двухсеточного метода. Метод экстраполяции Ричардсона для сингуляр но возмущенных эллиптических задач исследовался, например, в работах [87,88]. Рассмотрим случай, когда вспомогательная сетка Шишкина имеет вид (3.24) и содержит сеточных ин тервалов в раз меньше по каждому направлению, чем исходная сетка, где 1 — целое число.

Решение схемы направленных разностей (3.25) вычисляется на сетке,. Для повышения точности будем также использовать решение этой схемы на сетке,, которая содержит сеточных интервалов и имеет те же параметры,, что и сетка,. Эти сетки вложены так, что, = {(, )}, = {(, )}. Очевидно, что сетку, можно получить из, делением каждой ячейки на равных частей по каждому на правлению.

Обозначим решение схемы (3.25) на, как и пусть 1 = =, = =.

1 В соответствии с методом экстраполяции Ричардсона зададим функцию на сет ке,, приближающую решение (, ) с более высоким порядком точности, чем.

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

(, ) = (, ) + (, ), (, ),.

В узлах исходной сетки,, не совпадающих с узлами сетки,, зада дим сеточную функцию (, ), используя интерполяцию. Тогда для каждого уз ла (, ),, принадлежащего некоторой ячейке, = [1, +1 ] [1, +1 ], определим:

(3.27) (, ) = ([ ],,, ), где интерполяционную формулу для ячейки, зададим следующим образом [25]:

(, ) (, 1 ) ([ ],,, ) = ( )+ + (, +1 ) 2 (, ) + (, 1 ) ( (3.28) + ( ) ( ) +1 2 + ( ) (1 ) ) ( ) + (, ), + где (, ) (1, ) (, ) = (, ) + ( )+ + (+1, ) 2 (, ) + (1, ) ( ( ) ( ) + +1 2 + ( ) (1 ) ) ( ).

+ Интерполяция (3.28) является точной на функциях () и () и будет квадратиче ской при задании () = 2, () = 2. Функции () и () можно выбирать в соответ ствии с пограничными слоями задачи (3.22).

3.2.3. Результаты численных экспериментов Рассмотрим краевую задачу:

+ + = (, ), (, ), (3.29) (, ), (, ) = (, ), где, соответствуют решению (, ) = + + + cos().

Решение задачи (3.29) находим на основе схемы (3.25). Начальное приближение для используемых итерационных методов задаем следующим образом:

{ (, ),,, 0, (0) (, ) = (, ), (, ),.

Итерационный метод (3.7) на сетке, завершаем, если выполнено условие:

( ), тогда будет выполнена оценка:

( ).

Использование формул линейной и квадратической интерполяций сеточной функ ции с сетки, на исходную сетку, приводило к тому, что погрешность метода Ричардсона становилась значительно выше, чем в узлах вспомогательной сетки,, по этому функции (), () были заданы следующим образом:

() = 2, () = +.

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

Таблица 3. Количество итераций односеточного и двухсеточного методов Зейделя, = 8 16 32 64 128 256 4 39(11) 118(11) 335(10) 970(10) 2936(10) 9331(9) 30847(9) 8 110(37) 320(33) 940(30) 2869(28) 9164(27) 30393(26) 16 292(104) 882(91) 2738(82) 8845(75) 29540(69) 32 789(291) 2525(252) 8305(223) 28087(202) 64 2218(845) 7502(731) 25883(646) 128 6537(2592) 23009(2255) 256 21191(8357) 43 123 347 1002 3045 9694 В табл. 3.13 при различных значениях и приведена норма погрешности двухсе точного метода с экстраполяцией Ричардсона (3.27). В нижней строке для сравнения приве дена норма погрешности односеточного метода в зависимости от.

Из табл. 3.13 следует, что экстраполяция Ричардсона (3.27) повышает точность схемы до порядка (ln2 / 2 ).

Таблица 3. Норма погрешности односеточного метода Зейделя и двухсеточного метода Зейделя с экстраполяцией Ричардсона, = 8 16 32 64 128 256 4 2.67–1 2.40–1 2.57–1 3.15–1 3.66–1 4.09–1 4.47– 8 7.43–2 9.43–2 1.28–1 1.60–1 1.94–1 2.26– 16 3.03–2 3.74–2 4.80–2 6.05–2 7.48– 32 9.82–3 1.15–2 1.38–2 1.73– 64 3.58–3 2.84–3 3.28– 128 1.15–3 8.83– 256 3.74– 2.30–1 1.37–1 7.23–2 3.70–2 2.21–2 1.39–2 8.20– В табл. 3.14 при = 104 проведено сравнение исследуемых итерационных методов.

Двухсеточный метод используем в случае = /2. Для метода последовательной верхней релаксации итерационный параметр = 2/(1 + 0.7), т. е. = 0.3, для метода Писмана Речфорда итерационный параметр = 8/.

Таблица 3. Сравнение количества итераций, = Метод 8 16 32 64 128 Зейделя 39(11) 110(37) 292(104) 789(291) 2218(845) 6537(2592) 43 123 347 1002 3045 верхней 32(7) 92(30) 245(87) 663(244) 1862(709) 5471(2174) релаксации 35 103 291 841 2553 Писмана- 11(2) 26(13) 57(31) 122(70) 258(155) 559(340) Речфорда 12 30 68 152 333 Применение методов последовательной верхней релаксации и Писмана-Речфорда при вело к уменьшению количества итераций по сравнению с методом Зейделя. Повышение точ ности на основе экстраполяции Ричардсона не зависит от конкретного итерационного метода.

В табл. 3.15 приведена скорость сходимости схемы (3.25) в зависимости от и при её реализации односеточным методом Писмана-Речфорда (3.20). В последней строке табл. 3.15 приведена теоретическая оценка скорости сходимости схемы (3.25) в зависи мости от, соответствующая оценке погрешности (3.26).

Таблица 3. Скорость сходимости в случае односеточного метода Писмана-Речфорда 8 16 32 64 128 1 0.985 0.992 0.997 0.999 0.999 1. 10 0.816 0.857 0.926 0.960 0.979 0. 10 0.848 0.929 0.752 0.671 0.733 0. 10 0.761 0.920 0.972 0.712 0.724 0. 10 0.754 0.920 0.964 0.743 0.674 0. 10 0.753 0.920 0.964 0.744 0.669 0. 0.415 0.585 0.678 0.737 0.778 0. В табл. 3.16 приведена скорость сходимости схемы (3.25) в зависимости от и при её реализации двухсеточным методом Писмана-Речфорда с использованием экстраполяции Ричардсона при = /2. В последней строке табл. 3.16 приведена теоретическая оценка скорости сходимости схемы (3.25) с экстраполяцией Ричардсона в зависимости от, соответствующая оценке (ln2 / 2 ).


Таблица 3. Скорость сходимости в случае двухсеточного метода Писмана-Речфорда при использовании экстраполяции Ричардсона 8 16 32 64 128 1 2.369 2.472 2.241 2.143 2.077 2. 10 1.502 2.156 2.310 2.003 2.005 2. 10 1.574 1.268 1.564 1.393 1.779 1. 10 1.779 1.293 1.622 1.486 1.307 0. 10 1.844 1.295 1.626 1.454 1.643 1. 10 2.015 1.294 1.626 1.450 1.648 1. 0.830 1.170 1.356 1.474 1.555 1. Итак, применение двухсеточного метода приводит к выигрышу в количестве ариф метических действий, а использование экстраполяции Ричардсона повышает точность раз ностной схемы на порядок с (ln / ) до (ln2 / 2 ) вне зависимости от используемого итерационного метода. Исследованы методы Зейделя, последовательной верхней релаксации и Писмана-Речфорда, наибольшую скорость сходимости среди которых показал последний.

3.3. Задача конвекции-диффузии в случае регулярных пограничных слоев 3.3.1. Постановка задачи Рассмотрим линейную сингулярно возмущенную эллиптическую краевую задачу:

+ + () + () (, ) = (, ), (, ) ;

(3.30) (, ), (, ) = (, ), где = (0, 1)2, =, функции,,,, — достаточно гладкие, (3.31) () 0, () 0, (, ) 0, 0.

Известно [58], что при выполнении условий (3.31) решение задачи (3.30) является рав номерно ограниченным и имеет два регулярных пограничных слоя у границ = 0 и = 0.

Зададим в области кусочно-равномерную сетку [58]:

, = {(, ),, = 0,, = 1, = 1, 0 = 0, = 1, 0 = 0, = 1}, где 2(1 ) 2 =, 1 ;

=,, 2 2(1 ) 2 (3.32) =, 1 ;

=,, 2 { } { } 1 2 1 = min, ln, = min, ln.

2 На заданной сетке, выпишем схему направленных разностей:

( ) 2 +1,,, 1, + + +1 +1 ( ) 2,+1,,,1 +1,, + + ( ) + + +1 +1 + (3.33),+1, (, ) = (, ), (, ),, +( ), + = (, ), (, ), =,.

, Отметим, что матрица схемы (3.33) является M-матрицей. В соответствии с [58, 82] выполнено:

(3.34) [], 1, = ln /, где под понимаем положительные постоянные, не зависящие от и.

3.3.2. Экстраполяция Ричардсона Исследуем экстраполяцию Ричардсона для повышения точности разностной схемы при использовании двухсеточного метода. Метод экстраполяции Ричардсона для сингуляр но возмущенных эллиптических задач исследовался, например, в работах [87,88]. Рассмотрим случай, когда вспомогательная сетка Шишкина имеет вид (3.32) и содержит сеточных ин тервалов в раз меньше по каждому направлению, чем исходная сетка, где 1 — целое число.

Решение схемы направленных разностей (3.33) вычисляется на сетке,. Для повышения точности будем также использовать решение этой схемы на сетке,, которая содержит сеточных интервалов и имеет те же параметры,, что и сетка,. Эти сетки вложены так, что, = {(, )}, = {(, )}. Очевидно, что сетку, можно получить из, делением каждой ячейки на равных частей по каждому на правлению.

В виду того, что оценки (3.26), (3.34) для схем (3.25), (3.33) соответственно имеют один и тот же порядок точности, то согласно методу экстраполяции Ричардсона зададим функ цию на сетке,, приближающую решение (, ) задачи (3.30) с более высоким порядком точности, чем, в соответствии с (3.27).

3.3.3. Результаты численных экспериментов Исследование односеточного и двухсеточного алгоритмов Рассмотрим краевую задачу:

+ + + 2 = (, ), (, ), (3.35) (, ), (, ) = 0, где соответствует решению ) ) 1 1 ( ( (, ) = (1 ) ( ) (1 ) ( ) + sin() sin().

1 1 1 Решение задачи (3.35) находим на основе схемы (3.33). Начальное приближение для используемых итерационных методов задаем следующим образом:

(0) (, ) = 0, (, ), Итерационный метод (3.7) на сетке, завершаем, если выполнено условие:

( ), тогда будет выполнена оценка ( ).

При реализации формулы (3.27) использовалась квадратическая итерполяция, поэто му функции (), () были заданы следующим образом:

() = 2, () = 2.

Результаты численных экспериментов для метода Зейделя при = 104 приведены в табл. 3.17 и табл. 3.18.

Таблица 3. Количество итераций односеточного и двухсеточного методов Зейделя, = 8 16 32 64 128 256 4 37(11) 115(10) 336(9) 993(9) 3064(8) 9905(8) 33270(8) 8 107(35) 323(32) 966(29) 3001(27) 9741(26) 32815(24) 16 299(102) 922(89) 2896(80) 9458(73) 31994(68) 32 853(294) 2755(252) 9096(222) 30953(200) 64 2553(870) 8647(744) 29725(652) 128 8023(2712) 28261(2329) 256 26272(8879) 40 121 354 1047 3236 10463 В табл. 3.17 при различных значениях и указано количество итераций двухсе точного метода на исходной сетке,, при этом в скобках приведено количество итераций на более редкой вспомогательной сетке,. В нижней строке указано число итераций од носеточного метода в зависимости от.

В табл. 3.18 при различных значениях и приведена норма погрешности двухсе точного метода с экстраполяцией Ричардсона (3.27). В нижней строке для сравнения приве дена норма погрешности односеточного метода в зависимости от.

Таблица 3. Норма погрешности односеточного метода Зейделя и двухсеточного метода Зейделя с экстраполяцией Ричардсона, = 8 16 32 64 128 256 4 2.74–1 2.96–1 3.52–1 4.13–1 4.74–1 5.29–1 5.76– 8 1.29–1 1.29–1 1.55–1 1.91–1 2.33–1 2.77– 16 5.63–2 4.90–2 5.32–2 6.32–2 8.11– 32 2.38–2 1.69–2 1.53–2 1.81– 64 8.23–3 5.52–3 4.22– 128 2.71–3 1.73– 256 8.46– 4.79–1 2.76–1 1.59–1 9.51–2 5.50–2 3.09–2 1.71– Из табл. 3.18 следует, что экстраполяция Ричардсона (3.27) повышает точность схемы до порядка (ln2 / 2 ).

Отметим, что в случае задачи (3.30) в соответствии с [72] метод Зейделя должен учитывать направление потока для уменьшения количества итераций. Тогда векторно матричная запись метода Зейделя для задачи (3.30) будет иметь вид:

() = 1 + (1) + ().

( ) В табл. 3.19 при = 104 проведено сравнение исследуемых итерационных методов.

Двухсеточный метод используем в случае = /2. Для метода последовательной верх ней релаксации итерационный параметр = 2/(1 + 0.9), т. е. = 0.1. Метод Писмана Речфорда не подходит для решения данного вида задачи.

Таблица 3. Сравнение количества итераций, = Метод 8 16 32 64 128 256 Зейделя 37(11) 107(35) 299(102) 853(294) 2553(870) 8023(2712) 26272(8879) 40 121 354 1047 3236 10463 верхней 36(10) 102(33) 285(97) 812(280) 2426(828) 7621(2578) 24943(8433) релаксации 38 115 336 995 3074 9935 Зейделя 27(2) 85(25) 254(80) 762(247) 2368(776) 7653(2526) 25532(8509) по потоку 31 99 307 953 3050 10094 Применение методов Зейделя по потоку и последовательной верхней релаксации при вело к уменьшению количества итераций по сравнению с классическим методом Зейделя.

Повышение точности на основе экстраполяции Ричардсона не зависит от конкретного ите рационного метода.

В табл. 3.20 – 3.22 при различных значениях и приведено количество итераций методов Зейделя, BiCRSTAB и BiCGSTAB соответственно. Двухсеточный метод используем в случае = /2.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и 8 16 32 64 1 12(6) 40(25) 152(110) 595(495) 2346(2223) 25 110 495 2223 10 10(5) 23(14) 75(50) 270(191) 1020(771) 16 50 191 771 10 22(7) 60(22) 167(65) 481(188) 1461(569) 25 74 220 664 10 30(9) 85(29) 238(85) 683(246) 2054(737) 33 99 294 878 10 37(11) 107(35) 299(102) 853(294) 2553(870) 40 121 354 1047 Таблица 3. Количество итераций в случае односеточного и двухсеточного методов BiCRSTAB в зависимости от и 8 16 32 64 1 4(2) 6(4) 11(11) 17(25) 45(58) 4 11 25 58 10 5(2) 6(6) 13(12) 24(25) 45(59) 5 12 25 59 10 15(3) 35(13) 73(53) 137(123) 514(341) 15 51 152 392 10 28(3) 77(30) 235(134) 750(544) 1604(1539) 36 200 585 1923 10 65(3) 232(53) 1493(622) 2869(2464) 9208(7314) 48 768 2856 7791 Таблица 3. Количество итераций в случае односеточного и двухсеточного методов BiCGSTAB в зависимости от и 8 16 32 64 1 3(2) 4(4) 9(10) 24(22) 43(58) 4 10 22 58 10 4(2) 5(4) 10(12) 23(28) 43(64) 5 12 28 64 10 14(2) 37(12) 68(45) 149(129) 249(309) 16 50 136 340 10 24(3) 120(24) 288(127) 724(526) 1562(1587) 28 136 573 1872 10 45(3) 400(57) 905(656) 2588(1937) 6340(6759) 48 654 2280 7768 Из табл. 3.20 – 3.22 следует, что использование стабилизированных методов бисопря женных градиентов и направлений при = 1, а также не очень малых значениях приводит к существенному сокращению количества итераций по сравнению с методом Зейделя. Но при малых стабилизированные методы бисопряженных градиентов и направлений показывают скорость сходимости существенно меньшую, чем у метода Зейделя. Отметим, что исследо вание метода бисопряженных градиентов и метода сдвоенных сопряженных градиентов для задачи (3.30) и трехмерного её варианта при = 1 проведено в [60].

В табл. 3.23 приведена скорость сходимости схемы (3.33) в зависимости от и при её реализации односеточным методом последовательной верхней релаксации (3.20). В послед ней строке табл. 3.23 приведена теоретическая оценка скорости сходимости схемы (3.33) в зависимости от, соответствующая оценке погрешности (3.34).

Таблица 3. Скорость сходимости в случае односеточного метода последовательной верхней релаксации 8 16 32 64 128 1 0.764 0.910 0.955 0.978 0.990 0. 10 0.725 0.881 0.940 0.969 0.985 0. 10 0.836 0.783 0.758 0.805 0.840 0. 10 0.802 0.795 0.741 0.791 0.832 0. 10 0.799 0.795 0.740 0.790 0.831 0. 10 0.799 0.795 0.739 0.790 0.831 0. 0.415 0.585 0.678 0.737 0.778 0. В табл. 3.24 приведена скорость сходимости схемы (3.33) в зависимости от и при её реализации двухсеточным методом последовательной верхней релаксации с исполь зованием экстраполяции Ричардсона при = /2. В последней строке табл. 3.24 приведена теоретическая оценка скорости сходимости схемы (3.33) с экстраполяцией Ричардсона в зависимости от, соответствующая оценке (ln2 / 2 ).


Таблица 3. Скорость сходимости в случае двухсеточного метода последовательной верхней релаксации при использовании экстраполяции Ричардсона 8 16 32 64 128 1 2.486 2.094 2.010 2.016 1.948 1. 10 1.354 1.531 1.681 1.320 1.090 1. 10 1.107 1.315 1.186 1.554 1.576 1. 10 1.092 1.208 1.235 1.538 1.603 1. 10 1.089 1.196 1.240 1.534 1.604 1. 10 1.089 1.195 1.240 1.533 1.604 1. 0.830 1.170 1.356 1.474 1.555 1. Исследование методов Зейделя на сетке Шишкина и равномерной сетке Рассмотрим краевую задачу:

+ + (1 + ) + (1 + ) 2 = sin(), (, ), (3.36) (, ).

(, ) = 0, Для задачи (3.36) точное решение не задается в явном виде, тем самым пограничные слои формируются, исходя из вида задачи. В ряде работ [18, 72] исследован метод Зейдля, учитывающий направление потока, на равномерной сетке. На сетке Шишкина исследований не проводилось. Сравним количество итераций метода Зейделя и метода Зейделя по потоку для задачи (3.36) на Шишкина сетке и на равномерной сетке.

В табл. 3.25 приведено количество итераций метода Зейделя в зависимости от и на сетке Шишкина.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и на сетке Шишкина 8 16 32 64 1 4(2) 15(11) 71(53) 294(262) 1175(1274) 11 53 262 1274 10 7(2) 13(9) 36(34) 126(127) 459(502) 11 34 127 502 10 17(6) 48(19) 134(55) 386(161) 1175(488) 21 63 188 571 10 26(8) 74(26) 212(76) 619(224) 1884(675) 29 89 266 803 10 33(10) 96(32) 273(94) 794(272) 2404(813) 36 111 327 976 106 48(14) 137(44) 385(127) 1107(361) 3308(1059) 51 152 439 1286 В табл. 3.26 приведено количество итераций метода Зейделя в зависимости от и на равномерной сетке. Число итераций значительно меньше, чем на сетке Шишкина. От метим, что при этом разностная схема не обладает свойством равномерной сходимости по параметру.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и на равномерной сетке 8 16 32 64 1 4(2) 15(11) 71(53) 294(262) 1175(1274) 11 53 262 1274 10 5(2) 13(9) 36(34) 126(127) 459(502) 9 34 127 502 10 5(2) 9(8) 14(24) 29(62) 72(160) 8 24 62 160 10 5(2) 8(8) 10(23) 14(54) 42(119) 8 23 54 119 10 5(2) 8(8) 10(23) 14(53) 39(115) 8 23 53 115 106 5(2) 8(8) 10(23) 14(53) 39(114) 8 23 53 114 В табл. 3.27 приведено количество итераций метода Зейделя по потоку в зависимости от и на сетке Шишкина.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя по потоку в зависимости от и на сетке Шишкина 8 16 32 64 1 3(2) 19(8) 73(48) 300(251) 1188(1251) 8 48 251 1251 10 2(1) 7(4) 35(18) 123(92) 457(428) 5 18 92 428 10 10(1) 31(9) 97(34) 309(117) 1016(398) 12 43 145 482 10 18(1) 55(16) 173(54) 539(178) 1723(583) 20 68 221 711 10 25(1) 77(22) 234(72) 714(227) 2243(720) 27 89 282 884 10 40(1) 118(34) 346(105) 1026(316) 3146(967) 41 130 394 1194 В табл. 3.28 приведено количество итераций метода Зейделя по потоку в зависимо сти от и на равномерной сетке. При малых требуется только одна итерация, что согласуется с [72].

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя по потоку в зависимости от и на равномерной сетке 8 16 32 64 1 3(2) 19(8) 73(48) 300(251) 1188(1251) 8 48 251 1251 10 2(1) 7(4) 35(18) 123(92) 457(428) 4 18 92 428 10 1(1) 2(1) 6(4) 17(15) 54(59) 1 4 15 59 103 1(1) 1(1) 2(1) 3(3) 8(9) 1 1 3 9 10 1(1) 1(1) 1(1) 2(1) 3(2) 1 1 1 2 10 1(1) 1(1) 1(1) 1(1) 1(1) 1 1 1 1 На равномерной сетке с уменьшением количество итераций метода Зейделя и метода Зейделя по потоку сокращается, так как при этом узлы не попадают в область больших градиентов, а вне пограничного слоя решение задачи (3.30) близко к решению вырожденной задачи, когда = 0, которое можно найти, исходя из явных соотношений.

В случае сетки Шишкина при всех половина узлов находится в пограничном слое, поэтому с уменьшением число итераций несколько увеличивается.

Исследование влияния преобладания конвекции на скорость сходимости методов Зейделя Рассмотрим краевую задачу:

+ + () + () 2 = sin(), (, ), (3.37) (, ).

(, ) = 0, Для задачи (3.37) исследуем влияние преобладания конвекции на скорость сходимо сти метода Зейделя. Подобный анализ на равномерный сетке для уравнения стационарного переноса зарядов в полупроводнике проведен в [18].

В табл. 3.29 приведено количество итераций метода Зейделя в зависимости от и на сетке Шишкина при () = 5(1 + ), () = 5(1 + ).

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и на сетке Шишкина, () = 5(1 + ), () = 5(1 + ) 8 16 32 64 128 1 7(2) 18(11) 61(47) 233(199) 901(865) 3528(3799) 11 47 199 865 3799 10 5(4) 9(11) 21(29) 59(78) 208(223) 780(707) 12 29 78 223 707 10 15(6) 33(15) 72(36) 169(82) 422(191) 1143(475) 16 38 87 205 515 10 18(7) 39(18) 85(40) 196(90) 488(210) 1323(521) 19 43 97 227 569 10 21(8) 43(20) 94(44) 215(98) 533(224) 1441(555) 22 48 106 244 609 105 23(9) 48(22) 102(48) 233(104) 573(238) 1544(586) 25 53 114 260 646 В табл. 3.30 приведено количество итераций метода Зейделя по потоку в зависимости от и на сетке Шишкина при () = 5(1 + ), () = 5(1 + ).

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя по потоку в зависимости от и на сетке Шишкина, () = 5(1 + ), () = 5(1 + ) 8 16 32 64 128 1 3(1) 14(6) 61(33) 235(168) 905(802) 3540(3669) 6 33 168 802 3669 10 2(1) 4(2) 13(7) 42(30) 157(124) 660(502) 2 7 30 124 502 102 4(1) 10(4) 27(11) 77(29) 239(85) 781(262) 5 13 35 100 305 10 7(1) 16(7) 38(15) 103(38) 305(103) 965(308) 8 19 45 122 359 10 10(1) 20(9) 47(19) 121(45) 348(118) 1081(341) 11 23 54 139 398 10 13(1) 25(11) 55(23) 138(52) 387(131) 1181(372) 13 28 62 155 434 В табл. 3.31 приведено количество итераций метода Зейделя в зависимости от и на сетке Шишкина при () = 10 +, () = 10 +.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и на сетке Шишкина, () = 10 +, () = 10 + 8 16 32 64 128 1 6(3) 17(13) 60(48) 223(188) 842(777) 3267(3289) 13 48 188 777 3289 10 5(4) 10(12) 22(30) 76(75) 247(199) 835(579) 13 30 75 199 579 10 15(6) 32(15) 68(34) 148(73) 339(161) 830(370) 16 35 76 168 389 10 17(7) 35(17) 74(36) 161(78) 364(169) 882(382) 18 38 81 176 403 10 19(8) 38(18) 79(39) 171(81) 384(176) 930(396) 19 41 85 185 420 105 20(9) 41(20) 84(41) 179(85) 402(182) 972(410) 21 43 90 192 435 В табл. 3.32 приведено количество итераций метода Зейделя по потоку в зависимости от и на сетке Шишкина при () = 10 +, () = 10 +.

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя по потоку в зависимости от и на сетке Шишкина, () = 10 +, () = 10 + 8 16 32 64 128 1 3(1) 15(5) 57(30) 218(150) 833(698) 3249(3127) 5 30 150 698 3127 10 2(1) 3(2) 9(6) 31(23) 136(90) 593(355) 2 6 23 90 355 102 4(1) 7(3) 16(8) 44(18) 131(49) 417(142) 4 9 21 56 163 10 5(1) 10(5) 22(10) 55(22) 153(56) 467(155) 6 12 26 64 178 10 7(1) 13(7) 27(12) 63(26) 171(62) 510(168) 8 15 31 193 10 9(1) 16(8) 31(15) 71(30) 187(69) 548(182) 10 17 35 80 209 В табл. 3.33 приведено количество итераций метода Зейделя в зависимости от и на сетке Шишкина при () = 32(1 + ), () = 32(1 + ).

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя в зависимости от и на сетке Шишкина, () = 32(1 + ), () = 32(1 + ) 8 16 32 64 128 1 5(4) 8(11) 15(26) 50(61) 145(136) 419(318) 11 32 92 286 983 10 5(4) 8(11) 15(26) 50(61) 145(136) 419(318) 12 26 61 136 318 10 13(5) 28(14) 59(30) 121(64) 256(135) 559(284) 14 31 65 137 289 10 14(6) 31(15) 64(32) 132(67) 277(139) 599(292) 15 32 68 141 297 10 16(7) 32(16) 67(33) 137(69) 288(142) 619(297) 16 34 70 145 304 105 17(7) 34(16) 69(34) 142(71) 295(145) 635(303) 17 35 72 148 309 В табл. 3.34 приведено количество итераций метода Зейделя по потоку в зависимости от и на сетке Шишкина при () = 32(1 + ), () = 32(1 + ).

Таблица 3. Количество итераций в случае односеточного и двухсеточного методов Зейделя по потоку в зависимости от и на сетке Шишкина, () = 32(1 + ), () = 32(1 + ) 8 16 32 64 128 1 2(1) 6(2) 18(11) 64(46) 243(190) 968(786) 2 11 46 190 786 10 1(1) 2(1) 4(2) 10(7) 41(25) 182(87) 1 2 7 25 87 102 2(1) 3(2) 6(4) 15(8) 42(18) 126(47) 2 4 9 20 53 10 3(1) 5(3) 9(5) 21(10) 52(22) 147(53) 3 6 11 24 60 10 4(1) 7(4) 12(7) 24(12) 58(25) 160(59) 5 7 13 28 66 10 5(1) 8(5) 14(8) 27(14) 64(28) 171(63) 6 9 15 31 71 Из табл. 3.29 – 3.34 следует, что чем более выражено преобладание конвекции, тем меньше требуется итераций и тем больше преимущество по количеству итераций у метода Зейделя по потоку перед классическим его вариантом.

Сравнение с прямым методом пакета Pardiso Рассмотрим краевую задачу:

+ + (1 + ) + (1 + ) 2 = sin(), (, ), (3.38) (, ).

(, ) = 0, Задачу (3.38), помимо итерационного метода, можно решать и прямым методом. Од ним из распространенных решателей, содержащих эффективный прямой метод для сильно разреженных матриц является Pardiso [84–86]. Но следует отметить, что прямой метод паке та Pardiso более требователен к памяти и поэтому для порядка 2000 метод завершается с ошибкой "не достаточно памяти".

В табл. 3.35 для = 32 при = 104 проведено сравнение времени выполнения пря мого метода решателя Pardiso и двухсеточного метода.

Таблица 3. Сравнение время выполнения Pardiso и двухсеточного метода, = N 256 512 Pardiso 1.83 17.96 121. Зейделя по потоку 1.24 21.05 290. В табл. 3.36 для = 100 (слева) и для = 200 (справа) при = 104 проведено сравнение времени выполнения прямого метода решателя Pardiso и двухсеточного метода.

Таблица 3. Сравнение время выполнения Pardiso и двухсеточного метода, = 100, = k=100 k= 256 512 1024 256 512 Pardiso Pardiso 2.00 18.76 136.27 2.08 19.88 142. Зейделя по потоку Зейделя по потоку 0.63 7.74 95.94 0.45 4.62 51. Результаты в табл. 3.35, 3.36 показывают ещё одну особенность сингулярно возмущенных задач. Чем больше коэффициент конвекции, тем медленнее работает прямой метод пакета Pardiso и тем быстрее сходится двухсеточный метод.

Итак, применение двухсеточного метода приводит к выигрышу в количестве ариф метических действий, а использование экстраполяции Ричардсона повышает точность раз ностной схемы на порядок с (ln / ) до (ln2 / 2 ) вне зависимости от используемого итерационного метода. Исследованы методы Зейделя, последовательной верхней релакса ции, стабилизированные методы сопряженных градиентов и направлений и метод Зейделя, учитывающий направление потока. Использование стабилизированных методов бисопряжен ных градиентов и направлений при = 1, а также не очень малых значениях приводит к существенному сокращению количества итераций по сравнению с методом Зейделя. Но при малых стабилизированные методы бисопряженных градиентов и направлений показывают скорость сходимости существенно меньшую, чем у метода Зейделя. Выигрыш в количестве итераций метода Зейделя по потоку по сравнению с методом Зейделя в случае сетки Шиш кина намного меньше, чем на равномерной сетке, так как при всех значениях половина узлов находится в пограничном слое. Также, чем более выражено преобладание конвекции, тем меньше требуется итераций и тем больше преимущество по количеству итераций у ме тода Зейделя по потоку перед классическим его вариантом. Проведено сравнение с прямым методом пакета Pardiso и показано, что при больших коэффициентах конвекции двухсеточ ный метод эффективнее. Также прямой метод пакета Pardiso для достаточно больших не может быть использован.

Таким образом, исследован двухсеточный метод решения линейно в третьей главе го эллиптического уравнения в случаях полного вырождения, регулярных и параболических пограничных слоев. Экспериментально показано, что использование экстраполяции Ричард сона в двухсеточном методе приводит к повышению точности на порядок используемых на сетке Шишкина схем. При реализации двухсеточных алгоритмов исследованы итерацион ные методы Зейделя, последовательной верхней релаксации, Писмана-Речфорда, стабили зированные методы сопряженных направлений и градиентов, метод Зейделя, учитывающий локализацию пограничных слоев. Проведено сравнение по времени выполнения двухсеточ ного алгоритма с прямым методом пакета Pardiso.

Заключение В диссертации разработаны и исследованы разностные схемы на сгущающихся сет ках для сингулярно возмущенных задач, проведено исследование двухсеточного метода для реализации построенных схем и применение экстраполяции Ричардсона.

Основные результаты являются новыми и заключаются в следующем.

1. В случае сингулярно возмущенной задачи Коши для линейного обыкновенного дифференциального уравнения второго порядка построен и обоснован аналог схе мы А. М. Ильина на равномерной сетке и обоснована равномерная сходимость схемы направленных разностей на сетке Шишкина. Результаты вычислительного экспери мента подтверждают полученные теоретические оценки.

2. Разработан метод решения сингулярно возмущенной краевой задачи для нелинейного обыкновенного дифференциального уравнения второго порядка на основе двухсеточ ного метода на сетках Шишкина. Для схемы направленных разностей в двухсеточ ном методе при использовании экстраполяции Ричардсона получена оценка погрешно сти в зависимости от соотношения между шагами исходной и вспомогательной сеток.

Результаты вычислительного эксперимента подтверждают полученные теоретические оценки.

3. Для сингулярно возмущенной краевой задачи для нелинейного обыкновенного диффе ренциального уравнения второго порядка построен и обоснован алгоритм повышенной точности на основе линеаризаций Пикара и Ньютона с применением монотонной схе мы Самарского. Предложен двухсеточный метод реализации построенных алгорит мов, приводящих к экономии вычислительных затрат. Экспериментально показано, что экстраполяция Ричардсона приводит к повышению точности схемы Самарского.

4. Исследован двухсеточный метод решения линейного эллиптического уравнения в слу чаях полного вырождения, регулярных и параболических пограничных слоев. Экспе риментально показано, что использование экстраполяции Ричардсона в двухсеточном методе приводит к повышению точности на порядок используемых на сетке Шишкина схем. При реализации двухсеточных алгоритмов исследованы итерационные методы Зейделя, последовательной верхней релаксации, Писмана-Речфорда, стабилизирован ные методы сопряженных направлений и градиентов, метод Зейделя, учитывающий локализацию пограничных слоев. Проведено сравнение по времени выполнения двух сеточного алгоритма с прямым методом пакета Pardiso.

Список литературы [1] Андреев В. Б. О точности сеточных аппроксимаций негладких решений сингулярно возмущенного уравнения реакции-диффузии в квадрате // Дифференциальные урав нения. – 2006. – Т. 42. – № 7. – С. 895 – 906.

[2] Андреев В. Б., Коптева Н. В. Об исследовании разностных схем с аппроксимаци ей первой производной центральным разностным отношением // Журнал вычисл.

матем. и матем. физики. – 1996. – Т. 36. – № 8. – С. 101 – 117.

[3] Андреев В. Б., Савин И. А. О равномерной по малому параметру сходимости мо нотонной схемы А.А. Самарского и ее модификации // Журнал вычисл. матем. и матем. физики. – 1995. – Т. 35. – № 5. – С. 739 – 752.

[4] Багаев Б. М., Карепова Е. Д., Шайдуров В. В. Сеточные методы решения задач с пограничным слоем. – Новосибирск: Наука, 2001. – Ч. 2. – 224 c.

[5] Багаев Б. М., Шайдуров В. В. Сеточные методы решения задач с пограничным слоем. – Новосибирск: Наука. Сиб. предприятие РАН, 1998. – Ч. 1. – 198 c.

[6] Бахвалов Н. С. К оптимизации методов решения краевых задач при наличии погра ничного слоя // Журнал вычислительной математики и математической физики.

– 1969. – Т. 9. – № 4. – С. 841 – 859.

[7] Бахвалов Н. С. О сходимости одного релаксационного метода при естественных ограничениях на эллиптический оператор // Журнал вычисл. матем. и мат. фи зики. – 1966. – Т. 6. – № 5. – С. 861 – 883.

[8] Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. – Москва: Наука, 1987. – 600 c.

[9] Блатов И. А. О проекционном методе для сингулярно возмущенных краевых задач // Журнал вычисл. матем. и мат. физики. – 1990. – Т. 30. – № 7. – С. 1031 – 1044.

[10] Блатов И. А., Добробог Н. В. Условная -равномерная сходимость алгоритмов адап тации в методе конечных элементов для сингулярно возмущенных задач // Журнал вычисл. матем. и мат. физики. – 2010. – Т. 50. – № 9. – С. 1550 – 1568.

[11] Блатов И. А., Стрыгин B. В. Сходимость метода Галеркина для нелинейной двухто чечной сингулярно-возмущенной краевой задачи в пространстве [, ] // Журнал вычисл. матем. и мат. физики. – 1985. – Т. 25. – № 7. – С. 1001 – 1008.

[12] Вазов В. Асимптотические разложения решений обыкновенных дифференциальных уравнений. – Москва: Мир, 1968. – 464 c.

[13] Ван-Дайк М. Методы возмущений в механике жидкости. – Москва: Мир, 1967. – 310 c.

[14] Васильева А. Б., Бутузов В. Ф. Асимптотические разложения решений сингулярно возмущенных уравнений. – Москва: Наука, 1973. – 272 c.

[15] Вишик М. И., Люстерник Л. А. Регулярное вырождение и пограничный слой для линейных дифференциальных уравнений с малым параметром // Успехи матема тических наук. – 1957. – Т. 12. – № 5. – C. 3 – 122.

[16] Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. – Москва: Наука, 1984. – 320 с.

[17] Годунов С. К., Рябенький В. С. Введение в теорию разностных схем. – Москва:

Изд-во физ.-мат. лит-ры, 1962. – 340 c.

[18] Доледенок О. А., Ильин В. П. О скорости сходимости метода неполной факто ризации для диффузионно-конвективных уравнений // Труды ВЦ СО РАН. Выч.

математика. – 1995. – Вып. 3. – С. 41 – 51.

[19] Дулан Э., Миллер Д., Шилдерс У. Равномерные численные методы решения задач с пограничным слоем. – Москва: Мир, 1983. – 200 с.

[20] Задорин А. И. Метод интерполяции для задачи с пограничным слоем // Сибирский журнал вычисл. математики. – 2007. – Т. 10. – № 3. – С. 267 – 275.

[21] Задорин А. И. Метод интерполяции на сгущающейся сетке для функции с погранс лойной составляющей // Журнал вычисл. матем. и матем. физики. – 2008. – Т. 48.

– № 9. – С. 1673 – 1684.

[22] Задорин А. И. О численном решении третьей краевой задачи для уравнения с малым параметром // Журнал вычислительной математики и математической физики.

– 1984. – Т. 24. – № 7. – С. 1008 – 1015.

[23] Задорин А. И. Разностные схемы для задач с пограничным слоем. – Омск: ОмГУ, 2002. – 118 с.

[24] Задорин А. И. Численное решение краевой задачи для системы уравнений с малым параметром // Журнал вычислительной математики и математической физики.

– 1998. – Т. 38. – № 8. – С. 1255 – 1265.

[25] Задорин А. И., Задорин Н. А. Интерполяция функций с погранслойными составля ющими и ее применение в двухсеточном методе // Сибирские электронные мате матические известия. – 2011. – Т. 8. – С. 247 – 267.

[26] Задорин А. И., Тиховская С. В. Анализ разностной схемы для сингулярно возму щенной задачи Коши на сгущающейся сетке // Сиб. журн. вычисл. математики / РАН. Сиб. отделение. – 2011. – Т. 14. – № 1. – С. 47 – 57.

[27] Задорин А. И., Тиховская С. В. Двухсеточный метод для нелинейной сингулярно возмущенной краевой задачи на сетке Шишкина // Сиб. журн. индустр. матем. – 2013. – Т. 16. – № 1(53). – С. 42 – 55.

[28] Задорин А. И., Тиховская С. В. Двухсеточный метод на неравномерной сетке для нелинейного сингулярно возмущенного уравнения второго порядка // Сеточные ме тоды для краевых задач и приложения. Материалы Восьмой Всероссийской конфе ренции, посвященной 80-летию со дня рождения А. Д. Ляшко. – Казань: Казанский университет, 2010. – С. 210 – 216.

[29] Задорин А. И., Тиховская С. В. Разностная схема на равномерной сетке для сингу лярно возмущенной задачи Коши // Вестник НГУ. Серия: Математика, механика, информатика. – 2011. – Т. 11, вып. 3. – С. 114 – 122.



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.