III Канатников А.Н., Крищенко А.П. Аналитическая геометрия (2 изд. 2000) (1081377), страница 37
Текст из файла (страница 37)
Запишем расширенную иап!рацу системы ь, Ьг 6з ам апг а1З " а1 ° ащ агг агз ... аг„ ПЗ! Пэг ОЗЗ " ПЗв 1А!ь) = а,д а„г а з ... п„„6„ На первом шаге делим 1-ю строку расширенной матрицы на ее 1-й элемепп! аы и полУчаем новУю стРокУ (1, а!12, а!12,..., а1„, 6!). Верхние индексы в коэффициентах аьЧ и ЬЬ указывают на то, что соответствующий элемент расширенной матрицы СЛАУ был пересчитан на Ь-м шаге метода Гаусса. Затем из каждой последующей 1-й строки вычитаем 1-ю, умноженную на коэффициент аи. В результате получаем матрицу 0 а„г а„з ...
а„„ ! 1 1 Ь„' На втором шаге делим 2-ю строку на ее диаеоналъныб элемепо! а1 и получаем новую 2-ю строку 10, 1, аггз, ..., агг„, 622) расширенной матрицы. Затем из каждой последующей 1-й строки (! = 3,...,и) вычитаем полученную строку с коэффициентом а! из 2-го столбца. В результате получаем матрицу 62 Ьз 0 0 пг ... аг„Ь2 О!г Е1З " П! 1 ! 1 1 1 1 0 пгг агз ...
аз„ ОЗ2 аЗЗ ... аэ 1 1 1 1 1 1 0 1 о22 .'' п2в 0 0 аг ... агз„ 61 Ь,' 63 275 10.а Метод Гаусса Процесс продолжаем до последней строки расширенной матрицы. На к-м шаге остается разделить последнюю строку на ее диагональный элемент а"„„1, и мы получим матрицу Е12 Е1З .. а во 1 1 1 О 1 еггз .. аг„ О О 1 ... азз Ь1 йг Ьз' О О О ... 1 йо+! 1 й"+1 2 Ьп+1 з Е12 Е13 ' ' ' Е1,о-1 1 1 1 О 1 аггз " ег, -1 О О О 1 ...
а~э„, О Ьо+! о-1 О О О О О О 1 О О 1 На 1к+ 2)-м шаге вычитаем (а- 1)-ю строку из всех предшествующих с коэффициентами из (к — 1)-го столбца. Получаем В результате выполненных преобразований приходим к СЛАУ, эквивалентной исходной. Матрица этой СЛАУ является верхкей огреугааькоб и имеет диагональные элементы, равные едннице. На этом завершается первая часть алгоритма метода Гаусса, которую называют прлмым ходом мегггодо Гаусса. Вторая часть алгоритма состоит в преобразовании верхней треугольной матрицы в едикичкую, эту часть называют обретпкым ходом метпода Гаусса.
Итак, продолжаем преобразования. На (к+ 1)-м шаге (первый шаг обратного хода) вычитаем последнюю строку из всех предшествующих с коэффициентами иэ к-го столбца. Получаем матрицу 276 2ц ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ матрицу Процесс продолжаем до 2-й строки. На последнем (2в — 1)-и шаге вычтем из 1-и строки 2-ю с соответствующвм козффициентом а~з и в результате получим расширенную матрицу вида (Е~ь'), где Ь( 1Ьзв-1 Ь2в-2 Ьл+1 р1 ( 2 ~ 2 1 '''~ ~ Ы столбец, представляющий собой искомое решение.
Последовательные шаги алгоритма могут быть сведены к серии формул (в них ае = а;, Ьо = Ь;): ° прямой ход 1-й шаг, Ь = 1,...,п — 1: а) у=2+1,...,в, Ь) 2' = 2'+1,...,П, Ьл = Ь» ~ — а~я,; ~Ь';, 1=2+1,...,п; — и-й шаг: *„= ь„"; 1 а12 а12 ... а2 „2 0 0 1 1 1 0 1 азз .. а2 2„2 0 0 0 0 1 ... азз„з 0 0 0 0 0 ... 1 0 0 0 0 0 ... 0 1 0 О О 0 ... О О 1 1-1 2 И б 2-1' ов у-1 и 2 2-1 2-! 2 оМ вЂ” -ц„-еы еб, Ь„"' Ьв в И и — Ъ~ а„,, Ьа+2 1 у+2 2 Ь+2 з Ь"+' л-1 Ь"+' л-1 Ь" а 277 10.4. Осебеянаетя метода Гвуссе ° обратный ход — 1-й шаг, 1= и+1,...,2п — 1: и *, = Ь,* — ~ а,';х,, в = 2п — е'. 1=е+1 В приведенных формулах представление процесса вычислеиня как преобразования расширенной матрицы системы теряется.
Двойной нижний индекс в буквенных обозначениях означает, что в процессе вычислений необходимо использовать двумерный массив. Верхний индекс отражает лишь шаг процесса вычисления. Отметим, что коэффициенты а'„у и 6'„, вычисляемые в процессе прямого хода метода Гаусса, при обратном ходе непосредственно используются для определения решения системы, значит, никаких преобразований расширенной матрицы при обратном ходе вообше выполнять нет необходимости.
10.4. Особенности метода Гаусса Разумеется, изложенный в 10.3 метод пригоден только в том случае, если матрица СВАУ невырождека (иначе единичная матрица в результате элементарных преобразований строк не получится). Но даже если это требование выполнено, мы можем на каком-то шаге получить нуль в качестве диагонального элемента, на который необходимо делить. Это может случиться даже на первом шаге. Пример 10.2. К системе с расширенной иатрицей мы не можем непосредственно применить изложенный алгоритм и вынуждены предпринять дополннтельные действия, например предварительно переставить на первое место 2-ю или 3-ю строку.
4 278 1О. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ В практике численных методов диагональные элементы матрицы, на которые в методе Гаусса приходится делить, называют ведущими, или еловмььми. При каких условиях ведущие элементы не обращаются в нуль7 Рассмотрим деловые миноры матрицы А системы, сосредоточенные в ее верхнем левом углу: б | — — М~, Ьз = М~ 'з, ..., ) Теорема 10.1. СЛАУ Ае = Ь может быть решена методом Гаусса тогда и только тогда, когда все угловые миноры матрицы А системы отличны от нуля. М Отметим, что элементарные преобразования прямого хода мепюда Гаусса являются также элементарными преобразованиями овределншелеб бь. В результате таких преобразований угловые миноры изменяются, но не меняются ранги соответствующих матриц. Это значит, что угловой минор и-го порядка равен нулю тогда и только тогда, когда равен нулю угловой минор того же порядка верхней шреугольноб лватврины, полученной в результате прямого хода.
Но это возможно лишь в том случае, если один из ведущих элементов равен нулю. Наоборот, если все миноры Ьь отличны от нуля, то и все ведущие элементы метода Гаусса являются ненулевыми. ь Сформулированный критерий проверить трудно, может быть, не легче, чем решить саму систему. Поэтому он интересен, скорее, с теоретической точки зрения, чем с практической. Однако в одном важном случае выполнение критерия следует из вида матрицы. Говорят, что в матрице А = (а; ) диагональные элементы преобладают, если для каждой строки с номером 1 выполняется неравенство ~а;;~ ) ~~~ )а;~~, т.е. каждый диагональный элемент по абсолютной величине превосходит сумму абсолютных величин всех остальных зле- г0.4. Особеинести метода Гаусса О= 1а;;~ > ~~! ~а;.! > О, ИФ или 0>0.
Теорема 10.2. Если в матрице А преобладают диагональные элементы, то все угловые миноры этой матрицы отличны от нуля. м Отметим, что преобладание диагональных элементов в матрице означает, что и в каждом угловом миноре диагональные элементы преобладают, Поэтому достаточно доказать, что определитель матрицы с преобладанием угловых элементов отличен от нуля. Рассмотрим определитель аы агг " а! аг! агг .. аг„ а„! а„г ...
а„„ у которого диагональные элементы преобладают. Тогда аг! ~0 и для его матрицы можно выполнить первый шаг метода Гаус- са. В результате первого шага получим определитель 1 агг а!з .. аг„ ! ! ! 0 агг агз ... аг„ ! ! ! 0 ааг азз ... аз„ ! ! ! Ь! —— 0 а„г а„з ... а„„ ! ! ! ментов своей строки. Такие матрицы называют магнриг!ами с диаеональным преобладанием. Отметим, что в матрице с диагональным преобладанпем все диагональные элементы отличны от нуля.
Действительно, если бы некоторый диагональный элемент ан матрицы равнялся нулю, то из 110.1) следовало бы неравенство 280 нь численные метОдЫ РЕШЕНИЯ СЛАУ с элементами а~~ ~ в11 а1 — —, аь — аьй — — аы, аы оы у = 2, н. Убедимся, что у нового определителя Ь1 диагональные элементы также преобладают. Для этого оценим сумму модулей всех элементов Й-й (Й ) 1) строки, кроме 1-го (он равен нулю) и Й-го (он диагональный): !аь ! = ~ !ал — — заы! < ~ !аь !+ — ~) !а,у! < (используем преобладание аы в 1-й строке) < ~) !аь1!+ — ((аы! — !а1ь!) = ~~~ )аМ!+ !аы!— !аы! !аы ! !а1ь! )аы! !аы! юМй юФй ч,, !аы!!а1ь! !аы! (используем преобладание аль в Й-й строке) !аы!!о1ь! ! аыа1ь ! < !аьл!— < ~аль — ~ = !аль!.
)аы! ~ аы При транспонировании матрицы ее угловые миноры транспонируются и потому сохраняют свое значение. Поэтому если Итак, после первого шага прямого хода метода Гаусса преобладание диагональных элементов в матрице сохранилось. Используя разложение определителя Ь1 по 1-му стполбцу, приходим к определителю (н — 1)-го порядка с преобладанием дпагональных элементов, который является минором определителя Ьм соответствующим единице в верхнем левом углу, Доказательство завершаетсл методом математической индукции по порядку определителя.
Для определителей первого порядка, т.е. чисел, утверждение теоремы очевидно. ~ 281 Шса Особекыоста метода Гаусса к системе с данной матрицей применим метод Гаусса, то он применим и к системам с транспонированной матрицей. Другими словами, метод Гаусса применим к системам, в матрицах которых диагональные элементы являются преобладающими в столбцах. Если метод Гаусса не проходит, т.е. один иэ угловых миноров обращается в нуль, то в алгоритм приходится включать дополнительные действия, например перестановку строк. С дополнительной перестановкой строк метод Гаусса можно применять к любым системам с невырожденной матрицей, и он будет давать правильное решение в предположении, что все вычнсления выполняются точно.
Однако, даже если метод Гаусса проходит без модификаций, все равно могут возникнуть неприятности. Дело в том, что паза ошибок вычислений вместо ведущих элементов, на которые предстоит делить, мы получаем лишь их некоторое приближение. Значит, вместо теоретического нуля мы можем получить число, хотя и малое, но не нуль. Тогда дальнейшие вычисления могут привести к переполнению разрядной сетки компьютера, вызванному делением большого числа на малое (зто фактически можно расценивать как деление на нуль).
Если же переполнение не произойдет, то дальнейшие вычисления не будут иметь никакого отношения к реальному решению. Конечный результат будет определяться не исходными данными, а причудливой игрой ошибок вычислений. Прпмер 10.3. Система Е 4х+ Зу = 3, 10х+ 7,51у+ 8х = — 0,49, 2х — у — х= 0 имеет решение (О, 1, -1), в чем можно убедиться непосредственной проверкой. Применим метод Гаусса, предполагая, что вычисления выполняются с точностью до четырех значащих цифр. После 282 ш.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
