МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ХПИ»

Кафедра «Вычислительной техники и програмирования»

Расчётно–графическое задание

по курсу «Теория алгоритмов и вычислительные методы»

Харьков – 2005

Исходные данные:

Задача 1

Исходные данные вводятся в ЭВМ как абсолютно точные числа и представляются в ней в виде чисел с плавающей точкой с относительной погрешностью в одну миллионную. Введенные данные x₀ и y₀ служат основой формирования двух векторов x=(x₀, x₁, …, x_n) и y=(y₀, y₁, …, y_n) по рекуррентным формулам:

Вычислить скалярное произведение с := (x, y) по алгоритму:

с := 0; i := 0;

while i < n + 1 do c := c + x_i · y_i;

и оценить аналитически и численно инструментальную абсолютную и относительную погрешности.

Решение

Поскольку данные представляются в ЭВМ в виде чисел с плавающей точкой с относительной погрешностью, то

x₀ = x₀(1+δ)

y₀ = y₀(1+δ)

C₀ = x₀y₀(1+δ)

При i = 1

При i = 2

x₂ = x₀³(1+δ)⁵

y₂ = y₀(1+δ)³

C₂ = x₀y₀(1+δ)⁵ + x₀²(1+δ)⁷ + x₀³y₀(1+δ)¹⁰

При i = 3

x₃ = x₀⁴(1+δ)⁷

y₃ = (1+δ)⁵

C₃ = x₀y₀(1+δ)⁶ + x₀²(1+δ)⁸ + x₀³y₀(1+δ)¹¹ + x₀⁴(1+δ)¹⁴

При i = 4

x₄ = x₀⁵(1+δ)⁹

y₄ = y₀(1+δ)⁷

C₄ = x₀y₀(1+δ)⁷ + x₀²(1+δ)⁹ + x₀³y₀(1+δ)¹² + x₀⁴(1+δ)¹⁵ + x₀⁵y₀(1+δ)¹⁸

Выявим закономерность изменения C_i:

При расчете C_n без учета погрешности исходных данных и погрешности вычисления, получим

Обозначим эту сумму как S₁.

Тогда абсолютная погрешность S₂

а относительная погрешность

$IMAGE6$

Оценим инструментально относительную и абсолютные погрешности при n = 10

S₁ = 0.0923071

S₂ = 1.45914·10^-6

S₃ = 1.58075·10^-5

Задача 2

Для функции g(x), заданной своими значениями в шести точках, составить таблицу всех повторных разностей. Преобразовать функцию g(x) с помощью линейного преобразования x = a + b * k в функцию G(k) с целочисленным аргументом k. В качестве проверки правильности заполнения таблицы вычислить аналитически конечную разность Δⁿg(x) = ΔⁿG(k) для n = 5.

Решение

Составим таблицу всех повторных разностей:

$IMAGE7$

Найдем формулу перехода от x к   k:

	$IMAGE8$

Выполним проверку, вычислив аналитически конечную разность

Δⁿg(x)= ΔⁿG(k) для n = 5:

Конечные разности, вычисленные аналитически и таблично Δⁿg(x) = ΔⁿG(k) для n = 5 совпали, следовательно, таблица повторных разностей составлена верно.

Задача 3

Таблично заданную функцию G(k) с целочисленным аргументом представить в виде разложения по факториальным многочленам (z⁽ⁿ⁾ = z · (z-1) · (z-2) · … · (z - n + 1)) и преобразовать его в степенные многочлены G(z) и G(x).

Решение

Представим функцию G(k) в виде разложения по факториальным многочленам:

$IMAGE9$

Преобразуем функцию G(k) в степенной многочлен G(z):

$IMAGE10$

Выполним проверку при k = 1:

$IMAGE11$

0.604=0.604

Так как результаты совпали, значит степенной многочлен G(z) представлен правильно.

Преобразуем функцию G(k) в степенной многочлен G(x). Зная, что получим:

$IMAGE12$

$IMAGE13$

Проверим вычисления при x = 0.8:

$IMAGE14$

0.6045128 ≈ 0.604

Так как результаты совпали, то вычисления сделаны верно.

Задача 4

Вывести аналитическое выражение суммы для функции целочисленного аргумента G(z). Проверить правильность вычисления полученного выражения прямым суммированием табличных значений G(k), k = 0, 1, 2, 3, 4, 5 (m = 5).

Решение.

Для вычисления значения суммы используем функцию G(z) в виде разложения по факториальным многочленам, полученным в задаче 3:

$IMAGE15$

	$IMAGE16$

где

Для проверки, просуммируем значения 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₀; x₁; x₂; x₃] по формуле ее аналитического представления.

Решение

Составим таблицу упорядоченных разделенных разностей для g(x):