Дипломная работа: Розробка алгоритму та програми чисельного розвязку систем лінійних алгебраїчних рівнянь з розрідженою

До прямих методів, що використовують властивість розрідженості матриці, можна віднести: алгоритм мінімального ступеня, алгоритм мінімального дефіциту, деревовидна блокова розбивка для асиметричного розкладання, методи вкладених або паралельних перетинів і ін.

1.2 Ітераційні методи розв’язку СЛАР

Наближені методи розв’язку систем лінійних рівнянь дозволяють одержувати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів. Процес побудови такої послідовності називається ітераційним (повторюваним).

Ефективність застосування наближених методів залежить від вибору початкового вектора і швидкості збіжності процесу.

1.2.1 Метод простих ітерацій

Нехай дана система n лінійних рівнянь з n невідомими: . Припускаючи, що діагональні елементи a_ii ≠0 (i =1,...,n ) , виразимо x ₁ через перше рівняння системи, x ₂ – через друге рівняння і т.д. У результаті одержимо систему:

(1.38)

Позначимо b_i / a_ij =β _i - a_ij / a_ii =α _ij , де i,j =1,..., n . Тоді система запишеться, таким чином, у матричній формі: x =β +α x . Розв'яжемо цю систему методом простих ітерацій. За нульове наближення приймемо стовпець вільних членів. Кожне (k+1) -е наближення обчислюють по формулі:

(1.39)

Якщо послідовність наближень x⁽⁰⁾ ,..., x^{( k)} має границю , то ця границя є розв’язком системи, оскільки в силу властивості границі , тобто x=β+α x [4,6].

1.2.2 Метод Зейделя

Метод Зейделя являє собою модифікацію методу простих ітерацій.

Нехай дана СЛАР, приведена до нормального вигляду: x=β+αx . Вибираємо довільно початкові наближення невідомих і підставляємо в перше рівняння системи. Отримане перше наближення підставляємо в друге рівняння системи і так далі до останнього рівняння. Аналогічно будуємо другі, треті і т.д. ітерації.

Таким чином, припускаючи, що k -і наближення відомі, методом Зейделя будуємо (k+1) -і наближення по наступних формулах:

(1.40)

(1.41)

(1.42)

1.2.3 Метод релаксації

Метод релаксації – наближений метод розв’язку систем лінійних рівнянь.

Система лінійних рівнянь

(1.43)

приводиться до виду:

(1.44)

де

(1.45)

Знаходяться нев'язки R_j :

(1.46)

Вибирається початкове наближення x ⁽⁰⁾ =0. На кожному кроці необхідно перетворити на нуль максимальну нев'язку:

(1.47)

Умова зупинки:.

Відповідь знаходиться по формулі:

(1.48)

1.2.4 Багатосітковий метод

Багатосітковий метод – метод розв’язку систем лінійних алгебраїчних рівнянь, заснований на використанні послідовності зменшуваних сіток і операторів переходу від однієї сітки до іншої. Сітки будуються на основі більших значень у матриці системи, що дозволяє використовувати цей метод при рішенні еліптичних рівнянь навіть на нерегулярних сітках.

Припустимо, що необхідно розв'язати систему виду:

(1.49)