Бабенко - Основы численного анализа (947491), страница 101
Текст из файла (страница 101)
Простые итерации. В пп. 4. 7 3 4 гл. 2 мы уже познакомились с нтерацнямн нелинейного отображения В:  — т В, где  — некоторое В неравенства (29) (30) входят константы, которые можно лишь приближенно определить апостериори. Это константы тпах !»т. ),, (1т т, )Е, ' ,', <овсу 1. т<ь< — т В реальной ситуации пам дана матрица А -' сЛ. а не матрица А, и мы находим Ь„нт. Из оценок (29), (30) стелует, что если невырожденный минор матрицы А хорошо обусловлен, то будет хорошо обусловлен и соответствующий минор матрицы А+яВ н значение величины шах ~ тсь ', будет близко т<т< — т к той жс величине, но построенной по матрице 11,.
Поэтому апостериорный анализ разложения и Ьт может дать четкую картину при условии, что минор матрицы У, хорошо обут "ювлен. Таким образом, если нам известны априорная информация о вырожденнос.ти матрицы А, то при условии хорошей обусловленности соответствующего минора папучиьт, что у возмущенной задачи элемент ат,"„т (е) будет мал, и мы надежно сможем определить решение системы. Заметим, что такого рода задачи линейной алгебры возникают при решении краевых зада*с для обыкновенных дифференциальных уравнений, когда однородная задача имеет нетривиальные решения.
Если же число обусловленности матрттцы, построенной по невырожденпому минору. велико, мы после прямого хода ис.ключеиия получим нечеткую — тт — эт картину: может быть мзл не только элемент и„„, (к), но и о„, „( ) и др. Если нам априори известен ранг матрицы А, то можем принять волевое решение н поступать с возмущенной матрицей как с вырождетпюй. Если же нам заранее ничего не известно, то мы сталкиваемся с трудной дилеммой — какое решение принять, телт более что правые части возмущенной системы могут быть далеки от того, чтобы удовлетворять ушювию совместности. Уйы остерегаемся сказать, как нужно в дальнейшем посту.пнттэ поскольку нужна дополнительная информация о происхождении матрицы, о существе задачи, которая была сведена к решению системы линейных уравнений, н т.
и. О том, как влияют погрешности ОкруглЕния, мы уже гОвОрили (см. прЕдложение 3 33). Итак, резюмируя содержание этого параграфа, мы должны отметить следующее. Если решается система с вырожденной матрнпей, то необходимо обеспечить минимальные возмущения матрицы, особенно в случае ранга, меньшего и — 1. Для приведения к верхнему треутольному виду нужно воспштьзоваться алгоритмом Гаусса с выбором главного элемента по строкам и столбцам, а затем сделать дополнительные вычисления, найдя величины тпзх (»' ~, ~бт,т, ~1, .
Тогда можно надежно судить о достоверности — т с<с< — т результатов, во всяком случае, когда ранг равен и — 1. 492 Глава 3. Творил игпероций и мегподм решения неко»норма задач банахово пространство. Мы видели, что предельные точки орбиты (х )г х„, = Г(ж >) (т = 1, 2,...) могут быть множествами довольно сложной природы, и при нелинейных итерациях можно столкнуться и с циклами с довольно большим периодом, и с аттракторами иного типа. В этом параграфе рассмотрим линейный конечномерпый случай, сосредоточив внимание на чисто вычислительных аспектах проблемы. Для решения системы линейных уравнений Ах = а, где А и х п-матрица, часто применяют следующий прием. Пусть В = = ейгая (гди)," „преобразуем систему (1) к виду где Е = Р '( — А), Ь вЂ” -- Р ' а.
и ищом решение этой системы, используя простые итерации (2) х †. Ех > + Ь, т †. 1, 2,..., где хо —. начальное приближение. Часто в качестве матрицы Р берут либо единичную матрицу 1, либо диагональ матрицы А, если она является преобладающей, т.е. если ан > 2,' ~а„(г = 1, 2, ..., и). Этот >ем прием расщепления можно обобщить, введя разложение матрицы системы А =  — С, где В певырождепная матрипаг для которой система Вх = Ь может быть легко решена, и тогда итерации проводятся по следующему правилу: х э>=В >Сх +В заг (3) х„, > =" х — В (Ахы — а), т —.
О, 1,... Интересног что итерационный метод, известный как метод переменных направлений, можно пшчучить таким же способом. Пусть А =  — С, о некоторый параметр, и предположим, что системы (В + о1)х = Ь, (С вЂ”, о1)р —.— с могут быть «легко» решены (например, это будет, когда матрицы В, С эквивалентны треугольным). Итерации метода переменных направлений выполняются по правилам х +>1> =.-(В-ро1) '(о1 — С)х + (В+а1)" а, хы,г = (С р о1) (с«1 - В)х ья+ (С+ о1) а, т — — О, 1, Введем матрицы С = (2а) >(В+а1)(С+а1), 11=(2о) >( — е»1)(С вЂ” о1), тогда С вЂ” Н = —,ВС + о — оС ь а 1) — — (ВС вЂ” о — оС + сг 1], 1 2 з 1 я 2а ' 2о "е 5.
ХХтероиионные методы ртвения систем линейных 1уввнекий 493 и поэтому С вЂ” Н = В+ С = А. С учетом зтнх формул получим х э, = (С- о!) '(о1 — В)(В+ а!) '(о1 — С)х + -~- (С ч- ог") а+ (С вЂ” Ы) г(о! — Б)(В -с Ы) а: откуда в силу перестановочности матриц сЛ вЂ” В и (В + а1) ' г получим т„„эе —.— С Нх„— (С вЂ” ат) [а1 —  —, В+ОТ~(В -ЬО1) го =- = С'Нх — С"'а, Последнюю формулу можно записать в виде х,„~ —.-х„, - С' (Ах — а), т=0,1, (3') т.е.
мы получим итерационную формулу, аналогичную (3). Перейдем к методу простых итераций в его простейшей форме, которая дается уравнением (2). Из теоремы 1 З 4 гл. 2 и приведенных вслед за ней рассуждений вытекает необходимое и достаточное условие сходи- мости простых итераций. Мы сформулируем этот резулгиат несколько в более общей ситуации., считая, что В -- компактный оператор, отображающий банахово пространство В в себя. Теорема 1. Пусть  — колепвктный оператор.
Для того чтобы простые итерации (2) сходились к реиеению сиспгемы (1) при любом начальном векторе хе, необходимо и достаточно, чтобы спектпрвльний рвдиус р(В) тьвраторв В удовлепгворлл неравенству р(Ц < 1. ДокА3АтельстВО. Достаточность условия есть непосредственное следствие теоремы 1 54 гл. 2: условие р(В) < 1 влечет существование нормы 5 ~~м эквивалентной исходной норме в пространстве В, в которой , :Г ~~ < г < 1, Поэтому соотношение х — х з — -1(х„, е — х з) влечет неравенство 5хт х~п — 1[(1 г[(хт — 1 х~п — 25 и откуда ;х — х ~"ч <т ,'х~ — хосм и, следовательно, ряд ~„(х — х,„з) сходится в норме 5 .
~~м т. е. существует 1пп х„, в этой норме, а значит, и в исходной норме. Необходимость условия очевидна. Если р(В) > 1, то, поскольку оператор В компактный, спектр его дискретный, существуют собственное значение Л и собственный вектор у: 1,у = Лу такие, что ~Л > 1, Л ~л 1. 494 Глаза 3. Теоттио итпераций и тетоди уеитениа некотпория задач Подпространство., порогкденное вектором у, -- неустойчивое надпространство оператора А, и поэтому, если яе = д + у, где ~ -- решение уравнения (2), я =й — Л у, па=1 2,..., (4) что легко доказываетгя по индукции, и, стало быть, т, со. Если (Л) — -- 1, Л;~ 1, то я .,т — я .— — Л™(Л вЂ” 1)у и звт т — ят(! тт О. П Злмкчлник. Предыдущее доказательство несостоятельно, если В вещественное банахово простраяство, а Л комплексное собственное значение оператора 1.
В таком случае оператор А нужно рассматривать в комплекспфикации В,-пространства В. Если у ~ Во — собственный вектор оператора Е, то у = аз, + тсог, где рм уг е В. Рассьтотрим надпространство У с В, натянутое па векторы ~р» агг. Если Л = р ехр(1д), то оператор Ь действует в подпространстве У по формуле т (сттРт —, сг~Рг) .— —. ВРт -т т1тРг, Положив сов д зшд 1 — зш д соь'д/ П и предположив, что в формуле (4) у = щтрт — сглаз, вьтесто формулы (4) получим выражение ут=и ' тот+9 уг (от) где (О) (~„„т! )' = р Г (сы сг) .
из которого следует, что ят - ж при р > 1 и в данном случае. Если р = = 1, но д ф О, получим, как и выше, звтот — ат ~~ —,тт О. 2. Влияние погрешностей округления. Теорема 1 хотя и дает необходимые и достаточные условия сходимости простых итераций, но очспь часто сс практичсскос зпачспис мало. Мы зто установим па примере, а сейчас рассмотрим, как влияют погрешности округления на последовательность (жт ). получаемую в процессе простых итераций.
Пусть А — матрица размера п х п. Несколько упростив задачу, будем считать, что вычисляются не векторы ят, а приращения я — ят н Тогда вместо формулы (2) будем иметь (7) ят шп — т = В ад (ят т — г.'т — г), щ = 2. 3,. где теперь я„, — з т вектор, компоненты которого являются числами в системе с плавающей запятой. Пусть машинное представление матрицы А имеет вид! = (1, )," . Применяя формулу (1.2.14), получим для "1 5. Итерационные методи ре1аения систем линейных красновой 495 1ьй компоненты вектора т — ж„, 1 формулу (Жп — тт — 1)е =- ~~' 1п(ап — 1 — ттс 2)1(1+ еп )~ 1=-1~ 2 ~ и 1т — 11 где е,„.
= 1З„П(п+ 2 — у)(1+ п)е. Отсюда следует, что Х вЂ” т,п 1=1. 1(Х -1 — т З), т= 2,3,..., где 1т-В и .~'т — 1 (1м + 11де11 ) (8) (9) Жп — ~т-1 = 7т-1.. 81(~1 — те). Можно указать простое достаточное условие, когда последовательность (тт — Х„1) СтРЕМИтСЯ К НУЛЮ, И, СЛЕДОВатЕЛЬПО, ПРИ ВЫЧИСЛЕНИИ На ЭВМ по формуле (7), начиная с некоторого момента, показатель исчез- Допустим, что имеется целое Й такое, что (Ао! =с<1. Тогда легко видеть, что Х„,...Е, а11 = 1.~ з- Х ы откуда Ь Е вЂ” ьь1,'х < г — -'6ь „,и, следовательно, 1 1,1~ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
