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

Теоретическая часть

Пусть Ax=b, где A — трехдиагональная матрица. Матрица A=[aij] называется (2m+1) — диагональной, если aij=0 при |i-j|>m.

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

Матрица A

Получаем A{i}x{i-1}+C{i}x{i}+B{i+1}x{i}=b{i} (1), используем метод прогонки, исходя из следующего рекуррентного соотношения:x{i-1}=?{i-1}x{i}+?{i-1},(2) получаем:

?{2}=(-B{1})/C{1} ; ?{2}=b{1}/C{1} ; (3)

?{i+1}=(-B{i})/(A{i}?{i}+C{i}) ; ?{i+1}=(b{i}-A{i}?{i})/(A{i}?{i}+C{i}) ; (4)

Эти формулы представляют собой прямой проход метода. Обратный проход:

x{n}=(b{n}-A{n}?{n})/(A{n}&#945{n}+C{n}) ; (5)

Остальные xi находим из формулы (2).

Для применимости метода прогонки достаточно, чтобы матрица A была с диагональным преобладанием.

Алгоритм:

1.     Вводим str/stlb — количество строк/столбцов, A — элементы расширенной матрицы

2.     Проверяем матрицу на диагональное преобладание

3.     Если матрица с диагональным преобладанием тогда п.4, иначе п.8

4.     Выполняем прямой ход метода (формулы (3), (4)): c[1]:=A[1,2]/A[1,1]; d[1]:=A[1,stlb]/A[1,1];
c[i]:= (-A[i,i+1])/(A[i,i-1]*c[i-1]+A[i,i]);
d[i]:= (A[i,stlb]-A[i,i-1]*d[i-1])/(A[i,i-1]*c[i-1]+A[i,i])

5.     Далее обратный ход (формулы (2),(5)):
x[str]:=(A[str,stlb]-A[str,str-1]*d[str-1])/(A[str,str]+A[str,str-1]*c[str-1]);
x[i]:=c[i]*x[i+1]+d[i];

6.     Выводим x;

7.     Проверки на невязку;

8.     Заканчиваем алгоритм.

В программе: A[i,i+1] = Bi, A[i,i] = Ci, A[i,i-1] = Ai, A[i,stlb] = bi, d[i] = ?i, c[i] = ?i, str = n.

Описание входной информации: Str (Stlb) — количество строк (столбцов) в расширенной матрице, A [i, j] — матрица A (i — строки, j — столбцы)

Описание выходной информации: x — матрица-ответ

Ссылки для скачивания:Метод прогонки

Вернуться назад

9 комментариев к “Метод прогонки”

Комментарии

  1. Починил, теперь файл можно загрузить без проблем.

  2. никита

    файл не работает, пишет You do not have permission to download this file. и не могу скачать !

  3. mment11

    у кого-нить есть исходник? пожалуйста скиньте куда-нибудь а то для начала курсовой нужно

  4. Адриан

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

  5. AlexR

    Да, я помню, когда писал теорию к этому методу пользовался одним учебником и там было немного не понятно как соотношение получают, поэтому переписал так как есть. Если Вы разобрались, то покажите как данную формулу получают? Буду весьма благодарен.

  6. Андрей

    В формуле (2) ошибка, как легко убедиться, если подставить.
    Правильно x[i-1] = alpha[i]*x[i] + beta[i]

  7. Виталий

    Проблемы с решением задач на языке Delphi?

  8. AlexR

    Чем он не полон и не совсем верен?
    То что надо он считает, но только для матриц с диагональным преобладанием.

  9. Двоечник

    Алгоритм не полон и не совсем верен.

Комментарии