В численной линейной алгебре , то трехдиагональная матрица алгоритма , также известный как алгоритм Томаса ( по имени Луэллина Томаса ), является упрощенной формой исключения Гаусса , которая может быть использована для решения трехдиагональных систем уравнений . Трехдиагональную систему для n неизвестных можно записать как
где а также .
Для таких систем решение может быть получено в операции вместо требуется методом исключения Гаусса . Первая развертка устраняет's, а затем (сокращенная) обратная подстановка дает решение. Примеры таких матриц обычно возникают в результате дискретизации одномерного уравнения Пуассона и интерполяции естественным кубическим сплайном .
Алгоритм Томаса в целом нестабилен , но таков в некоторых частных случаях, например, когда матрица доминирует по диагонали (по строкам или столбцам) или симметрично положительно определена ; [1] [2] для более точной характеристики устойчивости алгоритма Томаса см. Теорему Хигэма 9.12. [3] Если в общем случае требуется стабильность, вместо этого рекомендуется исключение по Гауссу с частичным поворотом (GEPP). [2]
Методика
Прямая развертка состоит из вычисления новых коэффициентов следующим образом, обозначающих новые коэффициенты с простыми числами:
а также
Затем решение получается обратной подстановкой:
Вышеупомянутый метод не изменяет исходные векторы коэффициентов, но также должен отслеживать новые коэффициенты. Если векторы коэффициентов могут быть изменены, то алгоритм с меньшим объемом бухгалтерского учета:
- Для делать
с последующей обратной заменой
Реализация подпрограммы VBA без сохранения векторов коэффициентов показана ниже.
Sub TriDiagonal_Matrix_Algorithm ( N% , A # (), B # (), C # (), D # (), X # ()) Dim i% , W # Для i = 2 К N W = A ( i ) / B ( i - 1 ) B ( i ) = B ( i ) - W * C ( i - 1 ) D ( i ) = D ( i ) - W * D ( i - 1 ) Далее i X ( N ) = D ( N ) / B ( N ) Для i = N - от 1 до 1 шага - 1 X ( i ) = ( D ( i ) - C ( i ) * X ( i + 1 )) / B ( i ) Next i End Sub
Вывод
Вывод трехдиагонального матричного алгоритма является частным случаем исключения Гаусса .
Предположим, что неизвестные , и что необходимо решить следующие уравнения:
Рассмотрите возможность изменения второго () уравнение с первым уравнением следующим образом:
что даст:
Обратите внимание, что был исключен из второго уравнения. Использование аналогичной тактики с модифицированным вторым уравнением для третьего уравнения дает:
Этот раз был ликвидирован. Если эту процедуру повторять дострока; (измененный) уравнение будет включать только одно неизвестное, . Это можно решить, а затем использовать для решения уравнение и так далее, пока не будут решены все неизвестные.
Ясно, что коэффициенты в модифицированных уравнениях становятся все более и более сложными, если они указаны явно. Изучив процедуру, можно вместо этого рекурсивно определить модифицированные коэффициенты (обозначенные тильдами):
Чтобы еще больше ускорить процесс решения, могут быть разделены (если нет деления на нулевой риск), новые модифицированные коэффициенты, каждый из которых обозначен штрихом, будут:
Это дает следующую систему с теми же неизвестными и коэффициентами, определенными в терминах исходных выше:
Последнее уравнение включает только одно неизвестное. Решение этого, в свою очередь, сводит следующее последнее уравнение к одному неизвестному, так что эту обратную подстановку можно использовать для поиска всех неизвестных:
Варианты
В некоторых ситуациях, особенно связанных с периодическими граничными условиями , может потребоваться решение слегка возмущенной формы трехдиагональной системы:
В этом случае мы можем использовать формулу Шермана-Моррисона, чтобы избежать дополнительных операций исключения Гаусса, и по-прежнему использовать алгоритм Томаса. Метод требует решения модифицированной нециклической версии системы как для входного, так и для разреженного корректирующего вектора, а затем комбинирования решений. Это можно сделать эффективно, если оба решения вычисляются одновременно, так как прямая часть алгоритма чистой трехдиагональной матрицы может использоваться совместно.
В других ситуациях система уравнений может быть блочной трехдиагональной (см. Блочную матрицу ) с меньшими подматрицами, расположенными как отдельные элементы в вышеупомянутой матричной системе (например, двумерная проблема Пуассона ). Для этих ситуаций были разработаны упрощенные формы исключения Гаусса. [4]
В учебнике « Числовая математика » Квартерони, Сакко и Салери приведена модифицированная версия алгоритма, в которой не используются некоторые деления (вместо этого используется умножение), что полезно для некоторых компьютерных архитектур.
Параллельные трехдиагональные решатели были опубликованы для многих векторных и параллельных архитектур, включая графические процессоры [5] [6]
Подробное описание параллельных трехдиагональных и блочно-трехдиагональных решателей см. В [7]
Рекомендации
- ^ Прадип Niyogi (2006). Введение в вычислительную гидродинамику . Pearson Education India. п. 76. ISBN 978-81-7758-764-7.
- ^ а б Бисва Натх Датта (2010). Численная линейная алгебра и приложения, второе издание . СИАМ. п. 162. ISBN. 978-0-89871-765-5.
- ^ Николас Дж. Хайэм (2002). Точность и устойчивость численных алгоритмов: второе издание . СИАМ. п. 175. ISBN 978-0-89871-802-7.
- ^ Quarteroni, Alfio; Сакко, Риккардо; Салери, Фаусто (2007). «Раздел 3.8». Вычислительная математика . Спрингер, Нью-Йорк. ISBN 978-3-540-34658-6.
- ^ Chang, L.-W .; Hwu, W, -M. (2014). «Руководство по реализации трехдиагональных решателей на графических процессорах». В В. Кидратенко (ред.). Численные вычисления на графических процессорах . Springer. ISBN 978-3-319-06548-9.
- ^ Venetis, IE; Курис, А .; Собчик, А .; Gallopoulos, E .; Самех, А. (2015). «Прямой трехдиагональный решатель, основанный на вращениях Гивенса для архитектур GPU». Параллельные вычисления . 49 : 101–116.
- ^ Gallopoulos, E .; Philippe, B .; Самех, АХ (2016). «Глава 5». Параллелизм в матричных вычислениях . Springer. ISBN 978-94-017-7188-7.
- Конте, С.Д. и деБур, К. (1972). Элементарный численный анализ . Макгроу-Хилл, Нью-Йорк. ISBN 0070124469.
- Эта статья включает текст из статьи Tridiagonal_matrix_algorithm _-_ TDMA_ (Thomas_algorithm) на CFD-Wiki, которая находится под лицензией GFDL .
- Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, ВР (2007). «Раздел 2.4» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.