Розробка алгоритму та програми чисельного розвязку систем лінійних алгебраїчних рівнянь з розрідженою (стр. 3 из 9)
у яких матриця А симетрична, тобто АТ=А, aij=aji (i=j=1,...,n).
Розв’язок системи (1.18) здійснюється у два етапи.
Прямий хід. Перетворення матриці А і представлення її у вигляді добутку двох взаємно транспонованих трикутних матриць:
де
Перемножуючи SТ і S, і дорівнюючи матриці А, одержимо наступні формули для визначення sij:
Після знаходження матриці S систему (1.18) заміняємо двома їй еквівалентними системами з трикутними матрицями (1.19):
Зворотній хід. Записуємо системи (1.21) у розгорнутому виді:
Використовуючи (1.22) і (1.23) послідовно знаходимо:
1.1.6 Метод прогону
Для розв’язку систем виду
або, що те ж саме, 
використовується метод прогону, заснований на припущенні, що шукані невідомі зв'язані рекурентним співвідношенням:
де i=1,…,n-1.
Використовуючи це співвідношення, виразимо xi-1і xiчерез xi+1і підставимо в рівняння (1.26):
де Fi – права частина i-го рівняння. Це співвідношення буде виконуватися незалежно від розв’язку, якщо зажадати
Звідси випливає:
З першого рівняння одержимо:
Після знаходження прогоночних коефіцієнтів α і β, використовуючи рівняння (1.27), одержимо розв’язок системи. При цьому
1.1.7 Матричний метод
Матричний метод розв’язку систем лінійних алгебраїчних рівнянь з ненульовим визначником полягає в наступному.
Нехай дана система n лінійних рівнянь з n невідомими (над довільним полем):
Тоді її можна переписати в матричній формі:
, де A– основна матриця системи, 
і 
– стовпці вільних членів і рішень системи відповідно:
Помножимо це матричне рівняння ліворуч на A-1– матрицю, зворотню до матриці A:
Оскільки A−1A=E (враховуючи асоциативність матричного добутку), одержуємо
. Права частина цього рівняння дасть стовпець рішень вихідної системи. Умовою застосовності даного методу (як і взагалі існування розв’язку неоднорідної системи лінійних рівнянь із числом рівнянь, рівним числу невідомих) є невирідженість матриці A. Необхідною і достатньою умовою цього є нерівність нулю визначника матриці A: detA≠0.Для однорідної системи лінійних рівнянь, тобто коли
, дійсно зворотнє правило: система 
має нетривіальний (тобто ненульовий) розв’язок тільки якщо det A=0. Такий зв'язок між рішеннями однорідних і неоднорідних систем лінійних рівнянь зветься альтернативою Фредгольма.До прямих методів, що використовують властивість розрідженості матриці, можна віднести: алгоритм мінімального ступеня, алгоритм мінімального дефіциту, деревовидна блокова розбивка для асиметричного розкладання, методи вкладених або паралельних перетинів і ін.
1.2 Ітераційні методи розв’язку СЛАР
Наближені методи розв’язку систем лінійних рівнянь дозволяють одержувати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів. Процес побудови такої послідовності називається ітераційним (повторюваним).
Ефективність застосування наближених методів залежить від вибору початкового вектора і швидкості збіжності процесу.
1.2.1 Метод простих ітерацій
Нехай дана система n лінійних рівнянь з n невідомими:
. Припускаючи, що діагональні елементи aii≠0 (i=1,...,n), виразимо x1 через перше рівняння системи, x2 – через друге рівняння і т.д. У результаті одержимо систему:
Позначимо bi/aij=βi-aij/aii=αij, де i,j=1,...,n. Тоді система запишеться, таким чином, у матричній формі: x=β+αx. Розв'яжемо цю систему методом простих ітерацій. За нульове наближення приймемо стовпець вільних членів. Кожне (k+1)-е наближення обчислюють по формулі:
Якщо послідовність наближень x(0),...,x(k) має границю
, то ця границя є розв’язком системи, оскільки в силу властивості границі 
, тобто x=β+αx [4,6].1.2.2 Метод Зейделя
Метод Зейделя являє собою модифікацію методу простих ітерацій.
Нехай дана СЛАР, приведена до нормального вигляду: x=β+αx. Вибираємо довільно початкові наближення невідомих і підставляємо в перше рівняння системи. Отримане перше наближення підставляємо в друге рівняння системи і так далі до останнього рівняння. Аналогічно будуємо другі, треті і т.д. ітерації.
Таким чином, припускаючи, що k-і наближення
відомі, методом Зейделя будуємо (k+1)-і наближення по наступних формулах:
