Числові методи 2

1. Методи розв’язування нелінійних рівнянь та систем 2

4

2. Чисельні методи розв’язання систем лінійних рівнянь. Числа обумовленості СЛР. 5

3. Методи інтерполювання. Множники Лагранжа та Ерміта. Сплайни. 8

4. Методи чисельного інтегрування. 10

5. Чисельні методи розв’язання задачі Коші. 11

Числові методи

1. Методи розв’язування нелінійних рівнянь та систем

Нехай задано функцію f(x) дійсного аргументу. Треба знайти корені рівняння: f(x)=0 (1).

Задача знаходження коренів рівняння виду (1) складається з двох етапів:

1. Відокремлення коренів (вивчення розташування коренів на комплексній площині і визначення областей, в кожній із яких міститься лише один корінь). Крім того вивчається питання про кратність коренів. Таким чином стає відоме початкове наближення до розв’язку.

2. Використовуючи задане початкове наближення, здійснюється ітераційне наближення (ітераційне уточнення до кожного кореня).

Найчастіше 1-ший етап доводиться реалізовувати графічним методом.

2-гий етап може реалізовуватися декількома методами:

1. Метод дихотомії.

2. Метод простої ітерації (МПІ).

3. Метод релаксації.

4. Метод Ньютона (метод дотичних).

Коротко розглянемо кожний з методів.

I. Метод дихотомії.

Припустимо, що 1-ша частина задачі вирішена, тобто знайшли [a,b]. Нехай на [a,b] неперервна функція f(x) має лише один корінь (f(a)f(b)0). Нехай для визначеності f(a)>0, f(b)<0. Обираємо точку x₀=(a+b)/2. Підраховуємо f(x₀). Якщо f(x₀)>0, то корінь р-ня лежить на відрізку (x₀,b). Якщо f(x₀)<0, то корінь лежить на відрізку (a,. Далі, двох інтервалів (a,, (x₀,b) обираємо той, на границях якого функція має різні знаки, знаходимо точку – середину вибраного інтервалу, обчислюємо і повторюємо вказаний процес.

В результаті отримаємо послідовність інтервалів, що містять шуканий

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

Переваги. 1) простота; 2)цей метод відноситься до глобально-збіжних методів (обов’язково знайдемо корінь).

Недоліки. 1) збіжність повільна; 2) метод не можна узагальнити для розв’язання системи рівнянь.

II. Метод простої ітерації (умовно-збіжний метод).

Рівняння (1) замінюється еквівалентним рівнянням x=g(x) (2). Ітерації здійснюються за правилом x_k+1=g(x_k), k=0,1,... (для систем ) (3), x₀ - відоме початкове наближення. Для збіжності велике значення має вибір функції g(x) .

Озн. Функція g(x) називається Ліпшиць-неперервною зі сталою  на множині X, якщо  x₁, x₂  X виконується нерівність (4).

Теорема. Якщо на функція g(x) Ліпшиць-неперервна зі сталою   (0,1) і виконується умова , то ітераційний процес (3) веде до єдиного розв’язку рівняння (2) при  x₀  U_r(a). Для похибки роз-ку справедлива нерівність: .

Теорема показує умовний характер збіжності. Метод простої ітерації має лінійну збіжність.

Наслідок. Умова (4) на неперервн-диф. функції g(x) еквівалентна умові: . (1) перетворюється в (2) так, щоб умова збіжності виконувалася: х = x + (x)f(x), де  - неперервна і знакостала функція на проміжку наближень..

III Метод релаксації.

Коли (x)= =const, отримаємо ітераційний процес: і для якого і метод збіжний при умові (*).

Припустимо, що , ₁ (5) , де М₁ – максимум першої похідної, m₁– мінімум. Щоб виконувалась умова (*)  повинно задовольняти: 0 <   М₁ . Якщо  задовольняє цю умову, то процес збіжний. Підберемо  так, щоб процес (3) збігався якнайшвидше:

x_k-=z_k, z_k=x_k-– підставляємо в рівняння релаксації і отримаємо ,. (розклад в ряд Тейлора). Можна записати , Якщо виконується умова (5), то одержимо . Потрібно мінімізувати і тоді отримаємо .