Метод Ньютона (дотичних)

Лекція 3

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

Нехай корінь рівняння f(х) =0 відділений на відрізку [a, b], причому f'(х) і f"(х) неперервні і зберігають постійні знаки на всьому відрізку [а, b].

Геометричний зміст методу Ньютона полягає в тому, що дуга кривої у=f(х) замінюється дотичною до цієї кривої (звідси і друга назва: метод дотичних).

Перший випадок. Нехай f(а) <0, f(b) >0, f'(х) >0, f'(x)>0 (мал.5а), або f(а) >0, f(b)<0, f'(х) <0, f ” (х)<0 (мал.5б). Проведемо дотичну до кривої у=f(х) у точці B₀ (b; f(b)) і знайдемо абсцису точки перетину дотичної з віссю Ox.

Відомо, що рівняння дотичної в точці B₀ (b; f(b)) має вигляд:

y – f(b) = f^¢(b)×(x-b)

Вважаючи y=0, x=x₁, отримаємо

x₁ = b - f(b)/f^¢(b) (5)

Тепер корінь рівняння знаходиться на відрізку [a, x₁]. Застосовуючи знову метод Ньютона, проведемо дотичну до кривої в точці В₁(x₁; f(х₁)) і отримаємо

x₂ = x₁ - f(х₁)/ f^¢(х₁)

І взагалі

x_n+1 = x_n - f(х_n)/ f^¢(х_n) (6)

Одержуємо послідовність близьких значень x₁, x₂,..., x_n кожний наступний член якої ближче до кореня , ніж попередній. Однак всі x_n залишаються більше істинного кореня , тобто x_n - наближене значення кореня x_n з надлишком.

Другий випадок. Нехай f(а) <0, f(b) >0, f'(х)>0, f” (х)<0 (мал.6а) або f(а) >0, f (b)<0, f'(х)< 0, f”(х)>0 (мал.6б).

Якщо знову провести дотичну до кривої у = f(x) в точці В, то вона перетне вісь абсцис у точці, що не належить відрізку [a, b]. Тому проведемо дотичну в точці A₀(a; f(a)) і запишемо її рівняння для даного випадку:

y – f(a) = f^¢(a)(x-a)

Вважаючи у=0, x=x₁, знаходимо

x₁ = a - f(a)/ f^¢(a) (7)

Корінь знаходиться тепер на відрізку[ x₁, b ]. Застосовуючи знову метод Ньютона, проведемо дотичну в точці A₁ (x₁; f(x₁)) і отримаємо

x₂ = a - f(x₁)/ f^¢(x₁)

Мал.6

І взагалі

x_n+1 = a - f(x_n)/ f^¢(x_n) (8)

Одержуємо послідовність близьких значень х₁, х₂,..., x_n кожний наступний член якої ближче до істинного кореня , ніж попередній, тобто x_n — близьке значення кореня з недоліком.

Порівнюючи ці формули з раніше виведеними, помічаємо, що вони відрізняються друг від друга тільки вибором початкового наближення: у першому випадку за x₀ приймався кінець b відрізка, в другому — кінець a.

При виборі початкового наближення кореня необхідно керуватися наступним правилом: за вхідну точку слідує вибирати той кінець відрізка [а, b], на якому знак функції співпадає зі знаком другої похідної. У першому випадку f(b) • f”(х)>0 і початкова точка b=x₀, в другому f(a) • f”(x) >0 і в якості початкового наближення беремо а=x₀.

Для оцінки похибки можна користуватися загальною формулою

ç x - x_n ç£ç f (х_n) ç/ m, (9)

де m = min ç f^¢ (х) ç [а £ x £ b].

Ця формула годиться і для методу хорд. У випадку, коли відрізок [а, b] настільки малий, що наньому виконується умова

m₂<2m₁, де m₂ = max ç f^¢¢ (х) ç, a m₁ = min ç f^¢ (х) ç [а £ x £ b].

Точність наближення на k- ому кроку оцінюється так:

якщо ç x_k+1 - x_k ç< e,, то ç x - x_k ç< e².

Якщо похідна f'(x) мало змінюється на відрізку [а, b], то для спрощення обчислень можна користуватися формулою

x_n+1 = x_n - f(x_n)/ f^¢(x_n) (10)

тобто значення похідної в початковій точці достатньо обчислити тільки один раз. Геометрично це означає, що дотичні в точках В_n(x_n; f(x_n)) замінюються прямими, паралельними до дотичної, проведеної до кривої у= f(х) в точці В₀ (x₀; f (x₀)) (мал.7).

Приклад. Методом дотичних уточнити до =0.001 корінь рівняння x³ +Зx²-3=0, розташований на відрізку [-2.75; -2.5].

Розв’язання. Раніше було встановлено, що f (-2.75)• f"(х) >0. Тому, щоб скористуватися методом дотичних, слід вибрати x₀ =-2.75. Обчислення будемо вести по формулі (10). Знаходимо f'(x₀) =Зх²+6x; f' (x₀)= f'(- 2.75)=6,1875.

Для зручності всі обчислення зведемо в наступну таблицю:

Таблиця 1

N	xп	x^3п	x^2п	3 x^2п	f(xп)	-f(xn) /6,1875
	-2,75 -2,571 -2,545 -2,537 -2,534 -2,533	-20,797 -16,994 -16,484 -16,329 -16,271	7,5625 6,6100 6,4770 6,4364 6,4212	22,6875 19,8300 19,431 19,309 19,2636	-1,111 -0,164 -0,053 0,020 0,007	0,179 0,026 0,008 0,003 0,001

З таблиці 1 видно, що ç x₅ - x₄ ç<0.001, тому x = x₅ =-2.533.

Дата добавления: 2014-01-07