![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть система линейных алгебраических уравнений (2) приведена нормальному виду (3) тем или иным способом. Решим ее методом простых итераций. Используя систему (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) так, чтобы коэффициенты aii не были равны нулю. Например, уравнение
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
Дата публикования: 2015-03-26; Прочитано: 1972 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!