Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Можем заметить лишь, что в достаточно малой окрестности решения скорость сходимости метода квадратичная....IV.8. Критерии сходимости итерацийВ методах, использующих локализацию корня, останов итераций призаданной точности  > 0 вычисления положения корня осуществить просто: когда длина очередного отрезка локализации| an – bn | < ,итерационный процесс останавливается.Для одноточечных линейно сходящихся методов (МПИ) итерационный процесс следует остановить при выполнении оценки|| x*  x n ||  .(8.1)Так как точное решение x* неизвестно, то это условие на практике вявном виде проверить невозможно. Здесь поступают следующим образом.Введем величину ||xn – xn – 1||, которая называется итерационной поправкой.

Иногда требуют просто, чтобы итерационная поправка не превосходила заданного значения точности:|| xn  xn 1 ||  .(8.2)В реальных больших задачах скорость сходимости линейного итерационного процесса может быть весьма медленной, поэтому критерий (8.2)не является удовлетворительным. Для обеспечения критерия сходимости(8.1) по итерационной поправке в предположении сходимости процессаиспользуем следующий прием:94IV.9. Задачи на доказательство|| xn  x* ||  || xn  x ||  || xn  xn 1  xn 1  xn  2  xn  2  xn 3  ...

 x ||  || xn  xn 1 ||  || xn 1  xn  2 ||  || xn  2  xn 3 ||  ...  || x n  x n 1 ||  (1  q  q 2  ...)  || x n  x n 1 ||(8.3)11 qТаким образом, мы видим, что для достижения заданной точности критерий (8.1) в терминах итерационной поправки нужно переформулироватьследующим образом:|| xn  xn 1 ||   (1  q) ,(8.4)что при q, близких к единице, может существенно увеличить количествотребуемых итераций для достижения заданной точности по сравнению скритерием (8.2).Величина q в оценке (8.4) должна уточняться на итерациях:q || xn  xn 1 || / || xn 1  xn 2 || .(8.5)В случае достаточной малости величины q в (8.4) можно пренебречьмножителем (1 – q) и перейти к оценке (8.2).Для метода Ньютона нахождения простого корня нелинейного уравнения выполнение условия (8.2) на итерационную погрешность являетсядостаточным в силу квадратичной сходимости метода.

Для кратных корней необходимо переходить к оценке (8.4).Можно использовать также критерий сходимости по самой функции.Считается, что итерационный процесс сошелся, если выполнено условие||F(xn)|| < ε.Для кратных корней такой критерий является неудовлетворительным.IV.9. Задачи на доказательствоIV.9.1. Доказать формулу (4.4).IV.9.2. Доказать, что метод простой итерации x(n+1) = φ(x(n)) сходится длялюбого начального приближения x0  R:а) φ(x) = cos (x);б) φ(x) = a sin2x + b cos2x +c, где |a – b| < 1;в) φ(x) = a exp(– bx2) + c, где b  0, 2a 2b  e .95IV.

ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙIV.9.3. Написать формулу метода Ньютона для решения уравнения x2 = a,a > 0. Доказать, что если за начальное приближение принять произвольное x0 > 0, то все последующие приближения xk, k ≥ 1, больше, чем a .IV.9.4. Известно, что уравнение F(x) = 0 имеет решение на отрезкеα ≤ x ≤ β. Причем на этом отрезке Fʹ(x) > 0, Fʹʹ(x) > 0. Показать, что задачуможно решить численно методом Ньютона, положив x0 = β. Построитьпример, в котором при выборе в качестве начального приближения числаx0 = α сходимость не имеет места.IV.9.5. Известно, что уравнение F(x) = 0 имеет решение на отрезкеα ≤ x ≤ β. Как следует выбирать начальные приближения x0, чтобы былагарантирована сходимость метода Ньютона в следующих случаях: на отрезке   x   всюду F   x   0 , F   x   0 , на отрезке   x   всюду F   x   0 , F   x   0 , на отрезке   x   всюду F   x   0 , F   x   0 .IV.9.6.

Доказать, что уравнение x + 0,5 sin x + a = 0 имеет единственныйкорень при любом a. Найти его значение с точностью ε = 10- 3 дляa = ±1, ±2, ±3.IV.9.7. Какие условия теоремы о сходимости простых итераций для уравнения x = φ(x), φ(x) = x/2 – 4/5, x0 = 0, на отрезке [–1, 1], не выполнены?Будет ли это уравнение иметь решение на этом отрезке?IV.9.8. Пусть уравнение f(x) = 0 имеет на отрезке [a, b] корень z кратностиp, причем f (x) – дважды дифференцируемая функция.а) Показать, что при этих условиях метод Ньютона сходится линейносо скоростью геометрической прогрессии со знаменателем (p – 1)/p.б) Построить модификацию метода Ньютона, имеющую квадратичную скорость сходимости.Указание. Искать указанную модификацию среди методов видаf ( x(n) )( n 1)и найти значение параметра α, обеспечивающееx x( n)  f ( x ( n ) )квадратичную сходимость.IV.9.9. Для нахождения простого нуля z функции f ( x)  C 4 используетсяитерационный процессx( n 1)  0.5(u ( n 1)  v( n 1) ) , где96IV.10.

Задачи с решениямиf ( x( n) )g ( x( n) )f ( x)( n 1)(n),vx, g ( x) .f ( x)f ( x( n ) )g ( x ( n ) )Доказать, что если метод сходится, то скорость – кубическая.u ( n 1)  x ( n ) IV.9.10. Пусть уравнение f (x) = 0 имеет единственный корень на отрезке[a, b]. Для его численного решения используются метод деления отрезкапополам и другой похожий метод, в котором отрезок делится на три равные части. Пусть каждое вычисление функции выполняется за время О(1),а сравнение знаков выполняется мгновенно. Доказать, что метод деленияпополам сходится к корню быстрее.IV.10.

Задачи с решениямиIV.10.1. (Е.Н. Аристова) Методом простой итерации найти ширину функции y = x e –x , x > 0 на полувысоте с точностью ε = 10 –2.Решение. Найдем максимальное значение функции:y' = e –x – x e –x обращается в ноль при x = 1, при этом максимальное значение функции ymax = e –1 (рис. 4.5).Рис. 4.5 К задаче IV.10.1Необходимо найти два значения аргумента, при которых функция принимает значения, равные половине от максимального:x e –x = 1/2e.(10.1)Уравнение (10.1) может быть очевидным образом приведено к форме метода простой итерации двумя способами:1 спо со б .

xk + 1 = 0.5exp(xk – 1), в этом случае правая часть метода простой итерации f(x) = 0.5exp(xk – 1). Для сходимости метода необходимовыполнение условия |f (x)| < 1:97IV. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙf (x) = 0.5exp(xk – 1), и эта величина меньше единицы при выполненииусловия x < 1 + ln2 ≈ 1.7.Этот итерационный процесс пригоден для поиска левого корня уравнения (10.1).2 спо со б . xk + 1 = ln(2exk), f (x) = 1/x, производная |f (x)| < 1 при x > 1.Этот итерационный процесс пригоден для поиска правого корняуравнения (10.1).Каждый из корней должен быть найден с точностью ε/2.

С учетомкритерия сходимости (8.4) имеем для обоих итерационных процессов,стартующих от точки максимума функции:Правый кореньx0 = 1.x1 = 1.69314x2 = 2.21973x3 = 2.49053x4 = 2.60564x5 = 2.65083x6 = 2.66802x7 = 2.67448x8 = 2.67690x9 = 2.67780x10 = 2.67814Левый кореньx0 = 1.x1 = 0.5x2 = 0.30326x3 = 0.24910x4 = 0.23597x5 = 0.23289x6 = 0.23217Таким образом, искомая величина 1/2  x2  x1  2.678  0.232  2.446 .IV.10.2. Оценить число итераций метода Ньютона для нахождения положительного корня уравнения sinx + x 2 –1 = 0 с точностью ε = 10 –4.Решение. Для начала локализуем корень.

Графически можно показать,что функции sin x и 1 – x 2 пересекаются на отрезке [0, 1]. Для более точного определения отрезка локализации для оценки производных заменимв уравнении sin x ≈ x:x 2 + x –1 = 0, положительный корень x = 0.5(–1 + 5 ) ≈ 0.618. В качествеотрезка локализации возьмем интервал [π/6, π/4] а в качестве начальногоприближения величину x0 ≈ 0,7.98IV.10. Задачи с решениямиТогдаM1 F ( x) ( F ( x))1   inf /6 x/4 /6 x /4sup  inf2 x  cos x  /6 x/4M 2  sup F ( x) /6 x/4111 0.4063 . / 3  cos  / 4sup 2  sin x  2  sin  / 4  1.2929 Тогда/6 x/4показатель квадратичного убыванияq = 0.5 M1M2 = 0.2626.По теореме 2 справедлива оценка| xn  x* |   q 2n 1n| x0  x* |2  .Подставляя грубую оценку |x0 – x*| ≈ 0,5, будем иметь для оценки необходимого числа итераций 0.5  0.26262n1 2 , или  0.13132n 1 2 104 , n  3 .Начиная от выбранного начального приближения x0 ≈ 0.7, получим последующие приближения метода Ньютона:x1 ≈ 0.63801, x2 ≈ 0.63673, x3 ≈ 0.63673.IV.10.3.

Доказать, что если методx n 1  x n F ( xn )Fx ( x n )F ( x n ) F 2 ( x n )2 Fx ( x n )3сходится, то порядок сходимости – третий.Решение. Используем представление этого метода в качестве методапростой итерации xn+1 = f(xn) с функциейf ( x)  x F ( x) F ( x) F 2 ( x).Fx ( x) 2  F  ( x) 3xВычислим производные этой функции в ряд Тейлора в корне нелинейного уравнения F(x*) = 0:99IV. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙf ( x)  1 F 2  FF F 2F F 2 F   2F F 2 F  3F 2 F 2 F 22 F 4,илиf ( x) FF F 2F F 22 F 3F F 2 F   2 F F 2 F  3F 2 F 22 F 4 F  3F 23F 2 F 2 F2  2 F 3 2 F 42 F 4.Множитель F 2 перед скобкой обеспечивает второй порядок нуляпроизводной f ′(x) в корне, поэтому сходимость не ниже квадратичной.Вторую производную правой части МПИ в корне можно не вычислять – она обращается в нуль при x = x* в силу множителя F2 перед скобкой.

Таким образом, сходимость не хуже кубической. Можно показать,что третья производная в корне в нуль не обращается, т.е. если сходимость имеет место, то с кубической скоростью.IV.10.4. В середине XIX века Ферхюльст для описания динамики популяционной системы предложил измерять ежегодно численность особейuk, где k – номер года. Относительная численность uk+1 полагалась пропорциональной численности в k год, однако она начинает убывать, когдаживотных становится много (uk сравнимо с 1):uk 1  uk (1  uk ), u0  aПусть численность популяции нормирована на максимальную возможную численность. Так как uk  [0,1] , то   [0, 4] .

Функция в правой части называется логистическим отображением.Исследовать свойства логистического отображения при значенияхпараметра 0    1  6. Представить графически последовательностьитераций логистического отображения при разных значениях параметра.Решение. Рассмотрим подробнее свойства отображенияuk 1  uk (1 uk ), u0  a.Заметим, что если f (0) = f (1) = 0 и max f (u) = f (0,5) = /4, то при0 < λ <4 интервал Х = [0, 1] отображается в себя, u  X.Рассмотрим вначале случай 0 < λ <1.

На Х = [0, 1] существует только одна предельная (или неподвижная) точка x = 0. Любая последова-100IV.10. Задачи с решениямительность, { f k (u0 )}k 0 сходится к предельной точке рассматриваемогоотображения x = 0. Если рассматривается популяционная модель, то этоозначает, что рассматриваемая популяция не может выжить.Из теоремы о сжимающем отображении следует, что последова-тельность {uk }n 0 сходится к своей предельной точке, если |fu′| ≤ 1.

Характеристики

Список файлов книги