Метод поділу відрізка пополам

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

Якщо тоді одержимо проміжок і якщо ж тоді одержимо проміжок і . Одержали новий проміжок

Шукаємо до тих пір якщо і тоді за наближене значення розвязку ми вибираємо середнє значення . Так як на кожному кроці ми вдвічі зменшуємо проміжок то на n-му кроці початковий проміжок. Цей метод є найповільнішим, але якщо швидкість не грає ролі то цей метод один з найкращих. Недоліком його є те, що він не знаходить коренів парної кратності.

Збіжність методу простої ітерації

Означення. Функцію будемо називати Ліпшиц неперервною із сталою на якщо для виконується

За область будемо приймати деяку множину (проміжок довжиною 2r з серединою в точці .)

Теорема. (про збіжність простої ітерації)

Якщо є Ліпшиц-неперервною з сталою на проміжку при чому то рівняння має на єдиний корінь і метод простої ітерації збіжний до розвязку при довільному початковому наближенні і дл похибки буде справедлива така оцінка

Доведення. Покажемо що , тобто метод простої ітерації не виходить за межі множини де функція є Ліпшиц-неперервною. Нехай покажемо що

тоді враховуючи умову Ліпшица неперервності і умову (3) можемо записати

,

тобто . Тобто метод простої ітерації не виходить за межі де функція є ліпшиц неперерервною Тоді оцінимо різницю двох ітерацій оскільки то одержимо оцінку

ця оцінка дозволяє довести фундаментальність послідовності

Нехай тоді згідно (5)

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

Покажемо єдиність корненя. Припустимо що також є розвязком рівняння відмінний від . і розглянемо різницю .

Так як q<1 остання нерівність буде .виконуватись коли Розглянемо оцінку похибки (4) так як то ми перейдемо до нерівності

справедлива оцінка (4) Доведено.

Для перевірки збіжності зручніше користуватись наслідком.

Наслідок . Нехай є неперервною і диференційованою і якщо то метод простої ітерації збігається і справедлива оцінка (4)

Збіжність методу Ньютона

Розглянемо рівняння виду ., де на міститься єдиний корінь.

початкове наближення.

Виберемо довільне початкове наближення в околі нашого розвязку. Розглянемо рівняння

Якщо то

В околі розвязку буде виконуватись умова (3). Тоді при належному виборі початкового наближення метод Ньютона буде збіжним. Метод ньютона має квадратичну збіжність

Ітераційні методи для систем нелінійних рівнянь

Розглянемо систему нелінійних рівнянь

нелінійні функції

Надалі систему будемо розглядати як операторне рівняння

із (1) можемо записати

Дуже багато ітераційних методів для розв’язання системи (2) можуть бути записані по аналогії до системи лінійних алгебраїчних рівнянь.

канонічна форма для СНАР

початкове наближення

розвязок одержаний на k-ій ітерації

-визначає ітераційний метод

явний ітераційний метод

стаціонарний метод

Ітераційний метод може бути записаний

Тоді система (4) можна розв’язати будь-яким прямим або ітераційним методом.

– система лінійних алгебраїчних рівнянь яку ми можемо розв’язати будь-яким із ітераційних методів для розв’язання СЛАР. В ітераційних методах ітерації, що приводять до розв’язання системи (4) будуть називаються внутрішніми ітераціями, а ітераційні системи (3) будуть називатися зовнішніми .