 |
Метод Гаусса с выбором главного элемента
|
|
|
|
Основное накопление погрешностей решения в методе Гаусса происходит на этапе приведения системы к треугольному виду. Механизм накопления основной части этой погрешности заключается в привнесении погрешностей вычисления коэффициентов ведущего уравнения в коэффициенты последующих уравнений при исключении каждого очередного неизвестного. Анализ соотношений метода Гаусса показывает, что погрешности вычисления коэффициентов ведущего уравнения привносятся в соответствующие коэффициенты всех последующих уравнений в долях отношений этих коэффициентов к диагональному (главному) коэффициенту ведущего уравнения. В связи с этим привносимая погрешность будет тем меньше, чем меньше доли этих отношений. Поэтому в методе Гаусса с выбором главного элемента на каждом шаге исключения i -го неизвестного в качестве ведущего используетсяуравнение (с i -го по n -ое), содержащее максимальный по модулю коэффициент – главныйэлемент. При этом в качестве него может использоваться один из коэффициентов i -го столбца, i -ой строки или всей непреобразованной части матрицы. Первый подход называется выбором главного элементапостолбцу, второй – по строке, а третий – по всейматрице. При использовании двух последних происходит перестановка столбцов матрицы системы. Это приводит к изменению порядка следования компонент вектора неизвестных и требует его восстановления по окончании процесса решения.
В качестве примера применения метода Гаусса можно рассмотреть задачу отыскания решения следующей системы уравнений
при ограничении разрядной сетки вычислений до трёх знаков и с оценкой погрешности получаемого решения.
Поставленная задача будет решаться методом Гаусса с выбором главного элемента по столбцу.
|
|
|
1. Прямой ход.
а. Выбор главного элемента среди элементов первого столбца
.
б. Нормировка первого уравнения
.
в. Исключение элементов первого столбца
.
г. Выбор главного элемента среди элементов второго столбца второго и третьего уравнений
.
д. Нормировка второго уравнения
.
е. Исключение элементов второго столбца
.
ё. Нормировка последнего уравнения
.
2. Обратный ход
,
.
В итоге получено решение системы уравнений
.
3. Погрешность найденного решения.
а. Пересчёт вектора правых частей системы
б. Формирование системы уравнений, определяющей погрешности решения
,
то есть
в. Решение системы относительно погрешностей оно выполняется аналогично пунктам 1 и 2. Прямой ход (пункт 1) даёт следующую систему с верхней треугольной матрицей
,
а обратный ход позволяет получить решение
.
г. Оценка абсолютной и относительной погрешностей решения системы линейных алгебраических уравнений
,
,
.
Реализация описанного метода без нахождения погрешности решения в рамках программы Excel приведена на рис.1.
Рис.1.
Итерационные методы. К этим методам относятся метод простых итераций, метод Зейделя и ряд других. Методы этой группы обладают высокой эффективностью, но их применение связано с рядом ограничений, накладываемых на свойства матрицы A.
Метод простых итераций
Метод основывается на приведении исходной системы 
к форме 
, где D – квадратная матрица, полученная из матрицы A, а p – вектор-столбец, полученный из b. Это преобразованиеможет быть выполнено многими способами. Например, путем разрешения i -го уравнения относительно i -го неизвестного:
при этом элементы матрицы D и вектора p
будут вычисляться следующим образом
.
Далее процесс уточнения корня строится по итерационной схеме
,
,
………………
,
……………….
|
|
|
где x 0 – начальное приближение вектора решения системы. То есть
,
и так далее.
Если последовательность векторов x k (k = 0,1,...) имеет конечный предел (тоже вектор), то итерационный процесс сходится к точному решению системы x т за бесконечно большое число шагов. Абсолютная и относительная погрешности найденного вектора решения системы уравнений на k -ом шаге (x k) могут быть получены из выражений
, 
,
где в качестве нормы матрицы D можно использовать любое из трёх соотношений
, 
, 
.
Кроме приведённого выражения для абсолютной погрешности существуют другие формы её записи
, 
.
Формулы для вычисления погрешности вектора решения системы линейных алгебраических уравнений требуют нахождения нормы матрицы системы, поэтому на практике часто итерации завершают при выполнении одного из условий
или 
,
где δ абс и δ отн – задаваемые абсолютная и относительная разницы между соседними приближениями вектора решения, соответственно. В этом случае надо помнить, что истинная погрешность определения решения может заметно отличаться от δ абс или δ отн. Поэтому после завершения поиска решения необходимо вычислить истинное значение его погрешности по приведённым выше формулам для ε абс или ε отн.
Встречаются ситуации, когда последовательность вычисляемых векторов x k (k = 0,1,2,...) не имеет предела. В этом случае метод расходится, и описанная итерационная схема не может быть применена для решения системы уравнений. Для того, чтобы последовательностьвекторов x k (k = 0,1,2,...) при любом начальном векторе x 0 сходилась к точному решению системы, надо выбрать матрицу D так, чтобы её норма 
была меньше единицы.
Если описанный выше приём формирования итерационной схемы не позволяет получить матрицу D, которая подчиняется условию сходимости, а матрица А – симметрична и положительно определена, то можно поступить следующим образом. Исходная система линейных алгебраических уравнений
приводится к эквивалентному виду
путем переноса произведения Ax в правую часть уравнения, умножения обеих частей уравнения на константу l и добавления к ним вектора x. В результате этого преобразования получается итерационная схема
,
где
.
Здесь под матрицей E понимается единичная матрица, а параметр lk может вычисляться с использованием выражения
|
|
|
,
где
, 
, 
.
Подбирая таким способом коэффициент λk на каждом шаге процесса итераций, удается получить матрицы D k, подчиняющиеся условию сходимости. Описанный приём называется методом простых итераций с релаксацией.
Если система уравнений
имеет матрицу A, которая не является симметричной и положительно определённой, то надо произвести её симметризацию. Она заключается в умножении левой и правой частей системы на транспонированную матрицу A T
,
что приводит исходную систему к системе
,
где
,
в которой матрица H симметрична и положительна определена.
Метод Зейделя (L.Seidel, 1874)
Этот метод является разновидностью метода простых итераций. Исходная система приводится к такому же виду, как и в методе простых итераций, но процесс итераций организуется иным образом. Как только на k -ой итерациивычислена i -я компонента 
вектора x k, её значение используют для вычисления последующих компонент 
, 
,..., 
этого вектора, не дожидаясь начала следующей итерации. Например
.
Вопрос о сходимости метода Зейделя, в общем виде, является открытым. Однако известно, что выполнение условия сходимости метода простых итераций гарантирует сходимость метода Зейделя. При этом благодаря особенностям итерационной схемы, метод Зейделя позволяет за то же количество шагов, что и метод простых итераций, получать более точный результат.
Если при решении системы уравнений методом Зейделя итерационный процесс расходится, то могут использоваться описанные выше приемы с релаксацией и симметризацией системы уравнений.
В качестве примера применения метода Зейделя можно рассмотреть задачу поиска решения следующей системы уравнений
с относительной разницей между соседними приближениями вектора решения не более 0.01 и с оценкой его погрешности.
Следуя алгоритму метода Зейделя, требуется преобразовать исходную систему уравнений к виду
,
где
,
и выполнить её проверку на сходимость
Так как условие сходимости выполняется, то итерационный процесс может быть начат с любого удобного значения вектора x. В качестве начального приближения обычно принимается нулевой вектор
|
|
|
.
Первая итерация
Вторая итерация
Третья итерация
Четвёртая и пятая итерации дают соответственно
, 
,
, 
.
Определение погрешности решения по последней итерации
,
.
При реализации алгоритма метода Зейделя для решения рассмотренного выше примера в программе Excel может быть применена расчётная таблица 1.
Таблица 1.
| i | x i | 
| 
| 
| ||
| 
| 
| – | – | ||
| 
| 
| 
| 
| 
| |
| …… | …… | …… | …… | ……. | ………….. |
Ниже на рис.2 представлены результаты расчётов в программе Excel по предлагаемой таблице. Для вычисления максимума из нескольких чисел здесь использована функция МАХ из числа встроенных в программу Excel статистических функций.
Рис.2.
О выборе метода решения систем уравнений
Каждый из рассмотренных методов имеет свои достоинства и недостатки. В частности, метод Гаусса позволяет получить решение за конечное число шагов. Для этого требуется выполнить n (n 2 + 3 n – 1)/3 операций умножения и деления и n (n – 1)(2 n + 5)/6 операций сложения и вычитания, количество которых при больших порядках системы (n > 100) можно принять равным n 3/3 в обоих случаях. Однако его методические ошибки, связанные с размером разрядной сетки вычислений, резко нарастают с увеличением порядка системы и не позволяют применять его для систем высоких порядков без использования специальных приёмов.
Итерационные методы позволяют получать решение систем бóльшего порядка. Для выполнения каждой итерации с их помощью необходимо выполнить n (n + 1) операций умножения и деления и столько же операций сложения и вычитания. При больших порядках системы уравнений (n > 100) их количество можно принять равным n 2. Из сравнения трудоёмкости итерационных методов и метода Гаусса следует оценка, которой можно руководствоваться при окончательном выборе метода решения системы при необходимости его многократного нахождения. Если количество итераций, требуемое для получения решения системы итерационными методами, не превышает n /3, то выгоднее применять их, а не методы типа Гаусса. Однако здесь следует помнить, что итерационные методы требуют, чтобы матрица системы обладала определёнными свойствами, обеспечивающими их сходимость. Необходимо также отметить, что выполнение этих требований часто не гарантирует высокой скорости их сходимости.
|
|
|
