Метод Ньютона. Порядок збіжності ітераційного процесу.



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Метод Ньютона. Порядок збіжності ітераційного процесу.



Розглянемо класичний ітераційний метод обчислення кореня х* рівняння f(x) = 0 на відрізку ізоляції [a;b], який є простим і дуже ефективним одночасно – метод Ньютона. Нехай хk – відоме k– е наближення кореня, треба знайти хk+1. Будемо вважати, що f(x) двічі диференційовна на [a;b] і застосуємо формулу Тейлора в околі точки хk:

f(x) = fk) + f′k)(х – хk) + ½ f′′k)(х – хk)2 + … = 0.

Нехтуючи нелінійними відносно х – хk додатками, отримаємо fk) + f′k)(х – хk) = 0, звідки х = хk . Знайдене значення х і будемо вважати рівним хk+1:

хk+1 = хk (k = 0, 1, 2, … ).

Ця формула і визначає ітераційний метод Ньютона: тут φ(х) = х – λ(х) ∙ f(x), λ(х) = . Від прикладів попередніх розділів він відрізняється лише тим, що тут λ залежить від х.

Метод Ньютона має просту геометричну інтерпретацію. Рівняння y = fk) + f′k)(х – хk) – це рівняння дотичної до графіку функції y = f(х) у точці хk , а отже вище знайдене хk+1 є точкою перетину цієї дотичної з віссю абсцис. Тому метод Ньютона називають ще методом дотичних. Будемо вважати, що не тільки f′(х), але й f′′(х) не змінює знак на [a;b], тобто що f′′*) ≠ 0 і відрізок ізоляції обрано достатньо малим. Тож можливі чотири варіанти залежно від знаків f′(х) та f′′(х). Наприклад, якщо f′(х) > 0, f′′(х) < 0, то функція f(х) є зростаючою та опуклою, як це зображено на наступному рисунку 1. З нього можна

 

Рисунок 1.

 

Рисунок 2.

 

Рисунок 3.

 

Рисунок 4.

 

безпосередньо побачити, що для всіх можливих варіантів з одного боку відрізка ізоляції ітерації монотонно збігаються до кореня х* , а з другого можуть опинитись за межами відрізку вже на першому кроці. Легко переконатись (рисунки 1 – 4), що збіг спостерігається при всіх варіантах на тому боці, де виконується умова f(х) ∙ f′′(х) > 0.

Отже, для застосування метода Ньютона необхідно забезпечити наступні передумови.

1. Треба знайти відрізок ізоляції шуканого кореня.

2. Треба забезпечити, щоби на відрізку ізоляції не змінювався знак у f′′(х), зменшуючи при необхідності початковий відрізок.

3. За початкове наближення можна брати будь – яку точку х відрізку ізоляції, у якій виконується умова f(х) ∙ f′′(х) > 0.

Розглянемо застосування методу Ньютона на прикладі задачі: розв‘язати рівняння f(x) = 2х + 5x – 3 = 0 з точністю e = 0,5*10-5.

1. Ця задача уже була розв’язана методом дихотомії і там був знайдений відрізок ізоляції [a;b] = [0;1] для єдиного кореня цього рівняння.

2. f′(х) = 2х(ln 2) + 5, f′′(х) = 2х(ln 2)2 > 0 при всіх х. Отже на [0;1] знак f′′(х) не змінюється.

3. Як з графіку функції у = f(x), так і обраховуючи безпосередньо, отримаємо f(0) = –2, f(1) = 4. Тому за початкове наближення можна взяти точку b = 1.

4. Нарешті знайдемо корінь на [0;1] з точністю e = 0.5*10-5 методом Ньютона за допомогою Excel. Надамо чарункам електронної таблиці таких значень:

 

  A B C
= 2^A1 + 5*A1 – 3 = 2^A1*ln2 + 5
= A1 – B1/C1

 

Тут у А1 початкова точка b = 1, у В1 значення f(x) при х = А1, у С1 – значення f′(х) при х = А1, у А2 задано формулу метода Ньютона хk+1 = хk і далі копіюємо ці формули. В результаті отримуємо:

 

  A B C
6,386294361
0,373658686 0,163927839 5,898065336
0,345865193 0,000238894 5,880929713
0,345824571 5,03792E-10 5,880904909
0,345824571 5,880904909
0,345824571 5,880904909

 

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

 

Задача. Знайти корінь рівняння 2∙sin x –x2 +2 = 0 з точністю e = 0,5*10-5.

За змістом тут досить знайти будь – який один корінь рівняння. Як уже відомо, існує два корені у відрізках ізоляції [-1;-0,6] і [1,8;2,2]. Обираємо другий: у ньому кількість ітерацій була дещо більшою і дорівнювала 12.

1. Отже [a;b] = [1,8;2,2].

2. f′(х) = 2 ∙ cos x – 2x, f′′(x) = – 2 ∙ sin x – 2 ≤ 0 при всіх х. Отже на [1,8;2,2] знак f′′(х) не змінюється.

3. З графіку функції у = f(x) бачимо, що f(1,8) > 0, f(2,2) < 0. Тому за початкове наближення можна взяти точку b = 2,2.

4. Відповідна електронна таблиця:

 

  A B C
= 2*sin x – x2 + 2 = 2*cos x – 2*x
= A1 – B1/C1

 

В результаті отримуємо:

 

  A B C
2,2 -1,22300719 -5,57700223
1,980705271 -0,08887914 -4,75846218
1,962027148 -0,0006697 -4,68670735
1,961884255 -3,9295E-08 -4,68615736
1,961884246 -4,68615733
1,961884246 -4,68615733

 

Стабілізація знову на п’ятому кроці! Схоже на то, що метод Ньютона більш ефективний, ніж попередні. Формалізуємо це спостереження.

Означення.Нехай хk (k = 0,1,2,…) – значення ітерації деякого процесу без урахування похибок обчислень, хk= х*. Порядок збіжності ітераційного процесу – це таке найбільше натуральне число α, що │хk – х*│≤ С│хk-1 – х*α (k = 0,1,2,…), де С > 0 – деяка стала.

Якщо α = 1, то кажуть, що ітераційний процес збігається лінійно; якщо α = 2, то квадратично і так далі. Наприклад, якщо хk – це процес простої ітерації, тобто хk = φ(хk-1) (k = 0,1,2,…) і функція φ(х) задовольняє умові Ліпшиця з константою Ліпшиця q, то

│хk – х*│ = │φ(хk-1) – φ(х*)│ ≤ q│хk-1 – х*│. Звідси видно, що будь – який процес простої ітерації має принаймні лінійну збіжність.

 

Теорема 7. Ітераційний процес метода Ньютона збігається квадратично.

1. Спочатку розглянемо довільний процес простої ітерації: хk = φ(хk-1) на відрізку ізоляції [a;b] кореня х*, хk= х*. Нехай в околі кореня х* функція φ(х) має m неперервних похідних і

φ′(х*) = φ′′(х*) = … = φ(m-1)(х*) = 0, φ(m)(х*) ≠ 0. (3)

За формулою Тейлора

φ(х) – х* = (х – х*)φ′(х*) + φ′′(х*) + … + φ(m-1)(х*) + φ(m)(ξ) = = φ(m)(ξ), де ξ є [x; x*] [a;b] . Зокрема при х = хk-1, φ(хk-1) = хk маємо хk – х* = φ(m)k), де ξk є [хk ; x*] [a;b]. Звідси

│хk – х*│ ≤ С│хk-1 – х*m , де С = │φ(m)(ξ)│ ≠ 0. (4)

Отже з (3) випливає, що порядок збіжності α процесу хk = φ(хk-1) дорівнює m.

2. Тож для доведення теореми достатньо порахувати похідні функції φ(х) = х – , яка визначає метод Ньютона, у корені х* (f(x*) = 0). Отже

φ′(х*) = (х – )′│х* = 1 – х* = х* = 0.

φ′′(х*) = ( )′│х* = ( + f(x) ∙ ( )′ )│х* = ≠ 0,

оскільки у методі Ньютона за умовою f′(x*) ≠ 0, f′′(x*) ≠ 0. Теорема доведена.

З формули (4) випливає також, що │хk – х*│ ≤ С ∙│хk-1 – х*2, де С = │. Отже, якщо наближення хk-1 має m правильних десяткових знаків, то хk у методі Ньютона щонайменше матиме 2m правильних десяткових знаків. Однак, у теоремі 7 врахована тільки похибка методу і згідно з висновком теореми 6 цей найшвидший збіг триватиме лише доти, доки похибка методу за величиною не зрівняється з похибкою обчислень.



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.68.118 (0.008 с.)