Zadachnik_2014_Kosarev
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский физико-технический институт (государственный университет)
Сборник задач
для упражнений по курсу:
Основы вычислительной математики
Москва 2014
УДК 519.5:517.949.8 Сборник задач для упражнений по курсу: Основы вычислительной мате-
матики. -
Составители: В.И.Косарев, О.Л.Косарева, Н.П.Онуфриева, В.Б.Пирогов, В.С.Рябенький, Л.И.Северинов, Л.М.Стрыгина, Р.П.Федоренко, А.С.Холодов, Л.А.Чудов.
Издание содержит ряд исправлений. Задачи, помеченные y отличаются от задач в издании 1996 года.
c Московский физико-технический институт (государственный университет), 2014
–3 –
I.Погрешности
I.1. Величина y вычисляется по формуле y = f(x), а величина x получается прямым измерением, которое осуществляется с погрешностью, не превосходящей некоторое заданное число x.
Требуется указать наименьшее число y, при котором для данного x , полученного в результате приближенного измерения величины x, справедлива
оценка
jy yj < y; y = f(x ); y = f(x):
Указать факторы, от которых зависит точность приближенной формулы
y = f0(x ) x для y. |
|
|
1 |
|
|
а) f(x) = sin x; |
б) f(x) = ln x; |
в) f(x) = |
: |
||
|
|||||
x2 5x + 6 |
I.2. Пусть z = f(x; y), причем величина x получается в результате приближенных измерений с неустранимой погрешностью x = 10 3. Пусть при
вычислении z нас интересует абсолютная погрешность. |
|
|
||
С какой разумной точностью следует измерять y? |
|
x |
||
а) f(x; y) = x + 10y |
б) f(x; y) = xy + xy2 |
в) f(x; y) = |
||
y |
||||
|
|
|
I.3. Пусть требуется вычислить производную f0(x) заданной функции f(x) в некоторой точке x. Пусть известно, что jf00(x)j 1 и jf000(x)j 1 при всех x.
Используются приближенные формулы |
|
|
|
||||
f0(x) |
|
f(x + h) f(x) |
f0(x) |
|
f(x + h) f(x h) |
: |
|
h |
2h |
||||||
|
|
|
Указать в обоих случаях h, при которых погрешность полученного значения f0(x) не превосходит 10 3.
I.4. Пусть требуется вычислить производную функции f(x), причем известно, что f00(x) 1 при всех x. Используется приближенная формула
f0(x) = f (x + h) f (x); h
где f (x) приближенные значения функции f(x), полученные в результате неточных измерений с погрешностью, не превосходящей 10 4.
Какова наибольшая точность, с которой можно вычислить f0(x) по указанной формуле? Указать оптимальный выбор шага h.
I.5. Пусть неустранимая погрешность при измерении x не превосходитx = 10 3. Для вычисления заданной функции y = f(x) используется ча-
стичная сумма ряда Маклорена |
|
|
|
|
|
|
|
||
|
f0(0) |
|
f00(0) |
|
f(n) |
( ) |
|||
y f(0) + |
|
|
x + |
|
|
x2 + + |
|
xn |
|
1! |
|
2! |
|
n! |
– 4 –
а) Как выбрать n, чтобы погрешность приближения функции f(x) отрезком ряда Маклорена не превосходила неустранимую погрешность y определения y? Рассмотреть функцию f(x) = sin x на отрезке 0 x 1 и на отрезке
10 x 11.
б) Каковы требования к относительным погрешностям округления слагаемых xk, чтобы абсолютная погрешность при их вычислении не превосходила неустранимую погрешность y? Рассмотреть функцию f(x) = sin x на отрезке 0 x 1 и на отрезке 10 x 11.
Не можете ли Вы предложить для вычисления sin x на отрезке 10 x 11 более совершенную процедуру, чем задаваемую формулой ( )?
–5 –
II.Обусловленность и вычисление решения
линейных систем
II.1. Для системы
10 3x1 + x2 = b1 x1 x2 = b2
ответить на следующие вопросы:
а) Каково число обусловленности = kAk kA 1k системы, где A матрица этой системы, а в качестве нормы произвольного вектора ~x = (x1; x2) используется первая норма, то есть k~xk = max(jx1j; jx2j)?
б) Какова допустимая относительная погрешность при задании~ 1 2 , b = (b ; b )
при которой относительная погрешность решения не превосходит 10 2?
в) Пусть b1 = 2; b2 = 1. С каким числом знаков надо вести вычисления по методу Гаусса без выбора главного элемента, чтобы относительная погрешность найденных x1 и x2 не превосходила 10%? Тот же вопрос для метода Гаусса с выбором главного элемента.
II.2. Дана система
8 x1 |
1 |
+ 10x2 + x3 |
|
|
|
|
|
|
|
|||
10x + x2 |
|
|
|
|
|
|
|
|
|
|
||
> |
|
x2 |
+ 10x3 |
+ |
x4 |
|
|
|
||||
> |
|
|
|
|
||||||||
> |
|
|
|
|
|
|
|
|
|
|
|
|
> |
|
|
|
|
|
|
|
|
|
|
|
|
> |
|
|
|
|
|
|
|
|
|
|
|
|
> |
|
|
. |
. |
|
. |
. |
|
|
. |
. |
|
> |
|
|
|
. |
|
. |
|
|
. |
|||
> |
|
|
|
|
|
|
|
|
|
|||
> |
|
|
|
|
|
|
|
|
|
|
|
|
< |
|
|
|
|
|
|
|
|
|
|
|
|
> |
|
|
|
|
x98 |
+ 10x99 |
+ x100 |
|||||
> |
|
+ x2 |
+ : : : |
+ |
x99 |
+ x100 |
||||||
> x1 |
|
>
>
>
>
>
>
:
=1
=2
=3
=99
=P
где P некоторый параметр.
а) Описать алгоритм метода Гаусса без выбора главного элемента для решения системы при P = 100.
б) Описать алгоритм, позволяющий экономно вычислять совокупность ре-
шений, отвечающих многим различным значениям параметра. |
|
||
II.3. Рассмотрим систему |
|
|
|
|
0:199x1 + x2 |
= b2 |
|
|
x + 0:99x2 |
= b1 |
|
~ |
|
~ |
; b2). То- |
а) Пусть вектор b = (b1 |
; b2) получает некоторое возмущение b = ( b1 |
гда решение ~x = (x1; x2) получит соответствующее возмущение ~x = ( x1; x2).
|
|
|
– 6 – |
|
|
|
|
||
|
|
|
|
|
|
|
|
~ |
~ |
Найти наименьшее число , при котором независимо от b и b выполняется |
|||||||||
оценка |
|
|
|
|
|
~ |
|
|
|
|
|
|
|
|
|
|
|
||
k ~xk |
|
|
k bk |
: |
|
||||
|
~x |
|
|
|
~ |
|
|
||
k k |
|
|
|
kbk |
|
|
|||
Дать ответ, используя нормы k k1; k k2; k k3, введеные формулами |
|||||||||
k k2 |
= j |
|
1j |
j |
|
2j |
|
|
|
k~xk1 |
= max jx1j; jx2j |
|
|||||||
~x |
|
x |
+ x |
|
|
|
q
k~xk3 = x21 + x22
и найти соответствующие значения = 1; = 2 и = 3.
~ |
~ |
б) При заданном фиксированном b найти наименьшее число = (b), при |
~ |
|
|
|
|
|
|
котором независимо от b выполнена оценка |
|
|||||
|
|
|
|
~ |
|
|
|
k ~xk |
|
(~b) |
k bk |
: |
|
|
~x |
|
~ |
|
||
|
k |
k |
|
kbk |
|
|
~ |
|
|
|
|
|
~ |
Найти то b, которому соответствует наименьшее значение (b), а также это |
наименьшее значение в случае использования первой, второй и третьей нормы.
II.4. Рассмотреть систему
( |
|
|
|
|
p |
|
|
|
1 |
x |
1 |
+ |
3 |
x2 |
= b1 |
||
p2 |
2 |
23 x1 + 12 x2 = b2
иответить для нее на вопросы предыдущей задачи.
II.5. Для системы
x1 + x2 = b1 x1 x2 = b2
ответить на вопросы задачи II.3.
II.6. Для численного решения краевой задачи вида
y00(x) P 2(x)y(x) = f(x); |
0 < x < 1 |
|
y(0) |
= ' |
(1) |
y(1) |
= |
|
где P (x) и f(x) заданные функции, а ' и |
заданные числа, можно |
поступить так: зададим натуральное N и отметим на отрезке [0; 1] точки xk =
|
|
|
|
|
|
|
|
|
|
|
|
|
– 7 – |
|
|
|
|
|
k |
|
h; k |
= |
0; 1; : : : ; N; h = |
1 |
. Искомую функцию |
y(x) |
заменим сеточной |
||||||||||
|
|
(h) |
|
|
|
|
|
N |
|
|||||||||
функцией y |
|
= (y0; y1 |
; : : : ; yN ), определенной в точках xk; k = 0; 1; : : : ; N. |
|
||||||||||||||
|
|
Для вычисления y0; y1; : : : ; yN составим систему линейных уравнений |
|
|||||||||||||||
|
|
8 yk+1 |
|
2yk + yk 1 |
|
|
2 |
|
|
|
|
|
|
|||||
|
|
> |
y0 = ' |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
2 |
|
|
P |
|
(xk)yk = f(xk); k = 1; 2; : : : ; N |
|
1 |
(2) |
||||
|
|
> |
|
|
|
|
h |
|
|
|
|
|
|
|
|
|||
|
|
> |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
< |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>
>
: yN =
а) Показать, что система (2) есть частный случай системы вида
8
<
akyk 1 : aN yN 1
b0y0
+bkyk
+bN yN
+ c0y1 |
= f0 |
k = 1; 2; : : : ; N 1 |
(3) |
+ ckyk+1 |
= fk |
||
|
= fN |
|
б) Выписать матрицу системы (2).
в) Выписать формулы алгоритма решения системы (3) методом Гаусса без выбора главного элемента (методом прогонки).
г) Показать, что в случае jbkj > jakj + jckj в формулах метода прогонки не встретится деление на нуль.
д) Написать программу для вычисления решения системы (3) методом прогонки и вычислить решение в случае
|
|
|
P (x) = 1 + x2; f(x) = xex; |
' = 1; |
= 3; N = 20: |
|
||||
|
|
|
II.7. Рассмотрим задачу |
|
|
|
|
|
|
|
|
|
|
y00(x) = f(x); 0 < x < 1 |
|
|
|
|
|||
|
|
|
y(0) = y(1) = 0: |
|
|
|
|
|
||
1 |
|
Для ее численного решения введем на интервале (0; 1) сетку xk = k h;(h)h = |
||||||||
|
|
; |
k = 1; 2; : : : ; N 1 и заменим искомую функцию y(x) сеточной y |
= |
||||||
|
N |
|||||||||
(y1; y2; : : : ; yN 1). |
|
|
|
|
|
|
|
|||
|
|
|
Для определения чисел y1; y2; : : : ; yN 1 будем пользоваться системой |
|
||||||
|
|
|
yk 1 2yk + yk+1 |
= f(x |
); |
k = 1; 2; : : : ; N |
|
1; |
(1) |
|
|
|
|
h2 |
k |
|
|
|
|
положив y0 = yN = 0.
|
|
|
|
|
|
|
|
|
|
– 8 – |
|
|
а) Проверить, что сеточные функции |
|
|
||||||||||
(m) = 1 |
; |
|
2 |
|
; : : : ; |
N 1 |
; |
m = 1; 2; : : : ; N 1; |
||||
|
(m) |
|
|
(m) |
|
|
(m) |
|
|
|||
(m) |
= sin |
km |
|
|
|
|
|
|
|
|
||
k |
N |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||
являются собственными векторами матрицы A системы (1) и что соответству- |
||||||||||||
ющие собственные числа суть |
|
|
|
|||||||||
|
|
|
4 |
|
|
sin2 |
m |
|
|
|
||
|
m = |
|
|
|
; |
m = 1; 2; : : : ; N 1: |
||||||
|
h2 |
2N |
б) Найти наименьшее число (A), при котором независимо от f(h) и f(h) справедлива оценка
|
(h) |
|
(h) |
|
|
|
||
|
k y |
k3 |
k f k3 |
(A):? |
(2) |
|||
|
y(h) |
3 |
f(h) 3 |
|||||
|
k |
k |
|
k |
k |
|
|
|
Здесь через f(h) = f1(h); f2(h); : : : ; f |
(h) |
обозначено возмущение, которое |
||||||
придается правой части |
|
|
|
|
N 1 |
|
|
|
системы (1), а через |
y(h) соответствующее возму- |
щение решения. Как ведет себя (A) при возрастании N?
в) При каких f(h) и f(h) достигается равенство в оценке (2)? При каких f(h) и f(h) левая часть неравенства принимает наименьшее значение и чему это наименьшее значение равно?
г) На основе исследования модельной задачи (1) сделайте (благоприятные) выводы о свойствах линейной алгебраической системы, рассмотренной в задаче II.6.
II.8. Дана система
10x + y z = 1 x 20y + 3z = 2
2x + 3y 10z = 1:
Выписать формулы для вычисления решения итерациями, используя свойство диагонального преобладания. Сколько итераций достаточно сделать, чтобы уменьшить погрешность исходного приближения в тысячу раз?
II.9. Пусть вещественная матрица A системы линейных уравнений поряд-
ка m |
|
~ |
; x2; : : : ; xm) |
A~x = f; ~x = (x1 |
симметрична, и ее наименьшее и наибольшее собственные числа min и max
p
положительны. Введем норму kyk = y12 + y22 + + ym2 .
– 9 –
а) Подобрать параметр так, чтобы в методе последовательных приближений
~x |
(n+1) |
(n) |
A~x |
(n) |
~ |
|
= ~x |
|
f ; n = 0; 1; 2; : : : ; |
норма погрешности ~"(n) = ~x(n) ~x убывала как можно быстрее. Здесь x(0) заданное начальное приближение, ~x вектор-решение системы.
б) Подобрать пару итерационных параметров 1; 2 так, чтобы в методе последовательных приближений
~z(n) = x(n) 1 |
A~x(n) f~ |
~x(n+1) = z(n) 2 |
A~z(n) f~ |
норма погрешности ~"(n) убывала как можно быстрее.
в) Пусть min = 1; max = 10. Во сколько раз больше арифметических операций потребуется для уменьшения первоначальной погрешности в заданное число раз при использовании первого итерационного алгоритма по сравнению со вторым?
–10 –
III.Метод наименьших квадратов для решения переопределенных линейных систем
III.1. Найти обобщенное в смысле наименьших квадратов решение переопределенной системы уравнений
x + y = 3:0 2x y = 0:2 x + 3y = 7:0 3x + y = 5:0
III.2y. Напряженность магнитного поля H и магнитная индукция B связаны соотношением B = a+HbH . По результатам следующих экспериментальных измерений определить a и b:
H |
8 |
10 |
15 |
20 |
30 |
40 |
60 |
80 |
B |
13:0 |
14:0 |
15:4 |
16:3 |
17:2 |
17:8 |
18:5 |
18:8 |
|
|
|
|
|
|
|
|
|
III.3. Измерения трех углов плоского треугольника привели к значениям:
A1 = 54 50; A2 = 50 10; A3 = 76 60. Сумма углов A1 + A2 + A3 = 180 120
дает невязку в 120, превосходящую погрешность наблюдения. Ликвидировать невязку, следуя предписанию метода наименьших квадратов.
III.4. Сопротивление проволоки R линейно зависит от температуры t: R = a0+a1t. По результатам следующих экспериментальных измерений определить a0 и a1:
t |
19:1 |
25:0 |
30:1 |
36:0 |
40:0 |
45:1 |
50:0 |
R |
76:30 |
77:80 |
79:75 |
80:80 |
82:35 |
83:90 |
85:10 |
|
|
|
|
|
|
|
|
III.5. Выполнить линейную аппроксимацию по методу наименьших квадратов для таких исходных данных, найденных экспериментально:
|
x |
0:2 |
0:3 |
|
0:7 |
0:8 |
|
1:2 |
1:4 |
1:8 |
|
y |
2:229 |
2:180 |
|
1:972 |
1:887 |
|
1:696 |
1:590 |
1:332 |
Определить y для x = 0:578; |
x = 0:882; |
x = 1:356. |
|
|
III.6. Выполнить квадратичную аппроксимацию по методу наименьших квадратов для таких экспериментальных данных:
x |
1:0 |
2:0 |
2:5 |
3:0 |
4:0 |
4:5 |
5:0 |
6:0 |
y |
1:88 |
0:96 |
0:13 |
2:08 |
6:72 |
10:67 |
14:13 |
22:80 |