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

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

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

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

a_i x_{i - 1}  + b_i x_i  + c_i x_{i + 1}  = d_i , \,\!

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

 
\begin{bmatrix}
   {b_1} & {c_1} & {   } & {   } & { 0 } \\ 
   {a_2} & {b_2} & {c_2} & {   } & {   } \\ 
   {   } & {a_3} & {b_3} & \ddots & {   } \\ 
   {   } & {   } & \ddots & \ddots & {c_{n-1}}\\ 
   { 0 } & {   } & {   } & {a_n} & {b_n}\\ 
\end{bmatrix}
\begin{bmatrix}
   {x_1 }  \\ 
   {x_2 }  \\ 
   {x_3 }  \\ 
   \vdots   \\
   {x_n }  \\
\end{bmatrix}
=
\begin{bmatrix}
   {d_1 }  \\ 
   {d_2 }  \\ 
   {d_3 }  \\ 
   \vdots   \\
   {d_n }  \\
\end{bmatrix}
.

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

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

c'_1 = \frac{c_1}{b_1};\ c'_i = \frac{c_i}{b_i - c'_{i-1} a_i },\, i=\overline{2,n}

та

d'_1 = \frac{d_1}{b_1};\ d'_i = \frac{d_i- d'_{i-1} a_i}{b_i - c'_{i-1} a_i},\, i=\overline{2,n}

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

x_n = d'_n\,

x_i = d'_i - c'_i x_{i + 1}; \ i = n - 1, n - 2, \ldots, 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];
}


Код на Java[ред.ред. код]

    public static double[] progonka(int n,double[] a,double[] b,double[] c,double[] d) {
        double[] x = new double[n];
 
        for (int i = 1; i < n; i++) {
            double m = a[i] / b[i - 1];
            b[i] = b[i] - m * c[i - 1];
            d[i] = d[i] - m * d[i - 1];
        }
 
        x[n - 1] = d[n - 1] / b[n - 1];
 
        for (int i = n - 2; i >= 0; i--) {
            x[i] = (d[i] - c[i] * x[i + 1]) / b[i];
        }
        return x;
    }