Методичка по курсовым и лабораторным работам (1085639), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Опишем алгоритм метода наискорейшего спуска для квадратичной функции.

Алгоритм 2.2 (Алгоритм метода наискорейшего спуска для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + + с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c, i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например, x = (0, 0, … , 0)^T и погрешность вычислений e > 0.

Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно

g = (g₁, g₂, … , g_n)^T,

g_i = + b_i, i = 1, …, n.

Шаг 3. Для заданной точности вычислений e проверить выполнение критерия окончания вычислений.: ||f '(x)|| < e, Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x^* = x = (x₁, x₂, … , x_n)^T, f^* = f(x^*).

В противном случае перейти к шагу 4 для продолжения итерационного процесса.

Шаг 4. (Шаги 4 – 7 используются для вычисления величины шага a^(m) по формуле (2.26)

Вычислить

B₁= (g, g) = .

Шаг 5. Вычислить

Ag = (A₁, A₂, … , A_n)^T, где

A_i = , i = 1, …, n.

Шаг 6. Вычислить

B₂ = (Ag, g) = .

Шаг 7. Вычислить

a = .

Шаг 8. Положить

x = x – ag(x) или покоординатно x_i = x_i – ag_i, i = 1, …, n. Перейти к шагу 2.

Пример 2.4.

Как и в примере 2.3, найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.01. В примере 2.3. было установлено, что функция f(x) имеет минимум. Найдем этот минимум методом наискорейшего спуска.

Шаги 1 – 3 совпадают с шагами 1 – 3 примера 2.3.

Шаг 1. Полагаем x = (0, 0)^T и погрешность вычислений e =0.01. Вычисляем f(x) = 0.

Шаг 2. Вычисляем g = f '(x) = Ax + b, или покоординатно

g = (g₁, g₂)^T,

g₁ = + b₁ = 2×0 + 0×0 – 4 = –4,

g₂ = + b₂ = 0×0 + 4×0 – 4 = –4.

Шаг 3. Проверяем выполнение критерия окончания вычислений.

||f '(x)|| = = > e. Переходим к шагу 4.

Шаг 4. Вычисляем

B₁= (g, g) = = 32.

Шаг 5. Вычисляем

Ag = (A₁, A₂)^T, где

A₁ = = 2×(–4) + 0×(–4) = –8,

A₂ = = 0×(–4) + 4×(–4) = –16.

Шаг 6. Вычисляем

B₂ = (Ag, g) = = (–8)×(–4) + (–16)×(–4) = 96.

Шаг 7. Вычисляем

a = = = .

Шаг 8. Полагаем

x₁ = x₁– a g₁ = 0 – ×(–4) = ,

x₂ = x₂ – a g₂ = 0 – ×(–4) = .

Перейдем к шагу 2 для следующей итерации.

Результаты последующих итераций приведены в табл. 2.2.

Таблица 2.2

N	a	x1	x2	g1	g2	f(x)
1 2 3 4 5 6 7	0.333 0.333 0.333 0.333 0.333 0.333 0.333	0 1.333 1.778 1.926 1.975 1.982 1.997	0 1.333 0.889 1.037 0.988 1.004 0.999	-4 -1.333 -0.444 -0.148 -0.049 -0.016 -0.005	-4 1.333 -0.444 0.148 -0.049 0.016 -0.005	0 -5.333 -5.926 -5.992 -5.999 -6.000 -6.000

Вычисления прекращаются после 7-ой итерации, так как требуемая точность достигнута (||f '(x)|| = » 0.002 < 0.01).

Таким образом, x^* » (1.997, 0.999)^T и f(x^*) » –6.000.

Можно показать, что на m-ой итерации, m > 1, будут получены значения:

g^(m) = (1, (–1)^m)^T, a^(m) = , x^(m) = x^* – (2, (–1)^m)^T.

Существует точное значение точки минимума: x^* = (2, 1)^T.

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

До сих пор в итерационной процедуре градиентного спуска

x^(m+1) = x^(m) + a^(m)p^(m)

мы предполагали, что движение к минимуму функции производится в направлении антиградиента, p^(m) = –g^(m). Для некоторых функций направление антиградиента в точке x^(m) может значительно отличаться от направления к точке минимума x^*. В результате траектория приближения к точке минимума может иметь зигзагообразный характер. Метод сопряженных градиентов в существенной степени избавлен от этого недостатка. Этот метод основан на понятии сопряженных направлений. Будем рассматривать задачу минимизации квадратичной функции

f(x) = (Ax, x) + (b, x) + c

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

Направления p⁽⁰⁾, p⁽¹⁾, … , p^{(m –1)} называются взаимно сопряженными относительно матрицы A, если (Ap^(k), p^(l)) = 0 для всех k ¹ l.

В основе метода сопряженных градиентов лежит итерационный процесс:

x^(m+1) = x^(m) + a^(m)p^(m), m = 0, 1, …; p⁽⁰⁾ = –g⁽⁰⁾ = –f ^'(x⁽⁰⁾) .

Величина шага a^(m) так же, как и в методе наискорейшего спуска, выбирается из условия одномерной минимизации функции j^(m)(a) = f(x^(m) + a^(m)p^(m)),

Направления p^(m) находят по следующему правилу:

p⁽⁰⁾ = –g⁽⁰⁾ = –f ^'(x⁽⁰⁾),

p^(m+1) = –g^(m+1) + b^(m) p^(m), n ³ 1,

b^(m) = ,

g^(m) = Ax^(m) + b,

где

p^(m) = p(x^(m)) – вектор сопряженных направлений;

g^(m) = g(x^(m)) – вектор направлений градиента;

x^(m) = (x , x , … , x ) – m-ое приближение.

Алгоритм 2.3 (Алгоритм метода сопряженных градиентов для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c, i = 1, … , n; j = 1, … , n, Выбрать произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T, например, x⁽⁰⁾ = (0, 0, … , 0)^T и погрешность вычислений e > 0.

Шаг 2. Вычислить

p⁽⁰⁾ = – g⁽⁰⁾ = –(Ax⁽⁰⁾ + b),

Покоординатно:

p⁽⁰⁾ = (p , p , … , p )^T,

p = – g = – , i = 1, …, n.

Далее вычисления производятся в цикле по m = 0, 1, … до тех пор, пока не будет выполнен критерий окончания вычислений.

Шаги 3 – 6 реализуют вычисление величины шага a^(m)

Шаг 3. Вычислить

B = (g^(m), p^(m)) = .

Шаг 4. Вычислить

Ap^(m) = (A , A , … , A )^T, где

A = , i = 1, …, n.

Шаг 5. Вычислить

B = (Ap^(m), p^(m)) = .

Шаг 6. Вычислить

a^(m) = – .

Шаг 7. Вычислить

x^(m+1) = x^(m) +a^(m)p^(m), или покоординатно

x^(m+1) = (x , x , … , x )^T,

x = x + a^(m)p , i = 1, …, n.

Шаг 8. Вычислить

g^(m+1) = Ax^(m+1) + b, или покоординатно

g^(m+1) = (g , g , … , g ),

g = , i = 1, …, n.

Шаг 9. Для заданной точности вычислений e проверить выполнение критерия окончания вычислений.: ||f '(x^(m+1))|| = ||g^(m+1))|| < e, Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x^* = x^(m+1) = (x , x , … , x )^T, f^* = f(x^*). В противном случае перейти к шагу 10 для продолжения итерационного процесса.

Шаги 10 – 12 реализуют вычисление нового вектора сопряженного градиента p^(m+1).

Шаг 10. Вычислить

С = (Ap^(m), g^(m+1)) = .

Шаг 11. Вычислить

b^(m) = .

Шаг 12. Вычислить

p^(m+1) = – g^(m+1) + b^(m) p^(m), или покоординатно

p^(m+1) = (p , p , … , p ),

p = – g + b^(m)p , i = 1, …, n.

Шаг 13. Перейти к шагу 3 при m = m+1.

Пример 2.5.

Найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.1.

Как было показано ранее, эта функция имеет минимум в точке x^* = (2, 1)^T.

Матрица этой квадратичной функции имеет вид:

2 0

A= 0 4 , b = (– 4, – 4)^T.

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

Шаг 1. Возьмем начальное приближение x⁽⁰⁾ =(x , x )^T = (0, 0)^T, положим e = 0.01.

Шаг 2. Вычисляем

g⁽⁰⁾ = (g , g )^T,

g = = 2×0 + 0×0 – 4 = –4,

g = = 0×0 + 4×0 – 4 = –4,

g⁽⁰⁾ = (–4, –4) ^T,

p⁽⁰⁾ = (p , p )^T = (4, 4) ^T,

1-ая итерация, m = 0.

Шаг 3.

B = (g⁽⁰⁾, p⁽⁰⁾) = – (g⁽⁰⁾, g⁽⁰⁾) = – = –(16 + 16) = –32.

Шаг 4.

Ap⁽⁰⁾ = (A , A ),

A = = 2×4 + 0×4 = 8,

A = = 0×4 + 4×4 = 16.

Шаг 5.

B = (Ap⁽⁰⁾, p⁽⁰⁾) = = 8×4 + 16×4 = 96.

Шаг 6.

a⁽⁰⁾ = – = – = .

Шаг 7.

x⁽¹⁾ = x⁽⁰⁾ +a⁽⁰⁾ p⁽⁰⁾,

x⁽¹⁾ = (x , x ),

x = x + a⁽⁰⁾ p = 0 + ×4 = ,

x = x + a⁽⁰⁾ p = 0 + ×4 = .

Шаг 8.

g⁽¹⁾ = Ax⁽¹⁾ + b, или покоординатно

g⁽¹⁾ = (g , g )^T,

g = = 2× + 0× – 4 = – ,

Характеристики

Список файлов книги