Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 5
Текст из файла (страница 5)
Всего: 2п(йд Йг+ йд+ 2 юг+ 1) арифметических операций. 3 5.2. Алгоритм Ид'-разложения для трехдиагональных матриц Пусть требуется трехдиагональную матрипу вида ад сд дд! аг сг аг аз А= а„д д1ч — д с„д представить в виде А = И7, где 1 ид 1 иг 1 Лд Лг 13 (2) В этом случае формулы (4.13) алгоритма построения ИУ-разложения могут быть получены путем непосредственного перемножения матриц Ь и У и ре- шения получающихся уравнений: = ад, ид — — сд/1д Л, = дд„1г — — аг — Лдид, иг =с/1г Лд =до дд+д — а;+д — Лдио и,.дд — — с;+д/1;+д (3) Лп — г = дьд — г~ Л„д — — д1„д 1„д —— а„д — Л„ги„— г, и„д — — со-ддд1н-д = а„— Л„ди„д Построение ИУ-разложения по этим формулам требует п — 1 аддитивных и 2(п — 1) мультипликативных операций.
Решение линейной системы Ах = 6 может быть осуществлено следующим образом: 1. Вначале строится Ид-разложение матрицы А по формулам (3), на это требуется п — 1 аддитивных и 2(п — 1) мультипликативных операций. К.Ю.Богачев Точные методы решения линейных систем Аналогичное сокращение вычислительной работы может быть произведено для алгоритма Ид-разложения. '35. МЕТОДЫ ДЛЯ,ЛЕНТОЧНЫХ МАТРИЦ 2. Затем находится решение у линейной системы Б у = Ь путем последовательного исключения неизвестных, начиная с первого уравнения: у; = (Ьд — Лд-дуд-д)/1д, 1 = 2, (4) уд — — Ьд/1д, На этом этапе требуется произвести и — 1 аддитивных и 2(п — 1) + 1 мультипликативных операций.
3. Искомый вектор х находится как решение линейной системы Гх = у путем последовательного исключения неизвестных, начиная с последнего уравнения: х; = у; — идхд.дд, г = и — 1,..., 1. (5) На этом этапе требуется произвести и — 1 аддитивных и и — 1 мультипликативных операций. Складывая оценки трудоемкости на каждом шаге, находим, что для осуществления алгоритма требуется произвести 3(п — 1) аддитивных и 5(п — 1) + 1 мультипликативных операций. Замечание 2. Вспомогательный вектор у в приведенном выше алгоритме решения линейной системы может хранится на месте вектора х. Это следует из формул (4), (5), которые можно записать в виде хд — — Ьд/1д, хд = (Ь; — Лд дхд д)/1д, д = 2,...,и, х;:= х; — дддхддм г' = и — 1,...,1.
3 5.3. Метод прогонки для трехдиагональных матриц Пусть требуется трехдиагональную матрицу А вида (1) представить в виде А = ИУ, где 12 дз од ид х2 пг и„д К.Ю.Богачев Точные методы решения линейных систем Замечание 1. Хранение в памяти ЭВМ матриц А, Е и У. Матрипу вида (1) в памяти ЭВМ обычно не хранят. Вместо этого запоминают вектора а = (ад,..., а„)', с = (сд,..., с„д)', д1 = (ддд,..., дд„д)д .
Аналогично, вместо матрицы Б хранятся вектора 1 = (Ед,..., 1и)д, Л = (Лд,..., Л„д)', а вместо матрицы Г - вектор и = (ид,..., и„д)д . Как и в обычном алгоритме БГ-разложения, матрицы Б и Г можно хранить на месте матрицы А: вектор 1 — на месте вектора а, вектор Л на месте дд', и -- на месте с. '35. МЕТОДЫ ДЛЯ,ЛЕНТОЧНЫХ МАТРИЦ 25 В отличие от Ш-разложения, это представление не единственно.
Перемножая матрицы Ь и У,находим уравнения для определения коэффициентов 1о и;,и;: 11и1 = а1, и; 1+1и; =а;, и„1+ 1„и„= а„. 1ги~ — — с1 1и; =с;, в=2,...,п — 1 (6) и1= дп из 4~ ~1 е1 = а1, иг-1+ 1зиь = аь и„1+ 1„и„= а„. 1~ и1 — — с1 1;и; =сз г= 2,...,п — 1 Отсюда получаем расчетные формулы: = а1/им — (~И и1 — 1)/иб 1„ив= а„— и„ь и1 —— с~/11 и;= ~/1;, г= 2,...,п — 1 (7) Из последнего уравнения в (7) мы можем определить только произведение 1„е„. Зафиксировав один из параметров 1„или ен, мы определим второй. Мы будем считать, что е„= 1 . В этом случае, количество арифметических операций, необходимое для осуществления разложения по формулам (7) равно количеству арифметических операций, необходимому для осуществления разложения по формулам (3). Решение линейной системы Ах = 5 может быть осуществлено следующим образом: 1.
Вначале строится ИУ-разложение матрицы А по формулам (7), на это требуется и — 1 аддитивных и 2(п — 1) мультипликативных операций. 2. Затем находится решение у линейной системы Ь у = 5 путем последовательного исключения неизвестных, начиная с первого уравнения: у; = (5; — у, 1)/1ь г' = 2,..., и. (8) у~ = 51/11, На этом этапе требуется произвести и — 1 аддитивных и (п — 1) + 1 мультипликативных операций.
3. Искомый вектор х находится как решение линейной системы Гх = у путем последовательного исключения неизвестных, начиная с последнего уравнения: х„= у„/и„, х; = (у; — и;х;~1)/иь г = и — 1,..., 1. (9) На этом этапе требуется произвести и — 1 аддитивных и 2(п — 1) мультипликативных операций (с учетом е„= 1). Складывая оценки трудоемкости на каждом гааге, находим, что для осуществления алгоритма требуется произвести 3(п — 1) аддитивных и 5(п — 1) + 1 мультипликативных операций.
К.Ю.Богачев Точные методы решения линейных систем Число уравнений в этой системе, равное 2+ 3(п — 2) + 2 = Зп — 2, на 1 меныпе числа неизвестных 1ь н;,и; . Перепишем (6) в виде ~6. ЗАДАЧА ОБРАЩЕНИЯ МАТРИЦЫ 26 Замечание 3. Хранение в памяти ЭВМ матриц А, Т и У осуществляется так, как описано в Замечании 1. Вместо матрицы А запоминают вектора а = (аы...,а„)', с = (см...,с„г)', Н = (4,...,д„г)', вместо матрицы Ь вектор 1 = (1ы..., 1„)', а вместо матрицы Г -- вектора и = (гм..., и„)',и = (им..., и„~)' . Аналогично алгоритму Ш-разложения, матрицы Ь и У можно хранить на месте матрицы А: вектор 1 на месте вектора а, вектор г — на месте д (последняя, не определяемая однозначно компонента и„вектора г не хранится; ее можно считать равной 1), и на месте с.
Замечание 4. Вспомогательный вектор у в приведенном вьппе алгоритме решения линейной системы может хранится на месте вектора х. Это следует из формул (8), (9), которые можно записать в виде х~ — — 61/1м х; = (б; — х; 1)/1о г' = 2,..., и, х;:= (х; — и;х;~,)(и;, ю' = и — 1,..., 1. (здесь считается и„= 1 .) 3 6. ЗАДАххА ОБРАЩКНИЯ МАТРИЦЫ Рассмотрим задачу нахождения матрицы, обратной к данной.
Случай произвольного алгоритма. Пусть В некоторый алгоритм решения линейных систем вида Ах = 6, так, что х = В(А,о). Тогда 1'-й столбец х матрицы А ' равен х = В(А,е ), где е = (0,...,0,1,0,...,0)' есть у-й 1 — 1 орт стандартного базиса. Если алгоритм В требует для своего проведения д(п) арифметических операций, то этот способ нахождения обратной матрицы потребует пд(п) арифметических операций. Например, если В это метод Гаусса, то потребуется 2/3 п4 + 0(пэ) арифметических операций. Случай специального алгоритма. Многие алгоритмы решения линейных систем (в частности, все алгоритмы, рассматриваемые нами) обладают следующим свойством: алгоритм (по крайней мере его самая трудоемкая с вычислительной точки зрения часть) состоит в проведении над системой преобразований, которые выполняются над матрицей системы и правой частью независимо.
Эта особенность позволяет вместо правой части — вектора 6 — рассматривать набор правых частей, т.е. матрицу В. Преобразования алгоритма выполняются над матрицей системы и набором правых частей. Таким образом, такой алгоритм решения системы Ах = й может быть преобразован в алгоритм решения матричного уравнения АХ = В, где Х,В и х и матрицы. Обычно алгоритм решения системы Ах = й требует 0(пэ) арифметических операций для проведения преобразований над матрицей и 0(пв) арифметических операций для проведения преобразований над правой частью.
Поэтому алгоритм решения матричной системы АХ = В требует 0(пэ) + п . О(п2) = 0(пэ) арифметических операций. К.Ю.Богачев Точные методы решения линейных систем 'З7. МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА 8 7. МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА Теорема 4.1 показывает, что метод Гаусса в изложенном выше виде применим не ко всем невырожденным матрицам.
Например, если в системе (4.1) ап —— О, то нельзя осуществить первый же шаг алгоритма. Модернизируем алгоритм следующим образом. Уравнения в системе (4.1) равноправны, мы можем их занумеровать в произвольном порядке. Присвоим номер 1 тому уравнению, в котором коэффициент при х1 отличен от О. Если такого уравнения не нашлось, то матрица А имеет нулевой первый столбец, т.е. вырождена.
После этой перенумерации уравнений мы сделаем первый шаг метода Гаусса, т.е. перейдем от системы (4.1) к системе (4.3). Далее в подматрице АО) = (а) )); 2 „Е М„~ присвоим номер 2 тому уравнению, в котором коэффициент при х2 отличен от О, и сделаем следующий шаг метода Гаусса.
Затем этот процесс применяется к подматрице А е М„2 (2) и так далее. Если уравнений, в которых коэффициент при хг отличен от О, несколько, то с вычислительной точки зрения не безразлично, какое из этих уравнений получит номер 1. Пусть погрешность в элементе а; матрицы А равна е;,, т.е. вместо точной матрицы А рассматривается матрица А, элементы которой содержат вычислительные погрешности: а; = а; + е; . Для простоты будем считать, что элементы первого столбца известны точно: ен = О, г = 1,...,п. Из формул для элементов матрицы АО) (см.
(4.8), (4.6)): пц а$1 = ага ап ан = а(1) + а 11 ан , , ап — а1 — — а;. + е," — (а1 + е~ ) ан ан О) з;, ю',) =2,...,п, а,, = а,~ — снап — — а,у— ап = а;, — а1, + е,, — я11 ам где — е14 " г,у = 2,...,п, ам' К.Ю.Богачев Точные методы решения линейных систем Использование ИУ-разложения для обращения матрицы. Пусть для матрицы А возможно осуществить ИУ-разложение.
Действительно, если А = ИУ, то А ' = сг 'Т ". Матрицы, обратные к Т и Н, строятся, например, описанным выше способом. Поскольку системы с матрицами Т и Н решаются методом последовательного исключения неизвестных за соответственно п(п — 1) + и = пе+0(п) и п(п — 1) = и~+0(п) действий (см. формулы (4.10)), то матрицы сГ ' и Е ' могут быть вычислены с затратой пз+ 0(п~) арифметических операций. Следовательно, для вычисления обратной матрицы требуется: 2/3пз + 0(пе) арифметических операций для построения Ш-разложения, аз + 0(пе) арифметических операций для вычисления Г ' и Е ', п~+ 0(п2) арифметических операций для вычисления А ' = У 'Х '; всего: 8/Зпз+0(п2) арифметических операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
