Главная > Математика > Вычислительные методы для инженеров
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 5.9. Метод прогонки

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

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

1. Вывод расчетных формул.

Преобразуем первое уравнение системы (5.69) к виду

где

Подставим полученное для выражение во второе уравнение системы:

Преобразуем это уравнение к виду

где Выражение (5.71) подставляем в третье уравнение системы и т. д.

На шаге этого процесса уравнение системы преобразуется к виду

где

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

Отсюда можно определить значение

Значения остальных неизвестных для теперь легко вычисляются по формуле (5.72).

2. Алгоритм прогонки.

Сделанные преобразования позволяют организовать вычисления метода прогонки в два этапа".

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

а при по рекуррентным формулам

При прямая прогонка завершается вычислением

Обратный ход метода прогонки (обратная проюнка) дает значения неизвестных. Сначала полагают Затем значения остальных неизвестных вычисляют по формуле

Вычисления ведут в порядке убывания значений до 1.

Пример 5.17. Используя метод прогонки, решим систему

Прямой ход. Согласно формулам получаем

Обратный ход. Полагаем Далее находим Итак, получаем решение:

3. Свойства метода прогонки.

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

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

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

следовательно, обратная прогонка по формуле (5.76) устойчива по входным данным (см. пример 3.27). Положим

Теорема 5.4. Пусть коэффициенты системы (5.69) удовлетворяют следующим условиям диагональном преобладания:

Тогда для всех

Воспользуемся принципом математической индукции. Из условий теоремы имеем

Пусть теперь для некоторого Тогда

Из полученной оценки в силу условий (5.77) вытекает справедливость неравенств Следовательно, и

4. Метод прогонки и разложение матрицы на множители.

Описанный вариант метода прогонки можно рассматривать как одну из схем метода Гаусса (без выбора главного элемента), в результате прямого хода которого исходная трехдиагональная матрица

представляется в виде произведения двух двухдиагональных матриц:

Здесь

Так как для определения нет необходимости вычислять коэффициенты то общее число операций на получение разложения (5.78) составляет примерно

Подобно тому как это описано в § 5.7, разложение (5.78) можно использовать для решения систем с многими правыми частями. Если нужно решить систем с матрицей А, то общее число операций составит примерно

К сожалению, при обращении матрицы А теряется ее трехд и атональная структура. Обратная матрица является заполненной, однако для ее вычисления с помощью разложения (5.78) требуется примерно арифметических операций.

Так как то определитель трехдиагональной матрицы, после того как получено разложение (5.78), вычисляется по элементарной формуле

5. Некоторые варианты метода прогонки.

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

Для систем уравнений, обладающих близкой к (5.69) структурой, разработаны методы циклической прогонки, матричной прогонки и

С указанными вариантами метода прогонки можно подробно ознакомиться в [42], [72].

<< Предыдущий параграф Следующий параграф >>
Оглавление