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

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

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

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

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

Харьков — 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₂.

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

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

S₁ = 0.923 071.

S₂ = 1.45 914· 10^-6.

S₃ = 1.58 075· 10^-5.

Задача 2.

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

Решение.

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

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

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

?ⁿ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) в виде разложения по факториальным многочленам:

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

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

0.604=0.604.

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

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

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

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

Решение.

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

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

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

Задача 6.

Получить интерполяционные многочлены Лагранжа и Ньютона, проходящие через первые четыре точки таблично заданной функции G (x), и сравнить их степенные представления.

Решение.

Для нахождения интерполяционного многочлена Лагранжа используем формулу.

где n = 3.

Проведем проверку вычислений, подставив x=0.8 в интерполяционный многочлен Лагранжа, получим y₁=0.604.

Интерполяционный многочлен Ньютона находится по формуле:

l_n(x) = g₀ + (x-x₀)[x₀;x₁] + (x-x₀)(x-x₁)[x₀;x₁;x₂] + … +.

+(x-x₀)(x-x₁)• …•(x-x_n-1)[x₀;x₁;x₂;…;x_n].

Подставив в формулу g_i и x_i получим:

Интерполяционные многочлены Ньютона и Лагранжа совпадают.

Проведем проверку вычислений, подставив x=0.8 в интерполяционный многочлен Ньютона, получим y₁=0.604.

Задача 7..

Вывести выражения для вычисления второй производной в точке x=x₃ в виде функций:

где ?ⁿg (0) и g (x_n) для n = 0,1,…, 5 соответственно значения разностей в точке x = x₀ и ординаты g (x_n) = g_n из задачи N2. Значения производной вычисленные по выведенным формулам, сравнить с вычисленным значением производной, найденной путем дифференцирования интерполяционного многочлена G (x):

Решение.

Для вычисления производной воспользуемся оператором дифференцирования:

Выражение для вычисления производной в точке x₀ имеет вид:

Для того, чтобы преобразовать его к выражению для вычисления производной в точке x₃, применим оператор сдвига:

Для того, чтобы перейти от функции к функции воспользуемся формулой:

Получим выражения для ?²y₀:

?⁵y₀ = -y₀ + 5y₁ — 10y₂ + 10y₃ — 5y₄ + y₅.

?⁴y₀ = y₀ — 4y₁ + 6y₂ — 4y₃ + y₄.

?³y₀ = -y₀ + 3y₁ — 3y₂ + y₃.

?²y₀ = y₀ — 2y₁ + y₂.

Подставим эти значения в функцию:

Сравним это значение с вычисленным значением производной путем дифференцирования интерполяционного многочлена G (x):

при x₃ = 1.8.

Значения производной равны, следовательно, вычисления сделаны верно.

Задача 8.

Методом наименьших квадратов для таблично заданной g(x) получить аппроксимирующие степенные полиномы нулевой, первой, второй и третьей степеней (P_i(x), i = 0, 1, 2, 3) и изобразить их на одном графике.

Решение..

Составим таблицу степеней x и xy.

Составим системы уравнений:

Откуда a₀ = -0.93 621; a₁ = 3.89 576; a₂ = -2.8954; a₃ = 0.488 001.

Аппроксимирующий степенной полином 3-й степени имеет вид:

P₃(x) = -0.93 621 + 3.89576x — 2.8954x² + 0.48 8001x³.

Откуда a₀ = -0.710 314; a₁ = 0.989 486; a₂ = -0.624 589;

Аппроксимирующий степенной полином 2-й степени имеет вид:

P₂(x) = -0.710 314 + 0.98 9486x — 0.62 4589x².

Откуда a₀ = 0.974 118; a₁ = -0.946 742;

Аппроксимирующий степенной полином 1-й степени имеет вид:

P₁(x) = 0.974 118 — 0.94 6742x.

6a₀ = -2.96.

Откуда a₀ = -0.493 333;

Аппроксимирующий степенной полином 0-й степени имеет вид:

P₀(x) = -0.493 333.

Изобразим полученные полиномы на графике:

Задача 9.

Для аппроксимирующего полинома третьей степени P₃(x) получить аналитические выражения ?ⁿP₃(x), n = 0, 1, 2, 3, 4 и все конечно-разностные разностные кривые изобразить на одном графике.

Решение.

Обозначим на графике все конечно-разностные кривые:

Задача 10.

Вывести квадратурные формулы для вычисления определенных интегралов с пределами [0, 1] и [-1, 1] от подынтегральных функций f (t), принадлежащих классу степенных многочленов степеней 0, 1, 2, 3. Вывод проделать для трех случаев использование в квадратурных формулах численных значений подынтегральных функций:

в) заданы значения функции в точках, обеспечивающих получение формул наивысшей алгебраической степени точности.

Решение

Значение определенного интеграла найдем, исходя из формулы:

где w₁, w₂ — некоторые коэффициенты.

t₁, t₂ — точки, плавающие внутри интервала интегрирования.

Составим систему уравнений.

w (t) = (t-t₁)(t-t₂) = C₀ + C₁t + C₂t² = 0.

C₂ = 1.

Домножив уравнения на соответствующие коэффициенты получим:

2C₀ + 2/3 = w₁ (C₀ + C₁t₁ + t₁²) + w₂ (C₀ + C₁t₁ + t₂²).

2C₀+ 2/3 = 0.

C₀ = -1/3.

Подставляя полученные значения в первую систему, получим:

Квадратурная формула:

Задача 11.

С помощью квадратурных формул, полученных в задаче 10, вычислить определенный интеграл от степенного представления интерполяционного многочлена Лагранжа (Ньютона), полученного в задаче № 6 в пределах от x₀ до x₀ +3h, и сравнить его с аналитически вычисленным значением определенного интеграла по первообразным многочлена.

Решение.

Используем степенное представление интерполяционного многочлена Лагранжа из задачи 6.

Для перехода к интегралу с канонической формой используем линейное преобразование: x =? + ?t.

Составим систему уравнений:

Подставив x = 1.05 + 0.75t, получим многочлен Лагранжа от переменной t:

L (t) = 0.24975t³ — 0.80325t² — 0.49575t + 0.537 253.

Учитывая, что 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₀ = 1 и T₁ = x.

Найти аналитическое выражение и вычислить значения полинома Чебышева i-й степени, если и i = 4. Проверить вычисления непосредственно по заданной рекуррентной формуле. Найти положение нулей и экстремумов у многочленов Чебышева в общем виде и для заданных выше x и i. Оценить модуль максимально возможного значения полинома в точках экстремумов.

Решение..

Исходя из того, что.

x_i = |y_i| надо найти T₄ т. е. для i = 4.

Из T_i+2 — 2xT_i+1 + T_i = 0 следует, что.

T₂ = 2xT₁ — T₀.

T₃ = 2xT₂ — T₁ = 2x (2xT₁ — T₀) — T₁.

T₄ = 2xT₃ — T₂ = 2x (2x (2xT₁ — T₀) — T₁) — 2xT₁ + T₀ = 8x³T₁ — 4x²T₀ — 4xT₁ + T₀.

Подставим значение T₀ = 1 и T₁ = x.

T₄ = 8x⁴ — 4x² — 4x² + 1 = 8x⁴ — 8x² + 1.

Найдем значения x:

T₄ = 0.99 980.

Проверим по заданной рекуррентной формуле:

T₂ = 2· 0.490·0.490 — 1 = -0.9999.

T₃ = 2· 0.490·(-0.9999) — 0.490 = -0.1 469.

T₄ = 2· 0.490·(-0.1 469) + 0.9999 = 0.99 980.

Нули функции находятся, как решения биквадратного уравнения:

8x⁴ — 8x² + 1 = 0, где.

x₁ = 0.9 238 795.

x₂ = -0.9 238 795.

x₃ = 0.3 826 834.

x₄ = -0.3 826 834.

Чтобы найти экстремумы найдем.

Задача 16.

Выравнивание по всей длине с течением времени температуры T (x, t) на тонком однородном хорошо теплоизолированном стержне описывается дифференциальным уравнением в частных производных с начальным распределением температуры (в градусах Цельсия) по длине стержня в 6 равномерно расположенных с шагом h точках.

T (x₀, 0) = T₀, T (x₁, 0) = T₁, …, T (x₅, 0) = T₅; (T_i = 100· y_i ?C).

На концах стержня в точках x_-1 и x₆ удерживается нулевая температура.

Применяя конечно-разностное представление производных по пространственной переменной x, свести уравнение в частных производных к системе дифференциальных уравнений в обыкновенных производных относительно температуры T.

Решение..

Получаем систему диф. уравнений:

Учитывая начальные условия, получим систему уравнений:

Задача 17..

Используя метод Ньютона-Рафсона, найти с относительной погрешностью в одну миллионную нуль многочлена Чебышева T_i(x), полученного в задаче 14. В качестве начального приближения к корню взять В качестве x_i берутся |y_i| из таблицы исходных данных.

Решение..

Из задачи 14 возьмем полином Чебышева T₄ = 8x⁴ — 8x² + 1. В качестве начального приближения к корню возьмем x_нач, вычисленное по формуле.

Т.к. 8x⁴ — 8x² + 1 = 0, то можем сказать, что f (x_нач + ?) = 0.

Воспользуемся DERIVE для нахождения корня с необходимой точностью:

получим такие значения: 0.38 234, 0.382 689, 0.382 683, 0.382 683, 0.382 683.

На третьей итерации получаются значения корня с нужной точностью.

Задача 19.

Скорость изменения переменной x (t) во времени равна функции от этой переменной f (x). Найти аналитическое выражение последней от времени, начиная с t = 0, если в начальный момент x (0) = 0. В качестве f (x) взять степенной многочлен P₂(x), полученный в задаче 8. Протабулировать полученное решение с шагом h = 0.1 в интервале [0, 0.5].

Решение.

P₂(x) = -0.710 314 + 0.98 9486x — 0.62 4589x² = 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.622 648.

t = 0.2 x = -0.137 833.

t = 0.3 x = -0.230 872.

t = 0.4 x = -0.347 464.

t = 0.5 x = -0.496 850.

Задача 20.

Методом Эйлера в интервале [0, 0.5] с шагом h = 0.1 получить решение нелинейного дифференциального уравнения:

dx/dt = a + bx + cx²,.

x (0) = 0.

Коэффициенты a, b, c взять из P₂(x), полученного в задаче 8.

Решение

y = P₂(x).

P₂(x) = -0.710 314 + 0.98 9486x — 0.62 4589x².

Общая формула для решения.

x = x₀ + h· P₂(x₀, t₀).

x₁ = 0 + 0.5· (-0.710 314) = -0.355 156.

x₂ = -0.355 156 + 0.5· (-0.710 314 + 0.989 486 (-0.355 156)¹ ;

— 0.624 589· (-0.355 156²) = -0.53 854.

x₃ = -0.53 854 + 0.5· (-0.710 314 + 0.989 486 (-0.53 854)¹ ;

— 0.624 589 (-0.53 854)²) = -0.636 315.

x₄ = -0.636 315 + 0.5· (-0.710 314 + 0.989 486 (-0.636 315)¹ ;

— 0.624 589 (-0.636 315)²) = -0.689 304.

x₅ = -0.689 304 + 0.5 (-0.710 314 + 0.989 486 (-0.689 304)¹ ;

— 0. 0.624 589 (-0.689 304)²) =—0.71 827.

Задача 23.

Проверить заданную систему из трех векторов на линейную зависимость. При обнаружении линейной зависимости поменять местами первые компоненты векторов x1, x2 и выполнить повторную проверку. Из исходных данных векторы формируются так:

x₁ = (y₀, y₁, y₂); x₂=(y₃, y₄, y₅); x₃=(h, x₀, 0).

На базе линейно независимой системы векторов x₁, x₂, x₃ методом Грама-Шмидта построить ортонормированную систему трех векторов:

y₁ = (y₁₁, y₂₁, y₃₁); y₂=(y₁₂, y₂₂, y₃₂); y₃=(y₁₃, y₂₃, y₃₃).

На основе полученной системы векторов сформировать квадратную матрицу T = (y₁, y₂, y₃). Вычислить det (T) и получить матрицы — обратную T^-1 и транспонированную T'. Найти произведение T^-1 · T, T · T'. Сделать выводы о свойствах матрицы T.

Решение.

Исходные векторы x₁ = (-0.02,0.604,0.292); x₂=(-0.512,-1.284,-2.04);

x₃=(0.5,0.3,0).

Составим матрицу и проверим ее на линейную зависимость:

det (A· A^T) = 0.23 591 > 0, значит система линейно независима.

Найдем векторы v₁, v₂, v₃.

v₁ = x₁.

v₂ = x₂ + a₂₁· v₁.

v₃ = x₃ + a₃₂· v₂ + a₃₁· v₁.

v₁ = (-0.02, 0.604, 0.292);

v₂ = (-0.572 423, 0.54 078, -1.15 782);

v3 = (0.471 405, 0.104 651, -0.184 183).

Матрица T:

det (T) = -1.

Ортонормированная матрица T состоит из собственных векторов. Определитель матрицы T равен 1. Если транспонировать ортогональную матрицу то она будет равна обратной. T' = T^-1. Это значит, что если умножить T· T' = E — получим единичную матрицу.

Задача 24.

Считая числа -1, -2, -3 собственными значениями, а векторы у₁, у₂, у₃ из задачи 23 — собственными векторами некоторой матрицы А, найдите проекторы этой матрицы (Р₁, Р₂, Р₃), саму матрицу, А и ей обратную А_-1. Получить характеристическое уравнение матрицы, А и подтвердить правильность всех промежуточных вычислений.

Решение.

Найдем проекторы матрицы А:

Найдем обратную матрицу А^-1:

Характеристическое уравнение матрицы, А имеет вид:

— x³-6x²-11x-6=0;

Корни характеристического уравнения — собственные значения матрицы.

x₁= -1; x₂= -2; x₃= -3.

Задача 25.

Решить систему алгебраических уравнений А· x = b, где Аматрица коэффициентов из задачи 24, x = (x1, x2, x3) — векторы решения, b = (3, 2, 1) — вектор правых частей. Решение получить, используя обратную матрицу, полученную из задачи 24.

Решение.