Бабенко - Основы численного анализа (947491), страница 152
Текст из файла (страница 152)
П '33. Несколько замечаний о построении алеоротмоо без насыщения 739 Замкчлник 1. В гл. 8 мы впдели, что полученный результат еще не парантнрует практической пригодности метода простых итераций для решения системы (8'). Важна еще и структура матрицы б, а именно отсутствие жордановых клеток высокого порядка. Хотя матрица б и несимметрическая, но очень мало от таковой отличается. Ниже покажем, что задача на собственные значения (1 — ЛФ)б = 0 является аппроксимацией спектральной задачи для оператора — 21, и поэтому нет оснований ждать патологии в структурных свойствах матрицы Ю.
ЗАмечАние 2. Из результата зада юи 2 шгедует, что,11 — Ь~ ~( < СМ" 1п гУ, и поэтому прн г1 > Ао утверждение теоремы 1 остается вер-ша э ным н дгш системы (8). 3. Строение матриц сопзроксимвции. Матрицы 11, 45 имеют весьма примечательное строение. Рассмотрим вначале строение матрицы 0 — гб м, где о . (рп)'.а=~ Ы = Лай(ч(-„))ь н Таким образом, необходимо исследовать матрипу гб, Прежде всего отметим, что имеет место предложение, аналогичное предложению 1 3 5 гл.
4 и предложению 1 3 5 гл. 9. Введем интерполяционный многочлен б2н(щ б) = (1 †:я о) ~ ' ,1,(х) = ~ б,оз(а), ,,1 — !АР ' Подчеркнем, что прн определении фундаментальных многочленов 1з( ) мы полагаем п1 = ... =- пп и =- 21; пусть т =- ш1п(п — 1, пг). Учитывая результат задачи 1 35 гл. 3, имеем 1;1н о юх, +ж Рассмотрим матрицу Ж вЂ”.
Предложение 2. Матрица Ус обрапиом; если М"" ~э1 = 8, гоо н 5, = — Е 1С( „1)1 (1)2 о Л=-1, о......, ~У., а=1 в оли, дрреоми словами. (21) Мы не будем приводить доказательство этого предложения. Оно совершенно аналогично доказательству предложений 1 3 5 гл. 4 и 1 3 5 гл.
9. Соотношение (21) может быть ключевым для вычисления элемонтов матрицы М, поскольку элементы матрицы Ж вычисляются элементарно. В случае небольших п, и па 0 =.- 1, 2,, 1) можно вычислять элементы матрицы Ж непосредственно. Докажем, что матрица Ж содержит всего (о/2)о(ог -' 1), а не Х различных элементов н для фиксированных величин и, = ... =- по и = 21 вычисляется один раз независимо от той области П, в которой первоначально ставится задача. Поэтому (п/2) (пг —,' Ц с<ютветствующих элементов матрицы Ж вычисляются один раз.
740 Глава 10. Некоторые вопросы численного решения краевых задач Представим матрипу сд в блочном виде; с этой целью занумеруем узлы интерполяционного многочлена 1эм двумя индексами к, 0; яь, (lс = 1, 2, ..., и/2, 1 =- О, 1, ..., 2пс). Тогда, учитывая формулу (3.5.!4) н обозначая функции дз(с) (определяемые по формуле (7)) через дь,(е), получим с 2 дьз(е) = с([гь(р) — ть(р)] !птах(р, г)+ дгсс +! у о — [(рг)" — о'] [1ь(р) — ( — 1)'гь(р)] сов м(0 — 01]) р с!р, =1 где г = )е[, 0 = агк г, 0 < 0 < 2к, 1ь(р) = Т„(р)(р -- т) '[Т„'(гь)], ге(р) =- = Т (р)(р+гь) [Т" (гь)]; функция о = о(р; г) определяется соотношениями и = гр, если г < р, и и = рг, если р < г.
— г — 1 Положим 2 ор(!с, 1) = ! [(ргс)" — ь"] [сь(р) — ( — 1)"гь(р)]рйр, р = 1, 2,..., и, (2пс -1-1)р у о где г определяется по г = гь При р = 0 положим с оо(к, 1) =, !ишак(р, гс) [1ь(р) — гь(р)] 0 с(р, о и пуСть р(1с,1;0) =~> а (1с,1)сов, 0=0, 1,,,,, 2тм. 2лру 2пс — ' 1' р=о (22) Тогда дю(гс ехр(10,)) = р((с, 1; в — 0). Наедем матрицы р()с, 1; О) р()с, 1; 1) ... р()с, 1; 2пс — 1) р()с, 1; йпг) р(к, 1; 2ис) р(1с, 1; 0) ... у(1с, 1; 2пс — 2) р(1с, 1; 2пс — 1) еды = рЯ, 1; 1) р()с, 1: 2) ... р(1с, 1; 2пс) рЯ, 1: 0) )с, 1 = 1, 2,..., и)2.
с сдгг 'досад еда дк 72 . д /2, уз Таким образом, для образования матрицы сд нам нужно вычислить (сс/2) (ос —: + !) величин ор(в, 1) (р = О, 1,..., пи 1с, 1 = 1, 2,, и,,с2). Умножение матрицы сд на вектор 0 требует не с< Н~ операций, а — (и/2) с(2гп + 1) !ояс(2пс -1-1) Матрицы (дса - циркулянты; при притштом способе нумерации узлоа матри- ца сд будет иметь блочный вид: 3 3. Несколько важечапий а построении аяворнтлгое бев нисып!ения 741 операций. В самом деле, чтобы убелиться в справедливости этой оценки,под- считаем число операций прн умножении матрицы гльгна вектор ~ б тг Если г, .=- (Оо, ..., С2„)', то компоненты вектора Мы~ в силу формулы (22) будут имЕть вид 2р1 1 Г 2и1 1=О р=е 1'=О 2 21гв12 т 2лру' -!- в!и, 22 б, вш йип !.1~ 2пг-!1 1.=0 и, таким образом, нужно четыре раза воспользоваться алгоритмом ЬПФ (см, 3 3 гл. 1); вначале вычислить величины 2, 2 1 2лрг х 2лр2' 'ср:~2' бгсов 1 йр = 2 сгв!и 1 !2: О 1 ...
'п1 в=о 2пг + 1' 2и1-!-1' 1=2 а затем вычислить Р 1 22 вр . 2твр ~ор(18 !)(яр сов + дрсйп ), в = О, 1,, 2пз, 2иг + 1 " 2пг + 1)' р=о гп;2 1 Тмя х ( — ) (2иг — 1) 1ой. (2пг .! 1) !ой— "хЫ- (23) операций. Если в задаче (2) правая часть г" —. гладкая функция, то целесообраз- но правую часть в уравнении (8) вычислять, игпользу я для аппроксимации г" (2) интерполяционный агрегат Рп(2:, !). Тогда г(2) — -- Рм(2! У) + Ли(-' () Р(2.) =- — 2 У(21) / !2(!) С(вю Г)стг — / С(вв, !) Е(и(!! Х)г(ог + ое(2,), 1=1 и и, отбрасывая остаточный член, получим, что компоненты вектора правых ча- стей в уравнении (8) равны а, = — ~ дв(2,) ((22) + оо(2,-), в = 1, 2, ..., бг. (24) Допустим, что в задаче (2) функция /1 = О.
Тогда полученный результат мовсно сформулировать следующим образом. На все это потребуется х (2пг + 1)!о82(2п1 -!- 1) операций, если 2пг + 1 = 3 (р ) О целое) (см. 8 3 гл, 1). Поскольку Ф = гвЫ, то из замечания 2 к теореме 1 получаем,что для решения системы (8) с погрешностью с требуется 742 Гласа 10, Пскоторые вопросы числскного решения краееыг задач Теорема 2. Пусть выполнены услоеэ я предложения 1. Систему (8) можно решапэь методом простой игаерацииэ т1'~ = (1 — о)ц +о'угэз + па, о = О, 1,..., где и ) О,.
причем итерации сходятсл со скоросэпью геометрической прогрессии со знаменагпеээам р < 1, независящим от эээ. Если правые части системы (8) еычишэяюпэся по формуле (24) и ц — ее точное решение, а цо — д-я итерация, для которой ~ц — цо,:сь < е, то, полагал и"(г) =- 2' ц" (э(г), будем э::1 ~(и (г) — о(г)~ < Се(1-~-)Рн ) [Е,„(ээ) — , 'Е,(ооЯ вЂ” ' 1- С,(1 -. ~1эн( ) Е Ц) 4 е(Рн( .
(25) Дяя оьэчисления и" ( ) требушпся Тнл операций, где Тмл даеэпся форму- лой (23). Докязятнльствсь Оно ясно из предыдуэцих рассуждений. В пояснеэпги нуждается, люжет быть, неравенство (25). Оно следует из (18), очевидного неравенства и того факта, что при изменении правой части системы (8) на некоторый вектор б. ее решение меняется на величину 0(~(1 — ог2) '~ )б.~ ). Нам остается только учесть, что б = дг, где Х(л) — —. — ) С(з, 1) Йь(Ц 1")доэ, и воспользов ваться для оценки Вн(; 1) результатом задачи 1 35 гл.
3 н неравенством Лебега. П Из оценки (25) следует, что щэедлагаемый алгоритм не имеет насыщения, и в случае гладких функпий о, )." и гладкой границы области он будет иметь огромные преимущества перед другими алгоритмамп. Замвчянпк. Хотя матрица системы (8) и является заполненной, тем не лгенее число операций дается формулой (23). Крайне интригующий вопрос возникает в связи с формулой (23). Нельзя ли в ней множитель (п,э2) заменить на (и)2) 1обг(ээ/2)7 Ведь мы не воспользовались тем, что по переменной г интерполяция делается по чебышевским узлам.
4. Яисленньэе примеры. Рассмотрим некоторые численные примеры. Дадим применение предложенного способа дискрстизапии к задаче на собственные:значения †(3и)(х).~- йа(х) и(х) =. Лро(х) и(х), х й 1), ээ~ — — О. (26) Для такого рода задач крайне важно, чтобы численный алгоритм их решения не имел насыщения. Переходя от области (1, кото1эую лгы по-прежнему считаем односвязной, к кругу В с помощью отображения В э г ьч б й Й, придом к задаче на собственные значения — и)(г)+й(г) о(г) = Лр( )э'(г), = б В, и! = О, (27) 3 3. Несколько замечаний о построеипи алеорптмое без пасът1снил 743 где о = ]1д(я)] оо о р, р = ]тд( )] ро о,р. Производя аппроксимацию, которая приводила к уравнению (8), с учетом того, что ! = Лра, и в силу формулы (24) получим а = — Ласт, где 'У! = с11а8(р(г!))' .
Пусть г1 — приближенное значе!=! ние вектора Уг. Тогда вместо системы (8) получим алгебраическую задачу на собственные значения (Т вЂ” Ф)!1 = — Л!В!1, (28) где 'З = Ягг. Еш!и оо —.— О, то мы сразу получаем стандартную задачу на собственные значения (!В -1- Л Т)г1 = О. (26) Аналогично получается и дискретизация задачи на собственные значения, когда вместо условия первого рода березтя условие второго рода или условие третьего рода. Детальное построение алгоритма читатель найдет в работе ]16]. Если О < б < ро(я) < со, т б 11, то спектр задачи (26) дискретный, а собственные значения Л 0 = 1, 2,...) можно занумеровать так, чтобы Л! < Л! < Лз < ...
и притом Л вЂ” ! оо, Максик!ачьное собствеш!ое значение д! матрицы —. 'З дает приближенное значение для 1/Л!; остальные ее собственные значения будут давать приближение для величин 1/Лг, !/Лз,... Теорема 2 является надежной эвристической основой для утверждения о том, что предлагаемый алгоритм отыскания собственных значе!шй и собственных функций задачи (26) не имеет насыщения. Точное утверждение, аналогичное теореме 1 36 гл, 9, можно доказать и в данном случае, Однако мы это делать не оудем.
учитывая, что в случае надобности можно проделать процедуру апостериорной оценки погрешности. Пвимнн 1. Пусть исходная область П совпадает с кругом Н, и пусть оо .—.. О, ре = 1. Тогда известно, что собственные функции имеют вид о —.. = ехр(ЖР)уь( /Ль, т) (к = О, 1,...), где оь( ) — функция Бесселя первого рода, а собственные значения Ль! выражаются через ее нули, поскольку Уь(ъУЛьз) —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
