Алгоритмічна і програмна реалізація метода подвійної факторизації

Розв’язуємо систему лінійних рівнянь за формулою (3.1) з використанням оберненої матриці коефіцієнтів . Для обернення матриці застосовуємо метод подвійної факторизації. Виконується два етапи обчислень:

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

б) розв’язання системи лінійних рівнянь і обчислення значень невідомих Х.

Можливі два варіанти реалізації. Перший передбачає обчислення оберненої матриці перемноженням факторних матриць відповідно до (3.2), а потім визначення Х із (3.1). Другий варіант об’єднує (3.1) та (3.2) і полягає в послідовному множенні кожної із факторних матриць на вектор вільних членів В в зворотному порядку (від до і від до ). Результат кожного множення розміщується в поле масиву В.

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

Процес перемноження факторних матриць при розв’язанні системи рівнянь можна поділити на 2 етапи:

 

а)

б)

 

Перемноження матриці на вектор виконується за відомою схемою:

 

		B
	L

…

 

		…
		…	*
…	…	…	…
		…

 

…

 

 

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

Після реалізації цих обчислень в масиві В будуть знаходитись значення Х, які є розв’язком системи рівнянь. Отриманий результат треба вивести на екран і у файл.

Для перевірки правильності розв’язання системи необхідно підставити обчислені значення у вихідну систему і виконати перемноження.

 

Алгоритм і програма подвійної факторизації матриці використовують такі масиви і змінні:

а - елементи матриці А ( двомірний масив розмірністю );

n - кількість рядків і стовпців матриці;

k - номер кроку факторизації (k=1,…,n);

i, j - номер рядка і номер стовпця матриці.

На вході програми - двомірний масив - вихідна матриця коефіцієнтів А, на виході – факторизована матриця .

 

1. Опорний елемент відповідно до (3.3);

2. Елемент матриці відповідно (3.3);

3. Інші елементи рядка і відповідно до (3.5);

4. Елемент матриці відповідно до (3.4);

Програмна реалізація:

…

for k:=1 to n do

Begin

a[k,k]:=1/a[k,k];

for i:=k+1 to n do

Begin

a[i,k]:= - a[i,k]*a[k,k];

for j:=k+1 to n do

a[i,j]:=a[i,j]+a[i,k]*a[k,j];

End;

For j:=k+1 to n do

a[k,j]:= - a[k,j]*a[k,k];

end;

…

 

Алгоритм і програма розв’язання СЛАР використовують такі змінні і масиви:

А - елементи факторизованої матриці (двомірний масив розмірністю );

в - елементи допоміжного масиву В ( одномірний масив );

n - кількість рядків і стовпців у масивах ;

k - номер кроку факторизації.

 

1. Перемноження лівих факторних матриць (k=1,…,n).

На вході фрагмента програми - факторизована матриця (її елементи, що

відповідають факторним матрицям ) і вектор B (одномірний масив). На виході - масив В, елементи якого містять результат перемноження всіх

лівих факторних матриць на вектор вузлових струмів.

 

Алгоритм: Програмна реалізація:

…

For k:=1 to n do

Begin

for j:=n downto k+1 do

B[j]:=B[j]+A[j,k]*B[k];

B[k]:=A[k,k]*B[k];

End;

…

 

 

2. Перемноження правих факторних матриць (k=n-1,…,1). На вході фрагмента програми - факторизована матриця (її елементи, що відповідають факторним матрицям ) і вектор В. На виході - масив В, елементи якого є розв’язком системи рівнянь.

 

Алгоритм:

 

Програмна реалізація:

…

for k:=n-1 downto 1 do

Begin

For j:=n downto k+1 do

B[k]:=B[k]+a[k,j]*B[j];

End;

…

 

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

Виконати завдання Заняття № 2 (розділ 2.3), застосовувавши для розв’язання заданної СЛАР метод подвійної факторизації.

 

 

Заняття № 4

Розробка програми

Розв’язання системи нелінійних алгебраїчних рівнянь (СНАР)

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

Мета роботи: Закріплення знань із застосування ітераційних методів для чисельного розв’язання СНАР, вивчення алгоритмів метода Зейделя і простої ітерації, розробка відповідної комп’ютерної програми на мові Pascal і застосування її для розв’язання заданої системи рівнянь.

 

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

Методи простої ітерації і Зейделя для розв’язання СНАР

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

У загальному вигляді нелінійну систему рівнянь можна записати:

(4.1)

Для її розв’язання методами простої ітерації і Зейделя, систему необхідно перетворити: розв’язати кожне і - те рівняння системи відносно відповідної невідомої величини

Перетворена система набуває загального вигляду:

(4.2)

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

При цьому ітераційна форма запису системи має вигляд:

(4.3)

Підставивши в (4.3) нове наближення невідомих і виконавши обчислення, знаходимо нові значення невідомих і т.д. Це відповідає послідовності розрахунків за методом простої ітерації. Більш ефективним по показниках збіжності є модифікація методу простої ітерації - метод Зейделя.

Відмінність методу Зейделя полягає в тому, що для визначення чергового (к+1)- го наближення і - го невідомого використовуються ( к+1 ) -і наближення невідомих , що обчислені на цій же (к+1 ) -й ітерації, а також к -ті наближення невідомих обчислених на попередній к -ій ітерації.

Система рівнянь (4.3) при розв’язанні її методом Зейделя набуває вигляду:

(4.4)

Ітерації повторюються доти, поки не стане виконуватись умова (1.6) для всіх невідомих, або умова (1.7) - для всіх рівнянь системи.

 

Послідовність дій при розв’язанні СНАР методом Зейделя:

1. Перетворення вихідної системи у форму (4.2) і запис її в ітераційній формі (4.4).

2. Визначення початкового наближення невідомих

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

:

 

 

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

3. Обчислення наступного наближення невідомих.

Підставляємо вибрані наближення коренів (на 1-й ітерації – це початкові наближення) у перше рівняння системи (4.4) і обчислюємо . Із другого рівняння отримаємо , використовуючи нове значення і наближення невідомих із попередньої ітерації Із наступних рівнянь отримаємо (к+1 )- і наближення всіх інших невідомих.

4. Контроль завершення ітераційного процесу за умовами досягнення заданої точності .

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

 

Приклад розв’язання СНАР методом Зейделя

Знайти корені системи 3-х нелінійних рівнянь з трьома невідомими. Точність .

Система рівнянь у формі (4.1):

Перетворюємо систему у форму (4.2):

Записуємо систему в ітераційній формі по методу Зейделя:

Вибираємо початкові наближення невідомих =0.

Ітерація 1. Визначаємо перші наближення невідомих:

Нев’язки рівнянь при цих наближеннях:

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