Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Шпаргалки до екзамену - Чисельні методи - Методи розв'язування алгебраїчних рівнянь - файл 1.doc


Шпаргалки до екзамену - Чисельні методи - Методи розв'язування алгебраїчних рівнянь
скачать (350 kb.)

Доступные файлы (1):

1.doc350kb.26.11.2011 01:13скачать

содержание

1.doc

Чис. методи

  1. Методи розв’язання нелінійних рівнянь.

Нехай задано рівняння з однією змінною: (1) , де f(x) визначена і неперервна на деякому проміжку аb. Розв’язати р-ня означає знайти множину його коренів, тобто таких значень при яких р-ня (1) перетвориться в тотожність. Корінь р-ня (1) наз. нулем ф-ції f(x). Якщо ф-ція f(x) – алгебраїчний многочлен, то рівняння (1) наз. алгебраїчним. Якщо ф-ція f(x) містить тригонометричні, показникові або логарифмічні функції, тоді рівняння (1) наз. трансцендентним.

Знайти точні значення коренів заданого р-ня можна лише для найпростіших ф-цій f(x): алгебраїчних многочленів не вище 4-го степеня, деяких многочленів степеня n>5 і деяких трансцендентних функцій.

Отже, метод вважається точним, якщо похибка методу =0.

Універсальних методів для знаходження точних значень коренів алгебраїчних р-нь степеня n>5 і трансцендентних р-нь не існує. Крім того, розв'язуючи практичні задачі, часто дістають р-ня з коеф-ми, які є наближеними числами. Тоді постановка задачі знаходження точних коренів не має смислу. Тому важливого значення набувають наближені методи знаходження коренів рівняння з достатньою для практики точністю. Задача знаходження коренів р-ня(1) вважається розв'язаною, якщо корені обчислені із наперед заданою точністю.

Нехай х* – точний корінь, а його наближене значення. Кажуть, що корінь х обчислено з наперед заданою точністю , якщо . Нехай, наприклад, х* і , тоді числа а і b - наближені значення кореня х* відповідно з недостачею і надлишком з точністю . У цьому випадку за наближене значення з точністю можна взяти будь-яке число з відрізка [а;b].

Знаходження наближених коренів р-ня (1) складається з двох етапів:

  1. відокремлення коренів, тобто знаходження досить малих відрізків, на кожному з яких міститься один і тільки один корінь рівняння;

  2. обчислення коренів з наперед заданою точністю.

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

^ Відокремлення коренів:

Корінь х* р-ня(1) вважається відокремленим на відрізку якщо х* і на цьому відрізку дане р-ня не має інших коренів. Щоб відокремити корені р-ня (1), треба розбити область визначення даного р-ня на проміжки, на кожному з яких міститься один і тільки один корінь або немає жодного кореня. Відокремлюють корені графічним і аналітичним методами, а також методом послідовного перебору.

  • Графічний метод.

Для відокремлення коренів будують графік функції і знаходять точки перетину графіка з віссю абсцис та кінці відрізків ізоляції коренів. Часто р-ня (1) записують у вигляді і будують графіки ф-цій і , потім знаходять межі, в яких містяться абсциси точок перетину графіків функцій у1 та у2.

  • Аналітичний метод.

Ґрунтується на теоремі Больцмана-Коші: Якщо функція f(x) неперервна на [а;b] і набуває на кінцях цього відрізка значень протилежних знаків, тобто , то всередині відрізка [а;b]  хоча б один корінь рівняння, що . Якщо похідна f(x) зберігає сталий знак всередині відрізка [а;b], то рівняння на цьому відрізку має корінь, причому єдиний.

  • Метод послідовного перебору.

Нехай на [а;b] функція f(x) р-ня (1) задовольняє умові попередньої теореми, тоді, застосовуючи ЕОМ, можна відокремити всі корені р-ня (1) (крім кратних) цим методом. Для цього беруть початкове значення х=а, фіксований крок і обчислюють з-ня ф-ції f(x) у точках . На кінцях кожного з відрізків визначають знак функції f(x). Якщо знаки однакові, тобто , то на відрізку р-ня (1) не має кореня; якщо знаки функції протилежні, то на даному відрізку є корінь р-ня, значення якою є наближеним значення кореня з точністю , оскільки . Після цього переходить до наступного відрізка. Такни процес продовжують доти, поки правий кінець розглядуваного відрізка не досягає точки b. Зазначимо, цей метод пов’язаний з порівняно великим обсягом і не гарантує втрат коренів р-ня, особливо тоді, коли корені дуже близькі один до одного, а крок h недостатньо малий. У таких випадках треба провести новий підрахунок з дрібнішим кроком.

^ Уточнення коренів:

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

Позначимо через х* - точне з-ня кореня р-ня (1) на відрізку [а;b], а - його граничну абсолюту похибку. Суть методу в тому, що відрізок [а;b] ділять пополам точкою с=0,5(а+b) і обчислюють f(c). Якщо то х=с є точним значенням кореня. Якщо , але то - і значення х=с буде шуканим наближеним коренем. Якщо , але , тоді розглядають той з двох відрізків [а;с] і [с;b] , на кінцях якого функція f(x) набуває значень протилежних знаків. Позначимо цей відрізок 1;b1]. На відрізку 1;b1] ф-ція f(x) задовольняє умови попередньої теореми. Далі відрізок 1;b1] точкою с=0,5(а+b)ділять пополам і міркують так само, як і для відрізка [а;b]. В результаті процесу ділення відрізків пополам дістають послідовність вкладених відрізків [а;b], 1;b1]., 2;b2],..., n;bn],..., кожен з яких містить точне значення кореня х*. Довжина відрізка n;bn]=(b-a)/2n, тому . Звідси випливає, що для деякого п буде справедлива нерівність . Тоді буде наближеним значенням кореня х* з точністю e, тобто. При цьому абсолютна похибка знайденого кореня не перевищує e.


  • Метод простої ітерації.

В основі цього методу лежить принцип стискуючих відображень. Озн.1 Непорожня множина X елементів довільної природи називається метричним простором (МП), якщо будь-яким двом елементам х, у X поставлено у відповідність невід'ємне число р(х,у), яке задовольняє такі умови:

  1. ρ(х,у)=0 , коли х=у;

  2. ρ(х,у)=ρ(у,х) (аксіома симетрії);

  3. ρ(х,z) ρ(х,z)+р(у,z) для будь-яких х,у,zХ (аксіома трикутника).

Елементи множини X називають точками метричного простору, а дійсне число ρ(х,у) - відстанню між елементами (точками) х і у.

Метричний простір позначають R=(Х,ρ). Властивості 1-3 відстані ρ наз. аксіомами МП. Приклади МП:

  • множина дійсних чисел з відстанню ;

  • м-на n-вимірних векторів з дійсними координатами і відстанню

, де , є МП, який наз. n-вимірним евклідовим простором, його поз. Rn.

  • м-на n-вимірних векторів з відстаннює МП, який позн. .

  • -на n-вимірних векторів з відстанню, який позн. .

Озн.2 Точку х* довільного МП R наз. границею послідовності х(1)(2),...,х(к),... точок цього МП і записують або , якщо . Послідовність {x(k)} точок, що має границю, наз. збіжною.

Озн.3. Послідовність точок {x(k)} {k=1,2,…} МП R наз. фундаментальною, якщо для  числа 0  таке натуральне число , що дя всіх к і , тобто

.

^ Озн.4 МП R наз. повним, якщо в ньому кожна фундаментальна послідовність має границю.

Озн5. Якщо  таке додатне число <1, що для будь-яких х', х" Х виконується нерівність

то оператор U наз. оператором стиску, а відображення стискуючим.

Озн.6 Точка хХ наз. нерухомою точкою оператора U, якщо .

Для знаходження нерухомих точок оператора U застосовують метод послідовних наближень. При цьому беруть  точку хоХ і послідовно знаходять .

В результаті дістають послідовність , яку називають послідовністю наближень, або ітераційною послідовністю.

Для операторів стиску справедлива така теорема Банаха про нерухому точку.

Теорема1. (принцип стискуючих відображень). Якщо оператор стиску U відображає повний МП R у себе, то він має єдину нерухому точку, яку можна дістати методом послідовних наближень при будь-якій початковій точці хо R.

А тепер обґрунтуємо сам метод.

Нехай задано рівняння (1), де f(x) - неперервна ф-ція. Щоб, знайти дійсні корені цього р-ня, замінимо його рівносильним:

(2)

Якщо на відрізку [а;b] є МП:  х12[а;b], в якому   нерухома точка х* р-ня (2): і можемо побудувати послідовність {} х*.

Збіжність послідовності {хк} забезпечується відповідним вибором ф-ції і початкового наближення х0. Вибираючи по-різному ф-цію , можна дістати різні ітераційні методи розв'язання р-ня (2).

Вибираючи деяке початкове наближення х0 і послідовно обчислюють наступні наближення: (3), к=1,2,...

Теорема2. Нехай рівняння має корінь х* і в деякому околі цього кореня ф-ція задовольняє умову Ліпшиця (4), де 0<q<1. Тоді для  х0 R послідовність {хк}, обчислюють за формулою (З), збігається до кореня х*, причому швидкість збіжності характеризується нерівністю (5).

Доведення.

Множина точок відрізка R з відстанню у є повним МП. Ф-ція відображає відрізок R у самого себе. Справді, якщо хR, то також належатиме R, оскільки,

Доведемо, що від-ня стискуюче.

Справді, для х R і х R



з принципу стискуючих від-нь  , що в околі R  одна і тільки одна нерухома точка , така, що . Цю точку можна знайти як границю послідовності , де к=1,2,..., х0 R.

З умови Ліпшиця маємо:

тобто

Теорему доведено.

Отже, послідовність {хк} збігається до кореня х* із швидкістю геометричної прогресії із знаменником q. Чим менше число q, тим швидше збігається послідовність {хк}, тобто тим менше число кроків треба виконати для того, щоб дістати наближене значення кореня із наперед заданою граничною абсолютною похибкою ε. Швидкість збіжності залежить також від вибору початкового наближення хо. Чим ближче до кореня х* вибрано хо, тим швидше буде знайдено результат. Умова Ліпшиця з константою буде виконана для функції φ(х) на відрізку R, якщо на Rφ(х), причому .

Цей метод має простий геометричний зміст. Побудуємо графіки ф-цій у=х і у=(х) Абсциса точки перетину графіків цих ф-цій є коренем рі-ня (2). На рис1. зображені випадки:

















Якщо , то послідовності наближення хк збігаються до кореня х* , якщо , то послід. наближ. віддаляються від нього.


  • Метод Ньютона.

Нехай р-ня на відрізку [а;b] має ізольований корінь х*, тобто , а ф-ції і неперервні і зберігають знак на [а;b]. Нехай хк к-е наближення кореня. Розкладемо в рад Тейлора в околі точки хк.



Замість р-ня розглядатимемо р-ня

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

Взявши знайдене значення х за наступне наближення, матимемо

(3) .

Формула (3) визначає метод Ньютона. Він має просту геометричну інтерпретацію. Значення э абсцисою точки перетину дотичної до кривої в точці

Тому цей метод ще наз. методом дотичних.

З рис2 видно, що послідовні наближення збігаються до кореня х* монотонно.







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

Метод Ньютона є методом послідовних наближень , де ф-ція . Достатні умови збіжності методу Ньютона дає така теорема: Нехай на відрізку [а;b] функція f(х) має неперервні із сталими знаками похідні f(х)0, f(х)0 і . Тоді  такий окіл R[а;b] кореня х* р-ня f (х)= 0, що для  послідовність {хк}, обчислена за формулою (3), збігається до кореня х*.

  • Метод січних.

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



Підставивши значення у формулу (3), знайдемо

(4)

Метод, що визначається ф-лою(4), наз. методом січних. Геометрично наближення хк+1 дістають як абсцису точки перетину осі Ох і січної, що проходить через точки к-1,f(хк-1)) і к,f(хк)) кривої у=f(х).



Алгоритм методу січних починається із задання двох початкових наближень хо і х1, які вибирають на відрізку ізоляції кореня х*. Тому складність цього методу полягає в знаходженні таких хо і х1, досить близьких до х*, щоб метод був збіжним.

Якщо похідна f(х) мало змінюється на [а;b] то кількість обчислень у методі Ньютона можна зменшити, коли значення похідних fк) у точках хк, к=1,2,... замінити значенням f0) у точці хо. Тоді формула (3) набере вигляду:



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



  • Метод хорд.

Цей метод - один з поширених ітераційних методів. Його ще наз. методом лінійного інтерполювання, методом пропорційних частин, або методом хибного положення.

Нехай задано рівняння f(х)=0, де f(х) на відрізку [а;b] має неперервні похідні 1-го й 2-го порядків, які зберігають сталі знаки на цьому відрізку, і , тобто корінь х* р-ня відокремлений на [а;b].

Ідея методу хорд в тому, що на досить малому відрізку дуга кривої у=f(х) замінюється хордою і абсциса точки перетину хорди з віссю Ох є наближеним зн-м кореня.







У загальному випадку нерухомим буде той кінець відрізка ізоляції кореня, в якому знак ф-ції f(х) збігається із знаком другої похідної, а за початкове наближення хо можна взяти точку відрізка [а;b], в якій . Отже, метод хорд можна записати у вигляді:

(5)

де

з формули (5) видно, що м.ітерації , в якому



А р-ня на відрізку [а;b] рівносильне р-ню =0.

Достатні умови збіжності м. хорд дає така теорема: Нехай на відрізку [а;b] функція f(х) має неперервна разом із своїми похідними до 2-го порядку включно, причому , а похідні f(х), f(х) зберігають сталі знаки на [а;b]. Тоді  такий окіл кореня х* р-ня f (х)= 0, що для  початкового наближення хо з цього околу послідовність {хк}, обчислена за формулою (5), збігається до кореня х*.

  • Комбінований метод дотичних і хорд.

Характерна особливість методів дотичних і хорд та, що послідовності їх наближень монотонні. Причому, якщо для даного рівняння послідовність наближень методу хорд монотонно спадна, то послідовність наближень методу дотичних - монотонно зростаюча, і навпаки. Одночасне застосування цих методів дає змогу наближатися до кореня рівняння з двох боків, дістаючи наближення з недостачею і надлишком.

Розглянемо р-ня f(х)=0 корінь якого х* [а;b]. Нехай н-д f(x)>0, f(x)>0, f(a)<0, f(b)>0.



У даному випадку за початкове наближення в методі хорд вибирають точку х=а, а в методі дотичних- точку b. На відрізку [а;b] застосовують метод дотичних і хорд (спочатку дотичних, а потім хорд). У результаті дістають нові наближення а1, b1, і початковий відрізок ізоляції кореня звузився. Для знаходження нових наближень застосовують метод дотичних і хорд уже на відрізку 1;b1]. У результаті дістають наближення а2, b2 відповідно, причому 2;b2]1;b1] [а;b]. Такий процес продовжують доти, поки довжина відрізка к;bк] стане меншою або дорівнюватиме величині 2, де  - наперед задана точність кореня.

За шукане значення кореня беруть півсуму наближень ак і bк, тобто , а модуль їх піврізниці дасть граничну абсолютну похибку наближеного кореня, тобто



Зазначимо, що на кожному кроці комбінованого методу за нерухомий кінець с у формулі методу хорд треба брати наближення, обчислене на цьому самому кроці за формулою дотичних.

Формули комбінованого методу дотичних і хорд мають вигляд:



За початкове наближення b0 у формулі (6) методу дотичних беруть той з кінців відрізка [а;b], в якому значення функції f(х) і її другої похідної мають однакові знаки, тоді протилежний кінець відрізка [а;b] беруть за початкове наближення а0 у формулі (7) методу хорд.

Завдяки своєрідній комбінації методів дотичних і хорд комбінований метод має вищу швидкість збіжності, ніж методи хорд і дотичних окремо взяті.


Скачать файл (350 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации