Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи розв'язування систем лінійних алгебраїчних рівнянь
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
1. МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Розглянемо чисельні методи розв’язування систем лінійних алгебричних рівнянь
EMBED Equation.3 , (1)
де A - матриця m*m, EMBED Equation.3 - шуканий вектор, EMBED Equation.3 - заданий вектор.
Припускаємо, що EMBED Equation.2 та визначник матриці А відмінний від нуля, так що існує єдиний розв’язок Х. З курсу алгебри відомо, що систему (1) можна розв’язати за формулами Крамера1. Для великих m цей спосіб практично нереалізований тому, що потребує порядку m! aрифметичних дій. Тому широко використовуються інші методи розв’язування, наприклад, метод Гауса2, який потребує EMBED Equation.2 дій.
Методи чисельного розв’язування системи (1) поділяються на дві групи:
- прямі методи;
- ітераційні методи.
У прямих (або точних) методах розв’язок Х системи (1) відшукується за скінченну кількість арифметичних дій. Внаслідок похибок заокруглення прямі методи насправді не приводять до точного розв’язку системи (1) і назвати їх точними можливо лише залишаючи осторонь похибки заокруглення.
Ітераційні методи (їх також називають методами послідовних наближень) полягають у тому, що розв’язок x системи (1) відшукується як границя при EMBED Equation.3 послідовних наближень EMBED Equation.3 де n- номер ітерації. Як правило, за скінченну кількість ітерацій ця границя не досягається.
1.1. МЕТОД ГАУСА
Запишемо систему (1) у розгорнутому вигляді:
EMBED Equation.3 (2)
Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні невідомих EMBED Equation.3 з цієї системи.
Припустимо, що EMBED Equation.3 . Поділивши перше рівняння на EMBED Equation.3 , отримаємо
EMBED Equation.3 , (3)
де EMBED Equation.3
Розглянемо тепер рівняння системи (2), що залишилися
EMBED Equation.3 . (4)
Помножимо (3) на EMBED Equation.3 та віднімемо одержане рівняння з і-го рівняння системи (4), EMBED Equation.3 .
У результаті отримаємо наступну систему рівнянь
EMBED Equation.3 (5)
Tут позначено:
EMBED Equation.3 . (6)
Матриця системи (5) має вигляд:
EMBED Equation.3 .
Матриці такої структури заведено позначати так:
EMBED Equation.3 ,
де хрестиками позначені ненульові елементи.
У системі (5) невідоме х міститься тільки в першому рівнянні, тому у подальшому достатньо мати справу із скороченою системою рівнянь:
EMBED Equation.3 (7)
Тим самим ми здійснили перший крок методу Гаусса. Коли EMBED Equation.2 , то з системи (7) зовсім аналогічно можна вилучити невідоме x2 і прийти до системи, еквівалентній (2),що має матрицю такої структури:
EMBED Equation.3 . (8)
При цьому перше рівняння системи (5) залишається без зміни.
Вилучаючи таким же чином невідомі EMBED Equation.3 , приходимо остаточно до системи рівнянь виду
EMBED Equation.3 (9)
що еквівалентна початковій системі (2).
Матриця цієї системи
EMBED Equation.3 (10)
містить нулі усюди нижче головної діагоналі. Матриці такого виду називаються верхніми трикутними матрицями. Нижньою трикутною матрицею називається така матриця, у якої дорівнюють нулю усі елементи, що містяться вище головної діагоналі.
Побудова системи (9) складає прямий хід методу Гаусса. Зворотний хід полягає у відшуканні невідомих EMBED Equation.3 з системи (9). Тому що матриця системи має трикутний вигляд, можна послідовно, починаючи з EMBED Equation.3 , відшукати всі невідомі. Дійсно,
EMBED Equation.3 , ...
Загальні форми зворотного ходу мають вигляд
EMBED Equation.3 (11)
При реалізації на ЕОМ прямого ходу методу Гаусса немає необхідності діяти із змінними EMBED Equation.3 . Досить вказати алгоритм, за яким початкова матриця А перетворюється до трикутного вигляду (10), та вказати відповідне перетворення правих частин системи.
Одержимо ці загальні формули. Нехай вже здійснені перші EMBED Equation.3 кроків, тобто вже вилучені змінні EMBED Equation.3 . Тоді маємо систему
EMBED Equation.3 (12)
Розглянемо k-те рівняння цієї системи:
EMBED Equation.3 , (13)
та припустимо, що EMBED Equation.2 . Поділивши обидві частини цього рівняння на EMBED Equation.2 , отримаємо
EMBED Equation.3 , (14)
де EMBED Equation.3 .
Далі помножимо рівняння (14) на EMBED Equation.2 та віднімемо отримане співвідношення з i-го рівняння системи (12). У результаті остання група рівнянь системи (12) набуває наступного вигляду:
EMBED Equation.3 (15)
де EMBED Equation.3 .
Таким чином, у прямому ході методу Гауса коефіцієнти рівнянь перетворюються за наступним правилом
EMBED Equation.3 (16)
EMBED Equation.3 (17)
EMBED Equation.3 (18)
Обчислення правих частин системи (7) здійснюється за формулами:
EMBED Equation.3 (19)
EMBED Equation.3 (20)
Коефіціенти EMBED Equation.3 і праві частини EMBED Equation.3 ; EMBED Equation.3 зберігаються у пам’яті ЕОМ і використовуються при здійсненні зворотного ходу за формулами (11).
1.2. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ
Розглянемо систему лінійних рівнянь
EMBED Equation.3 (21)
де EMBED Equation.3 - задана числова квадратна матриця EMBED Equation.3 -го порядку, EMBED Equation.3 - заданий вектор вільних членів.
Метод простої ітерації полягає в наступному. Вибирається довільне початкове наближення вектору EMBED Equation.3 і будується ітераційна послідовність векторів за формулою
EMBED Equation.3 (22)
Ітераційний процес триває до тих пір поки не виконається умова його збіжності
EMBED Equation.3 , (23)
де EMBED Equation.3 - похибка збіжності ітераційного процесу задана у відсотках.
Для збіжності методу простої ітерації при будь-якому початковому наближенні EMBED Equation.3 необхідно і достатньо, щоб всі власні значення матриці В були за модулем меншими від одиниці. Ця умова пов’язана з необхідністю розв’язування рівняння
EMBED Equation.3 . (24)
1.3. МЕТОД ЗЕЙДЕЛЯ
Ітераційний метод Зейделя відрізняється від методу простої ітерації тим, що на EMBED Equation.3 -й ітерації при обчисленні EMBED Equation.3 -ої компоненти вектору EMBED Equation.3 використовуються значення EMBED Equation.3 , обчислені на тій же ітерації. Ітераційний процес Зейделя має вигляд
EMBED Equation.3 (25)
В матричному вигляді система рівнянь (25) має вигляд
EMBED Equation.3 , (26)
де
EMBED Equation.3
Для збіжності методу Зейделя необхідно і достатньо, щоб всі власні значення матриці EMBED Equation.3 були за модулем менші від одиниці. Нагадаємо, що в загальному випадку власні значення є комплексними величинами EMBED Equation.3 , тоді вище згадана умова записується у вигляді
EMBED Equation.3 (27)
Рівняння EMBED Equation.3 =0 тотжнє рівнянню
EMBED Equation.3 (28)
Слід зауважити, що в загальному метод Зейделя має кращу збіжність ніж метод простої ітерації. Хоча все залежить від параметрів конкретної задачі, тому не виключена ситуація, що метод простої ітерації дасть кращі результати. Однозначну відповідь на це питання дають рівняння (24), (28).
Ітераційний процес (26) завершуємо при виконанні умови його збіжності (23).
2. МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
НЕЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Розглянемо нелінійне векторне рівняння
EMBED Equation.3 , (29)
де EMBED Equation.3 - нелінійна вектор-функція, EMBED Equation.3 - вектор шуканих змінних
EMBED Equation.3
2.1. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ
Цей метод можна застосувати лише у цьому випадку, якщо рівняння (29) можна звести до вигляду
EMBED Equation.3 , (30)
де EMBED Equation.3 .
Ітераційний процес, який розв’язує (30) можна записати у вигляді
EMBED Equation.3 (31)
Умова його збіжності має вигляд
EMBED Equation.3 , EMBED Equation.3 (32)
де EMBED Equation.3 - розв’язок рівняння (29).
2.2. МЕТОД ЗЕЙДЕЛЯ
Аналогом методу Зейделя при розв’язуванні нелінійних систем рівнянь є ітераційний процес, згідно якому послідовні наближення визначаються зі співвідношення
EMBED Equation.3 (33)
Зауважимо, що для розв’язування систем нелінійних алгебричних рівнянь важливо є вибрати правильне початкове наближення. Окрім цього такі рівняння, як правило, мають декілька розв’язків. Маніпулюючи початковим наближенням ми можемо попадати в область притягання того чи іншого розв’язку.
2.3. МЕТОД ДІЛЕННЯ ДІЛЯНКИ НАВПІЛ
Цей метод не можна застосувати до систем нелінійних адгебричних рів нянь, а лише до одного нелінійного рівняння. В цьому методі спочатку обчис люємо значення функції в точках, що розсташовані на однакових інтервалах одна від одної по осі EMBED Equation.3 . Коли EMBED Equation.3 мають протилежні знаки обчислюють середнє значення між цими точками EMBED Equation.3 та EMBED Equation.3 .
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Рис. 1
Якщо знак EMBED Equation.3 збігається зі знаком EMBED Equation.3 , тоді ділянка EMBED Equation.3 відкидається з розгляду. Це реалізується шляхом переприсвоєння EMBED Equation.3 , таким чином інтервал на якому є розв’язок звужується вдвічі. Потім знову шу кається нове середнє значення і визначається нова ділянка на якій локалізується розв’язок. Графічна інтерпритація цього методу наведена на рис. 1. Тут виконано три послідовних наближення EMBED Equation.3 і розв’язок локалізовано між точками EMBED Equation.3 . Алгоритм зупиняємо за умови, якщо значення функції EMBED Equation.3 в точці EMBED Equation.3 буде близьким до нуля. Цей метод має хоча і низьку, але гарантовану збіжність. У порівнянні з початковим інтервалом, на якому знаходиться корінь, його ширина після EMBED Equation.3 ітерацій зменшується в EMBED Equation.3 раз
EMBED Equation.3 . (34)
2.4. МЕТОД ПОМИЛКОВОГО ПОЛОЖЕННЯ (ХОРД)
Цей метод не можна застосувати до систем нелінійних адгебричних рівнянь, а лише до одного нелінійного рівняння. Основою цього методу є лінійна інтерполяція за двома значеннями функції, що мають протилежні знаки. Вважається, що цей метод в порівнянні з методом ділення ділянки навпіл має кращу збіжність. Алгоритм даного методу зводиться до наступного. Спочатку обчислюємо значення функції в точках, що розсташовані на однакових інтервалах одна від одної по осі EMBED Equation.3 . Цей процес повторюємо до тих пір, поки EMBED Equation.3 не будуть мати протилежні знаки. Запишемо рівняння прямої, що проходить через точки EMBED Equation.3
EMBED Equation.3 (35)
Якщо накласти умову, що EMBED Equation.3 є точкою перетину прямої з віссю EMBED Equation.3 , тоді EMBED Equation.3 . Підставивши дану умову в рівняння (35), визначимо цю точку перетину
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Рис. 2
EMBED Equation.3 (36)
Якщо знак EMBED Equation.3 збігається зі знаком EMBED Equation.3 , тоді ділянка EMBED Equation.3 відкидається з розгляду. Це реалізується шляхом переприсвоєння EMBED Equation.3 , таким чином інтервал на якому є розв’язок звужується вдвічі. Далі будуємо нову пряму і шукаємо її перетин з віссю EMBED Equation.3 згідно рівняння (36). Графічна інтерпритація цього методу наведена на рис. 2. Умова завершення ітераційного процесу така ж як і у попередньому методі.
2.5. МЕТОД НЬЮТОНА (ДОТИЧНИХ)
Цей метод є універсальним і може бути застосований до систем нелінійних адгебричних рівнянь. Метод Ньютона широко використовується при побудові ітераційних алгоритмів. Його популярність пояснюється тим, що на відміну від двох попередніх методів, для визначення інтервалу в якому знаходиться корінь, нема необхідності обчислювати значення функції з протилежними знаками. Замість інтерполяції за двома значеннями функції в методі Ньютона відбувається екстраполяція (передбачення) з допомогою дотичної до кривої в заданій точці. Саме з цієї причини його інколи називають методом дотичних. В основі цього алгоритму лежить розклад нелінійної функції в ряд Тейлора
EMBED Equation.3 (37)
Члени, що містять другу та вищу похідні відкидаються. Викорис товуючи співвідношення EMBED Equation.3 можна записати вираз для обчис лення наступного значення через попереднє, а саме
EMBED Equation.3 (38)
де EMBED Equation.3 - матриця Якобі системи нелінійних алгебричних рівнянь
EMBED Equation.3 (39)
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Рис. 3
Це відповідає точці, в якій дотична перетинає вісь EMBED Equation.3 . Далі виконуємо заміну EMBED Equation.3 і повто рюємо алгоритм. Процес завершуємо після виконання умови збіжності ітераційного процесу
EMBED Equation.3 (40)
Графічна інтерпритація цього методу наведена на рис. 3. Швидкість його збіжності залежить від вда лого вибору початкового наближення EMBED Equation.3 . Застосування методу ускладнюється коли похідна EMBED Equation.3 близька до нуля, або приймає дуже великі значення.
2.6. ЕКСТРАПОЛЯЦІЙНИЙ МЕТОД
У 1971 р. американський вчений McLeod1 запропонував -алгоритм визначення границі послідовності з експоненційними складовими. Оригінальність методу полягає в тому, що він визначає границю послідовності навіть функції багатьох змінних. У 1972 р. за цю розробку він отримав першу премію року в галузі математики.
Його ідея зводиться до наступного. Нехай задавшись початковим значенням функції EMBED Equation.3 ми створюємо певну послідовність дискретних значень. Нехай, при нескінченній кількості кроків ця послідовність має границю. Виявляється, що -алгоритм маючи декілька значень цієї послідовності може визначити її границю.
Екстраполяційні методи цільову функцію використовують у вигляді EMBED Equation.2 Нехай задана послідовність значень
EMBED Equation.3 (41)
де EMBED Equation.3 – дискретні значення послідовності. Для послідовності (41), починаючи з EMBED Equation.3 , застосовуємо екстраполяцйну формулу
EMBED Equation.3 , (42)
де EMBED Equation.3 – шукана границя послідовності EMBED Equation.3 .
В якості функції EXTR доцільно використати EMBED Equation.3 – алґоритм, який виконує обчислення границі послідовності з експоненційними складо вими. Формула для обчислення наступного значення EMBED Equation.2 має вигляд
EMBED Equation.2 (43)
де
EMBED Equation.2 (44)
Результат екстраполяції, що відповідає EXTR в (23) рівний EMBED Equation.2 В (43) використовується процедура обертання Самельсона
EMBED Equation.2 (45)
де EMBED Equation.3 – k-й елемент n-мірної колонки EMBED Equation.3 .
Для систем розмірності EMBED Equation.3 значення EMBED Equation.3 . Границю послідовності для швидкозатухаючих компонент EMBED Equation.3 визначаємо безпосередньо на EMBED Equation.3 кроках. Як правило EMBED Equation.3 . На жаль, не існує строгого критерію вибору EMBED Equation.3 i EMBED Equation.3 , тому тут можливий лише еврістичний підхід.
Даний алгоритм можна застосувати для знаходження періодичного розв’язку систем нелінійних диференціальних рівнянь. Виявляється для цього достатньо визначити початкові умови, що задовольняють умову періодичності
EMBED Equation.3 , (46)
де Т – період вимушуючого сигналу.
В кінцевому результаті все зводиться до задачі Коші
EMBED Equation.3 (47)
Алґоритм обчислень
1. Інтеґруємо рівняння (47), від заданих початкових умов EMBED Equation.3 на EMBED Equation.3 періодах і визначаємо початкові умови періодичного режиму швидкозатухаючих компонент EMBED Equation.3 .
2. Маючи на EMBED Equation.3 -й ітерації початкові умови EMBED Equation.3 (на першій ітерації умови п.1), інтеґруємо рівняння (47) на EMBED Equation.3 періодах і породжуємо послідовність
EMBED Equation.3 . (48)
3. Згідно (43) визначаємо уточнене значення початкових умов
EMBED Equation.2 (49)
4. Перевіряємо умову збіжності ітераційного процесу
EMBED Equation.3 (50)
Якщо вона не виконується, то процес повторюємо з п.2, в противному випадку зупиняємо ітераційний процес.
Приклад. Для пояснення роботи методу (43) розглянемо рівняння електричного фільтру схема якого наведена на рис. 4. Така схема описується двома диференціальними рівняннями
EMBED CorelDRAW.Graphic.10
i L r
u
EMBED Equation.3
C
EMBED Equation.3
Рис. 4
EMBED Equation.2 (51)
Вектор змінних стану буде містити два елементи EMBED Equation.3 . Система рівнянь стану (51) має розмірність n=2, тоді m=2n=4. Розпишемо формулу (43) для даного випадку змінюючи параметри EMBED Equation.3 i EMBED Equation.3 . Отже, проінтеґрувавши систему рівнянь (51) на 4-х періодах породжуємо послідовність
EMBED Equation.2 (52)
де EMBED Equation.2 - початкові умови. Задавши EMBED Equation.2 маємо
1) EMBED Equation.3
EMBED Equation.2
2) EMBED Equation.3
EMBED Equation.2
3) EMBED Equation.3
EMBED Equation.2
4) EMBED Equation.3
EMBED Equation.2
Присвоюємо EMBED Equation.3 та перевіряємо умову (50). Якщо вона не виконується повторюємо процес при EMBED Equation.3 , в противному випадку вважається, що ітераційний процес збігся.
Цей метод можна застосувати також і в нейронних мережах. Відомо, що вагові коефіцієнти нейронів визначаються ітераційним методом. Як правило, число ітерацій в процесі навчання мережі дуже велике інколи сягає декількох тисяч і навіть десятків тисяч. Застосувавши екстраполяцію при використанні алгоритму можна суттєво прискорити процес навчання мережі.
3. ЧИСЕЛЬНЕ ІНТЕГРУВАННЯ
На практиці лише інколи вдається обчислити точно означений інтеграл або проінтегрувати звичайне диференціальне рівняння. Наприклад, в елементарних функціях неможна обчислити звичайний інтеграл
EMBED Equation.3 (53)
Щоб вирішити таку задачу використовують чисельні методи обчислення означених інтегралів. Розглянемо декілька найбільш поширених з них.
3.1. МЕТОД ПРЯМОКУТНИКІВ
Нехай треба обчислити означений інтеграл
EMBED Equation.3 (54)
де EMBED Equation.3 - межі інтегрування.
Згідно означення інтеграла маємо
EMBED Equation.3 (55)
Розбивши ділянку інтегрування на EMBED Equation.3 частин формулу (55) можна записати в наближеному вигляді
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
x
Рис. 5
EMBED Equation.3 . (56)
Враховуючи, що EMBED Equation.3 , маємо остаточний вираз
EMBED Equation.3 . (57)
Графічна інтерпритація даного методу наведена на рис. 5. Слід зауважити, що тут EMBED Equation.3 , EMBED Equation.3 .
3.2. МЕТОД ТРАПЕЦІЙ
Замінивши функцію EMBED Equation.3 на інтервалі від EMBED Equation.3 до EMBED Equation.3 ламаними відрізками прямих, інтеграл (54) можна обчислити як суму площ трапецій.
Площа і-ої трапеції обчислюється за формулою
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
x
Рис. 6
EMBED Equation.3 (58)
Тоді інтеграл (54) наближено обчислюється за формулою
EMBED Equation.3 . (59)
Неважко зауважити, що внутрішні ординати EMBED Equation.3 будуть додаватися двічі, тому формулу (59) можна записати у вигляді
EMBED Equation.3 . (60)
Вираз (40) називають методом трапецій обчислення означених інтегралів.
3.3. МЕТОД СІМПСОНА
EMBED CorelDRAW.Graphic.10
EMBED Equation.3
EMBED Equation.3
x
Рис. 7
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
На відміну від попередніх методів тут реальну функцію EMBED Equation.3 на інтервалі EMBED Equation.3 замінюємо її наближенням, а саме параболою другого порядку
EMBED Equation.3 (61)
Графічно така заміна показана на рис. 7. Для обчислення коефіцієнтів апроксимації параболи можна накласти умову, що парабола проходить через точки EMBED Equation.3 . Тобто, можна записати систему трьох лінійних алгебричних рівнянь з яких можна обчислити коефіцієнти апроксимації
EMBED Equation.3 (62)
Розв’язуючи дану систему рівнянь можна визначити коефіцієнти параболи, а саме
EMBED Equation.3 . (63)
Тоді остаточно парабола (61) враховуючи співвідношення (63) буде
EMBED Equation.3 . (64)
Означений інтеграл від функції (64) в межах від EMBED Equation.3 до EMBED Equation.3 буде визначатися співвідношенням
EMBED Equation.3 . (65)
Метод Сімпсона вимагає розбиття інтервалу інтегрування на парну кількість ділянок, тому (65) доцільно записати у вигляді
EMBED Equation.3 . (66)
Сумуючи ліву та праву частини цього співвідношення по EMBED Equation.3 від 0 до EMBED Equation.3 , отримаємо узагальнену формулу методу Сімпсона
EMBED Equation.3 , (67)
або
EMBED Equation.3 , (68)
Вираз (68) є остаточним виразом методу Сімпсона на інтервалі від EMBED Equation.3 до EMBED Equation.3 .
3.4. ЧИСЛОВЕ ДИФЕРЕНЦІЮВАННЯ ФУНКЦІЇ
Прості формули чисельного диференціювання отримують в результаті диференціювання інтерполяційних формул
f (k) (x) EMBED Equation.3 EMBED Equation.3
Похибка формул оцінюється нерівністю
EMBED Equation.3 (69)
де y1 = EMBED Equation.3
Зокрема,
EMBED Equation.3 (70)
де EMBED Equation.3 -сума всіх EMBED Equation.3 по EMBED Equation.3 співмножників.
Наприклад, EMBED Equation.3
EMBED Equation.3 (71)
4. МЕТОДИ ЧИСЕЛЬНОГО ІНТЕГРУВАННЯ
ЗВИЧАЙНИХ ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ
Звичайне диференціальне рівняння має безмежну множину розв’язків. Для знаходження конкретного розв’язку потрібні додаткові умови. У випадку, коли додаткові умови задаються при одному значенні незалежної змінної має місце задача Коші. Якщо додаткові умови задаються при двох або більше значеннях незалежної змінної, то задача називається крайовою. В задачі Коші додаткові умови називаються початковими, а в крайовій – граничними.
Сформулюємо задачу Коші. Нехай задано диференціальне рівняння
EMBED Equation.3 (72)
та початкову умову EMBED Equation.3 . Необхідно визначити функцію EMBED Equation.3 на інтервалі EMBED Equation.3 , яка задовольняє рівнянню (72) та початковій умові.
Методи розв’язування задачі Коші
Основою чисельних методів розв’язування диференціальних рівнянь є розклад функції EMBED Equation.3 в ряд Тейлора в околі точки EMBED Equation.3
EMBED Equation.3 , (73)
де EMBED Equation.3 – крок чисельного інтегрування.
Зауважимо, що в різних методах враховується різна кількість членів розкладу, що визначає точність обрахунків.
Методи розв’язування задачі Коші можна поділити на дві групи явні та неявні. Кожна з цих груп ділиться на однокрокові, де для знаходження наступної точки EMBED Equation.3 потрібна інформація лише про один попередній крок EMBED Equation.3 ; багатокрокові (прогнозування та корегування), де для знаходження наступної точки EMBED Equation.3 потрібна інформація більш ніж про одну попередню точку.
ОДНОКРОКОВІ ЯВНІ МЕТОДИ
Метод Ейлера
Найбільш простим однокроковим методом є явний метод Ейлера. Тут для обчислення наступного значення функції використовуються лише перші два члени ряду Тейлора, а саме
EMBED Equation.3 , (74)
де EMBED Equation.3 обчислюється згідно (72). Вираз (74) можна поширити на наступні кроки
EMBED Equation.3 , (75)
де EMBED Equation.3 =0, 1, 2, ...
Цей метод має найнижчу точність і може розбігатися. Його можна вдосконалити різними способами. Найбільш відомі з них два: виправлений метод Ейлера та модифікований метод Ейлера. Ітераційні формули цих методів є наступними
EMBED Equation.3 , (76)
EMBED Equation.3 (77)
де EMBED Equation.3 . Ці методи належать до другого порядку точності і мають кращу збіжність ніж метод (75).
Принцип на якому побудований модифікований метод Ейлера можна пояснити користуючись рядом Тейлора та зберігши в ньому член з EMBED Equation.3 . Друга похідна EMBED Equation.3 при цьому може бути апрпоксимована скінченною різницею
EMBED Equation.3 . (78)
Аналогічно обчисленню другої похідної в різницевому вигляді можна обчислити інші похідні, наприклад EMBED Equation.3 -ну, за значеннями попередньої EMBED Equation.3 -ої.
Метод Рунге-Кутта
Метод Рунге-Кутта дає набір формул для розрахунку координат внутрішніх точок, необхідних для реалізації цієї ідеї. Найбільшого поширення набув метод Рунге-Кутта четвертого порядку точності
EMBED Equation.3 , (79)
де
EMBED Equation.3
Метод Ейлера та його модифікації по суті є методами Рунге-Кутта першого і другого порядків. Метод Рунге-Кутта четвертого порядку має значно вищу точність, що дозволяє збільшувати крок інтегрування.
Розглянуті методи можна застосовувати для розв’язування систем нелінійних диференціальних рівнянь. Вони також придатні для роз в’язування рівнянь вищих порядків, бо диференціальне рівняння EMBED Equation.3 -го порядку завжди можна звести до системи EMBED Equation.3 диференціальних рівнянь першого порядку.
Нехай задано рівняння третього порядку
EMBED Equation.3 . (80)
Введемо позначення
EMBED Equation.3 . (81)
Це означає, що
EMBED Equation.3 . (82)
Враховуючи співвідношення (81), (82) рівняння (80) запишемо у вигляді
EMBED Equation.3 . (83)
Тоді (78), (80) можна записати як систему трьох диференціальних рівнянь
EMBED Equation.3 (84)
5. МЕТОДИ ЗНАХОДЖЕННЯ ВЛАСНИХ ЗНАЧЕНЬ І ВЕКТОРІВ МАТРИЦЬ
Нехай маємо квадратну матрицю EMBED Equation.3 і вектор EMBED Equation.3 Позначимо EMBED Equation.3 .
Якщо виявиться, що елементи EMBED Equation.3 тобто EMBED Equation.3 пропорційні EMBED Equation.3 з коефіцієнтом пропорційності λ, то вектор х називається власним вектором матриці А, а λ – власним значенням, або характеристичним числом.
EMBED Equation.3 або EMBED Equation.3
Звідки отримуємо визначник
EMBED Equation.3 . (5.1)
Якщо розкрити його, то отримаємо поліном по степенях
EMBED Equation.3 , (5.2)
де Аі – суми всіх діагональних мінорів і-го порядку.
Відома теорема Гамільтона-Келі:
Всяка квадратна матриця А задовольняє своє характеристичне рівняння
EMBED Equation.3 . (5.3)
Введемо на розгляд деякий скалярний многочлен EMBED Equation.3 .
Теорема. Якщо λ1, λ2, ... , λп – власні значення матриці А, а g(μ) – деякий скалярний многочлен, то g(λ1), g(λ2), … , g(λn) – всі характеристичні числа матриці g(A):
EMBED Equation.3
З декількох відомих методів розкриття визначника (5.3) розглянемо два методи: Лавер′є і Крилова.
5.1. МЕТОД ЛАВЕР′Є
Метод Лавер′є ґрунтується на визначені слідів степенів матриці А.
Слідом матриці називається сума її діагональних елементів і позначається SpA. Нехай
EMBED Equation.3 (5.4)
Оскільки матриця Аk має своїми характеристичними числами EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 .
Суми EMBED Equation.3 , степенів коренів многочлена
EMBED Equation.3 (5.5)
зв’язані з коефіцієнтами цього рівняння формулами Ньютона
EMBED Equation.3 EMBED Equation.3 . (5.6)
Якщо визначити сліди S1, S2, ... , Sn матриць А, А2, ... ,Ап, то тоді із (5.6) почергово можна визначити коефіцієнти в (5.2):
EMBED Equation.3 (5.7)
5.2. МЕТОД КРИЛОВА
Виберемо довільно вектор х розміром п. Складемо ряд векторів Ах, А2х, ... , Ап-1х. Нехай вони лінійно незалежні, а вектор
EMBED Equation.3 (5.8)
або EMBED Equation.3
EMBED Equation.3 (5.9)
Припустимо тепер
EMBED Equation.3
Тоді (5.8)
EMBED Equation.3 (5.10)
З цього рівняння, для знаходження коефіцієнтів рівняння (5.9) отримуємо наступну систему лінійних алгебраїчних рівнянь:
EMBED Equation.3 (5.11)
Компоненти EMBED Equation.3 векторів EMBED Equation.3 визначаються за формулами:
EMBED Equation.3 (5.12)
Розв’язавши систему лінійних алгебраїчних рівнянь (5.11), отримаємо коефіцієнти р1, р2, ... , рп характеристичного рівняння (5.9).
5.3. ВИЗНАЧЕННЯ ВЛАСНИХ ВЕКТОРІВ
Якщо відомі коефіцієнти рі, EMBED Equation.3 , і власні значення λі, EMBED Equation.3 , то, використавши метод Крилова, можна знайти власні вектори х(k):
EMBED Equation.3 . (5.13)
Коефіцієнти EMBED Equation.3 визначаються по схемі Горнера:
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 (5.14)
Визначальна схема метода Крилова
1. Вибираємо довільно вектор х, наприклад
х = [1, 0, 0, ... , 0]T.
2. За (5.12) визначаємо п векторів EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 .
3. Розв’язуємо систему рівнянь (5.11), наприклад за схемою Халецького. Якщо система виявляється виродженою, то змінюємо вектор х, наприклад х=[1, 1, 0, ... , 0]Т і знову визначаємо EMBED Equation.3 за п. 2.
4. Знаходимо власні значення рівняння (5.9), наприклад, методом виділення коренів.
5. Визначаємо коефіцієнти EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 за (5.14).
6. Знаходимо власні вектори за (5.13).
6. НАБЛИЖЕННЯ ФУНКЦІЙ
Задача наближення функцій виникає при розв’язуванні багатьох задач (інтегрування і диференціювання функцій, розв’язування диференціальних і інтегральних рівнянь, опрацюванні експериментальних даних).
Найпростіша задача, яка приводить до наближення функцій, залючається в наступному. В дискретні моменти х1, х2, ... , хп знаходиться значення функції у=f(x); необхідно встановити її значення при інших х.
Інколи відомо, що наближаючу функцію необхідно шукати у вигляді
EMBED Equation.3
Якщо параметри а1, а2, ... , ап визначаються з умови співпадання f(x) і наближаючої функції g(x) в точках х1, х2, ... , хп; g(xі) = f(xі), EMBED Equation.3 , то такий спосіб наближення називається інтерполяцією.
Часто буває відомо, що функція нормально наближується функціями деякого виду, наприклад, многочленами, але невідомо, як краще вибрати степінь наближеного многочлена.
В задачах планування експериментів виникає наступна проблема. Відомо вид нормального наближення функції, наприклад, функція нормально наближується многочленом другої степені. В цей же час вимірювальні значення функції мають великі помилки. Необхідно отримати найкращі в визначеній нормі наближення при мінімальній кількості виміряних значень функцій.
6.1. ІНТЕРПОЛЯЦІЯ
Інтерполяційний многочлена Лагранжа
Серед способів інтерполяції найбільш поширеним є випадок лінійної інтерполяції EMBED Equation.3 ,
де EMBED Equation.3 EMBED Equation.3 - фіксовані функції.
Значення коефіцієнтів аі визначаються з умови співпадання з наближеною функцією в вузлах інтерполяції хі:
EMBED Equation.3 (6.1)
В випадку EMBED Equation.3 , маємо
EMBED Equation.3 (6.2)
і EMBED Equation.3 . (6.3)
EMBED Equation.3 (визначник Вандермонда), отже, система має лише один розв’язок.
Інтерполяційний многочлен (6.2), записаний у вигляді
EMBED Equation.3 (6.4)
називається інтерполяційним поліномом Лагранжа.
Введемо позначення: EMBED Equation.3 . Очевидно
EMBED Equation.3 ; EMBED Equation.3 .
Тому (6.4) можна записати у вигляді:
EMBED Equation.3 . (6.5)
Оцінка кінцевого члену інтерполяційного поліному Лагранжа
Припустимо
EMBED Equation.3 .
Виберемо К з умови EMBED Equation.3 х* - точка, в якій оцінюється похибка. Тоді
EMBED Equation.3 .
При такому виборі К EMBED Equation.3 перетворюється в нуль в (п+1) точці х1, х2,...,хп, х*. На основі теореми Ролля її похідна EMBED Equation.3 перетворюється в нуль, в крайньому випадку, в п точках, … , EMBED Equation.3 перетворюється в нуль, в крайньому випадку, в одній точці EMBED Equation.3 : EMBED Equation.3 ; EMBED Equation.3 . Так як EMBED Equation.3 , то з умови EMBED Equation.3 виходить EMBED Equation.3 і
EMBED Equation.3 , EMBED Equation.3 – (6.6)
кінцевий член інтерполяційної формули Лагранжа (6.4).
Визначальна схема Ейткена. Схема Ейткена дозволяє звести визначення коефіцієнтів аі, EMBED Equation.3 , полінома (6.2) з врахуванням (6.4) до визначення функціональних визначників другого порядку.
Введемо позначення:
EMBED Equation.3 , EMBED Equation.3 ; (6.7)
EMBED Equation.3 , EMBED Equation.3 ; (6.8)
і т.д.
EMBED Equation.3 . (6.9)
Тоді, визначивши функціональний визначник Р1,2, ... , п(х), отримаємо (6.4) у вигляді (6.2), тобто знайдемо значення коефіцієнтів а1, а2, ... , ап .
Особливо велику економію дає описана схема при визначенні значень полінома Лагранжа в фіксованих точках EMBED Equation.3 .
Для визначення визначників (6.7) маємо
EMBED Equation.3 , EMBED Equation.3 (6.10)
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 .
Коефіцієнти EMBED Equation.3 , EMBED Equation.3 визначаємо за формулами:
EMBED Equation.3 ; EMBED Equation.3 ;
EMBED Equation.3 ;
EMBED Equation.3 ; (6.11)
EMBED Equation.3 ; EMBED Equation.3 .
Замінивши EMBED Equation.3 , EMBED Equation.3 , можна за формулами виду (6.11) визначити коефіцієнти полінома загального виду (6.9):
EMBED Equation.3 ; EMBED Equation.3 (6.12)
EMBED Equation.3 ,
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 .
Інтерполяційний поліном Ньютона
Роздільні і кінцеві різниці. Узагальненням поняття довільної є поняття роздільної різниці. Рішення різниці першого порядку визначаються рівністю
EMBED Equation.3 ;
різниці другого порядку:
EMBED Equation.3 ;
різниці k-го порядку:
EMBED Equation.3 . (6.12)
Справедлива рівність
EMBED Equation.3 . (6.13)
Роздільним різницею є симетрична функція своїх аргументів.
Якщо вузли таблиці хі розміщені на рівних відстанях: EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 – відповідні значення функції, то роздільні різниці типу (6.12) називаються кінцевими різницями k-го порядку:
EMBED Equation.3 (6.14)
кінцеві різниці вперед;
EMBED Equation.3 (6.15)
кінцеві різниці назад k-го порядку.
Кінцеві різниці назад k-го порядку виражаються через значення функції за формулою:
EMBED Equation.3 . (6.16)
При EMBED Equation.3 справедлива рівність:
EMBED Equation.3 . (6.17)
Інтерполяційні формули Ньютона. Для інтерполяційного полінома Лагранжа справедлива рівність (з врахуванням (6.13) роздільних відмінків):
EMBED Equation.3 . (6.18)
Запишемо EMBED Equation.3 у вигляді:
EMBED Equation.3 . (6.19)
Так як
EMBED Equation.3 при EMBED Equation.3 ,
то
EMBED Equation.3 .
Припустимо EMBED Equation.3 , отримаємо:
EMBED Equation.3 .
Припустимо в (6.18) EMBED Equation.3 і EMBED Equation.3 , маємо:
EMBED Equation.3 .
Внаслідок,
EMBED Equation.3
і
EMBED Equation.3 .
Підставимо ці величини в (6.19):
EMBED Equation.3 . (6.20)
Інтерполяційний поліном, записаний в такій формі, називається інтерполяційним поліномом Ньютона з роздільними різницями.
Зробивши в (6.20) заміну змінних EMBED Equation.3 , отримаємо інтерполяційну формулу Ньютона для інтерполяція вперед (для початку таблиці):
EMBED Equation.3 (6.21)
або
EMBED Equation.3 ,
де EMBED Equation.3 , EMBED Equation.3 – узагальнення степені: EMBED Equation.3 EMBED Equation.3
Для вузлів EMBED Equation.3 EMBED Equation.3 при EMBED Equation.3 отримуємо:
EMBED Equation.3 . (6.22)
– інтерполяційна формула Ньютона для інтерполяції назад, яка дає найбільшу точність в кінці таблиці.
Визн...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора