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

Лекция 2: Метод прогонки Решение одномерной краевой задачи как методом конечных элементов так и методом разностных схем сводится к решению системы линейных алгебраических уравнений следующего вида: A j z j  1  C j z j  B j z j 1 F j , j 1,..., N  1 (2.1) z0  0 z1  0 , z N  N z N  1  N , (2.2) A j , C j , B j , F j ,  0 , 0 ,  N , N – заданные величины. В (2.1), (2.2) z0 , z1 ,..., z N - неизвестные величины, которые требуется найти. Будем предполагать, что C j  Aj  B j  Aj  0,  0  1,  N 1 (2.3) (2.3) обеспечивают существование и единственность решения исходной задачи. Систему (2.1), (2.2) можно переписать в векторном виде: Az b , где ... 0 1   z ( z0 ,..., z N ), b ( 0 , F1 ,..., FN  1 , N )  B1  A1  C1 A  ........  0  N      1  Таким образом система уравнений (2.1), (2.2) является трехдиагональной. При выполнении (2.3) матрица Aявляется матрицей с доминирующей главной диагональю. Систему (2.1), (2.2) называют краевой задачей для трехточечного разностного уравнения. Условия (2.3) позволяет находить решение системы экономичным методом, называемым методом прогонки. Подставим z0 , определяемое первым граничным условием (2.2) z0  0 z1  0 в первое уравнение (2.1): A1 (  0 z1  0 )  C1 z1  B1 z2 F1 Из последнего равенства будем иметь (2.4) z1 1 z 2  1 где B1 C1  A1  0 A  F 1  1 0 1 C1  A1  0 1  Величину z1,определенную в (2.4), подставляем во второе уравнение (2.1), это позволит выразить z 2 через z3 . Допустим, что уже найдено соотношение: (2.5) z k  1   k  1 z k  k  1 , k  N  1 Подставим z k  1 , определяемое равенством (2.5) в k -ое уравнение (2.1), получим: Ak (  k  1 zk  k  1 )  Ck zk  Bk zk 1 Fk Разрешим это уравнение относительно zk z k  k z k 1  k (2.6) где Bk A   Fk (2.7) k  ,  k  k k 1 Ck  Ak  k  1 Ck  Ak  k  1 Таким образом, коэффициенты уравнения (2.6), связывающих соседние значения zk и zk 1 , k 1,2,..., N  1 можно определить из рекурентных  0 и  0 заданы в (2.2). соотношений (2.7), поскольку Допустим (2.6) найдено для k N  1,т.е. z N  1  N  1 z N  N  1 Теперь подставим z N  1 , определенное последним равенством во второе граничное условие (2.2): z N  N (  N  1 z N  N  1 )  N получим (2.8) z N (1   N  N  1 )  N N  1  N zN   N N  1  N 1  N  N1 где  N и N заданы в (2.2), а величины  N  1 и  N  1 находились из равенства (2.6) при k N  1 Затем по формуле (11.6) в обратном порядке находим остальные неизвестные z N  1 , z N  2 ,..., z0 . Формула (2.6) при k 0 совпадает с первым из краевых условий (2.2). Процесс вычисления коэффициентов  k и  k , k 1,..., N  1 по формуле (2.7) называется прямы м ходом прогонки. Вычисление z k по формулам (2.8), (2.6) называется обратны м ходом прогонки. Замечание: Все действия при вычислении  k , k и z k являются корректными, так как знаменатели в дробях, в силу (2.3), нигде не обращается в 0.