Опис існуючих алгоритмів. Приведення матриці системи до трикутного вигляду в основі методу Гаусса, його зворотній хід. Сутність методів Гаусса-Зейделя, Зейделя, Якобі. Програмна реалізація алгоритму (послідовна програма). Розробка паралельного алгоритму.
Аннотация к работе
Спочатку за допомогою першого рівняння виключається зі всіх наступних рівнянь системи. Потім за допомогою другого рівняння виключається з третього і всіх наступних рівнянь. Цей процес, який називається прямим ходом метода Гаусса, продовжується до тих пір, поки в лівій частині останнього (-го) рівняння не залишиться лише член з невідомим , тобто матриця системи не буде приведена до трикутного вигляду. Зворотній хід метода Гаусса полягає у послідовному обчисленні шуканих невідомих: розвязуючи останнє рівняння, знаходимо єдине невідоме . Потім, помноживши перше рівняння на і додавши результат до третього рівняння, також виключимо з нього .Одним з найпоширеніших ітераційних методів, який відрізняється простотою та легкістю програмування, є метод Гаусса-Зейделя. Проілюструємо спочатку цей метод на прикладі розвязання системи Підставляючи ці значення в праву частину виразу (1.7), отримуємо нове (перше) наближення для : (1.10) Використовуючи це значення для і наближення для , знаходимо з (1.8) перше наближення для : (1.11)Тут в j-м-коді рівнянні ми перенесли в праву частину всі члени, xi, що містять, для i > j. Цей запис може бути представлений: (1.17) де в прийнятих позначеннях D означає матрицю, в якої на головній діагоналі коштують відповідні елементи матриці A, а всі останні нулі; тоді як матриці U і L містять верхню і ніжнюю трикутні частини Ітераційний процес в методі Зейделя будується по формуліПослідовні перетворення не зберігають вже встановлені нульові елементи, але в той же час позадіагональні елементи стають менше і менше до тих пір, поки матриця не стане діагональною з точністю до машинного нуля. Всі діагональні елементи матриці ротації Якобі дорівнюють 1, за винятком двох елементів в рядках (і стовпцях) p і q. Всі позадіагональні елементи дорівнюють нулю, за винятком двох елементів, рівних s і (-s). Ротація Якобі перетворить матрицю Відзначимо, що нижні індекси p і q в позначенні Ppq не означають елемент цієї матриці, а швидше індексують типа ротації, тобто плоскість, в якій вона відбувається.Такі системи рівнянь можуть бути, по-перше, дуже великого розміру, наприклад, Nxn=10000х10000, і навіть більше по-друге, система рівнянь може виявитися недовизначеною; по-третє, вона може виявитися з лінійно залежними рівняннями; по-четверте, вона може виявитися перевизначеною і неспільною.Методика розробки паралельних алгоритмів включає етапи виділення підзадач, визначення інформаційних залежностей, масштабування й розподілу підзадач по процесорах обчислювальної системи. Ці процеси ще називаються декомпозицією, проектуванням взаємодії між задачами, обєднанням та плануванням обчислень. На цьому етапі поставлене завдання аналізується і розбивається на підзадачі, виконання яких може бути паралельним. Вимоги, яким повинен задовольняти обираний підхід, звичайно полягають у забезпеченні рівного обсягу обчислень у виділюваних підзадачах і мінімуму інформаційних залежностей між цими підзадачами (за інших рівних умов потрібно віддавати перевагу рідким операціям передачі повідомлень більшого розміру в порівнянні із частими пересиланнями даних невеликого обсягу). На цьому етапі визначаються дії та методи, які потрібні для організації взаємодії між задачами (передавання даних, забезпечення синхронізації, доступ до спільних даних тощо).Після завершення виконання основних етапів побудови паралельного алгоритму, необхідно перейти до планування обчислень, тобто виконання розподілу задач по процесорам компютерної системи. Даний пункт виконується у відповідності з етапами, виконаними вище. В цьому алгоритмі таблично описуються операції, що повинні виконуватися кожним з потоків багатопоточної програми: вводи та виводи даних, операції над ними та над самими потоками. У відповідності з отриманим алгоритмом вже програмно оформлюється код програми. Розподіл задач між потоками дозволяє значно спростити процес написання програми, оскільки на цьому етапі вже стає видно помилки, допущені під час проектування, декомпозиції та обєднання.
План
Зміст
1. Огляд існуючих алгоритмів
1.1 Опис алгоритмів для вирішення поставленої задачі