01_Методічка_безусловний екстремум
Нагадаємо, що n - розмірність простору незалежних змінних. Варіант Б) відрізняється від варіанту А) тим, що містить так звану процедуру поновлення - для кожного k, кратного n. перехід з точки x k в точку x k +1 виконується як в методі найшвидшого спуску. Зауважимо, що перехід з точки x 0 в точку x 1 виконується як в методі найшвидшого спуску і в разі А) і в разі Б).
4. Відповідність. Збіжність будь-якого методу залежить від властивостей f (x), вибору початкової точки x 0 і параметрів ітераційного процесу. Корисна наступна теорема.
Теорема 1. ([1], с.47,83; [4], с.265). Нехай функція f (x) обмежена знизу, а її градієнт задовольняє умові Ліпшиця. Якщо побудова мінімізує послідовності виробляється способом п.1, або п.2 Б), або п.3 Б), то якою б не була початкова точка x 0,
Якщо точка x 0 така, що безліч K (x 0) = обмежена, то послідовність сходиться до безлічі S = стаціонарних точок функції f (x), тобто
inf x - x k → 0. k → ∞.
Зауважимо, що клас функцій, зазначений в теоремі 1, досить широкий, і серед стаціонарних точок таких функцій можуть бути не тільки точки глобальних екстремумів, а й точки локальних екстремумів, а також сідлові точки. Однак, як зазначено в [5], градієнтні методи, наприклад, "майже ніколи" не сходяться до точки максимуму або седловой точці. У той же час вони не розрізняють точок локального і глобального мінімуму і сходяться до довільної з них (точніше см. [5], с.168).
Оцінку швидкості збіжності послідовності для кожного з методів п.п.1 - 3 можна дати лише на досить вузьких класах функцій, пред'являючи досить жорсткі вимоги до гладкості і опуклості функцій f (x). Розглянемо, наприклад, клас двічі безперервно диференційовних сильно опуклих функцій. Двічі безперервно диференціюється функція f (x) називається сильно опуклою в R n. якщо існує постійна l. l> 0, така, що для всіх x R n маємо
l y 2 ≤ (2 f (x) y, y). y R n,
де 2 f (x) матриця Гессе (гессіан) функції f (x),
Якщо побудова послідовності виробляється способом п.2 Б) або п.1, то при будь-якої початкової точки x 0 послідовність сходиться до точки мінімуму x ¯ з лінійною швидкістю. У разі способу п.1 постійна q = (L - l) / (L + l).
Якщо поверхні рівня функції, що мінімізується мають складну сильно витягнуту (овражную) структуру, то напрямок антіградіента сильно відрізняється від напрямку на точку мінімуму
і збіжність градієнтних методів сповільнюється. Це явище називається яружний ефектом. Показником яружно в околиці точки мінімуму x ¯ функції f (x) є відношення найбільшого власного числа матриці Гессе 2 f (¯ x) до найменшого (див. [5], с.28). Чим більше цей показник, тим більше витягнутим і крутим є "яр" поверхні рівня f (x) в околиці x ¯
і тим повільніше сходяться в цій околиці градієнтні методи (див. [5], с.150).
Метод сполучених градієнтів - найкращий за швидкістю з розглянутих методів першого порядку (див. [5], гл.3. § 2). Для методу сполучених градієнтів в разі числа ітерацій, істотно більшому розмірності n. справедливий наступний результат (див. [5], с.74).
Теорема 3. Нехай функція f (x) тричі дифференцируемая сильно опукла функція. Тоді послідовність. побудована за способом п.3 Б), сходиться до точки мінімуму x ¯ функції f (x), причому в деякому околі точки x ¯ має місце оцінка швидкості збіжності
x (k +1) n - x ¯ ≤ C x kn - x ¯ 2. k = 1. 2.
Для квадратичних функцій f (x) = 1 2 (Ax, x) - (b, x) (A - позитивно певна симетрична матриця) метод сполучених градієнтів сходиться за кінцеве число кроків, що не перевищує числа n. При цьому послідовні напрямки p k задовольняють співвідношенню (Ap i. P j) = 0, i = ̸ j. тобто є ортогональними в метриці, що задається матрицею A, A - ортогональними (A - сполученими). Звідси - назва методу (див. [1], гл.2. § 3).
Про роль теорем збіжності для практичних обчислень см. Наприклад, [5], c.39-43.
5. Критерії закінчення ітераційних процесів. теорема
1 дозволяє для закінчення ітераційного процесу користуватися умовою виду
Вибір величини δ визначається заданою точністю δ
Однак, правильний вибір δ по заданій величині δ багато в чому залежить від мистецтва обчислювача. "На жаль, надійних критеріїв закінчення рахунку, які гарантували б отримання рішення задачі (1) з необхідною точністю, і застосовних до широкого класу задач, поки немає" ([4], c.264). Це зауваження стосується й інших методів, описаних нижче.
§2. Методи другого порядку.
Серед методів другого порядку основними є методи, пов'язані з ідеєю локальної апроксимації заданої функції квадратичною функцією.
1.Метод Ньютона. Для отримання итерационной формули цього методу використовуємо такі евристичні міркування (див. [5], с.36). Запишемо для функції f (x) в околі точки x k формулу Тейлора 2-го порядку
f (x) = Q k (x) + o (x - x k 2). x - x k → 0;
Q k (x) = f (x k) + (f (x k). (X-x k)) + 1 2 (2 f (x k) (x-x k). (X-x k)). (10)
У разі, коли гессіан 2 f (x k) позитивно визначено, квадратична функція Q k (x) досягає глобального мінімуму в точці
x k +1 = x k - [2 f (x k)] - 1 f (x k),
(Q k (x k +1) = 0). Якщо точка x k +1 досить близька до x k. то в силу (10) справедливо нерівність
f (x k +1) тобто x k +1 природно взяти наступним за x k наближенням до вирішення завдання (1). Формула (11) і є итерационная формула методу Ньютона. Таким чином, в цьому методі α k = 1, p k = - [2 f (x k)] - 1 f (x k). Практично p k зручніше шукати не за формулою (12), а вирішуючи систему лінійних рівнянь [2 f (x k)] p k = -f (x k) одним з прямих або ітераційних методів (див. відповідні лабораторні роботи), виключаючи тим самим операцію звернення матриці Гессе. Відзначимо, що для квадратичної функції f (x) метод Ньютона сходиться за один крок. Для досить гладкої функції f (x) з позитивно певної матрицею Гессе при вдалому виборі початкового наближення x 0 итерационная послідовність методу Ньютона сходиться до точки мінімуму з квадратичною швидкістю. Однак, знайти вдале початкове наближення - завдання досить складна, що вимагає певного мистецтва. Модифікуючи метод Ньютона введенням змінного множника α k. отримують методи спуску, що сходяться при будь-якому початковому наближенні x 0. 2. Метод Ньютона-Рафсона. У цьому методі напрямок спуску визначається формулою (12), а множник α k. регулює довжину кроку, можна вибирати, одним із таких способів: А) як і в методі найшвидшого спуску з умови мінімуму f (x k + α k p k) = min f (x k + αp k) (Див. Зауваження в п.1 §1); Б) так, щоб виконувалася нерівність f (x k + α k p k) ≤ f (x k) + εα k (f (x k). p k), де ε (0,1 / 2) -наперед задана постійна, одна і та ж для всіх ітерацій. Алгоритм знаходження множника α k тут такий же, як і в градієнтному методі з дробленням кроку. Початкове значення Теорема 4. (див. [2], гл.2. § 2, п.2). Нехай функція f (x) двічі неперервно диференційовна і виконується (6), а другі похідні f задовольняють умові Ліпшиця. тоді итерационнаяСхожі статті