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