Методи розв’язання систем лінійних і нелінійних алгебраїчних рівнянь

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

10

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

методи розв'язання систем лінійних і нелінійних алгебраїчних рівнянь

Прямі методи розв'язання систем лінійних алгебраїчних рівнянь. Метод гауса

розв'язання система лінійне алгебраїчне рівняння

Цей метод є точним. Він заснований на зведенні матриці системи до трикутного вигляду.

Нехай потрібно розв'язати систему ; тут - матриця коефіцієнтів системи розмірності , .

і - вектори.

Віднімемо від другого рівняння системи

(1)

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

(2)

 Помножимо -й рядок на число

, (3)

і віднімемо його від -го рядка. Перший ненульовий елемент цього рядка обернеться на нуль, а інші зміняться за формулами

,

, (4)

.

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

У результаті виконання прямого ходу одержимо систему з матрицею трикутного вигляду

. (5)

Така система легко розв'язується за допомогою так званого зворотного ходу, суть якого така. З останнього рівняння визначаємо . Підставляючи його в передостаннє рівняння, знаходимо і т.д. Загальні формули зворотного ходу мають вигляд

 . (6)

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

Якщо елемент на головній діагоналі малий, то цей рядок домножується на великі числа , що призводить до значних помилок округлення при обчисленнях. Щоб уникнути цього, кожен цикл завжди починають з перестановки рядків. Серед елементів стовпця знаходять головний, тобто найбільший за модулем у -ому стовпці, і перестановкою рядків переводять його на головну діагональ, після чого роблять виключення. У цьому суть методу Гауса з вибором головного елемента.

Питання для самоперевірки

Сформулюйте постановку задачі, опишіть метод розв'язання, оцініть похибку методу.

У чому суть і переваги методу Гауса з вибором головного елемента?

Завдання до лабораторної роботи № 4

Розв'язати систему лінійних алгебраїчних рівнянь

методом Гауса з вибором головного елемента.

НАБЛИЖЕНІ МЕТОДИ РОЗВ'ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Метод простих ітерацій

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

(1)

і її розв'язок знаходиться як границя послідовності

(2)

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

Нагадаємо визначення основних норм у просторах векторів і матриць. Якщо в просторі векторів введена норма , то погодженою з нею нормою в просторі матриць називають норму

.

Найбільш вживані в просторі векторів наступні норми

,

,

,

а погодженими з ними нормами в просторі матриць є відповідно норми

;

;

,

тут - власне значення матриці , - матриця, сполучена до матриці .

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

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

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

Приклад.

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

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



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

.

Тепер у нову систему ввійшли рівняння і , тому в рівняння обов'язково повинне ввійти рівняння даної системи. Підбором переконуємося, що за рівняння можна взяти лінійну комбінацію , тобто

.

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

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

;

;

;

.

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

; ; ; .

Після нової підстановки будемо мати треті наближення коренів і т.д.

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

0 1 2 3 4 5 6 7 8 9	-0,4 -0,258 -0,301 -0,327 -0,330 -0,332 -0,333 -0,333 -0,333 -0,333	0,2 0,360 0,408 0,429 0,438 0,442 0,443 0,444 0,444 0,444	-0,4 -0,782 -0,844 -0,863 -0,879 -0,885 -0,887 -0,888 -0,889 -0,889	-1,111 -1,244 -1,197 -1,212 -1,220 -1,221 -1,222 -1,222 -1,222 -1,222

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

Питання для самоперевірки

Сформулюйте постановку задачі, опишіть метод розв'язання, оцініть похибку методу.

Які умови збіжності ітерацій до точного розв'язку є достатніми?

В чому полягає умова закінчення ітераційного процесу?

Метод Зейделя

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

Нехай дано зведену лінійну систему

, .

Оберемо довільно початкові наближення коренів .

Далі, припускаючи, що -і наближення коренів відомі, згідно Зейделю будемо будувати -і наближення за наступними формулами:

, . (1)

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

Розглянемо розв'язання попереднього прикладу методом Зейделя. Система була зведена до вигляду

Узявши, як і раніше, за початкове наближення стовпець вільних членів, тобто

згідно методу Зейделя, одержимо перші наближення коренів

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

0 1 2 3 4 5 6	-0,4 -0,258 -0,308 -0,329 -0,332 -0,333 -0,333	0,2 0,332 0,423 0,440 0,443 0,444 0,444	-0,4 -0,807 -0,870 -0,884 -0,888 -0,889 -0,889	-1,111 -1,197 -1,214 -1,221 -1,222 -1,222 -1,222

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

Завдання до лабораторної роботи № 5

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

,

Варіанти завдань

№ варіанта	Матриця коефіцієнтів системи	Стовпець вільних членів
1	2,1 0,0 5,2 -0,6 1,3 0,4	0,3 2,2 -1,0 1,5 0,2 0,0	4,4 -3,4 0,4 3,2 0,0 -2,7	-0,1 0,3 0,7 -2,1 0,8 1,4	1,4 -0,8 1,1 1,6 6,1 -1,8	0,0 1,4 -0,1 0,6 -1,4 3,1	-2,25 4,07 3,69 -8,02 -16,33 18,06
2	3,3 -0,1 -2,1 0,4 4,7 0,0	4,2 7,2 3,0 0,0 -0,6 0,2	0,7 1,8 -0,6 1,9 3,3 -1,6	5,4 -2,3 -3,4 6,1 7,1 2,4	2,1 1,1 -0,5 -0,8 1,9 0,7	1,6 0,3 0,0 -2,1 -4,6 5,7	24,87 7,81 0,20 11,00 0,12 22,04
3	0,4 4,8 -2,1 0,6 6,3 4,2	7,6 -5,2 3,3 2,4 -0,4 -1,7	2,0 -2,3 -0,4 -1,7 1,4 6,9	-0,3 1,6 3,4 3,0 0,8 0,0	1,8 0,8 -0,5 -8,0 0,0 1,1	2,1 -3,5 0,0 1,1 1,0 9,2	29,95 -20,33 2,11 -1,91 7,01 17,25
4	1,7 1,2 -0,1 2,1 8,4 1,6	-3,1 -1,0 7,2 1,3 -1,6 8,7	2,2 0,7 4,8 -5,2 0,0 -0,2	0,6 -0,9 2,3 1,4 0,7 0,8	1,8 0,0 5,1 3,3 -1,8 -2,0	-0,1 5,9 3,3 4,6 1,2 1,1	2,68 -6,17 -35,57 -25,65 8,50 -14,46
5	-1,1 -2,7 8,8 2,1 0,3 2,3	-0,8 1,9 -1,5 3,6 7,4 -2,0	0,1 -5,9 0,3 -1,5 -1,9 3,9	0,6 1,3 -0,7 -2,1 1,1 4,2	5,7 -2,2 1,2 0,0 0,9 0,2	2,0 1,0 -2,1 4,6 0,2 -1,9	11,83 16,24 18,64 -37,76 -7,90 -8,78
6	3,4 2,2 4,4 -1,3 -2,5 0,1	-1,0 0,6 -2,9 -0,8 5,8 0,3	2,2 6,8 -1,5 0,1 1,1 -1,0	1,0 0,0 -0,7 0,6 3,1 5,4	4,8 -0,1 1,3 2,0 0,0 -1,9	1,4 -0,4 0,8 5,7 2,4 0,1	20,16 -1,58 15,62 -0,39 -11,95 -12,82
7	2,2 -2,1 0,0 4,9 -0,4 -2,9	-0,4 3,6 0,2 -1,9 2,1 4,0	0,6 4,7 -1,0 -2,7 2,0 1,1	5,2 -1,3 0,0 1,2 -0,3 -1,6	-1,2 -2,8 6,8 0,3 1,8 3,7	0,1 2,0 1,4 -1,0 7,6 -1,1	9,43 7,77 -6,20 10,28 16,05 -9,78
8	3,4 -2,3 7,9 2,2 1,4 3,2	1,6 0,1 -0,3 -1,0 8,9 -2,0	2,2 6,6 1,3 3,0 -0,1 1,7	-1,2 -0,4 -0,1 -1,2 0,0 4,1	4,2 0,0 1,8 3,4 -1,1 -1,9	-2,1 1,2 0,1 5,8 -0,7 0,4	20,72 6,52 13,20 5,70 -4,31 0,23
9	2,2 2,6 6,3 -3,1 -0,4 3,3	-0,1 0,0 0,1 2,4 7,9 -1,9	-0,3 4,1 -2,7 1,4 2,0 -2,1	0,2 -1,2 0,2 2,1 -0,2 4,8	5,3 2,1 -1,3 0,5 -1,7 0,0	-1,7 -0,1 -0,5 3,7 1,9 1,7	-6,11 -18,21 -2,48 13,14 21,60 2,68
10	-3,9 0,4 4,6 0,1 2,2 -1,3	2,3 -1,6 0,7 1,3 5,2 1,8	0,0 5,3 2,1 1,6 0,9 -0,2	-1,5 1,0 -1,4 -2,1 -1,1 8,6	3,8 -0,2 2,7 0,2 -2,1 -2,2	-4,1 -0,1 -3,6 6,7 1,2 0,0	15,40 2,83 35,68 -10,10 -0,95 -29,34
11	0,1 -2,3 6,8 -2,7 -1,0 3,3	0,0 3,6 0,1 1,4 8,1 -1,8	0,9 4,3 -1,1 2,0 0,0 2,2	-1,1 2,4 -1,4 0,0 1,2 4,4	6,2 0,3 2,0 -3,4 -0,1 2,1	0,6 -1,2 -0,8 4,3 0,4 0,0	-2,06 2,86 16,15 -6,29 -10,12 34,53
12	0,3 1,3 5,7 2,7 0,1 -4,7	-0,9 0,8 -1,5 3,2 6,8 2,4	0,0 4,1 -0,4 -2,0 1,2 -3,9	1,1 2,5 1,2 1,3 -2,0 -3,9	6,3 -3,0 0,0 -3,6 -0,8 0,4	-3,0 -1,7 0,6 4,9 1,2 2,1	-18,47 -11,85 0,69 33,99 14,64 24,29
13	0,4 1,7 -2,0 3,1 -0,9 4,5	0,6 -2,2 -1,1 -2,4 6,8 2,4	2,2 4,1 0,0 -3,8 1,6 -2,0	5,4 -3,2 0,2 2,0 -0,2 3,9	-1,2 1,9 6,8 0,0 1,2 -1,1	-0,1 2,1 1,2 4,6 -1,0 4,1	-26,32 13,22 23,50 -20,28 13,06 -29,17
14	-3,5 -2,4 3,9 0,1 -0,9 1,4	-1,3 1,0 1,5 7,1 6,8 -0,6	-2,2 0,1 2,6 0,7 1,6 -8,8	1,4 6,9 -1,2 -1,1 -0,2 2,1	3,6 1,6 1,0 -1,9 1,2 -0,6	0,4 0,0 -4,8 1,6 -1,0 2,8	-22,69 -13,35 11,33 -17,57 -23,88 -30,08
15	2,1 -2,2 0,1 2,4 -0,7 7,5	0,4 -3,1 -1,4 -3,4 2,9 0,4	7,7 0,8 -1,8 1,1 4,6 -2,0	-1,9 4,2 2,0 -4,1 3,2 0,9	0,4 -3,8 0,0 0,9 1,6 -1,1	-1,7 1,2 6,6 2,1 -0,8 0,1	-19,76 -15,45 1,03 -20,28 3,86 14,59
16	4,9 1,3 -2,7 0,2 1,0 9,1	-2,7 -0,8 1,4 7,0 -2,1 -0,5	0,9 -2,0 3,3 -1,5 3,6 1,2	1,4 1,2 -2,5 -0,1 4,4 -2,4	-3,5 6,8 0,0 -2,3 0,9 0,0	0,0 0,1 -0,8 1,0 2,5 -0,6	-29,45 3,41 20,11 -7,93 -21,21 -28,18
17	0,1 -3,4 0,3 1,9 -0,8 -1,7	0,0 1,2 0,0 -4,1 1,1 0,4	0,9 -2,7 8,1 0,0 -2,8 -1,9	-1,1 4,8 1,5 -2,0 -1,4 7,7	6,0 -3,9 -1,0 3,7 0,1 0,4	2,3 0,9 -0,7 0,9 2,2 2,1	3,13 -4,70 -9,75 13,91 2,47 6,41
18	1,2 -3,7 0,9 -1,6 4,8 7,5	0,0 1,3 1,5 -2,4 -1,9 0,4	-0,4 2,8 0,6 -3,7 1,8 -2,0	6,6 -1,7 -1,2 4,1 -0,2 0,9	0,1 -4,2 1,0 0,0 -3,5 -1,1	-2,5 0,0 6,8 2,9 0,0 0,1	16,04 19,46 25,20 9,52 11,16 33,70
19	-3,7 0,4 1,9 -7,8 0,4 2,3	0,9 0,6 -2,3 -0,3 -0,2 1,7	4,1 2,2 -3,5 -1,9 1,1 0,9	-2,2 5,4 2,0 0,4 -0,6 3,4	1,9 -1,2 0,4 1,7 2,3 -4,4	0,0 -0,1 -4,2 2,2 5,7 -1,9	21,55 -22,09 2,71 12,63 -4,15 -27,60
20	1,2 -3,9 0,0 2,4 -4,1 0,0	0,0 2,6 -0,9 0,8 3,7 1,9	-0,4 4,1 6,1 -2,9 2,5 0,1	6,6 -0,8 0,7 3,3 -1,1 -1,3	0,1 2,4 -1,0 0,9 2,2 0,2	-2,5 1,6 1,2 -1,6 3,0 7,8	-10,39 12,90 -10,26 4,21 -3,00 -15,20
21	1,7 -0,7 2,8 -0,1 7,9 1,8	-0,8 -1,1 1,4 5,2 0,4 -2,4	-2,1 0,0 -1,0 -1,2 -0,2 3,5	1,1 0,3 -2,6 2,2 0,0 -1,1	0,4 8,1 -0,7 0,6 -1,0 0,8	0,0 1,3 3,1 -0,4 1,2 2,7	14,51 20,69 1,51 -8,76 3,98 -5,78
22	1,9 -0,9 2,1 -4,6 1,5 -0,5	-1,7 0,0 3,3 -2,8 0,6 0,3	0,3 6,8 -4,0 1,3 2,2 1,3	2,1 -2,1 1,7 3,5 -0,4 2,9	-7,9 -0,9 1,1 0,9 1,8 0,1	-0,4 1,3 2,4 0,0 -2,3 6,2	16,42 0,66 8,48 24,85 -14,05 35,58
23	1,8 -2,1 0,9 -4,4 5,8 0,0	-5,2 1,7 -1,4 2,9 0,5 2,2	0,2 -1,6 0,2 -3,5 -2,4 -1,2	-0,4 2,8 -2,1 1,9 0,3 8,0	0,0 -3,4 1,8 2,4 1,4 -0,1	2,2 0,0 -3,4 1,6 -0,1 1,7	-1,16 -25,32 11,05 -14,78 25,47 -9,90
24	-2,6 1,4 -0,1 0,0 3,6 0,4	1,7 -3,2 0,2 2,1 -4,1 -0,1	0,4 -2,9 -1,0 8,4 0,7 -1,1	-2,3 0,7 5,2 -0,2 2,4 0,0	3,1 -1,8 -0,8 1,6 1,9 8,0	0,0 2,2 1,4 -1,3 -3,2 1,2	-23,91 16,04 9,91 1,18 45,77 -1,15
25	-1,2 -0,8 4,5 2,6 6,7 -1,5	5,7 1,9 -3,4 1,8 -0,1 2,0	-0,5 -1,4 1,9 -2,1 -1,2 0,8	0,2 1,1 -2,8 0,9 1,7 0,0	-0,1 0,0 3,7 -1,1 0,5 -2,3	-0,9 6,6 0,0 -0,6 0,0 1,9	11,76 43,81 -29,38 13,52 11,10 11,96
26	-0,2 4,6 1,1 0,0 0,4 -2,8	0,3 -3,0 2,9 2,1 -0,1 1,5	2,4 -2,7 0,8 8,4 1,2 -3,1	5,3 0,0 -3,1 0,2 0,0 -2,2	1,6 -1,9 0,7 -1,8 8,1 0,0	-0,3 3,5 -2,3 1,3 -1,0 3,3	-11,76 -4,58 7,68 -3,34 30,76 20,42
27	1,9 0,6 -0,8 2,4 -1,1 6,3	-4,6 6,0 2,0 -3,9 0,0 -1,4	0,0 -0,4 -1,4 1,6 0,5 0,0	3,8 -1,1 -0,1 4,1 1,7 2,0	-2,4 0,9 1,1 -2,7 0,8 0,4	1,2 0,0 6,8 -1,0 0,0 -0,7	10,07 -18,17 -12,57 15,23 3,21 11,36
28	2,1 -0,8 3,1 1,3 -0,7 0,9	0,4 1,2 -2,8 -0,8 1,0 0,0	7,7 0,0 -3,6 -2,0 1,5 0,1	-1,9 2,0 1,4 1,2 -8,1 0,0	0,4 -1,6 0,9 -6,8 0,0 1,2	-1,7 0,4 -2,2 0,1 0,3 -0,8	-8,75 4,72 3,07 19,48 -11,57 -2,73
29	2,5 0,0 -1,8 0,6 8,9 -3,3	-1,8 6,2 2,1 0,0 -0,6 2,9	-3,4 2,3 0,7 1,2 1,3 -4,1	0,0 1,1 -1,5 -0,4 -2,0 1,8	2,9 -0,8 2,4 -2,5 0,2 0,0	1,4 -0,4 0,1 5,7 0,7 -2,5	-10,68 10,44 20,68 -7,83 -32,61 7,49
30	-0,7 2,5 -1,1 2,0 -1,2 3,6	-1,1 1,7 0,9 -0,2 -0,8 2,7	1,6 -3,1 2,2 7,8 2,0 -3,3	8,0 0,0 -1,4 2,1 0,9 -1,8	0,1 -1,2 2,6 0,1 -6,6 0,0	-0,3 2,1 -0,7 -1,6 0,1 2,1	21,43 -1,33 -7,79 21,91 4,83 -6,21

Методом Зейделя з точністю до двох знаків після коми розв'яжіть систему лінійних алгебраїчних рівнянь

 , .

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

ЧИСЕЛЬНЕ РОЗВ'ЯЗАННЯ НЕЛІНІЙНИХ АЛГЕБРАЇЧНИХ І ТРАНСЦЕНДЕНТНИХ РІВНЯНЬ ТА ЇХ СИСТЕМ

Загальні положення

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

Нехай дано рівняння

, (1)

де визначена і неперервна в певному скінченому чи нескінченному інтервалі.

Усяке значення , що перетворює функцію на нуль, тобто таке, що , називається коренем рівняння (1) чи нулем функції .

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

відділення коренів, тобто встановлення проміжків , що містять один і тільки один корінь рівняння (1);

уточнення наближених коренів, тобто доведення їх до заданого ступеня точності.

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

Таким чином, якщо існує неперервна похідна і її нулі легко обчислюються, то для відділення коренів рівняння (1) можна вчинити так:

знайти корені рівняння , тим самим ми визначимо кінці інтервалів монотонності функції ;

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

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

Розглянемо кілька прикладів відділення коренів алгебраїчного рівняння:

Приклад 1. Відділити корені рівняння

.

Розв'язок. Область визначення даної функції .

Знайдемо корені рівняння

Одержуємо такі інтервали монотонності функції - , , .

Визначимо знаки функції на кінцях кожного з цих інтервалів:

, , , .

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

Приклад 2. Відділити корені рівняння

.

Розв'язок. Область визначення функції .

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

Уточнити розташування кореня можна за допомогою методів розв'язання, що будуть розглянуті нижче.

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

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

Нехай єдиний корінь рівняння

 (1)

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

. (2)

Початкове наближення і повинне задовольняти умові

. (3)

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

Для оцінки точності наближення можна скористатися формулою

, (4)

де , , (5)

- точне значення кореня.

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

Маємо:

;

;

;

;

.

Довжина отриманого інтервалу

.

Подальше уточнення кореня проведемо методом Ньютона.

Друга похідна на цьому інтервалі більше нуля, перша похідна - менше нуля. За початкове наближення візьмемо лівий кінець інтервалу, тобто . Тоді



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

.

Точність, з якою обчислене перше наближення, недостатня. Тому робимо наступний крок

,

.

Як видно з оцінки похибки другого наближення, ми одержали значення кореня з похибкою, що не перевищує задану.

Корені, розташовані в двох інших інтервалах , знаходяться аналогічно.

Питання для самоперевірки

Сформулюйте постановку задачі, опишіть метод Ньютона.

Наведіть формулу для контролю похибки методу Ньютона.

Дайте геометричну інтерпретацію методу.

В чому полягає умова вибору нульового наближення?

Метод пропорційних частин (хорд)

Розрахункові формули цього методу отримані з таких міркувань. Інтервал , усередині якого розташований корінь рівняння

, (1)

ділимо у відношенні . Це дасть нам наближене значення кореня , де

, . (2)

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

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

Уточнення кореня варто проводити доти, поки не буде досягнута задана точність. Для оцінки точності наближення можна скористатися формулою

 ,

де , , (3)

- точне значення кореня.

Наприклад, знайдемо з точністю до корені рівняння . Виконавши процедуру відділення коренів так, як описано вище (див. Розділ 3. Загальні положення) одержимо три інтервали , , , що містять корінь. Знайдемо корінь, розташований в інтервалі .

Маємо , , .

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

Маємо:

корінь ;

корінь ;

корінь ;

корінь ;

Довжина отриманого інтервалу , тому надалі будемо працювати з цим інтервалом.

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

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

, ,

де , .

Виконуючи розрахунок за цією формулою при , одержимо , .

Обчислимо похибку

 .

Таким чином, уже перше наближення дає значення кореня з потрібною точністю.

Корені, розташовані в двох інших інтервалах , знаходяться аналогічно.

Метод градієнтного спуску

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

(1)

чи в матричній формі

, (2)

де , .

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

. (3)

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

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

, (4)

де вибирається з умови мінімуму .

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

, (5)

де матриця Якобі вектор-функції .

. (6)

Слід зазначити, що ітераційний процес, побудований за методом градієнтного спуску, збігається до точного розв'язку, якщо початкове наближення обране з досить малого околу кореня.

Приклад.

Методом градієнтного спуску приблизно обчислити корені системи

розташовані в околі початку координат.

Розв'язок. Маємо .

Тут і .

Підставляючи нульове наближення, будемо мати:

і

За формулами (5) і (6) одержуємо перше наближення

 і

Аналогічно знаходимо друге наближення .

Маємо:

,

Звідси:

та

Отже,

і

.

Для контролю обчислимо відхил

Питання для самоперевірки

Сформулюйте постановку задачі, опишіть метод розв'язання.

В чому полягає основна ідея методу градієнтного спуска?

Які умови закінчення ітераційного процесу?

Що може відбутися при невдалому виборі нульового наближення?

Дайте геометричну інтерпретацію методу.

Завдання до лабораторної роботи № 7

Методом Ньютона з точністю до обчисліть всі дійсні корені рівняння

.

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

Шифр по вертикалі	0	1	2	3	4	5	6	7	8	9
	1,6	-2,4	0,8	3,6	-1,2	6,4	-2,8	1,2	-0,4	5,2
Кое-фіцієнт	Шифр по горизонталі
	0	1	2	3	4	5	6	7	8	9
	5,1	3,3	-6,3	-1,5	5,7	6,3	1,2	-6,9	5,4	-2,1
	0,2	0	0,8	0	-1,2	0,4	0	-0,6	1,0	0
	-2	3	7	-1	-4	6	-3	8	9	-5

Завдання до лабораторної роботи № 8

Методом хорд із точністю до знайдіть всі дійсні корені рівняння .

Значення коефіцієнтів візьміть з таблиці завдань до лабораторної роботи № 7.

Індивідуальне завдання № 3

Методом градієнтного спуску при заданому початковому наближенні знайдіть наближені корені системи

За умову закінчення ітераційного процесу прийміть .

Варіанти завдань

№ варі-анта	Матриця коефіцієнтів системи	Стовпець вільних членів	Початкове наближення коренів
1	-4,1 0,6 -3,4 0,5	2,4 -1,2 0,4 -2,8	1,3 3,1 -0,1 1,4	-0,7 2,9 -1,1 3,3	-18,12338 4,89797 -30,61106 -3,70831	-1,1 2,2 -3,3 0,0
2	2,4 -1,8 0,4 -3,2	3,1 -4,2 1,9 0,2	-0,8 2,6 -0,5 1,1	1,5 0,7 -2,6 0,9	-4,06003 -16,26196 -6,20337 -3,44529	1,3 -1,1 3,0 0,3
3	1,5 -0,4 2,1 -1,6	0,9 3,6 -0,3 2,5	-2,2 1,7 -2,9 0,7	3,2 -2,8 1,4 -0,1	11,10436 -10,36585 -0,27533 -16,43394	-0,5 1,0 -2,5 3,0
4	-2,8 1,4 -0,1 3,5	0,6 -2,2 1,5 -0,6	1,9 -0,8 2,6 -1,7	-3,1 1,2 -0,9 2,4	-2,74332 6,78768 -0,35866 -7,91985	0,9 2,1 1,6 -0,1
5	1,1 -3,4 2,5 -0,1	4,0 -0,7 1,9 -0,8	-2,3 1,2 -3,0 2,5	-0,5 2,4 0,8 -1,0	7,25672 -9,89640 16,31988 -1,00392	1,6 -0,3 2,5 -1,7
6	4,5 -0,6 1,1 -3,0	1,2 -2,0 0,8 -2,7	-0,6 1,3 -2,1 0,4	2,1 -3,2 0,2 -1,3	19,99632 -12,18632 -14,24772 -22,48474	-2,5 1,6 -0,7 3,3
7	2,4 -1,2 0,1 -2,0	0,9 -3,0 1,8 -0,5	-1,8 -2,3 0,4 1,6	0,2 1,7 -2,2 0,8	0,53615 -10,59093 -5,46305 -5,47281	0,9 -2,3 1,5 -0,8
8	0,8 -1,0 2,1 0,0	-1,1 3,4 -0,6 2,5	-0,4 1,8 -2,0 0,4	2,7 -0,2 1,9 -3,1	17,47656 -33,53480 9,65912 -9,05794	3,1 -0,6 -2,5 2,0
9	-3,4 2,1 0,0 -4,0	0,0 -1,9 3,4 1,9	1,2 -0,4 1,1 -0,2	-2,1 1,6 -0,7 2,4	-3,65902 0,76205 -1,16126 -15,32033	-0,1 0,2 1,8 -1,4
10	0,6 -1,9 2,0 -0,4	-2,1 3,4 -0,8 1,9	3,0 -1,5 2,4 -0,2	-0,1 2,4 -0,5 2,5	-0,57180 6,32067 5,10568 1,30491	-0,2 0,8 -0,3 2,3
11	2,7 -1,5 0,3 1,6	0,6 -1,4 2,2 -0,1	-1,5 -0,8 0,5 -2,4	-0,8 2,0 -1,8 0,5	12,31117 9,43067 18,78237 13,59151	2,6 2,1 -2,9 0,4
12	-0,5 1,0 -2,6 0,8	2,9 -0,8 1,5 -2,4	0,2 -2,5 0,8 1,2	-1,4 0,6 -2,2 0,5	2,02812 6,82786 -5,96430 10,15452	0,7 -2,0 -0,4 1,9
13	-1,2 0,5 -2,4 1,8	0,6 -2,2 1,6 -0,5	-0,5 1,4 -1,7 2,0	1,8 -0,9 2,5 -1,2	-1,89552 -0,51975 -4,79314 17,82578	-1,7 0,9 2,4 -2,6
14	-2,5 0,6 -0,5 1,4	0,2 1,5 -2,4 -3,2	1,8 -0,4 -1,6 0,5	-0,2 1,2 0,4 -2,0	-32,82288 -3,47712 14,80896 18,41504	3,6 -1,4 -0,5 2,5
15	0,9 -1,5 3,0 -2,8	-1,0 2,0 -0,5 1,2	2,2 -1,4 0,8 -1,0	-0,5 0,4 -2,6 0,5	1,24605 -3,02800 1,17404 -8,58912	-2,4 0,6 1,4 -1,6
16	1,9 -0,6 -3,2 1,1	-0,7 2,4 -0,1 0,5	-1,5 0,4 2,5 1,8	2,0 -0,5 1,4 -2,2	4,99613 -9,27880 -43,01664 11,28333	0,9 -2,5 -2,9 1,8
17	0,6 -2,5 1,4 -0,5	-2,8 1,2 -1,5 2,0	3,4 -0,6 2,2 -1,6	0,5 1,8 -0,4 0,2	4,43632 4,15527 9,58114 0,39000	-1,3 0,3 -2,5 0,0
18	1,2 -2,6 0,5 -4,1	-0,5 1,4 -2,1 0,6	2,8 -3,0 1,1 -0,5	-3,2 0,5 -2,6 1,2	-2,42752 3,16474 8,81720 -26,58144	3,2 -1,3 0,4 -2,5
19	1,6 -2,0 0,8 -1,2	-0,5 4,1 -1,5 0,4	3,2 -0,8 2,4 -2,5	2,1 -1,5 0,1 -0,6	-2,90940 -3,30594 -1,82784 -6,36048	-0,7 -2,0 -1,0 0,0
20	-0,4 1,1 -3,5 -4,0	-2,5 3,2 -0,1 0,2	1,8 -2,6 1,4 -0,5	-2,0 0,5 -2,6 1,1	0,42576 -30,21898 -16,27821 -6,42578	3,0 0,4 -2,6 -1,0
21	2,4 1,5 -0,8 1,2	-1,6 0,9 1,1 -2,8	-2,5 1,2 2,4 -0,5	0,7 2,6 -0,5 2,0	-2,28288 1,84254 -7,93506 11,00036	0,6 -1,5 1,1 1,9
22	0,4 -1,5 2,0 0,1	1,9 0,6 -4,1 3,0	-2,4 1,2 0,5 1,4	0,5 2,4 1,6 -2,5	0,30678 -4,21839 -8,45331 1,53789	1,2 2,5 -0,5 1,6
23	1,7 -0,1 2,6 1,5	0,6 2,5 -1,2 0,2	2,1 3,0 2,1 -1,7	-1,5 1,8 -0,5 2,2	-5,66937 -4,99050 13,15266 8,54615	0,7 1,5 -2,2 1,0
24	4,0 2,6 -0,5 1,9	-0,5 1,3 3,0 0,8	2,1 0,6 1,2 -0,5	0,2 -1,5 -2,4 1,2	18,84720 3,40392 -22,47560 -6,43244	-2,5 2,0 2,2 -0,3
25	-2,5 0,8 2,1 1,4	1,6 1,1 -1,2 0,5	2,1 -3,0 0,5 2,2	0,1 1,5 -2,7 0,3	-37,97268 2,22006 6,74865 6,29984	3,5 0,0 -1,0 2,1
26	0,5 3,0 1,9 -2,8	2,7 -2,2 0,5 1,3	-0,1 1,5 2,4 0,7	1,2 2,6 -0,4 2,5	-0,86703 14,43240 -12,59653 -9,05877	1,0 -2,5 0,2 1,5
27	1,1 0,9 -2,0 2,5	-0,6 3,0 0,5 1,1	2,2 -1,6 2,7 0,4	-1,5 2,4 1,1 -1,9	1,68870 10,30449 1,29780 2,89248	2,2 1,4 1,0 0,6
28	2,3 1,7 -0,2 1,4	1,4 0,9 2,6 -0,4	0,7 1,3 1,5 2,0	-1,1 2,2 -0,3 1,5	4,26706 24,95169 -11,60306 6,61972	-0,7 3,5 0,6 -1,5
29	0,9 4,1 -1,1 0,4	-0,9 1,4 2,2 3,0	1,7 -0,4 -3,3 1,5	2,0 2,7 1,1 -2,2	1,28439 10,74725 -17,52025 -8,26131	1,5 -2,0 -1,0 0,7
30	1,2 2,5 0,1 -2,4	-0,7 1,4 3,0 0,7	3,1 -2,1 1,6 2,5	2,4 0,9 -2,2 1,8	1,15208 13,88584 -0,20264 -11,25706	2,5 1,0 1,6 -2,0

НАБЛИЖЕНЕ РОЗВ'ЯЗАННЯ КРАЙОВОЇ ЗАДАЧІ ДЛЯ ЗВИЧАЙНИХ ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ

Метод Гальоркіна

Нехай дана крайова задача

(1)

(2)

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

.

Розглянемо функцію як лінійну комбінацію

(3)

де - невідомі константи.

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

Розглянемо функцію . Вона називається відхилом і отримується при підстановці в рівняння (1) виразу (3). Якщо відхил дорівнює нулю, то маємо випадок точного розв'язоку. Задача розв'язання звичайного диференціального рівняння зводиться до того, щоб відхил був мінімальним. Тоді вираз (3) буде наближеним розв'язком задачі.

Підбір коефіцієнтів породжує різні методи.

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

Умова ортогональності двох функцій має вигляд:

,

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

Приклад. Методом Гальоркіна знайти наближений розв'язок рівняння , що задовольняє крайовим умовам .

Розв'язок. За систему базисних функцій обираємо функції .

Наближений розв'язок задачі шукаємо у вигляді полінома

.

Підставляючи в ліву частину заданого диференціального рівняння, одержуємо відхил:

.

Умови ортогональності функції до функцій приводять до системи

Підставляючи замість її значення, після відповідного інтегрування одержуємо систему

.

Звідси знаходимо: ; , , і, отже, - наближений розв'язок крайової задачі. Похибка наближеного розв'язку залежить від кількості базисних функцій.

Питання для самоперевірки

Які існують типи крайових умов?

В чому полягає метод Гальоркіна? Що таке відхил?

В чому полягають принципи підбору базисних функцій?

Від чого залежить похибка методу Гальоркіна?

Метод кінцевих різниць

Розглянемо лінійне диференціальне рівняння 2-го порядку із змінними коефіцієнтами

(1)

де , , неперервні функції на , - сталі, такі, що . Розіб'ємо відрізок на n рівних частин, тобто одержимо ; побудуємо систему рівновіддалених вузлів

.

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

Введемо позначення , , , .

Одержимо:

 . (2)

Граничні умови запишемо в такому вигляді:

. (3)

Таким чином одержимо систему рівнянь з невідомими. Розв'язуючи цю систему, знайдемо значення функції у відповідних точках.

Приклад. Методом кінцевих різниць знайти розв'язок крайової задачі:

.

Розв'язок. Виберемо крок . Поклавши , з огляду на симетрію рівняння і крайових умов будемо мати . Таким чином, потрібно визначити лише дві ординати: і . Запишемо рівняння (2) у вигляді

.

При , тобто при будемо мати

.

Аналогічно при , тобто при будемо мати

.

З огляду на і використовуючи крайову умову , маємо систему

.

Звідси ; .

Отримані значення занесемо в таблицю

	0	1	2	3	4
	-1	-0,5	0	0,5	1
	0	0,721	0,967	0,721	0

Питання для самоперевірки

Опишіть метод кінцевих різниць.

Яка похибка методу кінцевих різниць?

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