Методи рішення систем лінійних алгебраїчних рівнянь

У програмах аналізу в САПР для рішення СЛАР найчастіше застосовують метод Гауса або його різновиду. Метод Гауса — метод послідовного виключення невідомих із системи рівнянь. При виключенні -й невідомої із системи рівнянь

(3.16)

всі коефіцієнти при й перераховують по формулі

(3.17)

Виключення невідомих, де — порядок системи (3.16), називають прямим ходом, у процесі якого матриця коефіцієнтів здобуває трикутний вид. При зворотному ході послідовно обчислюють невідомі, починаючи з .

У загальному випадку число арифметичних операцій для рішення (3.16) по Гаусу пропорційно . Це приводить до значних витрат машинного часу, оскільки СЛАР вирішується багаторазово в процесі одноваріантного аналізу, і істотно обмежує складність аналізованих об’єктів.

Можна помітно підвищити обчислювальну ефективність аналізу, якщо використати характерну практично для всіх застосувань властивість високої розрідженості матриці в моделі (3.16).

Матрицю називають розрідженою, якщо більшість її елементів дорівнює нулю. Ефективність обробки розріджених матриць велика тому, що, по-перше, перерахування по формулі (3.17) не потрібно, якщо хоча б один з елементів або виявляються нульовим, по-друге, не потрібні витрати пам’яті для зберігання нульових елементів. Хоча алгоритми обробки розріджених матриць більш складні, але в результаті вдається одержати витрати машинного часу, близькі до лінійних, наприклад, витрати виявляються пропорційними .

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

Для пояснення цієї залежності розглянемо два варіанти подання однієї й тієї ж СЛАР. У першому випадку система рівнянь має вигляд

 

При прямому ході відповідно до формули (3.17) всі елементи матриці, які спочатку були нульовими, стають ненульовими, а матриця виявляється повністю насиченою. Елементи, що стають ненульовими в процесі гаусових виключень, називають вторинними ненулями. Вторинні ненулі в Табл. 1 відзначені знаком «*».

У другому випадку міняються місцями перше й п’яте рівняння. Матриці коефіцієнтів мають вигляд Табл. 1 і Табл. 2, де ненульові елементи представлені знаком «+». Тепер вторинні ненульові елементи не з’являються, матриця залишається розрідженою, висока обчислювальна ефективність зберігається.

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

Таблиця 1

+	+	+	+	+
+	+	*	*	*
+	*	+	*	*
+	*	*	+	*
+	*	*	*	+

 

Таблиця 2

+	.	.	.	+
.	+	.	.	+
.	.	+	.	+
.	.	.	+	+
+	+	+	+	+

 

Методом розріджених матриць називають метод рішення СЛАР на основі методу Гауса з урахуванням розрідженості (первинної й вторинної) матриці коефіцієнтів.

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

При цьому виграш у витратах пам’яті досить значний. Так, при матриці помірного розміру 200х200 без урахування розрідженості буде потрібно 320 кбайт. Якщо ж взяти характерне значення 9 для середнього числа ненулів в одному рядку, то для коефіцієнтів і покажчиків координат буде потрібно не більше 28 кбайт.

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

Спосіб компіляції більше економічний по витратах часу, але уступає способу інтерпретації по витратах пам’яті. При компіляції пошук потрібних для (3.17) коефіцієнтів виконується однократно перед чисельним рішенням задачі. Замість безпосереднього виконання арифметичних операцій для кожної з них компілюється команда зі знайденими адресами ненульових коефіцієнтів. Такі команди утворять робочу програму рішення СЛАР, що і буде вирішуватися багаторазово. Очевидно, що тепер у робочій програмі буде виконуватися мінімально необхідне число арифметичних операцій.

До числа різновидів методу Гауса відноситься метод LU-розкладання, що заснований на розкладанні матриці коефіцієнтів системи (3.16) на верхні й нижню трикутні матриці, що еквівалентно прямому ходу в методі Гауса. Елементи матриць і обчислюються по рекурентним формулам

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

Крім методу Гауса, для рішення систем лінійних алгебраїчних рівнянь (3.17) застосовують ітераційні методи: метод простої ітерації, метод Зейделя, метод Якобі, методи послідовних верхньої й нижньої релаксації. Наприклад, у методі простої ітерації обчислення виконують по формулі

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