А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 52
Текст из файла (страница 52)
Действительно, так как Я вЂ” самосопряженный в Н оператор, то (!ов!! = зцр ((5 .с, х)!. Используя границы у„ у, оператора С !к!=1 Отсюда следует, что ()Я»(!> 1 при р» < — (1 — р»)!(2р,). Так как р»Е%„, то и 2» — 1 и — соз — (!»»( — соз — я=сов — й=! 2 ... и, 2» 2» 2»' 1 Э и, следовательно, для большого числа номеров й норма ((Я»(> 1 (число таких номеров й примерно равно и!2). Поэтому, если использовать подряд слишком много параметров т, для которых норма оператора Я» больше единицы, то может произойти накопление вычислительной погрешности и рост итерационных приближений, что служит причиной вычислительной неустойчивости метода.
Теорема ! фактически выражает устойчивость итерационной схемы по начальным данным. В случае реального вычислительного процесса необходимо исследовать устойчивость итерационной схемы и по правой части, поскольку ошибки округления можно трактовать как возмущение правой части итерационной схемы на каждой итерации. Если учесть погрешность округления, то вместо однородного уравнения для эквивалентной погрешности х» получим неоднородное уравнение гх + т», 'р „, й =- О, 1, ... (16) Здесь х»= Оп'(у» — и), где у» — реальное итерационное приближение.
Решая уравнение (16), найдем х„=Т„,х,+ ~ т Т„,гй, где т= ! и Т„= П Яи Т„,„=Е. Отсюда получим следующую оценку: !=!+1 и ()х„((()) Т„, »(Ях,~+ ~ тг!)Т„,Я шах ((~р !), (17) Оценка нормы оператора Т„, не зависит от упорядочения множества л)1„, и для любой последовательности чебышевских параметров т» имеем !Т„,1(у„. Оценка для ~Р ~т,()Т„,(! завис=! ' сит от упорядочения множества л)1„. Из (17) следует, что множество Я„должно быть упорядочено так, чтобы указанная сумма принимала минимальное значение.
Следующая лемма указывает минимально возможное значение этой суммы. Лемма !. Если у, и у,— точные границы оператора С, то для любого упорядочения множества Ы„имеет место оценка л ~чД Т„,; )! )) 279 Действительно, из определения оператора Т„получим л туТ„, =(Т„, — Т„,,)С ', 2', т Т„,у — — (Š— Т„,,)С '. /=1 Так как л л ЦЕ Т,е)С т//= Х т,Т„, ~( ~я~ т,ЦТ„у'( !1 ° ' )-1! то достаточно оценить норму оператора (Š— Т„,)С-'. Этот оператор самосопряжен в Н, и если у, и у,— границы оператора С, то Ка — т„,)с ') ч т~<~<т* Т (т — таттт тт тт Таким образом, показано, что для любого х Е Н имеет место оценка ))(Š— Т„,)С 'х!!(1 ч")!х'1.
тт Так как у, есть точная граница самосопряженного оператора С, то у, совпадает с минимальным собственным значением оператора С. Подставляя в (18) вместо х собственную функцию, соответствующую минимальному собственному значению оператора С, получим, что в (18) достигается равенство. Следовательно, получена оценка ((Š— Т„,) С т)~=(1 — д„)!ут. Лемма доказана.
5. Построение оптимальной последовательности итерационных параметров*). 5.1. Сл уча й п=2Я. Порядок использования итерационных параметров та в чебышевском методе существенно влияет на сходимость метода. Поэтому возникает задача построения наилучшей последовательности итерационных параметров, обеспечивающей минимальное влияние вычислительной погрешности метода.
Так как последовательность параметров определяется упорядочением множества %„, то необходимо построить оптимальное упорядочение множества й)1„. Приведем решение этой задачи. Пусть сначала число итераций есть степень 2: а=2Я. Обозначим через Е„множество, состоящее нз и целых чисел: е„=(в в, ... е-,. м ( 1 ~ а > '''Ф м ) ") Способ упорядочения итерационных параметров дан по работам: см.
Е. С. Николаев, А. А. Самарский (ЖВМ и МФ, 12, № 4, 1972) для любого и и 181 для п=2н. 280 Исходя из множества 0,=(1), построим множество О,р по следующему правилу. Пусть множество 8„построено. Тогда множество О, определим по формулам О, = (ОЯ""=4т — О,'"", О!)",'=О,' ', 1=1,2, ..., т), гп=!, 2, 4, ..., 2Р-~. (19) Нетрудно убедиться, что множество О,» состоит из нечетных чисел от 1 до 2ь"' — 1. Используя построенное множество О,р, упорядочим множество Ы,р следующим образом: Щ = ( — соз (31 > Р; = — О';", 1= 1, 2, ..., п ), и = 2г. (20) Это и есть искомое упорядочение множества %„в случае, когда и=2Р.
Для соответствующей этому упорядочению последовательности итерационных параметров доказана оценка л ~,т ) Т„~)( — ~". 1=! Сравнивая эту оценку с оценкой леммы 1, убеждаемся, что по- строенное упорядочение множества %„" действительно обеспечи- вает минимальное влияние вычислительной погрешности на схо- димость чебышевского метода. Приведем некоторые примеры построения множества 0 . 1) а=8.
О, = (1), О, = (1, 3), О, = (1, 7, 3, 5), О, = 11, 15, 7, 9, 3, 1 3, 5, 1 Ц. Множество О, построено. По формуле (20) упорядочивается множество И,*. 2) в=16. Используя найденное выше множество О„, построим по формулам (19) множество О„: 8м=(1 31 !5 17 7 25 9. 23 3 29з 13 19 5з 27 11ю 21). 3) и=32. 0„ = (1, 83, 31, 33, !5, 49, !7, 47, 7, 57, 25, 39, 9, 55, 23, 41, 3, 01, 29, 35, 13, 51, !9, 45, 5, 59, 27, 37, 11, 53, 21, 43). Из формул (19) следует простое правило перехода от мно- жества О к множеству О,: ОД,' =О,' ' и сумма двух соседних чисел равна 4пп 01)~,'+02~'= 4т, 1= 1, 2,, и. Аналогичное правило перехода применяется и в общем случае, к рассмотрению которого мы переходим. 5.2.
Общий сл уч ай. Пусть число итераций и есть любое целое число. Опишем процесс построения множества О„. Элементарными этапами этого процесса являются переходы от 281 множества О„к множеству О,„и от множества О,„к множеству О,„„, где и — произвольное целое число. Сформулируем правила перехода от множества к множеству. 1) Переход от О„„к О, е, состоит в добавлении к элементам множества О, нечетйого числа 2гп+!. 2) Переход от 0 к О,„осуществляется следующим образом. Если за этим переходом следует переход от О,„к О,„или переход от 0 к О, есть последний шаг в процессе построения множества 0„, то используются формулы, приведенные выше: Оп"",=0';"' О',""'+Опав =4гп 1=-1 2 т (21) Если за переходом от О„к О, следует переход от О,„к О, „, то используются формулы ОД"(=О,'"', 0((",'+01( '=4т+2, 1=1, 2, ..., и. (22) Используя эти правила и чередуя должным образом переходы от множества с четным числом элементов к множеству с нечетным числом элементов и от множества из т элементов к множеству из 2т элементов, можно, исходя из О,=(1), построить множество О„для любого и.
Приведем некоторые примеры. 1) п = 15. В этом случае переход от О, к О„осуществляется по следующей цепочке: В, В, О, О,-в,-в„-воо Согласно изложенным правилам переходы от О, к О„от О, к О, и от О, к О„осуществляются по формулам (22), а при переходе от О, к О„от О, к О, и от О„к О„нужно добавить соответствующее нечетное число к исходному множеству. Это дает: О, = (! ), О, =- (1, 5), О, = (1, 5, 3). О,= — (1,!3, 5, 9, 3, 11), О,=(1, 13, 5, 9, 3, 11, 7), О„ = (1, 29, !3, !7, 5, 25, 9, 21, З, 27, !1, !9, 7, 23), О„ = (1, 29, 13, 17, 5, 25, 9, 21, 3, 27, 11, 19, 7, 23, 15).
Множество ВК„упорядочивается по формуле (20). 2) и=-25. Этому случаю соответствует цепочка О, О, В, О, О„В„-О„, и переходы от О, к О, и от О„к О„выполняются по форму- лам (22), переходы от О, к О, й от О, к 0„— по формулам (21), переходы от О, к О, и от О„к О„осуществляются добавлением нечетного числа. Получим В, = (!), В, = (1, 5), О, = (1, 5, 3), О, = (1, 11, 5, 7, 3, 9), О„ = (1, 23, !1, 13, 5, !9, 7, 17, 3, 21, 9, 15), О„ = (1, 49, 23, 27, !1, 39, 13, 37, 5, 45, 19, 31, 7,'43, 17, 33, 3, 47, 21, 29, 9, 41, 15, 35), 282 О„ = (1, 49, 23, 27, 11, 39, 13, 37, 5, 45, 19, 31, 7, 43, 17, 33, 3, 47, 21, 29, 9, 41, 15, 35, 25). Изложенная выше процедура построения множества О„для произвольного и может быть формализована.
Для этого представим п в виде разложения по степеням 2 с целыми показателями Й,: в=2» +2» +... +2»», й (й~ » — 1, 1=2, 3, ..., з. Образуем следующие величины: ! и.= ~ 2»' «у, I »=! 1=1,2, ...,з, и положим а, », = 2л + 1. По формулам (23) строим множество О„: ! О„= (0,7 =О, 7, О„,' =пу, 1=1, 2, ..., пу — 1~, (23) 0,„=(ОЯ '=4т — 01~', 01)~,'=01»», 1=1, 2, ..., л») (24) для и»= л7, 2иу, 4п~, ..., '1(ат,» — 1)/4], где (а! — целая часть а. Если ((а~,— 1)(4! ( и,, то вйчисления по формуле (24) не проводятся, выполняется переход к следующему этапу.
Если 1=», то необходимое множество О„уже построено. Иначе полагаем т=(п7+,— 1)12 и строим множество О, =(01»» '=4л»+2 — О', ', ОЯ,'=О,' ', 1=1, 2, ..., »и). (25) Затем ! увеличивается на единицу и процесс повторяется, начи- ная с формулы (23). В результате будет построено множество 0„. Множество Щ упорядочивается согласно формуле (20). Для случая п=2» алгоритм (23) — (25) упрощается и пере- ходит в алгоритм, описываемый формулой (19). Действительно, для а=2» получим »=1, л,=р, п,=1, п,»,=2» ' — !. Следо- вательно, в алгоритме (23) — (25) ! принимает единственное зна- чение, равное единице, и вычисления ведутся по формуле (24) для л» = 1, 2, 4, ..., 2»-», Проиллюстрируем качество построенного здесь упорядочения множества ОК„" на примере, рассмотренном в и.
4 32. Задаваемое число итераций п изменялось от 16 до 5!2 с шагом 8. Для каж- дого и реальная точность, достигнутая после выполнения и ите- раций, не превосходила теоретическую точность д„(ц„, = = 1,23 10-'), и процесс был «безавостным» (см. табл. 5). 283 для ! =1 выбираем 0,=(1). Затем по формуле (24) строятся множества 5 3. Метод простой итерации 1. Выбор итерационного параметра. В 3 2 была решена задача о построении оптимального набора итерационных параметров т„ для двухслойной схемы в предположении, что оператор РВ 'А самосопряжен в Н и заданы 7; и 7, †постоянн энергетической эквивалентности опе.
раторов Р и РВ-'А: 7,0<РВ 'А(7,0, 7, ) О. (1) Получим теперь решение этой задачи при дополнительном ограничении ть=т, т. е. в предположении, что итерационные параметры ть не зависят от номера итерации я. Эта задача возникает при нахождении итерационного параметра т для стационарной двухслойной схемы Уй+1 УЯ 1 Ау ~ й О ] (2) Напомним формулировку указанной выше задачи: среди полиб помов степени п вида 9„(1) =П(1 — т,1) найти полином, паиме/=1 нее уклоняющийся от нуля на отрезке (7„7,]. В силу сделанного ограничения полипом Р„(1) имеет вид В (!) (1 т()и Поэтому поставленная выше задача эквивалентна следующей: среди полиномов первой степени, принимающих в точке ! = О значение единица, найти полином наименее уклоняющийся от нуля на отрезке 1'7„, 7,).
Эта задача является частным случаем рассмотренной в 3 2 задачи. В данном случае п = 1, и из результатов п. ! 2 2 следует, что искомый полипом имеет вид 9(1)=-дТ( ), т= —, р= —, 71 — та1'~ 2 1 — $ Ра ) тих+та !+$ ' 7з где Здесь Т, (х) — полипом Чебышева первого рода. Так как Т, (х) = х, то полипом Я,(1) имеет вид Я, (1) =! — 7,1, шах ) Я, (1) ~ = д, = р„ 7 <~<тз 284 поэтому Р (1) =(1 — то!)". Таким образом, оптимальное значение параметра т для схемы (2) найдено: т = то = 2! (у, + уо). (3) Так как норма разрешающего оператора Т„, для схемы (2) (см. п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
