1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 55
Текст из файла (страница 55)
Поэтому иxn+1 может быть произвольным. Итак, для начала прогонки можноположить, к примеру,ξ1 = η1 = xn+1 = 0.(3.95)Можно немного сэкономить на реализации прогонки, начав её прямой ход с назначенияξ2 = −c1 /b1 ,η2 = d1 /b1 .Оно вытекает как из первого уравнения системы (3.90), так и из нашихформул (3.93)–(3.94) с ξ1 = η1 = 0. Далее находятся все прогоночныекоэффициенты, а затем мы сразу полагаемxn = ηn .После этого в обратном ходе прогонки находятся неизвестные xn−1 ,. . . , x2 , x1 .Дадим теперь достаточные условия выполнимости метода прогонки, т.
е. того, что знаменатели в расчётных формулах прямого ходане обращаются в нуль. Эти условия, фактически, будут также обосновывать возможность приведения трёхдиагональной матрицы исходнойСЛАУ к двухдиагональному виду (3.91) преобразованиями прямого хода метода Гаусса без перестановки строк или столбцов, так как этипреобразования являются ничем иным, как прямым ходом метода прогонки.3363. Численные методы линейной алгебрыПредложение 3.8.1 Если в системе линейных алгебраических уравнений с трёхдиагональной матрицей (3.90) имеет место диагональное преобладание, т. е.|bi | > |ai | + |ci |,i = 1, 2, . . .
, n,то метод прогонки c выбором начальных значений согласно (3.95) является реализуемым.По поводу формулировки Предложения 3.8.1 можно заметить, чтоусловие диагонального преобладания в матрице влечёт её строгую регулярность, как мы видели в §3.6д. Поэтому в силу Теоремы 3.6.2 существует LU-разложение такой матрицы, и оно может быть получено спомощью прямого хода метода Гаусса без перестановки строк и столбцов. Но это и означает реализуемость метода прогонки.
Ниже, тем неменее, даётся другое доказательство этого факта, которое позволяетпомимо установления реализуемости дать ещё числовые оценки «запаса устойчивости» прогонки, т. е. того, насколько сильно знаменателивыражений (3.93)–(3.94) для прогоночных коэффициентов отличны отнуля в зависимости от элементов матрицы СЛАУ.Доказательство. Покажем по индукции, что в рассматриваемой реализации прогонки для всех индексов i справедливо неравенство |ξi | < 1.Прежде всего, ξ1 = 0 и потому база индукции выполнена: |ξ1 | < 1.Далее, предположим, что для некоторого индекса i уже установленаоценка |ξi | < 1. Если соответствующее ci = 0, то из (3.93) следуетξi+1 = 0, и индукционный переход доказан. Поэтому пусть ci 6= 0.Тогда справедлива следующая цепочка соотношений|ci |ci =|ξi+1 | = −ai ξi + bi |ai ξi + bi ||ci |≤ |bi | − |ai | · |ξi |из оценки снизу для модуля суммы<|ci |в силу диагонального преобладания|ai | + |ci | − |ai | · |ξi |=|ci ||ci |≤= 1,|ai |(1 − |ξi |) + |ci ||ci |3373.8.
Метод прогонкигде при переходе ко второй строке мы воспользовались известным неравенством для модуля суммы двух чисел:|x + y| ≥ |x| − |y|.(3.96)Итак, неравенства |ξi | < 1 доказаны для всех прогоночных коэффициентов ξi , i = 1, 2, . . . , n + 1.Как следствие, для знаменателей прогоночных коэффициентов ξi иηi в формулах (3.93)–(3.94) имеемai ξi + bi ≥ |bi | − |ai ξi | по неравенству (3.96)= |bi | − |ai | |ξi | в силу диагонального преобладания> |ai | + |ci | − |ai | · |ξi | из-за диагонального преобладания= |ai |(1 − |ξi |) + |ci |≥ |ci | ≥ 0 в силу оценки |ξi | < 1.Иными словами ai ξi + bi строго отделены от нуля, что и требовалосьдоказать.Отметим, что существуют и другие условия реализуемости методапрогонки.
Например, некоторые из них требуют от матрицы более мягкое нестрогое диагональное преобладание (3.18), но зато более жёсткие,чем в Предложении 3.8.1, условия на коэффициенты системы. Весьмапопулярна, в частности, такая формулировка [17]:Предложение 3.8.2 Если в трёхдиагональной системе линейных алгебраических уравнений (3.90) побочные диагонали не содержат нулей,т.
е. ai 6= 0, i = 2, 3, . . . , n, и ci 6= 0, i = 1, 2, . . . , n − 1, имеет местонестрогое диагональное преобладание|bi | ≥ |ai | + |ci |,i = 1, 2, . . . , n,но хотя бы для одного индекса i это неравенство является строгим,то метод прогонки реализуем.Нетрудно убедиться, что реализация прогонки требует линейного взависимости от размера системы количества арифметических операций(примерно 8n), т. е. весьма экономична.3383.
Численные методы линейной алгебрыНа сегодняшний день разработано немало различных модификацийметода прогонки, которые хорошо приспособлены для решения тех илииных специальных систем уравнений, как трёхдиагональных, так и более общих, имеющих ленточные или даже блочно-ленточные матрицы[17]. В частности, существует метод матричной прогонки [30].3.9Стационарные итерационные методыдля решения линейных систем3.9аКраткая теорияИтерационные методы решения уравнений и систем уравнений —это методы, порождающие последовательность приближений {x(k) }∞k=0к искомому решению x⋆ , которое получается как пределx⋆ = lim x(k) .k→∞Допуская некоторую вольность речи, обычно говорят, что «итерационный метод сходится», если к пределу сходится конструируемая импоследовательность приближений {x(k) }.Естественно, что на практике переход к пределу по k → ∞ невозможен в силу конечности объёма вычислений, который мы можем произвести.
Поэтому при реализации итерационных методов вместо x⋆ обычно довольствуются нахождением какого-то достаточно хорошего приближения x(k) к x⋆ . Здесь важно правильно выбрать условие остановкиитераций, при котором мы прекращаем порождать очередные приближения и выдаём x(k) в качестве решения. Подробнее мы рассмотримэтот вопрос в §3.14.Общая схема итерационных методов выглядит следующим образом:выбираются одно или несколько начальных приближений x(0) , x(1) ,. . .
, x(ν) , а затем по их известным значениям последовательно вычисляютсяx(k+1) ← Tk (x(0) , x(1) , . . . , x(k) ),k = ν, ν + 1, ν + 2, . . . ,(3.97)где Tk — отображение, называемое оператором перехода или оператором шага (иногда уточняют, что k-го). Конечно, в реальных итерационных процессах каждое следующее приближение, как правило, зависит не от всех предшествующих приближений, а лишь от какого-то их3.9. Стационарные итерационные методы339фиксированного конечного числа. Более точно, итерационный процесс(3.97) называют p-шаговым, если его последующее приближение x(k+1)является функцией только от p предшествующих приближений, т.
е.от x(k) , x(k−1) , . . . , x(k−p+1) . В частности, наиболее простыми в этомотношении являются одношаговые итерационные методыx(k+1) ← Tk (x(k) ),k = 0, 1, 2, . . . ,в которых x(k+1) зависит лишь от значения одной предшествующейитерации x(k) . Для начала работы одношаговых итерационных процессов нужно знать одно начальное приближение x(0) .Итерационный процесс называется стационарным, если операторперехода Tk не зависит от номера шага k, т. е.
Tk = T , и нестационарным в противном случае. Линейным p-шаговым итерационнымпроцессом будут называться итерации, в которых оператор переходаимеет видTk (x(k) , x(k−1) , . . . , x(k−p+1) )= C (k,k) x(k) + C (k,k−1) x(k−1) + . . . + C (k,k−p+1) x(k−p+1) + d(k)с какими-то коэффициентами C (k,k) , C (k,k−1) , . .
. , C (k,k−p+1) и свободным членом d(k) . В случае векторной неизвестной переменной x всеC (k,l) являются матрицами подходящих размеров, а d(k) — вектор тойже размерности, что и x. Матрицы C (k,l) часто называют матрицамиперехода рассматриваемого итерационного процесса.Итерационные методы были представлены выше в абстрактной манере, как некоторые конструктивные процессы, которые порождаютпоследовательности, сходящиеся к искомому решению. В действительности, мотивации возникновения и развития итерационных методовявлялись существенно более ясными и практичными. Итерационныеметоды решения уравнений и систем уравнений возникли как уточняющие процедуры, которые позволяли за небольшое (удовлетворяющеепрактику) количество шагов получить приемлемое по точности приближённое решение задачи.
Многие из классических итерационных методов явно несут отпечаток этих взглядов и ценностей.Ясно, что для коррекции приближённого решения необходимо знать,насколько и как именно оно нарушает точное равенство обеих частейуравнения. На этом пути возникает важное понятие невязки приближённого решения x̃, которая определяется как разность левой и правой3403.
Численные методы линейной алгебрычастей уравнения (системы уравнений) после подстановки в него x̃. Исследование этой величины, отдельных её компонент (в случае системыуравнений) и решение вопроса о том, как можно на основе этой информации корректировать приближение к решению, составляет важнейшую часть работы по конструированию и исследованию итерационныхметодов.Мы подробно рассматриваем различные итерационные методы длярешения нелинейных уравнений и систем уравнений в Главе 4, а здесьосновное внимание будет уделено итерационному решению систем линейных алгебраических уравнений и проблемы собственных значений.Причины, по которым для решения систем линейных уравненийитерационные методы могут оказаться более предпочтительными, чемпрямые, заключаются в следующем.
Большинство итерационных методов являются самоисправляющимися, т. е. такими, в которых погрешность, допущенная в вычислениях, при сходимости исправляется в ходеитерирования и не отражается на окончательном результате. Это следует из конструкции оператора перехода, в котором обычно по самомуего построению присутствует информация о решаемой системе уравнений (что мы увидим далее на примерах).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
