Лекция 7. Функционал ошибки

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

Теорема.	Если ( ) и отображение (оператор шага для ошибки: ) непрерывно при , то , т.е. .
Док–во.	Т.к. , то . Предположим, что . Т.к. , то . Т.к. , то . Тогда, выполнив предельный переход в соотношениях получим противоречие: .

Обычно используют нормы, порождаемые симметричной положительно определенной матрицей: .

Доказать: если , то

– скалярное произведение, – норма в .

Метод полной релаксации

для решения системы с матрицей – очередное приближение определяется по известному приближению за шагов:

где параметр выбирается из условия минимума .

Теорема.	и .
Док–во.	Т.к. , то имеем . Очевидно, что при будет максимальное уменьшение ошибки (полная релаксация): . , если хотя бы одна из компонент невязки (в противном случае , т.е. ). Итак, функционал ошибки строго убывает. Найдем оператор шага для ошибки: имеем (проверить!): или – метод Зейделя (он сходится) – непрерывный (всюду) оператор шага по теореме о функционале ошибки.

Метод неполной релаксации

для решения системы с матрицей – очередное приближение определяется по известному приближению за шагов:

где параметр , т.е. ошибка уменьшается меньше, чем в методе полной релаксации ( ):

Расчетные формулы имеют вид (проверить!):

или

Теорема.	Если , то метод неполной релаксации сходится .
Док–во	практически совпадает с доказательством сходимости метода полной релаксации.

Оценка сходимости методов релаксации

Итак, ошибка монотонно убывает в норме . Оценим .

Т. к.

, где , то , если .

.

Т.к. , то

где .

Пусть .

Т.к. ,

то .

Теорема.	где постоянные и таковы, что ( , )
Док–во	очевидно.

Доказать: .

Доказать: .

Пример

,

,

т.к. , то и ,

тогда (проверить):

верхняя релаксация	, ,
полная релаксация	,

т.е. метод верхней релаксации в раз дешевле.

Лекция 8.

Градиент, метод наискорейшего спуска

Как выбирать вектор при построении итерационного метода из условия минимизации ошибки: ?

Если , то

Следовательно, .

Теорема.	Метод наискорейшего спуска сходится , если .
Док–во.	минимум правой части достигается при : , если . Очевидно, что оператор : непрерывен всюду, кроме , быть может, 0. .