Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 6
Текст из файла (страница 6)
'37. МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА 28 Эти равенства показывают, как преобразуется погрешность после шага алгоап ритма. Из соотноптений (1) вытекает, что если отношение очень велико, то ап вычислительная погрешность, вносимая на шаге алгоритма, может быть недопустимо болыпой. Из (1) следует, что погрешность будет наименыпей, если модуль отношения ап наименыпий из возможных. Это будет в том случае, если аы — наибольап ший по модулю элемент в первом столбце. Поэтому описанный выше алгоритм преобразуем к следующему виду.
Присвоим номер 1 тому уравнению, в котором коэффициент при х1 наибольший по модулю. Этот коэффициент отличен от нуля, так как противное означало бы, что матрица А имеет нулевой первый столбец, т.е. вырождена. После этой перенумерации уравнений мы сделаем первый шаг метода Гаусса,т.е.перейдем от системы (4.1) к системе (4.3). Далее в подматрице А(') = (а;, ); г „Е М„1 присвоим номер 2 тому уравнению, в котором коэффициент при хг наибольший по модулю, и сделаем следующий шаг метода Гаусса. Затем этот процесс применяется к подматрице А Е М„г и так далее. Этот алгоритм называется (г) методом Гаусса с выбором главного элемента по столбцу. Можно преобразовать метод Гаусса и по-другому. Неизвестные в системе (4.1) равноправны, мы можем их занумеровать в произвольном порядке.
Присвоим номер 1 той неизвестной, при которой коэффициент в первой строке отличен от О. Если такой неизвестной не нашлось, то матрица А имеет нулевую первую строку, т.е. вырождена. После этой перенумерации неизвестных мы сделаем первый шаг метода Гаусса, т.е. перейдем от системы (4.1) к системе (4.3). Далее в подматрице А = (а; );,,— г,„,,„е М„| присвоим номер 2 той неизвестной, (О (1) при которой коэффициент в первой строке матрицы А(') (т.е. во второй строке матрицы А) отличен от О, и сделаем следующий шаг метода Гаусса. Затем этот процесс применяется к подматрице А е М„г и так далее. (г) Если неизвестных, при которых коэффициент отличен от О, несколько, то с вычислительной точки зрения не безразлично, какая из них получит номер 1. Рассуждениями, аналогичными вьппеприведенным, можно установить, что погрешность, вносимая на пгаге алгоритма, будет минимальной, если если ап — наибольший по модулю элемент в первой строке.
Поэтому описанный вьппе алгоритм преобразуем к следуюгцему виду. Присвоим номер 1 той неизвестной, при которой коэффициент в первой строке наибольший по модулю. Этот коэффициент отличен от нуля, так как противное означало бы, что матрица А имеет нулевую первую строку, т.е. вырождена. После этой перенумерации неизвестных мы сделаем первый шаг метода Гаусса, т.е. перейдем от системы (4.1) к системе (4.3). Далее в подматрице А = (а,, )ьг г „Е М„1 присвоим номер 2 той неизвестной, при которой (О ()) коэффициент в первой строке матрицы А(') (т.е.
во второй строке матрицы А) наибольший по модулю, и сделаем следующий шаг метода Гаусса. Затем этот процесс применяется к подматрице А Е М„г и так далее. Этот алгоритм (г) К.Ю.Богачев Точные методы решения линейных систем '37.
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА называется метподом Гаусса с выбором главного элемента по строке. Для уменыпения вычислительной погрешности используют следующую комбинацию приведенных выше методов. В качестве ап выбирается элемент, имеющий наибольший модуль среди всех элементов матрицы. Если этот элемент есть а;, то меняются номера у 1-й и 1-й строк и у 1-го и у-го столбцов. После этой перенумерации уравнений и неизвестных делается первый шаг метода Гаусса, т.е. осуществляется переход от системы (4.1) к системе (4.3). Далее в подматрице А = (а; );, г „Е М„1 выбирается элемент а; с наибольшим модулем (О (~) среди всех элементов матрицы А~О и меняются номера у 1-й и 1-й строк и у 1-го и у-го столбцов матрицы А~О (т.е.
у 2-й и 1-й строк и у 2-го и у-го столбцов матрицы А ). Затем этот процесс применяется к подматрице А~~~ е М„г и так далее. Этот алгоритм называется методом Гаусса с выбором главного элемента по всей матрице. Вычислим дополнительные (по сравнению с обычным методом Гаусса) затраты вычислительной работы на решение системы по этим алгоритмам. На й-ом шаге (й = 1,..., и) метода Гаусса с выбором главного элемента по столбцу или строке требуется п — й операций сравнения элементов матрицы А для нахождения максимального по модулю элемента. В методе Гаусса с выбором главного элемента по всей матрипе это число равно (п — к)г. Следовательно, в первых двух методах дополнительно требуется ~и~,(п — й) = п(п — 1)/2 = 0(п~) (п -+ со) операций сравнения, а в последнем методе — Я,(п — Й) = (и — 1)п(2п — 1)/6 = пг/3 + 0(п ) (и -+ оо) операций сравнения. На большинстве ЭВМ операция сравнения двух чисел с плавающей точкой выполняется за время, по порядку равное времени вычитания этих чисел.
(Это связано с тем, что вместо сравнения двух чисел выполняется операция вычитания одного числа из другого и сравнения результата с нулем. Поскольку сам результат нигде не запоминается и от него используется лишь его знак, то операция сравнения обычно осуществляется быстрее операции вычитания, однако следующая за операцией сравнения команда условного перехода с лихвой компенсирует эту разнипу.) Поэтому в методе Гаусса с выбором главного элемента по столбпу или строке количество операций асимптотически то же, что в обычном методе Гаусса: 2/3 па+0(пг). В методе Гаусса с выбором главного элемента по всей матрице количество операций асимптотически в полтора раза больше, чем в обычном методе Гаусса: пг + 0(пг). По этой причине этот метод обычно применяется тогда, когда с помощью других методов не удалось получить приемлемого по точности результата из-за сильного роста вычислительной погрешности (такая ситуация возникает, если матрица А имеет большое число обусловленности).
Теорема 1. Метод Гаусса с выбором главного элемента по столбцу осуи1ествим тогда и только тогда, когда г1е1А ~ О. Доказательство. Шаг метода Гаусса переводит невырожденную матрицу К.Ю.Богачев Точные методы решения линейных систем ~7. МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА 30 в невырожденную. Действительно, после перехода от матрицы (4.4) к матрице (4.7) по формулам (4.6), (4.8) определитель матрицы (4.4) равен определителю матрицы (4.7), умноженному на а„г (множитель возникает при вычислении (ь-О по формулам (4.6), при преобразовании матрицы по формулам (4.8) определитель не изменяется, так как они задают элементарные преобразования матрицы).
Согласно правилам вычисления определителей, определитель матрицы (4.4), получающейся после Й вЂ” 1 шагов метода Гаусса, равен определителю матрицы А = (а;, );„г „. Следовательно, невырожденность матрицы А эквива(ь О (г-О лентна невырожденности матриц А(г) для всех Й = 1,..., и .
Очередной, й-й шаг метода Гаусса с выбором главного элемента по столбцу возможен тогда и только тогда, когда первый столбец матрицы А(г ') ненулевой, т.е. эта матрица невырождена (см. подробное обоснование этого при построении метода). Таким образом, осуществимость всех и шагов метода Гаусса эквивалентна невырожденности матриц А(") для всех /с = 1,..., и, что эквивалентно невырожденности матрицы А. Теорема 2. Метод Гаусса с выбором главного элеывнта по строке осуществим тогда и только псогда, когда с(е1А ф О. Доказательство повторяет доказательство предыдущей теоремы. Изменения только в том, что очередной, й-й шаг метода Гаусса с выбором главного элемента по строке возможен тогда и только тогда, когда первая строка матрицы А(" О ненулевая, т.е.
эта матрица невырождена (см. подробное обоснование этого при построении метода). Теорема 3. Метод Гаусса с выбором главного элемента по всей матрице осуществим тогда и только тогда, когда с1е1 А ~ О. Доказательство повторяет доказательство теоремы 1. Изменения только в том, что очередной, й-и шаг метода Гаусса с выбором главного элемента по всей матрице возможен тогда и только тогда, матрица А~~ О ненулевая (см. подробное обоснование этого при построении метода). Замечание 1. Программная реализация методов Гаусса с выбором главного элемента. При реализации этих методов можно переставлть не строки или столбцы матрицы, а их номера. Сделать это можно, например, следующим способом.
Рассмотрим метод Гаусса с выбором главного элемента по всей матрице. Пусть массив 1п61 длиной п содержит номер строки матрицы А, массив (пав)' длиной и содержит номер столбца матрицы А. Вначале 1пс11(1)=1, (пав)'())=), 1,) = 1,..., и. Обращение к элементам матрицы А происходит следующим образом: элемент вн есть а(1п61(1), 1пб)' (1) ) . Для того, чтобы переставить местами К.Ю.Богачев Точные методы решения линейных систем ~8. МЕТОД ЖОРДАНА (ГАУССА-ЖОГДАНА) г1-ю и гя-ю строки матрицы А, достаточно переставить местами г1-й и гя-й элементы массива 1по1; для того, чтобы переставить местами )1-й и )2-й столбцы матрицы А, достаточно переставить местами )1 -й и )2-й элементы массива 1жЦ.
Существенным недостатком такого способа реализации перестановок строк и столбцов является замедление доступа к элементам массива. Замечание 2. Для матриц А произвольного вида методы Гаусса с выбором главного элемента практически вытеснили обычный метод Гаусса из вычислительной практики. Совершенно иная ситуация для случая ленточных матриц А. Дело здесь в том, что перестановка строк или столбцов в таких матрицах приводит к увеличению ширины ленты, что часто недопустимо (поскольку вместо матрицы хранится только ее лента).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
