Лекція 19. Метод Ньютона: локальна квадратична модель

Коротко про лекцію

Ви побачите, як метод Ньютона використовує градієнт і Гессіан для побудови локальної квадратичної моделі. Лекція пояснює Newton-крок, швидку локальну збіжність і ситуації, коли кривизна робить крок небезпечним.

Практичний сенс. Градієнтний спуск використовує інформацію першого порядку й окремо підбирає довжину кроку. Метод Ньютона враховує локальну кривизну через матрицю Гессе. Це дозволяє масштабувати рух за різними напрямами й дуже швидко розв’язувати добре поводжені задачі поблизу мінімізатора.

Постановка та базові поняття

1. Навіщо враховувати кривизну

На вузькій квадратичній долині градієнтний метод може зигзагувати.

Причина — однаковий довжина кроку працює з напрямами різної кривизни.

Матриця Гессе описує цю різницю.

Метод Ньютона використовує матрицю Гессе, щоб побудувати локальну квадратичну модель та знайти її мінімум.

1.1. Чому метод Ньютона використовує квадратичну модель

Метод Ньютона названий на честь Ісаака Ньютона. Його ідея в оптимізації полягає в тому, щоб біля поточної точки замінити складну гладку функцію простішою локальною квадратичною моделлю.

Градієнт задає нахил цієї моделі, а матриця Гессе — її кривизну. Замість малого кроку вздовж антиградієнта метод одразу шукає мінімум локальної квадратичної апроксимації. Для цього розв’язується система \(Hs=-g\).

Якщо модель точна, як для справжньої квадратичної функції, один крок може одразу привести до мінімізатора. Для загальної нелінійної функції модель точна лише поблизу поточної точки, тому іноді крок зменшують. Таке зменшення називають демпфуванням кроку.

2. Одновимірне нагадування

Локальна модель походить із розклад Тейлора другого порядку.

Біля \(x_k\):

\[ f(x_k+s)\approx f(x_k)+ f'(x_k)s+ \frac{1}{2}f''(x_k)s^2 \]

Перший доданок — поточне значення.

Другий — лінійний прогноз за похідною.

Третій — корекція кривизни.

Градієнтний спуск використовує переважно напрям першого порядку.

метод Ньютона використовує і першу, і другу похідну.

Тому його крок може краще відповідати локальній геометрії.

Для функції однієї змінної локальна квадратична модель біля \(x_k\):

\[ m_k(s)= f(x_k)+ f'(x_k)s+ \frac{1}{2}f''(x_k)s^2 \]

Тут \(s\) — крок від поточної точки.

Мінімізуємо модель за \(s\).

Похідна моделі:

\[ m_k'(s)= f'(x_k)+f''(x_k)s \]

Стаціонарність:

\[ f'(x_k)+f''(x_k)s=0 \]

Тому крок Ньютона:

\[ s_k= -\frac{f'(x_k)}{f''(x_k)} \]

3. Багатовимірна квадратична модель

У векторному випадку член:

\[ \frac{1}{2}s^THs \]

є аналогом \(\frac{1}{2}f''(x)s^2\).

Скалярний добуток:

\[ \nabla f(x_k)^Ts \]

є багатовимірним лінійним прогнозом.

Тому модель має ту саму структуру, що й одновимірне наближення Тейлора.

Мінімізуючи модель за \(s\), ми шукаємо крок, який балансує градієнт і кривизну.

Це причинне пояснення рівняння Ньютона.

Для вектора \(x\):

\[ m_k(s)= f(x_k)+ \nabla f(x_k)^Ts+ \frac{1}{2}s^TH(x_k)s \]

Градієнт моделі за \(s\):

\[ \nabla m_k(s)= \nabla f(x_k)+H(x_k)s \]

Умова стаціонарності моделі:

\[ H(x_k)s_k= -\nabla f(x_k) \]

Це центральне рівняння методу Ньютона.

4. Чому краще розв’язувати систему

Явна обернений матриця створює зайву операцію.

У чисельній лінійній алгебрі розв’язання системи може використати розклад матриці без формування повного оберненого оператора.

Це зазвичай стабільніше й ефективніше.

Тому математична формула через \(H^{-1}\) корисна для теорії.

У коді основний запис:

# Розв’язуємо лінійну систему напряму, без явного обчислення оберненої матриці.
newton_step = np.linalg.solve(
    current_hessian,
    -current_gradient,
)

безпосередньо відповідає системі \(Hs=-g\).

Формально можна написати:

\[ s_k= -H(x_k)^{-1}\nabla f(x_k) \]

У програмі явне обернення матриці зазвичай не потрібне.

Краще розв’язати лінійну систему:

\[ H(x_k)s_k= -\nabla f(x_k) \]

через np.linalg.solve.

Це чисельно природніше та ясніше.

5. Наскрізна функція

Використаємо:

\[ f(x,y)=(x-2)^2+2(y+1)^2 \]

Градієнт:

\[ \nabla f(x,y)= \begin{pmatrix} 2(x-2)\\ 4(y+1) \end{pmatrix} \]

матриця Гессе:

\[ H= \begin{pmatrix} 2 & 0\\ 0 & 4 \end{pmatrix} \]

Точний мінімізатор:

\[ x^*= \begin{pmatrix} 2\\ -1 \end{pmatrix} \]

Математична логіка

6. Крок Ньютона зі стартової точки

Візьмемо:

\[ x_0= \begin{pmatrix} 10\\ 10 \end{pmatrix} \]

Градієнт:

\[ g_0= \begin{pmatrix} 16\\ 44 \end{pmatrix} \]

Розв’язуємо:

\[ \begin{aligned} \begin{pmatrix} 2 & 0\\ 0 & 4 \end{pmatrix} s_0 &= -\begin{pmatrix} 16\\ 44 \end{pmatrix} \end{aligned} \]

З першого рівняння:

\[ 2s_1=-16 \]

тому \(s_1=-8\).

З другого:

\[ 4s_2=-44 \]

тому \(s_2=-11\).

Отже:

\[ s_0= \begin{pmatrix} -8\\ -11 \end{pmatrix} \]

7. Нова точка

Оновлення:

\[ x_1=x_0+s_0 \]

Тому:

\[ \begin{aligned} x_1 &= \begin{pmatrix} 10\\ 10 \end{pmatrix} +\begin{pmatrix} -8\\ -11 \end{pmatrix} \end{aligned} \]

Отримуємо:

\[ x_1= \begin{pmatrix} 2\\ -1 \end{pmatrix} \]

метод Ньютона досяг точного мінімізатор за один крок.

крок Ньютона для квадратичної функції

8. Чому один крок був достатнім

Якби функція мала додатковий кубічний або четвертий член, матриця Гессе змінювалася б із точкою.

Тоді модель у \(x_0\) лише наближала б справжню функцію.

Після першого кроку потрібно було б обчислити новий градієнт і нову матрицю Гессе.

Тому метод Ньютона також є ітераційний метод.

Один крок у нашому прикладі — спеціальна властивість точної квадратичної структури.

Вона корисна як еталон для перевірки реалізації.

Наша функція сама є квадратичною.

Тому локальна квадратична модель збігається з функцією глобально.

метод Ньютона мінімізує цю модель точно.

Для загальної нелінійної функції модель є лише локальним наближенням.

Тому зазвичай потрібно кілька ітерацій.

9. Геометрія масштабування

Градієнтний спуск рухався за:

\[ -\nabla f= \begin{pmatrix} -16\\ -44 \end{pmatrix} \]

крок Ньютона дорівнює:

\[ \begin{pmatrix} -8\\ -11 \end{pmatrix} \]

матриця Гессе зменшила компоненту за крутішим напрямом \(y\) сильніше.

Саме це компенсує різну кривизну.

крок Ньютона можна читати як градієнтний крок, скоригований за кривизною.

10. Локальна квадратична модель на графіку

Якість моделі залежить від відстані до точки розкладу.

Поблизу \(x_k\) наближення Тейлора зазвичай точніша.

Далеко від \(x_k\) члени третього і вищих порядків можуть домінувати.

Тому повний крок Ньютона може бути небезпечним далеко від мінімізатор.

Демпфування або область довіри обмежують вплив локальної моделі.

Такі механізми перетворюють швидкий локальний метод на надійніший глобалізований алгоритм.

Для одновимірної гладкої функції квадратична модель торкається функції в поточній точці за значенням, першою та другою похідними.

Локальна квадратична модель

На справжній квадратичній функції модель збігається з нею.

На нелінійній функції збіг локальний.

Чим далі від точки розкладу, тим сильніше можуть відрізнятися функція та модель.

11. Розмір ньютонівського кроку

Практично можна дивитися на норма кроку:

\[ \|s_k\|_2 \]

Якщо вона дуже велика відносно масштабу змінних, локальна модель пропонує агресивний рух.

Це сигнал для демпфування.

Малий крок Ньютона поблизу мінімізатор часто означає, що локальна модель уже близька до стаціонарності.

Проте, як і в градієнтний спуск, один критерій за крок норма не повинен бути єдиним.

Норма градієнта залишається важливою умовою.

Величина крок Ньютона показує, наскільки далеко локальна модель розміщує свій мінімум.

Якщо крок великий, модель може бути ненадійною.

Тому практичні метод Ньютонаs часто поєднують крок із демпфування або пошук довжини кроку.

Тоді:

\[ x_{k+1}=x_k+\alpha_ks_k \]

де:

\[ 0<\alpha_k\le1 \]

Повний крок Ньютона відповідає \(\alpha_k=1\).

12. Коли матриця Гессе додатно визначена

Доведення напрямку спадання можна прочитати через квадратична форма.

Оскільки \(H^{-1}\) також додатно визначена, для ненульового \(g\):

\[ g^TH^{-1}g>0 \]

напрям Ньютона:

\[ s=-H^{-1}g \]

тому:

\[ g^Ts=-g^TH^{-1}g<0 \]

Отже, це напрям спадання.

Цей факт дозволяє застосовувати Арміхо пошук довжини кроку так само, як для градієнтний спуск.

Якщо матриця Гессе додатно визначена, квадратична модель має локальну чашу.

Тоді напрям Ньютона є напрямом спадання.

Справді:

\[ g^Ts= -g^TH^{-1}g \]

Для додатно визначеного \(H\) цей вираз від’ємний за ненульового \(g\).

Отже, пошук довжини кроку може шукати крок уздовж напрям Ньютона.

13. Проблема невизначеної матриці Гессе

У сідловій області крок Ньютона може навіть рухатися в напрямі збільшення функції.

Це не програмна помилка.

Локальна квадратична модель сама має напрям негативної кривизни.

Практичні алгоритми можуть додавати до матриці Гессе регуляризуючий член:

\[ H+\mu I \]

із \(\mu>0\).

Якщо \(\mu\) достатньо велике, матриця стає додатно визначеною.

Такий модифікований крок Ньютона використовує стабілізовану кривизну.

На неопуклій функції матриця Гессе може бути невизначеною.

Тоді локальна квадратична модель має сідлову форму.

напрям Ньютона може не бути напрямом спадання.

У такій ситуації потрібна модифікація матриці Гессе, метод області довіри або інший алгоритм.

Тому метод Ньютона потребує більше контролю, ніж простий градієнтний спуск.

14. Проблема виродженої матриці Гессе

Перед solve можна оцінити власні значення або число обумовленості.

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

Тоді малий шум у градієнт може сильно змінити крок.

Це чисельна причина для демпфування або регуляризація.

Якщо матриця Гессе точно вироджена, потрібен інший механізм.

Важливо повернути зрозумілий статус замість мовчазного випадкового результату.

Якщо матриця Гессе сингулярна, система:

\[ Hs=-g \]

може не мати єдиного розв’язку.

np.linalg.solve тоді поверне помилку.

Причиною може бути плаский напрям або надлишкова параметризація.

Практичний код повинен виявляти таку ситуацію.

Не варто приховувати її широким try/except.

Алгоритм і покроковий розбір

15. Базовий алгоритм Ньютона

На кожній ітерації бажано зберігати:

objective
gradient_norm
step_norm
system_residual
min_eigenvalue

Ці величини пояснюють якість крок Ньютона.

Наприклад, малий нев’язка системи підтверджує коректне розв’язання лінійної системи.

Додатне найменше власне значення підтримує тлумачення напряму спадання.

Зменшення цільова функція перевіряє фактичний результат кроку.

Такий журнал значно полегшує налагодження.

вибрати стартову точку;
обчислити цільова функція;
обчислити градієнт;
перевірити норма градієнта;
обчислити матрицю Гессе;
перевірити його чисельні властивості;
розв’язати \(Hs=-g\);
за потреби знайти демпфування \(\alpha\);
оновити точку;
повторити до критерію зупинки.

Основна нова операція — розв’язання лінійної системи.

16. Один крок як повна ручна перевірка

Для старту \((10,10)\) ми вже отримали:

\[ s= \begin{pmatrix} -8\\ -11 \end{pmatrix} \]

Перевіримо систему:

\[ Hs= \begin{pmatrix} -16\\ -44 \end{pmatrix} \]

Це точно дорівнює:

\[ -g \]

Після оновлення градієнт у новій точці дорівнює нулю.

Отже, нев’язка система Ньютона і нев’язка градієнта одночасно дорівнюють нулю.

17. Нев’язка лінійної системи

У чисельному випадку корисно обчислити:

\[ r_N= \|Hs+g\|_2 \]

Якщо np.linalg.solve працює коректно, нев’язка має бути малим.

Це незалежна перевірка самого крок Ньютона.

Після цього окремо перевіряється, чи нова точка зменшує цільова функція.

18. Демпфований метод Ньютона

Послідовне зменшення кроку можна застосувати до напрям Ньютона.

Спочатку обчислюється \(s_k\).

Потім пробується \(\alpha=1\).

Якщо умова Арміхо виконується, приймається повний крок.

Якщо умова не виконується, \(\alpha\) послідовно зменшується.

Поблизу мінімізатор алгоритм часто повертається до \(\alpha=1\).

Це дозволяє зберегти швидку локальну збіжність і водночас підвищити надійність далеко від розв’язку.

Якщо повний крок занадто агресивний, використовують:

\[ x_{k+1}=x_k+\alpha s_k \]

із \(\alpha<1\).

Пошук довжини кроку може перевіряти умова Арміхо.

Поблизу хорошого мінімізатор повний крок часто приймається.

Далеко від нього демпфування підвищує надійність.

Програмна реалізація та перевірка

19. Зіставлення математики й Python

Математика	Python	Зміст
\(x_k\)	`point`	поточна точка
\(g_k\)	`current_gradient`	градієнт
\(H_k\)	`current_hessian`	матриця Гессе
\(s_k\)	`newton_step`	напрям Ньютона
\(r_N\)	`system_residual`	нев’язка системи

20. Навчальна реалізація одного кроку

# Імпортуємо NumPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np


# Описуємо цільову функцію тією самою формулою, що й у математичній постановці.
def objective(point):
    x = point[0]
    y = point[1]

    # Повертаємо результат допоміжного обчислення у погодженому числовому форматі.
    return (
        (x - 2.0) ** 2
        + 2.0 * (y + 1.0) ** 2
    )


# Описуємо градієнт у фіксованому порядку координат, щоб код відповідав математичному вектору.
def gradient(point):
    x = point[0]
    y = point[1]

    # Повертаємо результат допоміжного обчислення у погодженому числовому форматі.
    return np.array([
        2.0 * (x - 2.0),
        4.0 * (y + 1.0),
    ])


# Виносимо окрему математичну операцію в допоміжну функцію, щоб її було легко перевірити.
def hessian(point):
    return np.array([
        [2.0, 0.0],
        [0.0, 4.0],
    ])


# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
point = np.array([
    10.0,
    10.0,
])

# Обчислюємо крок Ньютона або перевіряємо систему для цього кроку.
current_gradient = gradient(point)
current_hessian = hessian(point)

# Розв’язуємо лінійну систему напряму, без явного обчислення оберненої матриці.
newton_step = np.linalg.solve(
    current_hessian,
    -current_gradient,
)

# Обчислюємо крок Ньютона або перевіряємо систему для цього кроку.
next_point = point + newton_step

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("STEP:", newton_step)
print("NEXT_X:", next_point)
print("OBJECTIVE:", objective(next_point))
print("GRAD_NORM:", np.linalg.norm(gradient(next_point)))

21. Очікуваний результат

STEP: [ -8. -11.]
NEXT_X: [ 2. -1.]
OBJECTIVE: 0.0
GRAD_NORM: 0.0

З рухомою комою представлення може містити дуже малі похибки.

Для цієї квадратичної функції точний результат особливо простий.

22. Перевірка матриці Гессе

Для складної функції бажано виконати перевірка матриці Гессе до Ньютона оптимізація.

Можна чисельно диференціювати градієнт і порівняти матриці.

Якщо нев’язка матриці Гессе велика, напрям Ньютона може бути систематично неправильним.

Перевірка градієнта і перевірка матриці Гессе виконують різні ролі.

Перший перевіряє перші похідні.

Другий перевіряє локальну зміну градієнт.

Обидва тести особливо цінні до запуску дорогого ітераційний чисельний розв’язувач.

Перед кроком корисно обчислити власні значення:

# Обчислюємо власні значення симетричної матриці, щоб визначити знак локальної кривизни.
eigenvalues = np.linalg.eigvalsh(
    current_hessian
)

Очікуємо:

[2. 4.]

Це підтверджує додатну визначеність.

На загальній функції така перевірка може бути дорогою для великої матриці.

Тому великі чисельні розв’язувачі використовують інші чисельні механізми.

23. Перевірка Ньютона нев’язка системи

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
system_residual = np.linalg.norm(
    current_hessian @ newton_step
    + current_gradient
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print(system_residual)

Очікується число близьке до нуля.

Цей нев’язка перевіряє, чи крок справді розв’язує локальну лінійну систему.

Інтерпретація, межі та підсумок

24. Типові помилки

Також часто забувають, що матриця Гессе повинна відповідати тій самій точці, що й градієнт.

Використання старої матриці Гессе із новим градієнтом створює іншу локальну модель.

У деяких методах таке наближення робиться навмисно, але тоді це вже інший алгоритм.

У базовому метод Ньютона обидва об’єкти обчислюються в \(x_k\).

Ще одна помилка — порівнювати кількість Ньютона і градієнт ітерації без урахування вартості одного кроку.

Типова помилка. У коді явно обчислюють np.linalg.inv(H) @ g. Для крок Ньютона краще розв’язати систему через np.linalg.solve.

Друга помилка — матриця Гессе використовується без перевірки кривизни.

Третя — повний крок завжди приймається далеко від мінімізатор.

Четверта — помилка в матриці Гессе не перевіряється чисельно.

П’ята — Ньютона нев’язка системи не контролюється.

25. Вартість методу

Для щільної матриці розв’язання загальної системи може бути дорогим приблизно кубічно за \(n\).

Це грубий орієнтир для щільної лінійної алгебри.

При великих \(n\) структура матриці стає критичною.

Розріджена матриця Гессе може бути значно дешевшою.

У деяких задачах використовують добуток матриці Гессе на векторs без явного зберігання повної матриці.

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

Градієнтний спуск потребує градієнт.

Метод Ньютона потребує градієнта, матриці Гессе та розв’язання лінійної системи.

Для \(n\) змінних повна матриця має \(n^2\) елементів.

Це може бути дорого за пам’яттю та часом.

Тому метод Ньютона особливо привабливий для задач помірного розміру з доступною матрицею Гессе.

Для великих задач з’являються квазіньютонівські методи.

26. Локальна швидкість

Поблизу добре поводженого мінімізатор метод Ньютона може мати квадратичну збіжність.

Інтуїтивно кількість правильних цифр може швидко зростати.

Ця швидкість пояснює привабливість методу.

Проте вона є локальною властивістю.

Далеко від мінімізатора поведінка залежить від моделі, демпфування і кривизни.

26.1. Порівняння з градієнтним спуском на наскрізній функції

Градієнтний спуск із довжиною кроку 0.1 робить:

\[ \begin{pmatrix} 10\\ 10 \end{pmatrix}\rightarrow \begin{pmatrix} 8.4\\ 5.6 \end{pmatrix} \]

Метод Ньютона робить:

\[ \begin{pmatrix} 10\\ 10 \end{pmatrix}\rightarrow \begin{pmatrix} 2\\ -1 \end{pmatrix} \]

Різниця виникає через масштабування за локальною кривизною.

За координатою \(y\) матриця Гессе має більшу кривизну, тому крок Ньютона сильніше коригує компоненту градієнта.

Цей приклад показує, що метод Ньютона масштабує компоненти кроку відповідно до локальної кривизни.

26.2. Число обумовленості і система Ньютона

Якщо матриця Гессе має велике число обумовленості, розв’язання лінійної системи може бути чутливим до чисельних похибок.

Тоді навіть правильна математичний формула може давати нестабільний крок.

Корисно оцінювати:

\[ \kappa(H) \]

або найменше власне значення.

Висока число обумовленості є сигналом для масштабування або регуляризація.

Це ще одна причина, чому чисельна лінійна алгебра є частиною оптимізація метод.

26.3. Модифікований метод Ньютона

Один практичний варіант:

\[ \widetilde{H}=H+\mu I \]

де \(\mu>0\).

Потім розв’язується:

\[ \widetilde{H}s=-g \]

Якщо початкова матриця Гессе має від’ємне власне значення, додавання \(\mu I\) зміщує всі власні значення вгору.

За достатнього \(\mu\) матриця стає додатно визначена.

Це робить напрям придатним для спадання пошук довжини кроку.

26.4. Коли метод Ньютона особливо доречний

Метод привабливий, якщо:

кількість змінних помірна;
градієнт і матриця Гессе доступні;
матриця Гессе має корисну структуру;
потрібна висока локальна точність;
розв’язання лінійної системи не є надто дорогим.

Для великих щільний задачі BFGS або L-BFGS часто практичніші.

26.5. Мінімальний звіт

Для одного крок Ньютона достатньо вказати:

X_K
GRADIENT
HESSIAN
STEP
SYSTEM_RESIDUAL
NEXT_X
NEXT_OBJECTIVE
NEXT_GRAD_NORM

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

26.6. Одновимірний крок Ньютона як знайомий приклад

Для:

\[ f(x)=(x-2)^2+1 \]

маємо:

\[ f'(x)=2(x-2) \]

та:

\[ f''(x)=2 \]

Ньютона оновлення:

\[ x_{k+1}= x_k-\frac{2(x_k-2)}{2} \]

Отже:

\[ x_{k+1}=2 \]

з будь-якої стартової точки.

Це одновимірний аналог збіжність за один крок на квадратична функція.

26.7. Що робити після `np.linalg.solve`

Розв’язання лінійної системи повертає крок, але його ще потрібно перевірити.

Спочатку обчислюється нев’язка системи.

Потім перевіряється напрямна похідна:

\[ g^Ts \]

Для додатно визначеної матриці Гессе очікується від’ємне значення.

Після оновлення перевіряється цільова функція та нова норма градієнта.

Такий порядок дає підтвердження для кожного етапу ньютонівської ітерації.

26.8. Регуляризація і масштаб

Параметр \(\mu\) у модифікованій матриці Гессе:

\[ H+\mu I \]

має той самий масштаб, що й власні значення матриці Гессе.

Тому значення \(\mu\) не можна вибирати абсолютно без урахування кривизна масштаб.

Малий \(\mu\) майже не змінює добре обумовлену матрицю Гессе.

Великий \(\mu\) робить напрям ближчим до масштабованого градієнтного кроку.

Отже, регуляризація плавно змінює поведінку між ньютонівським і градієнтним рухом.

26.9. Метод Ньютона і точність похідних

Помилка градієнт впливає на праву частину система.

Помилка матриці Гессе впливає на крок.

Тому метод другого порядку чутливий до обох рівнів похідних.

Якщо матриця Гессе наближена, метод уже наближається до квазіньютонівської ідеї.

BFGS систематично будує таку наближення без других похідних.

26.10. Напрям Ньютона і координатне масштабування

метод Ньютона природно враховує кривизна масштаб.

Якщо одна координата має кривизну у 100 разів більшу, обернена матриця Гессе зменшує відповідну компоненту напряму.

Це пояснює меншу чутливість до простого масштабування координат порівняно з звичайним градієнтним спуском.

Проте дуже погано обумовлена матриця Гессе все одно створює чисельні проблеми.

Тому масштабування залишається корисним навіть для метод другого порядкуи.

26.11. Верифікація після демпфування

Якщо використано \(\alpha<1\), точка вже не є мінімізатор локальної квадратична модель.

Тому потрібно окремо перевірити фактичне зменшення цільова функція.

Також слід зберегти:

NEWTON_STEP
DAMPING
ACTUAL_STEP

де:

\[ \text{ACTUAL_STEP}=\alpha s \]

Це дозволяє відрізнити геометрію напряму від прийнятий рух.

26.12. Ліміт ітерацій і статус

метод Ньютона також потребує max_iterations.

Можливі статусes:

CONVERGED
MAX_ITERATIONS
SINGULAR_HESSIAN
NON_DESCENT_DIRECTION
LINE_SEARCH_FAILED

Такий набір причин значно корисніший за одне логічне значення.

Він пояснює, на якому математичному етапі зупинився алгоритм.

26.13. Порівняння повного та демпфованого кроку

Повний крок Ньютона використовує:

\[ \alpha=1 \]

варіант зі зменшенням кроку використовує:

\[ 0<\alpha<1 \]

Напрям \(s\) залишається тим самим.

Змінюється тільки фактична довжина руху.

Тому пошук довжини кроку зберігає ньютонівську геометрію напряму та контролює довіру до локальної моделі.

Це важлива різниця між побудовою напрям і вибором прийнятого кроку.

26.14. Чому квадратична збіжність є локальною

Швидка збіжність очікується, коли точка вже достатньо близька до регулярного мінімізатора, матриця Гессе невироджена і похідні гладкі.

Далеко від мінімізатора модель Тейлора може бути грубою.

Тому перші ітерації іноді потребують демпфування.

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

26.15. Підсумкова схема перевірки

Ньютона ітерація можна перевіряти так:

GRAD_NORM
MIN_EIGENVALUE
SYSTEM_RESIDUAL
STEP_NORM
DIRECTIONAL_DERIVATIVE
NEW_OBJECTIVE

Разом ці числа показують стаціонарність, кривизна, якість розв’язання лінійної системи, масштаб крок та фактичний прогрес.

26.16. Контрольна думка

Метод Ньютона активно використовує кривизну, тому якість матриці Гессе критична. Перед довгим запуском потрібно перевірити градієнт, матрицю Гессе, нев’язку лінійної системи та фактичне зменшення цільової функції.

26.17. Практична інтерпретація

крок Ньютона є розв’язком локальної моделі, тому його якість залежить від того, наскільки добре квадратичний наближення описує справжню функцію. Перевірка нового цільова функція показує, чи локальна модель була достатньо надійною.

26.18. Контрольний висновок

Коректний крок Ньютона має малий малу нев’язку лінійної системи, узгоджену кривизна інформація і фактичний чисельний прогрес. Якщо будь-яка з цих перевірок не проходить, повний крок не слід приймати автоматично.

26.19. Фінальна примітка

метод Ньютона поєднує математичний аналіз і лінійну алгебру в одному кроці. Тому студентський звіт повинен показувати обидві частини: інформацію про похідні та перевірене розв’язання лінійної системи.

Ця структура також пояснює, чому квазіньютонівські методи намагаються відтворити Ньютона геометрія дешевшим способом.

Практичний Ньютона перевірка завершує перевірку локальної моделі.

Це принципово для надійності.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

27. Підсумок

Метод Ньютона будує біля поточної точки локальну квадратичну модель, яка використовує градієнт і матрицю Гессе. Крок \(s_k\) знаходять із системи \(H(x_k)s_k=-\nabla f(x_k)\), після чого оновлюють точку як \(x_{k+1}=x_k+s_k\). Для точно квадратичної функції ця модель збігається з початковою ціллю, тому мінімізатор може бути досягнутий за один крок.

У наскрізному прикладі зі старту \((10,10)\) система дає крок \((-8,-11)^T\) і точку \((2,-1)\). Важливо перевірити нев’язку \(Hs+g\), нове значення цілі та норму градієнта. У коді практичніше розв’язувати лінійну систему через solve, ніж формувати явну обернену матрицю.

Для загальної нелінійної функції повний ньютонівський крок може бути надто сміливим, особливо далеко від мінімізатора або за невизначеної матриці Гессе. Тому практичні реалізації використовують демпфування, пошук довжини кроку або модифікацію кривизни. Наступна тема покаже, як наближати корисну інформацію другого порядку без явного обчислення повної матриці Гессе.