Размещено на http://www.allbest.ru/

Зміст

• 1. Огляд існуючих алгоритмів
• 1.1 Опис алгоритмів для вирішення поставленої задачі
• 1.1.1 Метод Гаусса
• 1.1.2 Метод Гаусса-Зейделя
• 1.1.3 Метод Зейделя
• 1.1.4 Метод Якобі
• 1.2 Програмна реалізація алгоритму (послідовна програма)
• 1.3 Аналіз поставленої задачі на доцільність розпаралелювання
• 2. Розробка паралельного алгоритму
• 2.1 Виконання основних етапів побудови паралельного алгоритму
• 2.2 Алгоритм роботи потоків
• Додатки

1. Огляд існуючих алгоритмів

1.1 Опис алгоритмів для вирішення поставленої задачі

1.1.1 Метод Гаусса

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

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

Розглянемо застосування метода Гаусса для системи

(1.1)

Для виключення з другого рівняння додамо до нього перше, помножене на . Потім, помноживши перше рівняння на і додавши результат до третього рівняння, також виключимо з нього . Отримаємо рівнозначну систему рівнянь вигляду

(1.2)

Тепер з третього рівняння системи (1.2) треба виключити . Для цього помножимо друге рівняння на і додамо результат до третього. Отримаємо

(1.3)

Матриця системи (1.3) має трикутний вигляд. На цьому закінчується прямий хід метода Гаусса. Відмітимо, що в процесі виключення невідомих доводиться виконувати операції ділення на коефіцієнти , , і т.д. Тому вони мають бути відмінними від нуля; в іншому випадку необхідно відповідним чином переставити рівняння системи. Переставляння рівнянь повинна бути передбачена в обчислювальному алгоритмі при його реалізації на ПК. Зворотній хід починається з розв'язання третього рівняння системи (1.3):

(1.4)

Використовуючи це значення, можна знайти з другого рівняння, а потім з першого:

(1.5)

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

1.1.2 Метод Гаусса-Зейделя

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

(1.6)

Припустимо, що діагональні елементи , , відмінні від нуля (в іншому випадку можна переставляти рівняння). Виразимо невідомі , , відповідного з першого, другого і третього рівнянь системи (1.6):

₍1.7), ₍1.8)

₍1.9)

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

Задамо деякі початкові (нульові) наближення невідомих: , , . Підставляючи ці значення в праву частину виразу (1.7), отримуємо нове (перше) наближення для :

₍1.10)

Використовуючи це значення для і наближення для , знаходимо з (1.8) перше наближення для :

(1.11)

І нарешті, використовуючи обчислені значення ,, знаходимо за допомогою виразу (1.11) перше наближення для :

(1.12)

На цьому закінчується перша ітерація розв'язання системи (1.7) - (1.9). Використовуючи тепер значення , , , можна таким же чином провети другу ітерацію, в результаті якої будуть знайдені другі наближення до розв'язку: , , і т.д. Наближення з номером можна представити у вигляді

(1.13)

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

1.1.3 Метод Зейделя

Метод Зейделя є класичним ітераційним методом вирішення системи

лінійних рівнянь. Візьмемо систему:

(1.14)

де , Або (1.15)

Перепишемо завдання у вигляді:

(1.16)

Тут в j-м-коді рівнянні ми перенесли в праву частину всі члени, xi, що містять, для i > j. Цей запис може бути представлений: (1.17)

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

(1.18)

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

(1.19)

де

Таким чином i-танучи компонента (до + 1) - го наближення обчислюється за формулою:

(1.20)

Умова закінчення ітераційного процесу Зейделя досягши точності в спрощеній формі має вигляд: (1.21). Точніша умова закінчення ітераційного процесу має вигляд (1.21) і вимагає більше обчислень. Добре підходить для розріджених матриць.

1.1.4 Метод Якобі

Метод Якобі складається з ланцюжка ортогональних перетворень подібності матриці. Кожне перетворення (ротація Якобі) - це плоский поворот з метою обнулення одного з позадіагональних елементів матриці. Послідовні перетворення не зберігають вже встановлені нульові елементи, але в той же час позадіагональні елементи стають менше і менше до тих пір, поки матриця не стане діагональною з точністю до машинного нуля. Накопичення в процесі перетворень твору трансформаційних матриць дає матрицю власних векторів, тоді як діагональні елементи є власними значеннями. Метод Якобі завжди є робустним для дійсних симетричних матриць. Для матриць розміру, скажемо більше 10, цей алгоритм повільніший, ніж метод QR (див. нижчий). Проте алгоритм Якобі значно простіший за інші ефективніші методи, таким чином він рекомендується у випадках, коли час виконання не є критичним. Базова матриця ротації Якобі має вигляд:

P_pq = (1₎

(…)

(c…s)

(…1…)

(-s…c)

(…) (1.22) (1)

Всі діагональні елементи матриці ротації Якобі дорівнюють 1, за винятком двох елементів в рядках (і стовпцях) p і q.

Всі позадіагональні елементи дорівнюють нулю, за винятком двох елементів, рівних s і (-s). Числа з і s є косинусом і синусом кута повороту f, так що c2+s2=1.

Ротація Якобі перетворить матрицю A згідно з формулою:

A' = P_pq^TAP_pq. (1.23)

Множення PPQTA змінює лише рядки p і q матриці A, тоді як Appq міняє лише стовпці p і q. Відзначимо, що нижні індекси p і q в позначенні Ppq не означають елемент цієї матриці, а швидше індексують типа ротації, тобто плоскість, в якій вона відбувається. Таким чином, змінені елементи в матриці A'' розташовані лише в рядках і стовпцях p і q:

(. a'_1p. a'_1q.)

(…...)

(a'_p1. a'_pp. a'_pq. a'_pn)

A' = (...)

(a'_q1. a'_qp. a'_qq. a'_qn)

(…...)

(. a'_np … a'_nq.) (1.24)

Для змінених елементів матриці (з врахуванням приведеного вище і її симетрії) виходять явні формули:

a'_rp = ca_rp - sa_rq (r! =p, r! =q) a'_rq = ca_rq + sa_rp (r! =p, r! =q) a'_pp = c²a_pp + s²a_qq - 2csa_pq a'_qq = s²a_pp + c²a_qq + 2csa_pq a'_pq = (c^{2 -} s²) a_pq + cs (a_pp - a_qq)

Ідея методу Якобі в тому, щоб постаратися обнулити позадіагональні елементи серією ротацій. Для того, щоб обнулилося a''pq, кут ротації, згідно з формулами, приведеними вище, має бути наступним:

q = cot (2f) = (c2 - s2) / (2cs) = (aqq - app) / (2apq). Вважаючи t=s/c, для визначення t прийдемо до наступного рівняння: t2 + 2tq - 1 = 0. Менший по модулю корінь цього рівняння відповідає обертанню на кут, менший p/4; вибір цього кута на кожній із стадій дає найбільш стійкий алгоритм.

Використовуючи формулу для вирішення квадратного рівняння з дискримінантом в знаменнику, менший корінь визначається як:

t = sign (q) / (|q|+sqrt (q²+1)). (1.25)

Якщо величина q така, що q2 дасть переповнювання, вважаємо t = 1/ (2q). За значенням t визначаються з і s:

c = 1/sqrt (t²+1), s = tc. (1.26)

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

a'_pp = a_pp - ta_pq a'_rp = a_rp - s (a_rq + ga_rp) a'_rq = a_rq + s (a_rp - ga_rq), (1.27)

де t (тангенс половини кута повороту) визначається, як t = s/ (1+c). Збіжність методу Якобі можна оцінити, розглядаючи суму квадратів позадіагональних елементів S; рівняння перетворень дають для цієї суми після трансформації наступне співвідношення: S = Sr! =s (|ars|2); S'' = S - 2|apq|2. Оскільки перетворення ортогональні, сума діагональних елементів при цьому зростає відповідно на |apq|2.

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

Після ланцюжка перетворень виходить матриця D, діагональна з точністю до машинного нуля. Її діагональні елементи утворюють власні значення первинної матриці A, оскільки виконується D = VTAV, де V = P1p2p3., а Pi - матриці ротації Якобі. Стовпці матриці V є власними векторами. Вони обчислюються рекурентно, на кожній стадії по формулах: V'' = Vpi, де спочатку V - одинична матриця. Для перетворення елементів V використовуються формули:

v'_rs = v_rs (s! =p, s! =q) v'_rp = cv_rp - sv_rq v'_rq = sv_rp + cv_rq (1.28)

Для зменшення помилки округлення наведені вище формули слід переписати в термінах g (як вище для елементів матриці A). Єдиним питанням, що залишається, тепер є стратегія, по якій потрібно перебирати знищувані елементи. Оригінальний алгоритм Якобі від 1846 року на кожній стадії шукав у верхньої трикутної області найбільший по модулю елемент і обнуляв його. Це вельми раціональна стратегія для ручного рахунку, але вона неприйнятна для комп'ютера, оскільки робить число операцій на кожній стадії ротації Якобі порядку N2 замість N. Для наших цілей кращою стратегією є циклічний метод Якобі, де елементи віддаляються в строгому порядку. Наприклад, можна просто проходіть по рядках: P12, P13. P1n; P23,.,p2n;. Можна показати, що швидкість збіжності буде в загальному випадку квадратичною, як для оригінального, так і для циклічного методу Якобі. Назвемо одне така безліч послідовних n (n-1) /2 перетворень Якобі проходом. Програма, поміщена нижче, містить дві тонкість: На перших трьох проходах ми проводимо ротацію відносно індексу (pq) лише тоді, коли |apq|>e для деякого порогового значення e = S0/ (5n2), де S0 - сума модулів позадіагональних елементів верхньої трикутної матриці.

Після чотирьох проходів у тому випадку, коли |apq|<<|app| і |apq|<<|aqq|, вважаємо |apq|=0 і пропускаємо ротацію. Критерієм порівняння є перевищення діагональних елементів в 10D+2 рази, де D - число значущих десяткових цифр. У приведеній нижче програмі симетрична матриця а розміром (n x n) на вході завантажена в масив а [1. n] [1. n]. На виході наддіагональні елементи а руйнуються, але діагональні і піддіагональні залишаються на місці з тим, щоб зберегти інформацію про початкову симетричній матриці. Вектор d [1. n] повертає власні значення а. Під час обчислення він містить поточну діагональ. Матриця v [1. n] [1. n] повертає набір нормалізованих власних векторів, що відносяться до d [k] для її к-го стовпця. Параметр nrot - число ротацій Якобі, необхідних для досягнення збіжності. Типові матриці вимагають від 6 до 10 проходів для досягнення збіжності, або від 3n2 до 5n2 ротацій. Кожна ротація вимагає порядку 4n операцій множення і складання, так що загальні витрати мають порядок від 12n3 до 20n3 операцій. При обчисленні власних векторів поряд з власними значеннями, число операцій на ротації зростає з 4n до 6n, що означає перевищення лише на 50 відсотків.

1.2 Програмна реалізація алгоритму (послідовна програма)

Рисунок 1.1 - Блок - схема алгоритму послідовної програми

Рисунок 1.2 - Режим тестування

1.3 Аналіз поставленої задачі на доцільність розпаралелювання