Ім'я файлу: Курсова робота_ТРСПО.docx
Розширення: docx
Розмір: 263кб.
Дата: 26.05.2022
скачати

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

Факультет кібербезпеки, комп’ютерної та програмної інженерії Кафедра комп’ютерних інформаційних технологій
КУРСОВА РОБОТА

з дисципліни

«Технології розподілених систем та паралельних обчислень» Варіант


Виконав:студент 4-го курсуСпеціальності:122

«Комп’ютерні науки»Групи УС-401БзІм’я,Прізвище
Роботуприйняв:к.т.н.,доцентТолстіковаО.В.

Київ 2022

КУРСОВА РОБОТА



Тема: «Чисельне розв’язання систем лінійних алгебраїчних рівнянь.

Автоматизація переводу алгоритму розв’язання систем лінійних алгебраїчних рівнянь у паралельну форму»



Мета роботи: Ознайомитися з чисельними методами розв’язання систем лінійних алгебраїчних рівнянь. Навчитися знаходити розв'язки СЛАР точними та наближеними методами. Розробити програмний проект для автоматизації переводу алгоритму розв’язання систем лінійних рівнянь у паралельну форму.

    1. Теоретичні відомості


      1. Загальні відомості

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

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

(1.1)

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

Запишемо систему рівнянь (1.1) у матричному вигляді:
(1.2)

де AX=B.

Розв’язати СЛАР означає знайти такі xj, що перетворюють кожне рівняння системи (1.1) в тотожність.

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

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

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

Отже, необхідною і достатньою умовою існування єдиного розв’язку СЛАР є: det A≠0, тобто визначник головної матриці системи повинен бути відмінним від нуля. Ця умова поширюється на СЛАР будь-якого порядку.

      1. Чисельні методи розв’язання СЛАР


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

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

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

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

До наближених (ітераційних) належать методи, які дозволяють отримати

розв'язок системи (1.1) у вигляді границі послідовності векторів , яка збігається до точного розв’язку системи, де:

Методом Крамера можна розв’язувати СЛАР будь-якого порядку n. Але зі зростанням n метод стає дуже громіздким, оскільки число арифметичних операцій для обчислення визначника приблизно рівна (n+1)!, а визначників є (n+1).

Можна знаходити розв’язок СЛАР (1.2) при m=n з використанням оберненої матриці А-1. Помноживши зліва рівняння (1.2) на А-1, одержуємо Х=А-1В. Однак за кількістю арифметичних операцій знаходження оберненої матриці не простіше за формули Крамера.

Найпоширенішим обчислювальним методом розв’язування СЛАР є метод, запропонований німецьким математиком Карлом Фрідріхом Гаусом.

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

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

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


(1.3)

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

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

      1. Метод Гауса з послідовним виключенням невідомих


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



Аналогічно виключимо з отриманої системи. Послідовно виключивши всі невідомі до , отримаємо систему трикутного вигляду:

(1.4)

Виконання описаної вище процедури прямого ходу можливе при умові, що

всі , не дорівнюють нулю.

У результаті зворотного ходу методу Гауса, виконуючи послідовні підстановки (починаючи з останнього рівняння) в системі (1.4), отримаємо всі значення невідомих:
.

Метод Гауса може бути легко реалізований на комп'ютері. Цей метод та його модифікації вирізняються меншою кількістю арифметичних дій, приблизно рівною n3. Однак, один з основних недоліків методу Гауса пов'язаний з тим, що при його реалізації накопичуються обчислювальні похибки, які спотворюють розв’язок великих погано обумовлених СЛАР.

Для вирішення цієї проблеми був створений метод QR-розкладу, що майже усунув ці похибки.

Однією з найбільш поширених модифікацій методу Гауса є метод LU-розкладу, що полягає у розкладі матриці СЛАР на добуток двох матриць, нижньої трикутної L та верхньої трикутної U: A=LU. Тоді систему AX=B розв’язують у два етапи: спочатку розкладають матрицю А на добуток LU (прямий хід методу Гауса), а потім послідовно розв’язують системи LY=B та UX=Y (зворотний хід).

QR-розклад полягає у розкладі матриці А на добуток дійсної ортогональної матриці Q і верхньої трикутної R. Поетапний розв’язок системи AX=B виконують так: спочатку обчислюють Y=Qт×B, а потім розв’язують систему RX=Y. QR-розклад є складнішим, ніж LU-розклад, а погано обумовлені системи не так часто зустрічаються. Для того, щоб зменшити зростання обчислювальної похибки застосовуються різні модифікації методу Гауса. Наприклад, метод Гауса з вибором головного елемента по стовпцях, в цьому випадку на кожному етапі прямого ходу рядка матриці переставляються таким чином, щоб діагональний кутовий елемент був максимальним.

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

      1. Метод простих ітерацій


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

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

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

Розглянемо метод простих ітерацій для розв’язування СЛАР.

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

З цією метою розв’яжемо перше рівняння системи (1.1) відносно , друге відносно і т. д. Отримаємо систему:

(1.5)
де , при ; , при ;

; ; .

Нульове наближення розв'язку системи (1.5) можна вибрати довільним.

Виберемо, наприклад, стовпчик вільних членів . Далі послідовно побудуємо матриці-стовпці наступних наближень розв’язку системи (1.5):

  • перше наближення,

  • друге наближення і т.д.

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

, (k = 0, 1, 2, …). (1.6)
У розгорнутому вигляді .

Якщо послідовність наближень має границю
, (1.7)

то ця границя є розв’язком системи (1.5).

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

Значно простішою для програмної реалізації є така формула методу простих ітерацій:

. (1.8)

Умови збіжності методу простих ітерацій

Розглянемо метод Зейделя для розв'язування СЛАР, що зведена до нормального вигляду (1.5).

Виберемо вектор початкових наближень



(наприклад, стовпець вільних членів ). Тоді проводимо уточнення значень невідомих чином:

  1. перше наближення:

  2. k + 1 наближення:



де k = 0, 1, 2, …, n.

Ітераційний процес методу Зейделя подібний до методу простих ітерацій.

Відмінним є те, що уточнені значення одразу ж підставляються в наступні рівняння. Отже, ітераційна формула методу Зейделя:
.

Тобто, метод Зейделя відрізняється від методу простих ітерацій тим, що при

обчисленні на (k+1)-му кроці враховуються значення , , , обчислені на цьому самому кроці.

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

Умова збіжності: метод Зейделя є збіжним, якщо виконується нерівність

, для всіх i=1, 2, ..., n.

і якщо хоча б для одного і ця нерівність строга

.

    1. Порядок виконання роботи:


  1. Ознайомитися з теоретичними відомостями.

  2. Обрати завдання згідно варіанту.

  3. Описати алгоритм розв’язку СЛАР (згідно варіанту).

  4. Зробити масштабування і розподіл підзадач по процесорах.

  5. Розробити програму для розв’язку СЛАР у звичайному (послідовному) та паралельному режимах виконання.

  6. Зробити аналіз роботи програми:

    • час виконання звичайного алгоритму;

    • час виконання паралельного алгоритму.

  7. Знайти розв'язок заданої СЛАР з точністю 10-6 методом простих ітерацій та методом Зейделя. Для цього спочатку забезпечити виконання умови збіжності ітераційного методу. Розробити блок-схему алгоритму та написати програму, яка забезпечить розв’язок СЛАР та виведення на екран результатів роботи. Порівняти кількість ітерацій для кожного з методів.

  8. Порівняти отримані розв'язки СЛАР.

  9. Зробити висновки про швидкість збіжності кожного з методів. Оформити звіт про виконання роботи.

Звіт повинен містити:

    • титульний лист;

    • тему, мету роботи, варіант завдання;

    • порядок виконання роботи;

    • результати всіх етапів обчислень;

    • блок-схему алгоритму та текст програми для розв'язання СЛАР заданим методом;

    • код програми;

    • результат виконання програми;

    • висновки.



    1. Варіанти завдань




Варіант

Система рівнянь

Метод


1




Матричний метод


2




Метод Крамера


3




Метод Гауса


4




Метод Якобі


5




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


6




Метод Халецького


7




Метод Гауса-Жордана


8




Метод Гауса- Халецького


9




Матричний метод


10




Метод Крамера


11




Метод Гауса


12




Метод Якобі


13




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


14




Метод Халецького


15




Метод Гауса-Жордана

    1. Контрольні запитання

  1. Сформулюйте необхідну і достатню умову існування єдиного розв’язку СЛАР.

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

  3. Яка умова збіжності ітераційного процесу?

  4. Опишіть порядок знаходження розв'язку СЛАР методом Зейделя.

  5. У чому полягає відмінність методів Зейделя та простої операції? Який з цих методів забезпечує більш точні результати і чому?

  6. У чому полягає метод LU-розкладу?

  7. У чому полягає метод оберненої матриці для розрахунку СЛАР?



Додатковийматеріал(пояснення)докурсовоїроботи:
Опис алгоритму Гауса(послідовний)

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

Початок алгоритму.


Прямий хід: Шляхом елементарнихперетвореньрядків (додавань до рядка іншого рядка, помноженого на число, і перестановок рядків) матриця приводиться до верхнього трикутного вигляду (ступінчатого вигляду).

З цього моменту починається зворотний хід.

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

Масштабування і розподіл підзадач по процесорах


  1. У разі, коли розмір матриці, яка описує систему лінійних рівнянь, виявляється більшим, ніж число доступних процесорів (тобто, n> p), базові підзадачі можна укрупнити, об'єднавши в рамках однієї підзадачі кілька рядків матриці.


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

  1. Основним видом інформаційної взаємодії підзадач є операція передачі даних від одного процесора всім процесорам обчислювальної системи.

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






скачати

© Усі права захищені
написати до нас