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

Використовуючи верхній індекс як номер рівня введемо наступні позначення:

Послідовність сіток , причому

Сіткові оператори A=A¹ ,A² ,…,A^M .

Оператори інтерполяції P^k , k=1,2,…,M-1.

Оператори згладжування S^k , k=1,2,…,M-1.

Усі ці компоненти багатосіткового методу будуються на першому етапі, відомому як етап побудови.

Етап побудови.

Дорівняти k=1.

Розділити Ω^k на непересічні множини C^k і F^k .

Дорівняти Ω^k+1 =C^k .

Побудувати оператор інтерполяції P^k .

Побудувати A^{k +1} =(P^k )^T A^k P^k .

Побудувати якщо необхідно S^k .

Якщо сітка Ω^k досить мала, дорівняти M=k+1 і зупинитися. Інакше k=k+1 і перехід на крок 2.

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

Алгоритм: MGV(A^k , P^k , S^k , u^k , f^k ).

Якщо k=M, розв'язати A^M u^M =f^M використовуючи прямий метод.

Інакше.

Застосувати метод релаксації S^k μ₁ раз до A^k u^k =f^k .

Зробити корекцію на грубій сітці.

Обчислити r^k =f^k −A^k u^k .

Обчислити r^{k +1} =(P^k )^T r^k .

Застосувати MGV(A^{k +1} , P^{k +1} , S^{k +1} , e^{k +1} , r^{k +1} ).

Обновити розв’язок u^k =u^k +P^k e^k +1.

Застосувати метод релаксації S^k μ₂ раз до A^k u^k =f^k .

Вищенаведений алгоритм описує V(µ₁ , µ₂ ) – цикл.

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

Складність оператора C_op розраховується як відношення кількості ненульових елементів у всіх матрицях A_k , k=1,2,…,n до кількості ненульових елементів у матриці першого рівня A¹ =A.

1.2. 5 Метод Ланцоша