III Канатников А.Н., Крищенко А.П. Аналитическая геометрия (3 изд. 2002) (1081381), страница 37
Текст из файла (страница 37)
Точно так же можно перестааеа сь столбцы, что равносильно изменению порядка неизвестны~ '!'аким способом не всегда можно получить матрицу с !о пладанием диагональных элементов в строках, но тем не «юч перестановки улучшают работу метода. 1! ргстановку строк и столбцов матрицы можно выполнять н !ндственно в процессе вычислений перед выполнением ' н !н диого шага прямого хода.
Перестановка столбцов должна !на ироваться, так как потом, когда будет получено решение, о,луот расставить значения найденных переменных в нужном !едко. Перестановку строк запоминать нет необходимости. ! 1~ ионная цель перестановки строк и столбцов — получение ь а нч.тве ведущего элемента возможно большего коэффициенматрицы. Поэтому на г-м шаге прямого хода метода Гаусса в н ~ троке выбирают наибольший по абсолютной величине элена и соответствующий столбец меняют местами с 1-м. В н ~уеьтате перестановки новый ведущий элемент становится нсн льшнм по абсолютной величине в своей строке (хотя, возано, н не преобладающим).
Выбор наибольшего ведущего «о и |та 1-й строки делают в столбцах с номерами е,1+1, ..., и, а ьак первые 1 — 1 элементов строки к г-му шагу обнуляютОп исанный алгоритм модифицированного метода Гаусса с ю лнительной перестановкой столбцов называют меуподом ! ну са с выбором елавмоео элементпа. ! !мбор главного элемента можно также проводить по столб- 1, ш !н ставляя строки так, чтобы на 1-м шаге ведущий элемент «агн олютной величине превосходил элементы своего столбца |пиная с (г+ 1)-го. Оба подхода не имеют преимуществ друг д другом, каждый может использоваться, когда стандартен метод Гаусса не работает (т.е.
один из угловых миноров а и нулю). С точки зрения ошибок округления и выбор по » еппу, и выбор по строке не являются безупречными, хотя - « ~сын инстве случаев дают хороший результат. Оба подхода 284 дО. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ можно комбинировать, и тогда выбор главного элемента выполняется и по строкам, и по столбцам, а именно: в качестве главного элемента на 1-м шаге выбирается наибольший из элементов а'„,, й, д' = д', и. Всего, следовательно, возможны три стратегии выбора главного элемента. 1 0 0,75 0 8 0,01 0 — 1 — 2,5 -7,99 На втором шаге делим 2-ю строку на 8 и прибавляем к 3-й (вычитание с коэффициентом — 1).
Получаем следующук> матрицу (с учетом округлений): с 1 0 0,75 0,75 0 1 0,00125 -0,9987 0 0 -2,499 -2,499 В конечном счете ошибки вычислений появляются, но с учетом округлений мы получаем точное решение. 10.5. Метод прогонки Рассмотрим СЛАУс трехдиагональнодд лдагарицедд 0 0 0 0 0 адд адз азд азз азз 0 ... 0 О 0 О азз азз азд ... 0 0 0 0 0 0 0 ... 0 а„ д „ а„„ Пример 10.4. Применим метод Гаусса с выбором главного элемента по строке к системе из примера 10.3.
Первый шаг совпадает с первым шагом метода Гаусса. Перед вторым шагом меняем местами 2-й и 3-й столбцы. Получаем 2ДО 10.5, Метод прогонки 1 о< О ... О д< О 1 оэ ... О ~9э О О 1 ... О дз О О О ... 1,3„ ги м< нты этой матрицы можно вычислить по формулам 6< А= —, ам' а<я «< .= —, ам 6; — Д <а;; < 1= ап — о;<а;,;< аь;+< 1=2,3,...,п — 1, аи — о<-<а«,-! 6„— 13„< а„„< <1„= а„„вЂ” <т„< а„,„< Обратный ход метода Гаусса также упрощается: Хо =<9и< х; = Д вЂ” о;х< ь<, 1 = и — 1,в — 2,..., 1. < <ии< аиный алгоритм для решения СЛАУ с трехдиаговальной митрицей называют ляетаодоля <эроеомкм. Замечание 10.1.
При решении СЛАУ с трехдиагональи й матрицей методом Гаусса перестановки строк и столбцов ирииодят, вообще говоря, к нарушению трехдиагональности м«ч рицы. Исключение составляет ситуация перед (и — 2)-м шитом, когда перестановка двух последних строк оставляет митрицу трехдиагональной. Учитывал это, в методе прогонки и< рестановки строк и столбцов не используют. Лл я СЛАУ с такой матрицей вен<од Гаусса упрощается. На ко<ядом 1-м шаге прлиоео хода нужно пер~~читывать толь~о ни <'троки: 1-ю и (г+ 1)-ю.
После прямого хода расширеннал иишрица СЛАУ будет иметь вид 286 10. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИИ СЛАУ Следующий пример показывает, что ошибки округления прп использовании метода прогонки столь же опасны, как и при использовании метода Гаусса. Пример 10.5. Несколько изменим СЛАУ из примера 10.3, добавив еще одно уравнение и введя четвертую переменную так, чтобы получилась система 4х+ Зу = 3, 10х+ 7,51у+ 8х = — 0,49, — 2,5у — я+1 = — 1,50, я+1= — 1 с трехдиагональной матрицей.
Ее точным решением является х = О, 9 = 1, х= — 1, 1= О, в чем можно убедиться непосредственной проверкой. Применим метод прогонки, предполагал, что вычисления выполняются с точностью до четырех десятичных знаков. После выполнения первых двух шагов метода прогонки, так же как в примере 10.3, получаем матрицу 1 0,75 0 0 0 1 800 0 0 0 1999 1 0 0 1 1 0,75 -799 -1998 — 1 1 0,75 0 0 О, 1 800 0 0 0 1 0 5002,10-з 0 0 0 1 0,75 -799 — 0,9995 0 5003,10-з В результате обратного хода получаем в качестве решения х = О,З, у = 0,6, х = — 0,9995, 1 = — 0,5003 10 з, что, как и и примере 10.3, значительно отличается от верного решения. Выполнив третий и четвертый шаги, приходим к следующей матрице: Д.10.1.
Мультиалииативиые раэлолееиия матриц 287 Дополнение 10.1. Мультипликативные разложения матриц Рассмотрим СЛАУ Ах = Ь. Если представить каким-либо аг>р>сюм матрицу А в виде произведения А = РЯК трех (или ц угого числа) невырожденных матриц Р, Я, В, то СЛАУ '>х — Ь можно разложить на три системы: П>иледовательно решал эти системы, мы получим решение я> х»дной СЛАУ. Представление невырожденной матрицы в виде произведения нескольких матриц называется мульти>злимаувивным разложением матрицы. Решение любой СЛАУ в конечв>м счете сводится к обращению матрицы ~т.е. вычислению нциианой к ней). Поэтому наиболее важны такие мультиплию>тивные разложения матрицы, в которых сомножители легко ог>ратить.
Назовем наиболее известные виды легко обращаемых матриц. Лля обращения диагональной матрицы достаточно замешггь все ее диагональные элементы на обратные к ним числа. Ортогональная матрица А (удовлетворяющая соотноше- т ниь> А А = Е) обращается при помощи операции транспониро- т ю>ния: А ' =А . Нерхнлл треугольнал матрица, у которой все элементы под .>ниной диагональю равны нулю, интересна тем, что решение иттемы с такой матрицей методом Гаусса упрощается: факеп и ски требуется выполнить лишь обратный ход. Пижнлл треугольная матрица, у которой все элементы над > ханной диагональю равны нулю, аналогична верхней треу«>хьиой матрице, и в случае такой матрицы метод Гаусса 288 10.
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ также упрощается: прямой код меп>ода Гаусса сразу приводи < к ответу. Оказывается, что метод Гаусса можно интерпретировать как один иэ способов построения мультипликативного разлож< ния матрицы А системы в произведение А = И7 двух матриц, где 6 — нижняя треугольная матрица, а П вЂ” верхняя тре угольная с диагональными элементами, равными единице. Это разложение матрицы А называют л сГ-разложением.
Отметим, что произведение верхних треугольных матриц тоже является верхней треугольной матрицей. При этом соот ветствующие диагональные элементы просто перемножаютсп Обратная к верхней треугольной матрице также является верх ней треугольной. Все это верно и для нижних треугольных матриц.
Наиболее важное наблюдение заключается в том, что лк> бое элементарное преобразование стирок какой-либо матрицы равносильно умножению этой матрицы слева на невырождеп ную матрицу специального вида (см. 6.8). То же верно и для последовательных шагов метода Гаусса. Таким образом, выполнение прямого хода метода Гаусса означает умножени< уравнения Ак = Ь слева на некоторую невырожденную матрицу 5, равную произведению матриц специального вида для элементарных преобразований прямого хода, причем в результате такого умножения система преобразуется к виду 1>'ж = 6' = зЬ, где П вЂ” верхняя треугольная матрица с единицами по главной диагонали.
Обозначив А = Я ', заключаем, что А = ИУ. Выясним, какой вид имеет матрица 6. Для восстановления Ь-й строки в матрице А надо Ь-ю батраку матрицы П умножить на а „и к результату последовательно прибавить 1-ю, 2-ю, ..., 1-1 (й — 1)-ю строки с коэффициентами соответственно аь1, а1,, ..., а„„,. Это равносильно умножению матрицы П слева на >с-2 матрицу-строку ( 1 Ь-2 <с-1 аь1, аь2, ..., аь „„аь 1,, О, ..., 0) Д.10.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
