Решение линейных систем с трехдиагональной матрицей

Здесь представлены два альтернативных друг другу алгоритма решения линейных систем с трехдиагональной матрицей. Подобные линейные системы возникают при реализации решений параболических или эллиптических уравнений в одномерном случае или в многомерном при покоординатном расщеплении решения. Первый из этих алгоритмов использует факторизацию системы, называется прогонкой или алгоритмом Томаса и входит во все классические учебники по численным методам. Второй алгоритм, также называемый алгоритмом редукции, использует последовательное бинарное исключение уравнений из системы; он менее известен и более сложен, зато обладает очень высокой устойчивостью и меньшим накоплением погрешности в процессе счета.

Трехдиагональная линейная система уравнений может быть записана в виде:

a_i*u_i-1-b_i*u_i+c_i*u_i+1+f_i=0, где 0<=i<N, a₀=c_N-1=0, u - искомое решение.

Матрица этой системы состоит из главной диагонали (с коэффициентами -b_i) и примыкающих к ней сверху и снизу диагоналей (соответственно c_i и a_i).

Прямое (безытерационное) решение этой системы уравнений можно проводить методом ее факторизации (прогонка, или алгоритм Томаса), либо методом последовательного исключения сначала нечетных, затем делящихся на 2, но не на 4, и т.д. уравнений и соответствующего преобразования коэффициентов. Последний метод называется редукцией или бинарным исключением.