Лекции.Орг


Поиск:




Метод минимальных поправок




Содержание

1. Введение. Постановка задачи..................................................................... 3

2. Описание методов решения задачи............................................................ 4

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

2.2. Метод минимальных поправок............................................................. 4

2.3. Метод скорейшего спуска.................................................................... 5

2.4. Метод сопряженных градиентов.......................................................... 5

3. Алгоритмы и блок-схемы решения............................................................. 8

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

3.2. Метод минимальных поправок............................................................. 9

3.3. Метод скорейшего спуска.................................................................. 10

3.4. Метод сопряженных градиентов......................................................... 11

4.Руководство пользователя......................................................................... 13

5. Тестирование и оптимизация................................................................... 15

6. Выводы.................................................................................................... 18

Список использованных источников........................................................... 19

Приложение 1. Контрольные примеры......................................................... 20

Приложение 2. Код программы.................................................................... 22

 


Введение. Постановка задачи.

Большое количество задач математики и физики сводится к решению дифференциальных уравнений в частных производных, решение которых, в свою очередь, приводит к решению систем линейных алгебраических уравнений (СЛАУ). Методы решения СЛАУ, можно разделить на прямые методы, позволяющие получить точное решение системы (к ним относится, например, метод Гаусса, метод Крамера и т. д.) и итерационные методы, позволяющие получить решение системы с заданным приближением. Среди итерационных методов особое место занимают методы вариационного типа, особенностью которых является то, что при их использовании нет необходимости знать границы спектра матрицы системы.

Итак, сформулируем задачу:

Дана система линейных уравнений

где A симметричная положительно определенная матрица.

Требуется решить данную СЛАУ следующими итерационными методами вариационного вида:

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

2. Метод минимальных поправок

3. Метод скорейшего спуска

4. Метод сопряженных градиентов

 

Методы решения СЛАУ рассматриваются практически в каждой книге по численным методам. Общее описание алгоритмов для каждого метода дано, например, в книге Самарского А.А., Гулина А.В. «Численные методы» [3]. Также популярными книгами являются: М.Ю. Баландин, Э.П. Шурина “Методы решения СЛАУ большой размерности” [1], Y.Saad “Iterative Method for Sparse Linear System” [5]. В перечисленных книгах, описаны такие методы как CG (Conjugate Gradient – метод сопряжённых градиентов) и MinRES (Minimal Residual – метод минимальных невязок). В книге [5] изложены не только базовые алгоритмы данных методов, но и указания к их практической реализации.


Описание методов решения задачи

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

Рассмотрим систему с матрицей A = AT >0. Обозначим через

(1)

невязку, которая получается при подстановке приближенного значения xk, полученного на k -й итерации, в уравнение (1). Заметим, что погрешность zk=xk - х и невязка rk связаны равенством Azk=rk.

Рассмотрим явный итерационный метод

, (2) <=> (3)

где параметр t k +l выбирается из условия минимума погрешности || rk +1|| при заданной норме || rk ||.Метод (2) называется методом минимальных невязок.

Найдем явное выражение для параметра t k +l. Из (3) получаем

, (4) => (5)

т. е. rk удовлетворяет тому же уравнению, что и погрешность zk=xk - х. Возводя обе части уравнения (5) для невязки скалярно в квадрат, получаем

(6)

Отсюда видно, что rk +1|| достигает минимума, если

(7)

Таким образом, в методе минимальных невязок переход от k -й итерации к (k +1)-й осуществляется следующим образом. По найденному значению xk вычисляется вектор невязки rk=Axk - f и по формуле (7) находится параметр t k +l. Затем по формуле (3) досчитывается вектор xk+ 1.

Метод минимальных невязок (3), (7) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром t.

Метод минимальных поправок

Рассмотрим неявный итерационный метод вида

, (8)

Запишем этот метод в виде

. (9)

Вектор w k =B -1 rk называется поправкой на (k +1)-й итерации. Она удовлетворяет тому же уравнению, что и погрешность zk=xk - x неявного метода, т. е.

уравнению

. (10)

Будем предполагать, что B = BT >0. Методом минимальных поправокназывается неявный итерационный метод (8), в котором параметр t k +lвыбирается из условия минимума нормы ||w k +1|| B =(B w k +1,w k +1)1/2 при заданном векторе w k. В случае B = Е метод минимальных поправок совпадает с методом минимальных невязок.

Найдем выражение для итерационного параметра t k +l. Перепишем (10) в виде

и вычислим

.

Отсюда следует, что минимум этого выражения достигается при

. (11)

Для реализации метода минимальных поправок требуется на каждой итерации решить две системы уравнений B w k= rk и Bvk=A w k, откуда найдем вектор vk = B -1 А w k (воспользуемся формулой (9)).

Скорость сходимости метода минимальных поправок определя­ется границами спектра обобщенной задачи на собственные значения

. (12)

Метод скорейшего спуска

Рассмотрим явный метод (2) и выберем итерационный параметр t k +l из условия минимума || zk +1|| A при заданном векторе zk, где zk +1 =xk +1- x. Поскольку погрешность zk удовлетворяет уравнению

, то

.

Следовательно, это выражение достигает минимума, если

.

Величина zk=xk - x здесь неизвестна (так как неизвестно точное решение х), поэтому надо учесть, что Azk=rk=Axk - f, и вычислять t k +l по формуле

. (13)

 





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 4487 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Неосмысленная жизнь не стоит того, чтобы жить. © Сократ
==> читать все изречения...

765 - | 677 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.012 с.