Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ), страница 4

МЕТОД ГАУССА Из (11) получаем: 1,! = АА, откуда А = Ш, где Т = А ' Е ЬТ (и), 11 верх- няя треугольная с единицами на главной диагонали. Полученное представление матрицы А называется ИУ-разложением. Итак, показано, что метод Гаусса эквивалентен построению И!-разложения. 3 4.4. Алгоритм построения И,!-разложения Пусть требуется найти нижнюю треугольную матрицу Ь = (1; ) и верхнюю треугольную матрицу с! = (и,,) с единицами на главной диагонали такую, что А = Иг, т.е. 1;,иь=а!ь, Е 4=! (12) 1,Й =1,...,п. Поскольку 1; = О при г < !, и ь = О при ! > й, и" = 1, то (12) есть система из па уравнений относительно и(и+ 1)/2 неизвестных 1и, 1 > у и и(п — 1)/2 неизвестных и !, ! < Й, всего п(п+ 1)/2+ п(п — 1)/2 = пв неизвестных.

Получим формулы для решения системы (12), которые и составляют алгоритм нахождения И! -разложения. В силу 1; = О при г < !', и ь = О при у' > й сумма в (12) имеет вид з,1=1,...,п, й ~: 1,,и,„=ави у=! ~': 1!, и,„= аич Й< 1, г,1=1,...,п, Й>г, К.Ю.Богачев Точные методы решения линейных систем Знание И! -разложения матрицы А может быть полезно, например, в следующей ситуации. Пусть требуется решить ряд систем вида Ах = й, га = 1,..., М с одной и той же матрицей А и разными правыми частями 6 .

Применяя М раз метод Гаусса это можно сделать за (2/3) М иа + 0(М г!э) (и -э оо) арифметических операций. Предположим, что нам известно ИУ-разложение матрицы А: А = Ш. Тогда решение каждой из систем Ах = б может быть сведено к решению двух систем Ау„! = 6~, ! !.г„„= у„„с треугольными матрицами. Решение системы с треугольной матрицей осуществляется обратным ходом метода Гаусса за 0(и~) (п — > со) арифметических операций.

Следовательно, если ИГ-разложение матрицы А уже построено и на это построение потребовалось д(п) арифметических операций, то решение М систем с той же матрицей А потребует д(и) + 0(Ми~) (п — э со) арифметических операций. Подчеркнем, что число а(п) не зависит от М. Сейчас мы построим алгоритм для получения Ш- разложения и покажем, что !1(п) = (2/3)п + 0(п ) (и — ~ оо) (т.е. равно числу операций, необходимых для проведения метода Гаусса). 34. МЕТОД ГАУССА 20 Выделим в первой из этих сумм отдельно случай Й = 1, а во второй - случай 1= 1, и учтем, что иы, — — 1 для всех Й = 1,...,и, Перегруппируем эти формулы 1=1,...,п, (13) 1<1<1, к>г>1, г,1=2,...,п.

Процесс вычислений по этим формулам строится следующим образом: вначале по первой из формул (13) вычисляются неизвестные элементы первого столбца матрицы Т: 1п, 1 = 1,...,и, затем по второй из формул (13) вычисляются неизвестные элементы первой строки матрицы сГ: и1ь, Й = 2,..., и (напомним, элемент ип известен, он равен 1). Далее в вычислениях участвуют только третья и четвертая из формул (13). По третьей формуле (13) вычисляются неизвестные элементы второго столбца матрицы Ь: 1еь г' = 2„...,п (напомним, 1ьч = О, так как Ь -нижняя треугольная) 1ье — — аье — 1п и12, 1 = 2,..., и. По четвертой формуле (13) вычисляются неизвестные элементы второй стро- ки матрицы 11: ияы й = З,...,п (напомним, и21 — — О, так как 11 -верхняя треугольная, и22 — — 1, так как 1,1 имеет единичную главную диагональ) и2ь = (а2ь 121 иИ)/122, ~ = 3 ...

и. Затем по третьей формуле (13) вычисляются неизвестные элементы третьего столбца матРицы Ь: 11тч г' = 3,..., и, а по четвеРтой фоРмУле (13) вычислЯютсЯ неизвестные элементы третьей строки матрицы 11: изы Й = 4,..., и и так далее. Замечание 1. Организация хранения матриц Ь и Е~ в памяти. Формулы (13) таковы, что при вычислении элемента 1; или и; используются значения элемента а; и вычисленных ранее элементов 1ь,„, т < 1 и и1,, Й < 1. Это позволяет хранить нижнюю треугольную матрицу Ь на месте нижнего треугольника матрицы А: 11, = асп 1 > у, г, 1 = 1,..., и, а вернюю треугольную матрицу 11 (без единичной главной диагонали) — на месте верхнего треугольника матрицы А: и11 =аип 1<у, 1,2'=1,...,п. К.Ю.Богачев Точные методы ретения линейных систем ! 1п =ап, й — 1 1;, иа, +1ь — — аап 1=1 с 111 и1ь = а1ы в — 1 111 иуи+ 1и ига = ацо 1=1 1п — — ап, и1ь = а1ь/111, й — 1 11ь — — ац, — 2„1;, ивы 1=1 1 — 1 ии — — (а1ь Е 111 игь)(1а> 1=1 1=1,...,п, 1<Й<1, 1,1=2,...,п, 1=2,...,п, Й>г>1, г,1=2,...,п.

34. МЕТОД ГАУССА 3 4.5. Оценка количества арифметических операций в алгоритме построения Е1.т-разложения 1. При фиксированном й = 1,...,п вычисление элементов 1а, для всех 1 = й,..., и по тРетьей фоРмУле (13) тРебУет 2," ь(й — 1) = (и — й + 1)(й — 1) мультипликативных и столько же аддитивных операций. Следовательно, вычисление всех элементов матрицы Е требует ~,ь~,(п — Й + 1)(Й вЂ” 1) = и ~;ь~,(Й— 1) — ~ ~,(Й вЂ” 1)г = п~,":„"1 — ~,":„'Р = п~(п — 1)/2 — (и — 1)п(2п — 1)/6 = пз/2 — из/3+ О(и~) = из/6+ О(ттг) (и — ~ со) мультипликативных и столько же аддитивных операций. 2. При фиксированном ю' = 1,...,и вычисление элементов и;ь для всех Й = г'+ 1,...,и по четвертой формуле (13) требует У'.~;„,1 = (и — 1)1 мультипликативных и 2 ~;+ (1 — 1) = (п — 1)(1 — 1) адцитивных операций.

Следовательно, вычисление всех элементов матрицы 1Е требует ~,",(и — 1)ю' пг(п+ 1)/2 — п(п+ 1)(2п+ 1)/6 = пг/6+ 0(пг) (и -+ оо) мультипликативных и Х;,",(и — 1)(1 — 1) = п~(п — 1)/2 — п(п+ 1)(2п+ 1)/6 + п(п+ 1)/2 = пз/6+ 0(тР) (и — т оо) аддитивных операций. Таким образом, алгоритм построения ЕЕт-разложения требует для своего проведения выполнения пг/3 + 0(п~) (п -+ со) мультипликативных и столько же аддитивных операций, а в сумме (2/3) из+0(п~) (и — ~ со) арифметических операций. 3 4.6. Осуществимость метода Гаусса Теорема 1. Метод Гаусса осуществим (т.е. возможно П1-разложение) тогда и тполько тогда„когда для всех й = 1,...,п ее главные угловые миноры с1е1Аь ф О, где ап а~г ..

аи агт а22 агь Аь —— аы аьг ... аьь главные угловые т~одматрицы матрицы А. Доказательство. Можно показать (мы этого делать не будем), что если с1е1 Аь ~ О для всех 1с = 1,..., и, то существует и единственно И1-разложение матрицы А. Обозначим через Еь и Ет~ главные угловые подматрицы матриц Е и Ет. Так как Š— нижняя треугольная, а Ет — верхняя треугольная матрицы, и А = ЕЕт, то Аь = ЕгЦ,.

Следовательно, с1е$ Аь = с1е1Ет с1е$ 1тт.. Но матРица Ет -веРхнЯЯ треугольная с 1 на главной диагонали, поэтому с1е1 ать = 1 для всех Й = 1,..., п. Значит, с1е1Аь = с1е1Е~. Матрица Еь -нижняя треугольная, поэтому с1е1Еь = 1н...1ьь. Следовательно, с1е1 Ат, — — 1п... 1ць. Пусть для всех Й = 1,...,п с1е$Аь ф О. Тогда 1п = с1е$А~ ф О, с1е$ Аь/с1е$ Аь т ~ О и в формулах (13) возможно осуществить деление на 1н, 1 = К.Ю.Богачев Точные методы ретення линейных систем ~5. МЕТОДЫ ДЛЯ,ЛЕНТОЧНЫХ МАТРИЦ 22 1,..., п. Следовательно, осуществим алгорим построения Ы7-разложения, а значит, и метод Гаусса. Пусть осуществим алгорим построения И7-разложения, т.е.

в формулах (13) возможно осуществить деление на 1а, г = 1,...,п. Следовательно, для всех 1 =1,...,п 1а ~ 0 и потому с1е$Аь = 1м...1ьь ~ 0 для всех й =1,...,п. 8 5. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО ИСКЛЮЧЕНИЯ НЕИЗВЕСТНЫХ ДЛЯ ЛЕНТОЧНЫХ МАТРИЦ Определение. Матрица А Е М„называется ленточной, если а; = 0 при г — у > й~ либо 1 — 1 > йз. Величина й~ + й~ + 1 называется шириной ленты. Если й1 — — й2 — — 1, то матрица называется трехдиагональной. з 5.1. Метод Гаусса для ленточных матриц Расчетные формулы метода Гаусса (4.6), (4.8) „(4.10) остаются справедливыми и для ленточных матриц, но объем вычислений по ним может быть сокращен при учете структуры матрицы А. В формулах прямого хода (4.6), (4.8) вычисления надо вести для у = 1+1,...,Й+Йг, 1 = 1+1,...,Й+Й1.

Ширина ленты системы (4.9), получающейся после прямого хода, равна йз+ 1, поэтому в формуле (4.10) обратного хода метода Гаусса надо учитывать только йа + 1 слагаемых. Аналогично тому, как это было сделано выше, можно подсчитать, что 1. На вычисление сь при у' = 1+1,..., й+й2, к = 1,..., и по формулам (4.6) требуется п йг + 0(1) операций деления. 2. Навычисление а; при г = 1+1,...,й+/см у = 1+1,...,И+1с2, й =1,...,п по формулам (4.8) требуется п й1 йа + 0(1) операций умножения и столько же операций вычитания.

Итак, на вычисление коэффициентов сь„1 = й + 1,..., й + Й2, й = 1,..., п системы (4.9) требуется п(й~ Й2 + Й2) + 0(1) мультипликативных и столько же аддитивных операций. 3. На вычисление уь при й = 1,..., и по формулам (4.6) требуется и операций деления. 4. На вычисление 5; при г = 1+1,..., Й+йп й = 1,..., п по формулам (4.8) 00 требуется и й~ + 0(1) операций умножения и столько же операций вычитания. Итак, на вычисление правых частей ш, й = 1,..., п системы (4.9) требуется и(Й1 + 1) мультипликативных и столько же аддитивных операций. Таким образом, прямой ход метода Гаусса требует п(й~ Ьд+ Й1+ 12+ 1) мультипликативных операций и столько же аддитивных операций. 5. На вычисление решения по формулам (4.10) (т.е.

на проведение обратного хода метода Гаусса) требуется и Й2 + 0(1) операций умножения и столько же операций вычитания. К.Ю.Богачев Точные методы решения линейных систем '35. МЕТОДЫ ДЛЯ,ЛЕНТОЧНЫХ МАТРИЦ Следовательно, метод Гаусса требует и(йд йг+ йд + 2 йг+ 1) мультипликативных операций и столько же аддитивных операций.