НАЦІОНАЛЬНІЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

„КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Інститут прикладного системного аналізу

Кафедра системного проектування

д.т.н, проф. Петренко Анатолій Іванович

к.т.н. Корначевський Ярослав Ілліч

Методичний посібник

для контролю залишкових знань по курсу

“Чисельні методи в інформатиці”

Рекомендовано кафедрою системного проектування _________________________ (протокол №, дата) Завідувач кафедри Петренко А.І. (підпис) (ініціали, прізвище)

Київ – 2008

Зміст

Вступ 3

Розділ 1. Розв’язок систем лінійних рівнянь 3

1.1 Розв’язок систем лінійних рівнянь методом LU 3

1.1.1 Завдання: виконати LU-розклад матриці 4

1.1.2 Завдання для самостійної роботи 5

1.1.3 Завдання: розв'язати систему лінійних рівнянь за відомим LU-розкладом 6

1.1.4 Завдання для самостійної роботи 6

1.2 Розв’язок систем лінійних рівнянь методом Гауса-Зейделя 10

1.2.1 Завдання: виконати одну ітерацію для знаходження розв'язку системи лінійних рівнянь методом Гауса-Зейделя 11

1.2.2 Завдання для самостійної роботи 11

Розділ 2. Розв’язок нелінійних рівнянь 15

2.1 Розв’язок нелінійних рівнянь методом Ньютона 15

2.1.1 Завдання: виконати один крок метода Ньютона для нелінійного рівняння 15

2.1.2 Завдання для самостійної роботи 15

2.2 Розв’язок систем нелінійних рівнянь методом Ньютона 17

2.2.1 Завдання: сформувати систему лінійних рівнянь для розв'язку системи нелінійних рівнянь 17

2.2.2 Завдання для самостійної роботи 18

Розділ 3. Розв’язок диференційних рівнянь 21

3.1 Розв’язок диференційних рівнянь методом Ейлера 21

3.1.1 Завдання: виконати один крок метода Ейлера з екстраполяцію Річардсона для диференційного рівняння 21

3.1.2 Завдання для самостійної роботи 22

Розділ 4. Рекомендована література 25

Вступ

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

Курс “Чисельні методи в інформатиці” умовно можна розділити на три великі частини:

• розв’язок систем лінійних рівнянь;

• розв’язок нелінійних рівнянь;

• розв’язок диференційних рівнянь.

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

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

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

1.1Розв’язок систем лінійних рівнянь методом lu

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

Нехай ми маємо систему Ax=b. Ведемо заміну A=LU, тут L та U відповідно нижня та верхня трикутні матриці. Тоді LUx=b. Якщо ми зможемо розкласти матрицю A на добуток LU, тоді розв’язок можна виконати в дві прості операції. Спочатку введемо заміну Ux=y, тоді маємо Ly=b. L та b відомі, отже можна легко знайти y, оскільки матриця L – трикутна. Далі повертаємося до виразу Ux=y, і нарешті знаходимо x. Формули для обчислення y та x приведено нижче:

Для виконання LU-розкладу необхідно скористатися наступними формулами:

тут а, u та l – елементи матриць A, L та U;

n – розмір матриці А.

Для засвоєння методу розглянемо приклад.

1.1.1Завдання: виконати lu-розклад матриці

3	2	4	1
6	2	11	3
12	14	6	4
3	8	–3	–11

Будемо записувати матриці L та U разом.

1. Рахуємо перший рядок матриці U:

U₁₁ = A₁₁

U₁₂ = A₁₂

U₁₃ = A₁₃

U₁₄ = A₁₄

3	2	4	1

2. Рахуємо перший стовпчик матриці L:

L₂₁ = A₂₁/U₁₁

L₃₁ = A₃₁/U₁₁

L₄₁ = A₄₁/U₁₁

3	2	4	1
2
4
1

3. Рахуємо другий рядок матриці U:

U₂₂ = A₂₂ – L₂₁∙U₁₂

U₂₃ = A₂₃ – L₂₁∙U₁₃

U₂₄ = A₂₄ – L₂₁∙U₁₄

3	2	4	1
2	–2	3	1
4
1

4. Рахуємо другий стовпчик матриці L:

L₃₂ = (A₃₂ – L₃₁∙U₁₂)/U₂₂

L₄₂ = (A₄₂ – L₄₁∙U₁₂)/U₂₂

3	2	4	1
2	–2	3	1
4	–3
1	–3

5. Рахуємо третій рядок матриці U:

U₃₃ = A₃₃ – L₃₁∙U₁₃ – L₃₂∙U₂₃

U₃₄ = A₃₄ – L₃₁∙U₁₄ – L₃₂∙U₂₄

3	2	4	1
2	–2	3	1
4	–3	–1	3
1	–3

6. Рахуємо третій стовпчик матриці L:

L₄₃ = (A₄₃ – L₄₁∙U₁₃ – L₄₂∙U₂₃)/U₃₃

3	2	4	1
2	–2	3	1
4	–3	–1	3
1	–3	–2

7. Рахуємо четвертий рядок матриці U:

U₄₄ = A₄₄ – L₄₁∙U₁₄ – L₄₂∙U₂₄ – L₄₃∙U₃₄

3	2	4	1
2	–2	3	1
4	–3	–1	3
1	–3	–2	–3

Маємо відповідь – зверху матриця U, знизу – матриця L.