Разностные схемы и их анализ. Петрусев А.С. - 39 стр.

при нечётном N, система остаётся хорошо обусловленной. Её
очевидное решение имеет вид u2k=a, u2k+1=b.
     Для решения систем уравнений трёхдиагонального вида с
нарушением условия (4.7) А.А.Абрамовым в [5] был предложен
алгоритм немонотонной прогонки (или прогонки с выбором
главного элемента). Подобно монотонной прогонке, он имеет
две равноправные модификации: сверху вниз - снизу вверх и
снизу вверх - сверху вниз. Мы для определённости рассмотрим
первую. При этом решение (4.2)-(4.4) начинается с левого
краевого условия (4.3). Коэффициенты b0 и c0 не могут
одновременно обратиться в ноль, так как это ведёт к
вырождению системы уравнений. Если ⎜b0⎜≥⎜c0⎜, то аналогично
монотонной прогонке, мы исключаем u0 из первого уравнения. В
обратном случае мы исключаем u1 из первого и второго
уравнений. Уравнения принимают вид:
a1u0+c1u2=d1
f2u0+b2u2+c2u3=d2
Далее, при ⎜a1⎜≥⎜c1⎜ исключаем u0 из второго уравнения и
второе уравнение принимает вид, аналогичное диагональному
случаю. Иначе исключаем u2 из второго и третьего уравнений и
т.д.. В результате прямого прохода немонотонной прогонки
матрица системы будет состоять из расположенных по главной
                         ⎡ xx x0 0x 00 ⎤    ⎡ x0 xx 0x 00 ⎤
диагонали клеток вида: ⎢ x 0 0 x ⎥ и ⎢ 0 0 x x ⎥. Все
                         ⎣ . . . . ⎦        ⎣ . . . . ⎦
остальные элементы матрицы нулевые. Таким образом, в каждой
строке матрицы (кроме последней) остаётся два ненулевых
элемента, а в последней - один. В ходе прямого прохода
следует     запоминать  номер    крайнего    левого    элемента,
отличного от нуля в данной строке. Алгоритм обратного
прохода очевиден.
     Не останавливаясь на анализе данного алгоритма, укажем
лишь, что он теряет устойчивость только тогда, когда
матрица системы близка к вырождению, аналогично методу
Гаусса с выбором главного элемента при решении систем
линейных уравнений общего вида.
     Алгоритм немонотонной прогонки экономичен, требуя O(N)
операций, но несколько более трудоёмок (примерно в 1,5
раза), по сравнению с монотонной прогонкой.
     Благодаря хорошей устойчивости немонотонная прогонка
является     основным  методом    решения    конечно-разностных
уравнений типа (3.7),(3.32),(3.34), когда обычная прогонка
не работает.


п.5.Схема трёхдиагональной циклической прогонки.

     Данный алгоритм предназначен для частного, но важного
на практике случая уравнения, записанного в полярной или
сферической   системе   координат  относительно  угла   ϕ.