Лаб9_отчёт

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра ИС

отчет

по лабораторной работе №9

по дисциплине «Конструирование программ»

Тема: Решение систем линейных алгебраических уравнений методом простых итераций

Студент гр. 9373		Заболотников М.Е.
Преподаватель		Копыльцов А.В.

Санкт-Петербург

2021

Цель работы.

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

Основные теоретические положения.

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

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

Пусть дана система - квадратная невырожденная матрица. Преобразуем ее к виду (5.5.1)

где - квадратная матрица такой же размерности что и , - вектор -столбец. В развернутой форме записи система (5.5.1) имеет вид

(5.5.2)

Операция приведения системы к виду (5.5.2) не является очевидной и простой и требует специальных знаний, а также существенного использования специфики системы. Самый простой способ приведения системы к виду (5.5.2) состоит в последовательном исключении из первого уравнения системы переменной , из второго уравнения - переменной и так далее. Метод итерации в такой реализации называется методом Якоби^. Система уравнений метода Якоби имеет вид

(5.5.3)

На главной диагонали матрицы системы (5.5.3) стоят нули, а остальные элементы, очевидно, выражаются по формулам

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

(5.5.4)

В развернутой форме записи система (5.5.4) выглядит таким образом:

(5.5.5)

5.6. Сходимость метода простых итераций

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

(5.6.1)

Доказательство

Пусть в (5.5.5) тогда Если - точное решение системы, то оно удовлетворяет уравнению (5.5.1), то есть . Вычтем два последних уравнения друг из друга. Получим Найдем норму этого выражения: , так как неравенство верно для всех индексов от 0 до .

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

Теорема 5.5. (Апостериорная оценка погрешности решения).

Если , то справедлива следующая оценка:

(5.6.2)

Доказательство

В предыдущей теореме имели равенство Преобразуем его алгебраически: . Тогда Отсюда легко получаем

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

Экспериментальные результаты.

Экспериментальные данные были взяты из методических указаний и представлены в виде таблицы на рисунке 1:

Рис. 1. Экспериментальные данные.

Обработка результатов эксперимента.

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

Рис. 2. Иллюстрация результата работы программы.

Выводы.

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

 Карл Густав Якоб Якоби (1804-1851 ) - немецкий математик.

5