Метод лінійного інтерполювання.



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


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



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


ЗНАЕТЕ ЛИ ВЫ?

Метод лінійного інтерполювання.



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

 

 

Рисунок 1.

 

Рисунок 2.

 

 

Рисунок 3.

 

 

Рисунок 4.

 

Як і у методі Ньютона, будемо вважати, що не тільки f′(х), але й f′′(х) не змінює знак на [a;b] (тобто що f′′*) ≠ 0 і відрізок ізоляції обрано достатньо малим). Тож можливі ті ж чотири варіанти залежно від знаків f′(х) та f′′(х). У всіх варіантах метод полягає в тому, що спочатку на [a;b] графік функції у = f(x) замінюється хордою АВ і абсциса точки перетину хорди з віссю Ох х1 є першим наближенням кореня. Далі те ж саме треба повторити на відрізку [a;х1] або [х1;b] залежно від того, якому з цих відрізків належить корінь х*, отримати друге наближення х2 і так далі. Із рисунку безпосередньо видно, що збіг ітерацій до кореня є монотонним для всіх чотирьох варіантів, як і у методі Ньютона. Тому всі відрізки, над якими графік замінюється хордою, мають одну спільну кінцеву точку: а або b залежно від варіанту. Не важко перевірити, що у всіх випадках нерухомим буде той кінець відрізку ізоляції, де знак f(x) збігається із знаком f′′(х), тобто f(x) ∙ f′′(х) > 0. У методі Ньютона саме ця умова була критерієм для вибору початкового наближення: отже збіг у методі хорд відбувається з протилежного боку і початкова точка – це довільна точка з [a;b], у якій виконується умова f(x) ∙ f′′(х) < 0.

Для виведення формули методу хорд запишемо рівняння прямої, що проходить через точки Аkk, f(xk)) і С(с, f(с)) (тут хk – це k – е наближення; с = а, якщо f(а) ∙ f′′(а) > 0 або с = b, якщо f(b) ∙ f′′( b) > 0 ):

.

Поклавши у = 0, знайдемо звідси точку перетину хорди AkC з віссю Ох – це і буде наступне наближення xk+1:

 

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

Ця формула визначає ітераційний метод: тут

φ(х) = х – (х – с) = х – λ(х) ∙ f(x), де λ(х) = .

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

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

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

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

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

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

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

2. f′′(х) = 2х(ln 2)2 > 0 при всіх х.

3,4. Оскільки f(0) = –2, f(1) = 4, то за початкове наближення можна взяти точку а = 0, за нерухомий кінець b = 1.

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

 

  A B C D
= 2^A1 + 5*A1 – 3 = 2^C1 + 5*C1 – 3
= A1 – B1*(A1 – $C$1)/(B1 – $D$1)    
   

 

Тут у чарунці А1 початкове наближення а = 0, у В1 f(a), у C1 нерухомий кінець b = 1, у D1 f(b). Зауважимо, що формулу у D1 можна просто скопіювати з В1. У чарунці А2 задана формула методу лінійного інтерполювання (5). Нерухомий кінець не змінюється, отже для його завдання використана абсолютна адресація (після набору С1 треба натиснути F4, так само з D1). Формули у стовбцях А і В копіюються. В результаті отримуємо:

 

 

  A B C D
-2
0,333333333 -0,073412283    
0,345348204 -0,0028014    
0,345806369 -0,000107047    
0,345823876 -4,09071E-06    
0,345824545 -1,56323E-07    
0,34582457 -5,97374E-09    
0,345824571 -2,28281E-10    
0,345824571 -8,72369E-12    
0,345824571 -3,33067E-13    
0,345824571 -1,28786E-14    
0,345824571    

 

Для стабілізації тут знадобилось 8 ітерацій. Це дещо поступається за швидкістю методу Ньютона, де їх було 5, але значно перевищує метод дихотомії, де в тому ж прикладі до стабілізації було 23 ітерації. Розглянемо другий приклад: знайти корінь рівняння 2∙sin x – x2 + 2 = 0 з точністю e = 0,5*10-5.

1. За змістом тут достатньо знайти один будь – який корінь. Обираємо той самий відрізок ізоляції [a;b] = [1,8;2,2].

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

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

Надамо чарункам електронної таблиці таких значень:

 

  A B C D
1,8 = 2*sin(A1) – A1^2 + 2 2,2 = 2*sin(C1) – C1^2 + 2
= A1 – B1*(A1 – $C$1)/(B1 – $D$1)    
   

 

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

 

  A B C D
1,8 0,707695262 2,2 -1,2230072
1,946619229 0,071085379    
1,960537606 0,00630708    
1,961766184 0,000553234    
1,961873901 4,84788E-05    
1,96188334 4,24772E-06    
1,961884167 3,72184E-07    
1,961884239 3,26106E-08    
1,961884246 2,85732E-09    
1,961884246 2,50358E-10    
1,961884246 2,19358E-11    

 

Тут 9 ітерацій при 5 у методі Ньютона і 12 для метода простої ітерації із сталим λ. Який порядок збігу у ітераційного процесу метода лінійного інтерполювання? Згідно з доведенням теореми 7 достатньо порахувати похідні функції, яка визначає метод хорд: φ(х) = х – λ(х) ∙ f(x), де λ(х) = , у корені х* (f(x*) = 0). Отже

φ′(х*) = 1 – λ′(х*) ∙ f(x*) – λ(х*) ∙ f ′(x*) = 1 – f ′(x*) ∙ = 1 – f ′(x*) / f ′( ) ,

де за теоремою Лагранжа є (x*; c). Звідси маємо φ′(х*) = ≠ 0, оскільки f ′(x*) – f ′( ) = f ′′(ξ) ∙ (х* – ), де ξ є (x*; ), а f ′′(х) ≠ 0 на всьому відрізку ізоляції за передумовою методу лінійного інтерполювання. Отже метод хорд збігається лінійно так само, як і метод простої ітерації із сталим λ, однак, як бачимо на прикладах, за рахунок несталості λ швидкість збігу дещо підвищилась.



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

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