Національній технічний університет україни

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

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

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

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

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

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

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

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

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

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

 

 

Київ – 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 Розв’язок систем лінійних рівнянь методом Гауса-Зейделя. 9

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

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

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

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

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

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

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

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

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

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

3.1 Розв’язок диференційних рівнянь методом Ейлера з екстраполяцією Рідчардсона. 16

3.1.1 Завдання: виконати один крок метода Ейлера для диференційного рівняння. 16

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

Рекомендована література. 19

 

 

Вступ

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

 

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

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

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

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

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

 

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

 

Розділ 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 – розмір матриці А.

 

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

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

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

Системи нелінійних рівнянь розв’язують аналогічно до нелінійних рівнянь, однак маємо замість однієї функції вектор функцій, замість однієї невідомої – вектор невідомих: F(x) = 0.

Ітераційна формула та ж:

Однак похідна у даному випадку буде якобіаном J(x_n), і операція ділення на матрицю замінюється операцією знаходження оберненої матриці.

Фактично, необхідно розв’язати систему лінійних рівнянь J(x_n)∙ ∆x_n= –F(x_n) (щоб не шукати обернену матрицю).

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

Рекомендована література

1. Фельдман Л.П., Петренко А.І., Дмитрієва О. А. Чисельні методи в інформатиці (підручник). – К.: Видавнича група BHV, 2006. – 480 с.

2. Бахвалов Н.С. Численные методы. – М.: Наука, 1978, – Т.1. – 632 с.

3. Ортега Д., Пул У. Введение в численные методы решения дифференциальных равнений. – М.: Наука, 1986. – 288 с.

4. Форсайд Д., Малькольм Н., Моулер К. Машинные методы математических вычислений. – М.: Мир, 1980 – 324 с.

 

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

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