Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 39
Текст из файла (страница 39)
Заметим, что рассмотренная нами в гл. У! разиостиая аадача Дкрихле лля уравнения Пуассона на прямоугольной равномерной по каждому направлению сотке, введенной з прямоугольник, может быть записана в виде (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Ы == Ьг(а,+, + Ь;+, + УЫ ) ~ и складывая полученшге уравнения с (26), найдем — аГЫУ + (а(гэ ' ЬОΠ— ' г((Ы) у — Ь(юу „.= 1Ы), — а у; , (а, + ,.
+ ; ) у, — ; у;.„з = , где агы = аг(ыа;, ь1О = ()ггтэь,„м ам = п)ыаг „+ У;+ ())т)а, 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. Самарский Л. Л.. !1пколаев 1'. С. Методы рсшсапп сеточных уравнений.—. У!х Наука. 1973. 13. С а и а р с к и й А, Л..! ! о и о в !О, Н. !>взнос>ные методы га.п>вой динамики.— Мл !!в> ка. !980. 14. Т и хо и о в Л. ! !., С а м а р с к н н А. А. Уравнении математической физик>с — й!.: Наука, !972. 15, Ф ад де е и Д, К., Ф а дд е е на В.
Н. Вычис >ишльпыс мотоды лппсйпой алг> бры.— Мх Физматгиз, 1963. 10. Ни е и к о И, Н Метод дробных шагов реш> нип .ппогоиерных задач математической физики,— Новосибирск: Паука, 1907. ПРЕДМЕТНЫЙ УНАЗАТЕЛЬ Алгоритм неустойчивый 13 — условно устойчивый 13 — экономичный Н Л1шраксвлгацпя разпостная (на сетке) 138 — суммарная 254 Весовые множители?О Вычислитольпая неустойчивость 115 Уйесткис системы уравнений 192 Задача Дирихлс 211 — корректная 14 — Кеши 32 -- краевая 32 — нскаррсктная 15 — о собственных зпачспиях 42 Нптерполяпта 61 Интерполяцианный полинам 62 — -- Лагранжа 64 — — Ньютона 64 Интерполяция зрмитона 65 Птсрационные методы 90 Итерационный метод двухшаговый (трехслайный) 97 — — неявный 97 — одпошагавьп( (двухслойный) 97 -- — явный 97 Квадратурвая формула 70 — -- Гаусса 82 — — 1(атега 74 — — прямоугольника 71 — — Инмпсапа 72 — — трапсцип 71 — — Чебышева К) Каэффацпепты 71агран|ка 62 Краевые условия 3,") — — 1-га рода 3:1 — — 2-го рад» 33 Краевые условия 3-го рода 33 Кубичсская сплайп-интерполяция 65 Линейно независимые векторы 39 — — решения 27 Линейное пространство 38 — — дсйствительное 38 — — камплскспое 38 Мажараптная функция (мажорапта) 55 Матрица всрхпяя треугозьная 87 — диагональная 86 — ленточная 88 — нижняя треугольная 86 — разреженпан 87 Мара обусловленности 89 Метод Адамса — Штйрмера 191 — баланса (ннтегро-иитерполяцпоппый) 167 -- 1)убнава — Галеркина 173 — вариационно-разностный 171 — вариапионпого типа 126 — верхней релаксации 101 — дихотомии 130 — Зейдслн 99 - — касатеш,ных 133 - - конечных элементов 173 — липеарнэацпи 133 — мпкимальпыт повязок 127 †- Ньютона 133 — исрсчепаых направлений 251 Макар» (нослсдоватсльных араб:аакспнй) 175 паш ргпгнна тргугальный 120 — аон)эавок 128 прогонки 31 -- — встречной 37 — — лавой 37 — — правой 37 ПРГДЫПТ11ЫЙ УКАЛАТКЛЬ Метод простой итерации 98 — прямой 89 — прямых 234 — разделенпл псремспаых 222 — Рптца 172 — Ричардсона 1!5 — Рунге 82, 165, 178 — !'унте — Кутта 174 — секущих 136 — скорейшего спуска 128 — сопряженных градиентов 129 — стациоиаряыи втерацпаниый 102 — сумматорпых тождеств 17! — Штермсра 189 — энергетических перавспств 144, 207 5!пнихгазг1ру~ощггй квадратичный функционал 171 Наплучшсо средвеивадратич- пое приближенно 68 Невязка для разпостпой схемы иа решешш 116 Норма агпратора 40 Обратпае пптерпа;пцювапко 67 Одиородваи разпасгпал схема 150 Оператор одиапчпый Я вЂ” типейпыи 40 — неотрицательный Ы вЂ” обратный 40 — ограниченный 40 — паложитальяый 41 — разрешанпцпй 11! — самосапрл1кеиный 41 — сопряженный 4! — факторизовапиый 129, 252 — экономичный (зкапомичность оператора) 119 Операторное ураввение первого рода 88 Операторы перестаповочпые 41 Ошибка округления 10 Погрешность аппроксимации для краевого условия 146 — — в точке, ж-й порядок 139 — — для уравпскпл 146 — — па решсппп !47 — — па сетка 140, 185 — — оператора !39 — квадратурной формулы 70 — метода 10 Погрешность неустранимая 10 Налипал обобщепиый 68 — Чебышева !12, !14 Припцпп максимума 55 Нрострапстно евклидова (уиптарпос) 39 — пармпроваппае 39 — сеточных функций 46 — энергетическое 45 Процесс Эйткспа 81 Равепство Парсеваля — Стеклова 69 Равномерное приближение 69 Раздслеипые разности 1-го порядка 64 — — 2-го порядка 64 !'азмерность .типсйного прострапстг~а 39 Разпостиая производная 139 — — левая 139 — — правая Р39 — — цсптральпан 139 — схема 14! -- — Адат!се 186 — — аддптпвпая 256 — безусловно устойчивая (прпьпр) !82 — — дзухслойпая 181, 197 — —,1[угласа — !'екфарда 254 — — неазиустойчивая 14а — — консервативная 152 — — корректная 142 — — Бранка — Николсона 236 — — крест 212 — — локально-одномерная 258 — — мпогошаговая 184 — — ш-го порядка точпасти 146 — — т-шаговая (аг ж 1) 185 — — неустойчивая 142 — — пеленая 198 — — одношаговая 181 — — Писмспа — Рскфарда 25! — — предш1тор — корректор (счет — пересчет) 180 — — расщеплепия 258 — — р-устойчивая 201 — — Рунге — Кутта 179 — — с весами 198 — — с апережеяием 198 — — симметричяая 198 — — условно устойчивая схема (прпмер) 182 — — устойчивая 142, 143 гтгедьгктнглй унлзлтгль Ревностная схема чебышевская итерационная 112 — — чисто неявная 193 — — Эйлера 141, 176 — — экономнчкан 250 — — явная 198Р Разпостпое уравнение линейное с постоянными ноэффицнентамн 26 — — т-го порндка (ю ) 1) 26 — — однородное 28 Раепостные неравенства 27 — формулы Грина 50 Сетка квадратная 212 — неравномерная 16 — равпомгрнал 16 Сеточная функция 16, 138 Сплайн порядка и 66 Среднеквадратичное уклон кке 68 Сходкмость разпостной схеьпм (со скоростью 0(й('") 146 — о квадратичной скоростью 134 Уравнение тсплопроводностк 232 Устойчквость разпостной схб мы с весами 182 Формула Тейлора 74 формулы бегущего счета 123 Чнслсппое ннтегрировално 70 ')пело обусловленности 80 Шаблон 139 — кзадратурной формулы 71 СПИСОК ОБОЗНАЧЕНИЙ ых = (/; 1 = О, 1, ..., /т) — сетка с целочисленными узлами ыв = (х/ =- 1/в, а = 1/и', О в 1 ( л/) — равномерная сетка с, шагом /в па отрезне (О, Ц б — шаг остии овв У; = у(х;) = у(1) — значение сеточной функции в 1-м узле сетки евв — лераввомернаи сетка /ы = х; — х, в — шаг неравномерной сотни /ев.' = е (х!, хз 1 — значение сеточной двумерной фуикцип в в/з ' /г /т/ узле (1, Д /х) — значение сеточной функции в узле (1, /) лв /л па л-м временном слое е,"„ ' = з — значение сеточной двумерной фувкцпи в узле (/,/') на (з + 1)-и временном слое /Гу = у вв — у; — правая разность в 1-м узле т у/ = у; — у/ в — левал разность в 1-м узле 1 бу, = й (ту, + Лу/) — центральная разность в 1-м узле Леу/вв = й(ру/ /] = вв(ду/) — разность второго порядка у,/ = (у,,в — у/)/Й вЂ” правая разяостиая производная в узле х; У-, .=- (У; — у/ в)!л — левая разностнал пропзводяал в узле .т; ух = (У, т — Ув г)/(2Ь) †центральн разиостная пропзводхд ная з узле х/ у- .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
