Введення
Ця курсова робота включає в себе три ітераційних методу рішення систем лінійних алгебраїчних рівнянь (СЛАР):
1. Метод Якобі (метод ітерацій).
2. Метод Холецкого.
3. Метод верхньої релаксації.
Також дана курсова робота включає в себе: опис методу, застосування методу до конкретної задачі (Аналіз), код програми вирішення перерахованих вище методів на мові програмування Borland C + + Builder 6.
Опис методу
Метод рішення завдання називають ітераційним , якщо в результаті отримують нескінченну послідовність наближень до вирішення. Основна перевага ітераційних методів полягає в тому, що точність шуканого рішення задається. Число ітерацій, яке необхідно виконати для отримання заданої точності, є основною оцінкою якості методу. За цим числом проводиться порівняння різних методів.
Головним недоліком цих методів є те, що питання збіжності ітераційного процесу вимагає окремого дослідження. Прикладом звичайних ітераційних методів служать: метод ітерацій (метод Якобі), метод Зейделя, метод верхніх релаксацій.
Почнемо з методу ітерацій або як його ще називають методу Якобі.
Існує сіcтема A В· x = f (1), де матриця A = [ a ij ] ( I, j = 1, 2, ... m ) має зворотну матрицю; x = ( x 1 , x 2 , x 3 , ... x m ) - вектор невідомих, f - вектор вільних членів. Систему (1) потрібно перетворити до наступного вигляду: (2) i = 1, 2, ..., m, де, , При цьому aii 0.
Значення суми вважається рівним 0, якщо верхня межа підсумовування менше нижнього. Тоді при i = 1 рівняння має вигляд: (3). У методі Якобі виходять із запису системи у вигляді (2), ітерації при цьому визначають наступним чином:, (n = 0, 1, ..., n0, i = 1, 2, ..., m) (4).
Початкові значення - (i = 0, 1, ..., m ) задаються довільно (В програмі ми це робимо, вводячи функцію по генерації випадкових чисел - В«randomВ»). Закінчення ітераційного процесу визначають або завданням максимального числа ітерацій n 0 , або наступною умовою:, де> 0. В якості нульового наближення в системі (4) приймемо.
Якщо послідовність наближень x 1 (0) , x 2 (0) , ..., x m (0) , x 1 (1) , x 2 (1) , ..., x m (1) , ... , x 1 (k) , x 2 (k) , ... , x m (k ) має межу,, то ця межа є рішенням системи (2).
Достатньою умовою збіжності розв'язку системи (1) є те, що матриця A є матрицею з переважаючими діагональними елементами, тобто, i = 1, 2, ..., m.
Тепер розглянемо другий ітераційний метод - метод Зейделя , який є модифікацією методу Якобі. Основна його ідея полягає в тому, що при обчисленні ( k +1) - го наближення невідомою x i враховуються вже обчислені раніше ( k +1) - е наближення ( x 1 x 2 , ..., x i-1 ).
Нехай дана наведена лінійна система: ( i = 1, 2, ... n ) (5). Вибираються довільно початкові наближення коренів x 1 (0) , x 2 (0) , ..., x n (0 ) , щоб вони в якійсь мірі відповідали невідомим x 1 , x 2 , x 3 , ..., x n .
Передбачається, що k -е наближення коренів відомо, тоді в відповідності з ідеєю методу будується ( k +1) - е наближення за наступними формулами:
k = 0,1,2, ... (6)
Якщо виконується достатня умова збіжності для системи (5) - по рядках, то в методі Зейделя вигідно розташувати рівняння (6) так, щоб перше рівняння системи мало найменшу суму модулів коефіцієнтів:.
Тепер розглянь 3 метод - метод верхніх релаксацій .
Метод верхньої релаксації - це є метод Зейделя із заданим числовим параметром w.
Одним з найбільш поширених однокрокових методів є метод верхніх релаксацій, який має наступний вигляд (7), де w заданий числовий параметр (0
Гідністю ітераційного методу верхніх релаксацій є те, що при його реалізації програмним шляхом алгоритм обчислень має простий вигляд і дозволяє використовувати всього один масив для невідомого вектора.
Для отримання розрахункових формул (7) перепишемо у вигляді: або в компонентної записи отримаємо (8) - це є основна обчислювальна формула.
У вираз (8) і входять однаковим чином => при обчисленнях вони можуть бути записані в один і той же масив. При реалізації методу верхніх релаксацій використовується наступна форма запису алгоритму обчислень.
Дійсно, при послідовному знаходженні елемента (i +10 ітерації) на кожному кроці будуть використовуватися знайдені раніше значення, які при k
Застосування методу до конкретної задачі (аналіз)
Складаючи завдання на мові програмування Borland C + + Builder 6 для реалізації точних методів розв'язку СЛАР я враховував різну кількість рівнянь в системі (розмірність матриці задавав рівним nxn). Але для перевірки результатів використовував систему рівнянь:
Взагалі кажучи, процес Зейделя сходиться швидше, ніж метод Якобі. Буває, що процес Зейделя сходиться, коли проста ітерація розходиться і т.п. Правда, буває і навпаки. У всякому разі, достатні умови збіжності для методу Якобі достатні і для збіжності методу Зейделя. Реалізувавши програми з отриманого відповіді я побачив, що процес Зейделя сходиться швидше. Це видно з кількості ітерацій отриманих в програмі при наближеною точності = 0,000001. Якщо для методу Якобі вони становлять 16, то для методу Зейделя вони становлять 9.
Також розглядаючи метод верхньої релаксації і порівнюючи його з двома іншими методами видно, що в методі верхньої релаксації кількість ітерацій залежить від заданого числового параметра w. Ставлячи w = 1, кількість ітерацій дорівнює 9, зменшуючи значення параметра від 1 кількість ітерацій починає рости, в свою чергу збільшуючи параметр кількість ітерацій теж починає зростати.
Наведемо таблицю показують кількість ітерацій (k) при різних значеннях параметра w:
w
0.1
0.4
0.8
0.9
1
1.1
1.2
1.3
1.7
1.9
k
16
15
14
13
9
13
14
|
