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