Сборник задач для упражнений по курсу - Основы вычислительной метаматики

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИРОССИЙСКОЙ ФЕДЕРАЦИИМосковский физико-технический институт(государственный университет)Сборник задачдля упражнений по курсу:Основы вычислительной математикиМосква 2014УДК 519.5:517.949.8Сборник задач для упражнений по курсу: Основы вычислительной математики. -Составители: В.И.Косарев, О.Л.Косарева, Н.П.Онуфриева, В.Б.Пирогов,В.С.Рябенький, Л.И.Северинов, Л.М.Стрыгина, Р.П.Федоренко,А.С.Холодов, Л.А.Чудов.Издание содержит ряд исправлений.

Задачи, помеченные † отличаются отзадач в издании 1996 года.cМосковский физико-технический институт (государственный университет), 2014–3–I. ПогрешностиI.1. Величина y вычисляется по формуле y = f (x), а величина x получается прямым измерением, которое осуществляется с погрешностью, не превосходящей некоторое заданное число ∆x.Требуется указать наименьшее число ∆y, при котором для данного x∗ ,полученного в результате приближенного измерения величины x, справедливаоценка|y ∗ − y| < ∆y, y ∗ = f (x∗ ), y = f (x).Указать факторы, от которых зависит точность приближенной формулы∆y = f 0 (x∗ )∆x для ∆y.1.а) f (x) = sin x,б) f (x) = ln x,в) f (x) = 2x − 5x + 6I.2. Пусть z = f (x, y), причем величина x∗ получается в результате приближенных измерений с неустранимой погрешностью ∆x = 10−3 . Пусть привычислении z нас интересует абсолютная погрешность.С какой разумной точностью следует измерять y?xа) f (x, y) = x + 10yб) f (x, y) = xy + xy 2в) f (x, y) =y0I.3.

Пусть требуется вычислить производную f (x) заданной функции f (x)в некоторой точке x. Пусть известно, что |f 00 (x)| ≤ 1 и |f 000 (x)| ≤ 1 при всех x.Используются приближенные формулыf (x + h) − f (x)f (x + h) − f (x − h)f 0 (x) ≈.h2hУказать в обоих случаях h, при которых погрешность полученного значения f 0 (x) не превосходит 10−3 .f 0 (x) ≈I.4. Пусть требуется вычислить производную функции f (x), причем известно, что f 00 (x) ≤ 1 при всех x. Используется приближенная формулаf ∗ (x + h) − f ∗ (x),hгде f ∗ (x) — приближенные значения функции f (x), полученные в результатенеточных измерений с погрешностью, не превосходящей 10−4 .Какова наибольшая точность, с которой можно вычислить f 0 (x) по указанной формуле? Указать оптимальный выбор шага h.f 0 (x) =I.5.

Пусть неустранимая погрешность при измерении x не превосходит∆x = 10−3 . Для вычисления заданной функции y = f (x) используется частичная сумма ряда Маклоренаf 0 (0)f 00 (0) 2f (n) ny ≈ f (0) +x+x + ··· +x1!2!n!(∗)–4–а) Как выбрать n, чтобы погрешность приближения функции f (x) отрезком ряда Маклорена не превосходила неустранимую погрешность ∆y определения y? Рассмотреть функцию f (x) = sin x на отрезке 0 ≤ x ≤ 1 и на отрезке10 ≤ x ≤ 11.б) Каковы требования к относительным погрешностям округления слага(k)емых fk! xk , чтобы абсолютная погрешность при их вычислении не превосходила неустранимую погрешность ∆y? Рассмотреть функцию f (x) = sin x наотрезке 0 ≤ x ≤ 1 и на отрезке 10 ≤ x ≤ 11.Не можете ли Вы предложить для вычисления sin x на отрезке 10 ≤ x ≤ 11более совершенную процедуру, чем задаваемую формулой (∗)?–5–II.

Обусловленность и вычисление решениялинейных системII.1. Для системы10−3 x1 + x2 = b1x 1 − x 2 = b2ответить на следующие вопросы:а) Каково число обусловленности µ = kAk · kA−1 k системы, где A — матрица этой системы, а в качестве нормы произвольного вектора ~x = (x1 , x2 )используется первая норма, то есть k~xk = max(|x1 |, |x2 |)?б) Какова допустимая относительная погрешность при задании ~b = (b1 , b2 ),при которой относительная погрешность решения не превосходит 10−2 ?в) Пусть b1 = 2, b2 = 1.

С каким числом знаков надо вести вычисления пометоду Гаусса без выбора главного элемента, чтобы относительная погрешность найденных x1 и x2 не превосходила 10%? Тот же вопрос для методаГаусса с выбором главного элемента.II.2. Дана система10x1 + x2x1 + 10x2 + x3x2 + 10x3 + x4.........x98 + 10x99 + x100 x + x + ... + x1299 + x100===123= 99= Pгде P — некоторый параметр.а) Описать алгоритм метода Гаусса без выбора главного элемента для решения системы при P = 100.б) Описать алгоритм, позволяющий экономно вычислять совокупность решений, отвечающих многим различным значениям параметра.II.3. Рассмотрим системуx1 + 0.99x2 = b10.99x1 + x2 = b2а) Пусть вектор ~b = (b1 , b2 ) получает некоторое возмущение δ~b = (δb1 , δb2 ). Тогда решение ~x = (x1 , x2 ) получит соответствующее возмущение δ~x = (δx1 , δx2 ).–6–Найти наименьшее число µ, при котором независимо от ~b и δ~b выполняетсяоценкаkδ~bkkδ~xk≤µ.k~xkk~bkДать ответ, используя нормы k · k1 , k · k2 , k · k3 , введеные формуламиk~xk1 = max |x1 |, |x2 |k~xk2 = |x1 | + |x2 |qk~xk3 = x21 + x22и найти соответствующие значения µ = µ1 , µ = µ2 и µ = µ3 .б) При заданном фиксированном ~b найти наименьшее число ν = ν(~b), прикотором независимо от δ~b выполнена оценкаkδ~xkkδ~bk≤ ν(~b).k~xkk~bkНайти то ~b, которому соответствует наименьшее значение ν(~b), а также этонаименьшее значение ν в случае использования первой, второй и третьей нормы.II.4.

Рассмотреть систему(√31x+x2 12 2√31− 2 x1 + 2 x2= b1= b2и ответить для нее на вопросы предыдущей задачи.II.5. Для системыx 1 + x 2 = b1x 1 − x 2 = b2ответить на вопросы задачи II.3.II.6. Для численного решения краевой задачи видаy 00 (x) − P 2 (x)y(x) = f (x),y(0) = ϕy(1) = ψ0<x<1(1)где P (x) и f (x) — заданные функции, а ϕ и ψ — заданные числа, можнопоступить так: зададим натуральное N и отметим на отрезке [0, 1] точки xk =–7–k · h, k = 0, 1, . . . , N, h = N1 .

Искомую функцию y(x) заменим сеточнойфункцией y (h) = (y0 , y1 , . . . , yN ), определенной в точках xk , k = 0, 1, . . . , N .Для вычисления y0 , y1 , . . . , yN составим систему линейных уравненийy0 = ϕyk+1 − 2yk + yk−1(2)− P 2 (xk )yk = f (xk ), k = 1, 2, . . . , N − 12hyN = ψа) Показать, что система (2) есть частный случай системы видаb0 y0 + c0 y1 = f0ak yk−1 + bk yk + ck yk+1 = fk k = 1, 2, . . . , N − 1aN yN −1 + bN yN= fN(3)б) Выписать матрицу системы (2).в) Выписать формулы алгоритма решения системы (3) методом Гаусса безвыбора главного элемента (методом прогонки).г) Показать, что в случае |bk | > |ak | + |ck | в формулах метода прогонки невстретится деление на нуль.д) Написать программу для вычисления решения системы (3) методом прогонки и вычислить решение в случаеP (x) = 1 + x2 ,f (x) = xex ,ϕ = 1,ψ = 3,N = 20.II.7.

Рассмотрим задачуy 00 (x) = f (x), 0 < x < 1y(0) = y(1) = 0.Для ее численного решения введем на интервале (0, 1) сетку xk = k · h, h =k = 1, 2, . . . , N − 1 и заменим искомую функцию y(x) сеточной y (h) =(y1 , y2 , . . . , yN −1 ).Для определения чисел y1 , y2 , . .

. , yN −1 будем пользоваться системой1,Nyk−1 − 2yk + yk+1= f (xk ),h2положив y0 = yN = 0.k = 1, 2, . . . , N − 1,(1)–8–а) Проверить, что сеточные функции(m)(m)(m)ψ (m) = ψ1 , ψ2 , . . . , ψN −1 ,(m)ψk= sinm = 1, 2, . . . , N − 1,kmπNявляются собственными векторами матрицы A системы (1) и что соответствующие собственные числа сутьλm = −4mπ,sin22h2Nm = 1, 2, . . . , N − 1.б) Найти наименьшее число µ(A), при котором независимо от f (h) и δf (h)справедлива оценкаkδy (h) k3 kδf (h) k3≤ µ(A).?(2)ky (h) k3kf (h) k3(h)(h)(h)Здесь через δf (h) = δf1 , δf2 , . . . , δfN −1 обозначено возмущение, котороепридается правой части системы (1), а через δy (h) — соответствующее возмущение решения. Как ведет себя µ(A) при возрастании N ?в) При каких f (h) и δf (h) достигается равенство в оценке (2)? При какихf (h) и δf (h) левая часть неравенства принимает наименьшее значение и чемуэто наименьшее значение равно?г) На основе исследования модельной задачи (1) сделайте (благоприятные) выводы о свойствах линейной алгебраической системы, рассмотренной взадаче II.6.II.8.

Дана система10x + y − z = 1x − 20y + 3z = 22x + 3y − 10z = −1.Выписать формулы для вычисления решения итерациями, используя свойство диагонального преобладания. Сколько итераций достаточно сделать, чтобы уменьшить погрешность исходного приближения в тысячу раз?II.9. Пусть вещественная матрица A системы линейных уравнений порядка mA~x = f~,~x = (x1 , x2 , . . .

, xm )симметрична, и ее наименьшее и наибольшеесобственные числа λmin и λmaxp222 .положительны. Введем норму kyk = y1 + y2 + · · · + ym–9–а) Подобрать параметр τ так, чтобы в методе последовательных приближений(n+1)(n)(n)~~x= ~x − τ A~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+y2x − yx + 3y3x + y= 3.0= 0.2= 7.0= 5.0III.2† .