МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет»
Кафедра АСОИУ
ОТЧЕТ
по лабораторной работе №2
на тему «Решение систем линейных алгебраических уравнений итерационными методами»
по дисциплине «Вычислительная математика»
Вариант №6
Выполнил:
студентка гр.Б03-782-1 Ю.С. Вотинцева
Проверил:
ст. преподаватель кафедры АСОИУ А.А. Коробейников
Ижевск 2012
1 ПОСТАНОВКА ЗАДАЧИ
Написать программу, реализующую алгоритмы:
-
метода простых итераций;
-
метода Зейделя.
с точностью = 10-12.
В программе требуется:
-
предусмотреть приведение СЛАУ к виду, пригодному для итераций;
-
организовать проверку условия сходимости методов;
-
выбрать начальное приближение;
-
сделать априорную оценку количества шагов и подсчитать реальное количество шагов для достижения заданной точности указанных методов;
-
подсчитать апостериорные оценки методов.
Провести сравнительный анализ метода простых итераций и метода Зейделя.
2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
2.1 Итерационные методы решения СЛАУ
Пусть дана система n линейных уравнений с n неизвестными:
(1)
Запишем систему (1) в матричном виде:
A x = b, (2)
Преобразуем систему (2) тем или иным способом (таких способов существует множество; некоторые из них будут рассмотрены ниже) к эквивалентной ей системе вида:
x = x + , (3)
где x – тот же вектор неизвестных, , - некоторые новые матрица и вектор соответственно.
Эта система называется приведенной к нормальному виду. Она пригодна для итерационного процесса.
2.2 Методы простых итераций (МПИ) решения СЛАУ
Пусть система линейных алгебраических уравнений (2) приведена к нормальному виду (3) тем или иным способом. Решим ее методом простых итераций. Используя систему (3), можно определить последовательность приближений x(k) к неподвижной точке x* рекуррентным равенством
x(k+1)= x(k)+, (4)
где k =0,1,2,….
Итерационный процесс (4), начинающийся с некоторого вектора
x(0) =( x ,…, x)Т, будем называть методом простых итераций (МПИ).
Приближения к решению СЛАУ методом простых итераций могут быть записаны в виде следующей системы равенств:
(5)
где k = 0,1,2, …
Выбор начального приближения
Сходимость МПИ гарантирована при любом начальном векторе x(0). Очевидно, что итераций потребуется меньше, если x(0) ближе к решению x*. Если нет никакой информации о грубом решении задачи (3) или решении близкой задачи, то за x (0) обычно принимают вектор свободных членов системы (3).
Способы приведения СЛАУ к нормальному виду
Для решения СЛАУ итерационными методами систему (2) нужно привести к эквивалентной ей системе (3), которая называется системой, приведенной к нормальному виду каким-либо способом. Рассмотрим их.
1. Если в матрице коэффициентов наблюдается диагональное преобладание, т. е.
, j#i, i =1,2,…n,
то систему (3) можно получить, разделив уравнения системы на соответствующие диагональные элементы и выразив x1 через первое уравнение системы, x2 – через второе и т.д. В результате получим:
- новая матрица коэффициентов
- новый вектор свободных членов
2. Иногда выгоднее приводить систему (2) к виду (3) так, чтобы коэффициенты ii не были равны нулю.
Вообще, имея систему
, i = 1, 2, … n,
можно положить
,
где # 0. Тогда исходная система эквивалентна нормальной системе:
, i =1, 2, … n,
где ; при i # j
Теорема 1. Пусть |||| q < 1. Тогда при любом начальном векторе x(0) МПИ сходится к единственному решению x* и при всех k N справедливы оценки погрешности:
-
|| х *-х(k) || ||х(k)-х(k-1) || - апостериорная (6)
-
|| х *-х(k) || ||х(1)-х(0) || - априорная (7)
Здесь обозначение ||.|| используется для матричных и векторных норм, согласованных между собой, т.е. таких, что ||Ах|| ||А||||х||.
В качестве матричных норм может быть использована одна из следующих:
||||1 = (норма – сумма), j = 1,2…n
|||| = (норма – максимум), I = 1,2…n
f= (норма Фробениуса)
В качестве векторных норм может быть использована одна из следующих:
- (норма-максимум)
- (евклидова норма)
- (норма-сумма)
Согласованными между собой матричными и векторными нормами являются: и ; и ; и .
Априорная оценка позволяет подсчитывать заранее число итераций k, достаточное для получения решения х* с заданной точностью при выбранном начальном векторе х(0). Для этого нужно найти наименьшее целое решение неравенства
||х(1)-х(0) || относительно переменной k.
Апостериорной оценкой пользуются непосредственно в процессе вычислений и применяют для останова процесса итераций при выполнении неравенства:
||х(k)-х(k-1) ||
2.3. Метод Зейделя
Метод Зейделя представляет собой модификацию МПИ (5) решения СЛАУ, при котором для подсчета i-й компоненты (k+1)-го приближения используются уже найденные на этом, т.е. (k+1)-м шаге, новые значения первых (i-1) компонент. Т.е., если система (1) тем или иным способом сведена к системе (3) с матрицей коэффициентов и вектором свободных членов , то приближения к ее решению по методу Зейделя определяются системой равенств:
(8)
где k = 0, 1, 2, …;
xi(0) – компоненты выбранного начального вектора.
Теорема 1 о сходимости МПИ остается верной и для метода Зейделя. Выбор начального приближения осуществляется по тому же принципу, что и в МПИ.