ЛЕКЦІЯ № 5 МЕТОДИ РІШЕННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ СНУ Нехай дана система виду:
(5.1)
f '(x) =
- Похідна
Приватна похідна
- Вектор (всі значення).
МЕТОД НЬЮТОНА Дана система виду (5.1), де f
i один раз безперервно діфірінціруемие
функції, тобто існують всі приватні перші похідні цих функцій.
Будуємо послідовність наближень
сходящуюся до точного розв'язку системи
.
Нехай
- Деяке початкове наближення до вирішення, а
- Катое наближення до вирішення. Побудуємо залежність, що дозволяє на підставі
побудувати
.
Точне наближення
ξ-корінь звертає рівняння у вірне рівність (тотожність).
(5.2)
Розкладемо функції f
i з системи (5.2) в ряд Тейлора в околі точки х
до до лінійних складових.
(5.3)
Система (5.3) являє собою систему лінійних алгебраїчних рівнянь для пошуку компонента вектора поправки h
k. Перепишемо систему (5.3) у вигляді:
(5.4)
Скорочуємо запис системи (5.4):
(5.5)
Вирішимо систему (5.5) методом зворотної
матриці. Визначник Якобіан в точці х
до не дорівнює 0.
Отримали зв'язок подальшого наближення з попереднім.
(5.6)
умова закінчення обчислень. (5.7)
- Відстань між векторами (метрика).
Метод ітерацій
Нехай дана система виду (5.1).
Перетворимо її до вигляду
(5.8)
Система (5.8) у векторному вигляді
(5.9)
Необхідно знайти нерухому точку систему
Очевидно, що ця точка ξ - рішення системи (5.1)
Нехай дано
-Деяке початкове наближення до ξ і на k-тому кроці отримано наближення
. Тоді подальше наближення:
(5.10)
Умова закінчення збігається з (5.7)
Чи завжди метод сходиться?
Нехай М-матриця, складена з елементів m
ij M = [m
ij], де m
ij =
Визначення норми матриці А:
-Число задовольняє властивостям.
1)
≥ 0,
= 0
≡ 0
2)
число
3)
4)
Способи завдання норми матриці:
1)
=
2)
=
3)
=
Достатня умова збіжності методу ітерацій:
Якщо
, I = 1, n,
на Сч і
Сч, то
процес ітерацій сходиться незалежно від вибору початкового наближення.
Метод Зейделя
Нехай дана система виду (5.1), перетворимо її до вигляду (5.8).
Як і в методі ітерацій будуємо послідовність наближень
до нерухому точку.
прискорення збіжності за рахунок підстановки попереднього наближення.
Достатня умова збігається з достатніми умовами збіжності методу ітерацій.
Умова закінчення отримання наближень збігається з (5.7).
ЛЕКЦІЯ № 6, 7 НАБЛИЖЕННЯ ФУНКЦІЇ
Загальна постановка задачі.
Нехай | (c) - деяка функція, яка може бути відомо, частково відомою і невідомою. Цю функцію необхідно замінити деякою «хорошою» функцією j (c), яка буде достатньо близькій | (c).
Для того щоб конкретизувати постановку задачі наближення функції необхідно відповісти на наступні питання:
1. що відомо про | (c) (спосіб завдання, ступінь гладкості);
2. до якого класу, сімейству функцій повинна належати j (c);
3. що розуміємо під близькістю j (c) і | (c) який критерій згоди;
Часто наближення функції називають
апроксимацією Постановка задачі інтерполяції.
Нехай | (c) задана на деякій розбитті відрізка [a; b] точками х i ,
i = 0, n, де a = х 0 <х 1 <... <x n = b
інтерполяція - обчислення | (c) в точці Î [a; b], x ¹ x i, i = 0, n
екстраполяція - обчислення функції | (c) в точці ХÎ [a; b];
Визначення інтерполяції ввів в 1656 році Джон Воллес, а в 1655 році ввів
символ ¥.
Для поліноміальної інтерполяції j (c) має вигляд j (c) = а
0 + а
1 х + а
2 х
2 + ... + а
n x
n. Для того, щоб вважати j (c) до | (c) вводиться обмеження j (c
i) = | (c
i), i = 0, n;
Тобто значення цих функцій в точці х
i повинні збігатися. Точки
х i будемо називати
вузлами інтерполяції Необхідно визначити коефіцієнти полінома ступеня n (їх буде n +1), побудови апроксимації функції, заданої в n +1 вузлі. Використовуючи обмеження на j (c): j (c
i) = | (c
i) = y, i = 0, n, складемо систему:
(6. 1)
Випишемо визначник цієї системи
Визначник
Вандермонда
За умови: x
0 ¹ x
j при
i ¹ j визначник системи (6.1) відмінний від нуля, отже, система має єдине рішення.
Висновок: якщо задано розбиття у вигляді n +1 різної точки, то завжди існує
функція у вигляді полінома n-го ступеня, яка проходить через всі точки графіка | (c), визначеної на цьому розбивці.
Сторонні наближення
функції за допомогою
поліномів зазначеним способом досить трудомістким і володіє великою обчислювальною похибкою, тому його використання для великої кількості вузлів інтерполяції недоцільно.
Лагранж запропонував будувати
інтерполяційні поліноми у вигляді:
P
n (x) = Σ C
i l
i (x) (6.2)
C
i = y
i = | (c
i), l
i (x) = поліноми n-го ступеня, які задовольняють умові:
Для полінома вузли інтерполяції x
j, j = 0, n, j ≠ I є корінням, причому дійсними і попарно різними (всі мають кратність 1)
Тоді поліном l
i може бути записаний у вигляді:
(6.3)
Загальний вигляд полінома Лагранжа: (6.4)
Постає питання про точність, про наближення функції. Вводиться
поняття залишкового члена многочлена Лагранжа; для того, щоб оцінити апроксимації | (c) в деякій точці x Î [a; b]
Функцію | (c) представимо у вигляді | (c) = P
n (x) + R
n (x), де R
n (x) - залишковий член многочлена Лагранжа в
процесі тривалого і трудомісткого виводу для R
n (x) отримана наступна формула:
(6.5)
Будується система вкладених відрізків
|
(N +1)-похідна (n +1)-го порядку
Нехай
(6.6)
Якщо | (c)-поліном n-го ступеня, то похідна (n +1)-го порядку дорівнює 0, тоді R
n (x) ≡ 0 і ми отримуємо точну апроксимацію.
Теорема: Многочлен Лагранжа виду (6.4) для таблично заданої функції єдиний.
Доказ: Нехай Q
n (x) - многочлен Лагранжа, побудований для цієї ж функції | (c) за тими ж вузлам інтерполяції. Q
n (x) ¹ P
n (x) Q
n (x
i) = y
i = P
n (x
i), Розглянемо многочлен L
n (x) = Q
n (x)-R
n (x)-це многочлен n-го ступеня, для якого точки x
i , I = 0, n є корінням. Це
суперечить основній теоремі алгебри, яка говорить про те, що поліном n-го ступеня має рівно n коренів. А L
n (x) має n +1 коренів. Протиріччя доводить теорему.
Інтерполяціонная схема Ейткіна
Оскільки при великому числі вузлів інтерполяції обчислення значення полінома Лагранжа за формулою (6.4) громіздко, необхідно отримати рекуррентную формулу.
Нехай | (c) - неперервна, вузли обрані на відрізку [a; b] таким чином, що:
Введемо функцію
x
i-вузли інтерполяції;
y
i = | (c)
Поліном Лагранжа: P
n (x) див. (6.4)
Таким чином,
функція Q
0,1 (x) являє собою поліном Лагранжа l-го ступеня, побудованої по вузлах x
0, x
1 введемо функцію виду
Функція Q
1,2 (x) -
інтерполяційний поліном Лагранжа, побудований по вузлах
x
1, x
2. Введемо тепер функцію
Аналогічно:
Q
0,1,2 (x
2) = у
2 У силу єдиності полінома Лагранжа, побудованого по вузлах
x
0, x
1, x
2 функція Q
0,1,2 (x) є інтерполяційний поліном Лагранжа 2-го ступеня, побудований по вузлах x
0, x
1, x
2. Введемо функцію:
(7.1)
Функція представляє собою поліном Лагранжа 2-го ступеня, побудованого по вузлах x
0, x
1, ... x
i. Формула
(7.1) дозволяє рекуррентно обчислювати поліном Лагранжа будь-якого ступеня.
Оскільки (7.1) являє собою альтернативну форму запису інтерполяційного полінома, точність наближення функції також може бути оцінена за формулою (6.5)
(7.1)-інтерполяціонная схема Ейткіна.
КІНЦЕВІ РІЗНИЦІ
Нехай функція | (c) задана на системі рівновіддалених вузлів x
i = x
0 + ih,
де h-крок сітки, y
i = | (c
i). Кінцевою різницею першого порядку в точці x
0 називається Δy
0 = y
1-y 0 Кінцевою різницею першого порядку в точці x
i: Δy
i = y
i +1-y 0-y i Кінцевою різницею другого порядку в точці x
0: Δ
2 y
0 = Δy
1-Δy 0 Кінцевою різницею другого порядку в точці x
i: Δ
2 y
i = Δy
i +1-Δy i Загальна формула для кінцевої різниці k-того порядку в точці x
i: Δ k y i = Δ k -1 y i +1-Δ k y (7.2)
Зауважимо:
Δ 0 y i = y i Формула (7.2) дозволяє обчислювати рекуррентно кінцеві різниці
Зв'язок кінцевих різниць і похідних
чим менше h, тим точність вище
Аналогічно можемо отримати зв'язок
; (7.3)
Властивості кінцевих різниць
У зв'язку з похідними виду (7.3)
кінцеві різниці мають властивості:
1. постійні, дорівнюють нулю;
2. постійний множник у функції виноситься за знак
3. суми 2-х функцій дорівнюють сумі кожної функції
4.
полінома n-го ступеня, n-го порядку постійні і дорівнюють
Δ
n y = h
n a
n n!
a
n-коефіцієнт при x
n полінома R
n (x)
Вірно і зворотне твердження: всі кінцеві різниці n-го порядку деякої функції постійні і однакові, кінцеві різниці n +1- го порядку рівні 0, а кінцеві різниці n-1-го порядку різні, то функція являє собою поліном n-го ступеня.
Поширення помилки у вихідних даних при обчисленні кінцеві різниці Будь-які вимірювання несуть в собі похибка (помилка округлення, точність вимірювання приладів)
Нехай значення функції визначені у вузлах x 0, і в деякій точці x k значення деякій точці x k значення функції знайдено з помилкою ε, тобто ỹ k + ε
Складемо таблицю кінцевих різниць
x k -2 y k -2 Δy k -2 Δ 2 y k -2 Δ 3 y k -3 + ε
x k -1 y k -1 Δy k -1 + ε Δ 2 y k -2 + ε Δ 3 y k -2 -3 ε
x k y k + ε Δy k -1 - ε Δ 2 y k -1 - 2 ε Δ 3 y k -1 + 3 ε
x k +1 y k +1 Δy k +1 Δ 2 y k + ε Δ 3 y k - ε
x k +2 y k +2 Δ 2 y k +1
Як видно з
таблиці скінчених різниць при збільшенні порядку кінцевих різниць помилка у вихідних даних поширюється і росте.
Така взаємодія помилок називають шумом, якщо це помилки заокруглень - то
шумом заокруглень. Якщо помилки заокруглень досить великі, то може відбуватися наступне явище: при збільшенні порядку кінцевих різниць вони можуть зменшуватися і → 0, але, дійшовши до деякого малого значення, знову можуть почати рости через шум заокруглень.
Стовпець у таблиці кінцевих різниць, в якій всі кінцеві різниці ≈ 0, називають «практичним постійним»; при цьому кінцеві різниці вищих порядків не використовують.
Для інтерполяції доцільно використовувати многочлен такого ступеня, який збігається з порядком «практичної постійної» кінцевих різниць.
ЛЕКЦІЯ № 8 Дана функція y = | (c), задана на сітці рівновіддалених вузлів:
y
i = | (c
i), x
i = x
0 + ih
i, Будуємо інтерполяційний поліном з метою спрощення запису полінома (інтерполяційного) і подання його у вигляді, що дозволяє оцінювати вплив кожного з компонентів на значення апроксимації, запишемо його так:
N n (x) =- a
0 + a
1 (xx
0) + a
2 (xx
0) (xx
1) + ... + a
n (xx
0) ... (xx
n-1) (8.1)
Необхідно порахувати його коефіцієнти a
i. Будемо знаходити з умови
N n (x
i) = y
i i = 0: N n (x
0) = y
0 = a
0 + a
1 0 + ... + a
n 0 a
0 = y
0 i = 1: N n (x
1) = y
1 = y
0 + a
1 (x
1-x 0) + a
2 0 + ... + a
n 0
x
1 = x
0 +1 h = x
1-x 0 = h
i = 2: N n (x
2) = y
2 = y
0 + Δy
0 / h (x
2-x 0) (x
2-x 1) + a
3 0 + ... + a
n 0
x
2-x 0 = 2h
x
2-x 1 = h
y
2 = y
0 + Δy
0 2 + a
2 2h
2 i = k: (8.2)
Запишемо тепер, використовуючи
(8.2), поліном
(8.1) у вигляді:
N n (x) = y
0 + Δy
0 / h (xx
0) + ... + Δ
n y
0 / n! h
n (xx
0) (xx
1) ... (xx
n-1) (8.3)
Поліном
(8.3) 1-ий інтерполяційний многочлен Ньютона.
Він найбільш пристосований для обчислення значення функції в точках, близьких до x
0 З метою спрощення запису полінома введемо змінну
x = x
0 + gh
Якщо g-ціле, то буде збігатися з номером вузла
x
0 - базовий вузол полінома
(8.3) x
i = x
0 + gh-x
0-ih = h (gi);
N n (g) = y
0 + Δy
0 g + ... + Δ
n y
0 / n! g (g-1) (g-2) (g-n +1) (8.4)
Поліном Ньютона в силу єдиності
існування інтерполяційного полінома Лагранжа є однією з форм запису полінома Лагранжа, тому для полінома (8.3) справедливо, що формула залишкового члена полінома Лагранжа
Для обчислення функції в точках знаходяться в середині сітки вузлів інтерполяції або в її кінці, тобто близькі до x
n, застосовують два підходи
1. будують формули для обчислення функції в точках х, близьких до середини сітки інтерполяції
2. формули для точок х, близьких до х
n (упорядкування вузлів інтерполяції).
Відповідно виходять формули Стірлінга, Бесселя, Гауса, і 2-ий інтерполяційний многочлен Ньютона.
Другий шлях: як вузла х
0 для заданої точки х беруть той вузол, який найбільш близький до х, вузол х
1 вибирають як найближча з решти вузлів до х.
Тобто послідовність
Впорядкувати за Зростанням.
Для обчислення значення функції в точці х використовується першого інтерполяційний многочлен Ньютона.
х0 х1 х2 х3 х4 х5 х6
Перетворимо вузли:
х
0 '= x
3; x
1 '= x
4; x
2 '= x
2; x
3 '= x
5; Розділені різниці Нехай функція | (c), задана на системі нерівно віддалених вузлів.
Розділеної різницею 1-го порядку назвемо вираз:
Розділеної різницею 2-го порядку:
Розділеної різницею k-го порядку:
(8.6)
| Xx
0 |,
Властивості розділеної різниці: - На сітці рівновіддалених вузлів розділеної різниці збігаються кінцевими різницями
- Розділені різниці знижують ступінь многочлена
- Розділені різниці n-го порядку постійні і дорівнюють
Інтерполяціонная формула Ньютона для не рівновіддалених вузлів Нехай функція | (c), задана на сітці не рівновіддалених вузлів x
i, . Запишемо наступні розділені різниці:
Виконаємо такі дії n-1 раз, отримаємо:
Поліном Ньютона:
N n (x) =
|
0 (c)
R
n (x) = | (c, c
0, ... c
n) (xx
0) ... (xx
n) (8.8)
Те | (c) =
N n (x) + R
n (x)
N n (x) ≈ | (c)
R n (x) = | (c) - N n (x)
Якщо | (c) має (n +1)-ую похідну, то залишковий член може бути перетворений до виду залишкового члена
(8.9) полінома Лагранжа.
При обчисленні полінома в точці х вузли інтерполяції краще перейменувати так, щоб х
0 був найближчим до х, а всі інші вузли тим більш віддалені по збільшенню відстані до х.