Варианты заданий

Вариант	Система линейных уравнений	Вариант	Система линейных уравнений
1		9
2		10
3		11
4		12
5		13
6		14
7		15
8

Лабораторная работа №9

Итерационные методы решения задач линейной алгебры. Метод Гаусса-Зейделя.

Цель работы: научится применять итерационные методы и метод Гаусса.

Итерационные методы

Системы линейных алгебраических уравнений можно решать как с помощью прямых, так и итерационных методов. Для систем уравнений средней размерности чаще используют прямые методы.

Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций. Большие системы уравнений, возникающие в основном в приложениях, как правило являются разреженными. Методы исключения для систем с разреженным и матрицами неудобны, например, тем, что при их использовании большое число нулевых элементов превращается в ненулевые и матрица теряет свойство разреженности. В противоположность им при использовании итерационных методов в ходе итерационного процесса матрица не меняется, и она, естественно, остается разреженной. Большая эффективность итерационных методов по сравнению с прямыми методами тесно связанна с возможностью существенного использования разреженности матриц.

Применение итерационных методов для качественного решения большой системы уравнений требует серьезного использования ее структуры, специальных знаний и определенного опыта.

Уточнение решения. Решения, получаемые с помощью прямых методов, обычно содержат погрешности, вызванные округлениями при выполнении операций над числами с плавающей точкой на компьютере с ограниченным числом разрядов. В ряде случаев эти погрешности могут быть значительными, и необходимо найти способ их уменьшения. Рассмотрим здесь один из методов, позволяющий уточнить решение, полученное с помощью прямого метода.

9.1

Найдем решение системы линейных уравнений

Пусть с помощью некоторого прямого метода вычислено приближенное решение (тобто приближенные значения неизвестных , называемое начальным или нулевым приближением к решению. Подставляя это решение в левую часть системы (9.1), получаем некоторый столбец правых частей , отличный от :

9.2

9.3

Введем обозначения: - погрешность полученного решения, - невязка, тобто

9.4

Вычитая равенство(9.2) из равенства (9.1), с учетом обозначений (9.3) получаем

Решая эту систему, находим значение погрешности , которое используем в качестве поправки к приближенному решению , вычисляя таким образом новое приближенное решение (или следующее приближение к решению):

Таким же способом можно найти новую поправку к решению и следующее приближение и т.д. Процесс продолжается до тех пор, пока очередное значение погрешности (поправки) не станет достаточно малым, тобто пока очередные приближенные значения неизвестных не будут мало отличатся от предыдущих значений .

Рассмотренный процесс уточнения решения представляет собой фактически итерационный метод решения системы линейных уравнении. При этом заметим, что для нахождения очередного приближения, тобто на каждой итерации, решаются системы уравнений вида (9.4) с одной и той же матрицей, являющейся матрицей исходной системы (9.1), при разных правых частях. Это позволяет строить экономичные алгоритмы. Например, при использовании метода Гаусса сокращается объем вычислений на этапе прямого хода.

Решение систем линейных уравнений с помощью рассмотренного метода (а также решение систем линейных уравнений иным итерационными методами, решение итерационными методами уравнений другого вида и их систем) сводится к следующему (рис. 9.1).

Рис. 9.1. Решение системы уравнений методом итераций

Вводятся исходные данные, например, коэффициенты уравнений и допустимое значение погрешности. Необходимо также задать начальные приближения значений неизвестных (вектор-столбец .

Они либо вводятся в компьютер, либо вычисляются каким – либо способом (в частности, путем решения системы уравнений с помощью прямого метода). Затем организуется циклический вычислительный процесс, каждый цикл которого представляет собой одну итерацию – переход от предыдущего приближения к последующему .

Если оказывается, что с увеличением числа итераций приближенное решение стремится к точному:

то итерационный метод называют сходящимся.

На практике наличие сходимости и достижение требуемой точности обычно определяют приближенно, поступая следующим образом. При малом (с заданной допустимой погрешностью) изменении на двух последовательных итерациях, тобто при малом отличии от , процесс прекращается, и происходит вывод значений неизвестных, полученных на последней итерации.

Возможны разные подходы к определению малости отличия на двух последовательных итерациях. Например, если задана допустимая погрешность , то критерием окончания итерационного процесса можно считать выполнение одного из трех неравенств:

9.5

9.6

9.7

9.8

Здесь в первом случае отличие векторов и понимается в смысле малости модуля их разности, во втором – в смысле малости разностей всех соответствующих компонент векторов, в третьем – в смысле малости относительных разностей компонент. Если система не является плохо обусловленной, то в качестве критерия окончания итерационного процесса можно использовать и условие малости невязки, например

Заметим, что в рассмотренном алгоритме не предусмотрен случай отсутствия сходимости. Для предотвращения непроизводительных затрат машинного времени в алгоритм вводят счетчик числа итераций и при достижении им некоторого заданного значения счет прекращают. Такой элемент будет в дальнейшем введен в структурограмму.

Метод простой итерации. Этот метод широко используется для численного решения уравнений и их систем различных видов. Рассмотрим применение метода простой итерации к решению систем линейных уравнений.

Запишем систему уравнений в векторно-матричном виде и выполним ряд тождественных преобразований:

(9.9)

где – некоторое число, - единичная матрица, . Получившаяся система (9.9) эквивалентна исходной системе и служит основой для построения метода простой итерации.

Выберем некоторое начальное приближение и подставим его в правую часть системы (9.9):

П

9.10

оскольку не является решением системы, в левой части (9.9) получится некоторый столбец , в общем случае отличный от . Полученный столбец будем рассматривать в качестве следующего (первого) приближения к решению. Аналогично, по известному -му приближению можно найти -е приближение:

Формула (9.10) и выражает собой метод простой итерации. Для ее применения нужно задать неопределенный пока параметр . От значения зависит, будет ли сходится метод, а если будет, то какова будет скорость сходимости, тобто как много итераций нужно совершить для достижения требуемой точности. В частности, справедлива следующая теорема.

ТЕОРЕМА. Пусть . Метод простой итерации (9.10) сходится тогда и только тогда, когда все собственные числа матрицы по модулю меньше единицы.

Для некоторых типов матрицы можно указать правило выбора , обеспечивающее сходимость метода и оптимальную скорость сходимости. В простейшем же случае можно положить равным некоторому постоянному числу, например, 1, 0.1 и т.д.

Метод Гаусса-Зейделя. Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является метод Гаусса-Зейделя.

Проиллюстрируем сначала этот метод на примере решения системы

9.11

Предположим, что диагональные элементы отличны от нуля (в противном случае можно переставить уравнения). Выразим неизвестные соответственно из первого, второго и третьего уравнений системы (9.11):

9.12

9.13

9.14

Зададим некоторые начальные (нулевые) приближения значений неизвестных: . Подставляя эти значения в правую часть выражения 9.12, получаем новое (первое) приближение для :

Используя это значение для и приближение для , находим из (9.13) первое приближение для :

И наконец, используя вычисленные значения , находим с помощью выражения 9.14 первое приближение для :

На этом заканчивается первая итерация решения системы (9.12) – (9.14). Используя теперь значения , можно таким же способом провести вторую итерацию, в результате которой будут найдены вторые приближения к решению: и т.д.

Приближение с номером можно вычислить, зная приближение с номером , как

Итерационный процесс продолжается до тех пор, пока значения не станут близкими с заданной погрешностью к значениям

Пример. Решить с помощью метода Гаусса-Зейделя следующую систему уравнений:

Легко проверить, что решение данной системы следующее:

Решение. Выразим неизвестные соответственно из первого, второго и третьего уравнений:

В качестве начального приближения (как это обычно делается) примем Найдем новые приближения неизвестных:

Аналогично вычислим следующие приближения:

Итерационный процесс можно продолжать до получения малой разности между значениями неизвестных в двух последовательных итерациях.

Рассмотрим теперь систему линейных уравнений с неизвестными. Запишем ее в виде

Здесь также будем, предполагать, что все диагональные элементы отличны от нуля. Тогда в соответствии с методом Гаусса-Зейделя -е приближение к решению можно представить в виде

9.15

Итерационный процесс продолжается до тех пор, пока все значения не станут близкими к , тобто в качестве критерия завершения итераций используется одно из условий (9.5)-(9.7), (9.8).

9.16

Для сходимости итерационного процесса (9.15) достаточно, чтобы модули диагональных коэффициентов для каждого уравнения системы были не меньше сумм модулей всех остальных коэффициентов (преобладание диагональных элементов):

При этом хотя бы для одного уравнения неравенство должно выполнятся строго. Эти условия являются достаточными для сходимости метода, но они не являются необходимыми, тобто для некоторых систем итерации сходятся и при нарушении условий (9.16).

Алгоритм решения системы линейных уравнений методом Гаусса-Зейделя представлен на рис.9.2. В качестве исходных данных вводятся , коэффициенты и правые части уравнений системы, погрешность , максимально допустимое число итераций , а также начальные приближения переменных . Отметим, что начальные приближения можно не вводить в компьютер, а полагать их равными некоторым значениям (например, нулю). Критерием завершения итераций выбрано условие (9.6), в котором через обозначена максимальная абсолютная величина разности и :

Рис. 9.2. Метод Гаусса – Зейделя

Для удобства чтения структурограммы объясним другие обозначения: - порядковый номер итерации; - номер уравнения, а также переменного, которое вычисляется в соответствующем цикле; - номер члена вида или в правой части соотношения (9.15). Итерационный процесс прекращается либо при , либо при . В последнем случае итерации не сходятся, о чем выдается сообщение. Для завершения цикла, реализующего итерационный процесс, используется переменная , которая принимает значения 0,1 и 2 соответственно при продолжении итераций, при выполнении условия и при выполнении условия .

Контрольные вопросы:

1. Какие вы знаете итерационные методы решения задач линейной алгебры?

2. Для чего используется метод простой итерации?

3. Какие преимущества метода Гаусс – Зейделя?