1. Прямі методи розв'язання СЛАР
2. Метод виключення Гаусса
3. послідовний алгоритм
4. паралельний алгоритм
5. Зв'язок методу Гаусса і LU-розкладання

Анотація: В лекції розглядаються типові алгоритми, що застосовуються в роботі з щільними і розрідженими матрицями. Розповідається про деякі форматах зберігання цих матриць. Розглядаються основні властивості матриць, методи розв'язування СЛАР, прямі та ітераційні методи.

Мета лекції: Основною метою лекції є застосування отримані знання про розробку і налагодження паралельних програм в реалізації чисельних алгоритмів для роботи з матрицями.

Прямі методи розв'язання СЛАР

Методи рішення систем лінійних алгебраїчних рівнянь (СЛАР) відносяться до чисельних методів алгебри. При формальному підході вирішення подібних завдань не зустрічає труднощів: рішення системи можна знайти, розкривши визначники у формулі Крамера. Однак при безпосередньому розкритті визначників рішення системи з n невідомими вимагає арифметичних операцій; вже при n близько 20 таке число операцій недоступно для сучасних комп'ютерів. При скільки-небудь великих n застосування методів з таким порядком числа операцій буде неможливо і в доступному для огляду майбутньому. Іншою причиною, по якій цей класичний спосіб непридатний навіть при малих n, є сильний вплив на остаточний результат заокруглень при обчисленнях.

Методи розв'язання алгебраїчних задач можна розділити на точні і ітераційні. Класи завдань, для вирішення яких зазвичай застосовують методи цих груп, можна умовно назвати відповідно класами завдань із середнім і великим числом невідомих. Зміна обсягу і структури пам'яті обчислювальних систем, збільшення їх швидкодії і розвиток чисельних методів призводять до зміщення меж застосування методів в сторону систем більш високих порядків.

Наприклад, в 80-х роках минулого століття точні методи застосовувалися для вирішення систем до порядку 104, ітераційні - до порядку 107, в 90-х - до порядків 105 і 108 відповідно. Сучасні суперкомп'ютери здатні використовувати точні методи при вирішенні ще більших систем.

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

У матричному вигляді система може бути представлена ​​як

де є речова матриця розміру ; b і x - вектора з n елементів.

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

Метод виключення Гаусса

В першу чергу розглянемо алгорітмии, призначені для вирішення системи

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

Метод Гаусса ґрунтується на можливості виконання перетворень лінійних рівнянь, які не змінюють при цьому рішення розглянутої системи (такі перетворення носять найменування еквівалентних). До числа таких перетворень відносяться:

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

Метод Гаусса включає послідовне виконання двох етапів. На першому етапі, який називається прямий хід, вихідна система лінійних рівнянь за допомогою послідовного виключення невідомих приводиться до верхнього трикутного вигляду. При виконанні зворотного ходу (другий етап алгоритму) здійснюється визначення значень невідомих.

послідовний алгоритм

Прямий хід складається в послідовному виключенні невідомих в рівняннях розв'язуваної системи лінійних рівнянь.

На ітерації i , Методу проводиться виключення невідомої i для всіх рівнянь з номерами k, великих i (тобто ) Для цього з цих рівнянь здійснюється віднімання рядка i, помноженої на константу з тим, щоб результуючий коефіцієнт при невідомої в рядках виявився нульовим - всі необхідні обчислення можуть бути визначені за допомогою співвідношень:

де - множники Гаусса.

У підсумку приходимо до системи з верхньою трикутною матрицею

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

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

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

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

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

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

Оцінимо трудомісткість методу Гаусса. При виконанні прямого ходу число операцій складе

Для виконання зворотного ходу буде потрібно

Таким чином, загальний час виконання методу Гаусса при великих n можна оцінити як

де час виконання однієї операції.

паралельний алгоритм

При уважному розгляді методу Гаусса можна помітити, що всі обчислення зводяться до однотипних обчислювальних операцій над рядками матриці коефіцієнтів системи лінійних рівнянь. Як результат, в основу паралельної реалізації алгоритму Гаусса може бути покладено принцип розпаралелювання за даними. В якості базової підзадачі можна прийняти тоді все обчислення, пов'язані з обробкою одного рядка матриці A і відповідного елемента вектора b. Розглянемо загальну схему паралельних обчислень і виникають при цьому інформаційні залежності між базовими подзадачами.

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

При виконанні зворотного ходу методу Гаусса підзадачі виконують необхідні обчислення для знаходження значення невідомих. Як тільки будь-яка подзадача i, , Визначає значення своєї змінної , Це значення має бути використано всіма підзадач з номерами k, : Підзадачі підставляють отримане значення нової невідомої і виконують коригування значень для елементів вектора b.

Виділені базові підзадачі характеризуються однаковою обчислювальної трудомісткістю. Однак розмір матриці, яка описує систему лінійних рівнянь, є істотно більшим, ніж число потоків в програмі (тобто, ), І базові підзадачі можна укрупнити, об'єднавши в рамках однієї підзадачі кілька рядків матриці. При цьому застосування послідовної схеми поділу даних для паралельного вирішення систем лінійних рівнянь призведе до нерівномірного обчислювальної навантаженні між потоками: в міру виключення (на прямому ході) або визначення (на зворотному ході) невідомих в методі Гаусса для більшої частини потоків всі необхідні обчислення будуть завершені і вони виявляться простоюють. Можливий спосіб вирішення проблеми балансування обчислень може складатися у використанні стрічкової циклічної схеми для розподілу даних між укрупненими подзадачами. В цьому випадку матриця A ділиться на набори (смуги) рядків виду (див. Мал. 7.1 ).

стрічкова схема

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

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

• пошук провідного рядка,
• віднімання провідною рядки з усіх рядків, що підлягають обробці,
• виконання зворотного ходу.

Оцінимо трудомісткість розглянутого паралельного варіанта методу Гаусса. Нехай n є порядок розв'язуваної системи лінійних рівнянь, а p, , Позначає число потоків. При розробці паралельного алгоритму всі обчислювальні операції, що виконуються алгоритмом Гауса, були розподілені між потоками паралельної програми. Отже, час, необхідний для виконання обчислень на етапі прямого ходу, можна оцінити як

Підставивши вираз отримаємо, що час виконання обчислень для паралельного варіанта методу Гаусса описується виразом:

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

Зводячи воєдино всі отримані оцінки можна зробити висновок, що час виконання паралельного методу Гаусса описується співвідношенням

Зв'язок методу Гаусса і LU-розкладання

LU -разложеніе - уявлення матриці A у вигляді

де L - нижня трикутна матриця з діагональними елементами, рівними одиниці, а U - верхня трикутна матриця з ненульовими діагональними елементами. LU -разложеніе також називають LU -факторізаціей. Відомо [4], що LU -разложеніе існує і єдино, якщо головні мінори матриці A відмінні від нуля.

Алгоритм LU -разложенія тісно пов'язаний з методом виключення Гауса. Справді, нехай ми вирішуємо систему рівнянь виду (7.2). Безпосередньо перевіряється, що перетворення k -го кроку методу Гаусса рівносильні домноженію системи (7.2) зліва на матрицю

де - множники Гаусса з (7.4). Як було розглянуто в п. 7.1.1, прямий хід методу Гаусса перетворює вихідну систему рівнянь до вигляду

з верхньою трикутною матрицею U. знаючи матриці , Можна записати матрицю U і вектор c як

позначимо Можна безпосередньо перевірити, що

Звідси отримуємо .

Таким чином, матрицю L можна отримати як нижню трикутну матрицю коефіцієнтів Гаусса, а матрицю U - як верхню трикутну матрицю, що отримується в результаті роботи методу Гаусса. При цьому очевидно, що трудомісткість отримання LU -факторізаціі буде такою ж- .

Розглянутий нами алгоритм LU-факторизації реалізований за допомогою виключення з колонки. Слід зазначити, що можна сформулювати аналогічний алгоритм, заснований на виключенні з рядку. Справді, основна ідея алгоритму за допомогою виключення з колонки полягає в тому, що на i-й ітерації провідна рядок з відповідними множниками віднімається з рядків, що лежать нижче, щоб занулити всі елементи матриці, розташовані в i-м стовпці нижче діагоналі. Тим часом можливо і інше: на кожній i-й ітерації можна вичитати з i-го рядка всі рядки, розташовані вище, помножені на відповідні коефіцієнти, так, щоб занулити всі елементи i-го рядка лівіше діагоналі. При цьому елементи матриці L нижче головної діагоналі і елементи матриці U на головній діагоналі і вище неї можна обчислювати на місці матриці А. Як і в разі виключення з колонки, наведена схема вимагає проведення операцій

Розглянемо тепер ще один спосіб LU-факторизації, званий компактної схемою. нехай матриця допускає LU-розкладання (7.6), де

тобто при а при . Зі співвідношення (7.6) випливає, що

Перетворимо цю суму двома способами:

Звідси знаходимо

Оцінка числа операцій даного алгоритму LUфакторізаці також становить

Якщо розкладання (7.6) отримано, то рішення системи (7.2) зводиться до послідовного розв'язування двох систем рівнянь з трикутними матрицями (зворотний хід)

Зворотний хід вимагає операцій.

Як випливає з наведених оцінок, обчислювальна складність методу виключення Гауса і методу LU-розкладання однакова. Однак якщо необхідно вирішити кілька систем з однаковими матрицями коефіцієнтів, але різними векторами вільних членів (права частина СЛАР), то метод LU-розкладання виявиться кращим, так як в цьому випадку немає необхідності проводити розкладання матриці коефіцієнтів багаторазово. Достатньо лише зберегти отримані трикутні матриці в пам'яті і, підставляючи різні вектора вільних членів, отримувати рішення методами прямого і зворотного підстановки. Це дозволить значно скоротити обсяг обчислень в порівнянні з методом Гаусса.