Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 15
Текст из файла (страница 15)
Однако время расчета зависит от мпогпх факторов: от числа арпфметпческпх и логпческпх действпй, которые нужно затратить для получеппя решеппн с заданной точпостьк>, от быстродействия и оперативной памятн машины, от качества программы. Прп теоретнческпх оценках качества алгоритмов пх сравнение проводится по числу >,>(е) арифметических действпй, достаточных для палок'денна решеппя задачи с заданной точностьк> т ) О.
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) При ! () получаем с- ! ; с!«сь!'!ьь ь-! (26) с! с!О Полагая ! = 1, 2, ..., находим последовательно гг! — )/1 (а!с(, а!г! =- е!сп аги гт, == ~г)ае! — с)сг(а! )-'~, Определитель матрицы, очевидно, равен К с(г( Л = П с! „$',!. где В и С вЂ” троугольиые матрицы вида 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}
