Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Многосеточних метод



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


Основи методу

Припустимо, що необхідно вирішити систему виду

Au = f,

де A - n \ times n матриця з елементами a_ {ij} . Для зручності зіставимо індекси з вузлами сітки, таким чином u_i являє собою значення u у вузлі i . Безліч вузлів сітки позначимо як \ Omega = \ left \ {1, \, 2, \, \ dots, \, n \ right \} . Основна ідея многосеточних методів полягає в тому, що помилка e , Яка не може бути усунена методами релаксації, повинна бути прибрана за допомогою корекції з рішення на грубій сітці.

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

  • Послідовність сіток \ Omega = \ Omega ^ 1 \ supset \ Omega ^ 2 \ supset \ dots \ supset \ Omega ^ M , Причому \ Omega ^ k = C ^ k \ cup F ^ k, \ quad C ^ k \ cap F ^ k = \ emptyset, \ quad \ Omega ^ {k +1} \ equiv C ^ k .
  • Сіткові оператори A = A ^ 1, \, A ^ 2, \, \ dots, \, A ^ M .
  • Оператори інтерполяції P ^ k, k = 1, \, 2, \, \ dots, \, M-1 .
  • Оператори згладжування S ^ k, k = 1, \, 2, \, \ dots, \, M-1 .

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

Етап побудови
  1. Прирівняти k = 1 .
  2. Розділити \ Omega ^ k на непересічні безлічі C ^ k і F ^ k .
    1. Прирівняти \ Omega ^ {k +1} = C ^ k .
    2. Побудувати оператор інтерполяції P ^ k .
  3. Побудувати A ^ {k +1} = \ left (P ^ k \ right) ^ T A ^ k P ^ k .
  4. Побудувати якщо необхідно S ^ k .
  5. Якщо сітка \ Omega ^ k досить мала, дорівняти M = k +1 і зупиниться. Інакше k = k + 1 і перехід на крок 2.

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

Алгоритм: MGV \ left (A ^ k, \, P ^ k, \, S ^ k, \, u ^ k, \, f ^ k \ right)
Якщо k = M , Вирішити A ^ M u ^ M = f ^ M використовуючи прямий метод.
Інакше:
Застосувати метод релаксації S ^ k\ Mu_1 раз до A ^ k u ^ k = f ^ k .
Зробити корекцію на грубій сітці:
Обчислити r ^ k = f ^ k - A ^ k u ^ k .
Обчислити r ^ {k +1} = \ left (P ^ k \ right) ^ T r ^ k .
Застосувати MGV \ left (A ^ {k +1}, \, P ^ {k +1}, \, S ^ {k +1}, \, e ^ {k +1}, \, r ^ {k +1 } \ right) .
Оновити рішення u ^ k = u ^ k + P ^ k e ^ {k +1} .
Застосувати метод релаксації S ^ k\ Mu_2 раз до A ^ k u ^ k = f ^ k .

Вищенаведений алгоритм описує V \ left (\ mu_1, \, \ mu_2 \ right) - Цикл.

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

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

Складність оператора C_ {op} розраховується як відношення кількості ненульових елементів у всіх матрицях A_k, \, k = 1, \, 2, \, \ dots, \, n до кількості ненульових елементів в матриці першого рівня A ^ 1 = A .



Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Метод
Метод Фолля
Метод Остроградського
Метод Ейлера
Метод Бекона
Метод опитування
Метод Брінелля
Метод Чохральського
Метод Грама
© Усі права захищені
написати до нас
Рейтинг@Mail.ru