Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (doc) (1113731), страница 5

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

Текст из файла (страница 5)

Найденное значение является границей интервала сходимости метода простой итерации

. 109109\* MERGEFORMAT ()

Это неравенство нам уже известно. Оно было получено ранее из теоремы Самарского как достаточное условие сходимости. Дополнительный анализ на основе леммы 2 позволяет уточнить результат. Теперь мы установили, что принадлежность итерационного параметра интервалу 109 является необходимым и достаточным условием сходимости метода простой итерации.

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

.

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

Найдем на отрезке точку , в которой убывающая функция сравнивается с возрастающей функцией . Она определяется уравнением

,

которое дает

. 110110\* MERGEFORMAT ()

В результате получаем:

111111\* MERGEFORMAT ()

Свое наименьшее значение норма матрицы достигает при :

. 112112\* MERGEFORMAT ()

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

В заключение заметим, что формула 109, определяющая границу интервала сходимости , и формула 110 для оптимального значения итерационного параметра представляют прежде всего теоретический интерес. Обычно при решении СЛАУ наибольшее и наименьшее характеристические числа матрицы неизвестны, так что подсчитать величины и заранее невозможно. В результате итерационный параметр нередко приходится подбирать прямо в процессе вычислений методом проб и ошибок.

Задача 2.

Рассмотреть систему двух уравнений с двумя неизвестными

113113\* MERGEFORMAT ()

и построить для нее приближенное решение с помощью метода простой итерации.

Выпишем сразу решение системы 113

, , 114114\* MERGEFORMAT ()

чтобы потом иметь возможность сравнивать его с членами итерационной последовательности.

Перейдем к решению системы методом простой итерации. Матрица системы имеет вид

.

Она самосопряженная и положительно определенная, поскольку

.

Составим характеристическое уравнение для матрицы и найдем его корни:

,

,

С их помощью можно определить границу интервала сходимости и оптимальное значение итерационного параметра :

, .

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

, где

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

, , ,

, , ,

, , ,

, , .

Норма невязок, хотя и медленно, но убывает, что говорит о сходимости процесса. Это же видно из сравнения членов итерационной последовательности с решением системы 114. Медленная сходимость связана с плохой обусловленностью матрицы :

.

1. Неявные итерационные методы. Метод Зейделя.

Вернемся к общей записи итерационного стационарного процесса в канонической форме 66.

Рассмотрим произвольную квадратную матрицу:

.

Разложим её на сумму трех матриц

, 115115\* MERGEFORMAT ()

где - диагональная часть матрицы , которая содержит элементы , стоящие на главной диагонали:

,

- нижняя треугольная матрица

,

- верхняя треугольная матрица.

.

В классическом методе Зейделя, записанном в канонической форме, полагают

116116\* MERGEFORMAT ()

В результате формула 66 принимает вид:

,

или

. 117117\* MERGEFORMAT ()

Перейдем от векторной формы записи рекуррентной формулы 117 к построчной:

118118\* MERGEFORMAT ()

Уравнения 118 позволяют последовательно рассчитать компоненты вектора - ой итерации подобно тому, как это делалось во время обратного хода в методе Гаусса:

, . 119119\* MERGEFORMAT ()

Формула 119 предполагает, что , . Если матрица удовлетворяет условиям теоремы Самарского 85: , то, согласно неравенству 82, все ее диагональные элементы должны быть строго положительными и, тем самым, не могут обращаться в ноль.

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

Сходимость метода Зейделя в случае, когда матрица удовлетворяет условию теоремы Самарского, т.е. является самосопряженной и положительно определенной, будет доказана в следующем разделе. К этому утверждению добавим без доказательства еще один результат: метод Зейделя сходится для любой системы 63, в которой матрица обладает свойством диагонального преобладания.

Задача 3.

Рассмотреть систему 113 (см. задачу 2) и построить для нее приближенное решение с помощью метода Зейделя.

В рассматриваемом случае рекуррентные формулы 119 для построения -ой итерации по -ой итерации принимают вид:

120120\* MERGEFORMAT ()

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

, , ,

, , ,

, , .

Обсудим полученные результаты. Начнем с невязки. Ее вторая компонента все время остается равной нулю, поскольку второе уравнение системы на каждой итерации выполняется, как видно из 120, точно. Первые компоненты невязки и норма убывают по закону геометрической прогрессии с знаменателем , т.е. гораздо быстрее, чем в методе простой итерации. Хорошая сходимость процесса видна также из прямого сравнения членов итерационной последовательности с точным решением системы .

1. Метод верхней релаксации

Модифицируем метод Зейделя. С этой целью введем параметр и запишем рекуррентное соотношение 66 в виде

. 121121\* MERGEFORMAT ()

В данном случае

, . 122122\* MERGEFORMAT ()

При мы возвращаемся к методу Зейделя.

Соотношению 121 можно придать вид

. 123123\* MERGEFORMAT ()

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

Для построения алгоритма вычисления очередной итерации нужно разделить в левой части рекуррентной формулы 123 члены, содержащие и , и придать ей форму, аналогичную 117:

. 124124\* MERGEFORMAT ()

Если перейти от векторной записи к записи типа 118 в виде отдельных уравнений, то можно получить для компонент очередной итерации формулы, структурно похожие на 119:

, . 125125\* MERGEFORMAT ()

Исследуем условия сходимости метода верхней релаксации при дополнительном предположении, что матрица удовлетворяет условиям теоремы Самарского 85. Самосопряженность матрицы означает, что , . Отсюда следует

. 126126\* MERGEFORMAT ()

Составим для рассматриваемого случая матрицу . Согласно 122

. 127127\* MERGEFORMAT ()

Запишем условие ее положительной определенности

. 128128\* MERGEFORMAT ()

Второе слагаемое в выражении 127 не дает вклада в квадратичную форму 128 в силу соотношения 126.

Матрица является, по предположению, положительно определенной. Следовательно, все ее диагональные элементы строго положительны: , . Это означает положительную определенность матрицы : . В результате знак выражения 128 определяется знаком первого множителя, так что достаточное условие для сходимости итерационной последовательности метода верхней релаксации принимает вид:

129129\* MERGEFORMAT ()

Метод Зейделя, соответствующий случаю , удовлетворяет этому условию.

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

Задача 4

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

Выпишем для рассматриваемого случая матрицы и , определяющие итерационный процесс:

, .

С их помощью рекуррентное соотношение 124, записанное покомпонентно, принимает вид:

Характеристики

Список файлов лекций