Лекція № 3 розв‘язування систем лінійних алгебраїчних рівнянь

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

2.1 Основні поняття та визначення

Системою лінійних алгебраїчних рівнянь (СЛАР) називають систему виду:

                    (2.1)

де     , ( ) – невідомі; , ( ) – вільні члени системи; , ( ) – коефіцієнти системи.

В матричному вигляді рівняння (2.1) прийме вигляд:

,

де     ={ } – вектор невідомих; ={ } – вектор

вільних членів; ={ } – матриця коефіцієнтів СЛАР.

Розв’язком системи лінійних алгебраїчних рівнянь (2.1) називають вектор , координати якого { } при підстановці у систему, що розв’язують, перетворюють кожне рівняння системи в тотожність .

Кількість невідомих m в системі називають порядком СЛАР. Систему лінійних алгебраїчних рівнянь називають сумісною, якщо вона має хоча б один ненульовий розв’язок. В протилежному випадку СЛАР називають несумісною. СЛАР називається визначеною, якщо вона має тільки один розв’язок (випадок, коли m=n). Систему називають невизначеною, якщо вона має безліч розв’язків (m№n). Система називається виродженою, якщо головний визначник системи дорівнює нулю. Система називається невиродженою, якщо головний визначник системи не дорівнює нулю.

Дві системи називаються еквівалентними, якщо ці системи сумісні, визначені і мають однаковий розв’язок.

СЛАР можна розв'язати на ЕОМ чисельними методами, якщо вона сумісна, визначена, невироджена.

2.2 Класифікація методів розв’язання слар на еом

Для розв’язання СЛАР на ЕОМ традиційно використовують дві групи чисельних методів, що представлені на рисунку 2.1:

     Рисунок 2.1. – Класифікація чисельних методів

  точні (метод Гауса, метод Гауса з вибором головного елементу, метод Гауса з одиничною матрицею, метод Гауса з перетвореною матрицею, метод Гауса-Халецького, метод Гауса-Жордана, метод Крамера);

  наближені (метод послідовних ітерацій, метод Гауса-Зейделя, метод векторів зміщень).

До точних методів відносять методи, які дозволяють отримати точний розв’язок системи (2.1) за відповідну кількість операцій перетворення без урахування похибок заокруглення.

До наближених методів відносять методи, які дозволяють отримати розв‘язок системи (2.1) у вигляді границі послідовності векторів , яка збігається до точного розв’язку системи, де:

2.3 Особливості методів Гауса

Найбільш відомим з точних методів розв’язання системи лінійних алгебраїчних рівнянь (2.1) є методи Гауса, суть яких полягає в тому, що система рівнянь, яка розв’язується, зводиться до еквівалентної системи з верхньою трикутною матрицею. Невідомі знаходяться послідовними підстановками, починаючи з останнього рівняння перетвореної системи. Алгоритми Гауса складаються із виконання однотипних операцій, які легко формалізуються. Однак, точність результату й витрачений на його отримання час у більшості випадків залежить від алгоритму формування трикутної матриці системи. У загальному випадку алгоритми Гауса складаються з двох етапів:

Прямий хід, в результаті якого СЛАР (2.1), що розв‘язується, перетворюється в еквівалентну систему з верхньою трикутною матрицею коефіцієнтів виду:

               (2.2)

Зворотній хід дозволяє визначити вектор розв‘язку починаючи з останнього рівняння системи (2.2) шляхом підстановки координат вектора невідомих, отриманих на попередньому кроці.

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