Метод прогонки, також відомий як алгоритм Томаса, дозволяє розв'язувати СЛАР з (Тридіагональною матрицею), і є спрощенням методу Гауса для таких обмежень. Працює за лінійний час.
Система має такий вигляд:
де та . В матричній формі це записується так:
В цілому, метод не є числово стійким, але є таким у декількох випадках, таких як діагонально панівна матриця або додатноозначена матриця.
Розв'язок
Розв'язок проводиться в два кроки, як і в методі Гауса, прямому, та зворотному. В прямому ході ми обчислюємо:
та
Тепер розв'язок знаходимо зворотнім ходом:
Код на C
/* Розв'язок повертається в x. c та d модифікуються!*/ void TridiagonalSolve (const double *a, const double *b, double *c, double *d, double *x, unsigned int n){ /* Modify the coefficients. */ c[0] /= b[0];/* Division by zero risk. */ d[0] /= b[0];/* Division by zero would imply a singular matrix. */ for (unsigned int i = 1; i < n; i++){ double id = 1 / (b[i] - c[i-1] * a[i]); /* Division by zero risk. */ c[i] *= id; /* Last value calculated is redundant. */ d[i] = (d[i] - d[i-1] * a[i]) * id; } /* Now back substitute. */ x[n - 1] = d[n - 1]; for (int i = n - 2; i >= 0; i--) x[i] = d[i] - c[i] * x[i + 1]; }
Доведення
Доведення методу вимагає ручного виконання деяких спеціалізованих Гаусових вилучань.
Припустимо, що невідомі - це , і що рівняння до розв'язання такі:
Розглянемо таку зміну другого () рівняння за допомогою першого рівняння:
що дасть:
у висліді маємо, що було вилучено з другого рівняння. Використовуючи подібну тактику зі зміненим другим рівнянням, щодо третього маємо:
Цього разу було вилучено якщо повторювати цю процедуру до рядка
; (змінене) рівняння
міститиме лише одну змінну,
. Таке рівняння ми можемо розв'язати і використати результат для того, щоб розв'язати рівняння
і так далі допоки всі невідомі не знайдені.
Очевидно, що коефіцієнти у змінених рівняннях ставатимуть все більш заплутаними якщо розписувати їх явно. Але змінені коефіцієнти (з тильдою) можна виразити рекурсивно:
Для дальшого пришвидшення процесу, можна нормувати діленням (якщо немає ризику ділення на число занадто близьке до нуля), тепер змінені коефіцієнти позначені рисочкою будуть:
це дає нам наступну систему з тими самими невідомими і коефіцієнтами вираженими через початкові:
Останнє рівняння містить лише одне невідоме. Розв'язуючи його, приводимо наступне останнє рівняння до одного невідомого. І так далі:
Примітки
- Pradip Niyogi (2006). Introduction to Computational Fluid Dynamics. Pearson Education India. с. 76. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет