Бабенко - Основы численного анализа (947491), страница 138
Текст из файла (страница 138)
Для конкретности рассмотрим суммирование по индексу ЙН с этой целью положим й = (6м 1), сй = гвй, (1). дй =. рй, (1) и в дальнейшем опустим мультииндекс 1. Таким образом, нам надлежит преобразовать сумму Гюй,. г -- юй, юй, -- юй, .1г 61 1н й1= а причем ом бй зависят от мультииндекса 1 и ид1 1 =. ю, 1 .= О. Ясно, что д1 д1 х 1 юй, юй,.1 — юй, г 1, х юй, Яг =-. т -- ' ' ' — 'рй,юй, — , 'г юй, 1 1 й1=а1 д1 д,— 1 ( — е 1 1 трй гвй ) + ~ ~гвй,+1 1 1 й1=а1 6 — юй, юй, тй — юй, 62 1 Но юй, й(юй,тй — юй,) юй, 1 — юйа г 6' й1=а1 — 1 поскольку юв, 1 =. О.
Поэтому и поскольку аналогичное неравенство справедливо при суммировании по остальным индексам, то неравенство (19) доказано. Обозначим через Лр (Лг < ... < Льт) собственные значения оператора Е, а через 4~Р соответствующие собственные функции уйл: юй а 4". Чтобы записать уравнения для определения собственных функций и собственных значений, достаточно в уравнениях (9) сделать замену 6* 6 э ьй ь- у~йв, 7й ч-- Лрйй'„' и предположить, что ах(г:) .=. 1 (у =- 1, 2, ..., 1); граничное условие (10) нужно заменить условием 678 Гласа 10, Нсиоторис попроси числсииого рсигсни ирасомх,сарач Таким образом, (УСйа)ь — -- Лги~~, ша Е Йсб (У аао)ь = ЛргдГм х" Е дйь Л Гь (20) Отса>да, принимая во внимание формулы для 'х' и У*, имеем Лр шах И~~ ( ~~46 в+ гаахдь1 п1ах ~ф.
1=1 Таким образом, Л„( ~~ 46 + шах 9ы г..1 (21) Далее, применяя к системе (20) предложение 7 з 7 гл. 3, получим неравенство в шах 15 ( пшх ~ис„~+ — шах~гав, ь хгега ' 21 ь откуда в силу граничных условий Лр > 21а7 т. Итак, 21с( ~ ( Л1 ( ... ( Ли ( 4 ~~~ 6 ~ — пихаю ь о=! (22) гь~ — — уь — (.Ки~)ю х Е Йрб гь~ — — уь — (.У*ни)ем х Е Йа ~ Гш (23) причем, когда вычисление ведется по второй формуле, то учитывается,. что иь — — рю если х~ е Гь. ь1ерез и = (иь.
6 е М') обозначен вектор неизвестных на и-й итерации. Если мы воспользуемся методом простых итераций, то вычисление будет производиться по формуле (8.5.12) либо (8.5.14), которые в наших обозначениях записываются в виде и'=и' ~+тг ~, и=1,2, (24) О. Итерационный метод решения системы (9), (10). Применим итерационные методы решения систем линейных уравнений, описанные в з 5 гл.
8, к системе (9), (10). В предыдущем пункте мы определили конечномерный симметрический оператор А в В.н. Мы знаем, что скорость сходимости итерационного процесса будет определяться числом обусловленности я = сопс(гЛ = ЛсаЛ, '. Неравенство (22) позволяет получить оценку для й. Еще один важный момент состоит в том, что вычисление вектора невязки при итерационном решении системы (9), (10) выполняется исключительно просто.
Так, если г' — вектор невязки на и-й итерации, то г сеточная функция на множестве узлов (Йь О дйа) Л Гш поскольку на множестве узлов Га решение фиксируется граничными условнямн. Если гь' --. значение повязки в узле ха, то 679 Э 1. 0 чиалаииам решении красами задач лиоо е = е" — ' т, .1г' ', и = 1, 2, (25) о ;е — е а ( ( ),е — е~т, и —;1 (26) где е -- решение системы (9), (10), ео -- вектор начальных данных. Напомним, что т = 2(Л1 -1- Лн) (27) Оценим число операций, необходимых для того, чтобы получить приближенное решение с точностью б. Для этого нужно сделать т итераций,. где о В процессе каждой итерации нужно сделать = йй операций, и поэтому общее число операций = ХЛн !п(1/б).
Но М = Уо! П/(ба... 6~), и, считая, что Лн ( С 2 6 " (так будет в случае областей частного вида, когда лп 6" =- 6 ), получим, что число операций = Уо! Йг(Я6 ' "!ой(1/б), (28) где 6.— средний шаг, 6 = 6 (б .— -- 1, 2, ..., !). Если воспользоваться итерационным процессом Ричардсона, т, е. формулами (25) при соответствующем выборе параметров т, либо оптимальным итерационным процессом второго порядка, определяемым формулами (8.5.32), мы получим намного более эффективный метод. В данном случае формула (8.5.32) приобретает вид Ье —. Л ~г +(2 ' б,— 1)пеа 1, и — 1,2,..., (29) 1 — т 1 — т, а — 1 где йе = е'~ 1 — е', т = Л1~Лн, и, = О, о., = (2-'-~~ — и, г ) и .=.
О, 1,... При выполнении вычислений по формуле (29) нам могут быть неизвестны отношение Л1,~Ли и Лм, и поэтому нужно уметь находить приемлемука верхнюю границу для них. Используя неравенство (8.5.33'), найдем, что для того, чтобы получить решение системы (9), (10) с точностью б (в евклидовой норме в К~'), нужно выполнить = Л'о! (ЫЯ6 ' ' !о8(1~б) (30) операций.
В случае простых итераций с фиксированным параметром оценка погрешности дается формулой (8.5.13'): 680 Глава Нб Некопгорые вопросы пивов>того региеиия краевых вабач Существуют еще более эффективные методы решения разностных уравнений (9), (10). Если область й является интервагюм (двумерным), то таким методом является метод Дугласа--Писмена — Рэкфорда. На совершенно иных идеях построен оригинальный метод Федоренко.
Хотя каждый из этих методов по-своему замечателен, мы не будем их излагать. За деталями отсылаем читателя к оригинальным работам (116, 133, 140) либо к известному учебнику !40), где дано довольно подробное ог>иоанне этих методов (см, так>ко предлагаемые ниже задачи). Число операций в упомянутых методах может быть снижено до величины = Лго! ПГ126 ' !од(1!б) !об(1Я.
(31) Считая, что б .= 6", и обозначая через погрепшость приближенного решения, мы получим для схемы второго порядка е = 6, и поэтому достаточное число операций будет >к ЛГО! йе(ге-Нг !082(1)в) (32) Отметим, что принципиально метод Федоренко позволяет избавиться от логарифмического множителя. Таким образом мы получаем оценку сверху для временной сложности алгоритма, о которой говорили выше, смыкающейся с оценкой снизу. Значит, для тех случаев, когда правая часть уравнения (1) задана таблицей интерполяционного типа, предлагаемый метод решения краевой задачи оптимален по числу операций. Злмцчлник.
Для решения разностных уравнений (9), (10) мы применяли общие итерационные методы и воспользовались только симметричностью матрицы системы и характером ее спектра. Важная особенность нашей задачи состоит в том7 что вектор невязки вычислялся с помощью локальных формул и для этого требовалось всего = 7."'7' операций на каждой итерации, где >ЛГ - - число внутренних узлов. Но эта особенность сохраняется и для некоторых других способов дискретизации эллиптических самосопряженных задач. Поэтому и при других способах дискретизации эти методы будут применяться столь же эффективно. В предыдущих рассуждениях мы полностью обошли вниманием вопрос о том, как поступать при наличии иррегулярных узлов.
Можно организовать итерационный метод решения и в этом случае, по нужно потребовать, чтобы выполнялись условия 6' > О6, О .=- 1, 2,, !), где 0 < О < 1 и д отделено от нуля. 3 а д ач н. 2. Пусть область й С' Я' является инте)>волам й = (х>, аг: О ~ (хд < а>, О ~ (хг <ы аг); положим 6> = а>>ЛГ>' (2 = 1, 2). Рассмотрим задачу на собственныо значения — (бГч +б7ь„)оо — ЛГою х" С йр, Ы(дйГ ГГ Го). :ио = О, х б Гь Зонумеруйге одним индексом узлы и запишите в матричном виде эту задачу Докажите, что собственные функции имеют вид Г 7Г67 Л . Г 7Г62 и": 6 -- оеЧ !>е =- в!и( 6777>1 юп( 6272), )' Й вЂ” ' (бы Йг), 7' — —. (ге, 7 г), 681 31.
О численном ресаении краеаыт задач а соответствующие собственные значения равны А, = юс(тг) -~- а11(тг), гс = 1, 2,, Яс — 1, гг = 1, 2, ..., Яг — 1, где 2в1п[хИгсс(2а )) 12 -1(й) = ' ' ) , д = 1, 2. =( ' ') 111 (1~", Ь') = ~ ивгыс ье.х а ды — символ Кронекера. Рассмотрите разлгпгные способы нумерации узлов н убедитесь, что структура матрицы сильно зависит от выбранного способа нумерации.
В последующих шести задачах область й. сетка и разностпый оператор будут такими же, как и в предыдущей зада ге. Пусть Х, — оператор, построенный в п. 5; через Е; (1' = 1, 2) обозна*шм конечномерный оператор, определенный с помощью локальных формул 1,,иь — -- — б„иго и С й ~дй, .2 ь причем, если л б дйь, то в выражении — дь иь слагаемые, отвечающие узлам 1 г, л" б дГь, принимаются равными нулю.
Таким образом, Š— -- Е1 1- 1.2. 3. Проверьте, что Е112 = Е211. Покажите, что уравнения метода расщепления, описанные в п. 1 3 5 гл. 8 применительно к решению системы (33) где и, 1 — векторы из В.н с компонентами и~, Х~, л~ с й 'с дй, соответственно могут быть записаны в виде -1- 11 2 в — ю" .1-11'2 =. — Еге — Еге + 1, т/2 -1-1 -1-112 т)2 = — Его — Еги +1, 12= 0, 1, (34) если положить о = 2)т. 4.
Пусть С(т) = — (Е1-~- — 1) (Ег — — 1). Покажите, что собственные векторы операторов 1 — (С(т)) 1, и Х совпадают, а собственные значения первого оператора определяются по формуле Л„(т) — —. (шг(гг) — 2т ) (агг(12) — йт ) (шг(гг) — 2т ) х х (~>г(тг)+2т ), 1'1 -1,'2,, %1 — 1, тг=1,2,...,Яг — 1. Указлнига Непосредственной проверкой убедитесь, что удовлетворяются уравнения и граничные условия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
