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