Бабенко - Основы численного анализа (947491), страница 96
Текст из файла (страница 96)
В настоящее время многие разделы численного анализа переживакгт бурную перестройку в связи с внедрением конвейерных процессоров и параллельных ЭВЫ. На первый план в настоящее время выдвигаются вопросы параллелизма вычислений, и для того, чтобы обеспечить высокую степень параллельности выполнения операций, жертвуют часто экономичностью алгоритма, т.е. идут на алгоритмы, решающие задачу зв большее число операций, но обладающие высоким параллелизмом выполнения операций, и в итоге получают меньшее время выполнения алгоритма.
На ЭВМ. где операции выполнялись последовательно и имелись один поток данных и один поток команд, время выполнения алгоритма. грубо говоря, пропорционально чиспу операций. На ЭВМ с параллельным действием зто не так: зтнм и объясняется тот реальный выигрыш во времени выполнения алгоритма при обеспечении высокого параллелизма. В связи с увеличением памяти ЭВМ заметна тенденция перехода к алгоритмам решения краевых задач, приводящих к заполненным матрицам. Раньше была обратная тенденцня алгоритм оценивался высоко, если он приводил к разреженныхи матрицам, т.е.
матрицам, у которых в каждой строке немного ненулевых злементов. Это просто означает, что если п -- порядок матрицы, то число )е ненулевых злементов в любой строке удовлетворяет условию 1г « п. Решение систем с заполненными матрицами естественно требует применения общих методов. Учитывая зти соображения, мы остановимся только на методе исключения Гаусса и некоторых его модификациях. Рассмотрим систему линейных уравнений вида аыхг + аггхг —, ... + аг„х„= Ь1, ашхг — аггхг — , '... — ' аг„х„=- Ьг, апПХ1 + апгХг — ' ...
+ апплп = Ь„. 11ерез А = (а,г)п, обозначим матрицу системы (1), а через х .=- (хг, ..., х„)' вектор неизвестных. если а11 ф О, мы можем исключить хг из всех уравнений, начиная со второго, для чего из второго уравнения вычтем первое, умноженное на т12 =- а12,1а11, из третьего вычтем первое. умноженное па тз1 = аз1/а11, и т, д, В результате система уравнений (1) заменится зквиввлентной системой а11х1 + а12 ' 2 + ° + а1птп, = Ь1 Ю.. %. а22'1'2 ~ ''' ~ еггпхп" "2 (2) апг х2 + 1 а„„хп — — Ь„ Я (Ц 111 468 Глава д.
Творил игпераций и лгетоды решения некоторых задач 1(озффициенты при неизвестных и правые части в последних п — 1 у рав- нениях определяются по формулам а, =ам — 7пглалзз 6, =6,— т, 6,. 7, 7=2г 3, ...г и. (3) Обозначим через А)1) матрицу системы (2). Нетрудно проверить, что матрицы А и А11) связаны соотношением А71) = М1Аг где Л»1 нижняя треугольная матрица следующего вида: 1 — тг1 1 О (4) ЛХ, = — тп1 О 1 аыхл+ алгхг ... + а1 х = 61, (И (1) )1) а22 ел+ а2пхп 62 Дг) а„т1 ° 1Х„;1+...
+ а„1 птп — -- Ьеа1 (б) 71) )е), 111) егп,е е1Хг 1 ' апптп и Новые козффициенты и новый вектор правых частей Ь' — (Ь1, 62 ...., Ьеы,..., 6„) были найдены по формулам 1е) (г) гг — 1) лг — О Ьгг) Ьгг — 1) агз =. агз — 7Пгеаш, '— , — 7Пге 7', 7 = г + 1г 7 + 2, ...г пг (6) где 1е — Ц7 ег — О гаге — ап 7 аг.г. (7) Положим ао — — ап; тогда формулы (6) будут справедливы при 7 = ео) —... 1, 2,.... Матрицу системы (б) обозначим через А<').
На основании формул (6) замечаем, что 41г) Ь» А(г — 1) (8) Ясно., что если агг ~ О, то процесс можно продолжить и произвести ОО исключение хг из уравнений, начиная с третьего и кончая п-м. Продолжим зтот процесс и предположим, что мы сделали г шагов и на г + 1-м шаге получили систему з 2, Решение аггнейннх ааеебраичесних ураанеггий где Мс — нижняя треугольная матрица: 0 (й) пгс ецг' имеющая отличные от ну.т элементы в позиции (1.
г) (1 = г + 1г г+ 2, ..., и) и диагональные элементы, равные 1. Поскольку переход от матрицы АО' ') к матрице А~") совершался с помощью преобразований, не меняющих величину миноров этих матриц, то миноры 1-го порядка матриц А1с г) и А1') равны. А поэтому равны и миноры 1-го порядка, содержащиеся в первых 1 строках матриц А и А~с). Обозначим минор 1-го порядка матрицы А, содержащейся в первых 1 строках, чс- (1 2 рез А ~,, ' ' ', ~ г где )гг < ...
< )лг номера столбцов. Учитывая структуру матрицы Агс), найдем при 1 < г 10 0 — 1) .— -- аиаз ... ан (10) 1 ... Г7 О) 1с — 1) гс) =аиа,, ...а„с а, Деля почленно второе равенство на первое, взятое при 1 = г получим А~ ''' .'~ )4~ ''' ~, гг..гг, г,..., .
гггг Для того чтобы г. шагов гауссовского метода исключения можно бы0 — г) ло осуществить, неооходимо и достаточно, чтобы а„ф О при г = — -- 1, '2г ..., г. Учитывая формулы (10), последние условия могут быть записаны в виде А фОг А 12 у-Ог ..., А ''' фО. В этом случае из соотношения (10) находим „=АЦг г, '=.4~ '' г1ггг~ ' г ~, г=г,г,.... гггг Из формулы (8) следует, что А~") = М„...М А. 470 Глава 3, Гаврил и«аераций и методы решения некоторых задач Допустим, что ранг матрицы А равен г.
Надлежащей перестановкой уравнений (строк матрицы) и изменением нумерации неизвестных (перестановкой столбцов матрицы) можно добиться выполнения неравенств Поэтому. мы можем исключить неизвестные хм ..., х„и привести систему (1) к эквивалентному виду (5). Поскольку ранг матрицы А равен г, то в силу (11) а,'. = О, й д > г+ 1., г — 2, ..., и. (14) и, значит, последние п — г уравнений системы (5) сводятся к условиям совместности Ь~"~ = О, з = г+ 1. г -' 2, ..., и. (15) Таким образом, в случае вырожденности системы дальнейший процесс исключений не нужен. Но нам удобно будет трактовать систему (5) как систему, полученную на и-м шаге исключения, полагая А«') =-... = А«н ц Ь<") =...
=. Ь«" ». (10) Если система «ювместна, мы можем, используя систему (5), найти частное решение х неоднородной системы, полагая х„= ... = х„= 0 и находя неизвестные х«, ..., х, из оставшихся уравнений (о) (о) омх + ашх —... оо х„= Ь» «о) «о) , «о) О) <о) <о) ,(о) аз«тв . + азах„ (17) ),-», «о) Ь«« — «) а х Матрица системы (17) верхняя треугольная, и неизвестные х «о) ..., хе можно найти последовательно по формулам % (о) Ь«е- «) « ) — » х„=, ««а„„ йо),;ЬО -1) а( — «)х)о) а( -«)х(оП )аб о) (18) з=-« — 1,г — 2,...,1.
Аналогично можно найти базис подпространства реп«еннй однородной системы, решив однородную систему (5) и найдя векторы х«) = (х ..., х,, О, ..., 1, ..., 0), где 1 стоит в г - ««-й позиции («« = 1, 2, ..., и— — г). Тем самым мы получим общее решение системы (3) в виде и — « 'з2. Рсюгнис линейных агггбргических грос~сниц 471 Изложенный способ решения системы (1) называется методом исключения Гаусса; процесс исключения неизвестных и приведение системы (1) к верхнему треугольному виду называется прлмь<м ходом гауссовского процесса исключения, а вычисление неизвестных по формулам (18) обратным ходом. Несложно подсчитать число операций, необходимых для того, чтобы решить систему (1) в случае, когда ранг матрицы А равен и,.
Число умножений и делений равно <с~<<3 з- п~ — г<<'3, а число вычитании и сложений равно пг73 ' г<г/2 -. бп)К Заметим, что перестановку строк и ст<шбпов матрицы Л можно делать не до начала вычислений, а в их процессе. Перестановка двух строк матрицы А (А<О) с номерами 1, 2 зюжет быть осуществлена с помощью умножения слева на матрицу 1, . Матрица 1, отличается от единичной лишь строками г и у' и столбцами < и зй ее элементы в позипиях (1, !), (у, !) равны нулю, а в позициях (1, !), (у, 1) единице при г Р у', 1и = 1, 1и1, = 1, где 1 — единичная матрица. При умножении матрицы А справа на матрицу 1,, переставляются 1-и и Лй столбцы.
Таким образом, в процессе прямого хода матрица Л<О будет умножаться слева и справа на матрицу 1и ., где гп у< выбираются так, чтобы после умножения в позиции (1-1, !+1) стоял элемент, максимальный по модулю среди к<ементов последних и — ! строк и столбцов. Гели таких элементов несколько, то берется элемент с минимальными номерами строк и столбцов. Затем исключается неизвестная, получившая номер !+1.
Если матрица Л имела ранг г,процесс закончится после г шагов. Этот метод называется методом исключения с выбором главного элемента. Делается он не только для того, чтобы процесс исключения не встречал препятствий, но и для того, чтобы повысить численную устойчивость метода. Если на некотором шаге исключения ведущий элемент а, у< О, но лгал., то в принципе следующий шаг исключения возмо- [О жен. Йо если его реализовать. то на следующем шаге появятся большие элеъ<енты, которые после еще одного шага исчезнут, но прн этом мол ет произойти огромная потеря точности.
Читатель сам может подобрать пример матрицы третьего или четвертого порядка, на котором можно проследить это явление потери знаков. Алгоритм с выбором главного элемента по столбцам и строкам довольно сложен. Намного проще метод исключения с выбором главного элемента по столбцу. Именно, если должна исключаться неизвестная х<ез, то в ! — 1-м столбце среди коэффициентов а, <, (1 = 1+ 1, 1+ !<! + '2...., и) выбирается наибольший по модулю, т. е. матрица А!О умножается слева на некоторую матрицу 1<тз ., и затем производится исключение. Если же а< < < = О (< = ! — '1, ! 2, ..., н), то матрица АОЗ особая, !<! так как ее первые ! + 1 столбцов линейно зависимы.
Но отс<ода следует, что и матрица А особая. В самом деле, образуем из первых ! — '1 столбцов матрицы А матрицу В размером и х (! — ' 1)., а из первых ! —, 1 столбцов матрицы А!О л<атрицу В<О. Матрица В<О получена из матрицы В пре- 472 Глава 3, Творил игперациб и методы решения некоторых задач образованиями, не меняющими ранга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
