МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ «ХПІ»
Кафедра «Обчислювальної техніки та програмування»
Розрахунково-графічне завдання
з курсу «Теорія алгоритмів та обчислювальні методи»
Харків - 2005
Вихідні дані:
Варіант № | y 0 | y 1 | y 2 | y 3 | y 4 | y 5 | h | x 0 |
64 | -0.02 | 0.604 | 0.292 | -0.512 | -1.284 | -2.04 | 0.5 | 0.3 |
Задача 1
Вихідні дані вводяться в ЕОМ як абсолютно точні числа і представляються в ній у вигляді чисел з плаваючою точкою з відносною похибкою в одну мільйонну. Введені дані x 0 і y 0 служать основою формування двох векторів x = (x 0, x 1, ..., x n) і y = (y 0, y 1, ..., y n) по рекурентним формулами:
Обчислити скалярний твір з: = (x, y) за алгоритмом:
з: = 0; i: = 0;
while i <n + 1 do c: = c + x i · y i;
і оцінити аналітично і чисельно інструментальну абсолютну і відносну похибки.
Рішення
Оскільки дані представляються в ЕОМ у вигляді чисел з плаваючою точкою з відносною похибкою, то
x 0 = x 0 (1 + δ)
y 0 = y 0 (1 + δ)
C 0 = x 0 y 0 (1 + δ)
При i = 1
При i = 2
x 2 = x 0 3 (1 + δ) 5
y 2 = y 0 (1 + δ) 3
C 2 = x 0 y 0 (1 + δ) 5 + x 0 2 (1 + δ) 7 + x 0 3 y 0 (1 + δ) 10
При i = 3
x 3 = x 0 4 (1 + δ) 7
y 3 = (1 + δ) 5
C 3 = x 0 y 0 (1 + δ) 6 + x 0 2 (1 + δ) 8 + x 0 3 y 0 (1 + δ) 11 + x 0 4 (1 + δ) 14
При i = 4
x 4 = x 0 5 (1 + δ) 9
y 4 = y 0 (1 + δ) 7
C 4 = x 0 y 0 (1 + δ) 7 + x 0 2 (1 + δ) 9 + x 0 3 y 0 (1 + δ) 12 + x 0 4 (1 + δ) 15 + x 0 5 y 0 (1 + δ) 18
Виявимо закономірність зміни C i:
При розрахунку C n без урахування похибки вихідних даних і похибки обчислення, отримаємо
Позначимо цю суму як S 1.
Тоді абсолютна похибка S 2
а відносна похибка
Оцінимо інструментально відносну і абсолютні похибки при n = 10
S 1 = 0.0923071
S 2 = 1.45914 · 10 -6
S 3 = 1.58075 · 10 -5
Задача 2
Для функції g (x), заданої своїми значеннями в шести точках, скласти таблицю всіх повторних різниць. Перетворити функцію g (x) за допомогою лінійного перетворення x = a + b * k у функцію G (k) з цілочисельним аргументом k. Як перевірки правильності заповнення таблиці обчислити аналітично кінцеву різниця Δ n g (x) = Δ n G (k) для n = 5.
Рішення
Складемо таблицю всіх повторних різниць:
k | x | y | Δ y | Δ 2 y | Δ 3 y | Δ 4 y | Δ 5 y |
0 | 0.3 | 0.02 | -1. 576 | 0. 044 | - 0. 136 | 0. 66 | -0.54 |
1 | 1. 1 | -1. 556 | - 1. 532 | -0. 0 92 | 0.524 | 0. 12 | - |
2 | 1. 9 | -3. 088 | - 1. 62 4 | 0. 4 32 | 0. 644 | - | - |
3 | 2. 7 | -4. 7 грудень | - 1. 19 лютого | 1 .0 7 6 | - | - | - |
4 | 3. 5 | -5. 904 | -0. 11 червня | - | - | - | - |
5 | 4. 3 | - 6 .0 2 | - | - | - | - | - |
Н айдем формулу переходу від x до k:
У иполнім перевірку, обчисливши аналітично кінцеву різниця
Δ n g (x) = Δ n G (k) для n = 5:
Кінцеві різниці, обчислені аналітично і таблично Δ n g (x) = Δ n G (k) для n = 5 збіглися, отже, таблиця повторних різниць складена вірно.
З Адачі 3
Т аблічно задану функцію G (k) з цілочисельним аргументом представити у вигляді розкладання по факторіальних многочленів (z (n) = z · (z -1) · (z -2) · ... · (z - n + 1)) і перетворити його в статечні многочлени G (z) і G (x).
Рішення
Уявімо функцію G (k) у вигляді розкладання по факторіальних и м многочленів:
П реобразуем функцію G (k) в степеневий многочлен G (z):
У иполнім перевірку при k = 1:
0.604 = 0.604
Так як результати збіглися, значить статечної многочлен G (z) представлений правильно.
Перетворимо функцію G (k) в степеневий многочлен G (x). Знаючи, що отримаємо:
П ровері обчислення при x = 0.8:
0.6045128 ≈ 0.604
Так як результати збіглися, то обчислення зроблені вірно.
Задача 4
Вивести аналітичний вираз суми для функції цілочисельного аргументу G (z). Перевірити правильність обчислення отриманого виразу прямим підсумовуванням табличних значень G (k), k = 0, 1, 2, 3, 4, 5 (m = 5).
Рішення.
Для обчислення значення суми використовуємо функцію G (z) у вигляді розкладання по факторіальних многочленів, отриманим в задачі 3:
де
Д ля перевірки, підсумуємо значення G (k) з таблиці:
-0.02 + 0.604 + 0.292 - 0.512 - 1.284 - 2.04 = - 2.96
- 2.96 = - 2.96
Так як результати обчислення аналітичного вираження і суми табличних значень G (k) збіглися, значить аналітичний вираз для суми виведено правильно.
Задача 5
З залишити таблицю упорядкованих розділених різниць для g (x). Перевірити правильність таблиці для розділеної різниці [x 0; x 1; x 2; x 3] за формулою її аналітичного уявлення.
Рішення
Складемо таблицю упорядкованих розділених різниць для g (x):
x i | g (x i) | [X i; x i +1] | [X i; x i +1; x i +2] | [X i; x i +1; x i +2; x i +3] | [X i; x i +1; x i +2; x i +3; x i +4] | [X i; x i +1; x i +2; x i +3; x i +4; x i +5] |
0.3 | -0.02 | 1.248 | -1.872 | 0.592 | 0.0533333 | -0.1567999 |
0.8 | 0.604 | -0.624 | -0.984 | 0.6986666 | -0.3386666 | - |
1.3 | 0.292 | -1.608 | 0.064 | -0.0213333 | - | - |
1.8 | -0.512 | -1.544 | 0.032 | - | - | - |
2.3 | -1.284 | -1.512 | - | - | - | - |
2.8 | -2.04 | - | - | - | - | - |
Д ля перевірки правильності заповнення таблиці розділених різниць, обчислимо розділену різниця п'ятого порядку за формулою її аналітичного подання:
Так як результати обчислень співпали, значить, таблиця розділених різниць складена правильно.
Задача 6
Отримати інтерполяційні многочлени Лагранжа і Ньютона, що проходять через перші чотири точки таблично заданої функції G (x), і порівняти їх статечні подання.
Рішення
Для знаходження інтерполяційного многочлена Лагранжа використовуємо формулу
де n = 3.
П роведем перевірку обчислень, підставивши x = 0.8 в інтерполяційний многочлен Лагранжа, отримаємо y 1 = 0.604
І нтерполяціонний многочлен Ньютона знаходиться за формулою:
l n (x) = g 0 + (xx 0) [x 0; x 1] + (xx 0) (xx 1) [x 0; x 1; x 2] + ... +
+ (Xx 0) (xx 1) ∙ ... ∙ (xx n-1) [x 0; x 1; x 2; ...; x n]
П одставів в формулу g i і x i отримаємо:
Інтерполяційні многочлени Ньютона і Лагранжа збігаються.
П роведем перевірку обчислень, підставивши x = 0.8 в інтерполяційний многочлен Ньютона, отримаємо y 1 = 0.604
Завдання 7.
У ивесті вирази для обчислення другої похідної в точці x = x 3 у вигляді опцій:
де Δ n g (0) і g (x n) для n = 0,1, ..., 5 відповідно значення різниць в точці x = x 0 і ординати g (x n) = g n з завдання N2. Значення похідної обчислені за виведеним формулам, порівняти з обчисленим значенням похідної, знайденої шляхом диференціювання інтерполяційного многочлена G (x):
Рішення
Д ля обчислення похідної скористаємося оператором диференціювання:
У ираженіе для обчислення похідної в точці x 0 має вигляд:
Д ля того, щоб перетворити його до вираження для обчислення похідної в точці x 3, застосуємо оператор зсуву:
Д ля того, щоб перейти від функції до функції скористаємося формулою:
П олучім вирази для Δ 2 y 0:
Δ 5 y 0 =-y 0 + 5y 1 - 10y 2 + 10y 3 - 5y 4 + y 5
Δ 4 y 0 = y 0 - 4y 1 + 6y 2 - 4y 3 + y 4
Δ 3 y 0 =-y 0 + 3y 1 - 3y 2 + y 3
Δ 2 y 0 = y 0 - 2y 1 + y 2
Підставимо ці значення у функцію:
З одно це значення з обчисленим значенням похідної шляхом диференціювання інтерполяційного многочлена G (x):
при x 3 = 1.8
З начення похідної рівні, отже, обчислення зроблені вірно.
Задача 8
Методом найменших квадратів для таблично заданої g (x) отримати апроксимуючі статечні поліноми нульової, першої, другої та третьої ступенів (P i (x), i = 0, 1, 2, 3) і зобразити їх на одному графіку.
Рішення.
Складемо таблицю ступенів x і xy
i | x | y | x 2 | x 3 | x 4 | x 5 | x 6 | xy | x 2 y | x 3 y |
1 | 0.3 | -0.02 | 0.09 | 0.027 | 0.0081 | 0.00243 | 0.000728999 | -0.006 | -0.0018 | -0.00054 |
1 | 0.8 | 0.604 | 0.64 | 0.512 | 0.4096 | 0.32768 | 0.262144 | 0.4832 | 0.38656 | 0.309247 |
1 | 1.3 | 0.292 | 1.69 | 2.197 | 2.8561 | 3.71293 | 4.8268 | 0.3796 | 0.493479 | 0.641523 |
1 | 1.8 | -0.512 | 3.24 | 5.832 | 10.4976 | 18.8956 | 34.0122 | -0.9216 | -1.65888 | -2.98598 |
1 | 2.3 | -1.284 | 5.29 | 12.167 | 27.9840 | 64.3634 | 148.035 | -2.9532 | -6.79236 | -15.6224 |
1 | 2.8 | -2.04 | 7.84 | 21.952 | 61.4656 | 172.103 | 481.89 | -5.712 | -15.9936 | -44.782 |
6 | 9.3 | -2.96 | 18.79 | 42.687 | 103.22 | 259.405 | 669.026 | -8.73 | -23.5666 | -62.4401 |
З залишимо системи рівнянь:
Про ткуда a 0 = -0.93621; a 1 = 3.89576; a 2 = -2.8954; a 3 = 0.488001
А ппроксімірующій статечної поліном 3-го ступеня має вигляд:
P 3 (x) = -0.93621 + 3.89576x - 2.8954x 2 + 0.488001x 3
Про ткуда a 0 = -0.0710314; a 1 = 0.989486; a 2 = -0.624589;
А ппроксімірующій статечної поліном 2-го ступеня має вигляд:
P 2 (x) = -0.0710314 + 0.989486x - 0.624589x 2
Про ткуда a 0 = 0.974118; a 1 = -0.946742;
А ппроксімірующій статечної поліном 1-го ступеня має вигляд:
P 1 (x) = 0.974118 - 0.946742x
6a 0 = -2.96
Про ткуда a 0 = -0.493333;
А ппроксімірующій статечної поліном 0-го ступеня має вигляд:
P 0 (x) = -0.0493333
Зобразимо отримані поліноми на графіку:
Задача 9
Для апроксимує полінома третього ступеня P 3 (x) отримати аналітичні вирази Δ n P 3 (x), n = 0, 1, 2, 3, 4 і всі кінцево-різницеві різницеві криві зобразити на одному графіку.
Рішення
Про бозначім на графіці все кінцево-різницеві криві:
Задача 10
Вивести квадратурні формули для обчислення визначених інтегралів з межами [0, 1] і [-1, 1] від подинтегральних функцій f (t), що належать класу статечних многочленів ступенів 0, 1, 2, 3. Висновок виконати для трьох випадків використання в квадратурних формулах чисельних значень подинтегральних функцій:
в) задані значення функції в точках, які забезпечують отримання формул найвищої алгебраїчної ступеня точності.
Рішення
Значення певного інтеграла знайдемо, виходячи з формули:
де w 1, w 2 - деякі коефіцієнти
t 1, t 2 - точки, плаваючі всередині інтервалу інтегрування.
Складемо систему рівнянь
w (t) = (tt 1) (tt 2) = C 0 + C 1 t + C 2 t 2 = 0
C 2 = 1
Домножити рівняння на відповідні коефіцієнти отримаємо:
2C 0 + 2 / 3 = w 1 (C 0 + C 1 t 1 + t 1 2) + w 2 (C 0 + C 1 t 1 + t 2 2)
2 C 0 + 2 / 3 = 0
C 0 = -1 / 3
Підставляючи отримані значення в першу систему, одержимо:
Квадратурна формула:
Задача 11
За допомогою квадратурних формул, отриманих в задачі 10, обчислити визначений інтеграл від статечного подання інтерполяційного многочлена Лагранжа (Ньютона), отриманого в задачі № 6 в межах від 0 до x x 0 +3 h, і порівняти його з обчисленим значенням аналітично певного інтеграла за первісних многочлена.
Рішення
Використовуємо статечне уявлення інтерполяційного многочлена Лагранжа з завдання 6
Для переходу до інтегралу з канонічною формою використовуємо лінійне перетворення: x = α + βt.
Складемо систему рівнянь:
Підставивши x = 1.05 + 0.75 t, отримаємо многочлен Лагранжа від змінної t:
L (t) = 0.24975 t 3 - 0.80325 t 2 - 0.49575 t + 0.537253
Враховуючи, що dx = βdt, отримаємо:
Застосуємо квадратурну формулу, отриману в задачі № 10
Для порівняння обчислимо аналітично значення інтеграла:
Так як результати збіглися, значить, обчислення зроблені вірно.
Задача 12
Оцінити похибку певного інтеграла від функції sin (x) в межах [0,2 / 3 π] по квадратурної формулою найвищої алгебраїчної ступеня точності, отриманої в завданні № 10в, в порівнянні з аналітично точним. Виконати те ж саме над усіченим статечним рядом, що представляє sin (x), в який входить x зі ступенем не вище третьої.
Рішення
Перейдемо від меж [0,2 / 3 π] до межі [-1,1]: для цього скористаємося лінійним перетворенням x = α + βt. Скласти систему
Враховуючи, що dx = βdt, отримаємо:
Застосуємо квадратурну формулу:
Обчислимо аналітично:
Знайдемо похибка обчислення:
Проробимо ті ж операції над усіченим статечним рядом, що представляє sin (x):
Перейдемо від меж [0, 2 π / 3] до меж [-1, 1], для цього використовуємо лінійне перетворення x = α + βt. Складемо систему рівнянь:
Враховуючи, що dx = βdt, одержимо
Застосуємо квадратурної формули, одержимо
Знайдемо похибка обчислення
Задача 14
Статечними поліномами Чебишева T i щодо змінної x (| x | <1) є рішеннями лінійного різницевого рівняння другого порядку:
T i +2 - 2x T i +1 + T i = 0,
з початковими умовами T 0 = 1 і T 1 = x.
Знайти аналітичний вираз і обчислити значення полінома Чебишева i-го ступеня, якщо і i = 4. Перевірити обчислення безпосередньо за заданою рекуррентной формулою. Знайти положення нулів і екстремумів у многочленів Чебишева у загальному вигляді та для заданих вище x і i. Оцінити модуль максимально можливого значення полінома в точках екстремумів.
Рішення.
Виходячи з того, що
x i = | y i | треба знайти T 4 тобто для i = 4
З T i +2 - 2 xT i +1 + T i = 0 слід, що
T 2 = 2xT 1 - T 0
T 3 = 2xT 2 - T 1 = 2x (2xT 1 - T 0) - T 1
T 4 = 2xT 3 - T 2 = 2x (2x (2xT 1 - T 0) - T 1) - 2xT 1 + T 0 = 8x 3 T 1 - 4x 2 T 0 - 4xT 1 + T 0
Підставимо значення T 0 = 1 і T 1 = x
T 4 = 8x 4 - 4x 2 - 4x 2 + 1 = 8x 4 - 8x 2 + 1
Знайдемо значення x:
T 4 = 0.99980
Перевіримо за заданою рекуррентной формулою:
T 2 = 2.0 .00490 · 0.00490 - 1 = -0.9999
T 3 = 2.0 .00490 · (-0.9999) - 0.00490 = -0.01469
T 4 = 2.0 .00490 · (-0.01469) + 0.9999 = 0.99980
Нулі функції знаходяться, як рішення біквадратного рівняння:
8 x 4 - 8 x 2 + 1 = 0, де
x 1 = 0.9238795
x 2 = -0.9238795
x 3 = 0.3826834
x 4 = -0.3826834
Щоб знайти екстремуми знайдемо
Задача 16
Вирівнювання по всій довжині з плином часу температури T (x, t) на тонкому однорідному добре теплоізольованому стержні описується диференціальним рівнянням в приватних похідних з початковим розподілом температури (в градусах Цельсія) по довжині стрижня в 6 рівномірно розташованих з кроком h точках.
T (x 0, 0) = T 0, T (x 1, 0) = T 1, ..., T (x 5, 0) = T 5; (T i = 100 · y i ˚ C).
На кінцях стрижня в точках x -1 і x 6 утримується нульова температура.
Застосовуючи звичайно-різницеве подання похідних по просторової змінної x, звести рівняння в приватних похідних до системи диференціальних рівнянь в звичайних похідних щодо температури T.
Рішення.
Отримуємо систему диф. рівнянь:
Враховуючи початкові умови, одержимо систему рівнянь:
Завдання 17.
Використовуючи метод Ньютона-Рафсона, знайти з відносною похибкою в одну мільйонну нуль многочлена Чебишева T i (x), отриманого в задачі 14. В якості початкового наближення до кореня взяти
Як x i беруться | y i | з таблиці вихідних даних.
Рішення.
З Задача 14 візьмемо поліном Чебишева T 4 = 8x 4 - 8x 2 + 1. В якості початкового наближення до кореня візьмемо x поч, обчислена за формулою
Т.к. 8x 4 - 8x 2 + 1 = 0, то можемо сказати, що f (x нач + α) = 0
Скористаємося DERIVE для знаходження кореня з необхідною точністю:
отримаємо такі значення: 0.38234, 0.382689, 0.382683, 0.382683, 0.382683.
На третій ітерації виходять значення кореня з потрібною точністю.
Задача 19
Швидкість зміни змінної x (t) у часі дорівнює функції від цієї змінної f (x). Знайти аналітичний вираз останньої від часу, починаючи з t = 0, якщо в початковий момент x (0) = 0. Як f (x) взяти статечної многочлен P 2 (x), отриманий в задачі 8. Протабулювати отримане рішення з кроком h = 0.1 в інтервалі [0, 0.5].
Рішення
P 2 (x) = -0.0710314 + 0.989486x - 0.624589x 2 = f (x)
Виходячи з початкових умов, тому що dx / dt = f (x), маємо
Т.к. x = F (t), то:
Протабуліруем x (t) на інтервалі [0; 0.5] c кроком h = 0.1:
t = 0 x = 0
t = 0.1 x = -0.0622648
t = 0.2 x = -0.137833
t = 0.3 x = -0.230872
t = 0.4 x = -0.347464
t = 0.5 x = -0.496850
Задач 20
Методом Ейлера в інтервалі [0, 0.5] з кроком h = 0.1 одержати рішення нелінійного диференціального рівняння:
dx / dt = a + bx + cx 2,
x (0) = 0
Коефіцієнти a, b, c взяти з P 2 (x), отриманого в задачі 8.
Рішення
y = P 2 (x)
P 2 (x) = -0.0710314 + 0.989486x - 0.624589x 2
Загальна формула для вирішення
x = x 0 + h · P 2 (x 0, t 0)
x 1 = 0 + 0.5 · (-0.0710314) = -0.0355156
x 2 = -0.0355156 + 0.5 · (-0.0710314 + 0.989486 (-0.0355156) 1 -
-0.624589 · (-0.0355156 2) = -0.053854
x 3 = -0.053854 + 0.5 · (-0.0710314 + 0.989486 (-0.053854) 1 -
- 0.624589 (-0.053854) 2) = -0.0636315
x 4 = -0.0636315 + 0.5 · (-0.0710314 + 0.989486 (-0.0636315) 1 -
-0.624589 (-0.0636315) 2) = -0.0689304
x 5 = -0.0689304 + 0.5 (-0.0710314 + 0.989486 (-0.0689304) 1 -
-0. 0.624589 (-0.0689304) 2) =-- 0.071827
Завдання 23
Перевірити задану систему з трьох векторів на лінійну залежність. При виявленні лінійної залежності поміняти місцями перші компоненти векторів x1, x2 і виконати повторну перевірку. З вихідних даних вектори формуються так:
x 1 = (y 0, y 1, y 2); x 2 = (y 3, y 4, y 5); x 3 = (h, x 0, 0).
На базі лінійно незалежної системи векторів x 1, x 2, x 3 методом Грама-Шмідта побудувати ортонормированном систему трьох векторів:
y 1 = (y 11, y 21, y 31); y 2 = (y 12, y 22, y 32); y 3 = (y 13, y 23, y 33).
На основі отриманої системи векторів сформувати квадратну матрицю T = (y 1, y 2, y 3). Обчислити det (T) і отримати матриці - зворотний T -1 і транспоновану T '. Знайти твір T 1 · T, T · T '. Зробити висновки про властивості матриці T.
Рішення
Вихідні вектори x 1 = (-0.02,0.604,0.292); x 2 = (-0.512, -1.284, -2.04);
x 3 = (0.5,0.3,0).
Складемо матрицю і перевіримо її на лінійну залежність:
det (A · A T) = 0.23591> 0, значить система лінійно незалежна.
Знайдемо вектори v 1, v 2, v 3
v 1 = x 1
v 2 = x 2 + a 21 · v 1
v 3 = x 3 + a 32 · v 2 + a 31 · v 1
v 1 = (-0.02, 0.604, 0.292);
v 2 = (-0.572423, 0.54078, -1.15782);
v3 = (0.471405, 0.104651, -0.184183).
Матриця T:
det (T) = -1
Ортонормированном матриця T складається із власних векторів. Визначник матриці T дорівнює 1. Якщо транспонувати ортогональну матрицю то вона дорівнюватиме зворотною. T '= T -1. Це означає, що якщо помножити T · T '= E - отримаємо одиничну матрицю.
Завдання 24
Вважаючи числа -1, -2, -3 власними значеннями, а вектори у 1, у 2, у 3 з завдання 23 - власними векторами деякої матриці А, знайдіть проектори цієї матриці (Р 1, Р 2, Р 3), саму матрицю А та їй зворотний А -1. Отримати характеристичне рівняння матриці А і підтвердити правильність усіх проміжних обчислень.
Рішення
Знайдемо проектори матриці А:
Знайдемо обернену матрицю А -1:
Характеристичне рівняння матриці А має вигляд:
-X 3-6x 2-11x-6 = 0;
Коріння характеристичного рівняння - власні значення матриці
x 1 = 1; x 2 = -2; x 3 = -3
Завдання 25
Вирішити систему алгебраїчних рівнянь А · x = b, де А-матриця коефіцієнтів з завдання 24, x = (x1, x2, x3) - вектори рішення, b = (3, 2, 1) - вектор правих частин. Рішення отримати, використовуючи зворотний матрицю, отриману з завдання 24.
Рішення