Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 96
Текст из файла (страница 96)
Такой функцией является, в частности, функция, осупгествляющая конформное отображение единичного круга на область В. Из теории конформного отображения следует, что такой выбор функции в(тв) является наивыгоднейшим, так как именно при нем досчигается наименьшее возможное значение 10(, Действительно, пусть г(тв) = а,я+ а,езз+ ... какая-либо допустимзя функция, з(0) = 1.
Далее, з = в (тв) = — а,ш+ азтва+ функция, осуществляющая конформное отображение единичного круга на область 1), ш =- Р (г) — функция. обратная к г(тв), О = Р(1). Покажем, что ) О ( с. 10 (. С этой целью рассмотрим функцию К(тв) =г. (з(ш)). Ясно, что К(0) = О, !г' (ш) регулярна в елиничном круге, 1В" (тв) ( ( 1 при 1тв) ( 1.
Согласно лемме Шварца ') для всех точек единичного круга будет ~ (р" ( ) ! < ~ ! Положив ш = О, получим (В (О)~=~Е(1)1=~0,(~0!. Знак равенства может иметь место, только если г (и) = з(шз), !е/=1, т. е. если функция з(ю) сама осуществляет конформпое отображение единичного круга на область г).
Метод конформного отобрзжения может быть приченен и в случае, если дополнение к 5, а вместе с ней и !) являются многосвязными областями. В этом случае наивыгоднейшей г(тв) является функция, осуществляющая конформное отображение единичного круга на универсальную накрывающую область В риманову поверхносчь. Перейдем теперь к описанию вычислительных схем метода.
В работе (2] В. Н. Кублановской приведены вспомогательные таблицы коэффициентов полиномов 1.,(1)=1+00,(1)+Оба(!)+ ... +00,(1)= — 1„+1ы1+ ... +1„1', для ряда отображающих функций г(я) при з=б и з= !О. Это позволяет вычислять приближения Е.,(В) О к решению Х как линейную комбинацию последовательных итераций О, ВО, В'О, ... или посредством применения схемы Хорнера.
При этом приходится заранее фиксировать число взятых в формуле (8) членов. Ограничиваясь небольшим г трудно рассчитывать на получение достаточной точности. Однако однократное применение приближен- т) См. цитированную на стр, 090 кингу Г. М. Голузина, стр. 29 9 95] пгименение конеогмного отовелжвния 595 ной формулы Х=Е,(В)0 можно рассматривать как элементарный шаг итерационного процесса Х'~ =Х ~+А,(В)гь л, где га,—— в! 1ь-0 =ВХ!" ')+6 — Х~ Легко построить вычислительные схемы метода, использующие лишь коэффициенты а отображающей функции г (ш). Именно, из тождества ]1 — 1(алга+ а.,таз+ ...)] (1+ Ь, (1) ш+ Ьа(1) шз + ...] = 1, равносильного формуле (6), получаем рекуррентные соотношения для полиномов Ь;(Г).
Именно, Ь, (г) = ал! Ь,(Г) =а,1Ьл,(1)+а,1Ь; зЯ+ ... +аз,ДЬл(т)+а;1. (9) Обозначив Ь;(В)6=0о бе= О, получим Ол=В(а,О;,+ ... +а;Ое) (1=1, 2, ...) Х= ~ О'Оп (10) Компоненты векторов 6; будут или не возрастать, или возрастать очень медленно, нбо радиус сходимости ряда ХО;ш' равен единице. Рекуррентные соотношения, аналогичные (9), можно установить и для полиномов Е;(1).
Именно, легко проверить, что Е.;(г)=1+алОг)л,(1)+а,ОлтЕ; з(г).+ ... +алОт].,Я. (1!) Это дает возможность строить по рекуррентным формулам сами последовательные приближения Х; == Е; л(В) О. Именно, Х,=О, Ха=О+а,ОВО Х;=О+алОВХл,+азОлВХл + ... +а,,О! 'ВХ,. (12) Очевидно, что формулам (12) можно придать вид Х, =О, Х,=(1 — а,О)0+а,О(ВХ,+6) Х;=(1 — а,Π— алба — ... — а;,О' ~)0+а,О (ВХ;,+6)+ +а;,О' '(ВХ,+6). (13) Вычисления по рекуррентным формулам (10), (12) или (13) требуют несколько большего числа вычислительных операций, чем вычисление при помощи заранее вычисленных коэффициентов 111, но имеют то преимущество, что нет необходимости заранее фиксировать число членов ряда. Формулы (13) соответствуют п.
7 9 86. Для получения формул, аналогичных п. 8 9 86, введем в рассмотрение полинам 1л(Г)=1 — (! — 1)Ц лИ). (14) 596 [гл. гх хниввгслльные ллгоеиемы Легко проверить, что полиномы (г«) связаны рекуррентными соотношениями !г«)=а,банг,«)+ ... + аг,0~ гг1,(г)+ +(1 — а 6 —... — а;,0' ') Ю. (16) Отсюда для Е-го приближения Х;=1;(В)Хо получим Х; = а,6 (ВХ;, -[- 0) + ... + аг,0' '(ВХ, + 6) + +(1 — а,6 —... — а;,0' ')(ВХо+6). (16) Формула (!6) преврашается в формулу (13) при Хо=О. Во многих случаях оказываются более удобными рекуррентные формулы, построенные исходя иа коэффициентов «разложения в ряд по степеням ге функции †.
Эта функция будет регулярной, ибо а = О только при те=О (если область П многосзязна, функция — будет мероморфной). Пусть — + „=«о+~,тв+«гта'+ ...; «о Ф О. (17) Тогда «о+ «гю + «ггог+ 1 — ег го «о+«гго+«ты+ ° .. — à — — его е «о+«гго+«гге + ° ! [ 0 (1) и [ 0 (1) г [ (16) Отсюда, приравнивая козффвциенты при одинаковых степенях, получим «обг «)+(«г 1) — «г «обг(т) [-(«г — 1) 0,(Г) =О «обо «)+(«г 1) бо-г«)+ «гбг — г«) '+ + «г-А«) = О, (!9) так что 0,«)= — 1; 0,«)= — '0,«) 1 à — «г "о «о 0,(~) = :„ "' бг , «) — "— г 0г г «) — ... — «г-г 0, (Г) « > З). (9О) "о 9 95) ПРИМЕНЕИИЕ КОНФОРМНОГО ОТОБРАЖЯНИЯ 597 Формулы (20) позволяют вычислять векторы 01 в формуле (10) по рекуррентным соотношениям 1Го "о (21) (1: 3).
Легко вывести также и рекуррентные формулы для полиномов 51(1) и 11(1). Именно 7О(1)=1: 71(1)=1+ — ~; 71й)= ( „1~11Я+ Еап е1-!л 7 (Г) В(1 — Н1) 7 (1) В.«а 5 (1) . Е Л1-1 7 (,)+ (22) э ло 0 и, + и,в+ ... + л1 1в'-1 ло Далее, О ла 0 + '+ЛВ " +Л'-ав' ' '11(г) (1>3) ло (23) при 11(0=1, 11(Г)=1 — — г+ — 11.
в в П1 Но Поэтому последовательные приближения можно вычислять по фор- мулам (24) (1> 3) или по форчулаи Х,=ВХ,+О; Х, = — (ВХ,+О)+ — 'Х,. В Еп„Вена Вг-1П Ха = — (ВХг 1+0) — — 1Х; — еХ; — ... — 1ХЕ+ ло "А+и~в+ +л1-ае' ~ Е Х (1> 3), (25) ле 1 Рассмотрим теперь метод конформного отображения с точки зрения идеи подавления компонент. Пусть Хе исходное приближение, 01= 1 Во; ле 1 01 = — В01 1 ла Х,=О; Х,= — ВХ, +Х, ло Е ВЛ, Вена Хе= — ВХ;,— — „Х,— — „аХ; + «,+иге+ ...
ло вг-ел1 т + а го + 1, евг-1 ! 598 УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ !гл. ~х Х'= Х, =Хе+ А,,(В) ге, ге = ВХе+ Π— Хе, Тогда соответствую- щие векторы ошибок связаны соотношением 1" = !'о — 1.. г(В)го=)а(В) 1'о где 1,(Р) = ! — (1 — 1)1,,(Р). Оценим )1,(1)) для любой точки 1, принадлежащей множеству 5, Пусть О ч ре ч. 1, См образ окружности !ш)=Ре при отображе- нии а=г(ш) единичного круга на область О. Имеем ~бу(!и =~ — ' —, 2., ) .„„—,*(.а ( !"! и Пока /те)=ре, функция г(тв) пробегает кривую Ср,. Если 1~5, то 1 — не принадлежат области О. Поэтому 1 — Рг не равно нулю при 1~ 5, а~0 и !1 — Ра! равномерно ограничен снизу константой гРР.. пока г~СР„,, 1~5.
Поэтому имеет место равномерная для !~5 оценка /б (1)! ( ! 2иае 2и ра И~ М рак Ро е Ре Таким образом, на основании формулы (7), (1)! ~~ ~ ~ты ! (1) лэ «~ ~ч~т~ (И !) ! ! Ро Ро откуда )1 (1)( ( ! — 1~ — аРа (С(ав)!(!+А)!О ~!'. Ро1!! Ро 1 Здесь е = — — 1 положительное число, которое можно сделать сколь Ро угодно малым, С(ре) = шах!(! — 1)( ! Итак, компоненты ~в~~' вектора ошибки „затухают" по крайней мере со скоростью [(!+а) ~0! !'.
Сделаем следующее замечание относительно применения метода конформного отображения. Если в систему Х= ВХ+ 0 ввести параметр г в виде Х = ЕВХ+ р (г) О, где р(г) регулярная в области В функция, обращающаяся в единицу при а = 1, то по методу конформного отображения решение исходной системы получим в виде Х = се0+ !)с, (В) 0+ бас (В) О+ ..., 9 96) пРимеРы 5"унивегсальных Алгоаиемоа 599 !де с!(() полиномы, являющиеся коэффициентами в разложении функции ( =се+с,(1)те+с (Г)таз+ ...
Здесь а(ш)=р(з(тв)) функция, регулярная в единичном круге. При любом выборе функции е(г) (или, что то же самое, Р(а)) порядок быстроты сходимости будет одним и тем же. 9 96. Примеры 3-универсальных алгорифмов Рассмотрим теперь несколько конкретных 8-алгорифмов. Как мы видели выше, каждый ~акой алгорифм определяется ограниченным замкнутым множеством 5, содержащим собственные значения матриц В. 1 1. 8 — круг радиуса —, () 1 с центром в начале координат (рис. 29). В этом случае область О есть внутренность круга радиуса ( 7 с центром в начале координат. Отображающая функция есть ! ! 7 з(ш) = Ттв. т Поэтому последовательные приближения вычисляются по формуле хг=вхг,+а, т.
е. в этом случае мы приходим к классическому методу последова- Рис. 29. тельных приближений. 1 11 2, Я вЂ” отрезок вещественной оси ~ — —, — ), у~ 1 (рис. Яб). т В этом случае область В есть плоскость с двумя разрезами вдоль 1 Рис. 30. вещественной оси, исходящими из точек — у и у в бесконечность. Отображающая функция есть 21м — В=т — Ута — ! ° !+ гав ' . [гл. »х бое униваРслльныв ллгоРиемы Однако в этом случае функция будет еще проще.
Именно, а( ) — = — (1+в ), так что»[о — — с»а= —,, »Р»=»»з=п»»= ° ., —— О. иу 1 «(ж) 21 е а 21» з 4 Поэтому последовательные приближения удобно строить по рекуррентным формулам (25), которые обращаются в формулы Л 210 (ВХ», + а) егх» =(1+0 ЦВХ»,+а) — ЕХ», при»> 3 х,=вх,+а, х,=210(вх,+а)+(1+210)х,= = (1+0») (ВХ, + а) — 0»Х,. 1 1 в точках — — ,— а а Рис. 31, будет внутренностью некоторого овала. Отображающая функция есть Р= » 1, В= 2ртэ т Гта т 7 та 1 6» где 0,=1 — р' '[а — 1.
Снова функция — оказывается квадратным полиномом «( ) + тва р 2рт 21 Поэтому 1 ° »Ро = —. »Ра = — »Р»»1» = »2» = ° ° ° = ») ° 2р1' 21 Процесс почти мом с постоянным началом процесса. 3. 5 — эллипс совпадает с универсальным трехчленным алгорифмножителем а= оа (е 91), отличаясь от него лишь 1 1 с фокусами в точках — — и — и с вершинами т т 1 ~ и) 1 (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
