Трехдиагональная матрица метод прогонки

Трехдиагональная матрица метод прогонки

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

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

  • • Приведение трехдиагональной матрицы к верхней треугольной (прямой ход). В случае трехдиагональной матрицы это означает приведение к двухдиагональной, т. е. приведение исходной системы к системе, содержащей по два неизвестных в каждом уравнении, кроме последнего, в котором содержится только одно неизвестное.
  • • Запись обратного хода в виде xi = Р, + tx( + х + Q( + v так как преобразованная матрица — двухдиагональная.
  • • Вывод рекуррентного соотношения для Pi + 1 и^ + 1 через Pt

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

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

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

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

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

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

Читайте также:  Как вытащить картридж из принтера hp laserjet

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

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

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

Подчеркнем, что последующие значения прогоночных коэффициентов Р.f j, Q, * ! вычисляются только по известным коэффициентам системы (1.6) и известным предыдущим значениям прогоночных коэффициентов Pr Qt.

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например Pv Qr Отметим, что, вообще говоря, начальные значения коэффициентов Pv в рассмотренной схеме вычислений не требуются, так как значения коэффициентов Р2, Q2 вычисляются только через коэффициенты первого уравнения системы (1.6): при i = 1 из (1.6) получаем соотношение -ЬуХу + сгхг — dv Сравнивая это выражение с (1.7) при i = 1, получаем Р2 = с11; Q2 = -djbv а значение в обратном ходе вычисляем по соотношению Ху — Р2х2 + Q2. Использование Pv Qj в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, . п; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты Р2, Q2 не зависят от Plt Qj (в соотношениях (1.8) при i = 1 коэффициенты Pj, Qj умножаются на ах = 0), следует, что можно задать любые значения для прогоночных коэффициентов Рj, Qj. Далее будет ясно, почему удобно положить Pi = Q1

0. Для начала обратного хода метода прогонки необходимо для вычисления xi = Р, + jXt + j + Q( + 1 задать значение хп + г Так как сп 0, то из первого соотношения (1.8) вытекает, что t, = 0 и, следовательно, можно задать любое значение для xn + v Обычно полагают хп +д = 0, и тогда xn = Qn х г

Метод прогонки устойчив, если [Pj |cj > 0 и, таким образом, не возникает ситуации деления на нуль. Так как условие | <г) >|а(| + jcj является только достаточным, то невыполнение его не означает нарушения корректности и устойчивости.

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

Метод прогонки обобщается на случай, при котором в системе (1.6) ar 6j( cj — квадратные матрицы размерности тх т, a xjt dt — векторы размерности т. Тогда соотношения (1.7) и (1.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а [Ь; — а,Р4] -1 в (1.8) является соответствующей обратной матрицей.

Читайте также:  Замена тач на телефоне

Условие устойчивости матричной прогонки выглядит как fdet P.f 1 А)

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

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

т.е. каждое уравнение связывает три соседних неизвестных:

Выразим из первого уравнения x через x:

из второго x через x:

и т.д. Из последнего уравнения:

Таким образом, для i=1, 2, …, n:

Таким образом, решение системы линейных уравнений (6.6) сводится к двум этапам:

1. Вычисление прогоночных коэффициентов P, Q, i=1, 2, …, n по формулам (6.8) – прямая прогонка.

2. Вычисление неизвестных x при i=n, n–1, …, 1 по формулам (6.7) – обратная прогонка.

Обозначим , тогда , при i=2,…,n.

Непосредственной проверкой можно убедиться, что имеет место представление A=LU, где

Таким образом, LU-разложение трехдиагональной матрицы A может быть выполнено простым алгоритмом, вычисляющим R, P при возрастающих значениях i.

Можно вычислить и определитель матрицы A

det A= . (6.9)

Контроль точности и уточнение приближенного решения в рамках прямых методов

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

Обозначим полученное приближенное решение через и подставим в исходное уравнение. Вектор называют невязкой приближенного решения . По величине невязки можно с некоторой осторожностью судить о близости найденного решения к точному решению x. Если

Читайте также:  Zte leo s1 характеристики отзывы

Недостаточно малая величина, то следует искать вектор поправку такой, что , т.е. . Следовательно . Нахождение поправки сводится к решению той же системы уравнений, где в качестве столбца свободных членов берется вектор невязки. Так как матрица коэффициентов левой части системы не меняется, нет надобности прямого хода преобразований коэффициентов при неизвестных (другими словами – LU-разложения), достаточно выполнить действия с новыми свободными членами. Прибавив найденную поправку, получаем уточненное решение . Если величина

Или

Окажется недостаточно малой, процесс уточнения может быть повторен: ищется поправка как приближенное решение системы , где ; тогда более точным должно быть решение . Но сходимость к нулю невязок в таком процессе может и не наблюдаться. Обычно делают не более двух-трех шагов уточнения, причем рекомендуется производить вычисление невязок в режиме накопления. если в этом процессе не происходит сближения при k=2,3,…, то это говорит скорее всего о плохой обусловленности данной системы и о том, что ее решение не может быть уточнено таким способом. Описанный контроль точности по невязкам не требует большого увеличения вычислительных затрат, но требуется отводить дополнительное место в памяти под хранение исходных данных.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9136 — | 7299 — или читать все.

Для решения систем A x = b с трехдиагональной матрицей наиболее часто применяется метод прогонки, являющийся адаптацией метода Гаусса к этому случаю.

Запишем систему уравнений

в матричном виде: A x = b где

A=

Выпишем формулы метода прогонки в порядке их применения.

  1. Прямой ход метода прогонки (вычисление вспомогательных величин):
    a 2 = -e1 / d1
    b 2 = b1 / d1
    a i+1 = -ei / [di + ci a i], i=2, . n-1
    b i+1 = [-ci b i + bi] / [di + ci a i], i=2, . n-1
    (1.9)
  2. Обратный ход метода прогонки (нахождение решения):
    xn = [-cn b n + bn] / [dn + cn a n]
    xi = a i+1xi+1 + b i+1, i = n-1, . 1
    (1.10)

Метод прогонки можно применять, если нигде в формулах знаменатели не равны нулю. В [2, стр.134] доказано следующее

УТВЕРЖДЕНИЕ 1.1 Для применимости формул метода прогонки достаточно выполнения условий диагонального преобладания у матрицы A, то есть

причем хотя бы одно неравенство должно быть строгим.

Ссылка на основную публикацию
Adblock detector