Избранные вопросы курса численных методов. Выпуск 3. Интерполяция кубическими сплайнами. Гудович Н.Н. - 21 стр.

            e0                         ei
   L 1 =−        ,     L i +1 =−                  , i =1, 2 , ... , N −1 ,         (6.18)
            d0                     d i +c i L i


            κ0                    κ i −c i M i
    M1 =         ,     M i +1 =                   , i =1 , 2 , ... , N −1 ,       (6.19)
            d0                    d i +c i L i


        κ N −c N M N
 sN =                   , s i =L i +1 s i +1 +M i +1 , i =N −1, N −2 , ... ,1 , 0 . (6.20)
        d N +c N L N


      Замечание 6.1. Изложенный метод решения систем линейных
алгебраических уравнений с трёхдиагональной матрицей – метод прогонки –
обладает высокой степенью эффективности как с точки зрения требуемой
оперативной памяти ЭВМ, так и с точки зрения необходимого числа
арифметических операций. С точки зрения объёма оперативной памяти его
эффективность объясняется тем, что при вычислениях по формулам (6.18)-(6.20)
обрабатывать приходится массив коэффициентов (6.17) и правых частей κi
размерности (N+1)×4, а не массив коэффициентов a i j и правых частей κ i
размерности (N+1)×(N+2), как в случае произвольной квадратной системы из
N+1      уравнений. С точки же зрения числа арифметических операций
эффективность метода прогонки является следствием двух причин. Во-первых, на
i-том шаге прямого хода исключать переменное s i приходится лишь из одного
(i+1)-вого уравнения, а не из всех уравнений с номерами m > i. Таким образом,
прямой ход требует лишь N, а не O(N2) исключений, как в случае метода Гаусса
для системы (N+1)-вого порядка с произвольной матрицей. Во-вторых, в случае
метода прогонки каждое исключение требует конечного ( не зависящего от N )
числа арифметических операций, поскольку у используемых при исключении si
уравнений (6.5), (6.6), (6.8) числовые наборы, состоящие из коэффициентов при
неизвестных и правой части уравнения, содержат не более четырёх элементов,
тогда как в случае систем общего вида аналоги упомянутых выше числовых
наборов содержат в среднем порядка          N/2    элементов, а значит, число
арифметических операций при исключении si из одного уравнения системы
имеет порядок O(N). В результате прямой ход метода прогонки – прямая
прогонка – требует O(N) арифметических операций, в то время как прямой ход
метода Гаусса для систем общего вида той же размерности              – O(N3)
арифметических операций. Обратный же ход метода прогонки – обратная
прогонка – как видно из формул (6.20), также требует O(N) арифметических
операций, тогда как для метода Гаусса в случае общих систем этот этап требует
O(N2) операций.

                                                                                           21