Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Архив1 / doc200 / Отчет ЛР№2 Юля

.doc
Скачиваний:
44
Добавлен:
01.08.2013
Размер:
117.25 Кб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Ижевский государственный технический университет»

Кафедра АСОИУ

ОТЧЕТ

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

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

по дисциплине «Вычислительная математика»

Вариант №6

Выполнил:

студентка гр.Б03-782-1 Ю.С. Вотинцева

Проверил:

ст. преподаватель кафедры АСОИУ А.А. Коробейников

Ижевск 2012

1 ПОСТАНОВКА ЗАДАЧИ

Написать программу, реализующую алгоритмы:

  1. метода простых итераций;

  2. метода Зейделя.

с точностью = 10-12.

В программе требуется:

  1. предусмотреть приведение СЛАУ к виду, пригодному для итераций;

  2. организовать проверку условия сходимости методов;

  3. выбрать начальное приближение;

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

  5. подсчитать апостериорные оценки методов.

Провести сравнительный анализ метода простых итераций и метода Зейделя.

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 справедливы оценки погрешности:

  1. || х *(k) || ||х(k)(k-1) || - апостериорная (6)

  2. || х *(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 о сходимости МПИ остается верной и для метода Зейделя. Выбор начального приближения осуществляется по тому же принципу, что и в МПИ.

Соседние файлы в папке doc200