А.А. Самарский - Введение в численные методы (1113832), страница 15
Текст из файла (страница 15)
Само приближенное решение явлнется результатом вь>чпс,>епп», полученным после конечного числа птерацпй. Выбор того нлп нного чнслешни.о метода завнспт от многнх обстоятельств — от имеющихся программ, от вода матрицы А, от тнпа расчета п др. Пояс>шм слова «тпп расчетаз. Возможны разные постановки задачн: 1) найти решение одной конкретной задачи (1); 2) найти решение песколькпх варпантоз задачи (1) с одной и той жо матрпцей А п разнымп правымп чостямп 1. Может оказаться, что пеоптнмальпый длл одной задачи (1) метод является весьма эффективным для многоварпантного расчета. Прп многовариантном расчете можно уменьшить среднее число операций длн одш>го варианта, если хранить некоторые величины, а пе вычнслять пх заново для каждого варианта. Ото, конечно, зависит от машины, от объема ее оператнвпой памяж>, 11з сказанного ясно, что выбор алгорнтма должен зависеть от ткпа расчета, от объема оперативной памяти машины и, конечно, от порядка системы.
Качество алгоритма определнется тем машинным временем, которое требуется для нахождения решеппв сметены (1). Естественно выбирать тот метод, для которого время реп>ения минимально по сравнению с другнмп методамп. Однако время расчета зависит от мпогпх факторов: от числа арпфметпческпх и логпческпх действпй, которые нужно затратить для получеппя решеппн с заданной точпостьк>, от быстродействия и оператлвной памятн машины, от качества программы. Прп теоретнческпх оценках качества алгоритмов пх сравнение проводится по числу >,>(е) арифметических действпй, достаточных для палок'денна решеппя задачи с заданной точностьк> т ) О. 5 е ниимыг ыктоды в 2. Прямые методы 1.
Метод Гаусса. Имеется несколько вычнс;ипгльпык вариантов метода Гаусса, основанного иа идее последовательного исключения. Процесс решения гигтемы линепныт алгебраическим уравнений Ах = ), или а о„.= )ь 1"- з. ч ио методу 1'аусса сошоит из двут:панов. П е р в ы й э т а и (иря кои ход). Си< т< ма (1) приводится к треугольному виду х+ Л'х == б, (2) где х = (х„..., т,.) — неизвестный, с~ = (с(,... „О;) известпыи векторы, В" — вертияя треугольная матрица. В т о р о й э т а и ~ обратный ход). Неизвестные х -, х,, ..., х, определяются по формулам (2) пз т 1. Перейдем к подробному пзло кеншо метода. П е р в ы й ~наг метода Гаусса состоит и исключении из веет уравнении, кроме первого, неизвестного х,.
Предполоктим, что а„чь О, разделим первое уравнение (1) ((= 1) на а„ и заишпем систему (1) в виде х; + Ьмх;+... + Ь,,та = ~го Ьс = а, Уа,о 2 ~ ) <:- Л', с(д == ),/ао, (3) а„.т, +а, х.+...+а„.хз 1„(=2. 3, ..., Х. (1) Умно кям уравнепио (3) иа иа, где 1 — лаюое из чисел 1 2, 3...., Ж, и вычтем полученное уравнение из Ьго ура в не ння (4): (аа — ааЬ,,)х, +... + (а,а — а„Ь,,)хт = ~; — а„ц.„ '.З,,...Х Вводя обозначения а„=- а;) — аибгп 1; ~ .=.,', — а,,ц,, (, )' --, 3, (5) перепишем полученную систему уравнений (эквивалентную системе (1)) в виде х, (- Ьых, -,'-... -,'- Ь,кхх —.. ~р„ ай Гл. П1. РГП!!!ниГ лчГГГР(нчГГких 1'Р1энш!ип Первый столбец матрицы этой системы состоит пз нулей, кроме первого элемента прп 1= 1, 1 = 1, равного единице.
В т о р о й ш а г состоит в исключении х, пэ системы (1) , (1) з(1) амхз р ° ° + пзмхл = )1 1 (б) ол)х. + ° ° -'г ох.тхл .- )я. (1) (1) з(1) Для этого разделим первое уравнение на азз ! (1). х2+ Ь22хз+ ... + Ь, Х, = рм Чз = )2 /пзз' Ьм =- пзз)/озз )' = 3,, Л', умножпм его затем на ( — а(2) п сложим с уравнением (1)1 амхз+амх,-;... + а(яхл = )к(, 1=3,4, ...,1)1, (1) (1) ( (1) (1) В результате подучим систему хз — - Ьыхз + ° ° ° + Ьз\хл (гзз 7 а х„-(- .
° ° + а;;-хл = !"1, 1 = 3, 4 з ~лз (2) (1) (1)з 42) 41) (1) а;) = ан — ам Ьан й = )1 — ам (р„ ( = 3, 4, ..., ))(. (8) Для х„хз, ..., хл имеем систему (У вЂ” 2)-го порядка, аналогичную системе (б) ((1' — 1)-го порядка для хз, х„...,х.-. Продоля(ая рассуждения, после (1)! — 1)-г о ш а г а (т. е, после исключения х„х„.. „т,,) получим а~"~. "хя = У~" ", или тл == (Рх (гл= )(У "/а7л и (9) В итоге приходим к системе (2) с верхней треугольной матрпцей: хз+ Ьз.хз+ Ь~зхз+ .. + Ьзлхк =(рзз х. + Ьмхз+... + Ьззэзх = ())з (10) х., 1+Ьк-ьхх.
=Ч'к2о Хз (Р т. Обратный ход метода Гаусса состоит в определении всех хз иэ системы (10) с верхней треугольной матрицей. Нетрудно показать, что изложенный выше метод Гаусса можно применять в том случае, когда все главные миноры отличны от яуля. а 2 пгямые метОды Подсчитаем число умножений п делений в методе Га. усса. Рассмотрим сначала прямой вод.
На первом шаге требуется ф = Ж' делений и умножений, второй шаг требует (), (Х вЂ” 1)' действий и т. д. Всего надо сделать 2т шагов прямого хода, эатратив на это Х (Л' й+ 1)2 Ь а2 тт(а ~ 1) (2У+ 1) (15) (16) — 5х,— 6,5х, = — 8, Зх,+х, 1. 51ы получпчп систему второго порядка. В т о р о й ш а г. Разделим (15) на — 5: х. + 1,3х, 1,6. Умнояшм (17) на — 3 и сложим с (16): — 2,9х, = — 5,8. Третий шаг. Делим (18) на — 2,9: х, 2.
В реаультате получили систему х, + 2х, + 1,5х, = 2, х,+1,3х,-16, (17) (18) умножений и делений. Для обратного хода, очевидно, нужно сделать Л(% — 1)/2 умножений. Таким обраэом, для решения системы уравнений (1) требуется %22'+ 3/т' — 1)/3 умножений и делений. Примерно столько же потребуется сложений. Приведем пример применения метода Гаусса, Рассмотрим систему трех уравнений (Х = 3) 2х,+4х.,+Зх, 4, (11) Зх, +х,— 2х,,— — 2, (12) 4х, + 11х, + 7х, = 7. (13) Прямой ход.
Первый шаг. Разделим первое уравнение на ао = 2: х, + 2х, + 1,5х, = 2. (14) Умножпм (14) на — 3 и слонсям с (12), затем умножпм (14) на -4 и сложим с (13): М Г-1 1П РГП!ЕНИГ .1ЛГЕБР.АП'!ЕСКПХ ГРЛВПЬППО с верхней треугольной матрнцей Е~Ч () б р а т и ы й х о д, Из системы последовательно находим: х„= 2, х, = ).Π— 1,3 х, = 1,6 — 1,3 2 = — '1, х, = ==2 — 2х,— 1,5 ° х, = 1.
Таким образом, решение снстемы (11) — (! 3) нандено: х, 1, х, = — 1, х, — 2. 2. Метод квадратного корня. Этот метод пригоден для систем Ап (1О) с зрмвтовой (в действительном случае — симметричноп) матрицей А. Матрица А разлагается в проиаведенпе А ЯЮЯ, (20) где Я вЂ” верхняя треугольная, !) — диагональная матрица. Решение уравненнн Аи ) сводится к последовательному решению двух систем Я«0у=г, Яа=у. (21) т1тобы получить раалоя!ение (20), обозначаем Я = («А), Ю = Ы„б«) и находим к л (Ы)1) Х И1ИЦ = И! «1Г (Я ПЯ)1)" Х «ы1) «) так как ЯА = («в), где черта — комплексное сопряжение. В реаультате получаем уравнение Х «ААПАА«А1 ОЦ.
(22) А=-1 Систему уравнений (22) можно решать рекуррентно. Так как Я вЂ” верхняя треугольная матрица, то «А! = 0 при й ) 1', «„ = 0 прп й : 1 и, следовательно, Х «А1«А1ПАА = А=-1 1 — 1 л ч1 — Х «А1«А,ААА -р «п«,1А11 + ~~А «А,ЯА;41 = А.— 1 А.==; 1-1 = .АА; «А1«А!г)АА + «1«1)111; = гмя А -1 а х пгйиыя метОды При ! =1 имеем с-! )х«)сс)!! = ૠ— ~ !ам(сг)ьь. ь=! (22) Выбирал с(п =- е|яп ૠ— ~ (яы ~Чм й=! (24) найдем (25) При ! () получаем 1- ! ; с!«сь!')ьь ь-! (26) с! с!О Полагая ! = 1, 2, ..., находим последовательно гг! — )~(а„~, а!г! =- е!сп аги гт, == ~г)ае! — с)сг(а! )!), Определитель матрицы, очевидно, равен К с(г( Л = П с! „$',!. где В и С вЂ” троугольиые матрицы вида 0 О 11 lь ь„О ...
О '! )) ь!!! ь.„, ьз„... о ! с1! с!3 ' с!к О ! с, ... с т ОО Г ...с„. 0 О О ь,ьт.ьт, ... ь, т. е. Ь,! О ОРи )с) !, с„О «Ри )с(с! с«=-!. Пс (22) Метод квадратного корня требует порядка!!'"'/3 арифметических действпгт, т. е. ири больших У оя вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти.
Зто обстоятельство объясняется тем, что метод использует ииформацшо о симметрии матрицы. 3. Связь метода Гаусса с разложением матрицы на множители. Пусть дана невырождениая матрица А размера )! Х г!!. Представим ее в виде произведения Л =- БС, Л =- (а„), В = (Ьс), С = (г„), (27) 96 гл. Н1. Ркшенне ллгевглнческнх твлвненнн следует, что ан = ~ Ьмсл;. А=! Преобразуем эту сумму двумя способами: я л-! я .ьз Ь!лсл! =- с~ Ьмсы+ Ьисв+ л'.! Ь!лсл! = л=! л=! л=л-.-! 3-! ~ Ьнсы =- '! Ьмсю + Ьяся + .с~ Ь!лсл! =- '%!! л=! л=! л=! л! л-1 ~~'.~ Ьнсл; + Ьпссь л=т ! — ! ~~~ Ьнсл! + Ьнся. л=! Отсюда находим ! ! Ьп .—.: ап — ~~э~ Ьмсю л::.! прв !~у, Ьм.-а„„сп — (, ! .! сп: — ил — ~„Ь!лсл! прн ! ( !'.
а Матрицы В п С найдены, Решение уравнения Ли= ВСи ! сводится к последовательному решению уравнений В!(=Л Сн=в. Построение матриц В и С и нахолкденне !р = В '! соответствуют прямому ходу, а решение уравнения Си сс соответствует обратному ъоду метода !'аусса. й 3, Итерационные методы Л =!. л(э!я ее решения выонрается некоторое начальное прнблн- !. Метод итераций для решения системы линейных алгебраических уравнений. Особое внимание в этой главе мы уделим нтерацнонныв! методам„так как онп широко применяются для решения разностных уравнений матсматической фнэикп, операторам которых соответствуют ленточные матрицы Л высокого порядка.
Перейдем к общему описанию метода мтерс!(ий длл системы линейных алгебраических уравненпй в з итввлцпонньш мвтоды жение у, «Н п последовательно находятся приближенные решештя (птерацпп) уравнения (1). Значение итерации уьы выражается через известные предыдущие итерации ут, ув-о ... Кслп прп вычислении у,.„, используется только одна предыдущая итерация у„, то итерационный метод называют одношаговым (шш двухслойным) методом; если же у,е, вырая1ается через две итерации у, и у, „то метод называется двухшаговыш (плп трвхслойныьз), Мы будем рассматривать в основном одношаговые методы.
Будем считать, что Л: П вЂ” П вЂ” линейный оператор в конечпомерноп пространстве П со скалярным произведением (, ). Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный итерационный метод мол~но записать в следугощей канонической форме: ух+, — в, чь Луь =- 1 тае1 й =-0,1,..., для всех у, еи П, (2) где Л: Н -~ Н вЂ” оператор исходного травпенпя (1), В: Н- Н вЂ” линейный оператор, 1гмеющпй обратный В ', )с — номер итерацнп, т„т„..., тг.п ...— итерационные параметры, тьы ) О. Оператор В может, вообще говоря, зависеть от номера й; для простоты излогкепия мы предполагаем всюду, что В пе зависит от й.
Если В = Š— единичный оператор, то метод а -)- Луе =- )', й — О, 1, ..., для всех у„~ Н, Аег называют явнызп ул.з находится по явной формуле уы ~ = ув тгы(Луг )). Естественно требовать, чтооы ооъем вычислений для ре- шения .системы ВУ„„=-.Р, бьпг меньше, чем объем вы- гислений для прямого решения системы Ли В общем случае, прп В Ф Ь, метод (2) называют нвявнхьп итерационным методом: для онределеиия у,, надо решить уравнеипе Вуги — — Вд — т„,(1У,— )') =Гь й О, 1, ... (Я вй гл. пт, Ргшкпив алгевглпчгскнх тпавпенип Точность итерационного метода (2) характеризуется величиной погрешности г„у,— и, т.
е. разностью между решением у„уравнения (2) н точным решением и исходной системы линейных алгебраических уравнений. Подстановка у,= з,+ и в (2) приводит к однородному уравнению для погрешности: В ~~ +Ать=О Л'=-0 1 за=ус и. (5) та„ Говорят, что итерационный метод сходится в В, если 1пп'(заЬ =- О, где "Ы'э = И(Л)з, з), Л) = )7*) О, Вч  — 1!. ь-ню Обычно задают некоторую погрешность (относительную) е ) О, с которой надо найти приближенное решение ут, н прекраща|от вычисления, как только выполняется условие 1у„— и1„( в~~у, — и(! (6) Коли п = п(е) — паименьшео на чисел, для которых (6) выполняется, то общее число арифметических действий, которые затрачиваются для нахождения приближенного решения уравнения (1), равно ()„(е) = п(е)дм где д~ — число действий, затрачиваемых для нахождения одной итерации, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
