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

1 Розв’язок даного рівняння - це точка, в якій крива проходить через нуль. Беремо початкове наближення . Замінюємо поблизу точки лінійним рівнянням (2.5).

. (2.5)

Ліва частина якого - це два перших члена розкладеної функції в ряд Тейлора.

2 Розв’яжемо лінійне рівняння (2.5) і знайдемо поправку до початкового наближення:

. (2.6)

3 Наближення визначаємо згідно 2.7:

. (2.7)

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

. (2.8)

Геометричне пояснення: один крок методу Ньютона зводиться до заміни кривої на пряму , яка є дотичною до кривої в точці . Тому метод Ньютона називають також методом дотичних. Наближення є точкою перетину дотичної до кривої в точці з віссю Х.

Алгоритм методу Ньютона для системи нелінійних алгебраїчних рівнянь

Розглянемо розв’язання за методом Ньютона системи нелінійних алгебраїчних рівнянь.

(2.9)

1 Застосуємо вектор-стовпчик Х і вектор функцію W(X), де

, . (2.10)

Систему (2.9) представимо у вигляді матричного рівняння

. (2.11)

2 Нехай , , - початкові наближення невідомих. Замінимо кожне з нелінійних рівнянь системи (2.9) лінеаризованим. Перше рівняння після лінеаризації матиме вигляд

(2.12)

3 Запишемо матрицю Якобі, тобто матрицю похідних систем функцій за змінними .

(2.13)

4 Представимо систему лінеаризованих рівнянь у матричному вигляді

. (2.14)

Дана система лінійна відносно поправок .

5 Розв’яжемо лінійну систему (2.14) і визначимо поправки, наприклад, за методом Гауса і визначимо перше наближення змінних.

(2.15)

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

і визначення наступного наближення невідомих

.

6 Контроль збіжності виконуємо за вектором нев’язок, тобто умова

(2.16)

має виконуватись для всіх нев’язок.

2.5 Градієнтний метод з постійним кроком

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

, (2.17)

де - одиничні вектори.

Величина вектора визначається за виразом

. (2.18)

З (2.17) і (2.18) видно, що функція, градієнт якої визначається, повинна бути такою, що диференціюється по всіх п змінних.

Фізична суть градієнта функції в тому, що він показує напрям (2.17) і швидкість (2.18) найбільшої зміни функції в даній точці. Якщо в деякій точці , то ця точка є екстремумом функції.

Алгоритм градієнтного методу з постійним кроком

1 Відповідно до граничних умов, областю допустимих значень змінних буде перший квадрант системи координат. У цій області довільно виберемо початкове (нульове) наближення - точку з координатами . Значення цільової функції в цій точці рівне Z⁰.

2 Згідно з виразом (2.18) обчислимо в цій точці величину градієнта функції Z. Виконаємо крок одиничної довжини (λ=1) у напрямі екстремуму функції Z. В результаті чого отримаємо перше наближення - точку з координатами . Значення цільової функції в цій точці рівне Z¹.

3 Далі обчислювальна процедура повторюється: послідовно отримуємо 2-е, 3-є і 4-е наближення - точки з координатами, . Значення цільової функції в цих точках приймають значення Z²,Z³,Z⁴.

4 В результаті обчислювального процесу послідовно здійснюється наближення до екстремуму функції. Обчислювальна процедура закінчується, коли відносна зміна цільової функції на попередньому і-му і подальшому (і+1)-му кроках буде меншою заданої точності обчислень ε:

У цьому методі всі кроки виконувалися однакової довжини λ=1. Метод достатньо простий. Основний його недолік - велика вірогідність зациклення обчислювального процесу в околиці мінімуму функції Z. При цьому як шуканий розв’язок слід прийняти одну з останніх точок.

Для отримання точнішого результату необхідно вибрати крок меншої довжини. При цьому об'єм обчислень (кількість кроків) збільшиться.

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