Реалізація методу простої ітерації за допомогою електронних таблиць

Спочатку згідно з методом треба замінити задане рівняння f (x) = 0 на еквівалентне х = φ(х). Існує універсальна заміна для функцій f (x), диференційовних на відрізку ізоляції її кореня та з незмінним там знаком f′ (x) згідно з теоремою 1. А саме покладемо φ(х) = х – λ f (x), тут λ – деяка дійсна стала, λ ≠ 0. Підберемо l так, щоби у φ(х) на [ a;b ] була константа Ліпшиця q < 1. Звідси │φ′(х)│ = ; або , якщо додатково вважати, що φ′(х) ≥ 0, тобто що збіг ітерацій до кореня є монотонним (див. рисунок). Тому або при φ′(х) ≥ 0. Тому, оскільки f′ (x) не змінює знак на , то стала λ має однаковий знак з f′ (x) і │λ│< 2/М₁, де М₁ = або ж │λ│≤ 1/М₁ при φ′(х) ≥ 0. Бажано, щоби q було найменшим можливим: чим менше q, тим збіг швидше. При умові φ′(х) ≥ 0, тобто при значення при кожному х буде найменшим можливим, якщо │λ│ обрати найбільшим можливим, тобто │λ│= 1/М₁. Тоді найменше спільне для всіх х є одночасно значення q = 1 – │λ│ = 1 – m₁/М₁, де m₁ = . Насправді ж це найменше можливе q і без припущення, що φ′(х) ≥ 0: за умови φ′(х) ≤ 0 можна так само отримати найкраще значення q = М₁/m₁ – 1. Але М₁/m₁ – 1 > 1 – m₁/М₁. Отже

Висновок. Н айкраще (тобто найменше) можливе значення константи Ліпшиця функції φ(х) = х – λ f (x) на відрізку [ a;b ] ізоляції кореня рівняння f (x) = 0 дорівнює

q = 1 – m₁/М₁, де М₁ = , m₁ = , при цьому │λ│= 1/М₁, > 0. (2) Крім того при такому λ збіг ітерацій процесу х_k = φ(х_k-1) до кореня є монотонним.

Зауважимо, що монотонний збіг значно спрощує перевірку умови застосування методу простої ітерації (тобто умови Ліпшиця) та вибір його початкової точки x₀. Справді, тоді всі наступні ітерації розташовані між коренем і x₀, тому умову застосування достатньо перевірити на обраному відрізку ізоляції, а у якості x₀ взяти будь – яку точку цього відрізку. У протилежному ж випадку, якщо корінь насправді розташований біля краю відрізка ізоляції, то наступна ітерація може опинитися за межами відрізку. Тому умову Ліпшиця слід перевіряти на відрізку втричі довше ніж відрізок ізоляції.

Іноді замість φ(х) = х – λ f (x) використовують рівносильну заміну φ(х) = х – , λ = , μ ≠ 0. Тоді відповідні необхідні умови на μ це і , найкраща оцінка q досягається при μ = М₁ = .

Нарешті значення М₁ і m₁ не важко знайти при умові, що функція f ′(x) монотонна на : тоді це значення f′ (x) на краях цього відрізку.

Отже, розглянемо застосування методу простої ітерації на такій задачі: розв‘язати рівняння f (x) = 2 ∙ sin x – x² + 2 = 0 з точністю e = 0,5*10^-5.

1. Відрізки ізоляції коренів рівняння f (x) = 0 уже визначені в першому розділі лекції і ці результати доведені комбінованим методом. Це [-1;-0,6] і [1,8;2,2].

2. Знайдемо заміну φ_i(х) = х – λ_i f (x) для кожного з відрізків, i = 1,2. При i = 1 = [-1;-0,6]. Тут f′′ (x) = – 2 ∙ sin x – 2 ≤ 0 при всіх х, тож f′ (x) монотонно спадає. Отже, на М₁ = = │ f′ (-1)│≈ 3,08, m₁ = = │ f′ (-0,6)│≈ 2,85. Згідно з (2) (оскільки f′ (x) > 0 на [-1;-0,6]) покладемо λ₁ = 1/М₁ ≈ 0,32, φ₁(х) = х – 0,32∙(2sinx–x²+2), тоді q = 1 – m₁/М₁ ≈ 0,07.

Аналогічно при i = 2 = [1,8;2,2], М₁ = │ f′ (2,2)│≈ 5,57, m₁ = │ f′ (1,8)│≈ 4,05, покладемо λ₂ = – 1/М₁ ≈ – 0,18 (оскільки f′ (x) < 0 на [1,8;2,2]), φ₂(х) = х + 0,18(2sinx–x²+2), тоді q = 1 – m₁/М₁ ≈ 0,27.

3. Знайдемо корені на відрізках ізоляції з точністю e = 0.5*10^-5 методом простої ітерації за допомогою Excel. У першому випадку = [-1;-0,6], φ(х) = х – 0,32∙(2 ∙ sin x – x² + 2). Оскільки оптимальний вибір λ передбачає монотонний збіг ітерацій, то можна вибрати будь – яку точку з у якості початкової точки x₀, наприклад x₀ = а = – 1. Надамо чарункам електронної таблиці таких значень:

 

	A	B	С
	– 1	= 2 ∙ sin(А1) – А1^2 + 2	0,32
	= A1 – $C$1*B1	↓
	↓	↓

 

Тут у А1 початкова точка а = – 1, у В1 формула функції f (x) при х = А1, у С1 значення λ₁ ≈ 0,32, у А2 формула функції φ₁(х) = х – λ₁∙ f (x) при х = А1. Як і раніше, символ ↓ означає копіювання попередніх чарунок. В результаті отримаємо таку таблицю:

 

	A	B	C
	-1	-0,68294197	0,32
	-0,78145857	-0,019308672
	-0,775279795	-0,000890639
	-0,77499479	-4,16322E-05
	-0,774981468	-1,94725E-06
	-0,774980845	-9,10811E-08
	-0,774980816	-4,26025E-09
	-0,774980814	-1,9927E-10
	-0,774980814	-9,32099E-12
	-0,774980814	-4,36096E-13

 

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

	A	B	C
	= B10 + 0,5*10^-^5
	= B10 – 0,5*10^-^5

 

 

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

	A	B	C
	-0,774980814	-4,36096E-13
	-0,774975814	1,48941E-05
	-0,774985814	-1,48942E-05

 

У стовпці В відповідні значення функції f (x) приймаються автоматично. Оскільки f (-0,774980814 + 0,5*10^-5) > 0, a f (-0,774980814 – 0,5*10^-5) > 0, то значення – 0,77498 є коренем рівняння f (x) = 0 з точністю 0,5*10^-5.

Другий випадок є аналогічним: = [1,8;2,2], φ(х) = х + 0,18(2∙sin x –x² +2), обираємо x₀ = 1,8, у електронній таблиці треба лише замінити значення у чарунках А1 і С1:

 

	A	B	С
	1,8	= 2 ∙ sin(А1) – А1^2 + 2	–0,18
	= A1 – $C$1*B1	↓
	↓	↓

 

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

 

	A	B	C
	1,8	0,707695262	-0,18
	1,927385147	0,159372589
	1,956072213	0,027171069
	1,960963005	0,004315447
	1,961739786	0,000676925
	1,961861632	0,000105972
	1,961880707	1,65847E-05
	1,961883693	2,5954E-06
	1,96188416	4,06159E-07
	1,961884233	6,35605E-08
	1,961884244	9,94668E-09
	1,961884246	1,55657E-09
	1,961884246	2,43591E-10
	1,961884246	3,81204E-11

 

Зміна значень з максимальним можливим числом значущих цифр припиняється у рядку 12. Зробимо перевірку:

 

	A	B	C
	1,961884246	3,81204E-11
	1,961889246	-2,34308E-05
	1,961879246	2,34308E-05

 

Тож значення 1,96188 є коренем рівняння f (x) = 0 з точністю 0,5*10^-5.

Спробуємо для = [-1;-0,6], замість оптимального λ = 0,32 вибрати вдвічі менше λ = 0,16. Очевидно, це λ задовольняє необхідним умовам збіжності: │λ│< 2/М₁, де М₁ = ≈ 3,08 і > 0. Збіг насправді має місце, однак стабілізація замість рядка 8 не завершується навіть у рядку 30:

 

	A	B	C
	-0,775010814	-8,93652E-05
	-0,775020814	-0,000119154
	-0,775015814	-0,000104259
	-0,775025814	-0,000134048
	-0,775020814	-0,000119154
	-0,775030814	-0,000148942