Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 48
Текст из файла (страница 48)
Чтобы избежать катастрофического влияния вычислпгильной погргзпнооги, применяют мешогу 1Ъуссп с амбаром слоеного злемеишо. Его отличие г юз Глава б. Численные методы алгебрь, 288 от описагшой выше схемы метода 1аугса состоит в слепующем. Пусть по ходу исключедия неизвестных получепа система уравнений т,+ ~гл,*ху —— а,* гл, 1=1,...,Й, л= +! Е л, ь айтз = а, м+л, г=льл с=821.....,ш. Ьч — — (а ли„ч,..., а,„м.ш) Т произведем вычисления по формулам (4), причем злемепты длл вычислим при л < й < т+ р. В результате будут получены р систем уравнений с треугольной матрицей, соответгтвулощих исходной задаче' 11х = слш сл = (л(г„,+ш..., А,чд, )т, Ч= 1,..., р. Решасьл зги системы каждую в отдельвости. Оказывается..по общее чи- сло арифметических действий при решении р систпьл уравнений 'лаким способом Ж вЂ” 2глз/2 + 2ршз.
Описанный выше прием иногда испавьзуетш дяв того, чтобы бп существенных дополнительных затрат получить сужденио о погрепшогтп рмпеипя, являюппйгл следствием погрешностей округления при вычислениях. Звдаклся вектрам к с компопеитлмп, имеющими по возможности тот же ипрядок и знак, что п компавегггы искомОго решевия; часта из-за отсутствия доствто шой илФармвглии берут х = (1,..., 1) .
Вычиглявглш век~ар с = Ах, и лйряду с па ходкой системой уравнений решаетгя система Ах = с. Пусть х' и к' — реально получаомые решения атих систем. Оулкдепяе о погрешности х' — х исКомого ршпепия можно получить, основываясь ва гвпот|пе: относительные пагрешиости при решении методом исюаачепия систем с адней и той же матрицей я различными правыми частями, которыми являкп ся сс аплетсгвеппо величины ((х — х'(((((х'(( и ((х — х'((Л()х'((, отличаются ие в очень бгвп,шое число рвз.
Другой прием для получения суждения о реальной велпчиие погрелппосги, возникающей зв счет округлеипй прп вычислениях, ссхтоит в ввмамиаа масплпа- Найдеьг 1 такое, что ~а ( = пшх)ал, л;( и переобозиачиьг хл л = х~ и л л- 3 х~ = хл„..гб Далее пРопзвеДем искллачеглие иеизвестпой тл л из всем УРавпеиий, начиная с (1. + 2)-го. Такое переобозпачеиие приводит к изменению порядка исключения пеизвестлых и во многих случаях сущеогвеллпо умепьшвет чуисгвнтельяость решении к иогрешиостям округления при пычиглениях. Часто требуетсл решить несколько систем ураввеиий Ах = Ьл, Ч = 1,..., р, с одной и той же матргщей А. Удобно поступись следукяцим образом: введя обазвачеипя гбй 11.
Методы последовательною исключения неизвестных бов, меняющем картину накопления вычислительной оогрешвости. Наряду с исходной системой тем гке метолом решается систеиа (оА)х' = !3Ь, где о и !3 — числа. При о и р3. ие являющими целыми степенями двойки, сравнение векторов х и об 'х' дает представление о ы!личиве вычислительной погрешности. Напри- мер, можно взять о = ъ'2, 33 = Л. (б) А =- о'338, где 8 — правая треугольная матрица, Я* сопряженная с ней, т.е. Я= О эээ причем все эп > О, 33 — диагональная матрица с элементами А,„, равными +1 или — 1. Матричное равенство (6) образует систему уравнений о„3 = — эпл3,А!! Р ..
+ ей!э,убь пРи ! < !. Аналогичные ураввения прв ! > 3 отброшены, так как уравнения, со- ответствующие парам (ь, !) и (г, !), эквивалентны. Отсюда получаем ре- «уррентные формулы для определении элемелтов Ак и э,эч *-! — ! .= э.(.-Кь„!г»)...;.= л=! ь.=! при г< 3. Матрица Я является правой треугольной, и, эакиы образок!, после получения представления (6) решевие исходной системы также сводится к последовательному решению двух систем с треугольными матрицами. За!!стим, что в случае А > О все А3! = 1 и А = 8*8.
Изучение многих задач принодит к необходимости решения систем линейных уравнений с симметричной положительно онределенной матрицей. Такие системы возникают, например, при решении дифференциальных уравнений методом конечных элементов или же конечно-раэвостными методами. В этих случаях матрица системы имеет также и .ленточную сгруктуру. Для рюпения таких систем, а также систем уравнений более общего вцца с эрмитовой не обязательно положительно определенной матрицей применяется лешо!3 коодрапшоэо к!увы (ыешод Холецкоео). Матрица А прелстллляетгн в виде Глава 6. Чискенные лгепжы алгебры 260 Зада га 3. Оценить число арифметических операций и загрузку памяти ЭВМ (пря условии ам.
— — а, объем памяти, требуемый для запоминания матрицы А, уменьшается) при решении системы с вещественной положи. тельно определеннной матрицей А метгшам квадратного корня. Многие пакеты прикладных программ для решения краевых задж математической физики мьтсдаы конечных элементов организованы по следующей схеме.
После формирования матрицы системы А путем перестановки строк и столбцов (одновременно переставляются г-я и утя строки и г-й и у-й столбцы) система преобразуется к виду с наилюньшей гпнриной ленты. Далее применявтся метод квадратного карня. При этом с целью уменьшения объема вычислений при решении системы Ах = Ъ с другими правыми частями матрица Л запоминастск. Замечание. г1асто этот метод уступает ио эффективности итерационным методам. Задача 4. Оценить число арифметических операций и объем требуемой памяти метода квадратного корня в случае матриц ленточной ьтруктурм. Если есть подозрение, что реально полученное решение хг сильно искажено вычислиэтшьной погрешностью, то можно поступить следующим образом.
Определим вектор Ъ| = Ь вЂ” Ахг. Погрешность г' = х — х1 удо. илеэноряег системе уравнений Аг = Ах — Ах' = Ъ'. (7] Решая эту гистелгу в условиях реальных округлений, получаем приближение г(11 к гг. Полагаем хт = х1+г1'1. Если тошосп нового приближения представляется неудовлетворительной, то повторяем эту операцию. При решении системы (7) нэд компонентами правой части щюизводятся те же линейные операции, что и над компонентами правой чисти при ре1гении системы (1).
Поэтому при вычислениях на ЭВМ с плавающей запятой естественно ожидать, что относительные погрешности решений этих систем будут одного по1жэна Поскольку погрешности округлений обычна ьивлы, то ))Ь )) (()(Ь)); тогда ))г () « )(х )(, и, как правило, решение (7) опрцлелитсл с существегню меньнгей абсолютной погрешностью, чгм решение системы (1). Таким обржюм, применение описаннгйо приема приводит к повьппению точности приближенного решения.
Особенно удобно применять этсо прием, когда по ходу вычисиелий в памяти ЭВМ сохраняютси матрицы В н Р. Тогда для каждого уточнения требушся найти вектор Ьь = Ь вЂ” Ах" и решить две системы с треугольными матрицами. Это потребует всего 77, 4глэ а1гифметических операций, что опошлит малую долю от числа операций 7'го 2гл /2, 3 гребуюшнхся для представления матрицы А в виде А = ВР. Идея описанного приема последовательного уточнения приближений к решению чести реализуется в такой форме. Пусть матрипа В близка е каком-то 2В1 11.
Мепды последовательного исключения веяэвестнььх смыгле к матрице А, но решение системы Вх = с требует существенно меньшего сбьема вычислений по сравнению с решением сися.;мы Ах = Ь. Решение системы Вх = Ъ принимаем в качеопге первого приближении х к решению. г Разность х — хг удовлетворяет системе уравнений А(х — х') = Ь вЂ” Ах'. Вмесхо решения этой системы исходим решелие системы Вг' = Ь вЂ” Ах' н полагзем хг = хг .1- г г.
'Реким обра.юм, кахщое првближевие находится яз прелмгугцего по формуле х'ыг = х" +В '(Ь вЂ” Ах") = (Š— В 'и)» +В 'Ь. Если матрицы А и В достаточно близки, то матрица Š— В ' А ивпп мэлую норму в гшсой нтеравяонный процесс быстро глодитгп (см. также г 10). Значитегпно более редкой, чем задача решения системы уравнений, является зэ;лача обращения матриц.
Ддя обратной матрицы Х = А имеем равенство АХ = ВРХ = Е. '12ким образом, двя нахождения матрицы Х достаточно последовательгго репгить две матричные системы ВУ = Е, ВХ = У. Нетрудно подсчитать, что при нахоггдении на таком пути матрицы А г общий объеы вычислений составит )хг 2гпх арифметических операций. В случае необходимости угтлгневвя приближения к обратной матрице могут производиться при помощи итерационного щюцесса Хь Хь г(2Е-АХ1 г).
Для последования сходимссти итерационного процесса рассмотрим матрицы Сг = Š— АХг. Имеем равенство Сь Е АХг Е АХь г(2Е АХь г) (Е АХь г)г Сгг Отсюда полу гаем цепочку равенстн гь С =Сь-г=бьы-г= ''=Со. Поекольку А г — Хг = А г(Š— АХь) = А гСг = А гСог, то имеем оценку ))А ' — Хг)) < ()А '().))Се() 2аким обрезом, при достаточно хорошем начальном приближении, т.е. если ~)Š— АХс)(< 1, этот итерационный процесс сходится со скоростью более быстрой, чем геометрическая прог1люсия. Глава б. 1всленные машам ал~'Жрь. 262 В 2. Метод отражений В настоящее время разработано так много точных методов численногю решения систем линейных алгебраических уравнений, что даже щюсгсе перечисление их затруднитсш,но. Большинство этих методов, как и мета исключения Гаусса, основано на переходе от заданной системы Ах = Б „ новой систвме САх = СЪ такой, что система Вх = су, где В=-.
СА и г1— СЪ, решается проще, чем исходная. Прп выборе подхадящен матрицы С нужно учитывать па крайней мере следующие два фактора. Во-первых, ее вычисление не должно быть чересчур сложным и трудоемким. Во вторых, умножение на матрицу С не должно в какоммо смысле портить матрицу А (мера обусловленности матрицы пе должна мснятыя сильно (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
