Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 41
Текст из файла (страница 41)
Квадратичная форма (1) называется полоасительно (отрицательно) определенной, если она принимает положительные (отрицательные) значения, обращаясь в нуль лишь при х,=х, =... =х =О. л Если и(х„х„..., хл) — положительно определенная квадратичная форма, то уравнение и(х„х„..., хл)=с (с)0) представляет собой уравнение эллипсоида. Заметим, что в этом случае ап) О (1=-1, 2, ..., Л), так как а д —— и (1, О, ..., 0) ) О, а„ = и (О, 1, ..., 0) ) О, алл = и (О, О, ..., 1) - О.
Решение систем линейных угьанений [ГЛ. ЧН! ЗО6 О п р е д е л е н и е 3. Назовем линейную систему ~ а!тх =в! (1=1, 2, ..., и) (4) ! ! нормальной, если: 1) матрица коэффициентов А=[агт] — симметрическая, т. е. а!у — — ат!, 2) соответствующая квадратичная форма л л и = ~~~~ ~~ а!тх;хт — положительно определенная. 1=1 Рль Нормальные системы встречаются при решении многих вопросов, например, в способе наименьших квадратов, при нахождении направлений главных осей вллипсоида и т.
д. Нормальную систему (4) приведем обычным способом к специальному виду хслл ~ а!тх +р„ ГФ! (4') где ь! (у~1') и [1;=-. ал' аг! се!/ ——— аи Ах= а (5) о неособенной матрицгй А = [а!т[ умножить слева на транспонированную матрицу А'= (а т1, то полученная новая система А'Ах = А'Ь (6) будет нормальной. Докажем сначала, что матрица А'А есть симметрическая матрица. В самом деле, имеем: (А'А)' = А'А" = А'А.
Теперь докажем, что квадратичная форма, соответствующая матрице А'А, — положительно определенная. Составим квадратичную форму с матрнцей А'А: л л л и(Х, Хь, ..., Хл) = ~ ~~' ,'5',аюаетмгХР 1=1 1=1 Ь=1 Т е о р е м а 1. Если линейная система (4) — нормальная, то процесс Згйдгля для эквивалентной гй приведенной системы (4') всегда сходится. Доказательство см. главу Х1, $5, а также (21. Способ приведения линейной системы к нормальному виду указывается следующей теоремой.
Теорема 2. Если обе части линейной системы 307 В!втод Рвллкслции 14) Изменяя порядок суммирования, получим: л л л л / л В и =,~~,са,~ а„х;аь7х7 —— ~~'„~ ~~~~~ а„;х; ~~»', а„х й 1 11 (=, Так как значение суммы не зависит от обозначения индекса сумми- рования, то и= ~ ~~'., аь;х; ~0. Согласно прелположению бе(А = бе(~а,,-] че О. Поэтому однородная система с~~ ~а„;х;=0 ()с=1, 2, ..., и) 1=1 имеет лишь нулевые решения.
Следовательно, и(х„х„..., х„) ~ 0 при (х,(+(х (+... +)х„(~0, Теорема доказана. ф 14. Метод релаксации Пусть имеем систему линейных уравнений аыхз+ а,вхв+... + а,„х„= Ьы аатх + ае,ха+... + а,„х„= — Ьв, а„,х +а„х +... +а„„х„=б„. Преобразуем эту систему следующим образом: перенесем свободные члены налево и разделим первое уравнение на — аып второе на — а,в и т. д.
Тогда полУчим системУ, пРиготовленнУю к Релаксации, — х +Ь хв+...+)) „х„-1-с =О, Ььтх„+Ь„ах +... — х„+с„=О, тле а0 ас Ь; = — — (1~7') и с;=— и 308 гашения аистам лннвйных тглвнвний 1гл. чн( )с('> = с) — х(,'>+ ~~~~ Ь, х(">, )=$ с»(»») с х(о>+ ~я~~ ~Ь,х(») )=1 ) и. е (3) и-1 7»(»> с х(»») 1 ~~»' Ь к]е) (=> Если одной из неизвестных х('> дать приращение ох('>, то соответствующая невязка )с<'> уменьшится на величину бх(,,'>, а все остальные невязки 77<'> ()' ~ а) увеличатся на величину Ь) бх<'>. Таким образом, чтобы обратить очередную невязку )с('> в нуль, достаточно величине х('> дать приращение бх(»> я(е) и мы будем иметь: )с<)> = 0 и И(»> Ро>+ Ь. 6х<о> при ( ~ а Метод релаксации (по-русски: метод ослабления) 13], '14] в его простейшей форме заключается в том, что на каждом шаге обращают в нуль максимальную по модулю невязку путем изменения значения соответствующей компоненты приближения.
Процесс заканчивается, когда все невязки последней преобразованной системы будут равны нулю с заданной точностью. Вопрос о сходнмости етого процесса мы оставляем без рассмотрения 14). Пример. Методом релаксации решить систему 13] 1Ох, — 2х, — 2хз = 6, — х,+ 1Ох — 2х =7, — х — х,+10х =8, (4) производя вычисления с двумя десятичными знаками. Решение. Приводим систему (4) к виду, удобному для релак- сации — х,+0,2хз+ 02ха+О 6=0, — х,+0,1х +0,2х +0,7=0, — ха+0,1хд+0,1хз+0,8 =0.
Пусть х(»> = (х(е>, х(»>, ..., х('>) — начальное приближение решения системы (2). Подставляя зтн значения в систему (2), получим невязка метод гвлакслции 809 Выбирая в качестве начальных приближений корней нулевые аначения =х"'=х<О= О 3 находим соответствующие „ '<" = О 70 Л<е> 0 80 Согласно общей теории полагаем: бх<ы = 0,80. е Отсюда получаем невязки <с<ы=<г<О+0,2 0,8=0,60+0,16=0,76; й«еп=й<е>+0,2 0,8=0,70+0,16=0,86; <т =<с — Л =О з 1 е Таблица 23 Решение линейной системы методом релаксации 310 Решение систем линейных уРЛВнений [Гл.
Шц Далее, полагаем бхсо = 0 86 и т. д. Соответствующие результаты вычислений приведены в таблице 23, Суммируя все приращения б)о> (1=1, 2, 3; Й=О, 1, ...), получим значения корней х = О+ 0,93+ 0,07 = 1,00; х = О+ 0,86+ 0,13+ 0,01 = 1,00; х = О+ 0,80+ 0,18+ 0,02 = 1,00. Для контроля подставляем найденные значения корней в исходные уравнения; в данном случае система (4) решена точно. й 1б. Исправление элементов приближенной обратной матрицы Пусть имеем неособенную матрицу А и требуется найти обратную матрицу А о.
Положим, что мы получили приближенное значение обратной матрицы 0ож А т. Тогда для улучшения точности можно воспользоваться методом последовательных приближений в специальной форме. В качестве предварительной меры погрешности используем разность Го = Е АОо. Если Го=О, то очевидно, что х)о=А г, поэтому, если молули элементов матрицы Го малы, то матрицы А о и ь1о близки между собой. Будем строить последовательные приближения по формуле во=по,+7)Е,ГЕ, (а=1, 2, 3, ...), (1) причем соответствующая погрешность есть Гь — — Š— АО . Оценим быстроту сходимости последовательных приближений. Имеем: '(ог = Е А (~-~о+ 7)оГо) = Е Ау~о (Е+ Го) = = Š— (Š— Го) (Е+ Г' ) = Š— (Š— Г,') = Г', .
Аналогично — Го Го о и, вообще, Го — — Г~* (Й=1, 2, 3, ...). (2) а 13) нспг»влвння элвмвнтов пгивлиженной овг»тной млтгицы 311 Докажем, что если Действительно, нз формулы (2) имеем: (г»1~~~Е Р <Ч Поэтому Иш]Е»]=О » Ф и, следовательно, 1пп Р»= Иш (Š— АО~) =О » ю» а нли Š— Айша„=о, »->в т. е. Иш 12» —— А 'Е=А т. »-~ Ф Таким образом, утверждение доказано. В частности, используя и»-норму (гл. Ч!1, $ 7), получаем, что если элементы матрицы Р = (717] удовлетворяют неравенству !Л;!~ ~ где и — порядок матрицы и Ом.:;д(1, то процесс итерации (1) заведомо сходится. Предполагая неравенство (3) выполненным, оценим погрешность й»=~!А-» — ~>») ~фА-'~!] Š— АП»]=(А-»)]Е»]=]А-»1п»'.
Так как АР» = Š— Р», А '=1:)»(Š— Ео) '=12»(Е+Ео+Р',+ ° ) то Отсюда Р ')~И(У»РАНЕН+й+Р'+" ]=Ф»П(ПЕ)+~ ' ~ ° Длв л»-нормы нли 1-нормы имеем 1Е(=1, и поэтому (Ре()-«аЧ < 1, (3) где 1Г»)' какая-нибудь каноническая норма матрицы Е (гл, ЧИ, Я 7), то процесс итерации (1) сходится, т. е. Иш Й» =А »-~ а РеШЕиие систем линейных уРАВнений (гл.
Уд!! Таким образом, (4) или (5) где норма понимается в смысле лд-нормы или 7-нормы. Из формулы (4) следует, что сходнмость процесса (1) при д(<1 очень быстрая. На практике процесс уточнения элементов обратной матрицы прекращают, когда обеспечено неравенство '112» — д)о д1:ц;е, где е †заданн точность. П р и м е р. Исправить элементы приближенной обратной матрицы, полученной в примере 9 7 на стр. 286. Решение. Для матрицы 1,8 — 3,8 0,7 — 3,7 0,7 2,1 — 2,6 -2,8 7,3 8,1 1,7 — 4,9 1,9 — 4,3 — 4,9 — 4,7 методом Гаусса получена приближенная обратная матрица — 0,21121 — 0,46003 0,16284 0,26956 В = 0'03533 0'16873 0'01573 0'08920 о = 0 23030 0 04607 0 00944 0 19885 — 0,29316 — 0,38837 — 0,06128 0,18513 причем 0,03 0,00 0,01 0,00 0,25 0,03 0,02 0,39 8,08 10,17 0,18 — 0,09 0,00 0,00 0,00 — 0,48 АПН=Š— 10 о ° Отсюда 0,03 0,00 0,01 0,00 0,25 0,03 0,02 0,39 8,08 10,17 0,18 — 0,09 0,00 0,00 0,00 — 0,48 Ро=Š— А04=10 Оо+д — — ЕРА+Р Еы Ео — — Š— АОА (Ф=О, 1, 2, ...).
Для дальнейшего уточнении элементов матрицы Оо воспользуемся итерационным процессом 314 Решение систем линейных уРАанений (гл. Еми 2 — 2 1 3 О 2 — ! О~) 3 4 — 5 1 о о Ед — — Š— А!У, =10 з ° На основании формулы (4) для погрешности имеем оценку )А-х д зк( о5г ))и )! Так как '! Рз(й = 0,46003+ 0,16873+ 0,04607+ 0,38837 с.
1,07 ))Рх ))г 10-ь. (2+ 2+ 4) 8. 10-ь то окончательно имеем: !А-' — Вт)х и=1 — 1 02.'19-з ° 8 10-' < 9 10-'. 3 а м е ч а н и е. Подбор приближенной обратной матрицы может быть осуществлен различными способами. В частности, используется способ обращения матриц, указанный в главе И1, 9 12. В заключение главы отметим следующее. В настоящее время разработаны многие другие методы решения системы линейных алгебраических уравнений (Метод Перселла, зскалаторный метод [6], метод Ричардсона 17) и др.) Литература к восьмой главе 1, В. Н.
Ф з д д е е в а, Вычислительные методы линейной алгебры, Гостех- издат, 1950, гл. 11. 2, Дж. С к а р б о р о, Численные методы математического анализа, ГТТИ. 1934, дополнение 1. ,'-', М. Дж. Сальвадорн, Численные методы в технике, ИЛ, М., 1955, гл. 1, 6 10. 4, Современная математика для инженеров, под ред. Э. Ф. Беккенбаха, ИЛ, М., 1956, гл. 15. 5, Х. Л. Смолицкий, Вычислительная математика (конспект лекций), ЛКВВИА им. Можайского, Л., 1960. 6, Д. К. Ф а д де е в н В.
Н. Ф а д д е е в а, Вычислительные методы линей- ной алгебры, Фнзматгиз, 1960, гл. 11. 7. И. С. Березин н Н. П. Жидков, Методы вычислений, Фнзматгиз, 1959, гл. У1. ГЛАВА 1Х» СХОДИМОСТЬ ИТЕРАЦИОННЫХ ПРОЦЕССОВ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ ф 1. Достаточные условия сходимости процесса итерации Пусть мы имеем приведенную линейную систему х=ссх+р, рх а=(а; ), хс — заданные матрица и вектор и х= . — искомый вектор. Т е о р е и а. Процесс итерации для приведенной линейной системы (1) сходится к единственному ее решению, если какая-нибудь каноническая норма матрицы а меньше единицы, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
