При решении задач конечно-разностными методами или методом конечных элементов, часто решение задачи сводится к решению линейной системы уравнений с трехдиаганальной матрицей коэффициентов, т.е. с матрицей, где все элементы нули, кроме трех диагоналей (в окрестности главной диагонали); рассмотрим систему с трехдиаганальной матрицей:
для решения этой линейной системы уравнений, конечно, можно применять метод Гаусса, но тогда пришлось бы делать много необязательных операций с нулями. Чтобы сэкономить время вычислений и не работать лишний раз с нулями, Томас (1949г.) разработал специальный алгоритм расчета. Рассчитывая по алгоритму Томаса элементы получаемой треугольной матрицы, мы следуем методу Гаусса, с уточнением, что с нулями никаких действий не производим; алгоритм Томаса называют – методом прогонки.
Для решения системы (40) методом прогонки – Томаса действуем следующим образом:
а) прямой ход:
Замечание: после проведения прямого хода предполагается, что все
б) обратный ход:
Таким образом, для системы линейных уравнений с трехдиаганальной матрицей наиболее экономным является алгоритм прогонки – Томаса, который является «отфильтрованным» методом Гаусса.
Метод минимизации невязки для решения линейной системы уравнений (метод наименьших квадратов).
При проведении экспериментов, часто приходится решать следующую задачу: определить
Число наблюдаемых величин больше числа неизвестных
Коэффициенты
Если бы все числа
задача теперь заключается в том, чтобы найти такие значения
В методе наименьших квадратов, в качестве нормы рассматривают дискретную норму Гаусса:
Очевидно, что эта норма минимальна тогда, когда минимально подкоренное выражение, т.е. сумма квадратов невязок
Условия существования минимума для функций специального вида
т.е. задача сводится, как и в общей теории приближений, к решению системы нормальных уравнений.
Для примера рассмотрим
Тогда система соответствующих нормальных уравнений имеет вид:
Решение системы (49) дает решение задачи (48) наилучшим приближением, в смысле дискретной нормы Гаусса.
Замечания:
1) классический метод Гаусса, метод Гаусса с выбором главного элемента, метод Якоби и метод минимизации невязки являются общими методами и применяются для определения решения невырожденных систем линейных уравнений, когда ведущие (большие по модулю) элементы матрицы системы расположены в окрестности главной диагонали (система хорошо обусловлена), если же система плохо обусловлена, тогда нужно менять соответствующую модель, чтобы она приводила к приемлемой системе уравнений;
2) для ускорения сходимости методов разработаны специальные методы – метод Гаусса-Зейделя, методы релаксации и др., которые применимы лишь для узкого класса систем – с симметрической, положительно-определенной матрицей; с ненулевыми диагональными элементами;
3) для нужд разностных уравнений разработаны специальные алгоритмы прогонки Томаса, которые являются «экономными» методами Гаусса для трехдиагональных матриц системы линейных уравнений.
Литература
1. Т. Шуп. Решение интегральных задач на ЭВМ. Мир., М.,2002
2. Л. Коллатц, Ю. Альберхт. Задачи по прикладной математике. Мир., М.,1998.
3. Т.А. Обгадзе. Элементы математического моделирования. Учебное пособие. Грузинский Политехнический Институт им. В.И. Ленина, Тбилисси, 1999.