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

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

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

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

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

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

Решение

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

Найдем формулу перехода от 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.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₀; 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.93621; a₁ = 3.89576; a₂ = -2.8954; a₃ = 0.488001

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

P₃(x) = -0.93621 + 3.89576x - 2.8954x² + 0.488001x³

Откуда a₀ = -0.0710314; a₁ = 0.989486; a₂ = -0.624589;

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

P₂(x) = -0.0710314 + 0.989486x - 0.624589x²

Откуда a₀ = 0.974118; a₁ = -0.946742;

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

P₁(x) = 0.974118 - 0.946742x

6a₀ = -2.96

Откуда a₀ = -0.493333;

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

P₀(x) = -0.0493333

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

Задача 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.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₀ = 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.99980

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

T₂ = 2·0.00490·0.00490 - 1 = -0.9999

T₃ = 2·0.00490·(-0.9999) - 0.00490 = -0.01469

T₄ = 2·0.00490·(-0.01469) + 0.9999 = 0.99980

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

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

x₁ = 0.9238795

x₂ = -0.9238795

x₃ = 0.3826834

x₄ = -0.3826834

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

Задача 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.38234, 0.382689, 0.382683, 0.382683, 0.382683.

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

Задача 19

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

Решение

P₂(x) = -0.0710314 + 0.989486x - 0.624589x² = 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²,

x(0) = 0

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

Решение

y = P₂(x)

P₂(x) = -0.0710314 + 0.989486x - 0.624589x²

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

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

x₁ = 0 + 0.5· (-0.0710314) = -0.0355156

x₂ = -0.0355156 + 0.5·(-0.0710314 + 0.989486 (-0.0355156)¹ -

-0.624589· (-0.0355156²) = -0.053854

x₃ = -0.053854 + 0.5· (-0.0710314 + 0.989486 (-0.053854)¹ -

- 0.624589 (-0.053854)²) = -0.0636315

x₄ = -0.0636315 + 0.5· (-0.0710314 + 0.989486 (-0.0636315)¹ -

-0.624589 (-0.0636315)²) = -0.0689304

x₅ = -0.0689304 + 0.5 (-0.0710314 + 0.989486 (-0.0689304)¹ -

-0. 0.624589 (-0.0689304)²) =--0.071827

Задача 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.23591 > 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.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 собственными значениями, а векторы у₁, у₂, у₃ из задачи 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.

Решение