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

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

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

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

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

||f '(x⁽¹⁾)|| = ||g⁽¹⁾)|| = = > e.

Переходим к шагу 10.

Шаг 10.

С = (Ap⁽⁰⁾, g⁽¹⁾) = = 8×(– ) + 16× = .

Шаг 11.

b⁽⁰⁾ = = = ×.

Шаг 12. Определяем новое направление

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

p⁽¹⁾ = (p , p ),

p = – g + b⁽⁰⁾p = + ×4 = ,

p = – g + b⁽⁰⁾p = – + ×4 = – .

Шаг 13. Перейдем к шагу 3 при m = 1. Начало новой итерации.

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

Шаг 3.

B = (g⁽¹⁾, p⁽¹⁾) = = – × + ×( – ) = – .

Шаг 4.

Ap⁽¹⁾ = (A , A ),

A = = 2× + 0×( – ) = ,

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

Шаг 5.

B = (Ap⁽¹⁾, p⁽¹⁾) = = × – ×( – ) = .

Шаг 6.

a⁽¹⁾ = – = .

Шаг 7.

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

x⁽²⁾ = (x , x ),

x = x + a⁽¹⁾p = + × = 2,

x = x + a⁽¹⁾p = + ×( – ) = 1.

Шаг 8.

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

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

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

g = = 0×2+ 4×1 – 4 = 0.

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

||f '(x⁽²⁾)|| = ||g⁽²⁾)|| = = 0 < e.

Вычисления прекращаем, так как требуемая точность достигнута.

Таким образом, полученное значение точки минимума x^* равно точному значению x^* = (2, 1)^T и f(x^*) » –6.000.

Решение найдено за два шага.

2.8. Метод покоординатного спуска

Пусть нужно найти минимум функции f(x₁, x₂, … ,x_n). Основная идея метода покоординатного спуска состоит в последовательной минимизации функции f(x₁, x₂, … ,x_n) сначала в направлении координатной оси x₁, затем в направлении координатной оси x₂ и т. д. После окончания минимизации в направлении координатной оси x_n цикл повторяется. Метод покоординатного спуска не требует вычисления производных функции f(x₁, x₂, … ,x_n), поэтому целесообразно использовать критерии окончания вычислений в виде (2.21) или (2.22).

Опишем сначала алгоритм метода покоординатного спуска в общем виде.

Алгоритм 2.4 (Алгоритм метода покоординатного спуска).

Шаг 1. Выбрать произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T, например, x⁽⁰⁾ = (0, 0, … , 0)^T и погрешность вычислений e > 0. Вычислить f (x⁽⁰⁾ ).

Шаг 2. Положить j =1.

Шаг 3. Рассмотреть функцию f(x₁, x₂, … ,x_n) как функцию одной переменной x_j, а все остальные переменные зафиксировать. Найти x , решив задачу одномерной минимизации, т.е. найти f(x₁, x₂, … ,x_n).

Шаг 4. Если j < n, то положить j = j + 1 и перейти к шагу 3. В противном случае перейти к шагу 5.

Шаг 5. Найдено очередное приближение x⁽¹⁾ = (x , x , …, x ). Проверить критерий окончания вычислений || x⁽¹⁾ – x⁽⁰⁾|| < e или |f(x⁽¹⁾) – f(x⁽⁰⁾)| < e. Если критерий окончания вычислений выполнен, то положить x^* = x, f^* = f(x^*) и закончить вычисления. В противном случае положить x⁽⁰⁾ = x⁽¹⁾ , f^*(x⁽⁰⁾) = f(x⁽¹⁾) и перейти к шагу 2.

На рис. 2.4 изображена геометрическая иллюстрация циклического покоординатного спуска.

Рис. 2.4

Применим метод покоординатного спуска для квадратичной функции f(x) = (Ax, x) + (b, x) + c с симметричной положительно определенной матрицей A.

Выберем произвольную начальную точку x⁽⁰⁾ = (x , x , … , x )^T. Рассмотрим функцию f(x₁, x , … , x ) как функцию одной переменной x₁, а все остальные переменные зафиксируем. Найдем значение x₁ = x , при котором достигается f(x₁, x , … , x ).

При этом необходимо, чтобы

= 0.

Это условие можно записать в следующем виде:

a₁₁x₁ + + b₁ = 0,

x = – ( + b₁).

Затем рассмотрим функцию f(x , x₂, x … , x ) как функцию одной переменной x₂, а все остальные переменные зафиксируем. Найдем значение x , при котором достигается f(x , x₂, x … , x ). Пусть на очередном j-ом шаге функция f(x₁, x₂, … ,x_n) рассматривается как функция одной переменной x_j, а все остальные переменные зафиксированы. Значение x_j, определяется из условия f(x , x , … , x , x_j, x , …, x ). При этом необходимо, чтобы

= 0.

Это условие можно записать в следующем виде:

+ b_j = 0.

Отсюда

x = – ( + b_j). (2.27)

В результате n шагов будет получено первое приближение x⁽¹⁾ = (x , x , …, x ). Затем итерационный процесс может быть продолжен. Опишем алгоритм этого процесса.

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

Шаг 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⁽⁰⁾ = (x , x , … , x )^T и погрешность вычислений e > 0. Вычислить f(x⁽⁰⁾).

Шаг 2. В цикле по m = 0, …

В цикле по j =1, … , n вычислить

x = – ( + b_j).

Если верхний предел суммирования окажется меньше нижнего, то положить S = 0. Положить x⁽¹⁾ = x = (x , x , … , x )^T.

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

||x⁽¹⁾ – x⁽⁰⁾|| = < e ,

или

|f(x⁽¹⁾) – f(x⁽⁰⁾)| < e.

Если критерий окончания вычислений выполнен, то положить x^* = x⁽¹⁾, f^*_min = f(x^*) и закончить вычисления. В противном случае положить x⁽⁰⁾ = x⁽¹⁾, f(x⁽⁰⁾) = f(x⁽¹⁾) и перейти к шагу 2.

Пример 2.6.

Как и в предыдущих примерах, найдем минимум функции f(x) = x + 2x – 4x₁ – 4x₂ с точностью e = 0.1.

2 0

A = 0 4 ,

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

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

Применим метод покоординатного спуска.

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

Шаг 2. Полагаем m = 0.

При j = 1 вычисляем x по формуле (2.27):

x = – ( + + b₁).

Первая сумма равна нулю (верхний предел суммирования меньше нижнего), поэтому

x = – (a₁₂x + b₁) = – (0×0 – 4) = 2;

При j = 2 вычисляем x по формуле (2.27):

x = – ( + + b₂).

Вторая сумма равна нулю (верхний предел суммирования меньше нижнего), поэтому

x = – (a₂₁x + b₂) = – (0×2 – 4) = 1;

Итак, x⁽¹⁾ = (2, 1)^T, т.е. найденное приближение совпадает с точным решением. Очевидно, f(x⁽¹⁾) = –6.000.

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

2.9. Метод Ньютона

Метод Ньютона использует информацию о производных первого и второго порядка. Поэтому он относится к градиентным методам второго порядка.

Метод Ньютона для функции многих переменных является обобщением метода Ньютона для одномерного случая (разд. 1.8)

Пусть дана дважды непрерывно дифференцируемая функция n переменных f(x) = f(x₁, x₂, … ,x_n) и начальная точка x⁽⁰⁾ = (x , x , … , x )^T.

Разложим функцию f(x) в ряд Тейлора в точке x⁽⁰⁾ как функцию многих переменных и ограничимся тремя членами:

f(x)=f(x⁽⁰⁾) + (2.28)

Пусть x^(m) приближенное значение точки минимума, полученное на m-ом шаге итерационного процесса. Разложение (2.28) будет иметь место и для точки x^(m), а именно

f(x)=f(x^(m))+ (2.29)

или в векторной форме

f(x) » f(x^(m)) + (g(x^(m)), (x – x^(m)) + (G(x^(m))(x – x^(m)), (x – x^(m))), (2.30)

где G(x^(m)) – матрица Гессе (матрица вторых производных) функции f(x) в точке x^(m).

Из соотношения (2.29) видно, что в окрестности точки x^(m) поведение функции f(x) может быть приближенно описано квадратичной функцией с точностью до величины порядка o(||x – x^(m)||)²

Необходимое условие минимума – равенство нулю в точке минимума первой производной функции f(x), т. е.

f ^'(x) » g(x^(m)) + G(x^(m))(x – x^(m)) = 0. (2.31)

Умножим (2.31) на G^–1(x^(m)):

G^–1(x^(m))g(x^(m)) + (x – x^(m)) = 0.

Следовательно,

x = x^(m) – G^–1(x^(m))g(x^(m)).

Пусть точка минимума x^* » x^(m+1). Тогда

x^(m+1) = x^(m) – G^–1(x^(m))g(x^(m)). (2.32)

Формула (2.32) является расчетной формулой метода Ньютона.

Для квадратичной функции матрица Гессе есть матрица квадратичной формы, равенство (2.31) является точным, и решение (точка минимума) находится за одну итерацию. В общем случае метод Ньютона обеспечивает , как правило, быструю сходимость. Недостатком метода Ньютона является необходимость на каждой итерации вычисления матрицы Гессе и обратной к ней матрицы. Кроме того, если начальная точка выбрана недостаточно близко к точке минимума x^*, то последовательность x⁽⁰⁾, x⁽¹⁾, …, x^(m), … может расходиться. Для избежания подобной ситуации используется обобщенный метод Ньютона, со следующей расчетной формулой:

x^(m+1) = x^(m) – a^(m)G^–1(x^(m))g(x^(m)). (2.33)

Формула (2.33) есть расчетная формула метода спуска (см. формулу (2.18)) с направлением в точке x^(m), определяемым вектором p^(m) = G^–1(x^(m))g(x^(m)), и с шагом a^(m).

Величина шага a^(m) может быть выбрана из условия одномерной минимизации функции j^(m)(a) = f(x^(m) – a^(m)G^–1(x^(m))g(x^(m)).

Формулу (2.32) также можно рассматривать как формулу спуска с шагом a^(m)= 1.

Опишем теперь алгоритм метода Ньютона.

Алгоритм 2.6 (Алгоритм метода Ньютона).

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

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