Метод прогонки, також відомий як алгоритм Томаса, дозволяє розв'язувати СЛАР з Тридіагональною матрицею, і є спрощенням методу Гауса для таких обмежень. Працює за лінійний час.
Система має такий вигляд:
де та . В матричній формі це записується так:
В цілому, метод не є числово стійким, але є таким у декількох випадках, таких як діагонально панівна матриця або додатноозначена матриця.
Розв'язок Розв'язок проводиться в два кроки, як і в методі Гауса, прямому, та зворотному. В прямому ході ми обчислюємо:
та
Тепер розв'язок знаходимо зворотнім ходом:
Код на 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 /= b; /* Division by zero risk. */ d /= b; /* 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]; }
Доведення Доведення методу вимагає ручного виконання деяких спеціалізованих Гаусових вилучань.
Припустимо, що невідомі - це , і що рівняння до розв'язання такі:
Розглянемо таку зміну другого () рівняння за допомогою першого рівняння:
що дасть:
у висліді маємо, що було вилучено з другого рівняння. Використовуючи подібну тактику зі зміненим другим рівнянням, щодо третього маємо:
Цього разу було вилучено якщо повторювати цю процедуру до рядка ; (змінене) рівняння міститиме лише одну змінну, . Таке рівняння ми можемо розв'язати і використати результат для того, щоб розв'язати рівняння і так далі допоки всі невідомі не знайдені.
Очевидно, що коефіцієнти у змінених рівняннях ставатимуть все більш заплутаними якщо розписувати їх явно. Але змінені коефіцієнти (з тильдою) можна виразити рекурсивно:
Для дальшого пришвидшення процесу, можна нормувати діленням (якщо немає ризику ділення на число занадто близьке до нуля), тепер змінені коефіцієнти позначені рисочкою будуть:
це дає нам наступну систему з тими самими невідомими і коефіцієнтами вираженими через початкові:
Останнє рівняння містить лише одне невідоме. Розв'язуючи його, приводимо наступне останнє рівняння до одного невідомого. І так далі:
Примітки