Минимизация квадратных функций. Градиентный метод наискорейшего спуска

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

факультет прикладной математики - процессов управления

Курсовая работа №2: Минимизация квадратных функций. Градиентный метод наискорейшего спуска.

Задание №1

Выполнил: Винницкий Иван

группа 28 

Санкт-Петербург, 2003

Задание 1

Изложить градиентный метод наискорейшего спуска(ГМНС) для отыскания минимума квадратной функции

f(x) = 0,5<Ax,x>+<c,x>        (1)

где x=(x₁, … , x_n)^T, c=(c₁, … , c_n)^T , A=(a_ij) _i,j=1…n – симметричная положительно определённая матрица. Указать скорость его сходимости и связь с решением системы уравнений Ax+b=0.

Задание 2

Реализовать ГМНС на компьютере. В качестве критерия прекращения спуска предусмотреть любой из трёх следующих:

a) ||f’(x^k) ||< ξ

b) ||x^k-x^k-1||< ξ

c) f(x^k-1)-f(x^k)< ξ

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

/ 1.5  1.6  1.7  1.8  \

A=     |  1.6  2.5  1.2  1.3   |

|  1.7  1.2  3.5  1.4   |

\ 1.8  1.3  1.4  4.5  /

c= (3,4; 3,8; 2,6; 5,8)^T

Выходные данные программы: x^k, ||x^k-x^k-1||, k –номер последнего шага

Задание 3

Решить систему и сравнить ||x^*-x^k|| с ||x^k-x^k-1||. Проверить вычисления при различных начальных векторах x⁰ и проследить за зависимостью k от x⁰.

ОТВЕТ Задание 1

ОПР.(градиент) Рассмотрим вещественную функцию F(x)=F(x₁, x₂… x_n) определённую в Rⁿ. Предполагаем, что функция F(x)=F(x₁, x₂… x_n) имеет непрерывные частные производные. Пусть y – произвольный вектор единичной длины: (y,y)=||y||²=1 и α – вещественное число. Производная функции F(x) по направлению y обозначается ¶F(x)/ ¶y и определяется следующим образом:

¶F(x)/ ¶y = lim{α ®0}[f(x+ αy) – F(x)]/α = ¶F(x+αy)/ ¶α |_α=0

Очевидно, имеем:

¶F(x)/ ¶y = dF(x₁+ α y₁, x₂ + αy₂, … x_n + αy_n)/dα |_α=0=(¶F(x)/ ¶x₁) y₁+(¶F(x)/¶x₂) y₂+…+ (¶F(x)/¶x_n)y_n=(z, y),

где z=  (¶F(x)/¶x₁ ,  ¶F(x)/¶x₂ , … ¶F(x)/¶x_n )^T есть вектор, называемый градиентом функции F(x).

Итак, для производноц функции F(x) по направдению y получили формулу. По неравенству Буняковского:

-||z||₂ =<(z,y)=<||z||₂

Таким образом, видно, что при y=z/||z||₂ производная по направлению ¶F(x)/ ¶y = ||z||₂ имеет наибольшее значение, а при y = -z/||z||₂ – наименьшее: ¶F(x)/ ¶y = -||z||₂. Следовательно, направление градиента в точке x есть направление наибольшей скорости роста функции F(x) в этой точке, а противоположное направление есть направление наибольшей скорости убывания F(x).

.

Рассмотрим функционал в Rⁿ

f(x)= 0,5<Ax,x>+<c,x> -> 2f(x)= <Ax,x>-2<b,x>= H(x)   (1)

и найдём его градиент. Имеем:

H(x+αy)=(A(x+αy),x+αy)-2(b,x+αy)=H(x)+ 2α(Ax-b,y)+ α²(Ay,y), где α –вещественное число, y – произвольный вектор единичной длины.     

Полученное неравенство называется формулой сложения. Из него имеем:

[H(x+αy)-H(x)]/α=2(Ax-b,y)+α(Ay,y)

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

H_y’(x)= 2(Ax-b,y)  {производная H(x) по направлению y }

От сюда вытекает, что градиент функционала H(x) равен 2(Ax-b).

Рассмотрим линейную алгебраическю сисстему

Ax=b                 (2)

С этой системой свяжем наш функционал (1).

ТЕОРЕМА 1Решение x* системы (2) доставляет наименьшее значение функционалу (1). Наоборот, вектор x, доставляющий наименьшее значение функционалу (1), совпадает с x*.

Дадим описание метода наискорейшего спуска для решения системы (2). Пусть x⁽⁰⁾– начальное приближение к решению системы (2). Градиент функционала H(x) в точке x⁽⁰⁾ имеет направление r⁽⁰⁾=A x⁽⁰⁾-b. В направлении - r⁽⁰⁾ функционал H(x) в точке x⁽⁰⁾ наиболее быстро убывает. От точки x⁽⁰⁾ будем двигаться в этом направлении по прямой x⁽⁰⁾ - αr⁽⁰⁾ до тех пор, пока на этой прямой H(x) не достигнет наименьшего значения.

По формуле сложения имеем:

H(x⁽⁰⁾+αr⁽⁰⁾)=H(x⁽⁰⁾)+ 2α(Ax⁽⁰⁾-b,r⁽⁰⁾)+ α²(Ar⁽⁰⁾,r⁽⁰⁾)

Функционал H(x) на рассматриваемой прямой как функция от α является квадратным трёхчленом, у которого коэфициент при α² равен (Ar⁽⁰⁾,r⁽⁰⁾) и, следовательно положителен. Действительно, матрица А положительно определённая, и мы считаем, что начальное приближение x⁽⁰⁾ не совпадает с решением системы (2). Значение α = α₀, при котором этот квадратный трёхчлен достигает минимума, совпадает с корнем его производной 

-2(r⁽⁰⁾,r⁽⁰⁾)+2α(Ar⁽⁰⁾,r⁽⁰⁾), и мы получаем

α₀=(r⁽⁰⁾,r⁽⁰⁾)/(Ar⁽⁰⁾,r⁽⁰⁾)

Точка x⁽¹⁾=x⁽⁰⁾-α₀r⁽⁰⁾ принимается за новое приближение к решению системы (2).

Аналогичным путём определяются дальнейшие приближения

x^(k)= x^(k)-α₀r^(k),  k=1,2…