А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 50
Текст из файла (страница 50)
у„Е(Се-.у,Е, у,>0, С=С*=0 г~ч(РВ 'А)Р-и'. (6) Действительно, полагая в неравенствах у,(0х, х)((ОВ 'Ах, х)(у,(0х, х) х= Р ы'у, получим неравенства (6). Таким образом, сделанные выше предположения относительно операторов А, В н О эквивалентны условиям (6). Сформулируем теперь задачу об оптимальном выборе итерационных параметров для схемы (2). Из определения разрешающего оператора Тм, и условий (6) следует, что оператор Т„,=Т,(С) самосопряжен в Н и норма операторного поли- нома Т„,(С) оценивается следующим образом: и (Т„,!~( шах ~ Ц (1 — те!) т, к 1 к ты е = 1 Из оценки (4) следует, что в самосопряженном случае итерационные параметры т„т„..., т„должны быть выбраны так, и чтобы максимум модуля полинома Р„(!) = Ц (1 — те!), построй=1 ениого по этим параметрам, на отрезке (у„у,1 был минимальным, т.
е. нужно найти параметры из условия и ппп шах ~ Ц (1 — те!) = шах (Р,(г) (. (~е) т к ~ кт* ! е = 1 т с ~ < т Тогда для погрешности метода (2) будет верна оценка (г„!!а( (д„(г,()о, где шах ) Р„(!) !. т1 к ~ < т1 Сформулированная выше задача является классической задачей минимакса. В 9 2 будет приведено решение этой задачи и будет построен набор итерационных параметров т„ т„ ..., т„'. Итерационный метод с этим набором параметров называется чебышевским методом. В литературе этот метод называют также методом Ричардсона, 9 2. Чебышевский двухслойный метод 1. Построение набора итерационных параметров. В 9 ! было показано, что построение оптимального набора итерационных параметров т„т„..., т„сводится к нахождению полинома 269 Р„(1) вида Р„(1)= Д (1 — тьг), максимум модуля которого на ь=! отрезке [у„у,) минимален. Решим эту задачу. Так как вид полинома определяется условием нормировки Р„(0) =1, то указанная задача формулируется следующим образом: среди всех полиномов степени п, принимающих в точке Г = 0 значение 1, найти полипом, наименее уклоняющийся от нуля на отрезке [у„у,), не содержащем точку О.
Решение этой задачи было получено русским математиком В. А. Марковым в 1892 г. и приведено в дополнении. Искомый полином Р„(1) имеет вид г де Т„(х) — полином Чебышева первого рода степени и, соз (и агссоз х), < х < ( 1, Т„(х) = сп (и Агсп х), <х<) 1, «+ы'О,г~ 6~(й~1~уй При этом гпах < Р„(1) < = д„. Отсюда следует оценка для к ~ ~ тя нормы погрешности г„в Нп. << г„<<о ( д„<< г, <<и, (3) где д„определено в (2). Получим формулы для итерационных параметров. Так как полиномы, стоящие в левой и правой частях (1), принимают при 1=-0 одно и то же значение, равное 1, то тождество в (1) будет иметь место лишь в том случае, когда множества корней полиномов Р„(г) и Т„( — ') совпадают.
Полипом Р„(г) имеет о корни 11ты А=1, 2, ..., и, а полином Т„(х) имеет корни, рав- ные — сов( и), 1=1, 2, ..., и. Если обозначить через И„ /Гн — 1 множество корней полинома Чебышева Т„(х): 2г — ! %,=.(-соз — „и, 1=1, 2 ..., и), (4) Здесь рьЕй)(„означает, что в качестве ра должны выбираться последовательно все элементы множества Ы„. Из полученной формулы для параметров т видно, что для вычисления итерационных параметров требуется задать число 270 то получим следующую формулу для итерационных параметров: та=то/(1+рюрь) )габй))л й=1 2 и (б) итераций и. Поэтому оценим число итераций.
Обычно в качестве условия окончания процесса итераций берется неравенство ) г„!)р(е(го!~о и числом итераций называют наименьшее целое и, для которого это неравенство выполняется. Из (3) следует, что для рассматриваемого метода число итераций находится из неравенства д„(е. Используя (2), решим это неравенство. Получим и ) п,(е), п,(в) =1и ~ —,+ у —,— 1р 1п —. Ро Обычно используют более простую формулу для п,(е) п~)п,(е), п,(е)=!п — (!п —. 2/ ! (6) После того как найдено требуемое число итераций и, по формулам (5) можно построить набор итерационных параметров.
Итак, для неявной двухслойной схемы ВУ',"' ~" +АУь=1 й=О 1 ° УоЕНо (7) доказана Теорема 1. Пусть выполнены условия 7,0 к-. РВ 'А к-. уо0, у, ) О, РВ 'А =(РВ 'А)', Р= 0* > О. (8) Тогда чебышевский итерационный процесс (7), (4), (5), (2) сходится в Нр и для погрешности г„имеет место оценка (3). Для числа итераций справедлива оценка (6). Из полученных оценок следует, что в самосопряженном случае скорость сходимости чебышевского метода зависит от отношения а=ус'у„причем скорость сходимости будет тем выше, чем больше $. 2.
0 неулучшаемости априорной оценки. Покажем теперь, что на классе произвольных начальных приближений у, оценка для погрешности чебышевского метода, полученная в теореме 1, является неулучшаемой в случае конечномерного пространства Н. Достаточно указать такое начальное приближение у„при котором для нормы эквивалентной погрешности хь будет иметь место равенство (х„(= — д„'(х,!!. Мы найдем начальную погрешность х„ которая обеспечивает выполнение этого равенства, а начальное приближение у, в силу связи между погрешностью г„и хы го = Р-мох„определится тогда по формуле у, = и+ О-ыохо. Найдем искомое х,. Пусть Н вЂ” конечномерное пространство (Н = Н, ). Так как оператор С самосопряжен в Н, то существует полная система собственных функций о„о„..., он оператора С.
Обозначим через Хо собственное значение оператора С, соответствующее собственной функции оо. Пусть собственные значения 27! упорядочены Х,(Х,(... (Хч. Тогда в качестве границ оператора С можно взять у, = Х, и у, = Хм. В качестве начальной погрешности х, возьмем собственную функцию о,. Из уравнения для погрешности хд. хь+, — — (Š— т„,,С)хы А=О, 1, ..., х,=о~ и равенства Соь=Хьоь последовательно получим х, = (Š— т,С) х, = (1 — т,у,) о, = (1 — т,у,) х„ х, = (Š— т,С) х, = (1 — т1 у,) (Š— т,С) х, = (1 — т1у,) (1 — т,у,) х„ Подставляя в (1) 1=у, и учитывая равенство 1 — тоу,=р„ вычислим Р„(у,) = О„Т„(1) = д„и, следовательно, х„= д„х„(! х„~! = д„) х, (), что и требовалось доказать. Итак, показано, что полученная в теореме 1 априорная оценка неулучшаема на классе произвольных начальных приближений.
3. Примеры выбора оператора 0. Приведем некоторые примеры выбора оператора 0. Напомним, что чебышевский метод рассматривается в предположении самосопряженности оператора 0В-'А. Ниже будут указаны требования на операторы А и В, при которых это предположение выполняется для выбранного оператора О. Для каждого конкретного выбора оператора 0 будут приведены неравенства, задающие априорную информацию об операторах итерационной схемы. Эта информация используется для построения набора итерационных параметров в чебышевском методе.
Рассмотрим первый пр имер. Пусть операторы А и В самосопряжены и положительно определены в Н. Тогда в качестве оператора 0 можно взять один из следующих операторов: А или В. Если, кроме того, оператор В ограничен в Н, то можно взять 0 — — АВ 'А. При этом априорная информация сводится к заданию постоянных энергетической эквивалентности операторов А и В: Т,В(А(у,В, у,) О, В)О. (9) Действительно, нужно показать, что выполнены следуюшие условия: выбранный оператор 0 самосопряжен и положительно определен в Н, оператор 0В 'А самосопряжен в Н, а неравенства (8) и (9) эквивалентны. Самосопряженность операторов 0 и 0В 'А для всех рассматриваемых случаев следует из самосопряженности операторов А и В.
Для случая, когда 0==-А или 0==-В, положительная определенность 0 вытекает из положительной определенности ' 272 операторов А и В. Покажем теперь, что оператор Р=АВ гА также положительно определен в Н. Действительно, пусть выполнены сформулированные выше условия на операторы А и В: А =- А') аЕ, В = В*'=э ()Е, ) Вх)<М1х~(, а, (1 > О, М <со. Из этих условий и лемм 6 и 8 из 9 1 гл. Ч получим, что В ''= — Е и (Ах, Ах))а(Ах, х)- ! >и'(х, х).
Отсюда найдем для энергии оператора Р оценку снизу (Рх, х)=(АВ 'Ах, х)=(В 'Ах, Ах))~ > — (Ах, Ах)> — (х, х), т.е. 0)~ — "Е. Следовательно, положительная определенность оператора 0 =АВ 'А доказана. Покажем теперь, что неравенства (8) и (9) эквивалентны для рассматриваемого примера. Действительно, пусть выполнены неравенства (9): у,(Вх, х)<(Ах, х)<у,(Вх, х), у,>0. (10) Если Р=-В, то РВ 'А=А, и следовательно, неравенства (10) и (8) совпадают. Пусть теперь 0=АВ 'А. В этом случае РВ-'А =АВ-'АВ 'А и, полагая в (!О) х=В 'Ау, получим у,(АВ-'Ау, у) <(АВ 'Ау, В 'Ау) <у,(АВ 'Ау, у) нли у, (Ру, у) < (РВ 'Ау, у) < у, (Ру, у), т. е, получим неравенства (8).
Обратный переход от (8) к (10) очевиден. Пусть В=А, тогда РВ 'А =АВ 'А. Из леммы 9 9 ! гл. Ч следует, что для самосопряженных и положительно определенных операторов А и В неравенства (10) и неравенства у„(А 'х„х)<(В 'х, х)<у,(А 'х, х), у,>0 эквивалентны. Полагая здесь х=Ау, получим неравенства (8). Обратный переход очевиден. Это неравенство позволяет сразу доказать положительную определенность Р: (Рх, х) > ку, (х, х).
В самом деле, (Рх, х)=(В 'Ах, Ах)>у,(А 'Ах, Ах)= = у, (Ах, х) ~ )ур (х, х). Второй пример. Пусть операторы А и В самосопряжены, положительно определены в Н и перестановочны: А=А'>О, В = В' > О, АВ = ВА. Если в качестве оператора Р взять оператор А', то априорная информация может быть задана в виде неравенств (9). 273 Действительно, самосопряженность и положительная определенность оператора О следуют из самосопряженности и невырожденности оператора А. Далее, РВ 'А =А(АВ-') А, а так как операторы А и В перестановочны, то перестановочны и операторы А и В '.
Отсюда и из самосопряженности операторов А и В следует самосопряженность оператора РВ 'А. Неравенства (8) в данном случае имеют вид у,(Ах, Ах)((АВ 'Ах, Ах)(у,(Ах, Ах), 7,)0. Полагая здесь х = А 'Вп'у и используя перестановочность корня из оператора В с оператором А, найдем у, (Ву, у) ( (Ау, у) ( у, (Ву, у), т. е. получим неравенство (9). Обратный переход от (9) к (8) очевиден. Рассмотрим еще один пример. Пусть А и  — произвольные невырождеиные операторы, удовлетворяющие условию В"'А = А*В. (11) Если в качестве 0 выбрать оператор А*А, то априорная информация может быть задана в виде неравенств у,(Вх, Вх)((Ах, Вх)( у,(Вх, Вх), 7,) О. (!2) Самосопряженность оператора 0 очевидна, а положительная определенность следует из невырожденности оператора А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
