Чисельні методи в мікро- та наносистемній техніці

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Вінницький національний технічний університет

Факультет інфокомунікацій, радіоелектроніки та наносистем

Кафедра електроніки та наносистем

Самостійна робота

студента з предмету «Чисельні методи в мікро- та наносистемній техніці»

Виконав:

Бровко Дмитро, МНТ -18б

Перевірив:

к.т.н., доц. Жагловська О. М.

Вінниця

2019

Зміст

1. Нелінійні задачі: метод простої ітерації. Метод Ньютона для системи двох нелінійних рівнянь. Метод Ньютона для системи з n рівнянь з n невідомими

2. Задачі лінійної алгебри: обчислення визначників та елементів оберненої матриці методом Гаусса. Метод квадратних коренів та Халецького

3. Методи розв'язання ЗДР: метод Адамса. Метод Мілна

4. Методи розв'язання диференціальних рівнянь в частинних похідних: метод сіток. Еліптичні рівняння ( задача Діріхле для рівняння Лапласа). Параболічні рівняння ( рівняння теплопередачі). Гіперболічні рівняння

5. Чисельне розв'язування інтегральних рівнянь: розв'язування рівнянь Фредгольма методом кінцевих сум

6. Екстраполяція та обернене інтерполювання. Сплайн-інтерполяція. Апроксимація

7. Інтерполяційні формули Гаусса, Стірлінга, Бесселя

8. Квадратурні формули Чебишева та Гаусса

9. Правило 3/8 для обчислення визначених інтегралів

10. Чисельні методи оптимізації

1. Нелінійні задачі: метод простої ітерації. Метод Ньютона для системи двох нелінійних рівнянь. Метод Ньютона для системи з n рівнянь з n невідомими

Метод простої ітерації полягає в тому, що рівняння f(x) = 0 попередньо приводиться до канонічного вигляду:

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

причому задається початкове наближення х0.

Якщо процес обчислень збігається до розв'язку а рівняння (4.1), тобто а = ц(а), то в разі припущення, що функція ф(х) визначена і неперервна на відрізку, де треба знайти корінь, можна встановити взаємозв'язок між похибками обчислень на двох сусідніх ітераціях:

Із виразу (4.6) випливає, що достатньою умовою збіжності методу простої ітерації, за якої |еn+і| буде менше |еn|, є умова

Умова збіжності (4.7) ітерацій під час розв'язування нелінійних рівнянь є, власне кажучи, узагальненням достатньої умови збіжності ітераційного процесу під час розв'язання систем лінійних рівнянь, отриманої в розділі З у вигляді М < 1, якщо покласти | ц '(х*)| = М. Чим менше значення | ц '(x*)|, тим швидше збігається ітераційний процес.

У випадку, коли ц '(x*>0) , похибки еn+і і єn будуть мати однакові знаки і збіжність хn+1 до а буде монотонною. Якщо ж ц '(x*) < 0, похибки еn+1 і еn матимуть різні знаки і наближення хn+1 буде збігатися до а, коливаючись біля а. Коли ц '(x*)>1, похибка еn+1 за абсолютним значенням більше еn, і наближення хn+1 буде відстояти від розв'язку а далі, ніж хn. Розв'язок а мов «відштовхує» наближення хn, близькі до нього, тому не буде збіжності послідовності хn до а.

Можливі варіанти збіжності ітерацій: а - монотонна збіжність; б - коливальна збіжність; в - монотонна розбіжність; - коливальна розбіжність

чисельний нелінійний рівняння формула

Особливим випадком є умова, коли ц'(x*) = 0, і збіжність ітерацій замість лінійної, обумовленої виразом (4.6), стає нелінійною, зокрема квадратичною, як це буде показано в наступному розділі. Оцінювання глобальної похибки |хn+1 - а| зручно виконувати на основі значень, локальної похибки, тобто за значеннями наближень. Для цього додамо до правої частини виразу (4.6) і віднімемо від неї хn+1.

Після зведення подібних членів одержимо:

| ц'(x*)| = M.

Якщо обчислювати похибку від початкового значення х0, то для поточної похибки на n-й ітерації згідно з виразом (4.6) справедливе співвідношення

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

Для прискорення збіжності ітераційного процесу чергове наближення xn+1 може бути визначене за формулою, де враховано як значення самої функції f(xn), так і швидкість її зміни f'(xn):



Ітераційний процес методу Ньютона

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

f(xn+1) = f(xn) + (xn+1 - xn)f'(xn) = 0,

Ефективність процедури (4.9) залежить від початкового наближення x0. наприклад, воно може збігатися з одним із кінців інтервалу ізоляції кореня [a,b], для якого виконується умова f(x)*f''(x) > 0.

2. Задачі лінійної алгебри: обчислення визначників та елементів оберненої матриці методом Гаусса. Метод квадратних коренів та Холецького

Для обчислення визначників матриць застосовують два підходи:

- рекурсивний розрахунок за допомогою розкладення по рядку чи стовпцю;

- обчислення на основі прямого ходу метода Гаусса.

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

Таким чином, обчислення одного визначника n-го порядку зводиться до розрахунку n визначників порядку n-1. Реалізується даний спосіб за допомогою рекурсії.

Рекурсивний спосіб зручно застосовувати по відношенню до рядків чи стовпців, що мають велику кількість нульових елементів. Якщо ж нульових елементів у матриці немає або дуже мало, то застосування цього способу є вкрай не ефективним. Для визначника n порядку доведеться розрахувати n!/2 визначників другого порядку.

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

Для обчислення визначника використовується алгоритм побудови послідовності матриць А?А1?А2?…?Аn прямого ходу метода Гаусса з тією відмінністю, що при перестановці рядків чи стовпців знак визначника змінюється на протилежний. Значення визначника розраховується по формулі:

,

де m - кількість перестановок.

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

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

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

Перемноживши і , отримаємо деяку матрицю, яку прирівнюємо до матриці . В результаті отримаємо формули, для знаходження невідомих :

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



Далі переходимо до другого етапу (обернений хід методу квадратного кореня). З першої системи формули (3), послідовно знаходимо невідомі , ведучи розрахунки «зверху вниз» за наступними формулами:

Після цього, з другої системи формули (3), за знайденими значеннями невідомих , ведучи розрахунки «знизу вверх», визначаємо невідомі :

Метод квадратного кореня більш зручний і економічний у порівнянні з методом Гаусса. Він легко програмується. Алгоритм цього методу заснований на формулах (3), (4), (5). Також слід відмітити, що метод квадратного кореня можна також використовувати і для знаходження визначника матриці. Для цього використовують наступну формулу: . Тобто, для обчислення визначника достатньо скористатись розрахунковими формулами прямого ходу методу квадратного кореня.

Метод Холецького використовується для розв'язання систем лінійних рівнянь з симетричними додатними матрицями ( aij = aji ). У цих випадках приймається,

що ukk = lkk , usj = ljs.

З добутку двох матриць:



За правилами матричного множення знаходимо співвідношення між елементами матриць:

З формули

Тому перетворення Холецького для симетричних матриць набуває такого вигляду:



3. Методи розв'язання ЗДР: метод Адамса. Метод Мілна

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

Стартові значення можна одержати декількома способами. Дж. К. Адамс обчислював їх за допомогою розкладання точного розв'язку в ряд Тейлора. Інший спосіб полягає у використанні якого-небудь однокрокового методу, наприклад, Рунге-Кутта. Стартові значення часто також обчислюють методами Адамса низького порядку з дуже малим кроком.

Розглянемо чисельні методи розв'язання задачі Коші (8.1)-(8.2), які можуть бути задані формулою

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

З класу (8.25) виділимо багатокрокові методи вигляду

 ,

застосовувані на сітці з постійним кроком

Різниця між найбільшим і найменшим значеннями індексу невідомої функції уn, що входить у рівняння (8.26), дорівнює . Тому співвідношення (8.26) є різницевим рівнянням -го порядку, загальний розв'язок якого залежить від параметрів. Щоб виділити єдиний розв'язок цього рівняння, необхідно задати додаткових умов на функцію уп. Цими додатковими умовами є значення функції уn при n = 0,1,... , -1:

які передбачаються відомими.

Використовуючи значення, з рівняння (8.26) при n=0 можна знайти , потім, використовуючи значення і покладаючи в (8.26) n =1, знайти і т.д. Таким чином, даний метод чисельного розв'язання диференціального рівняння полягає в розв'язанні різницевої задачі Коші для різницевого рівняння (8.26) і початкових умов (8.28).

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

Виведемо групу явних багатокрокових формул. Для точок сітки введемо позначення і припустимо, що нам відомі числові наближені значення точного розв'язку задачі (8.1)-(8.2).

З диференціального рівняння випливає

До правої частини (8.29) входить шуканий розв'язок . Але оскільки нам відомі його наближені значення , то ми маємо також і величини

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

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



де коефіцієнти задовольняють рівність

Числові значення цих коефіцієнтів наведені в таблиці 8.1.

Окремі випадки формули (8.32).

Для , виразивши різниці назад через , одержимо такі формули:

Зауваження. Для ми маємо явний метод Ейлера.

0 1 2 3 4 5 6 7 8

1

Похибка апроксимації явного двокрокового методу Адамса має другий порядок.

Неявний двокроковий метод Адамса виглядає так:



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

Нехай потрібно знайти розв'язок задачі Коші:

Для цього, виберемо деякий крок , і покладемо:

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

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

1. Використовуючи формулу (2), обчислюємо прогнозоване значення :



2. Дане прогнозоване значення підставляємо в диференціальне рівняння (1), в результаті отримуємо відповідне значення .

3. На наступному кроці проводимо корекцію прогнозованого значення за наступною формулою:

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

4. Методи розв'язання диференціальних рівнянь в частинних похідних: Метод сіток. Еліптичні рівняння (задача Діріхле для рівняння Лапласа). Параболічні рівняння (рівняння теплопередачі). Гіперболічні рівняння

Розглянемо метод сіток для розв'язування диференціальних рівнянь такого типу:

де - функції змінних х та у.

- одного знаку

Задача1: під нею розуміють розв`язок задачі Коші яка полягає в відшуканні розв`язку задачі (1) в області , який задовольняє:



Задача2: Розв`язок змішаної задачі яка полягає в відшуканні розв`язку рівняння (1) в області:

,

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

і деякі умови на прямих:

Розглядають три типи умов на прямих, що обмежують область:

1)

2)

3)

Аналогічно так само на прямій

- задані функції.

Розглянемо метод сіток:

Для кожного внутрішнього вузла диференціального рівняння (1) замінимо різницевим рівнянням замінивши відповідні похідні наступним способом :

Підставимо цю заміну в рівняння (1) маємо:

 (7)

(8)

З останнього рівняння (8) видно, що знаючи значення розв`язку в вузлах і рядка в усіх вузлах рядка. Тому для розв`язку задачі необхідно знати значення в усіх вузлах рядків і .

Ці значення шукають з початкових умов з одним з наступних способів:

1) Початкові умови:

2) Введемо додатковий (-1) рядок. Значення на цьому рядку нас не цікавлять. Але початкові умови:

Підставивши (8) маємо:

Таким чином значення розв`язку на перших двох рядках будуть знайдені за формулою:

Значення розв`язку на рядках шукають за (9) або (8`).

Зауваження: У випадку рівняння

і квадратичної сітки , різницеве рівняння набуде вигляду:

Для обчислення значення на перших двох рядках отримаємо наступне:

1)

2)

Будемо вважати, що у розв`язку існує до четвертого порядку.

Використавши розклад в ряд Тейлора аналогічно до еліптичних рівнянь отримаємо:

Позначивши

(12)

Похибки апроксимації початкових умов.

У випадку формул (8`) перша умова похибки не дає , а друга умова дає похибку:

До еліптичних рівнянь (elliptic equations) приводиться багато різних фізичних задач: розрахунок напружень, які виникають при пружному скруті довгого циліндричного стрижня; розподіл електричних напруг на площині, що проводить струм; задача про стаціонарні течії тепла в двовимірному тілі. Часто виникає необхідність розв'язання таких задач і в теорії автоматичного керування. Більшість еліптичних рівнянь описується рівнянням Пуассона або його окремим випадком - рівнянням Лапласа.

Розглянемо класичну задачу Діріхле для рівняння Лапласа в прямокутній області, яка формулюється таким чином: знайти неперервну функцію f(x,y), яка задовольняє всередині прямокутної області рівняння Лапласа:

і приймає на границі області задані значення:

x=0; f (0,y) = f1 (y),

x=a; f (a,y) = f2 (y),

y=0; f (x,0) = f3 (x),

y=b; f (x,b) = f4 (x).

Введемо в області розв'язання двовимірну сітку з кроком h по осі x і l по осі y. Тоді, користуючись прийнятими в попередніх розділах позначеннями і апроксимуючи рівняння Лапласа різницевим рівнянням, отримаємо таку систему лінійних рівнянь (приймемо для спрощення l=h):

(5.2)

i=1,2,…,n-1; j=1,…,m-1.

Ця система рівнянь має велику кількість нульових елементів і задовольняє умові збіжності при використанні ітераційних методів. Найбільше використання для розв'язання таких систем знайшов метод Гаусса - Зейделя, який, коли застосовується до еліптичних різницевих рівнянь, називається методом Лібмана або методом послідовних зміщень. Порядок ітерацій можна простежити, переписавши систему ( 5.2. ) у вигляді:



де верхніми індексами позначено порядковий номер ітерації: m - попередня, m+1 - наступна.

Зазвичай вважають для всіх i, j. Система рівнянь легко розв'язується на ЕОМ. Взагалі кажучи, будь-які еліптичні рівняння, які не містять, зводяться до систем різницевих рівнянь, які можна розв'язувати як методом Лібмана, так і іншими ітераційними методами (Якобі, послідовної верхньої релаксації та ін.), оскільки для них виконуються умови збіжності. Для еліптичних рівнянь, які містять в загальному вигляді, питання про збіжність ітераційних методів не має теоретичного розв'язку і необхідно розглядати отриману систему рівнянь в кожному конкретному випадку.

Прикладом задачі, яка приводить до параболічного рівняння (parabolic equation) в частинних похідних, є задача про теплопередачу по довгому стрижню. Вона описується рівнянням теплопередачі (або дифузії).

Задача полягає у знаходженні f (x, t), яка задовольняє в області ={(x, t) 0 x a, 0 t T } рівняння



Початкові

f (x, 0)=f0 (x)

і граничні умови першого роду

Заміна змінних t = k t приводить рівняння до вигляду

тому надалі будемо вважати k=1.

Можливі два варіанти отримання різницевого рівняння на сітці з кроком h по x та по t (рисунок 5.4).

Варіант з апроксимацією на чотириточковому шаблоні (рисунок 5.4, а) приводить до неявної двошарової різницевої схеми



Ця схема доповнена рівняннями, отриманими з крайових умов

зводить задачу до розв'язання до системи рівнянь, які мають стійкий розв'язок при будь-яких значеннях r.

Варіант з апроксимацією на чотириточковому шаблоні (рисунок 5.5, б) призводить до явної двошарової системи

Ця схема стійка тільки при r0,5, що приводить до необхідності проводити обчислення з дуже малим кроком по t, який обмежує швидкодію і вимагає більших витрат часу ЕОМ. Тому для параболічних рівнянь більш широке розповсюдження отримала неявна схема.

5. Чисельне розв'язування інтегральних рівнянь: розв'язування рівнянь Фредгольма методом кінцевих сум.

6. Екстраполяція та обернене інтерполювання. Сплайн-інтерполяція. Апроксимація

Екстраполяція -- отримання значень f(x) при х, що не належить відрізку [a, b], на якому задана функція. Вона також здійснюється за формулами інтерполяції, але із значно більшою похибкою. Для плавних f(x) екстраполяція доцільна при х, що виходить за вказані межі не більше, ніж на половину кроку сітки. У MathCad існує функція predict(y,m,n) - для передбачення вектора, що екстраполює вибірку даних, де у - вектор дійсних значень, через рівні проміжки значень аргументу; m - кількість послідовних елементів вектора у, по яким будується екстраполяція; n - кількість елементів вектора передбачень.

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

Пакет MathCad пропонує для лінійної інтерполяціїфункцію linterp(Х,Y,xp), (xp -- довільна координата, або масив точок вектора X), функція здійснює лінійну інтерполяцію на основі векторів значень Х та Y. Лінійна інтерполяція полягає в визначенні прямих ліній залежності Y(Х) між точками даних, на основі яких обчислюються інтерпольовані значення.

Багатоінтервальна інтерполяція полягає в інтерполяції f(x) в ряді часткових інтервалів (обмежених двома вузлами або групою вузлів) окремими поліномами невисокого степеня. Сплайн-інтерполяція є спеціальною різновидністю багатоінтервальної інтерполяції, при якій поліном, що інтерполює забезпечує не тільки рівність g(x) = уі у вузлах інтерполяції, але й неперервність заданої кількості перших похідних на границях часткових інтервалів. Математично сплайн це спеціальний многочлен, який приймає у вузлах значення g(x) = yi = y(xi) і забезпечує в них неперервність першої та другої похідних.

Для сплайн-інтерполяціїпакет підтримує чотири вбудованих функції: lspline, pspline, cspline та interp. Сплайн-інтерполяція реалізується у два етапи:

- на першому етапі використовується одна з функцій, яка формує вектор других похідних S:=lspline(X,Y) або функції: pspline, cspline. Три вказані функції відповідають трьом різним типам кривих, які використовуються для інтерполяції на відрізках між двома сусідніми точками Х -- пряма лінія, парабола, кубічна парабола;

- на другому етапі використовується функція interp(S,X,Y,xp), аргументами якої є чотири значення: вектор S других похідних, вектори даних Х, Y та координата xp точки інтерполяції. Кубічна сплайн-інтерполяція відповідає з'єднанню заданих пар точок [Xi, Y(Xi)] та [Xi+1, Y(Xi+1)] плавною кривою, тип якої визначається згідно функції, обраної на першому етапі інтерполяції.

Отже, інтерполяція дозволяє достатньо просто апроксимувати емпіричні залежності. Однак точність такої апроксимації гарантована лише в обмеженому інтервалі декількох кроків при рівномірній сітці, а при нерівномірній -- лише в малому околі вузла інтерполяції. При інтерполяції ми прирівнюємо значення P(x) та у(х) у вузлах. Якщо у(хі) визначені не точно, обтяжені похибками, то точне прирівнювання недоцільне. В подібних випадках краще наближати функцію не по точках, а в середньому. Таке наближення називається середньоквадратичним, а метод, за яким визначаються параметри апроксимуючої функції, називається методом найменших квадратів (МНК).

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

Емпіричну формулу, зазвичай, вибирають із формул визначеного типу, наприклад, y = ax + b, y = aebx + c, y = a + hsin(щx + ц). Вибір того чи іншого типу формул обумовлений, в першу чергу, фізичною природою даних, що вивчаються, наявною апріорною інформацією про характер їхньої залежності та іншими факторами, зокрема простотою аналітичного представлення емпіричного матеріалу.

Математична суть даної задачі -- визначення параметрів a, b, c, ... обраної формули. Позначимо обрану функціональну залежність як y = f(x; a0, a1,..., an). Параметри a0, a1,..., an потрібно визначити. Але це неможливо зробити точно за значеннями функції y1, y2, ..., yn, оскільки вони містять випадкові величини. Мова йде лише про найкраще наближення функції вихідних даних. Таке наближення здійснюється методом найменших квадратів (МНК), суть якого полягає в наступному: якщо усі виміри значень функції y1, y2, ..., yn виконані з однаковою похибкою, то оцінки параметрів a0, a1,..., an визначаються з умови, щоби сума квадратів різниці виміряних значень уk найменше відрізнялась від розрахункових f(x; a0, a1,..., an), тобтовеличина приймала найменше значення.

Визначення тих значень параметрів a0, a1,..., an, які приймають найменше значення функції

S = S(a0, a1,..., an) зводиться до розв'язку системи рівнянь

Залежність виду y = ax + b -- це лінійна функція, що графічно зображується прямою лінією. Така залежність широко використовується при обчисленні значень одного фізичного параметра по відомим значеннями іншого.

При визначенні параметрів a, b лінійної функції y = ax + b за МНК система рівнянь (8.4) зводиться до виду



Розв'язок цієї системи дає формули для коефіцієнтів a, b

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

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

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



після чого прирівняємо отримані похідні в точці , обчисленні через лівий і правий інтервал від ():

Замінивши у формулах (4), (5) з урахуванням , отримаємо:

На даному етапі ми маємо 4n невідомих і (4n-2) рівняння. Тобто, необхідно знайти ще два рівняння. Їх отримаємо прирівнявши до нуля другі похідні в першому і останньому вузлах інтерполяції: . В результаті будемо мати:

Таким чином ми отримали систему лінійних алгебраїчних рівнянь, яка складається з рівнянь (2), (3), (6) -- (9) і з допомогою якої легко можна знайти невідомі коефіцієнти . Для цього приведемо її до більш зручного вигляду. З умови (2) знаходимо всі коефіцієнти . Далі, з (7) -- (9) отримуємо:



Підставляючи (2), (8) і (9) у формулу (3), отримаємо розрахункові формули для обчислення коефіцієнтів :

Підставимо тепер формули (10), (11) у формулу (7), і таким чином виключимо з неї невідомі та . В рузультаті отримуємо систему рівнянь з трьохдіагональною матрицею у якій невідомими являються тільки коефіцієнти :

Розв'язавши її методом прогонки, за знайденими коефіцієнтами знаходимо і . Тобто, для того, щоб знайти наближене значення таблично заданої функції у вузлах відмінних від заданих, використовуючи для цього кубічну сплайн-інтерполяцію, необхідно в першу чергу знайти коефіцієнти , в наступній послідовності: спочатку з формули (2) знаходимо коефіцієнти ; далі, розв'язавши систему (12) знаходимо ; та знаходимо з допомогою формул (10) та (11) відповідно. Наступним кроком є визначення інтервалу в який потрапляє аргумент після чого, в якості наближеного значення в цій точці береться значення:

.

Апроксимація полягає у визначенні достатньо простого виду функції (її аналітичного виразу), значення якої при мало відрізнялись би від табличних даних. Якщо табличну залежність одержано в результаті експериментів, то задача апроксимації цієї залежності називається інакше підбором емпіричної функції. Геометрично задача апроксимації полягає в проведенні графіка функції f(x) якомога ближче до системи точок (на відміну від інтерполяції тут не ставиться умова повного збігання значень і ).

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

- вибору загального виду цієї функції;

- визначення кращих її параметрів.

Вибір виду емпіричної функції для нелінійних залежностей

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

В тому випадку, коли дослідні дані табл. 5.1 містять велику експериментальну похибку або коли не стоїть задача досягнення високої точності, можна обмежитися найпростішим видом формули, яка вміщує тільки два параметри . В загальному випадку найбільш уживані поліноми виду (5.1) - (5.3).

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

1) лінійну ;

2) показникову ;

3) дрібно-раціональну ;

4) логарифмічну ;

5) степеневу ( вона визначає параболічну залежність, якщо a > 0, і гіперболічну, якщо a < 0; якщо a = 0, то залежність вироджується в лінійну);

6) гіперболічну ;

7) дрібно-раціональну виду .

Для найкращого вибору виду аналітичної залежності виконаємо наступні проміжні дії:

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

- обчислюємо середні арифметичні , ;

середні геометричні , ;

середні гармонічні , ;

- за обчисленими значеннями х знаходимо по графіку значення

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

, , ,

, , , ;

- знаходимо з цих похибок мінімальну

7. Інтерполяційні формули Гаусса, Стірлінга, Бесселя

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

Далі, ввівши змінну і зробивши відповідну заміну в формулі (2) отримуємо першу інтерполяційну формулу Гаусса:

або в скороченій формі:

де .

Перша інтерполяційна формула Гаусса використовує центральні скінченні різниці (в таблиці утворюють нижню ламану люнію позначену червоним кольором).



Таблиця центральних скінченних різниць

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

або в скороченій формі:

.

Інтерполяційна формула Стірлінга, представляє собою середнє арифметичне першої та другої інтерполяційних формул Гаусса і приймає наступний вигляі:

.

Взявши середнє арифметичне вище вказаних формул отримуємо інтерполяційну формулу Бесселя:

.

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

8. Квадратурні формули Чебишева та Гаусса

Формула Гаусса називається формулою найвищої алгебраїчної точності. Для формули вигляду (6.24) найвища точність може бути досягнута для поліномів степеня , які визначаються постійними

Завдання полягає у визначенні коефіцієнтів і абсцис точок .

Для знаходження цих постійних розглянемо виконання формули (6.24) для функцій вигляду

Враховуючи, що

,

отримаємо систему рівнянь

Ця система нелінійна, і її звичайне розв'язання пов'язане із значними обчислювальними труднощами. Але якщо використовувати систему для поліномів вигляду



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

В результаті властивості ортогональності ліва частина виразу (6.28) дорівнює 0, тоді

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

Підставляючи ці значення в систему (6.27) і враховуючи перші рівнянь, можна визначити коефіцієнти .

Формула (6.24), де - нулі полінома Лежандра , а визначаються із системи (6.27), називається формулою Гаусса.

Для довільного інтервалу (a,b) формула для методу Гаусса приймає вигляд

.

Оцінка похибки формули Гаусса з вузлами визначається із співвідношення

де - максимальне значення 2 похідної на ділянці

Візьмемо за основу формулу і будемо вважати всі квадратурні коефіцієнти однаковими: . Тоді

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

Для маємо

Покладаючи в приходимо до системи нелінійних рівнянь для визначення квадратурних вузлів

Отримана квадратурна формула називається формулою Чебишева. Зокрема при



9. Правило 3/8 для обчислення визначених інтегралів

Використовуючи кубічну інтерполяцію по чотирьох точках можна отримати формулу Ньютона (або трьох восьмих)[16].

Складову формулу трьох восьмих можна отримати при числі вузлів кратному трьом, тобто n = 3m

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

для формули прямокутників

для формули трапецій

для формули парабол



для формули трьох восьмих

де f"max, f?max, f?max максимальні значення похідних на інтервалі інтегрування [a,b].

При практичному використанні формул чисельного інтегрування слід враховувати, що до методичної похибки, яка спадає із зменшенням кроку, додається ще й похибка обчислень, яка збільшується при збільшенні числа кроків, тому для зменшення загальної похибки слід вибирати певний оптимальний крок. Зазвичай для вибору кроку використовують подвійний перерахунок. Спочатку обчислюють інтеграл In з деяким кроком h, а потім крок зменшують удвічі і отримують значення інтеграла I2n. Якщо різниця задовольняє вимогам точності |In-I2n|Ј e , то обчислення припиняють, в іншому випадку продовжують дробити крок[4]. Загальну похибку обчислень в цьому випадку можна оцінити співвідношеннями:

Ш D » |In-I2n|/3 для метода трапецій;

Ш D » |In-I2n|/15 для метода парабол.

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

10. Чисельні методи оптимізації

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

Складність рішення задач оптимізації полягає в тому, що їх однозначне вирішення потребує пошуку рішення серед такого числа варіантів, що їх простий перебір звичайно потребує більше часу, ніж термін актуальності такої задачі. Так, наприклад, пошук рішення для задачі комівояжера для 100 населених пунктів, потребує перегляду {\displaystyle (n-1)!/2}Размещено на http://www.allbest.ru/

або {\displaystyle 10^{158}}Размещено на http://www.allbest.ru/

варіантів. Для комп'ютера, що міг би виконувати 10 млрд обчислень на секунду для перебору всіх варіантів знадобись би {\displaystyle 10^{141}}Размещено на http://www.allbest.ru/

років.

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

· створення математичної моделі об'єкта (процесу або системи), для якого необхідно отримати оптимальне рішення;

· складання цільової функції {\displaystyle y=f(x_{1},...,x_{n})}Размещено на http://www.allbest.ru/

, яка на множині вхідних параметрів {\displaystyle x_{1},...,x_{n}}Размещено на http://www.allbest.ru/

та їх допустимих значень дозволяє отримати значення деякого показника системи {\displaystyle y}Размещено на http://www.allbest.ru/

, за яким виконується оптимізація;

· складання системи обмежень (областей визначення) на значення параметрів об'єкта оптимізації;

· визначення виду цільової функції (класифікація задачі) та відповідних методів рішення задач оптимізації.

Результатом застосування чисельних методів оптимізації є отримання таких значень {\displaystyle x_{1},...,x_{n}}Размещено на http://www.allbest.ru/

, для яких значення {\displaystyle y=f(x_{1},...,x_{n})}Размещено на http://www.allbest.ru/

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

Одномірна оптимізація

Задачі оптимізації, в яких цільовий показник залежить лише від одного параметра {\displaystyle x_{1}}Размещено на http://www.allbest.ru/

розглядаються як задачі одномірної оптимізації.

Багатомірна оптимізація

Задачі оптимізації, в яких цільовий показник залежить від декількох параметрів {\displaystyle x_{1},...,x_{n}}Размещено на http://www.allbest.ru/

розглядаються як задачі багатомірної оптимізації.

Размещено на Allbest.ru

...