Метод простой итерации для решения систем линейных алгебраических уравнений (стр. 2 из 4)
Вспомогательный модуль x_ok.m содержит столбец точного решения исходной системы линейных алгебраических уравнений вида Ax=b.
Замечание: модули system_a.m, system_b.m, x0.m всегда описывает сам пользователь, работающий с данным программным обеспечением, в зависимости от решаемой системы линейных алгебраических уравнений.
Модуль x_ok.m также может быть описан пользователем, но он не является обязательным, так как точного решения обычно у пользователя нет. Отсутствие данного модуля не влияет на правильность работы программы, он является вспомогательным и необходим лишь для оценки погрешности полученного решения (как этого требует задание), но что обычно не нужно в прикладном использовании данного программного обеспечения.
3.3 Вызов и загрузка программы
Для вызова программы на выполнение необходимо загрузить программу MatLab 3.5f (и выше), затем в командной строке данной среды набрать имя одного из программных модулей (metod1.m или metod2.m).
3.4 Входные данные
1. system_а - матрица А исходной системы линейных алгебраических уравнений вида Ax=b, считывающаяся из модуля system_а.m;
2. system_b - столбец b исходной системы линейных алгебраических уравнений вида Ax=b, считывающийся из модуля system_b.m;
3. x0 - столбец начальных приближений, считывающийся из модуля x0.m;
4. x_ok - столбец точного решения исходной системы линейных алгебраических уравнений вида Ax=b, считывающийся из модуля x_ok.m.
Замечание: если отсутствует модуль x_ok.m, то переменная x_ok не передается в основные программные модули.
3.5 Выходные данные
Выходными данными программных модулей metod1.m и metod2.m является файл total - файл-отчет, содержащий результаты одного или нескольких итерационных процессов, а именно: полученные решения, погрешности полученного решения, скорость сходимости метода, время счета, число операций.
3.6 Описание алгоритмов
3.6.1 Программный модуль metod1.m
Исходный текст модуля metod1.m представлен в Приложении1.
Сначала производится инициализация переменных result (решение системы линейных алгебраических уравнений), temp (промежуточные значения решения системы линейных алгебраических уравнений на каждом шаге итерации), size_system (размерность системы), flag (флаг для остановки итерационного процесса), edop1 (абсолютное значение k-го и (k+1)-го решения), number_iter (количество итераций), time (время счета), number_oper (количество операций), a (матрица А системы Ax=b), b (столбец b системы Ax=b). После этого на дисплей выводится запрос допустимой погрешности. Когда погрешность введена, происходит очистка экрана, обнуление встроенного в MatLab счетчика операций с плавающей точкой, запоминание текущего момента времени.
Далее после этих приготовлений запускается цикл перехода от системы вида F(x)=xк системе вида x=
(x) первым способом (см. п.2.2.) и решения системы линейных алгебраических уравнений методом простой итерации. Блок-схема цикла представлена на рис.1.Как только заканчивается цикл итераций, происходит повторное запоминание текущего момента времени и количества операций с плавающей точкой. По окончании данных действий происходит подсчет времени счета, как разности ранее запомненных моментов времени. Далее происходит запись полученного решения в файл total.
Далее производится проверка, существует ли файл x_ok.m. Если таковой имеется, то высчитывается погрешность полученного решения и записывается в файл total.
После вышеописанных действий происходит последняя запись в файл total сведений о количестве шагов, необходимых для сходимости метода, времени счета, числе операций.
Затем происходит подготовка масштаба будущего графика итерационного процесса и непосредственно его построение, после которого выполнение программы прерывается до нажатия любой клавиши.
И наконец, когда какая-либо клавиша будет нажата, произойдет очистка экрана и построение графиков зависимости погрешности от шага итерации.
3.6.2 Программный модуль metod2.m
Исходный текст модуля metod2.m представлен в Приложении1.
Алгоритм данного программного модуля аналогичен алгоритму модуля metod1.m. Единственное отличие - реализация цикла перехода от системы вида F(x)=xк системе вида x=
(x) (см. п.2.2.) и решения системы линейных алгебраических уравнений методом простой итерации. Блок-схема цикла представлена на рис.2.
3.7 Используемые программные и технические средства
Все модули данного программного обеспечения написаны на языке MatLab в редакторе NortonEditor из комплекса утилит NortonUtilities 8.0.
Для правильной работы программ metod1 и metod2 необходима операционная система MSDOS (любой версии) или операционная система Windows95, программа MatLab 3.5f (или выше), а также персональный компьютер, совместимый с IBMPC 386SX (или выше).
4. Описание тестовых задач
В качестве тестовых задач рассмотрим две системы линейных алгебраических уравнений:
Cистема1
1,02x1 - 0,25x2 - 0,30 x3 =0,515-0,41x1 + 1,13x2 - 0,15x3 =1,555 (4.1)
-0,25x1 - 0,14x2 + 1,21x3 =2,780
Точное решение: x1 =2,0 ; x2 =2,5 ; x3 =3,0 .
В качестве начального приближения x( 0 ) возьмем два вектора: x( 0)=(1000,1000,1000); x( 0 )=(1,1,1).
Система2
0,22x1 + 0,02x2 + 0,12x3 + 0,13x4 = -30,02x1 + 0,14x2 + 0,04x3 - 0,06x4 = 14
0,12x1 + 0,04x2 + 0,28x3 + 0,08x4 = 250 (4.2)
0,14x1 - 0,06x2 + 0,08x3 + 0,26x4 = -77
Точного решения нет.
В качестве начального приближения x( 0 ) возьмем два вектора: x( 0)=(0,10,20,30); x( 0 )=(-270,-503,1260,-653 ).
Все вычисления будем проводить при заданной точности
=0.001 .5. Анализ результатов счета, выводы
Результаты вычислений тестовых систем линейных алгебраических уравнений представлены в виде файлов-отчетов, которые приведены в Приложении2, а также в виде графиков итерационных процессов и графиков зависимостей погрешностей решений исходных систем линейных алгебраических уравнений от шага итерации, которые приведены в Приложении3.
Анализируя эти результаты, можно сделать следующие выводы.
Во-первых, количество итераций сильно зависит от матрицы А исходной системы уравнений вида Ax=b. Чем ближе диагональные элементы матрицы А к нулю, тем больше итераций требуется для того, чтобы решить исходную систему линейных алгебраических уравнений.
Во-вторых, на количество шагов влияет начальное приближение. Чем оно ближе к точному решению, тем меньше требуется шагов для сходимости метода. Следует отметить, что в рассматриваемых примерах достаточно точное начальное приближение требует количества итераций приблизительно в 1,7-2,0 раза меньше, чем произвольное, достаточно далеко отстоящее от точного решения, приближение.
В-третьих, скорость сходимости метода зависит от того, каким способом реализован переход от системы вида F(x)=xк системе вида x=
(x).Анализ счета показывает, что если диагональные элементы матрицы А не близки к нулю, то при любом приближении (достаточно точном и не очень) количество шагов, требующихся для сходимости метода, практически не зависит от способа перехода от системы вида F(x)=xк системе вида x=
(x). А если элементы диагонали матрицы A близки к нулю и приближение недостаточно точное, то метод сходится быстрее, если в нем реализован первый способ перехода от системы вида F(x)=xк системе вида x= (x) (см. п.2.2.).Число операций для решения исходной системы линейных алгебраических уравнений при использовании первого способа перехода требуется несколько меньше, чем для решения исходной системы линейных алгебраических уравнений при использовании второго способа перехода. Это удалось выяснить при решении системы
(4.1) при приближении x( 0 )=(1,1,1), так как в этом случае для обоих способов потребовалось одинаковое количество шагов для сходимости и одинаковое время счета, но различное число операций с плавающей точкой.
Время счета, как видно из результатов решения систем (4.1) и (4.2) линейно зависит от количества шагов и числа операций. Чем показатели последних выше, тем больше время счета.
Наконец, погрешности полученных решений, как видно из файла-отчета, не превышает заданную погрешность
.Исходя из тестовых систем линейных алгебраических уравнений и результатов их решения, можно сделать следующие выводы.
Метод простой итерации (при любом способе перехода от системы вида F(x)=xк системе вида x=
(x) ) сходится быстро, если диагональные элементы матрицы А системы Ax=b близки к единице, а остальные - близки к нулю, и приближение достаточно близко к точному решению. Но при решении систем Ax=b с матрицей А, отличной от вышеописанной, метод сходится при первом способе перехода более быстро в случае, если начальное приближение далеко отстоит от точного решения, а если приближение достаточно близко лежит к точному решению, то при втором способе перехода метод сходится несколько быстрее, чем при первом.