Математика / 4. Прикладна математика

К.ф.-м.н Лазурчак І.І., к.п.н. Кобильник Т.П.

Дрогобицький державний педагогічний університет імені Івана Франка

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

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

Вивчення багатьох задач призводить до необхідності виконання дії з матрицею, у якій кількість під- та наддіагоналей є однаковою. Як правило, такі матриці мають так звану стрічкову структуру. Матрицю називають -діагональною (або матрицею, яка має стрічкову структуру), якщо при , де – кількість піддіагоналей (наддіагоналей). Число називають шириною стрічки. Такі матриці утворюються, наприклад, при знаходженні власних значень диференціального рівняння з заданими крайовими умовами. У процесі розв’язування такої задачі необхідно обчислити визначник трьохдіагональної матриці. Для обчислення визначника трьохдіагональної матриці розроблені спеціальні формули (див., наприклад, [1]).

У процесі розв’язування задач виникають випадки, коли необхідно обчислити визначник -діагональної матриці великої розмірності (наприклад, ). У такому випадку зручно використовувати метод LU–факторизації [] з дещо зміненими формулами:

, , , ,

, , , , (1)

, .

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

Зі стрічкових квадратних матриць та сформуємо прямокутні матриці та за таким правилом:

, , , . (2)

Інші елементи та дорівнюють нулю.

Тоді елементи матриці згідно (2) будуть обчислюватися за формулами:

, , ,

, (3)

де

, , , .

Крім того, існують випадки, коли у процесі розв’язування задачі необхідно обчислювати визначники довільних стрічкових матриць. Наведемо формули для обчислення визначника довільної стрічкової матриці, використовуючи модифікацію методу -факторизації.

Нехай задана стрічкова матриця шириною , де – кількість піддіагоналей, – кількість наддіагоналей. Тоді формули (1) набудуть вигляду:

, , , ,

, , , , (4)

, .

Для програмної реалізації формул (3) знову необхідно оголошувати три масиви розмірності .

Тому зі стрічкових матриць та сформуємо прямокутні матриці та таким чином:

, , , .

Інші елементи та дорівнюють нулю.

Тоді формули (3) можна переписати у вигляді:

, , ,

, , , , .

Остаточно

.

Якщо системи комп’ютерної математики такі як Mathematica, Maple мають можливість задання матриць у вигляді стрічок, то класичні мови програмування (Pascal) вимагають задання всіх елементів матриць, що в свою чергу вимагає виділення додаткового об’єму оперативної пам’яті ЕОМ.

Програмна реалізація запропонованого алгоритму проведена у кількох системах комп’ютерної математики таких як Mathematica 6.0, Maple 11.0.

Запропонований підхід дає змогу значно зменшити кількість обчислювальних затрат, включаючи об’єм RAM та час CPU.

Системи комп’ютерної математики містять команди для обчислення визначників матриць. Однією з умов ефективного використання певної СКМ для розв’язування задачі є зменшення затрат часу на розв’язування поставленої задачі. Зрозуміло, що СКМ містять функції для обчислення визначників. Проте при великих розмірностях матриць (навіть числових) кількість часу на обчислення визначників значно зростає. Ще гірша ситуація, коли елементами матриці є функції (символьні величини).

Цікавим є дослідження, яке проводить С.Стейнхаус (Stephan Steinhaus) [2] стосовно характеристик СКМ. Згідно його дослідження, для обчислення детермінанта матриці (елементи якої є псевдовипадкові дійсні числа) розмірності потрібно приблизно від 20 (система O-Matrix 6.3) до 505 секунд (система GAUSS 8.0). Серед найбільш поширених СКМ (Maple, Mathematica, Matlab) найкращий результат у системи Mathematica 6.0 (24,3 сек.). Дослідження проводились на комп’ютері з процесором Intel Quad Core Q6000 з тактовою частотою 2,4 GHz і розміром оперативної пам’яті 2 GB під управлінням операційної системи Windows Vista Home.

Література

1. Самарский А. А. Введение в численные методы: Учеб. пособие для вузов / Московский гос. ун-т им. М.В.Ломоносова. — 3-е изд., стер. — СПб. : Лань, 2005. — 288с.

2. Steinhaus S. Comparison of mathematical programs for data analysis (Edition 5.03) [Електронний ресурс] — Munchen/Germany. — 64 p. — Режим доступу : http://www.scientificweb.de/ ncrunch/.