Достаточные условия применимости метода прогонки.

Теорема 3.1. Достаточными условиями применимости метода прогонки являются: для любого,,,. (3.4)

Доказательство.

При выводе формул прогонки мы делили на некоторые величины, не задумываясь, не равны ли они нулю, а именно на () и . Докажем, что при выполнении условий (3.4) эти величины не равны нулю.

Докажем сперва, что , для любого. Доказательство проведем методом математической индукции. Приусловие выполняется:. Сделаем индуктивное предположение, что, и докажем, что. Рассмотрим разность

, так как .

Из полученного результата и (3.2) следует, что . По принципу математической индукции все величины, а следовательно,для всех. Так какпо условию, то, а следовательнодля.

Исследуем теперь величину . Докажем, что она строго больше нуля. Отметим, что. Из условий (3.4) следует, чтоине могут равняться 1 одновременно, то есть либо, либо.

Пусть , тогда. Изследует, что все, следовательно и, а также. Значит,. Пусть. Так как, то. Значит.

Итак, доказано, что . Теорема доказана полностью.

Итерационные методы. Метод простых итераций.

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

Соотношение задает отображение, где–m-мерное арифметическое пространство. Зададим на нем метрику, например, так:

.

Выразим неизвестные из уравнений системы.

Полученную систему можно записать в компактной форме: , где,,и,,,,.

Если отображение является сжатым отображением в себя, то для решения системыможно применить принцип сжатых отображений Банаха.

Найдем условия сжатости отображения B.

.

Следовательно, оператор B будет оператором сжатия, если или, или для всехi . Следовательно, для всехi ,. Здесь мы пользовались тем, что.

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

Пример.

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

Более подробно итерационный процесс можно записать так:

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

Если в исходной системе не выполняется условие диагонального преобладания, то следует путем линейных преобразований привести систему к требуемому виду.

Лекция 11.

«Метод Зейделя.

Метод Ньютона решения систем нелинейных уравнений.»

Метод Зейделя.

Пусть вновь дана система линейных алгебраических уравнений вида , где,– матрица коэффициентов системы,– искомый вектор,– заданный вектор свободных членов.

Метод Зейделя является своеобразной модификацией метода простой итерации и при прочих равных условиях дает более быструю сходимость.

Преобразуем систему к виду, где,,и,,,,.

Построим итерационный процесс следующим образом:

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

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