А.А. Самарский - Введение в численные методы (1113832), страница 39
Текст из файла (страница 39)
(12) Итак, формулы (4), (7) — (12) полностью определяют искомые коэффициенты. Сравнивая (10) л (12) при условиях (4), (7), (8), ДОПОЛНЕНИЕ получим, что р, — г), = $» = а, для г ) О. Таким образом, формулы (3), (6) нршп»мают вид уьы = а,у» — а,,у,— Ро 1) О, (13) У»-г = а»-»Ул-г — ал-,-~у. — д» -ь !»= 8', (!4) где Р' = СР»-» Р'-г+Р, г) 2, Рг = О, р» =)'ь (!3) д»=СУ,,— у, г+Гл-о г)2, д»=0, Ч,=Гл-ь [16) а»=Са㻠— аг-г, !)2, а»=1, а»=С. (17) Найдем теперь у~ п ул ь Для этого положим в (13) ! = А., а в (14) ! = )» + 2.
Учитывая, что д! = 28 + 1, получим У»+» = а»У» а»-»Уг — Р» У»г» = а» ~уа г — и» гул — Ч» Вычитая нз второго равенства первое, получим уравнение оюшсительно у» и уь — »: а у, г — а»уг + а» ~уг — а»-гул = Ч»-» — Рь (18) По. учим еще одно уравненне для у» п ул-ь полагая ! = ь. — 1 в (13) и ! У+1 в (14) и вычитая из первого равенства второе, — а»У»'-» + а»-гу» — а»-~у»+ а»-»Ул = Р»-1 — Ч». (18) Учитывая, что у» = у» = О, сложпм и вычтем (!8) п (19). Получим энвнвалентную систему (а»-» гг») (ух-~ + У») = Ч»-» — Р» + Р» -1 Чм (20) (а»- + а») (у. — — Р~) = у -! — Р» — Р»- + у», решая которую, найдем искомые значения у, н у; Уг = (аа г а») (а» (Уа г Р») + аа.
г (Ра г — Я»)) (21) Ум — г = (а»-! а») (а»-г(Ч»-г Р») + а» (Р»-! Ча)) Таким образом. алгоритм решении задачи (!) состоит е вычислении по формулам (15) — (17) ьоэффнцпектов р» ь Р», у» у!ы а» ь аы по формулам (21) — значений уь у».-~ и иенззестпыс уь ! == 2. 3, ..., У, г)о формуле (2). а чля» = Д вЂ” 2, )У--3..., ..., 8 + ! по формуле (3) нрп заданных уг. у; п зычпслешгых !гь ул-ь Описанный алгоритм получил название .»арлоалгорлтла, Легко подсчитать, что для его реализация требуется прлмерно 8»т' операцкй. Можяо показать, что если С чь 2 сов глл/У, эь — целоо число, то задача (!) разрешима прп любои правой части и а;, чь ~аз.
Следовательно, в этом случае формулы (21) не содержат деления па нуль. Оппсапнып выше марш-а;порптм можно испольэовать и в случае, когда С вЂ” квадратная матрица, Р', — заданные, а уг — искомые векторы. Заметим, что рассмотренная нами в гл. У! разиостиая аадача Дкрихле лля уравнения Пуассона на прямоугольной равномерной по каждому направлению сотке, введенной з прямоугольник, может быть записана в виде (1). В этом случае компонентами вектора являются зпаченая искомой сеточной функции, соответствующие 1-8 строке сетки, а матрица С вЂ” трехднагональная и ее порядок равен числу внутренних строк сетки, До ПОЧ/ти//ИИ )<1 ь<и в<с<,е л Сь(') =- (, )/ е )/«-, (' )/г . )'«т 2)« --1 Пспользуя явное выражение /Ьая иы и ) 11, и учип<вая, что и<— по<пиши с сдииичиыь< козффпииеитом ири старшей гт« «ли, пои<- но получить с/и<Ну<ошно разложения: а — с< (2/ — 1) и 1< 4-/ 2/ С), /=1 2/л / < (22) Испо<и,зуя (22) и (2й), построим с.<глу<ощпй алгорптз< Ллп нагоны девин у, и у< рь '/А -< рь < и </ь* оо </л ! /'е рь-< Г<//< С вЂ” 2 с<и //Х~е< —.- г (2/ — 1) и 2й+ 1 2/и у, =.
0,5(гь — и/,), дч, = [1,5(гь+ н<ь), (23) так как ка;иная из систем (23) имеет третииагопальную матрицу (число таких систем 2/<] и может быть решена а<столом прогонки с затратой 0(1/) операций, то Иля нахождения у, п ил, потребуется 0(Н/й/) арифметических операций, Итак. для решения системы (1) с трехдиагональной иатрнцей постро<н метод с числом арифметических операций, проиорциональиыи числу неизвестных, Обратии внимание на то, что построенный мер<и-а/мор<пи может быть численно неустойчивым.
Действительно, есчн число С удоалетаоряет условшо )С) ) 2. то для алгоритм» харантереи зкспоиснциа.и,ный по Н' рост погрешяости, поскольку среди корней характеристического уравнении Сз — Сд + 1 = 0 имеетгя адин. ио модулю больше единицы, Такого же типа неустойчивость Пусть 1/ — иорлиок матрицы С. Тогда вснторы и<, Е< имеют размер М и для вычисления р<-ь </ь-<, р<, </ь по формулам (15), (16) иотргбуетсл 0(НСУ) операций. Очевидно, что такое же количество операций потребуется и для нахождения векторов у<, 2 <н = /~(/у — 2, по формулаи (2), (5). 1'ассмотрим теперь вопрос о вычислении у, и уз-<. 11з формулы (17) следует, что аь есть полипом степени /< от С, причем, если С вЂ” число, то иь — алгебраический полипом, а сслп С вЂ” матрица, то ил — матричный полипом.
Для полинома, удовлетворявшего р<куррептному соотношению (17), еесь явное представ/<ение< иь = 0<<(С/2), где Сх(х] — поливом Чебьипева второго рода степени /« ' И ч (Л 5 11 агсссе г ДОПОЛНГННН вЂ” а;у; 1+с;у; — ь,уж~ =1ь 1: 1(ж — 1, (21) У,=О,уь =О, где с; = а; + Ь| + г(о аг ) О, Ьг ) О, а'; ) О, У = 2". Иден метода редукцян состоит в носледователыюм исключении яз системы (21) неизвестных сначала с нечетными номерами, затем с номерамя, кратнымя 2.
н т, д. Вынишеы трн идущие подряд уравнения системы (24) с нокерами 1 — 1, О 1+ 1, где г — четное число: — а; ту; з г(аь х+ь; т+аг т)у, г — ь, гу;=-11 — а у;, + (а1 + Ьг + г(;) у; — Ь,у,.„т =- 11 ту; + (а+~ г ьг+т + ')ы т) у1+т ьгчгуььз = 1гьх (25) (25) (27) Умножая уравнение (25) наи) ~.=а,(а,,+Ь; г+Уг т) г, уравеение (27) па (31Ы == Ьг(а,+, + Ь;+, + УЫ ) ~ и складывая полученшге уравнения с (25), найдем — аГЫУ + (а(гэ ' ЬОΠ— ' г((Ы) у — Ь(юу „.= 1Ы), — а у; , (а, + ,. + ; ) у, — ; у;.„з = , где агы = аг(ыа;, ь1О = ()ггтэь,„м ам = п)ыаг „+ 8;+ ())т)а, 7( = и; 1; т+ 1г+ (); 1сеы Если неизвестные с четными номерамн будут найдены (онп удовлетворяют системе (28)), то остальные неизвестные определится по фориуле а,У; г, Ьгу;+г г у,.
= , , 1 = 1, 3, 5...,, 7У вЂ” 1. ; г Оппсанныи процесс исключения неизвестных может быть, очевидно, применен к системе (28), нз которой на втором шаге будут исключены неизвестныв с ноиерамн, кратныии 2, но не кратными 4, В результате Иго шага процесса нсключейпя получим имеет место и в том случае, когда матрица С имеет собственныв значения, прееосходящне по модулю 2. Для таких задач з настоящее время построен аариант марш-алгоритма, устойчивый в том смысле, что погрсптпость растет по степенному закону прп росте Ю, 2.
Метод редукции. В ряде случаев прн решении систем линейных алгебраических уравнений с трехдиагональной матрицей большое значение имеет точность полученного решении. Аггалнз формул метода прогонки, который применяется для решения таких систем, йоказызает, что источником погрешности могут служить формульг для вычисления прогоночных коэффициентов, Зтн формулы содержат операцию деления на разность близких по значению величгш. Ниже будет рассмотрен метод редукции реп|ения указанных систем, свободный от этого недостатка.
11так, пусть требуется найти решение трехточечной разностной задачи дон дннннп систему (,> „У <О ( (<(> ) 3<0)у Ь(ну ..у — 2) у — О, уя -О, о (29) где а(0=>.и<~>а«-), Ь'О=Р( Ь«- а, =- и, а ( <. > ' > <(е(-\' ,0> „и)„«.<> и у«-Ы ( й<ня«-» ,<-> <.<.⫠—.' „> <» «ы, !«-» ()(<) (« — > =ы...) <ч < -г,, (-ы (г> ЫО «>) (ь«т) ~к()т) <-2< > <-3( > <-3( >> б<О=Ь((- >(а<(-т) +Ь('-" +й«-'> 1 ', 1 <х' > < ььт'-! ' Н-т) — г> ) = 2', 2 2), 3 2', ..., Л' — 2<, ! > !.
(30) а(е) „ (,(а) Ь у(е) , <( < ~ < Здесь испотьзованы обозначения У<е) Процесс исключен оп закончится па (я — 1)-м шаге, когда система (29) будет состоять пз одного уравнении относительно неизвестного уи>,=- у,и ,. Пз этого уравнении найдем г(а >) а<и >) < ((и — г), (ея <: а,я -Г уе ~ 'еч-< '(К .>та < а<а <) Ь<я — '> ',а 1 '.я-1-> .,я 1 у =. ут=.О. (3!) Остальные неизвестные спрэд~ »я<отел ио формулам У(У~ -',- а<')у ( + ь<'>у у, = < >,, ) .= 2, 3 2, 5 2, ..., Д< — 2, а, +Ь, +а< (32) где ! = л — 2, я — 3, ..., О, у„= у, = О.
Заметим, что формула (32) вклю шет в себя формулу (3!) при ( = и — !. 1!так, и методе редукции иа прнмом ходе по формулам (30) для ! -=- 1. 2, „л — ! вычисляются а< ), Ь< ), <(< ), /« >, а на обратном ходе ио формуле (32] для ! = л — 1, и — 2, ..., 0 находится искомоо решспи<, Отметим, что метод не требует дополнительной памяти. так как везичияы а, ), Ь< ), Н<, )< могут а< >) Ь< быть размещены соответственно иа месте а.
( х~ <,< т~ <((< >), /(~ '). Для реализации метода требуется !2гт' сложений, < 3Л' умножений и ЗУ делений. ЛИТЕРАТУРА 1. Б а х в а л о в Н. С. Численные методы.— Гйх Наука. 1975. 2. Б е р е з пи И. С.. еБ и д по в Н. П. Методы вычислений.— Мл Наука, !966, ч. 1; Фпчматгпз, 1962, ч. 2.
3. Вое.води н В. В Числеииыс методы алгебры; теорип о алга- рифмы.— Ых Наука, 1966. й>. Годунов С. К., Ри 6е н ь и и й В. С, Разиостиые схемы.— Ых Наука, 1977. 5. Кап и ть и к Н. Н. Часлсшгые методы.— Ых Наука. 1978. б. Чишко И И., Макаров В. 7!., Скоробогатько А. А. Методы вы шсленпи.— Кш ш Высшая школа. 1977, 7. М а р ч у к Г. И. У! столы вычислительной математики. — 3!х Наука. !980. 8 Н и кол >. с к п й С, 31, Квадратурами формулы.— Мх Паука, !97!!.
9. С а м а р с к и й Л. Л. Г>ч>рпн давностных гхс>ь-- Мх Наука, 1977. 10. Самарский Л. Л.. Ливре> в В. Б. Ра,шостпыс методы длп зпшштичсгкпх урапиеппи.— Мх Наука. !976. 11. С а марса и н Л. Л.. Гул и и Л, В. Устои швость разиосгиых стем,— Мх Наука. !97:>. 12. Самарский Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
