ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ
Задание находится внизу страницы, 19 номер. В ДЕМО ФАЙЛЕ
ЧАСТЬ ДЛЯ ПОИСКА ДУБЛИРУЮ НИЖЕ
Метод Зейделя представляет собой модификацию метода простых итераций решения СЛАУ, при котором для подсчета i-й компоненты (k+1)-го приближения используются уже найденные на этом, т.е. (k+1)-м шаге, новые значения первых (i-1) компонент. Т.е., если система Ах=b тем или иным способом сведена к системе, приведенной к нормальному виду, с матрицей коэффициентов a и вектором свободных членов b, то приближения к ее решению по методу Зейделя определяются системой равенств:
(1)
где k = 0, 1, 2, …;
xi(0) – компоненты выбранного начального вектора.
Сформулированная выше Теорема 1 о сходимости метода простых итераций остается верной и для метода Зейделя. Выбор начального приближения осуществляется по тому же принципу, что и в методе простых итераций.
Пример .
Для системы
6,1х1 + 2,2х2 + 1,2х3 = 16,55
2,2х1 + 5,5х2 -1,5х3 = 10,55
1,2х1 -1,5х2 + 7,2х3 = 16,80
записать сходящийся процесс метода Зейделя. Найти четвертое приближение, оценить его абсолютную погрешность и сравнить ее с абсолютной погрешностью, полученной при решении Примера 2 методом простых итераций в Лабораторной работе «Решение систем линейных алгебраических уравнений методом простых итераций», зная точное решение системы х*=(1,5; 2,0; 2,5)Т.
Матрица коэффициентов данной системы обладает диагональным преобладанием. Поэтому разделим уравнения системы на диагональные элементы. В результате система преобразуется к виду:
х1 = -0,36х2 - 0,197х3 + 2,71
х2 = -0,4х1 + 0,27х3 + 1,92
х3 = -0,167х1 + 0,208х2 + 2,333
Эта система равносильна исходной, в которой можно считать:
;
.
0,557
Т.к. ||a||¥= 0,673 = 0,673 (=q) <1, можно воспользоваться теоремой 1.
0,375 ¥
Итерационный процесс метода Зейделя запишется следующим образом:
х1(k+1) = -0,36х2(k) - 0,197х3(k) + 2,71
х2(k+1) = -0,4х1(k+1) + 0,27х3(k) + 1,92
х3(k+1) = -0,167х1(k+1) + 0,208х2(k+1) + 2,333,
Начиная процесс вычислений с того же начального приближения
x(0) = 0, последовательно получаем:
х1(1) = 2,71
х2(1) = -0,4×2,71 + 1,92 = 0,84
х3(1) = -0,167×2,71 + 0,208×0,84 + 2,333 = 2,06
х1(2) = -0,36×0,84 - 0,19×2,06 + 2,71 = 2,02
х2(2) = -0,4×2,02 + 0,27×2,06 + 1,92 = 1,67
х3(2) = -0,167×2,02 + 0,208×1,67 + 2,333 = 2,34
х1(3) = -0,36×1,67 - 0,197×2,34 + 2,71 = 1,65
х2(3) = -0,4×1,65 + 0,27×2,34 + 1,92 = 1,89
х3(3) = -0,167×1,65 + 0,208×1,89 + 2,333 = 2,45
х1(4) = -0,36×1,89 - 0,197×2,45 + 2,71 = 1,54
х2(4) = -0,4×1,54 + 0,27×2,45 + 1,92 = 1,96
х3(4) = -0,167×1,54 + 0,208×1,96 + 2,333 = 2,48
Истинная ошибка приближения x(4) метода Зейделя
.
Она меньше в 3 раза истинной ошибки метода простых итераций.
Заметим, что обычно метод Зейделя сходится к решению быстрее метода простых итераций.
Написать программу, реализующую алгоритм метода Зейделя.
с точностью e = 10-12.
В программе требуется:
1) предусмотреть приведение СЛАУ к виду, пригодному для итераций;
2) организовать проверку условия сходимости метода;
3) выбрать начальное приближение;
4) сделать априорную оценку количества шагов и подсчитать реальное количество шагов для достижения заданной точности метода Зейделя;
5) подсчитать апостериорную оценку метода.
Варианты заданий в Методических указаниях к лабораторной работе «Решение СЛАУ методом простых итераций».
СОДЕРЖАНИЕ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ
В отчете по лабораторной работе должны быть представлены следующие разделы:
1. Постановка задачи.
2. Математическая модель.
3. Текст программы.
4. Результаты работы.
5. Выводы.
Лабораторная работа выполняется на любом языке высокого уровня. Отчет помещается в текстовый файл формата Word.
_
ЛАБОРАТОРНАЯ РАБОТА НА ТЕМУ "РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СЛАУ) МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ».
Метод простых итераций относится к группе итерационных методов- методов, в которых решение может быть получено путем сходящихся бесконечных процессов.
Пусть дана система n линейных уравнений с n неизвестными:
(1) Запишем систему (1) в матричном виде:
A x = b, (2)
Преобразуем систему (2) тем или иным способом (таких способов существует множество; некоторые из них будут рассмотрены ниже) к эквивалентной ей системе вида:
x = ax + b, (3)
где x – тот же вектор неизвестных, a, b - некоторые новые матрица и вектор соответственно.
Эта система называется приведенной к нормальному виду. Она пригодна для итерационного процесса.
Решим ее методом простых итераций. Используя систему (3), можно определить последовательность приближений x(k) к неподвижной точке x* рекуррентным равенством
x(k+1)= a x(k)+b , где k =0,1,2,…. (4)
Итерационный процесс (4), начинающийся с некоторого вектора
x(0) =( x
,…, x
)
Т, будем называть методом простых итераций (МПИ).
Приближения к решению СЛАУ методом простых итераций могут быть записаны в виде следующей системы равенств:
…….. (5)
,
где k = 0,1,2, …
Выбор начального приближения
Сходимость МПИ гарантирована при любом начальном векторе x (0). Очевидно, что итераций потребуется меньше, если x (0) ближе к решению x *. Если нет никакой информации о грубом решении задачи (3) или решении близкой задачи, то за x (0) обычно принимают вектор b свободных членов системы (3).
Способы приведения СЛАУ к нормальному виду
В разделе 2 отмечалось, что для решения СЛАУ итерационными методами систему (2) нужно привести к эквивалентной ей системе (3), которая называется системой, приведенной к нормальному виду каким-либо способом. Рассмотрим их.
1. Если в матрице коэффициентов A наблюдается диагональное преобладание, т. е.
, j#i, i =1,2,…n,
то систему (3) можно получить, разделив уравнения системы на соответствующие диагональные элементы и выразив x1 через первое уравнение системы, x2 – через второе и т.д. В результате получим:
- новая матрица коэффициентов
- новый вектор свободных членов
2. Иногда выгоднее приводить систему (2) к виду (3) так, чтобы коэффициенты a
ii не были равны нулю. Например, уравнение
1,02 x1 – 0,15 x2 = 2,7
для применения МПИ естественно записать в виде
(1+0,02) x1 – 0,15 x2 = 2,7
x1 = 2,7 – 0,02 x1 + 0,15 x2
Вообще, имея систему
, i = 1, 2, … n,
можно положить
,
где
# 0. Тогда исходная система эквивалентна нормальной системе:
, i =1, 2, … n,
где
;
при i # j
Пример 1.
Привести систему к нормальному виду.
7,6x1 + 0,5x2 + 2,4x3 = 1,9
2,2x1 + 9,1x2 + 4,4x3 = 9,7
-1,3x1 + 0,2x2 + 5,8x3 = -1,4
Применим 1 способ, разделив строки на соответствующие диагональные элементы:
x1 = 0,25 – 0,065x2 – 0,3158x3
x2 = 1,0659 – 0,2418x1 – 0,4847x3
x3 = -0,2414 + 0,2241x1 – 0,3448x2
Приведем систему к нормальному виду вторым способом:
Перепишем исходную систему так:
Матрица a и вектор b принимают вид:
;
.
Последовательно находим:
Таким образом, с точностью до 10-3 получаем
x1 = 0,236; x2 = 1,103; x3 = -0,214.
Пример 2.
Для системы
6,1х1 + 2,2х2 + 1,2х3 = 16,55
2,2х1 + 5,5х2 -1,5х3 = 10,55
1,2х1 -1,5х2 + 7,2х3 = 16,80
записать сходящийся процесс простых итераций. За сколько шагов этого процесса, начатого с нуль-вектора, можно достичь точности e=0,001 по норме-максимум? Найти четвертое приближение, оценить его абсолютную погрешность и сравнить ее с истинной погрешностью, зная точное решение системы х*=(1,5; 2,0; 2,5)Т.
Матрица коэффициентов данной системы обладает диагональным преобладанием. Поэтому разделим уравнения системы на диагональные элементы. В результате система преобразуется к виду:
х1 = -0,36х2 - 0,197х3 + 2,71
х2 = -0,4х1 + 0,27х3 + 1,92
х3 = -0,167х1 + 0,208х2 + 2,333
Эта система равносильна исходной и имеет форму уравнения (3), в котором можно считать:
;
.
0,557
Т.к. ||a||¥= 0,673 = 0,673 (=q) <1, можно воспользоваться теоремой 1.
0,375 ¥
По этой теореме метод простых итераций
х1(k+1) = -0,36х2(k) - 0,197х3(k) + 2,71
х2(k+1) = -0,4х1(k) + 0,27х3(k) + 1,92
х3(k+1) = -0,167х1(k) + 0,208х2(k) + 2,333,
где (k = 0, 1, 2,…) определяет сходящуюся к решению х* последовательность векторов х(k) = (х1(k) ;; х2(k); х3(k))Т, априорная оценка погрешностей которых есть
||х* - х(k)||¥ £
||х(1) - х(0)||¥ =
||х(1) - х(0)||¥
При заданном векторе х(0)=0 первым приближением х(1) служит вектор b свободных членов, следовательно, ||х(1) - х(0)||¥ = ||b||¥ = 2,71.
Требуемое число итерационных шагов, достаточное для достижения точности 0,001, может быть найдено как первое из последовательности натуральных чисел k, удовлетворяющих неравенству:
×2,71 £ 0,001
×2,71 £ 0,001
0,673k×8,287 £ 0,001
0,673k £ 0,00012
Получив из неравенства k » 22,9 , принимаем k = 23.
Вычислим приближения х(2), х(3), х(4).
х1(2) = -0,36×1,92 - 0,197×2,333 + 2,71 = 1,56
х2(2) = -0,4×2,71 + 0,27×2,333 + 1,92 = 1,47
х3(2) = -0,167×2,71 + 0,208×1,92 + 2,333 = 2,28
х1(3) = -0,36×1,47 - 0,197×2,28 + 2,71 = 1,73
х2(3) = -0,4×1,56 + 0,27×2,28 + 1,92 = 1,91
х3(3) = -0,167×1,56 + 0,208×1,47 + 2,333 = 2,38
х1(4) = -0,36×1,91 - 0,197×2,38 + 2,71 = 1,55
х2(4) = -0,4×1,73 + 0,27×2,38 + 1,92 = 1,87
х3(4) = -0,167×1,73 + 0,208×1,91 + 2,333 = 2,44
Априорная оценка погрешности (7) четвертого приближения дает:
.
При этом истинная ошибка:
,
что на порядок лучше прогнозируемой ошибки. Следовательно, найденное априорное число итерационных шагов наверняка больше необходимого.
Апостериорная оценка погрешности (6) того же 4-го приближения:
.
Это лучше априорной оценки.
Условия сходимости итерационного процесса.
Дана система линейных уравнений, приведенная к нормальному виду
x = b + ax.
Теорема 1. Пусть ||a|| £ q < 1. Тогда при любом начальном векторе x(0) МПИ сходится к единственному решению x* и при всех k Î N справедливы оценки погрешности:
1) || х *-х(k) ||£
||х(k)-х(k-1) || - апостериорная (6)
2) || х *-х(k) ||£
||х(1)-х(0) || - априорная (7)
Здесь обозначение ||.|| используется для матричных и векторных норм, согласованных между собой, т.е. таких, что ||Ах|| £ ||А||×||х||.
В качестве матричных норм может быть использована одна из следующих:
||a||1 =
(норма – сумма), j = 1,2…n
||a||¥ =
(норма – максимум), I = 1,2…n
f=
(норма Фробениуса)
В качестве векторных норм может быть использована одна из следующих:
- (норма-максимум)
- (евклидова норма)
- (норма-сумма)
Согласованными между собой матричными и векторными нормами являются:
и
;
и
;
и
.
Априорная оценка позволяет подсчитывать заранее число итераций k, достаточное для получения решения х* с заданной точностью e при выбранном начальном векторе х(0). Для этого нужно найти наименьшее целое решение неравенства
||х(1)-х(0) ||£ e относительно переменной k.
Апостериорной оценкой пользуются непосредственно в процессе вычислений и применяют для останова процесса итераций при выполнении неравенства:
||х(k)-х(k-1) || £
e
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
Написать программу, реализующую алгоритм метода простых итераций с точностью e = 10-12.
В программе требуется:
1) предусмотреть приведение СЛАУ к виду, пригодному для итераций;
2) организовать проверку условия сходимости методов;
3) выбрать начальное приближение;
4) сделать априорную оценку количества шагов и подсчитать реальное количество шагов для достижения заданной точности метода простых итераций;
5) подсчитать апостериорную оценку метода.
ВАРИАНТЫ ЗАДАНИЙ
1.
;
.
2.
;
.
3.
;
.
4.
;
.
5.
;
.
6.
;
.
7.
;
.
8.
;
.
9.
;
.
10.
;
.
11.
;
.
12.
;
.
13.
;
.
14.
;
.
15.
;
.
16.
;
.
17.
;
.
18.
;
.
19.
;
.
20.
;
.
21.
;
.
22.
;
.
СОДЕРЖАНИЕ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ
В отчете по лабораторной работе должны быть представлены следующие разделы:
1. Постановка задачи.
2. Математическая модель.
3. Текст программы.
4. Результаты работы.
5. Выводы.
Лабораторная работа выполняется на любом языке высокого уровня.
Отчет заносится в текстовый файл формата Word.
