Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Новосибирский государственный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

BMLA.DOC

Скачиваний:

Добавлен:

09.11.2019

Размер:

3.4 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 138 9 10 11 12 13 > Следующая >>>

Метод минимальных невязок

В итерационном процессе параметр будем выбирать из условия минимизации невязки: .

Теорема.

сходится , если .

_{Док–во.}

минимум правой части достигается при :

, если .

Очевидно, что оператор :

непрерывен всюду, кроме , быть может, 0. .

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

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

_{Теорема.}		Если , то метод простой итерации сходится при ,

		При .
_{Док–во.}
	т.к. функция выпукла вниз. , метод сходится. Оптимальный параметр выбираем из условия легко проверить, что ,

Оценки сходимости мнс и ммн

_{Теорема.}

Если , то для ошибки метода наискорейшего спуска:

справедливы оценки:

Док-во.

Так как

то .

Т.к.

то .

_{Теорема.}

Если , то для метода минимальных невязок:

справедливы оценки:

Док-во.

Так как

и , то .

Т.к. и

Лекция 9. Метод Ричардсона с чебышевскими параметрами Задача оптимизации параметров

Параметры в итерационном методе можно выбирать из условия минимизации спектрального радиуса матрицы (оператора) ошибки за шагов: .

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

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

Т.к. , а последнюю минимаксную задачу решать проще (почему?), мы будем искать :

т.е. решать задачу о поиске полинома степени , наименее уклоняющегося от нуля на отрезке при условии .

Тогда, т.к. , где – корни полинома , и .

Если , то и, следовательно,

– оценка сходимости метода.

Полином Чебышева и решение задачи оптимизации параметров

Очевидно, что , – полиномы.

Т.к. , то при имеем – полином при любом .

Точки экстремумов : :

, .

Корни полинома : :

, .

Линейное преобразование : .

Рассмотрим полином: .

Очевидно, что , – корни полинома.

Покажем, что этот полином наименее уклоняется от нуля на интервале среди всех полиномов , т.е. .

Теорема.

Если , то .

Док-во.

Пусть ,

тогда : .

Так как

полином имеет экстремумы (одинаковые по модулю) в точках : , : , и знакопеременна:

то разность

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