Метод прогонки

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод прогонки, також відомий як алгоритм Томаса, дозволяє розв'язувати СЛАР з трьохдіагональною матрицею, і є спрощенням методу Гауса для таких обмежень. Працює за лінійний час.

Система має такий вигляд:

де та . В матричній формі це записується так:

В цілому, метод не є числово стійким, але є таким у декількох випадках, таких як діагонально панівна матриця або додатноозначена матриця.[1]

Розв'язок[ред.ред. код]

Розв'язок проводиться в два кроки, як і в методі Гауса, прямому, та зворотному. В прямому ході ми обчислюємо:

та

Тепер розв'язок знаходимо зворотнім ходом:

Код на 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];
}

Отримання[ред.ред. код]

Отримання методу вимагає ручного виконання деяких спеціалізованих Гаусових вилучань.

Припустимо, що невідомі - це , і що рівняння до розв'язання такі:

Розглянемо таку зміну другого () рівняння за допомогою першого рівняння:

що дасть:

у висліді маємо, що було вилучено з другого рівняння. Використовуючи подібну тактику зі зміненим другим рівнянням, щодо третього маємо:

Цього разу було вилучено якщо повторювати цю процедуру до рядка ; (змінене) рівняння міститиме лише одну змінну, . Таке рівняння ми можемо розв'язати і використати результат для того, щоб розв'язати рівняння і так далі допоки всі невідомі не знайдені.

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

Для дальшого пришвидшення процесу, можна нормувати діленням (якщо немає ризику ділення на число занадто близьке до нуля), тепер змінені коефіцієнти позначені рисочкою будуть:

це дає нам наступну систему з тими самими невідомими і коефіцієнтами вираженими через початкові:

Останнє рівняння містить лише одне невідоме. Розв'язуючи його, приводимо наступне останнє рівняння до одного невідомого. І так далі:

Примітки[ред.ред. код]

  1. Pradip Niyogi (2006). Introduction to Computational Fluid Dynamics. Pearson Education India. с. 76. ISBN 978-81-7758-764-7.