Метод простых итераций (МПИ) решения СЛАУ

Пусть система линейных алгебраических уравнений (2) приведена нормальному виду (3) тем или иным способом. Решим ее методом простых итераций. Используя систему (3), можно определить последовательность приближений x^{(k )} к неподвижной точке x* рекуррентным равенством

x^(k+1)= a x^(k)+b, где k =0,1,2,…. (4)

Итерационный процесс (4), начинающийся с некоторого вектора

x⁽⁰⁾ =(x ,…, x )^Т, будем называть методом простых итераций (МПИ).

Приближения к решению СЛАУ методом простых итераций могут быть записаны в виде следующей системы равенств:

…….. (5)

,

где k = 0,1,2, …

Выбор начального приближения

Сходимость МПИ гарантирована при любом начальном векторе x ⁽⁰⁾. Очевидно, что итераций потребуется меньше, если x ⁽⁰⁾ ближе к решению x ^*. Если нет никакой информации о грубом решении задачи (3) или решении близкой задачи, то за x ⁽⁰⁾ обычно принимают вектор b свободных членов системы (3).

Способы приведения СЛАУ к нормальному виду

В разделе 2 отмечалось, что для решения СЛАУ итерационными методами систему (2) нужно привести к эквивалентной ей системе (3), которая называется системой, приведенной к нормальному виду каким-либо способом. Рассмотрим их.

1. Если в матрице коэффициентов A наблюдается диагональное преобладание, т. е.

, j#i, i =1,2,…n,

то систему (3) можно получить, разделив уравнения системы на соответствующие диагональные элементы и выразив x₁ через первое уравнение системы, x_{2 –} через второе и т.д. В результате получим:

- новая матрица коэффициентов

- новый вектор свободных членов

2. Иногда выгоднее приводить систему (2) к виду (3) так, чтобы коэффициенты a_ii не были равны нулю. Например, уравнение

1,02 x₁ – 0,15 x₂ = 2,7

для применения МПИ естественно записать в виде

(1+0,02) x₁ – 0,15 x₂ = 2,7

x₁ = 2,7 – 0,02 x₁ + 0,15 x₂

Вообще, имея систему

, i = 1, 2, … n,

можно положить

,

где # 0. Тогда исходная система эквивалентна нормальной системе:

, i =1, 2, … n,

где ; при i # j

Пример 1. Привести систему к нормальному виду.

7,6x₁ + 0,5x₂ + 2,4x₃ = 1,9

2,2x₁ + 9,1x₂ + 4,4x₃ = 9,7

-1,3x₁ + 0,2x₂ + 5,8x₃ = -1,4

Применим 1 способ, разделив строки на соответствующие диагональные элементы:

x₁ = 0,25 – 0,065x₂ – 0,3158x₃

x₂ = 1,0659 – 0,2418x₁ – 0,4847x₃

x₃ = -0,2414 + 0,2241x₁ – 0,3448x₂

Приведем систему к нормальному виду вторым способом:

Перепишем исходную систему так:

Матрица a и вектор b принимают вид:

; .

Последовательно находим:

Таким образом, с точностью до 10^-3 получаем

x₁ = 0,236; x₂ = 1,103; x₃ = -0,214.

Пример 2.

Для системы

6,1х₁ + 2,2х₂ + 1,2х₃ = 16,55

2,2х₁ + 5,5х₂ -1,5х₃ = 10,55

1,2х₁ -1,5х₂ + 7,2х₃ = 16,80

записать сходящийся процесс простых итераций. За сколько шагов этого процесса, начатого с нуль-вектора, можно достичь точности e=0,001 по норме-максимум? Найти третье приближение, оценить его абсолютную погрешность и сравнить ее с истинной погрешностью, зная точное решение системы х^*=(1,5; 2,0; 2,5)^Т.

Матрица коэффициентов данной системы обладает диагональным преобладанием. Поэтому разделим уравнения системы на диагональные элементы. В результате система преобразуется к виду:

х₁ = -0,36х₂ - 0,197х₃ + 2,71

х₂ = -0,4х₁ + 0,27х₃ + 1,92

х₃ = -0,167х₁ + 0,208х₂ + 2,333

Эта система равносильна исходной и имеет форму уравнения (3), в котором можно считать:

; .

0,557

Т.к. ||a||_¥= 0,673 = 0,673 (=q) <1, можно воспользоваться теоремой 1.

0,375 ¥

По этой теореме метод простых итераций

х₁^(k+1) = -0,36х₂^(k) - 0,197х₃^(k) + 2,71

х₂^(k+1) = -0,4х₁^(k) + 0,27х₃^(k) + 1,92

х₃^(k+1) = -0,167х₁^(k) + 0,208х₂^(k) + 2,333,

где (k = 0, 1, 2,…) определяет сходящуюся к решению х^* последовательность векторов х^(k) = (х₁^{(k) ;}; х₂^(k); х₃^(k))^Т, априорная оценка погрешностей которых есть

||х^* - х^(k)||_¥ £ ||х⁽¹⁾ - х⁽⁰⁾||_¥ = ||х⁽¹⁾ - х⁽⁰⁾||_¥

При заданном векторе х⁽⁰⁾=0 первым приближением х⁽¹⁾ служит вектор b свободных членов, следовательно, ||х⁽¹⁾ - х⁽⁰⁾||_¥ = ||b||_¥ = 2,71.

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

×2,71 £ 0,001

×2,71 £ 0,001

0,673^k×8,287 £ 0,001

0,673^k £ 0,00012

Получив из неравенства k» 22,9 принимаем k = 23.

Вычислим приближения х⁽²⁾, х⁽³⁾, х⁽⁴⁾.

х₁⁽²⁾ = -0,36×1,92 - 0,197×2,333 + 2,71 = 1,56

х₂⁽²⁾ = -0,4×2,71 + 0,27×2,333 + 1,92 = 1,47

х₃⁽²⁾ = -0,167×2,71 + 0,208×1,92 + 2,333 = 2,28

х₁⁽³⁾ = -0,36×1,47 - 0,197×2,28 + 2,71 = 1,73

х₂⁽³⁾ = -0,4×1,56 + 0,27×2,28 + 1,92 = 1,91

х₃⁽³⁾ = -0,167×1,56 + 0,208×1,47 + 2,333 = 2,38

х₁⁽⁴⁾ = -0,36×1,91 - 0,197×2,38 + 2,71 = 1,55

х₂⁽⁴⁾ = -0,4×1,73 + 0,27×2,38 + 1,92 = 1,87

х₃⁽⁴⁾ = -0,167×1,73 + 0,208×1,91 + 2,333 = 2,44

Априорная оценка погрешности (7) четвертого приближения дает:

.

При этом истинная ошибка:

,

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

Апостериорная оценка погрешности (6) того же 4-го приближения:

.

Это лучше априорной оценки.

Условия сходимости итерационного процесса.

Дана система линейных уравнений, приведенная к нормальному виду

x = b + ax.

Теорема 1. Пусть || a || £ q < 1. Тогда при любом начальном векторе x⁽⁰⁾ МПИ сходится к единственному решению x^* и при всех k Î N справедливы оценки погрешности:

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

2) || х ^*-х^(k) || £ || х⁽¹⁾-х⁽⁰⁾ || - априорная (7)

Здесь обозначение ||. || используется для матричных и векторных норм, согласованных между собой, т.е. таких, что || Ах || £ || А ||×|| х ||.

В качестве матричных норм может быть использована одна из следующих:

|| a ||₁ = (норма – сумма), j = 1,2…n

|| a ||_¥ = (норма – максимум), I = 1,2…n

_f= (норма Фробениуса)

В качестве векторных норм может быть использована одна из следующих:

- (норма-максимум)

- (евклидова норма)

- (норма-сумма)

Согласованными между собой матричными и векторными нормами являются: и ; и ; и .

Априорная оценка позволяет подсчитывать заранее число итераций k, достаточное для получения решения х^* с заданной точностью e при выбранном начальном векторе х⁽⁰⁾. Для этогонужно найти наименьшее целое решение неравенства

|| х⁽¹⁾-х⁽⁰⁾ || £ e относительно переменной k.

Апостериорной оценкой пользуются непосредственно в процессе вычислений и применяют для останова процесса итераций при выполнении неравенства:

|| х^(k)-х^(k-1) || £ e