Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 21
Текст из файла (страница 21)
Поэтому онп должны быть отличными от нуля; в противном случае необходимо соответственным образом переставить уравнения системы. Перестановка уравнений должна быть предусмотрена в вычислительном алгоритме при его реализации на ЭВМ. Обратный ход начинается с решения третьего уравнения системы (4.14): РР/ Я хз = Ьз/'азз 1Л, 4. СПСТГЗ1В1 ЛППЕ01П~1Х УВЛВПГПП11 Рис, 16. Блок-скетча метода Риусса На рис. 16 приведена блок-салема реи1енпя методом Гаусса системы и линейны1 уравнений вида а„х, + а„х, +... + а„,х„= 6о а,,х, + а„х, +...
+ а.„х„= Ь.„ а ° ° ° ° ° а„,х, +а„,х, +... + а„„х„= Ь„, ~5 ~ пРямые з1етоды Левая часть блок-схемы соответствует прямому ходу. Иоясним смысл индексов: ~ — помер уравнения, из которого исключается неизвестное х,; у — номер столбца; Й вЂ” номер неизвестного, которое исключается из оставшихся и — Ь уравнений (а также номер того уравненпя, с помощью которого исключается х„) . Операция перестановки уравнений (т. е.
~'*А +1 перестановки соответствуюгцих коэффициентов) слу- л /с+1 1 1 жит для предотвращения деления на нулевой элемент. 11равая ' асть бчо '- хемы ~ - ! 1 . ,1 да ~а,~ ~ а„ описывает процесс обратного хода. Здесь ~ — помер не- Нет известного, которое определяется из ~-го уравнения; 1'= ~+1, ~+ 2, ...— номера уже найденных неизвестных. Нет Одной нз модификаций Да метода Гаусса является схема с въгбором главного элелынта. Она состопт в том, Нет что требование неравенства ;7'- т нулю диагональных элементов а„„, на которые происходит делепле в процессе ис- алу — ау~' ключения, заменяется более жестким: из всех оставшихся в й-м столбце элементов Аа ~'~ б Р1 нужно выбрать наиболь- ./,7 ший по модулю и переста- Нет вить уравнения так, чтобы ь,=ь, этот элемент 'оказался на месте элемента а„„.
Блок-схема алгоритма . с= а ~ (анн выбора главного элемента приведена на рпс. 17 Она Рис. 17. Выбор главного зле дополняет блок-схему мето- мента а Гаусса (см. рис. 16) . десь введены новые ипдексы: 1 — номер наибольшего по абсолютной величине элемента матрицы в столбце с номером Й (т. е. среди элементов а„„, ..., а,, ..., а,„); т— текущий номер элемента, с которым происходит сравне- 126 гл. 4. системы лпннйньгх уРАВненпй ние. Заметим, что диагональные элементы матрицы называются ведуи~ил~и элементами; ведущий элемент а„,— это коэффициент при Й-и неизвестном в Й-м уравнении на lс-м шаге исключения.
Благодаря выбору наибольшего по модулю ведущего элемента уменьшаются множители, используемые для преобразования уравнений, что способствует снижению погрешностей вычислении. Поэтому метод Гаусса с выбором главного элемента обеспечивает приемлемую точность решения для сравнительно небольшого числа ~п-~ < 100) уравнений. И только для плохо обусловленных систем решения, полученные по этому методу, ненадежны.
Метод Гаусса целесообразно использовать для решения систем с плотно заполненной матрицей. Все элементы матрицы и правые части системы уравнений находятся в оперативпоп памяти машины. Объем вычислений определяется порядком системы и: число арифметических операций примерно равно ~2/3)п'. И р и м е р. Рассмотрим алгоритм решения линейной системы методом Гаусса и некоторые особенности этого метода для случая трех уравнений: 10х~ — 7хг 7, — Зх,+2х,+6х, =4, 5х~ — х, + 5х~ = 6. Исключим х, из второго и третьего уравнений. Для этого сначала умножпм первое уравнение на 0.3 и результат прибавим ко второму, а затем умножим первое же уравнение на — 0.5 и результат прибавим к третьему, Получим 10х, — 7х, 7, — 0.1х, + 6х, = 6.1, 2.5х, + 5х, = 2.5.
Прежде чем исключать х, из третьего уравнения, заметим, что коэффициент при х, во втором уравнении (ведущий элемент) мал; поэтому было бы лучше переставить второе и третье уравнения. Однако мы проводим сейчас вычисления в рамках точной арифметики и погрешности округлений не опасны, поэтому продолжим 127 5 2. пРямые методы исключение. Умножим второе уравнение на 25 и результат сложим с третьим уравнением.
Получим систему в треугольном виде: 10х, — 7х, 7, — 0 1х. + 6х, = 6.1, 155х, = 155. На этом заканчивается прямой ход метода Гаусса. Обратный ход состоит в последовательном вычислении х„х„х, соответственно из третьего, второго, первого уравнений. Проведем эти вычисления: 155 6~з — 6.1 7з.,т 7 15 " = — '1 х = "' О Подстановкой в исходную систему легко убедиться, что (О, — 1, 1) и есть ее решение. Изменим теперь слегка коэффициенты системы таким образом, чтобы сохранить прежним решение и вместе с тем при вычислениях использовать округления. Таким условиям, в частности, соответствует система 10х, — 7х, =7, — Зх~ + 2.099х2+ 6хз = 3.901, 5х, — х,+ 5х.
=6. Здесь изменены коэффициент при х, и правая часть второго уравнения. Будем снова вести процесс исключения, причем вычисления проведем в рамках арифметш'и с плавающей точкой, сохраняя пять разрядов числа, После первого шага исключения получим 10х, — 7х, =7, — 0.00 1х, + 6х, = 6.001, 2.5х, + 5х, = 2.5.
Следующий шаг исключения проводим при малом ведущем элементе ( — 0.001). Чтобы исключить х, из третьего уравнения, мы вынуждены умножить второе уравнение на 2500. При умножении получаем число 15002.5, которое нужно округлить до пяти разрядов. В результате 128 г:,1. 4. систкмы линеиньгх уРАВнениЙ получаем третье уравнение ь виде 15 005х, = 15 001. Отсюда х, = 15 004/15 005 = 0.99993. Из второго и первого уравнений найдем 6 0.99993 — 6.00$, 0.0015 хг 0.001 О.001 Исключим теперь х, пз третьего уравнения, прибавив к псму второе, умноженное на 0.0004 (ведущий элемент здесь равен 2.5). Третье уравнение примет вид 6.002х, = 6.002.
Отсюда находим х, = 1. С помощью второго и первого уравнений вычислим х,, х,: х.=, = — 1 г т5 7+7( — 1) Таким образом, в результате перестановки уравнении, т. е. выбора наиболыпего по модулю из оставшихся в данном столбце элементов, погрешность рсшения в рамках данной точности исчезла. Рассмотрим подробнее вопрос о погрешностях решения систем линейных уравнений методом Гаусса, Запишем систему в матричном виде: АХ = В. Решение этой системы можно представить в виде Х = А-'В. Однако вычисленное по методу Гаусса решение Х„, отличается от этого решения пз-за погрешностей округлений, связанных с ограниченностью разрядной сетки машины, Вычисления проводились с усеченпем до пяти разрядов по аналогии с процессом вычислений на ЗВМ. В резуль- тате этого было получено решение ( — 0.35, — 1.5, 0.99993) вместо (О, — 1, 1) .
Такая большая неточность результатои обьясняетса . малой величиной ведущего элемента. В подтверждение этому переставим сначала уравнения системы: 10х, — 7х. = 7, 2.5х, + 5х, = 2.5, — 0.001х + бх, = 6.001. $2. прямые метОды 1.29 Существуют две величины, характеризующие степень отклонения полученного решения от точного. Одна из них — погрешность е, равная разности этих значений: е = Х вЂ” Х .
Другая — 'невязка г, равная разности между правой и левой частями уравнений при подстановке в нпх решения: г =  — АХ~, Можно показать, что если одна из этих величин равна нулю, то и другая должна равняться нулю. Однако из малости одной не следует малость другой. При з = 0 обычно г = О, но обратное утверждение справедливо не всегда.
В частности, для плохо обусловленных систем при г = 0 погрепгность решения может быть большой. , Вместе с тем в практических расчетах, если система не является плохо обусловленной, контроль точности решения осуществляется с помощью невязки. Можно отметить, что метод Гаусса с выбором главного элемента в этих случаях дает малые невязки. 3. Определитель и обратная матрица. Ранее уже отмечалось, что непосредственное нахождение определителя требует большого обьема вычислений. Вместе с тем легко вычисляется определитель треугольной матрицы: оп равен произведению ее диагональных элементов.
Для приведения матрицы к треугольному виду может быть использован иотод исключекия, т. е. прямой ход метода Гаусса. В процессе исключения элементов величина определителя но меняется, Знак определителя меняется на противоположный при перестановке его столбцов или строк. Следовательпо, значение определителя после приведения матрицы А к треугольному виду вычисляется по формуле йе$ А = -(- Ц аи. Здесь диагональные элементы а„берутся из преобразованной (а не исходной) матрицы. Знак зависит от того, четной или нечетной была суммарная перестановка строк (или столбцов) матрицы при ее приведении к треугольному виду (для получения ненулевого или максимального по модулю ведущего элемента на каждом этапе исключения).
Благодаря методу исключения можно вычислять определители 100-го и большего порядков, и объем вычислений значительно меньший, чем в проведенных ранее оценках, 9 л, и. турчаи 1ЗО гл. т. системы линеЙных уРАВнении а„э„+ а„г„+... + а,„г„; = О, ° ° а ° г ° ° ° * ° ° а аль„+а;,~2,+... + а;„2„, = 1, Э Э ° Ф ° ° Э ° ° ° Р Ф ап,й„+ а„,г„+... + а„„2„= О.
(4,16) Следовательно, для обращенття матрицы нужно и раз решить систему уравнений приведенного вида при т =— = 1, 2, ..., и. Поскольку матрица системы не меняется, то исключение неизвестных при использовании метода Гаусса (прямой ход) проводится только один раз. Для каждой системы делается только обратный ход после некоторых преобразований с использованием правых частей систем вида (4Л6) .
Оценки показывают, что это весьма экономичный способ обращения матрицы. Он требует примерно лишь в три раза больше действий, чем при решении одной системы уравнений, 4. Метод прогонки. Оп является модификацией метода Гаусса для частного случая разреткенных систем— системы уравнений с трехдиагопальной матрпцей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для дифференциальных уравнений. Запишем систему уравнений в виде Ь,х, + с,х~ а,х, + Кх, + с,х, а,х, + Ь,х, + с,х, А1 т7„ т~з~ (4.17)' ~~п — 1ф А.
Ъ 1 е ° . ° ° ° ап, 1~п а ~ Ьп 1~п 1 + сп 1хп -'- Ь а„х т + Ь х Теперь найдем обратную матрицу Л '. Обозначим ее элементы через г». Запишем равенство АА ' = Е в виде Х и ~1 У а1пгд,— — бцт б;,=1 .. т',т=1,2, ...,и. (4.15) Отсюда следует, что для нахождения элементов одного столбца обратной матрицы необходимо решить линейную систему (4.15) с матрицей Л. Например, элементы т-го столбца х1ь г„, ..., ы„, могут быть найдены в результате решения системы уравнений Ф 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
