Метод наискорейшего спуска для решения линейных систем

Федеральное государственное  образовательное учреждение высшего  
профессионального образования 
"Финансовый университет при Правительстве Российской Федерации" 

Кафедра «Прикладная математика»

 

 

Лабораторная работа по дисциплине «Численные методы» на тему:

«Метод наискорейшего спуска для решения линейных систем»

 

 

 

 

 

    

Выполнила:

студентка гр. ПМ 3-3

Вишнякова Е.Е.

Научный руководитель:

д. ф.-м. н. Делицын А. Л.

 

 

 

 

 

 

 

 

Москва 2012 г.

 

Оглавление

 

 

 

 

Введение

 

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

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

Все программы  написаны в программном пакете MATLAB Version 7.6.0.324 (R2008a).

 

 

1. Теоретическая справка

Пусть

       (1)

– заданная линейная система, где – положительно-определённая матрица.

Решение этой системы  связано с поиском вектора, дающего  минимум функционалу

,     (2)

отличающегося лишь постоянным, но заранее неизвестным слагаемым *, *) от функции ошибки . Здесь * – точное решение системы, совпадающее с вектором, реализующим минимум функционал , * – вектор ошибки.

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

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

Так как 

=

= ,

то это выражение  достигает минимума при

   ,     (3)

и этот минимум равен

.     (4)

Таким образом,

,

.

Далее определяется , где и

.

Процесс продолжается далее  по формулам

      (5)

,   (6)

где      .          (7)

При этом

.    (8)

 

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

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

Процесс прекращается при  достижении заданной точности :

. 

2. Практическая часть

1. Ручная реализация метода

Имеем систему линейных уравнений  ,    (9)

где  – положительно-определённая матрица,

Решим данную систему методом наискорейшего спуска с точностью .

• Пусть начальное приближение
• Рассчитываем вектор невязок = =

 

• Вычисляем 
• Находим  *

Приведённые и следующие  расчёты запишем в виде таблицы:

i
0				2
1			1,5	0,2
2			0,3	0,2
3			1,5	0,02
4			0,3	0,02
5			1,5	0,002 <

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

2. Реализация метода средствами MATLAB

• Будем решать ту же систему (9), но уже с помощью функции GradStDescent (gradient steepest descent), предварительно написанной в MATLAB (см. рис. 2.1), согласно алгоритму, приведённому в теоретической справке данной работы. В свою очередь функция GradStDescent содержит ещё одну функцию DefinSylv, также написанную автором (см. рис. 2.2), которая является ничем иным, как тест на положительную / отрицательную определённость матрицы , согласно критерию Сильвестра о положительной определённости квадратичной формы. Соответственно, если пользователь введёт не положительно-определённую матрицу, то он не сможет воспользоваться ни функцией GradStDescent для нахождения решения системы линейных уравнений, ни методом наискорейшего спуска вообще.

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

 

Текст всех программ приведён в Приложении 1.

Рис. 2.1. Функция GradStDescent

Рис. 2.2. Функция DefinSylv

Рис. 2.3. Решение системы (9) с помощью функции GradStDescent

 

• Далее проводится та же процедура нахождения вектора  в MATLAB с помощью вышеупомянутых функций, но уже для произвольно взятой матрицы A(10x10) (см. рис. 2.4 и Приложение 1):

,

     

     

     

         4

 

Рис. 2.4. Решение системы (9) с матрицей A(10x10) с помощью функции GradStDescent

 

Заключение

 

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

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

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

 

 

 

 

 

 

 

Список литературы

 

1. Д. К. Фаддеев, В. Н. Фаддеева – Вычислительные методы линейной алгебры.
2. А. Л. Делицын – Лекции по численным методам.
3. И. Е. Денежкина – Численные методы
4. Свободная энциклопедия Википедия http://ru.wikipedia.org/wiki/
5. Справочная система MATLAB  
   

Приложение 1

1.Создание функции DefinSylv

 

function [defin] = DefinSylv (A)

% Создаём функцию DefinSylv с аргументом A, значением которой будет + или

% -, в зависимости  от наличия положительной определённости  матрицы A

 

for i=1:sqrt(numel(A))

    Z=A(1:i,1:i);

    if det(Z)>0

        defin='+';

    else

        defin='-';

    end

end

end

 

 

2.Создание функции GradStDescent

 

function [X] = GradStDescent(A, Y, eps)

% Создаём функцию  GradStDescent с аргументами A, Y и eps, значением которой

% будет искомый  вектор X

 

[defin] = DefinSylv(A);

% Проводим тест  на положительную определённость  матрицы A

if defin == '+'

    % Функция сработает только для положительно определённой матрицы A

    X=Y;

    % Начальное приближение = вектор Y

    r=Y-A*X;

    % Находим вектор невязок

    while norm(r,inf)> eps

        % Цикл завершится, когда решение достигнет заданной точности

        a=dot(r,r)/dot(A*r,r);

        X=X+a*r;

        r=Y-A*X;

    end

else disp ('Enter positive defined matrix')

end

end

 

 

3.Реализация функции GradStDescent

 

[X] = GradStDescent (A, Y, eps);

 X;