Чисельні методи 4

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ЛЕКЦІЯ № 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 = х 01 <... <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 був найближчим до х, а всі інші вузли тим більш віддалені по збільшенню відстані до х.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Лекція
50.5кб. | скачати


Схожі роботи:
Чисельні методи 5
Чисельні методи 6
Чисельні методи 3
Чисельні методи розрахунків в Exel
Чисельні методи при вирішенні завдань
Чисельні методи для вирішення нелінійних рівнянь
Чисельні методи інтегрування та оптимізації складних систем
Чисельні методи розв`язання систем лінійних рівнянь
Мінімізація функції багатьох змінних Наближені чисельні методи Метод Монте-Карло
© Усі права захищені
написати до нас