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

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

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

Решение ищется в виде:

u_i-1=bet_i*u_i+gam_i В этом случае для bet и gam получаются рекуррентные формулы: bet_i+1=c_i*fi, gam_i+1=(f_i+a_i*gam_i)*fi, fi=1/(b_i-a_i*bet_i); bet₀=gam₀=0. По этим формулам вспомогательные массивы вычисляются для i от 1 до N, затем находится u_N-1=gam_N, а затем при известных вспомогательных массивах вычисляются все значения u.

Алгоритм принципиально не может иметь ведущего элемента, и есть вероятность того, что он не сойдется даже для несингулярной матрицы. Для этого в программе, реализующей прогонку, необходимо контролировать значения fi. Еще два замечания: длины рекуррентных цепочек порядка N, поэтому при экспоненциальном накоплении погрешностей (что происходит при преобладании значений |bet_i|>1) прогонка практически обязательно разойдется. Второе: алгоритм сохраняет исходные значения коэффициентов. Доказано, что для устойчивой работы алгоритма Томаса достаточно диагонального преобладания, однако, во многих случаях он сходится и при отсутствии такового.

Общее описание алгоритма таково.
Если провести исключение из имеющейся системы уравнений всех уравнений, находящихся на нечетных позициях, то от системы N исходных уравнений мы перейдем к системе из (N-1)/2+1 уравнений только для четных значений u, нечетные же значения будут вычисляться через четные. Повторяя эту процедуру для укороченной системы, мы в конце концов придем к единственному уравнению для узла, лежащего в позиции (N-1)/2 (только если N-1 — степень двойки). Затем, проводя обратную подстановку, определяются крайние, а затем и все прочие узлы.

Формулы для пересчета коэффициентов на каждом этапе исключения таковы:

Если число уравнений не является степенью двойки, алгоритм реализуется методом фиктивного восполнения области определения до степени 2. При этом никаких реальных действий, кроме нескольких целочисленных проверок, не производится, а только коэффициенты, индекс которых выпадает из области определения [0,N-1] включительно, считаются равными нулю и в преобразованиях не участвуют (подробности в программе).

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

Алгоритм не требует дополнительной памяти, но сохраняет только половину из имеющихся в начале его работы коэффициентов: те, что находятся на нечетных позициях (независимо от четности N). Скорость работы почти не зависит от того, является ли N-1 целочисленной степенью 2.

Ниже приводятся программы для прогонки и редукции.

Линейные уравнения. Решение систем линейных уравнений. Метод прогонки.

Метод прогонки (алгоритм Томаса) используют для решения СЛУ типа Ax=F, где A — трёхдиагональная матрица. Это вариант метода последовательного исключения неизвестных.

Система уравнений Ax=F равноценна соотношению:

Метод прогонки базируется на предположении, что неизвестные, которые необходимо найти, связаны соотношением:

Выразим x_i-1 и x_i через x_i+1, подставим в уравнение, используя это соотношение, (1):

где F_i — правая часть i-го уравнения.

Это соотношение выполняется не завися от решения, если потребовать:

,

,

Получаем из 1-го уравнения:

.

После того, как нашли прогоночные коэффициенты α и β, используем уравнение (2) и получим решение системы. Причем,

.

Еще одним вариантом объяснения смысла метода прогонки является такой вариант: преобразуем уравнение (1) к равнозначному ему уравнению:

c надиагональной (наддиагональной) матрицей:

Рассчеты проводим в 2 этапа. На 1-ом этапе вычисляем компоненты матрицы C′_i и вектора F′, начиная с i=2 до i=n:

На 2-ом этапе, для i=n,n−1,…,1 вычисляем решение:

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

О решении систем линейных уравнений с трехдиагональной матрицей Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — П. К. Корнеев

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

Похожие темы научных работ по математике , автор научной работы — П. К. Корнеев

ON THE SOLVING LINEAR EQUATION SYSTEMS WITH TRIDIAGONAL MATRIX

The article presents the development of representation as the product of terminating chain fractions for the cuicuiation of tridiagonal matrix determinants On its basis the first (last) coordinate of the vector of solving linear equation system with tridiagonal matrix factorize into terminating ascending chain fraction, the particular denominatorsof which are terminating vulgar chain fractions.

Текст научной работы на тему «О решении систем линейных уравнений с трехдиагональной матрицей»

Вестник Ставропольского государственного университета fiiMM

О РЕШЕНИИ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ С ТРЕХДИАГОНАЛЬНОЙ

ON THE SOLVING LINEAR EQUATION SYSTEMS WITH TRIDIAGONAL MATRIX

The article presents the development of representation as the product of terminating chain fractions for the culculation of tridiagonal matrix determinants On its basis the first (last) coordinate of the vector of solving lnnear equation system with tridiagonal matrix factorize into terminating ascending chain fraction, the particular denomnnatorsof which are terminating vulgar chain fractions.

В статье для вычисления определителей трехдиагональных матриц строится представление в виде произведения конечных цепных дробейй. На этой основе первая (последняя) координата вектора решения системы линейных уравнений с трехдиагональ-ной матрицей разлагается в конечную восходящую цепную дробь, частные знаменатели которой являются конечными обыкновенными цепными дробями

Системы линейных уравнений с трех-диагональной матрицей решаются обычно методом прогонки (см. [1], [3]).

Можно показать, что метод прогонки эквивалентен вычислению конечной цепной дроби.

Огромное значение для вычислительной математики имеет свойство цепных дробей мало накоплять погрешность с ростом числа звеньев в цепной дроби.

Детальный анализ погрешностей при вычислении цепных дробей делается в [2].

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

1. Найдем определитель трехдиаго-нальной матрицы

0 0 са п-1 п-1 Ъ п-

«О решении систем линейных уравнений с трехдиагональной матрицей»

Вычитая первый столбец, умноженный на Ъх!«1 из второго столбца, и разложив полученный определитель по элементам первой строки, будем иметь

где А п-1 — определитель того же типа, что и Ап. Продолжая этот процесс, получим сле-