МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НУ ”Львівська політехніка” Звіт про виконання лабораторної роботи №2 з курсу: ”Алгоритмічні основи криптології” на тему: ”Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь ” Львів-2007 Теоретичні відомості Методи чисельного розв‘язування систем лінійних рівнянь поділяються на дві групи: 1) „точні” (прямі) методи, які дозволяють одержати розв‘язок, якщо він існує, як скінченну кількість арифметичних операцій (наприклад: метод Крамера, метод Жордана-Гауса та ін.); 2) наближені (ітераційні) методи, які дозволяють одержати розв‘язки системи лінійних рівнянь лише з заданою точністю з припущенням, що обчислення проводиться без округлень. Точний розв‘язок в даному випадку можна одержати я к результат нескінченно збіжного процесу. До таких методів відносять метод простої ітерації, метод Зейделя та ін. „Точні” методи використовуються при розв‘язуванні на ЕОМ систем невисокого порядку (n<103 де n - число лінійних алгебраїчних рівнянь системи). Наближені методи використовуються для систем високого порядку (n=103ч106). Переваги наближених методів (метод простих ітерацій) над точними (метод Гауса) є такими: 1. Час обчислень пропорційний n2 на ітерацію, тоді як для методу виключення час обчислень пропорційний n3. Якщо для розв‘язку потрібно менше ніж n ітерацій, то затрати машинного часу будуть менші. 2. Як правило, похибки округлення при ітераційному методі впливають на остаточні результати значно менше, ніж при розв‘язуванні методом Гауса, оскільки при його використанні похибки не нагромаджуються. 3. Метод ітерацій стає особливо зручним при розв‘язку систем, переважна кількість коефіцієнтів яких дорівнює 0. Недоліком методу ітерацій є те, що рішення не завжди збігаються. Метод простої ітерації. Нехай задана система лінійних алгебраїчних рівнянь:
, (1) де
,
,
. Будемо вважати, що діагональні коефіцієнти матриці А
,
. Розв‘яжемо перше рівняння системи (1) відносно
, друге - відносно
і т.д. Тоді отримаємо еквівалентну систему:
, (2) де
при
;
при
,
. Введемо позначення:
,
. Тоді систему (2) можна записати:
. (3) Задамося вектором початкового наближення
, де
- довільні числа. Тоді послідовно знаходимо перше наближення:
, друге наближення:
, і т.д. довільне (K+1) наближення обчислюється за формулою:
,
, (4) або в розгорнутому вигляді:
,
. Ітераційний процес закінчують тоді, коли:
,
, де Е - гранична абсолютна похибка. Методом простої ітерації можна визначити розв‘язок системи рівнянь лише у випадку, коли цей метод є збіжним. Доведено, що якщо елементи матриці
задовольняють одну з умов:
,
, (5)

,
, (6) то процес ітерації збігається до точного розв‘язку при будь-якому векторі нульового наближення. Як правило, за вектор нульового наближення приймають стовпчик вільних членів
. Вихідна система лінійних алгебраїчних рівнянь

A= 24,21+s 2,42 3,85 2,31 31,49 1,52 3,49 4,84 28,72+s 30,24 40,95-r 42,81 де s = 0.2*k , r = 0.2*p, k=6, p=0. Блок-схема алгоритму


/*Текст програми розв’язку системи лінійних алгебраїчних рівнянь методом простої ітерації */ #include <stdio.h> #include <math.h> const int m=3; void main(void) /* оголошення змінних */ { typedef double matrix[3][3]; typedef double vector[3]; matrix a, alpha; vector b, beta, x, x0; int i, j, k; int rez=0; double E; /* вводимо значення матриці коефіцієнтів системи і вектора вільних членів */ for(i=0;i<m;i++) { for(j=0;j<m;j++) { printf("a[%d,%d]?:", i+1, j+1); scanf("%lf", &a[i][j]); } printf("b[%d]?:", i+1); scanf("%lf", &b[i]); } /* присвоєння значень ά і β*/ for(i=0;i<m;i++) { for(j=0;j<m;j++) { if (i!=j) alpha[i][j]=-a[i][j]/a[i][i]; else alpha[i][i]=0; } beta[i]=b[i]/a[i][i]; } /* вводимо значення похибки Е */ { printf("E="); scanf("%lf", &E); /* присвоюємо початкові наближення */ for(i=0;i<m;i++) x0[i]=beta[i]; /* перевірка виконання умови */ while (!rez) { rez=1; for(i=0;i<m;i++) { x[i]=beta[i]; for(j=0;j<m;j++) x[i]+=x0[j]*alpha[i][j]; rez*=(fabs(x[i]-x0[i])<E); } for(i=0;i<m;i++) x0[i]=x[i]; } /* виводимо результати виконання програми */ for(i=0;i<m;i++) printf("x[%d]=%lf\n", i+1, x[i]); /* здійснюємо перевірку перавильності виконаних обчислень */ for (i=0; i<n; i++) { q=0; for (j=0;j<(m-1);j++) q+=d[i][j]*x[j]; printf ("q%d=%lf\n",i,q); } } Результат виконання програми
Висновок: під час виконання даної лабораторної роботи ми вивчили найбільш поширені методи розв’язку системи лінійних алгебраїчних рівнянь. Похибки округлень при ітераційному методі впливають на остаточні результати значно менше, ніж при розв’язку за методом Гауса, оскільки при його використані похибки не нагромаджуються. Метод ітерації стає особливо зручним при розв’язку систем переважна кількість коефіцієнтів яких дорівнює 0. Недоліком методу ітерації є те, що рішення не завжди збігаються.