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

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

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

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

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.

Численные методы решения линейных уравнений

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

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

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

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

• Запись обратного хода в виде , так как преобразованная матрица – двухдиагональная.

•Вывод рекуррентного соотношения для и через и и получение соотношения для и .

• Осуществление обратного хода метода прогонки и определение всех неизвестных.

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

i = 1,2,…, n, (2.6)

Запись (2.6) представляет собой так называемый КАНОНИЧЕСКИЙ ВИД СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДА ПРОГОНКИ. При этом матрица система (2.6) имеет вид

Прямой ход метода прогонки сводится к исключению неизвестного в каждом уравнении системы. Получаемая в результате прямого хода система содержит в каждом уравнении только два неизвестных и , и матрица ее – верхняя треугольная с двумя диагоналями. Запишем i-ю строку преобразованной двухдиагональной матрицы в виде

(2.7)

Если система (2.6) приведена к виду (2.7), то обратный ход метода Гаусса очевиден. Однако использование общих алгоритмов прямого и обратного хода нецелесообразно. Построим эффективную вычислительную схему, которая и составляет суть метода прогонки. Для этого, уменьшив в (2.7) индекс на единицу, запишем

Подставляя в систему (2.6), получим соотношение

из которого нетрудно получить

Сравнивая это соотношение с (2.7), можем записать рекуррентные соотношения

(2.8)

для вычисления так называемых ПРОГОНОЧНЫХ КОЭФФИЦИЕНТОВ.

Подчеркнем, что последующие значения прогоночных коэффициентов вычисляются только по известным коэффициентам системы (2.6) и известным предыдущим значениям прогоночных коэффициентов

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например, Отметим, что, вообще говоря, начальные значения коэффициентов в рассмотренной схеме вычислений не требуются, так как значения коэффициентов вычисляются только через коэффициенты первого уравнения системы (2.6): при i = 1 из (2.6) получаем соотношение Сравнивая это выражение с (2.7) при i =1, получаем а значение в обратном ходе вычисляем по соотношению Использование в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, …,n; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты не зависят от (в соотношениях(2.8) при i =1 коэффициенты умножаются на ), следует, что можно задать любые значения для прогоночных коэффициентов . Далее будет ясно, почему удобно положить Для начала обратного хода метода прогонки необходимо для вычисления задать значение . Так как , то из первого соотношения (2.8) вытекает, что и, следовательно, можно задать любое значение для Обычно полагают , и тогда

Метод прогонки устойчив, если Метод прогонки корректен, если

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

Из этой формулы при следует, что в данном случае погрешность не возрастает.

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

i = 1,2, …, n.

В самом деле, если хотя бы для одного значения i выполняется строгое неравенство , то можно записать цепочку неравенств:

.

Было показано, что можно положить и тогда, во-первых, для всех i выполняется , что обеспечивает затухание погрешности, и, во-вторых, для всех i выполняется условие и, таким образом, не возникает ситуация деления на нуль. Так как условие является только достаточным, то невыполнение его не означает нарушения корректности и устойчивости.

Для реализации метода требуется примерно 8n операций, из которых 3n составляют операции типа умножения и 5n – операции типа сложения. При численном решении дифференциальных уравнений используются различные варианты метода прогонки: метод встречных прогонок, потоковая прогонка, матричная прогонка для систем векторных уравнений. Отметим, что

Метод прогонки обобщается на случай, при котором в системе (2.6) — квадратные матрицы размерности , а — векторы размерности m. Тогда соотношения (2.7) и (2.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а в (2.8) является соответствующей обратной матрицей.

Условие устойчивости матричной прогонки выглядит как , а условие корректности и устойчивости имеет вид .

Дата добавления: 2015-11-06 ; просмотров: 2638 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ