А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 18
Текст из файла (страница 18)
4. Метод немонотониой прогонки. Вернемся снова к методу прогонки решения трехточечных уравнений: соуо ()оуг = 1о~ — а уг,+с у,— (ггу,о,=~г, 1=1, 2, ..., )Ч вЂ” 1, — ад,уд,, + смут = ~~, 1 = гч', (46) который был построен в 2 1. Напомним, что в алгоритме правой (левой) прогонки неизвестные уг находятся последовательно при движении в сторону уменьшения (увеличения) индекса 1. При этом уг выражается только через соседнее неизвестное. Такая 93 причем хотя бы в одном из этих неравенств достигается строгое неравенство, Отсюда следует, что детерминант Ь, определенный в (37), отличен от нуля, Устойчивость и корректность метода прогонки для решения вспомогательных задач (34) — (36) следуют из (43). В качестве примера задачи, сводящейся к (32), рассмотрим схему с весами у~ — — пу"+1+ (1 — о) у", ! ~1~ Ф вЂ” 1, ««, г ««, г' структура алгоритма дает основание назвать построенный метод методом монотонной прогонки.
Монотонный порядок определения неизвестных у, на обратном ходе метода порожден естественным порядком исключения неизвестных из уравнений на прямом ходе. Таким образом, метод монотонной прогонки есть метод исключения Гаусса без выбора главного элемента, примененный к специальной системе линейных алгебраических уравнений (46) с трехдиагональной матрицей. Известно, что такой вариант метода исключения Гаусса корректен для случая систем уравнений с матрицами, имеющими диагональное преобладание. Для системы (46) это утверждение доказано в лемме 1. Остановимся на этом более подробно. Напомним, что в й 1, п. 1 на 1-м шаге процесса исключения неизвестных в системе (46) была получена «укороченная> система (с,— а>а,)у,— Ь,у,+,=~,+аА, 1=1, — а;у»+с;у,— Ь;у>+, — — )н 1+ 1 (<1 ( <У вЂ” 1, (47) — анун-'+ снун = ~н для неизвестных у,, у,+„..., ун. Предполагая, что с,— а,а, от. лично от нуля, мы преобразовывали первое уравнение системы(47) к виду у, =а,+еу,+«+Д,+„сс,+е — — Ь,/(с,— а,а,) (48) и использовали его для исключения у, из уравнения (47) при 1=1+1.
Лемма 1 утверждает, что если матрица А системы (46) имеет диагональное преобладание, то справедливо неравенство )с,— а,а, ) ) ~1Ь, !. Следовательно, в первом уравнении системы (47) коэффйциент при у, по модулю больше коэффициента при у,~,, Поэтому выбор главного элемента по строке осуществлять не надо, переход к виду (48) корректен и условие устойчивости ')а,+ ) (1 автоматически выполняется. Если же диагональное преобладание не имеет места, то гарантировать отличие от нуля величины с, — а,ан равно как и неравенство ~а,+,1«-.1, невозможно.
В этом случае алгоритм монотонной прогонки может породить деление на нуль или сильную чувствительность к ошибкам округления, и следовательно, необходимо модифицировать такой алгоритм. Построение корректного алгоритма метода прогонки для системы (46), имеющей единственное решение, базируется на использовании выбора главного элемента по строкам в методе исключения Гаусса. В таком алгоритме монотонный порядок определения неизвестных у> может быть нарушен, и поэтому этот метод будем называть методом немонотонной прогонки. Переходим к описанию алгоритма немонотонной прогонки. Пусть в результате 1-го шага процесса исключения Гаусса с выбором главного элемента по строке, примененного к системе (46), 94 получена следующая «укороченная» система: Су,„— Ь,у, „, =-- Р, 1=1, — Ау,„+с,+,у„,— Ь„,у,„,=Ф, 1=1+1, (50) 1=1+2, (51) — а„у„„» + с„.,у, ~, — Ь, „,у,, = )„„„ — а,д,,+с,у,— Ь,у,„=~о 1+3(1(М вЂ” 1, (52) — ачуг«, + с уч = ~м, ! = Л', (53) где т, (1.
(При ! = 0 в (49) — (53) следует положить С = с„А =а„ Р = — 1„Ф = 1, и т, = О). Опишем (1+ 1)-й шаг процесса исключения. Стратегия выбора главного элемента по строке приводит нас к двум случаям: а) Если ! С( ) !Ь,(, то уравнение (49) преобразуется к виду у,„,— а,«,у,«, =р,~„а,„,=ЬУС, ~,~,=Р С, причем !а„,~(1, неизвестное с индексом т, находится через неизвестное с индексом !+!. Далее, при помощи полученного уравнения исключается у, из (50).
Зто дает следующее уравнение: (54) где обозначено т„,== !+1, С=с...— Аа„о Р=Ф+А(3„». Уравнение (51) не преобразуется, так как оно не содержит у,, но переписывается в виде — Ау,„„,+С„,у„,— Ь„,у„» =Ф, (55) где полагается А = а„„ Ф =- 1, » Сбъединяя (54) и (55) с (52), (53), получим новую «укороченную» систему вида (49) †(53), в которой ! заменено на 1+1. На этом (1+1)-й шаг заканчивается. б) Если ! С ( ( (Ь,(, то (49) преобразуется к виду уг+» и»+»у Ре 1 сс»+ С1Ь| Р»м Г1Ь» где снова !а„,~ (1, но на этот раз неизвестное с индексом 1+1 вычисляется через неизвестное с индексом тс Полученное уравнение используется для исключения у,«, из (50) и (51). Прн этом уравнение (50) будет преобразовано к виду (54), где т„, =т„С =с„»а„,— А, г" =Ф вЂ” с„ф,~„а уравнение (51)— к виду (55), где величины А и Ф переопределяются по формулам А=а, »и„„Ф==~„»+а„,(1,«,.
Уравнения (52), (53) не преобразовываются, так как не содержат у,„. Снова мы получаем систему вида (49) — (53). Она отличается от полученной в первом случае коэффициентами С и А и правыми частями Р и Ф, вычисленными по другим формулам. 95 Итак, описан один шаг процесса исключения с выбором главного элемента. Заметим, что если исходная система не вырождена, то в уравнении 149) коэффициенты С и Ь, одновременно в нуль обратиться не могут. Это обеспечивает корректность формул для прогоночных коэффициентов а, 1 и )1,, Так как все вычисляемые а, , по модулю не превосходят единицы, то процесс вычисления неизвестных у; на обратном ходе метода будет устойчив по отношению к ошибкам округления.
Для предлагаемого алгоритма порядок вычисления неизвестных может иметь немонотонный характер. Это требует хранения информации о том, какое неизвестное вычисляется через какое, уже найденное на предыдуших шагах неизвестное, при помощи прогоночных коэффициентов а,„; и р„,. Эту информацию можно хранить в виде двух целочисленных множеств индексов 0 и х: 0 = ~0п 1 <1< Л'), х= ~хо 1(1<Л'), так что неизвестные находятся по формулам у =а;+,у„+~;~„т=8„„л=х,~„1= = сЧ вЂ” 1, У-2, ..., О. Множества 0 и х строятся на прямом ходе метода. Полностью алгоритм метода немонотонной прогонки можно определить следующим образом, 1) Задаются начальные значения для С, А, с" и Ф: С=с„ А=аз, г'=1„Ф=1'„и фоРмально полагаетсЯ х,=О. 2) Последовательно для 1=0, 1, ..., У вЂ” 1 выполняются в зависимости от ситуации действия, описанные в пп.
а) или б): а) если )С!))Ь~(, то а;,,=.ЬУС, (3;„=Г(С, С=с;~,— Аа,„, г=Ф вЂ” с,. Я~ „0;„=1+1, х;„,=х,, А=-а;„а, „Ф=~,~,+ + а~+43 +и Замечание. Для 1=Л' — 1'переопределение А и Ф в пп. а) или б) проводить не нужно. 3) Вычисляется сначала неизвестное у„, где п=х~ по формуле у„= Р!С, а затем последовательно для 1= У вЂ” 1, Л' — 2,..., О вычисляются остальные неизвестные у„=а;+,у„+Ц„,, т=8;+„ п = ха+э. Отметим, что предлагаемый здесь алгоритм переходит в обычный алгоритм правой прогонки, если выполнены условия леммы 1. Элементарный подсчет числа арифметических действий для алгоритма метода немонотонной прогонки показывает, что в худшем случае, когда для любого 1 вычисления ведутся по формулам п.
б), требуется 9 = 12Л/ действий. Это в 1,6 раза больше, чем в алгоритме монотонной прогонки. Рассмотрим пример применения метода немонотонной прогонки. Пусть требуется решить следующую разностную задачу: — у;,+у,— У„,=О, 1 1(Л' — 1, (56) Уе Уч Задача (56) есть частный случай системы (46), в которой 1а= 1с Ь,=аз,=О,сс=сА,=1,)и=О, с,=а,=Ь,=1, 1~ — — О, 1<1<<У вЂ” . Если У не кратно 3, то решение задачи (56) существует и имеет вид (см. п.
1 3 4 гл. 1) (57) Алгоритмы правой и левой прогонок для (56) некорректны, так как при вычислении прогоночных коэффициентов ас для правой прогонки н $д,, для левой прогонки необходимо будет делить на нулевой знаменатель с, †п, или СА,, — ЬА ,$„, с. Алгоритм немонотонной прогонки позволяет получить точное решение (57). Приведем для иллюстрации (табл. 1) значении коэффициентов сап Рп а также 8; и кг длЯ Лг= 11.
Таблица 1 В 3. Метод прогонки для пятиточечных уравнений' 1. Алгоритм монотонной прогонки. Выше мы рассмотрели различные варианты метода прогонки, который применяется для нахождения решения трехточечных разностных уравнений, Как было отмечено ранее, такие разностные уравнения возникают при аппроксимации краевых задач для обыкновенных дифференциальных уравнений второго порядка.
При нахождении решения краевых задач для уравнений более высокого порядка можно использовать два способа. Первый способ состоит в переходе к системе дифференциальных уравнений первого порядка и построении соответствующей разностной схемы. В этом случае мы получим краевую задачу длн двухточечных векторных уравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
