2.4. Метод простій ітерації

При великому числі невідомих лінійної системи схема метода Гаусса, яка дає вірне рішення, становиться дуже громіздкой. У цьому випадку для знаходження корней системи іноді краще користуватися приближеними обчислюваними методами - ітераційними. Пріваблівім у Ітераційних методах є іх властивість самовиправляємости та простота реалізації на ЕОМ.

Хай дана система лінійних алгебраічних рівнянь.

А*X=b (2.3)

з неособливою матрицею. Щоб використувати до неї метод ітерацій, необхідно довести її до вигляду

X=C*X+f (2.4)

де С - деяка матриця, а f - вектор-стовпець.

Ітераційний процес для початку обчислювання потребує завдання навчальних умов. Виходя з довільного вектора Х

x⁰₁

x ⁰ = x⁰₂

....

x⁰_N

будуємо ітераційний процес:

X^(к+1) = c*X ^(к) + f (k=0,1,2,....) (2.5)

Зробивши ітераціі, отримаємо послідовність векторів x⁽¹⁾, x⁽²⁾, х ⁽³⁾,..., x^(к) .

Якщо послідовність приближення має межу, то ця межа є рішенням системи (2.3)

lim ( x^(к+1) )=c * x^(к) + f (2.6)

Процес ітерації закінчується, коли |x ^(к+1) - x^(к) | < Є, де Є - дана точність рішення.

Процес ітерацій (2.5) добре зходиться (тобто чісло приближення, необхідне для отрімання корнів системи (2.3) з заданою точністю невелико), якщо елементи матриці А малі по абсолютній величині. Іншими словами для успішного використовування методу ітерацій модулі діагональних коефіцієнтів системи (2.3) повинні бути більш суми модулів

останніх коефіцієнтів рівняння (вільние члені не враховується). Ця умова являється умовою сходження.

Відмітимо одну з важливих особливостей методу ітерацій. Сходячийся процес ітерації обладає властивостями самовиправлення, тобто окрема помилка в обчисленнях не відображується на кінцевому результаті, так як помилкове приближення можна розглядати як нове навчальне приближення.

Начальний вектор x може бути вибран довільно. Іноді беруть x⁽⁰⁾ = f ⁽⁰⁾ . Найбільш доцільно як компоненту начального вектора увзяти приближенне значення невідомих, отриманих грубою прикидкою. Ніж ближче початкове приближення до значення корней системи, тим швидкіше зійдеться ітераційний процес .

Якщо матриця А неособлива, то систему (2.3) за допомогою сукупності елементарних перетворень завжди можна привести до вигляду (2.4).

До елементарного переворення матриць відносяться :

а) заміна рядків (стовпців);

б) множення усіх елементів якого-небудь рядка (стовпця) на одне і те ж число, відмінне від нуля;

в) додання до елементів якого-небудь рядка (стовпця), відповідних елементів другого рядка (стовпця), множенних на одне і те ж число.

Практично діють наступним чином. З заданой системи виділяють рівняння з коефіцієнтами, модулі яких більше суми останніх коефіцієнтів рівняння. Кожне віділене рівняння виписують у такий рядок нової системи, щоб найбільший по модулю коефіцієнт опинився діагональним. Потім, використючи елементарні перетворення, складають останні рівняння нової системи. При цьому необхідно, щоб були викорисовані у тому чи іншому сполученні усі рівняння початкової системи.

ПРИКЛАД:

Для знаходження коефіцієнтів емпирічної залежності необхідно визначити наступну систему рівняння

2*x₁-0.5*x₂+4*x₃=22 (A)

3*x₁+3.5*x₂+3*x₃=35 (Б)

x₁+0.5*x₂-x₃=-1 (B)

У рівнянні (А) коефіцієнт при х₃ по модулю більш суми модулей останніх коефіцієнтів, тому можна приймати це рівняння за третє рівняння нової системи. Щоб отримати друге рівняння з максимальному по модулю коефіцієнтом при х₂, достатньо скласти разність (Б)-(А):

х₁+4*x₂-x₃=13

При перетворенні початкової системи до вигляду (2.4) були використані рівняння (А) та (Б). Отже, у перше рівнняня обов'язково повинно увійти рівняння (В), наприклад, використовуючи наступне перетворення

(А)+4*(В): 6*x₁+1.5*x₂+0*x₃=18.

Таким чином, отримана еквівалентна система рівнянь,котра задовольняє умовам сходження:

6*x₁+1.5*x₂=18 (А1)

x₁+4*x₂-x₃=13 (Б1)

2*x₁-0.5*x2+4*x₃=22 (В1)

Вирішуя перше рівняння відносно х₁, друге - відносно х₂, третє - відносно х₃, отримаємо

x₁=3-0.25*x₂

x₂=3.25-0.25*x₁+0.25*x₃ (2.7)

x₃=5.5-0.5*x₁+0.125*x₂

Як навчальний вектор x⁽⁰⁾ візьмемо елементи стовбця вільних членів, округляючи їх значення до одного знаку після коми:

x⁽⁰⁾₁= 3; x⁽⁰ ₂ = 3.3; x⁽⁰⁾₃ = 5.5.

Точність обчислювання Є=0.01

Послідовно обчислюємо:

при k=1:

x⁽¹⁾₁ = 3 - 0.25*3.3 = 2.175

x⁽¹⁾₂ = 3.25 - 0.25*3 + 0.25*5.5 = 3.875

x⁽¹⁾₃ = 5.5 - 0.5*3 + 0.125*3.3 = 4.413

при k=2:

x⁽²⁾₁ = 3 - 0.25*3.875 = 2.031

x⁽²⁾₂ = 3.25 - 0.25*2.175 + 0.25*4.413 = 3.810

x⁽²⁾₃ = 5.5 - 0.5*2.175 + 0.125*3.875 = 4.897

та т.д.

Результати подальших обчислювань доведені у таблиці.

-----------------------------------------------------------------------

k | 0 | 1 | 2 | 3 | 4 | 5 | 6

-----------------------------------------------------------------------

x1 3 2.175 2.031 2.048 2.009 2.006 2.002

x2 3.3 3.875 3.810 3.966 3.978 3.991 3.997

x3 5.5 4.13 4.897 4.961 4.972 4.993 4.996

-----------------------------------------------------------------------

Так як модулі разностей значень Х^(к) при k=5 і k=6

| x⁽⁶⁾₁ - x⁽⁵⁾₁ | = 0.004; | x⁽⁶⁾₂ - x⁽⁵⁾₂ | = 0.006; | x⁽⁶⁾₃ - x⁽⁵⁾₃ | = 0.003;

меньш заданої точності Є, то як рішення приймаємо:

х₁ = 2.002 ; х₂ = 3.997 ; х₃ = 4.9967.

Для порівняння точні значення невідомих: х₁ = 2; х₂ = 4; х₃ = 5.