Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Методи Ньютона, Гауса, Фадєєва-Левер’є, Адамса-Мултона та інші (шпора)

План:

1. Метод поділу відрізку навпіл

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

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

4. Метод хорд

5. Комбінований метод

6. Метод Гауса

7. Многочлени ЧебишеваЧисельне диференціювання

8. Метод Фадєєва-Левер'є

9. Метод най скорішого спуску

10. Лінійне програмування

11. Постановка задачі чисельного інтегрування задачі Коші

12. Метод Адамса-Мултона


 

Метод поділу відрізку навпіл передбачає послідовне обчислення значень функції в ряді точок. Нехай потрібно знайти корінь рівняння який знаходиться на відрізку . У випадку єдиного кореня на вказаному відрізку буде виконуватись умова

. .

У залежності від знаку функції в точці новий відрізок знаходження кореня встановлюється за допомогою наступного правила:

похибки задаються виразами:

.

 

Метод простої ітерації полягає в тому, що рівняння записують у канонічному вигляді: ,

а ітерації здійснюються за правилом

Точність на сусідніх ітераціях

, .

достатня умова збіжності методу простої ітерації, а саме, буде менше за умови

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

У випадку, коли в околі кореня похідна задовольняє умову похибки і будуть мати однакові знаки і збіжність до буде монотонною – -збіжний коливається навколо х*

, -розбіжний і наближення буде знаходитись далі від розв'язку ніж ,

, - збіжність квадратична

похибка ,

.

Звідки отримуємо оцінку

, (2.9)

де .

Метод Ньютона Для прискорення збіжності ітераційного процесу методу простої ітерації функцію можна вибрати у вигляді

.

Достатні умови збіжності методу Ньютона дає така теорема.

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

Для чого в околі кореня рівняння розкладемо функцію в ряд Тейлора з урахуванням третього члена, що визначає нелінійність апроксимації:

, . .

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

, де .

Таким чином метод Ньютона має квадратичну збіжність

, , де .

Метод Ньютона для кратних коренів

,

Застосування методу Ньютона для знаходження

екстремальних точок функції

,

Метод хорд

Нехай потрібно розв'язати рівняння (2.1), яке має єдиний корінь на інтервалі , для якого виконується умова (рис. 13). Для побудови ітераційної формули методу хорд запишемо рівняння прямої (хорди), яка проходить через дві точки і :

Поклавши в одержаному рівнянні , дістанемо формулу для обчислення наближень за методом хорд вигляду:

, де – нерухома точка.

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

, де , тому що існує оцінка .

Комбінований метод Процес закінчується, коли .

Кінцеве наближення обчислюється за формулою

,

де і – наближення кореня, отримані методами Ньютона та хорд.

Метод Гауса з вибром глн.елемента

, , .

Тоді системи (1) запишемо у вигляді

 

Метод виключення Гаусса, прийнято реалізовувати за два ходи: прямого і зворотного. На прямому ході, за допомогою еквівалентних перетворень, систему зводять до верхнього трикутного вигляду, а на зворотному ході, з одержаної системи знаходять, значення невідомих, тобто розв'язок системи.

Прямий хід методу Гаусса. Нехай . Тоді перше рівняння залишимо без зміни

 

і використаємо його для виключення невідомого із всіх рівнянь системи (5), починаючи з другого. Для виключення із другого рівняння додамо до нього перше, помножене на . Потім, помноживши перше рівння на і додамо результа до третього рівняння, також виключимо з нього і т.д. В результаті одержимо системи рівнянь вигляду

(7)

де .

Нехай . Тоді друге рівняння залишимо без зміни

, (8)

і використаємо його для виключення невідомого із всіх рівнянь системи (5), починаючи з третього. Для цього до третього і наступних рівняннь системи (7) додамо рівняння (8), помножене на . В результаті одержимо систему вигляду

(9)

де

Продовжуючи процес за даною схемою далі, на n-1-му кроці одержимо систему трикутного вигляду

(10)

На цьому закінчується прямий хід методу Гаусса.

Зворотний хід. На зворотному ході методу Гаусса знаходимо значення невідомих в оберненому порядку.

З останнього рівняння системи (10) маємо, що . Тоді з передостаннього рівняння системи (10) знаходимо: т.д. Нарешті з першого рівняння знаходимо: .

Основним обмеженням методу Гаусса є припущення про те, що всі ведучі елементи відмінні від нуля. Слід мати на увазі, що якщо якийсь ведучий елемент не дорівнює нулю, а просто близький до нього, то в процесі обчислень може відбутись значне накопичення похибок. У такому разі, як уже відмічалось, у відповідній системі достатньо буде переставити місцями (перенумерувати) рівняння для продовження процесу вилучення. Уникнути цього дозволяє метод Гаусса з вибором головного елемента.

Ідея методу Гаусса з вибором головного елемента полягає в тому, щоб на черговому кроці виключати ту невідому, коефіцієнт при якій найбільший за модулем. Отже, ведучим елементом тут вибирається найбільший за модулем елемент матриці. Тим самим, якщо , то в процесі обчислень не відбудеться ділення на нуль.

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

Інтерполювання Під час розв'язання багатьох задач обчислювальної математики часто доводиться заміняти одну функцію (відому, невідому або частково відому) близькою до неї функцією , яка має визначені властивості. Таку заміну однієї функції іншою називають інтерполюванням функції.

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

. (1)

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

, (2)

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

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

,

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

Канонічний поліном , (

де – деякі постійні коефіцієнти, які потрібно визначити з певних умов. У випадку побудови канонічного полінома, коефіцієнти , визначаються з умови , , яка зводиться до розв'язання системи лінійних алгебраїчних рівнянь.

(4)

Визначник системи (4) , який називають визначником Вандермонда,

,

Лагранжа Інтерполяційний многочлен шукатимемо у вигляді: (7)

де – многочлен степеня , що у вузлах інтерполяції задовольняє умови:

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

.

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

,

який називається інтерполяційним многочленом Лагранжа, а наближену рівність – інтерполяційною формулою Лагранжа.

.

Вирази , що є коефіцієнтами при у многочлені Лагранжа, називають коефіцієнтами Лагранжа.

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

Якщо ввести позначення , тоді для абсолютної похибки інтерполяційної формули Лагранжа в поточній точці , дістанемо оцінку , (18)

а на всьому відрізку : .

Многочлени Чебишева. Многочлени Чебишева , на відрізку визначаються формулою .

При маємо: .

Далі із тотожності

або

при одержимо

(21)

Чебишев довів, що величина має найменше значення, якщо вузлами інтерполювання є числа , де – нулі многочлена Чебишева . Вони дійсні різні, належать інтервалу і згущаються біля кінців інтервалу.

Доведено, що за такого вибору вузлів інтерполювання ,

а оцінка (18) має вигляд

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

Скінченими різницями першого порядку називають величини, що обчислюються за формулами:

(23)

Скінченими різницями другого порядку називають:

(24)

У загальному вигляді скінчені різниця -го порядку обчислюється за формулою (25)

Розділені різниці першого порядку для у вузлах інтерполяції мають вигляд: Чисельне диференціювання До чисельного диференціювання функцій вдаються тоді, коли функція задана таблично, а тому методи диференціального числення просто незастосовні, або коли функція задана досить складним аналітичним виразом і тому обчислення похідних пов'язане із значними труднощами, хоча для сучасних пакетів це не проблема. У цьому випадку користуються наближеним диференціюванням

Інтегрування Якщо функція є неперервною на відрізку і відома її первісна , то для обчислення визначеного інтеграла можна використати формулу Ньютона-Лейбніца . ,де , – сталі. Наведена формула називається квадратурною формулою, точки – вузлами квадратурної формули, а – коефіцієнтами квадратурної формули.

Як правило, рівність (1) наближена. Різницю між визначеним інтегралом і квадратурною сумою ,

називають залишковим членом, або похибкою квадратурної формули (1).

. (9)

Коефіцієнти називаються коефіцієнтами Котеса. Квадратурна формула Ньютона-Котеса при цьому має вигляд

Узагальнені формули прямокутників одержуються з формул (15)-(17) шляхом сумування по від 0 до , а саме:

– формула лівих прямокутників,

– формула правих прямокутників,

– формула середніх прямокутників

лівих прямокутників остаточно набирає вигляду Правих

середніх прямокутників

- трапеції

узагальнену формулу Сімпсона (парабол) у вигляді

 

залишкові члени формул лівих і правих прямокутників відносно мають перший порядок: , середніх прямокутників і трапецій – другий: , а Сімпсона – четвертий: . Квадратурна формула вважається тим точнішою, чим більший порядок її залишкового члена . З розглянутих квадратурних формул найточнішою є формула Сімпсона, а найменш точними – формули лівих і правих прямокутників.

-правило Рунне -екстраполяція за Річардсоном

Узагальнена квадратурна формула

р

 

 

Лівих і правих прямокутників

1

 

 

Середніх прямокутників і трапецій

2

 

 

Сімпсона

4

 

 

Метод Фадєєва-Левер'єДля обчислення коефіцієнтів характеристичного рівняння крім прямого розкриття самого визначника існує декілька методів, серед яких виділяється метод Фадєєва-Левер'є, за допомогою якого обчислюються:

· коефіцієнти характеристичного полінома

; (2)

· обернена матриця ;

· резольвента матриці .

Метод Фадєєва-Левер'є базується на результатах обчислення слідів матриці А і добутків матриць , де – коефіцієнти чисельника резольвенти матриці (4). Коефіцієнти чисельника і знаменника виразу (4) визначаються ітераційно (спочатку коефіцієнти чисельника , а потім коефіцієнти знаменника відповідно до наведеного нижче алгоритму:

, ;

, ,

де Е – одинична матриця, – слід матриці. Умова перевірки правильності виконання алгоритму має вигляд .

Метод Крилова, який базується на відомій теоремі Келі-Гамільтона, яка стверджує, що будь-яка матриця А задовольняє своє характеристичне рівняння . (5)

Якщо рівняння (5) помножити на довільний вектор , то можна отримати такий запис: ,

де вектори обчислюються за формулами:

(7)

На основі рівняння (7) формуємо систему лінійних алгебраїчних рівнянь для знаходження коефіцієнтів характеристичного рівняння матриці:

. (8)

Якщо система (8) виявиться виродженою, то необхідно замінити початковий вектор , який для зручності зазвичай обирають як .

Метод Ньютона Розглянемо нелінійну систему

 

Якщо ввести -вимірні вектори , то систему можна записати у вигляді . , де – похибка кореня. .

Якщо функція непевно-диференційована в деякій області, якій належить , то , де

.

Матриця називається матрицею Якобі.

Рівняння (5) представляє собою лінійну систему, де в ролі невідомих виступають поправки , а головна матриця – : .

Припустивши, що визначник матриці відмінний від нуля, одержимо

. (7)

Замінивши в (3) на дістанемо формулу Ньютона:

, (8)

де за можна взяти грубе значення кореня. При практичному застосуванні метода для розв'язання нелінійних систем (2) обчислення за формулою (8) припиняються, коли

Метод най скорішого спуску Нехай маємо нелінійну систему

(1)

або в матричному вигляді , (2)

де – вектор, – вектор функція.

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

. градієнт функції

, де

, (7)

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

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

(8)

з дійсною матрицею і стовпцем вільних членів .

Тоді і .На основі цього для знаходження розв'язку системи (8) одержуємо ітераційний процес: ,де – нев'язка вектора

Лінійне програмування У загальному вигляді математична постановка екстремальної задачі полягає у визначенні найбільшого або найменшого значення цільової функції

f=f(x1, x2, ..., xn) при умовахgi(x1, x2, ..., xn) £ bi (i=1,2,...,m), де f і gi – задані функції, а bi – деякі дійсні числа.

Розрізняють три математичні моделі задачі лінійного програмування: загальної, стандартної і канонічної.

1. Математичну модель загальної задачі лінійного програмування можна подати у такому вигляді: знайти такі числові значення змінних x1, x2, ... , xn, які задовольняють систему обмежень

(6)

умову невідємності x1 ³ 0, x2 ³ 0, ... , xn ³ 0, перетворюють в екстремум (максимум або мінімум) цільову функцію

 

Коли канонічна то ставимо = , стандартна <=

Постановка задачі Коші. Задача Коші полягає в тому, щоб знайти розв'язок диференціального рівняння ,

який задовольняє початкову умову .

Геометрично задача Коші полягає у відшуканні такої інтегральної кривої рівняння (1), яка проходить через точку (рис. 1).

0

y0

x

y

x0

M0

y=y(x)

2. Постановка задачі чисельного інтегрування задачі Коші. Нехай на відрізку треба знайти чисельний розв'язок задачі Коші (1)-(2). Для цього відрізок поділимо на n (для простоти) рівних частин точками , де , де , .

Величину h називають кроком чисельного інтегрування задачі Коші.

Розв'язати задачу (1)-(2) чисельно – це означає, що для заданої послідовності точок незалежної змінної х і числа , треба знайти числову послідовність , яка є наближеним розв'язком заданої задачі Коші.

Якщо наближений розв'язок задачі Коші в точці відомий, то, проінтегрувавши рівняння (1) в межах від до , знайдемо його розв'язок в точці за формулою .

Метод А=Б У загальному випадку багатокрокові методи можна подати у вигляді

(1)

Або ,

де , – значення похідної шуканої функції, – деякі невідомі коефіцієнти, які знаходяться з певних умов. Ідея цього підходу полягає в тому, що якщо задача Коші має точний розв'язок у вигляді полінома степені k

,

де – константи, то за допомогою формули (1) цей розв'язок можна знайти точно. Метод Адамса-Башфорта є явним багатокроковим методом, який одержується з формули (1) при умові, що

.

Тоді формула (1) набуде вигляду

або . (2)

Невідомі коефіцієнти , які входять в формулу (2) будемо шукати з умови, що формула (2) є точною для всіх поліноміальних розв'язків, степінь яких не перевищує k. За такі поліноми візьмемо поліноми вигляду

. Використовуючи поліноми (3) побудуємо систему лінійних алгебраїчних рівнянь для знаходження невідомих коефіцієнтів наступним чином. Спочатку для поліномів зростаючого порядку обчислюємо значення функції та її похідної:

 

Одержані значення функцій та похідних підставимо в формулу (2), в результаті чого одержимо систему:

звідки ;

другого розділити відповідно на 2, 3,…, k, то одержану систему можна записати у матричному вигляді

.

Метод Адамса-Мултона є неявним багатокроковим методом, який одержується з формули (1) при умові, що .

Тоді формула (1) набуде вигляду

(6)

або .

Для знаходження невідомих коефіцієнтів використаємо функції (4):

звідки ;

 

Якщо кожне з рівнянь, починаючи з другого розділити відповідно на 2, 3,…, k, то одержану систему можна записати у матричному вигляді





Реферат на тему: Методи Ньютона, Гауса, Фадєєва-Левер’є, Адамса-Мултона та інші (шпора)


Схожі реферати



5ka.at.ua © 2010 - 2016. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.