Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 49
Текст из файла (страница 49)
у 11) ). Зтнм условиям в определенной сзтнени удовлетворяет описываемый вилле метод ашрааме~глгх Среди методов, требующих для сваей реализации числа оперецвй )У ггпз/3, втаг метод в настоящее время рвссмз. триваагся как один из наиболее устойчивых к вычислитгльной погрешности. Рассмотрим случай вещественной лштрицы А. Если лг — некоторый вектор-сттшбец единичной длины, (лг, и) = 1, то матрипу (7 — Е гвгму' называют магпргщей аглраакжиай Под тгтг~ здесь понимаетсв матрица, являющаяся произведением вектора-столбца тч на вектор-строку чгг, т.е. «чч~ = (ш,г), тле шб = 1и;ш,. Из опРеДеленин слеДУеб чта ипчт — симметричнаи матрица. Непосредственной проверкой убеждаемся, что П =- ат я (гьг = (е — гжлт~)(е — 2иит)т = е — 2ггвт — 2ввгл-4иитввт = е; здесь мы воспользовались тем, чта ттттв =- (лт, и ) = 1.
Таким образом, матрица (à — симметричная и ортагоналыпш. Напомним один факт из алпбры. Пусть В и В- две матрицы порядка вг, В— инагочлен ат 1/, В = Рг(В). Тогда люжно неРеУпоРЯдачвть их гсбствеиные значения так, чта Лг~ = Р~(Л ) при ) = 1,..., ас Поскольку (г симметрична и У~ = Уа'г =- Е, а все собственные числа Е равны 1, то все собственные числа лгатрицы У удовлетворяют условию Лзп — — 1, т.е. Равны или +1 или — 1. Собственному значению — 1 отвечает собственный вектор ис В самом деле, Вт = и — гипвтлв = вг — гг» = — и.
(г) 12М д р й 266 Все векторы, орзоюнальные вектору лч, являются собственными. Им озответствует собстпенное значение, равное +1. Дейстнительно, пусть (ч, тч) = О. Тогда имеем Пч =ч — гчгчгтч =- ч — 2н(чг, ч) = ъ. Предсгавим произвольный вектор у в виде у = в -~- ч, лце я = улч, (ч, лч) = О. Для этого атедунг взять в качестве в проекцию вектора у вв векюр ж, т.е. я = (у, н)лч, в ч =- у — (у, лч)лч. Вследствие (2) и (2) имеем Пу =. — я+ ч.
Таким образом, (гу есть зеркальное отражешю в~ктора у оцюсительно гнперплосколни, ортогональной вектору н. Испгшьзуя геометрические свойсзва матригвя агражеиий, нетрудно решить следуюгцую задачу: подобрать вектор ьт в матрице отражений так, чтаблл заданный вектор у уе О имел в результате преобразовылив Пу матрицей отражения П =  — 2нлчз направление заданною епиннчного вектора е. '1Ък как à — ортогональная лгатрлгпа, а при артогональпых преобразованиях длины векторов сохраняются, то ллы должны имать (уу = ае или (Гу = -ае,, где а = ьг(у, у).
Платону направление, перпендикулярное плоскости отражения, будет опрадевяться лаба вокторам у — ае, либо вектором у+не (см. рис. 6.2.1). Таким образом, век~оры нлг = яр, '(уае) или чгв = лрз (у + ае), где рл У 'ь:йЗ:ах, = Лгтйутлл будут искомыми. Ясвгп что данный про- м, цесс всегда сюуществим. Если векторы у н е коллинсаряы, а в этом случае либо рь лиГю рг будет равно нулю, то ника- -не ких отражений девать пг надо. Рис. 6.2.1 Матрипьл отражения нашли ппгрокоо применение при численном решении различных задач лвнейпай ало бры (в частности, в рассматриваемой вами аьпюле приведения матрицы системы уравнений к треугольному виду). У(емма. Лртюпольппл пепдрпппал лаплрпца мазкюп бить представлена е епде пропэеедеппл аршоэопипьппй и еервпей шреугальний магприц. 4апазащельстао. Пусть дана квадратная матрипа порядка яь Будем приварить ее к правой треуголыюй матрице путем последовательного Умножения слева на ортагональные матрицы.
На первом шаге припедения рассмотрим в качестве векюра у из предыдущего рассуждения верный столбец матрицы А: уг=(аы, °,а л) т Ъпи ам = азг = . ° ° = а г = О, то переходим к следующему шагу, полоцки А1л1 = А, Гг = Е и введя обозначения а(г) = а, . В противном случае О Глава б. Чны1енные методы алгебры умножаем матрицу А слева на лгатрицу отражения ()1 = Š— 2чггттт 1 где чг) подбирается так, чтобы вектор Г()уг был коллннеарен вектору е, = (1, О,..., О)».
Здесь и далее Ь' — единична» матрипа размерности 1) На этом первый шаг закончен, и на следующем шаге будем ра1хма (1) тривать магрнпу А(1) с элементамн а;, которая либо равна А, есви имеет мы."го первый случай, либо А1 = ())А, если именг место второй (1) ' случай. Пусть мы уже осуществили 1 — 1 > О шов и прн1пли к магрице АО 1) (1 — 1) О -1) с элементами о, такими, что а) =О при 1 > у, 1 = 1, 2,...,1 — 1 1 о' пространство В 1„.1 векшров размерности пг — (+1 рассмотрим нектор (1-1) (1 — 1) (1-0 т у)=(а,,а,,...,а ) Если а, = а. = ° . = О, то переходим к следующему пшгу, полагая А(О = АО 1), (11 =.
Е. В противном случае строим матрицу отражения Р) = Ь' )т) — 2и)и)1 (размеры ьютрицы Р) и вектора н) равны гл — 1+ 1], переводящую вектор у) в нектор, коллинеарный е) = (1, О,..., 0) б Л )т1, и пеРехоДим к матРиЦе А(') = П)А(' '); ЗДЕСЬ (11 = „г ( . ЯСНО, ЧтО ПРОЦЕСС ВСЕГДа ОСУЩГСтнны, И ПОСЛЕ ('Е), О ') 0 г') ) ' (т — 1)-го шага мы приходим к матрице А( "') = Пег 1(у,„з... ГГ1А, имеющей правую треугольную форму. Есвн обозначить ()„„1(( 1...
Пг = П, то из последнего равенства ыадуец что А = Пт А("' '), где Г(1 — ортогональная, а А( ' ') — правая треупснная матрицы. Лемма доказана. Вернемся к решению системы Ах = (ь С помощью указанных преобразований отражения последоват1шьно приводим ее к эквивалентному виду А( ')х = 0Ъ, где А( ' 1) — правая треугольная матрица. Если все диагональные элементы А( 1) отличны от нуля, то последовательно находим х,..., х). Если же хотя бы один из диаггжальных элементов равен нулю, то последняя система вырождена и в силу эквиввлелгтнооги вырождена и исходная система. Задача 1. Получить асимптотику числа операций метода отражений при П1 -+ ОО. 265 Э 3.
Меток простой итерации рассмотрим случай системы уравнений Ах = Ъ с комплексными А и Ь. Пусть А = А1-~-1Аэ, Ъ= Ь1+1Ьм х= хс+1хя. Исходная система уравнений равноснвьна систел~е (4) с веществевными С и сй Поэтому выешо непосредственного решения исходной закати можно перейти к рошели~о задачи (4) и применить дл» решения последней метод Отражений. Однако возможен н другой путь — непосредпсвенаое применение метода отражений к исходной системе Ах = Ь. Здесь матрица отражения У = Я вЂ” 2тттт*, ж* =- (юм..., шь) будет унитарной с собственными значениями вида Лп = с'"'. (с1ерпз и обюзпачено колшлексное число, сопряженное с «.) Задача 2. Перенести метод огражений на случай комплексных матриц.
Зццача 3. Илледовать метод отражений в случае есо применения для реплния систем уравненнй с ленточной матрицей. 3 3. Метод простой итерации Простешпим итерациошюым методом решения систем лннейньсс уравне- ний является метод простой втерацпв. Система уравнений Ах= Ь преобразуогсв к виду х = Вх+с, (2) н ее решение находится как предел последоватевьпосги х Ы =- Вх" -1- с. (3) Всякая система (4) х = х — В(Ах — Ь) имеет вид (2) и при с1е1Б ф 0 эквивалентна системе (1). В то же время всякая система (2), эквивалентная (1), зэлисываесся в виде (4) с матри.
цей .0 = (Я вЂ” В)А-'. Теорема (о достаточном условии сходнмости меропа простой итерэнди). Ксан (Щ( л 1, шо спстема щ1аененпп (2) пмееш едпнсоюеннсе репнине п Глава б. Численные ме>алы алгебры 26б и>перщионний процесс (3) сходи>эсл к решению со скорое>аью геометра">е. скоп нуюгрессии. ,Джазательство. Для всякого решения сисшмы (2) имыз место ((х(( < ((В((((х((+ ((с((, потому справедливо иерэзе>нхво ((х(((1 — ((В(() < ((с(( илн ((х(( < (1 — ((В(() >((с((.
Отсюда следует существование и един>хвенн>кть решения однородной си>гюмы х = Вх, а гледоватезьно, и системы (2) Путь Х вЂ” решение системы (2). Из (2) и (3) получаем уравнение атно. сительно погрешности г" = хь — Х: >л+ = Вг". (5) Из (5) получаем равенство (б) Отсюда следует, что ((гн(( < ((В(("((г~(( — > й. Теореыа доказана. Ка>ество итерационного проц>чхэ удобно характер>шовать скоростью убывания отношения пограпшости после и итераций к пачалын>й погрепшости: е =>"р е =((В ((. ((г (( ((Внгэ)( „э,я ((г" ((,.э е ((ге(( Можно шрантироват>ч что величина эв < е, если ((В(( < е, то.
при и > и, = 1п(е )/1п(((В(( >). (7) Кслн существуют пост>жнные у щ удо такие, по прн х д О ((х((д/((х((о < 7 р, ((х(( /((х((З < 7Э то нормы ((х((„и ((х((д нэзываэ>гся экоиваэентными. Им>ем ((г" ((д < у„в((гэ((,„< 7„в((В((" ((гэ((о < уоз уй„((В(~„''((г ((З. 'В>ким обрезом, если условие доказанной теоремы выполнено для нормы (( ((„, то утверждение справедливо относительно любюй экеиюленгной ей нормы. Любые две норл>ы в конечцомериом пространстве являю>гся эквивалентными. В частности, нормы ((х((>, ((х((э, ((х((,, эычи»чяемые соотвеч отвеина по формулам (2), (3), (4), приведенныы во вв>щеиии к настоящей главе, эквивалентны между собой вследствие справедливости цепочки неравенств ((х((,„, < ((х((г < ((х((> < п>((х((ьь.
Лемма. Пусть все собственные эна">ения Л> матрицы В лежат в круге (Л( < й, причем собс>поенным эна >етииг, по модулю равным д, соотввтс>верют экордановы клетки унэмерноспт 1. Тогда срществуе>п ма>арт>а й = Ю >ВЮ с нормой ((й(( < >у. 267 Ц 3. Метая простой итерации Докпзаспельстао. Положим ц =. д — агах (Лс!. Собственными значениями (ц(<г матрицы ц сВ будут ц слп Преобразуем матрицу ц сВ к жордановой форме / ц 'Лс осг О Р с(ц сВ)в = ~ 0 ц сЛг сгг где о, с+с принилсгют значения О нли 1.
После умножения на с1 получим / Л ° ц О Л=Р ВР=- О Лг огзц Если (Лс! = д, то согласно условиям леммы, сг,,ьс = О. Отсюда следует, .сто (Лс(+ (оаььсц! = ф Если (Л; < ц, то (Лс! + (о;,+ с 0! < вжх (Лс! + с1 = й. (Рд<с Таким образом, ЦЛЦ = шах((Л,(+ (аьсссц() < д. Теорема (а необходимом и доссаточном условии сходимостн метода простой ктерассви). Пртпь система (2) имеегп единственное ретениа Игпе1юционнмй процесс (3) сходится к ресссгнсск> сиспсемн (2) при любом начальном приблюкении тогда и только тогда, когда есс собсиюснньсе значения матрицы В по модрпо мен*исе 1.
Дткмаспельстео. Достато инскть. Возьмем произвольное й в пределах пжх !Л;! < й < 1. Условие леммы выполнено по относпению к атому д, позтому сугцествует матрица Р такая, что ЦЛЦ < 7 при Л = В сВР. Поскольку В = Рйв с, то в" = влв в..в 'влв =вл в Пснтому ЦВ Ц < ЦРЦ ЦР !Ц й -+ О Цх" — ХЦьс < ЦРЦ Цв Ц ЮаЦх — ХЦ -+ О при и -+ сю. Следовательно, и Цх" — ХЦс, Цх" — ХЦг -+ О. Если д.— «оорпинатвые орты, х = (кс,..., к )т, то х= ) к.йа Пусть Ц Ц— ! некоторая «орма, тогда ! ! х ! ! < Е ! я с ! ! ! Х с Ц < ! ! х ! ! Е ! ! К с Ц Глава б. Численные мешодв~ алгебРы 2ВВ Поэтому при любой корме )) ))имеем ))х" — Х)) < (~ ))х,))))Щ) ОБ-')) д"))х' — Х)) -г О. (9) Ссстисшеяяя Гб), (9) означают также, по любые кормы погрысвости убывыот быстрее любой геометрической прогрессии со звамеаатглгзь большим шах)ЛО Иесбзххлоиосшь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
