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

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

.

Отсюда, погрешность

.

Определим выражение

При выводе последнего соотношения использована симметричность матрицы А,

.

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

Вторая производная

положительна в силу положительной определенности А, то есть выражение принимает наименьшее значение при найденном .

Вспоминая, что - невязка решения системы уравнений, получаем

.

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

,

где - наименьшее и наибольшее собственные значения матрицы А; n - номер итерации.

Неявный метод скорейшего спуска

Рассмотрим неявную итерационную схему вида

с симметричной и положительно определенной матрицей B.

Для погрешности эта схема принимает следующую форму:

.

Отсюда, .

Как и ранее, с учетом симметрии матрицы А, определим выражение

Благодаря положительной определенности матрицы А,

,

минимум полученного выражения достигается при значении итерационного параметра

.

Погрешность неявного метода скорейшего спуска оценивается неравенством:

,

где - наименьшее и наибольшее собственные значения матрицы ; n - номер итерации.

Контрольные вопросы и задания

• Какие методы решения системы линейных алгебраических уравнений называются прямыми и итерационными?

• Сформулируйте условия существования и единственности решения системы линейных алгебраических уравнений.

• Сформулируйте условия разрешимости системы линейных алгебраических уравнений методом Гаусса.

• Покажите, какую структуру будут иметь матрицы, равные произведениям , если А и В являются обратимыми верхними (нижними) треугольными матрицами.

• Как можно вычислить определитель матрицы коэффициентов, используя процедуру метода Гаусса?

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

• Выбор "главного" элемента при использовании метода Гаусса возможен с помощью перестановки либо строк, либо столбцов. Обоснуйте, какой вариант предпочтителен.

• Сформулируйте условия применимости метода "квадратного корня" для решения системы линейных алгебраических уравнений.

• Сравните методы Гаусса и квадратного корня для решения системы линейных алгебраических уравнений. Укажите достоинства и недостатки каждого из этих методов.

• Сформулируйте понятие устойчивости системы линейных алгебраических уравнений.

• Чему равно и что характеризует число обусловленности системы линейных алгебраических уравнений?

• Определите смысл условия теоремы 2.3 .

• Какую погрешность, относительную или абсолютную , целесообразно оценивать при выполнении вычислений на ЭВМ?

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

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

• Дайте определение понятия скорости сходимости итерационного процесса.

• Обоснуйте идею и поясните условия применимости метода Якоби.

• Обоснуйте идею и поясните условия применимости метода Зейделя.

• Покажите, что из условия B - 0,5A > 0 теоремы 2.4 следует существование обратной матрицы B^-1.

• Докажите справедливость неравенства (Dx, x) > 0, использованного при доказательстве следствия 1 из теоремы 2.4.

• Укажите условия применимости метода верхней релаксации.

• Сформулируйте условия сходимости стационарного итерационного метода.

• Сформулируйте задачу, решение которой приводит к построению полинома Чебышева на отрезках [-1, 1] и [a, b].

• В чем преимущество метода решения системы линейных алгебраических уравнений с чебышевским набором параметров?

• Опишите порядок выбора итерационных параметров в методе минимальных невязок.

• Опишите порядок выбора итерационных параметров в методе минимальных поправок.

• Опишите порядок выбора итерационных параметров в явном методе скорейшего спуска.

• Опишите порядок выбора итерационных параметров в неявном методе скорейшего спуска.