Не накапливаются ошибки вычислений метод - Исправление ошибок и поиск оптимальных решений проблем

Добавил:

Upload

Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Предмет:

Файл:

теория.pdf

Скачиваний:

184

Добавлен:

11.05.2015

Размер:

5.05 Mб

Скачать

Отсюда можно гарантировать q(τ) <1 при τ (0,γ2). В частности, при

γ	0	≤ϕ (x)≤	1−γ	<1	.
τ = 1 справедлива оценка		′	α

Метод имеет линейную скорость сходимости.

Метод простых итераций и почти все другие итерационные методы имеют важное достоинство: в них не накапливаются ошибки вычислений. Ошибка вычислений эквивалентна некоторому ухудшению очередного приближения. Но это отразится только на числе итераций, а не на точности окончательного результата. Подобные методы устойчивы даже по отношению к грубым ошибкам (сбоям ЭВМ), если только ошибка не выбрасывает очередное приближение за пределы области сходимости.

6.5. Метод Ньютона

Этот метод называется также методом касательных или методом линеаризации. Если xk есть некоторое приближение к корню ξ , а f (x)

имеет непрерывную производную, то уравнение (6.1) можно преобразовать следующим образом:

0= f (ξ)= f [xk +(ξ−xk )]= f (xk )+(ξ−xk ) f ‘(θ).

Приближённо заменяя f ′(θ) на значение в известной точке xk , получим итерационный процесс Ньютона, который определяется линейным

уравнением	f (x )+ f (x )(x	−x )=0

		k	′	k	k +1		k
или в явном виде формулой							f (xk)
					xk +1=xk −		.	(6.11)
						′	k
y	f(x)							f (x )

				Геометрически этот процесс означает
			замену	на	каждой	итерации	графика
	x	x	y = f (x) касательной к нему (рис. 6.5).
	x2	x1 x0	(xk) к	Интуитивно ясно, что сходимость
			ξ		будет тем быстрее, чем ближе
Рис. 6.5 Итерации метода	функция f (x) к линейной и чем круче ее
	Ньютона	график	пересекает	ось	абсцисс;	так что

имеет смысл потребовать от f (x) , чтобы по модулю вторая ее производная была ограничена сверху, а первая снизу. Справедлива следующая теорема: Теорема 1: Пусть функция f (x) удовлетворяет условиям

| f ′(x)|≥α>0,

146

тогда, если члены последовательности (xk) , определенные методом Ньютона (6.11), при любом фиксированном k N0 принадлежат отрезку [a,b] и эта последовательность сходится на [a,b] к корню ξ уравнения (6.1), то справедливы неравенства ( k N0 )

\|ξ−xk +1\|≤	β	\|ξ−xk\|2	(6.12)
2α
\|ξ−xk +1\|≤	β	\|xk +1−xk\|2	(6.13)
2α

Первое из этих неравенств позволяет считать (6.11) методом второго порядка, а второе являясь апостериорной оценкой погрешности и может служить в качестве критерия прекращения процесса вычислений.

Метод

Ньютона

можно рассматривать

как

частный

случай метода

простых итераций, если положить

ϕ(x)

= x −

f (x)

′

′′

(x)

ϕ (x) =1−

f (x) f

(x)

Тогда

′

(6.14)

′

( f (x))

Если

есть

р-кратный

корень

уравнения,

то

вблизи

него

f (x)≈a(x−ξ) p;

отсюда

нетрудно

получить

ϕ ‘(ξ) = ( p −1) / p,

т.е.

0 ≤ ϕ ‘(ξ) <1.

Для

простого

корня р =

ϕ ‘(ξ) = 0.

Используя ранее

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

итерации сходятся, если всюду	f (x) f	′′		<( f	′	2 ; в противном случае

	(x)		(x))

сходимость будет не при любом нулевом приближении, а только в некоторой окрестности корня.

Сходимость вблизи любого корня монотонна, что легко видеть из рис.6.5; но вдали от корня возможна немонотонность итераций. Отметим, что рис.6.5 указывает ещё на одно достаточное условие сходимости итераций. Пусть f»(x) ≥ 0 справа от корня на отрезке [ξ, a]; если х0 выбрано также справа от корня на этом отрезке, то итерации сходятся, причём монотонно. То же будет, если f»(x) ≤ 0 слева от корня на отрезке [b, ξ], и на этом же отрезке выбрано нулевое приближение. Таким образом, итерации сходятся к корню с той стороны, с которой f (x) f ′′(x) >0 и справедлива следующая теорема:

147

Теорема 2: Пусть на отрезке [a,b] функция f (x) имеет первую и вторую производные постоянного знака и пусть f (a) f (b)<0 . Тогда, если точка x0

выбрана на [a,b] так, что

f (x0) f ′′(x0)>0 ,

то начатая с неё последовательность ( xk ), определяемая методом Ньютона (6.11), монотонно сходится к корню ξ (a,b) уравнения (6.1).

Оценим скорость сходимости вблизи простого корня. По определению простых итераций ξ −xk =ϕ(ξ) −ϕ(xk−1) . Разлагая правую часть по

формуле Тейлора и учитывая равенство ϕ′(ξ) = 0, получим

xk −ξ = 12 (xk−1 −ξ)2ϕ«(θ), θ (xk−1, ξ),

т.е. погрешность очередного приближения примерно равна квадрату погрешности предыдущего приближения. Например, если (k −1) —я итерация

давала 3 верных знака, то k -я даст примерно 6 верных знаков, а (k +1) -я –

примерно 12 знаков. Это иллюстрирует быструю сходимость вблизи корня. Разумеется, вдали от корня подобные соображения неприменимы.

Если вычисляется корень высокой кратности, то f'(x) в знаменателе формулы становится малой величиной вблизи корня. Чтобы не было потери точности, отношение f (x)/ f ′(x) нужно вычислять достаточно аккуратно. К

остальным погрешностям расчёта метод Ньютона хорошо устойчив.

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

Модифицированный метод Ньютона применяют,

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

xk +1=xk	−	f (xk )	,	f	′	.
	′
f	(x0)≠0
		(x0)

Метод имеет линейную скорость сходимости.

6.6. Метод секущих

В методе Ньютона требуется вычислять производную функции, что не всегда удобно. Можно заменить производную первой разделённой разностью, найденной по двум последним итерациям, т.е. заменить касательную секущей. Тогда получим

x	=x	−(xk −xk −1) f (xk ) .	(6.16)
k +1	k	f	(xk )− f (xk −1)

148

Для начала процесса надо задать х0 и	х1 (рис. 6.6). Такие процессы, где для
				вычисления очередного приближения нужно
y		f(x)	знать	два	предыдущих,	называют
	двухшаговыми.

				Эти, казалось бы, небольшие изменения
	x		x	сильно влияют на характер итераций.
		Например, сходимость итераций может быть
	x3 x2 x1	x0
	немонотонной не только вдали от корня, но и
Рис. 6.6 Итерации методау секущих	в малой окрестности корня.
				Скорость сходимости можно оценить,

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

xk +1−ξ=a (xk −ξ)(xk −1−ξ), a=	f «(ξ)	(6.17)
	.
2 f ‘(ξ)

Решение этого рекуррентного соотношения естественно искать в виде

степенной функции x	−ξ =aα (x − x)β	. Подставляя эту форму в
k +1	k
соотношение, получим

αβ = 1, β2 — β — 1 = 0.

Только положительный корень β квадратного уравнения соответствует убыванию ошибки, т.е. сходящемуся процессу. Следовательно, в методе секущих

x			−ξ	=a1/ β (x	−ξ)β ,
k +1		k
β	= 1	( 5	+1) ≈1,62; 1/ β ≈0,62,
	2

в то время как в методе Ньютона ошибка убывает быстрее (соответствуя β = 2). Но в методе Ньютона на каждой итерации нужно вычислять и функцию, и производную, а в методе секущих, – только функцию. Поэтому при одинаковом объёме вычислений в методе секущих можно сделать вдвое больше итераций и получить более высокую точность.

Взнаменателе формулы стоит разность значений функции. (Заметим, что приводить формулу к общему знаменателю не следует: увеличится потеря точности в расчётах.). Вдали от корня это несущественно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, что приводит к увеличению погрешности, начиная с некоторой итерации. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение невелико,

адля кратных может быть существенным.

Втакой ситуации применяют так называемый приём Гарвика:

выбирают не очень малое ε и ведут итерации до выполнения условия

149

f (x)

|xn + 1 – xn| < ε и затем продолжают расчёт до тех пор, пока величины

|xn+ 1 – xn| убывают. Первое же возрастание обычно означает начало увеличения погрешности, тогда расчёт прекращают и последнюю итерацию не используют.

6.7. Метод парабол

Если в методе Ньютона вместо производной вычислять разность первого порядка, то это можно рассматривать как замену функции

интерполяционным многочленом первой степени, построенным по узлам хn, хn-1. Но по трем последним итерациям можно построить интерполяционный многочлен второй степени, т.е. заменить график функции f (x) параболой.

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

az2 +bz +c =0,	(6.18)
где
z=x−xn, a= f (xn,xn−1, xn−2), b=a(x−xn)+F(xn,xn−1),	c=F(xn).

Тогда, решив уравнение, выбирают меньший по модулю корень, который будет определять новое приближение: х n+1= хn + z.

Очевидно, что для начала расчетов надо определить первые три приближения х0, х2 и х3. Обычно задают любые три числа из отрезка, на

котором ищется корень, но можно определить эти значения и иначе.

Метод парабол относится к трехшаговым методам. По сравнению с ранее изученными он сходится гораздо медленнее, но имеет следующее достоинство: даже если все предыдущие приближения действительны, этот метод может привести к комплексным числам. Во всех же остальных методах для сходимости к комплексному корню требуется задание комплексного начального приближения. Кроме того, метод парабол исключительно эффективен для нахождения всех корней многочлена высокой степени. Интересно заметить, что если f (x) – некоторый многочлен высокой степени,

то, хотя сходимость метода не доказана [Касаткин, 1978], при произвольном начальном приближении, на практике итерации всегда сходятся к какомулибо корню. По теореме Горнера для алгебраического многочлена частное f (x)/(x −xn) будет тоже многочленом, но меньшей степени. Поэтому,

последовательно удаляя найденные корни, можно найти все корни многочлена.

6.8. Комбинированный метод (хорд и касательных)

Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании. Комбинации методов могут быть

150

различны, но во всех случаях уточнение корня идет быстрее. Рассмотрим несколько вариантов расчетных схем комбинированного метода.

Метод касат.
Метод хорд	Метод хорд
	Метод касат.

Рис. 6.7 Графическая интерпретация комбинированного метода при f ‘(х)f «(х) > 0


Если	f (x) f	(x)	>	0	(рис. 6.7), то метод хорд дает приближение корня с
′	′′
недостатком,	а метод касательных – с избытком. Если же	f (x) f	(x)	<	0
′	′′

(рис. 6.8), то, наоборот, метод хорд дает приближение корня с избытком, а касательных – с недостатком.

	Методкасат.
	Методхорд
Методхорд	Методкасат.

Рис. 6.8 Графическая интерпретация комбинированного

метода при f ‘(х)f «(х) < 0

Однако во всех случаях истинный корень ξ заключен между промежуточными корнями, получающимися по методу хорд и методу касательных, т.е. выполняется неравенство

а < х < ξ Х< < b,

где х – значение корня с недостатком, а Х – с избытком.

Из этих соображений складывается следующая схема вычислений: в

первом случае, когда выполняется условие	f	(x) f	(x)	>	0	, то
	′	′′

151

последовательность {хi} (слева) образуется по методу хорд, а последовательность {Хi} (справа) образуется по методу касательных:

xi = xi−1 −

f (xi−1 ) ( X i−1 − xi−1 )

;

(6.19)

f ( X

i−1

) − f (x

)

i−1

X i = X i−1

−

f ( X i−1 )

f ′( X i−1 )

Во втором случае, когда

′

′′

слева лежит приближенное

(x) f (x)

значение корня, найденное по методу касательных, а справа – по методу хорд. При этом расчетные формулы будут несколько иные:

= xi−1

−

( xi−1 )

;

(6.20)

′(xi−1 )

X i =

X i−1

−

f ( X i−1 ) ( xi−1

− X i−1 )

f ( xi−1 ) − f

( X i−1 )

Другая вычислительная схема этого же метода дает более быструю

сходимость:

xi = xi−1 −

f (xi−1 ) ( X i−1

− xi−1 )

;

(6.21)

f ( X i−1 ) − f (xi−1 )

X i = xi −

f (xi )

f ′( xi

)

Для начала процесса в этом случае полагают x0 = a, X0 = b. За

приближенное

значение после окончания вычислений при любой из рассмотренных схем принимают среднее между Хn и хn: ξ ~ 1/2 (Хn + хn).

6.9. Методы ускорения сходимости

В применении к некоторым уравнениям рассмотренные итерационные методы сходятся довольно медленно. В таких случаях особое значение приобретают способы, позволяющие оптимизировать итерационный процесс путем ускорения сходимости метода итераций. Один из наиболее часто употребляющихся алгоритмов – метод Эйткена ускорения сходимости.

Главным является требование линейной сходимости основного итерационного метода. В случае методов, имеющих более высокую скорость сходимости, ускорение по Эйткену неэффективно. Метод состоит в том, что

после вычисления xn, xn+1 и xn+2 производится пересчет по формуле

yn+1 = xn+2	−	(xn+2	− xn+1)2
			(6.22)
xn+2	−
		2xn+1 + xn

и значение yn+1 принимается за новое приближение. Оно дает лучшее приближение к корню, чем очередная итерация xn+2. На практике не обязательно проводить пересчет на каждой итерации. Обычно он

152

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

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

Метод Вегстейна – улучшенный по Эйткену метод простой итерации;

– записан в виде, позволяющем проверять целесообразность пересчета:

= x

n+1

−

xn+1 − xn

xn − xn−1

(6.23)

−1

xn+1

− xn

Если rn почти постоянны, то использование в качестве очередного

приближения yn+1 сильно ускорит сходимость. Итерации прекращают, если выполняется

(xn+2 − xn+1)2	< ε.
xn+2 − 2xn+1 + xn

Метод Стеффенсена имеет квадратичную сходимость, – более быструю, чем исходный метод релаксации:

xn+1	= xn −	f 2	(xn )	.	(6.24)
f (xn ) − f (xn − f (xn ))

153

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Значит, успех метода зависит от того, насколько удачно выбрано . Например, для извлечения квадратного корня, т. е. решения уравнения можно положить или и соответственно написать такие итерационные процессы:

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

Каков практический критерий сходимости, т. е. когда надо прекращать итерации Из (24) видно, что если то итерации попеременно оказываются то с одной, то с другой стороны корня, так что корень заключен в интервале Это надежная, хотя несколько грубая оценка. Но она неприменима при когда итерации сходятся к корню монотонно, т. е. с одной стороны.

Вблизи корня итерации сходятся примерно как геометрическая прогрессия со знаменателем Чтобы сумма дальнейших ее членов не превосходила , должен выполняться критерий сходимости

При выполнении этого условия итерации можно прекращать.

Легко заметить, что выражение в левой части есть поправка Эйткена (4.24). Если последние три простые итерации уточнить процессом Эйткена, то это обычно заметно повышает точность расчета и позволяет ограничиться меньшим числом итераций.

При обработке эксперимента возникают стохастические задачи, где ошибки определения функции велики и носят случайный характер. Погрешность функции приводит к погрешности корня . Однако поскольку ошибки носят случайный характер, то методами статистики можно определить корень гораздо более точно, чем по указанной оценке. Рассмотрим простые итерации

при дополнительных условиях

которым удовлетворяет, например, последовательность Доказано [47], что при с вероятностью единица. Использование в формуле (27 а) знака производной не означает, что надо вычислять эту производную: достаточно лишь определить ее знак по разности двух значений функции.

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

Источник

Численные методы решения трансцендентных уравнений

Аннотация

Основной целью данной курсовой работы является изучение и сравнительный анализ численных методов решения трансцендентных уравнений.

В данной курсовой работе рассмотрено 5 методов решения трансцендентных уравнений.

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

Методы решения трансцендентных уравнений делятся на прямые и итерационные. Прямые методы позволяют записать корни в виде некоторого конечного соотношения или в виде формулы. Итерационные методы являются приближенными методами.

Оглавление:

)Введение

2)Общая информация

)Метод половинного деления (Дихотомии)

)Метод простой итерации

)Метод хорд

6)Метод Ньютона (Метод касательных, линеаризации)

7)Метод хорд и касательных

)Заключение

9)Литература

10)Приложение

1. Введение

Трансцендентное уравнение — уравнение <#»9″ src=»doc_zip1.jpg» />

Более строгое определение таково:

Трансцендентное уравнение — это уравнение вида , где функции и являются аналитическими функциями <#»justify»>Актуальность этих методов с момента создания и по сей день присутствует во многих областях жизни человека.

Объект исследования — рассмотрение методов решения трансцендентных уравнений.

Поставлены следующие задачи:

проанализировать приведенные методы;

выбрать один из методов;

создать контрольный вариант;

разработать алгоритм;

реализовать алгоритм на языке программирования;

проверить работоспособность алгоритма;

2. Общая информация

Основные понятия

Алгебраические уравнения (в канонической форме):

аn× x n + an-1× x n-1 + … + a1×x + a0 = 0

Трансцендентные уравнения — в которых переменная х находится под знаком трансцендентной функции:

показательная а х ;

логарифмическая log a x ;

тригонометрические sin x ;

cos x ;

tg x ;

Решение нелинейного уравнения не всегда возможно и не всегда целесообразно, поэтому решение таких уравнений ведется приближённо.

Пусть существует такая непрерывная функция f(x) и требуется найти все или некоторые корни уравнения:

f(x)=0, (1).

Допустим, существует такой корень x уравнения f(x)=0, что он сводит его в тождество f(x)=0, тогда, решая уравнение каким-либо численным методом, мы находим приближённое значение корня x*, с погрешностью r. r — абсолютная погрешность.

Итак, во-первых, необходимо найти количество и расположение этих корней. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них необходимые нам корни, а также уточнить их приближённые значения. Первые две задачи можно решить аналитическими, либо графическими методами.

Для отделения корней существуют различные методы. Например, это может быть ясно из смысла задачи.

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

Таблица(1)

x-¥-11+¥ f(x)-+-+

Но выявить по таблице корень четной кратности крайне сложно.

Также, возможно отделение корней с помощью построения графика функции y = f(x), где приближенные значения действительных корней уравнения f(x) = 0 соответствуют абсциссам точек пересечения или касания графика с осью 0x. Помимо этого, построение графика часто позволяет найти корни чётной кратности.

«Иногда удается заменить уравнение (1) эквивалентным ему уравнением ?(x)=?(x), в котором функции y1= ?(x) и y2= ?(x) имеют несложные графики. Например, уравнение x*sin(x)-1=0 удобно преобразовать к виду sin(x)=1/x. Абсциссы точек пересечения этих графиков будут корнями исходного уравнения».

Но наиболее распространен следующий метод: если на концах некоторого интервала [a, b] значения непрерывной функции f(x) имеют разные знаки, то на этом интервале уравнение F(x)=0 имеет хотя бы один корень. При этом корень является единственным, если производная функции f'(x) существует и сохраняет свой знак внутри интервала [a, b].

3. Метод половинного деления (Дихотомии)

На мой взгляд, самый легкий метод. Он прост и очень надёжен. К простому корню метод дихотомии сходится для любых непрерывных функций, в том числе недифференцируемых. Он устойчив к ошибкам округления.

Его суть заключается в построении отрезков, но при этом на каждом шаге очередной отрезок делится пополам и в качестве следующего отрезка берется та половина, на которой значения функции в концах имеют разные знаки. Процесс продолжают до тех пор, пока длина очередного отрезка не станет меньше, чем величина 2?. Тогда его середина и будет приближенным значением корня с точностью ?.

Рис. 1

Для этого метода существенно, чтобы функция f(x) была непрерывна и ограничена в заданном интервале [a, b], внутри которого находится корень. Предполагается также, что значения функции на концах интервала f(a) и f(b) имеют разные знаки, т.е. выполняется условие f(a)f(b) < 0.

Алгоритм данного метода можно записать так:

.Ввести данные (a, b, ?).

.Если нужная точность достигнута (| b — a | < 2?) то иди к п.6

.Возьми середину очередного отрезка (x= ( a + b )/ 2).

.Если значения функции в точках a и c одного знака (f(a)*f(c)>0), то в качестве следующего отрезка взять правую половину (а=c), иначе левую (b=c).

.Иди к п.2.

.Напечатать ответ c=…

Метод половинного деления легко реализуется и является наиболее универсальным среди итерационных методов уточнения корней. Его применение гарантирует получение решения для любой непрерывной функции f(x), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения.

Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Однако существуют, иногда довольно значительные, недостатки метода половинного деления. Как уже говорилось выше, для того чтобы решить уравнение необходимо найти отрезок, на котором функция меняет свой знак. И если в этом отрезке не один корень, то неясно, к какому из корней сойдется метод (к одному корню сойдется точно). Также метод неприменим для корней чётной кратности. Наконец, не используется для систем уравнений.

Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.

Один из минусов метода половинного деления (сходимость неизвестно к какому корню) имеется у всех итерационных методов, почти у всех. В таком случае может помочь только удаление ранее найденных корней. Однако, как я заметил, уменьшается точность методов.

Реализация удаления корней: « Если x1 есть простой корень уравнения f(x) непрерывна, то вспомогательная функция g(x)=f(x)/(x-x1) непрерывна, причем все нули функций f(x) и g(x) совпадают, за исключением x1, то он будет нулем g(x) кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы».

Пример. Необходимо методом дихотомии уточнить корень уравнения х 3 — 3× х +1 = 0 с точностью 10 -3 (табл. 2) .

Таблица 2

Na nb nf(x n)0010,5-0,375100,50,250,265620,250,50,375-0,072330,250,3750,31250,093040,31250,3750,34380,009250,34380,3750,3594-0,031860,34380,35940,3516-0,011370,34380,35160,3477-0,001180,34380,34770,34580,004090,34580,34770,34680,0013100,34680,34770,3473

|a10 — b10| = |0,3468 — 0,3477| = 0,0009 < , где = 0,001.

x » 0,347 .

4. Метод простой итерации

Или метод последовательных приближений. Чтобы применить этот метод для решения уравнения (1) необходимо преобразовать его к виду . Далее выбирается начальное приближение и вычисляется x1, затем x2 и т.д.:

x1 = j(x0);

x2 = j(x1);

…;

xk = j(xk-1);

Если xn стремится к некоторому пределу x, то этот предел и есть корень уравнения.

Полученная последовательность сходится к корню при выполнении следующих условий:f

) функция j(x) дифференцируема на интервале [a, b].

) во всех точках этого интервала j¢(x) удовлетворяет неравенству:

0 £ q £ 1 (2)

При таких условиях скорость сходимости является линейной, а итерации следует выполнять до тех пор, пока не станет справедливым условие:

. (3)

Критерий вида

, (4)

может использоваться только при 0 £ q £ ½. Иначе итерации заканчиваются преждевременно, не обеспечивая заданную точность. Если вычисление q затруднительно, то можно использовать критерий окончания вида

; . (5)

Возможны различные способы преобразования уравнения (1) к виду . Следует выбирать такой, который удовлетворяет условию (4), что порождает сходящийся итерационный процесс, как, например, это показано на рис. 2, 3. В противном случае, в частности, при ½j¢(x)½>1, итерационный процесс расходится и не позволяет получить решение (рис. 4).

Рис. 2

Рис. 3

Рис.4

Говорят, что итерационный процесс сходится, если при выполнении последовательных итераций получаются значения корней, все ближе и ближе приближающиеся к точному значению корня. В противном случае итерационный процесс считается расходящимся.

Почти все итерационные методы, в том числе и метод простых итераций, имеют важное достоинство: в них не накапливаются ошибки вычислений. Эта ошибка эквивалентна некоторому ухудшению следующего приближения. Однако это не отразится на результате и будет заметно лишь по количеству итераций.

Даже грубые ошибки не могут причинить видимого вреда. Но только если ошибка не выбрасывает приближение за пределы области сходимости.

Пример. Необходимо методом итераций уточнить корень xÎ[0;1] уравнения: х 3 — 3×х +1 = 0, с точностью 10 -3 (табл. 3).

Преобразованное уравнение:

Таблица 3

nх nj (x n)000,333310,33330,345720,34570,347130,34710,347340,3473

êх 4 — х 3 ê < e

x » 0,347.

5. Метод хорд

Или метод пропорциональных частей, хотя я так и не понял почему. Пусть дано уравнение f(x) = 0, где f(x) — непрерывная функция, имеющая в интервале (a, b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a, b].

Идея метода хорд состоит в том, что на достаточно малом промежутке [a, b] дугу кривой y = f(x) можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай, когда первая и вторая производные имеют одинаковые знаки, т.е. f ‘(x)f ²(x) > 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

. (6)

Приближение корня x = x1, для которого y = 0, определяется как

. (7)

Аналогично для хорды, проходящей через точки A1 и B, вычисляется следующее приближение корня

. (8)

В общем случае формула метода хорд имеет вид:

. (9)

Если первая и вторая производные имеют разные знаки, т.е.

‘(x)f «(x) < 0,

то все приближения к корню x* выполняются со стороны правой границы отрезка [a, b], как это показано на рис. 6, и вычисляются по формуле:

. (10)

Выбор формулы в каждом конкретном случае зависит от вида функции f(x) и осуществляется по правилу: неподвижной является граница отрезка [a, b] изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (9) используется в том случае, когда f(b)f «(b) > 0. Если справедливо неравенство f(a)f «(a) > 0, то целесообразно применять формулу (10).

Рис. 5 Рис. 6

Рис. 7Рис. 8

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

. (11)

Тогда условие завершения вычислений записывается в виде:

. (12)

где e — заданная погрешность вычислений. Необходимо отметить, что при отыскании корня метод хорд нередко обеспечивает более быструю сходимость, чем метод половинного деления.

Пример. Необходимо методом хорд уточнить корень x Î [0;1] уравнения х 3 — 3×х + 1 = 0 с точностью 10 -3 (табл. 4) .

;

а = 0; f(a) = 1.

Таблица 4

nх nx n — a f(x n )011-1-0,510,50,5-0,375-0,363620,36360,3636-0,0427-0,348730,34870,3487-0,0037-0,347440,34740,3474-0,0003-0,347350,3473

½x 5 — x 4½ < e.

x » 0,347.

6. Метод Ньютона (Метод касательных, линеаризации)

Пусть уравнение (1) имеет корень на отрезке [a, b], причем f ‘(x) и f «(x) непрерывны и сохраняют постоянные знаки на всем интервале [a, b].

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной. Для этого выбирается некоторое начальное приближение корня x0 на интервале [a, b] и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) до пересечения с осью абсцисс. Уравнение касательной в точке C0 имеет вид

= f(x0) + f ‘(x0)×(x — x0). (13)

Далее за приближение корня принимается абсцисса x1, для которой y = 0:

(14)

Затем проводится касательная через новую точку C1(x1, f(x1)) и определяется точка x2 ее пересечения с осью 0x и т.д. В общем случае формула метода касательных имеет вид:

(15)

В результате вычислений получается последовательность приближенных значений x1, x2, …, xi, …, каждый последующий член которой ближе к корню x*, чем предыдущий.

Начальное приближение x0 должно удовлетворять условию:

(x0) f ¢¢(x0) > 0. (16)

В противном случае сходимость метода Ньютона не гарантируется, так как касательная будет пересекать ось абсцисс в точке, не принадлежащей отрезку [a, b]. На практике в качестве начального приближения корня x0, обычно выбирается одна из границ интервала [a, b], т.е. x0 = a или x0 = b, для которой знак функции совпадает со знаком второй производной.

Метод Ньютона обеспечивает высокую скорость сходимости при решении уравнений, для которых значение модуля производной ½f ¢(x)½вблизи корня достаточно велико, т.е. график функции y = f(x) в окрестности корня имеет большую крутизну. Если кривая y = f(x) в интервале [a, b] почти горизонтальна, то применять метод касательных не рекомендуется.

Существенным недостатком рассмотренного метода является необходимость вычисления производных функции для организации итерационного процесса. Если значение f ¢(x) мало изменяется на интервале [a, b], то для упрощения вычислений можно пользоваться формулой

, (17)

т.е. значение производной достаточно вычислить только один раз в начальной точке. Геометрически это означает, что касательные в точках Ci(xi, f(xi)), где i = 1, 2, …, заменяется прямыми, параллельными касательной, проведенной к кривой y = f(x) в начальной точке C0(x0, f(x0)).

В заключение необходимо отметить, что все изложенное справедливо в том случае, когда начальное приближение x0 выбрано достаточно близким к истинному корню x* уравнения. Однако это не всегда просто осуществимо. Поэтому метод Ньютона часто используется на завершающей стадии решения уравнений после работы какого-либо надежно сходящегося алгоритма, например, метода половинного деления. Скорость сходимости велика для простого корня и соответствует скорости геометрической прогрессии для кратного корня.

Упрощенный вариант метода

Если » const , то » (см. рис. 9)

Рис. 9

. (18)

Замечание. Данный вариант метода актуален, если производная сложна.

Пример. Необходимо методом касательных уточнить корень xÎ [0;1] уравнения

с точностью 10 -3 (табл. 5) .

Таблица 5

N001-3-0,333310,33330,0371-2,6667-0,013920,34720,0003-2,6384-0,000130,3473ïx 3 — x 2ï < e .

x » 0,347 .

. Метод хорд и касательных

Применяется только в том случае, когда f'(X) и f»(X) не изменяют знака на отрезке [a,b], т.е. функция f(X) на отрезке [a,b] монотонна и не имеет точек перегиба.

Суть метода та же самая — построение последовательности вложенных отрезков, содержащих корень, однако отрезки строятся по-другому. На каждом шаге через концы дуги графика функции f(X) на очередном отрезке проводят хорду и из одного конца проводят касательную. Точки пересечения этих прямых с осью Оx и образуют следующий отрезок. Процесс построения прекращают при выполнении того же условия:

(| b — a | < 2?). (19)

Для того, чтобы отрезки получались вложенными, нужно проводить ту касательную из конца, которая пересекает ось ОХ на отрезке [a,b]. Перебрав четыре возможных случая, легко увидеть, что касательную следует проводить из того конца, где знак функции совпадает со знаком второй производной.

Также несложно заметить, что касательная проводится либо все время из правого, либо все время из левого конца. Будем считать для определенности, что этот конец — b .

Формулы, употребляемые в методе, хорошо известны из аналитической геометрии:

Уравнение хорды, проходящей через точки (a,f(a)) и (b,f(b)):

трансцендентное уравнение дихотомия

y = f(a)+(x-a)*(f(b)-f(a))/(b-a),

откуда точка пересечения с осью Оx:

x= a — f(a) *(b-a)/(f(b)-f(a)).

Уравнение касательной, проходящей через точку (b,f(b)): y=f(b)+f'(b)(x-b), откуда точка пересечения с осью Оx:

x= b — f(b)/f'(b).

При составлении алгоритма снова естественно использовать для концов отрезка только две переменные a и b и писать:

a= a — f (a) *(b-a)/ (f (b)-f (a)) (20)

b= b — f(b)/f'(b) (21)

Однако, в этом случае важен порядок формул (20) и (21).

Пример. Необходимо комбинированным методом уточнить корень xÎ[0;1] уравнения: х 3 — 3 × х +1 = 0, с точностью 10 -3 (табл. 6) .

Таблица 6

nx n f(x n)

00 11 -0,5 -3 -0,33331-1 10,3333 0,16670,0371 -0,0150 -2,6667 -0,01390,5-0,3750 20,3472 0,00110,0003 -0,0001 -2,6384 -0,00010,34830,0027 30,3473 00,3473

ê ê< e . x » 0,347 .

8. Заключение

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

9. Литература

.Вычислительная техника и программирование: Учеб. для техн. вузов/ А.В. Петров, В.Е. Алексеев, А.С. Ваулин и др. — М.: Высш. шк., 1990г. 479 стр. ISBN: 1522608, 1522607.

2.Гусев В.А., Мордкович А.Г. — Математика: Справ. материалы: Кн. для учащихся. — 2-е изд. — М.: Просвещение, 1990г. — 416 стр. ISBN 5-09-001292-X.

.Березин В.Л., Харитонова К.Ю. «Просмотрщик решений трансцендентных уравнений и его применение в задачах волоконной оптики», Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2004г. 168-170 стр.

.Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе. — М.: Мир, 1977г. — 584 стр.

.Демидович Б.П., Марон И.А. «Основы вычислительной математики». — М.: Наука, 1970г. — 664 стр.

6.<#»justify»>10. Приложение

Листинг программы для решения трансцендентного уравнения

Находит лишь один корень, т.к. удаление других корней не реализовано.

uses crt;, a, b, c, eps: real;f(y: real):real; //функция

f := y*y*y-y+1; //заданное уравнение

end;

begin

ClrScr;

Writeln(‘Введите требуемую точность’); //ввод точности вычисления

readln(eps);

Writeln(‘Введите a’); //задание интервала

readln(a);

Writeln(‘Введите b’); //задание интервала

readln(b);:= (a+b)/2;abs(b-a) > eps dof(a)*f(c) < 0 then b := c //проверка значенияa := c;:= (a+b)/2; //разбитие отрезка;:= (a+b)/2;(‘x = ‘, x:6:10);;.

Блок схема программы:

Источник

Итерационные методы решения системы линейных алгебраических уравнений

В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

Общие сведения об итерационных методах или методе простой итерации

Метод итерации — это численный и приближенный метод решения СЛАУ.

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .

Рассмотрим систему A x = b .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.

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

b i j = — a i j / a i i , i , j = 1 , 2 . . . , n

Элементы (компоненты) вектора d вычисляются по следующей формуле:

d i = b i / a i i , i = 1 , 2 , . . . , n

Расчетная формула метода простой итерации:

x ( n + 1 ) = B x ( x ) + d

Матричная запись (координатная):

x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b

Критерий окончания в методе Якоби:

x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε

В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:

x ( n + 1 ) — x ( n ) ε

Решить СЛАУ методом Якоби:

10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10

Необходимо решить систему с показателем точности ε = 10 — 3 .

Приводим СЛАУ к удобному виду для итерации:

x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1

Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.

В таком случае, первая итерация имеет следующий внешний вид:

x 1 ( 1 ) = — 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = — 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 — 0 , 1 × 1 + 1 = 1 , 01

Аналогичным способом вычисляются приближения к решению:

x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111

Находим норму матрицы В , для этого используем норму B ∞ .

Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:

x ( n + 1 ) — x ( n ) ε

Далее вычисляем нормы разности векторов:

x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .

Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.

x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .

Метод Зейделя

Метод Зейделя — метод является модификацией метода Якоби.

Суть: при вычислении очередного ( n + 1 ) — г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) — е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n — о е приближение, как в методе Якоби.

x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +

+ . . . + b i m x m ( n ) + d i

За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.

Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

Решим 3 системы уравнений:

2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1

Приведем системы к удобному для итерации виду:

x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .

Отличительная особенность, условие сходимости выполнено только для первой системы:

Вычисляем 3 первых приближения к каждому решению:

1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109

Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.

2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129

Итерационный процесс разошелся.

Решение: x 1 = 1 , x 2 = 2

3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2

Итерационный процесс зациклился.

Решение: x 1 = 1 , x 1 = 2

Метод простой итерации

Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

x = x — τ ( A x — b ) , τ — итерационный параметр.

Расчетная формула имеет следующий внешний вид:

x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .

Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .

Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .

τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .

Лекция 5. Итерационные методы решения уравнений и систем

5.1 Простая итерация. Уравнения с одним неизвестным.Пусть задана непрерывная функция f(x) и требуется найти все или некоторые корни уравнения

Эта задача распадается на несколько задач. Во-первых, надо исследовать характер и расположение корней. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью.

Первая и вторая задачи решаются аналитическими и графическими методами. Например, многочлен

имеет n комплексных корней, не обязательно различных, и все корни лежат внутри круга

Когда ищутся только действительные корни уравнения, то полезно составить таблицу значений f(x). Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере один). Если эти узлы близки, то, скорее всего, корень между ними только один. Но выявить по таблице корни четной кратности сложно.

По таблице можно построить график функции y=f(x) и графически найти точки его пересечения с осью абсцисс. Этот способ более нагляден и дает неплохие приближенные значения корней. Во многих задачах такая точность уже достаточна. В технике еще популярны графические методы решения уравнений (номография). Построение графика зачастую позволяет выявить даже корни четной кратности.

Иногда удается заменить уравнение (5.1.1) эквивалентным ему уравнением φ(x) = ψ(x), в котором функции и имеют несложные графики. Например, уравнение x sin x – 1 = 0 удобно преобразить к виду sin x = 1/x. Абсциссы точек сечения этих графиков будут корнями исходного уравнения.

Дихотомия (деление пополам). Пусть мы нашли такие точки , , что , т.е. на отрезке лежит не менее одного корня уравнения. Найдем середину отрезка и вычислим . Из двух половин отрезка выберем ту, для которой , ибо один из корней лежит на этой половине. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т.д. (рис. 5.1).

Если требуется найти корень с точность ε, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2ε. Тогда середина последнего отрезка даст значение корня с требуемой точностью.

Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т.е. уточнение трех цифр требует 10 итераций. Зато точность ответа гарантируется.

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

Дихотомия применяется тогда, когда требуется высокая надежность счета, а скорость сходимости малосущественна.

Удаление корней. Один из недостатков дихотомии – сходимость неизвестно к какому корню – имеется почти у всех итерационных методов. Его можно устранить удалением уже найденного корня.

Если есть простой корень уравнения (5.1.1) и f(x) липшиц-непрерывна, то вспомогательная функция непрерывна, причем все нули функции f(x) и g(x) совпадают, за исключением , ибо Если – кратный корень уравнения (5.1.1), то он будет нулем функции кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы.

Поэтому найденный корень можно удалить, т.е. перейти к функции . Тогда нахождение остальных нулей f(x) сведется к нахождению нулей . Когда мы найдем какой-нибудь корень функции , то этот корень тоже можно удалить, вводя новую вспомогательную функцию

= . Так можно последовательно найти все корни f(x).

Строго говоря, мы находим лишь приближенное значение корня . А функция имеет нуль в точке и полюс в близкой к ней точке (рис. 5.2); только на некотором расстоянии от этого корня она близка к . Чтобы это не сказывалось при нахождении следующих корней, надо вычислять каждый корень с высокой точностью.

Кроме того, в любом методе окончательные итерации вблизи определяемого корня рекомендуется делать не по функциям типа , а по исходной функции . Последние итерации, вычисленные по функции , используются при этом в качестве нулевого приближения. Важно это при нахождении многих корней, ибо чем больше корней удалено, тем меньше нули вспомогательной функции соответствуют остальным нулям функции .

Учитывая эти предосторожности и вычисляя корни с 8-10 верными десятичными цифрами, зачастую можно определить десятка два корней, о расположении которых заранее ничего не известно (в том числе корней высокой кратности p

Метод простых итераций. Заменим уравнение (5.1.1) эквивалентным ему уравнением . Это можно сделать многими способами, например, положив , где – произвольная непрерывная знакопостоянная функция. Выберем некоторое нулевое приближение и вычислим дальнейшие приближения по формулам

(5.1.2)

Очевидно, если стремится к некоторому пределу , то этот предел есть корень исходного уравнения.

Исследуем условия сходимости. Если имеет непрерывную производную, тогда

(5.1.3)

где точка ξ лежит между точками и . Поэтому если всюду , то отрезки убывают не медленней членов геометрической прогрессии со знаменателем и последовательность сходится при любом нулевом приближении. Если , то в силу непрерывности больше единицы и в некоторой окрестности корня; в этом случае итерации не могут сходится. Если , но вдали от корня , то итерации сходятся, если нулевое приближение выбрано достаточно близко к корню; при произвольном нулевом приближении сходимости может не быть.

Очевидно, что чем меньше q, тем быстрее сходимость. Вблизи корня асимптотическая сходимость определяется величиной и будет особенно быстрой при .

Значит, успех метода зависит от того, насколько удачно выбрано . Например, для извлечения квадратного корня, т.е. решения уравнения , можно положить или и соответственно написать такие итерационные процессы:

Первый процесс вообще не сходится, а второй сходится при любом ; сходится он очень быстро, ибо . Второй процесс используют при извлечении корня на калькуляторах.

Каков практический критерий сходимости, т.е. когда надо прекращать итерации (5.1.2)? Из (5.1.3) видно, что если , то итерации попеременно оказываются то с одной, то с другой стороны корня, так что корень заключен в интервале . Это надежная, хотя несколько грубая оценка. Но она неприменима при , когда итерации сходятся к корню монотонно, т.е. с одной стороны.

Вблизи корня итерации сходятся примерно, как геометрическая прогрессия со знаменателем . Чтобы сумма дальнейших ее членов не превосходила ε, должен выполняться критерий сходимости

(5.1.5)

При выполнении этого условия итерации можно прекращать.

Метод простых итераций и почти все другие итерационные методы имеют важное достоинство: в них не накапливаются ошибки вычислений. Ошибка вычислений эквивалентна некоторому ухудшению очередного приближения. Но это отразится только на числе итераций, а не на точности окончательного результата. Подобные методы устойчивы даже по отношению к грубым ошибкам (компьютерного сбоя), если только ошибка не выбрасывает очередное приближение за пределы области сходимости.

Метод Ньютона. Он называется также методом касательных или методом линеаризации. Если есть некоторое приближение к корню , а имеет непрерывную производную, то уравнение (5.1.1) можно преобразоватьть следующим образом:

Приближенно заменяя на значение в известной точке , получим такой итерационный процесс:

(5.1.6)

Геометрически этот процесс означает замену на каждой итерации графика касательной к нему (рис. 28).

Метод Ньютона можно рассматривать как частный случай метода простых итераций, если положить . Тогда Если есть р-кратный корень уравнения (5.1.1), то вблизи него ; отсюда нетрудно получить , т.е. . Для простого корня и . Используя результаты п.4, можно сформулировать следующие условия сходимости итерации (28). Если нулевое приближение выбрано достаточно близко к корню, ньютоновские итерации сходятся; скорость сходимости велика для простого корня и соответствует скорости геометрической прогрессии для кратного корня. При произвольном нулевом приближении итерации сходятся, если всюду ; в противном случае сходимость будет не при любом нулевом приближении, а только в некоторой окрестности корня.

Сходимость вблизи любого корня монотонна, что легко видеть на рис. 28; но вдали от корня возможна немонотонность итерации. Отметим, что рис. 28 указывает еще на одно достаточное условие сходимости итерации. Пусть справа от корня на отрезке ; если выбрано также справа от корня на этом отрезке, то итерация (28) сходится, причем монотонно. То же будет, если слева от корня на отрезке , и на этом же отрезке выбрано нулевое приближение. Таким образом, итерации сходятся к корню с той стороны, с которой .

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

(5.1.7)

Т а б л и ц а 1

n	, метод Ньютона	, метод секущих
1,0000	1,0000
2,5000	2,5000
2,0500	1,8571
2,0001	1,9836

т.е. погрешность очередного приближения примерно равна квадрату погрешности предыдущего приближения. Например, если (n-1)-я итерация давала 3 верных знака, то n-я даст примерно 6 верных знаков, а (n+1)-я – примерно 12 знаков. Это иллюстрирует быструю сходимость вблизи корня. Разумеется, вдали от корня подобные соображения неприменимы.

Если вычисляется корень высокой кратности, то в знаменателе формулы (28) становится малой вблизи корня. Чтобы не было потери точности, отношение надо вычислять достаточно аккуратно. К остальным погрешностям расчета метод Ньютона хорошо устойчив.

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

П р и м е р. Рассмотрим решение уравнения . Тогда общая формула метода Ньютона (5.1.6) принимает вид

Мы получили вторую формулу (5.1.4), которая, как отмечалось раньше, позволяет очень быстро находить квадратный корень с помощью только сложения и деления. Для иллюстрации в таблице 16 приведен ход итерации при извлечении квадратного корня из а = 4.Видно, что сходимость очень быстрая; несмотря на неважное нулевое приближение, уже третья итерация дает точность 0,005%. Попутно можно заметить, что вблизи корня итерация сходится с одной стороны, т.е. монотонно, хотя первая итерация дает переброс на другую сторону корня.

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

(5.1.8)

Для начала процесса надо задать и (рис. 29). Такие процессы, где для вычисления очередного приближения надо знать два предыдущих, называют двухшаговыми.

Эти небольшие изменения сильно влияют на характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня. Скорость сходимости также изменяется. Приведенный в таблице 1 для сравнения расчет по методу Ньютона показывает, что метод секущих сходится медленнее, т.к. в методе Ньютона ошибка убывает быстрей. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих – только функцию.

В знаменателе формулы (5.1.8) стоит разность значений функции; вдали от корня это несущественно, но вблизи корня значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счета, что ограничивает точность.

От «разболтки» страхуются так называемым приемом Гарвика. Выбирают не очень малое значение ε, ведут итерации до выполнения условия и затем продолжают расчет до тех пор, пока убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчет прекращают и последнюю итерацию не используют.

Метод парабол. Метод секущих основан на замене функции ф(х) интерполяционным полиномом первой степени по узлам x_n , x_n_-1 . По трем последним итерациям можно построить полином второй степени, т.е. заменить график функции параболой. Примем этот полином в форме Ньютона:

Приравняв его нулю, получим квадратноеуравнение

Меньший по модулю из двух корней квадратного уравнения определяет новое приближение x_n₊₁=x_n+z .

Для начала расчета надо задать три первых приближения х₀ ,х₁ ,х₂ (обычно наугад), т.е. процесс является трехшаговым.

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

В этом методе «разболтка» счета вблизи корня сказывается еще больше, чем в методе секущих, т.к. в расчете участвуют вторые разности, но все-таки корни можно найти с хорошей точностью; для определения оптимального числа итераций добно пользоваться приемом Гарвика (см. выше).

Метод парабол исключительно эффективен для нахождения всех корней многочлена высокой степени.

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

Для определенности запишем систему линейных уравнений четвертого порядка в виде + =0, где = (i,y=1,2,3,4), векторы

= , = .

Разрешим первое из уравнений относительно x₁ , второе – относительно x₂ и т.д. Тогда эту систему можно переписать в виде

= — (i=1, 2, 3, 4; k=1, 2, 3, 4, 5) . (2)

Система (1) является частным случаем записи вида

При этом линейная функция, например, L₁(x₁, x₂, x₃, x₄) фактически не зависит от x₁ согласно (1). Выводы не изменятся, если она будет содержать слагаемое вида α₁₁x₁ .То же относится к правым частям остальных уравнений.

Зададим произвольные начальные значения неизвестных , , , . Подставляя эти значения в правые части системы (3), получим первые приближения:

=L₁( , , , ) ,

=L₄( , , , ).

Полученные первые приближения могут быть таким же образом использованы для получения вторых, третьих и т.д., так что для любого ν можно получить ν-е приближение , , , .

Можно установить условия, которые обеспечат сходимость получающихся приближений к истинному решению системы x₁, x₂, x₃, x₄, для чего достаточно отличия от нуля определителя системы detA≠0.

Обозначим через ошибку ν-го приближения для k-го неизвестного

= – x_k ,

где x_k – точное значение неизвестного в решении системы, которое предполагается существующим.

Показано, что для сходимости итерационного процесса к точному решению системы в этом способе достаточно выполнения условия С (ν) =L₁ (x₁ (ν-1) , x₁ (ν-1) ,…),

Иначе говоря, следующее приближение полностью определялось значениями, полученными на предыдущем шаге. Между тем уже при построении первого приближения можно, например, вычисляя значение x₂ (1) , воспользоваться для x₁ не нулевым приближением x₁ (0) , а уже полученным нами первым приближением x₁ (1) . Вычисляя χ₃ , можно использовать уже не только x₁ (1) , но и x₂ (1) и т. д.

Таким образом, вместо формул (1) предлагается использовать для отыскания следующего приближения формулы такого вида (мы снова пишем их для конкретного случая системы четырех уравнений с четырьмя неизвестными):

(2)

Это изменение и составляет идею итераций по способу Зейделя.

Естественно ожидать, что итерации по способу Зейделя дадут при том же числе шагов более точные результаты, чем обычные итерации, или, что то же самое, та же точность будет достигнута за меньшее число шагов. Вообще говоря, эти ожидания оправдываются. Однако нужно иметь в виду, что условия сходимости обычного итерационного процесса и итерационного процесса Зейделя различны. Один из этих процессов для данной системы может оказаться расходящимся тогда, когда другой сходится.

Вычислительная схема итерационного процесса Зейделя строится, как и для обычных итераций, на вычислении последовательных поправок. Рассмотрим эту схему, ограничившись, для краткости, системой трех линейных уравнений с тремя неизвестными. Формулы для отыскания следующих приближений через предыдущие будут в этом случае иметь вид

(3)

Формулы для вычисления поправок легко получить, исходя непосредственно из определения и используя (3). Действительно, для ν-ой итерации

δ₁ (ν) = ˗ = ( + ) ˗ ( + ) = = + ( ,

δ₁ (ν) = + . (4)

Для формула выглядит несколько иначе. Так как = ˗ =

= ( + ) ˗ ( + ),

= + , (5)

= + . (6)

Как и для обычного итерационного процесса, формулы (4)-(6) могут быть использованы для вычисления поправок для всех ν = 1, 2, …. , но не для ν = 0; для формулы должны быть выведены отдельно. Если принять за начальные приближения значения соответствующих свободных членов

= , = = ,

то для первых поправок получим выражения

(7)

где = + и = + .

Расположение вычислений показано в табл. 1. Верхняя часть ее не отличается от обычного способа, а таблица для вычисления поправок имеет уже несколько другой вид: при вычислении очередных поправок в ряде случаев используются уже полученные поправки того же этапа вычислений. Соответствующие места в табл. 1. подчеркнуты.

Вычисления продолжаются до получения достаточно малых поправок. Окончательные значения неизвестных получаются по формулам

+… (𝓀 = 1,2,3).

Таблица 1. Алгоритм способа Зейделя

для системы трех уравнений с тремя неизвестными

Метод итераций

Правила ввода функции

Примеры
≡ x^2/(1+x)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)

На рис.1а, 1б в окрестности корня |φ′(x)| 1, то процесс итерации может быть расходящимся (см. рис.2).

Достаточные условия сходимости метода итерации

Процесс нахождения нулей функции методом итераций состоит из следующих этапов:

Получить шаблон с омощью этого сервиса.
Уточнить интервалы в ячейках B2 , B3 .
Копировать строки итераций до требуемой точности (столбец D ).

Примечание: столбец A — номер итерации, столбец B — корень уравнения X , столбец C — значение функции F(X) , столбец D — точность eps .

источники:

http://poisk-ru.ru/s48685t6.html

http://math.semestr.ru/optim/iteration_method.php

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

1 Введение
- 1.1 Постановка вопроса. Виды погрешностей
2 Виды мер точности
3 Предельные погрешности
4 Погрешности округлений при представлении чисел в компьютере
5 Погрешности арифметических операций
6 Погрешности вычисления функций
7 Числовые примеры
8 Список литературы
9 См. также

Введение

Постановка вопроса. Виды погрешностей

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

При переходе от математической модели к численному методу возникают погрешности, называемые погрешностями метода. Они связаны с тем, что всякий численный метод воспроизводит исходную математическую модель приближенно. Наиболее типичными погрешностями метода являются погрешность дискретизации и погрешность округления.
При построении численного метода в качестве аналога исходной математической задачи обычно рассматривается её дискретная модель. Разность решений дискретизированной задачи и исходной называется погрешностью дискретизации. Обычно дискретная модель зависит от некоторого параметра (или их множества) дискретизации, при стремлении которого к нулю должна стремиться к нулю и погрешность дискретизации.
Дискретная модель представляет собой систему большого числа алгебраических уравнений. Для её решения используется тот или иной численный алгоритм. Входные данные этой системы, а именно коэффициенты и правые части, задаются в ЭВМ не точно, а с округлением. В процессе работы алгоритма погрешности округления обычно накапливаются, и в результате, решение, полученное на ЭВМ, будет отличаться от точного решения дискретизированной задачи. Результирующая погрешность называется погрешностью округления (вычислительной погрешностью). Величина этой погрешности определяется двумя факторами: точностью представления вещественных чисел в ЭВМ и чувствительностью данного алгоритма к погрешностям округления.

Итак, следует различать погрешности модели, дискретизации и округления. В вопросе преобладания какой-либо погрешности ответ неоднозначен. В общем случае нужно стремиться, чтобы все погрешности имели один и тот же порядок. Например, нецелесообразно пользоваться разностными схемами, имеющими точность 10⁻⁶, если коэффициенты исходных уравнений задаются с точностью 10⁻².

Виды мер точности

Мерой точности вычислений являются абсолютные и относительные погрешности. Абсолютная погрешность определяется формулой

где tilde a – приближение к точному значению .
Относительная погрешность определяется формулой

$delta(tilde a)=frac{|tilde a-a|}{a}.$

Относительная погрешность часто выражается в процентах. Абсолютная и относительная погрешности тесно связаны с понятием верных значащих цифр. Значащими цифрами числа называют все цифры в его записи, начиная с первой ненулевой цифры слева. Например, число 0,000129 имеет три значащих цифры. Значащая цифра называется верной, если абсолютная погрешность числа не превышает половины веса разряда, соответствующего этой цифре. Например, , абсолютная погрешность . Записывая число в виде

имеем , следовательно, число имеет две верных значащих цифр (9 и 3).

В общем случае абсолютная погрешность должна удовлетворять следующему неравенству:

$Delta(tilde a)<0,5cdot10^{m-n+1} ,$

где — порядок (вес) старшей цифры, — количество верных значащих цифр.
В рассматриваемом примере $Delta(tilde a)le0,5cdot10^{3-2+1}le0,5cdot10^2=50$ .

Относительная погрешность связана с количеством верных цифр приближенного числа соотношением:

$delta(tilde a)lefrac{Delta(tilde a)}{alpha_m}10^mlefrac{10^{m-n+1}}{alpha_m10^m}lefrac{1}{alpha_m10^{n-1}},$

где alpha_m — старшая значащая цифра числа.

Для двоичного представления чисел имеем $delta(tilde a)le2^{-n}$ .

Тот факт, что число tilde a является приближенным значением числа с абсолютной погрешностью , записывают в виде

причем числа tilde a и записываются с одинаковым количеством знаков после запятой, например, или $a=2,347pm2cdot10^{-3}$ .

Запись вида

означает, что число tilde a является приближенным значение числа с относительной погрешностью .

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

Очень часто степень точности решения задачи характеризуется некоторыми косвенными вспомогательными величинами. Например точность решения системы алгебраических уравнений

AX=F

характеризуется невязкой

где tilde X — приближенное решение системы.
Причём невязка достаточно сложным образом связана с погрешностью решения , причём если невязка мала, то погрешность может быть значительной.

Предельные погрешности

Пусть искомая величина является функцией параметров — приближенное значение . Тогда предельной абсолютной погрешностью называется величина

$D(a^*) = suplimits_{(t_1, ldots ,t_n) in Omega } left|{a(t_1, ldots ,t_n) - a^*}right| ,$

Предельной относительной погрешностью называется величина .

Пусть $left|{t_j - t_j^*}right| le Delta (t_j^* ), qquad j = 1 div n$ — приближенное значение . Предполагаем, что — непрерывно дифференцируемая функция своих аргументов. Тогда, по формуле Лагранжа,

$a(t_1, ldots ,t_n) - a^* = sumlimits_{j = 1}^n gamma_j (alpha )(t_j - t_j^*),$

где $gamma_j (alpha ) = a^{prime}_{t_j}(t_1^* + alpha (t_1 - t_1^*), ldots ,t_n^* + alpha (t_n - t_n^*)), qquad 0 le alpha le 1$ .

Отсюда

$left|{a(t_1, ldots ,t_n) - a^*}right| le D_1 (a^*) = sumlimits_{j = 1}^n b_j Delta (t_j^*),$

где $b_j = suplimits_Omega left|{a^{prime}_{t_j}(t_1, ldots ,t_n)}right|$ .

Можно показать, что при малых $rho = sqrt{{(Delta (t_1^* ))}^2 + ldots + {(Delta (t_n^* ))}^2 }$ эта оценка не может быть существенно улучшена. На практике иногда пользуются грубой (линейной) оценкой

$left|{a(t_1, ldots ,t_n) - a^*}right| le D_2 (a^*),$

где $D_2 (a^*) = sumlimits_{j = 1} left|{gamma_j (0)}right| Delta (t^*)$ .

Несложно показать, что:

— предельная погрешность суммы или разности равна сумме предельных погрешностей.
$delta (t_1^* cdots t_m^* cdot d_1^{* - 1} cdots d_m^{* - 1} ) = delta (t_1^* ) + ldots + delta (t_m^*) + delta (d_1^*) + ldots + delta (d_n^*)$ — предельная относительная погрешность произведения или частного приближенного равна сумме предельных относительных погрешностей.

Погрешности округлений при представлении чисел в компьютере

Одним из основных источников вычислительных погрешностей является приближенное представление чисел в компьютере, обусловленное конечностью разрядной сетки (см. Международный стандарт представления чисел с плавающей точкой в ЭВМ). Число , не представимое в компьютере, подвергается округлению, т. е. заменяется близким числом tilde a , представимым в компьютере точно.
Найдем границу относительной погрешности представления числа с плавающей точкой. Допустим, что применяется простейшее округление – отбрасывание всех разрядов числа, выходящих за пределы разрядной сетки. Система счисления – двоичная. Пусть надо записать число, представляющее бесконечную двоичную дробь

$a=underbrace{pm2^p}_{order}underbrace{left(frac{a_1}{2}+frac{a_2}{2^2}+dots+frac{a_t}{2^t}+frac{a_{t+1}}{2^{t+1}}+dotsright)}_{mantissa},$

где $a_j={01$ , — цифры мантиссы.
Пусть под запись мантиссы отводится t двоичных разрядов. Отбрасывая лишние разряды, получим округлённое число

$tilde a=pm2^pleft(frac{a_1}{2}+frac{a_2}{2^2}+dots+frac{a_t}{2^t}right).$

Абсолютная погрешность округления в этом случае равна

$a-tilde a=pm2^pleft(frac{a_{t+1}}{2^{t+1}}+frac{a_{t+2}}{2^{t+2}}+dotsright).$

Наибольшая погрешность будет в случае $a_{t+1}=1, qquad a_{t+2}=1,$ , тогда

$|a-tilde a|lepm2^pfrac{1}{2^{t+1}}underbrace{left(1+frac{1}{2}+frac{1}{2^2}+dotsright)}_{=2}=2^{p-t}.$

Т.к. , где — мантисса числа , то всегда a_1=1 . Тогда $|a|ge2^pcdot2^{-1}=2^{p-1}$ и относительная погрешность равна $frac{|a-tilde a|}{|a|}le2^{-t+1}$ . Практически применяют более точные методы округления и погрешность представления чисел равна

( 1 )

$frac{|a-tilde a|}{|a|}le2^{-t},$

т.е. точность представления чисел определяется разрядностью мантиссы .
Тогда приближенно представленное в компьютере число можно записать в виде , где $|epsilon|le2^{-t}$ – «машинный эпсилон» – относительная погрешность представления чисел.

Погрешности арифметических операций

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

Округленное в системе с плавающей точкой число, соответствующее точному числу , обозначается через fl(x) (от англ. floating – плавающий). Выполнение каждой арифметической операции вносит относительную погрешность, не большую, чем погрешность представления чисел с плавающей точкой (1). Верна следующая запись:

где box — любая из арифметических операций, $|epsilon|le2^{-t}$ .

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

Рассмотрим сложение и вычитание приближенных чисел. Абсолютная погрешность алгебраической суммы нескольких приближенных чисел равна сумме абсолютных погрешностей слагаемых.

Если сумма точных чисел равна

сумма приближенных чисел равна

где — абсолютные погрешности представления чисел.

Тогда абсолютная погрешность суммы равна

Относительная погрешность суммы нескольких чисел равна

( 2 )

$delta(S)=frac{Delta(S)}{S}=frac{a_1}{S}left(frac{Delta(a_1)}{a_1}right)+frac{a_2}{S}left(frac{Delta(a_2)}{a_2}right)+dots=frac{a_1delta(a_1)+a_2delta(a_2)+dots}{S},$

где — относительные погрешности представления чисел.

Из (2) следует, что относительная погрешность суммы нескольких чисел одного и того же знака заключена между наименьшей и наибольшей из относительных погрешностей слагаемых:

При сложении чисел разного знака или вычитании чисел одного знака относительная погрешность может быть очень большой (если числа близки между собой). Так как даже при малых величина может быть очень малой. Поэтому вычислительные алгоритмы необходимо строить таким образом, чтобы избегать вычитания близких чисел.

Необходимо отметить, что погрешности вычислений зависят от порядка вычислений. Далее будет рассмотрен пример сложения трех чисел.

( 3 )

tilde S=(tilde S_1+x_3)(1+delta_2)=(x_1+x_2)(1+delta_1)(1+delta_2)+x_3(1+delta_2).

При другой последовательности действий погрешность будет другой:

tilde S=(x_3+x_2)(1+delta_1)(1+delta_2)+x_1(1+delta_2).

Из (3) видно, что результат выполнения некоторого алгоритма, искаженный погрешностями округлений, совпадает с результатом выполнения того же алгоритма, но с неточными исходными данными. Т.е. можно применять обратный анализ: свести влияние погрешностей округления к возмущению исходных данных. Тогда вместо (3) будет следующая запись:

где

При умножении и делении приближенных чисел складываются и вычитаются их относительные погрешности.

tilde S=a_1cdot a_2(1+delta(a_1))(1+delta(a_2))

≅

с точностью величин второго порядка малости относительно delta .

Тогда .

Если $S=frac{a_1}{a_2}$ , то $Delta(S)=frac{a_1(1+delta_1)}{a_2(1+delta_2)}-frac{a_1}{a_2}=frac{a_1(delta_1-delta_2)}{a_2(1+delta_2)}approx frac{a_1}{a_2}(delta_1-delta_2), qquad delta(S)$ ≅

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

$delta_Sigma approx delta_{fl} quad sqrt{n},$

где – суммарная погрешность, $|delta_{fl}|leepsilon$ – погрешность выполнения операций с плавающей точкой, epsilon – погрешность представления чисел с плавающей точкой.

Погрешности вычисления функций

Рассмотрим трансформированную погрешность вычисления значений функций.

Абсолютная трансформированная погрешность дифференцируемой функции y=f(x) , вызываемая достаточно малой погрешностью аргумента , оценивается величиной .

Если f(x)>0 , то $delta(y)=frac{|f'(x)|}{f(x)}Delta(x)=left|(ln(f(x)))'right|cdotDelta(x)$ .

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

$Delta(y)=sumlimits_{i=1}^nleft|frac{partial f}{partial x_i}right|Delta(x_i)$

Если , то $delta(y)=sumlimits_{i=1}^nfrac{1}{f}cdotleft|frac{partial f}{partial x_i}right|cdotDelta(x_i)=sumlimits_{i=1}^{n}left|frac{partial l_n(f)}{partial x_i}right|Delta(x_i)$ .

Практически важно определить допустимую погрешность аргументов и допустимую погрешность функции (обратная задача). Эта задача имеет однозначное решение только для функций одной переменной y=f(x) , если f(x) дифференцируема и :

$Delta(x)=frac{1}{|f'(x)|}Delta(y)$

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

$Delta(x_i)=frac{Delta(y)}{left|frac{partial f}{partial x_i}right|}qquad$

(погрешностью других аргументов пренебрегаем).

Если вклад погрешностей всех аргументов примерно одинаков, то применяют принцип равных влияний:

$Delta(x_i)=frac{Delta(y)}{nleft|frac{partial f}{partial x_i}right|},qquad i=overline{1,n}.$

Числовые примеры

Специфику машинных вычислений можно пояснить на нескольких элементарных примерах.

ПРИМЕР 1. Вычислить все корни уравнения

$x^4 - 4x^3 + 8x^2 - 16x + 15.underbrace{99999999}_8 = {(x - 2)}^4 - 10^{- 8} = 0.$

Точное решение задачи легко найти:

$(x - 2)^2 = pm 10^{- 4},$

$x_1= 2,01; x_2= 1,99; x_{3,4}= 2 pm 0,01i.$

Если компьютер работает при $delta _M > 10^{ - 8}$ , то свободный член в исходном уравнении будет округлен до 16,0 и, с точки зрения представления чисел с плавающей точкой, будет решаться уравнение , т.е. $x_{1,2,3,4} = 2$ , что, очевидно, неверно. В данном случае малые погрешности в задании свободного члена $approx10^{-8}$ привели, независимо от метода решения, к погрешности в решении $approx10^{-2}$ .

ПРИМЕР 2. Решается задача Коши для обыкновенного дифференциального уравнения 2-го порядка:

u''(t) = u(t), qquad u(0) = 1, qquad u'(0) = - 1.

Общее решение имеет вид:

$u(t) = 0,5[u(0) + u'(0)]e^t + 0,5[u(0) - u'(0)]e^{- t}.$

При заданных начальных данных точное решение задачи: $u(x) = e^{-t}$ , однако малая погрешность delta в их задании приведет к появлению члена , который при больших значениях аргумента может существенно исказить решение.

ПРИМЕР 3. Пусть необходимо найти решение обыкновенного дифференциального уравнения:

$stackrel{cdot}{u} = 10u,qquad u = u(t), u(t_0) = u_0,qquad t in [0,1].$

Его решение: $u(t) = u_0e^{10(t - t_0 )}$ , однако значение u(t_0) известно лишь приближенно: , и на самом деле $u^*(t) = u_0^*e^{10(t - t_0)}$ .

Соответственно, разность u* - u будет:

$u^* - u = (u_0^* - u_0)e^{10(t - t_0)}.$

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

$|{u^*(t) - u(t)}| le varepsilon.$

Очевидно, что:

$maxlimits_{t in [0,1]} |{u^*(t) - u(t)}| = |{u*(1) - u(1)}| = |{u_0^* - u_0}|e^{10(1 - t_0)}.$

Отсюда можно получить требования к точности задания начальных данных $delta: qquad|u_0^* - u_0| < delta, qquad delta le varepsilon e^{ - 10}$ при t_0= 0 .

Решение оказывается очень чувствительным к заданию начальных данных. Такого рода задачи называются плохо обусловленными.

ПРИМЕР 4. Решением системы линейных алгебраических уравнений (СЛАУ):

left{ begin{array}{l} u + 10v = 11, 100u + 1001v = 1101; end{array} right.

является пара чисел .

Изменив правую часть системы на 0,01 , получим возмущенную систему:

left{ begin{array}{l} u + 10v = 11.01, 100u + 1001v = 1101; end{array} right.

с решением , сильно отличающимся от решения невозмущенной системы. Эта система также плохо обусловлена.

ПРИМЕР 5. Рассмотрим методический пример вычислений на модельном компьютере, обеспечивающем точность . Проанализируем причину происхождения ошибки, например, при вычитании двух чисел, взятых с точностью до третьей цифры после десятичной точки , разность которых составляет .

В памяти машины эти же числа представляются в виде:

u_M = u(1 + delta_M^u), quad v_M = v(1 + delta_M^v)

, причем

Тогда:

u_M - u approx udelta_M^u, quad v_M - v approx vdelta_M^v.

Относительная ошибка при вычислении разности будет равна:

$delta = frac{(u_M - v_M) - (u - v)}{(u - v)} = frac{(u_M - u) - (v_M - v)}{(u - v)} = frac{delta_M^u - delta_M^v}{(u - v)}.$

Очевидно, что $delta = left|{frac{delta_M^u - delta_M^v}{Delta }} right| le frac{2delta_M}{0,001} approx 2000delta_M = 1$ , т.е. все значащие цифры могут оказаться неверными.

ПРИМЕР 6. Рассмотрим рекуррентное соотношение $u_{i+1} = qu_i, quad i ge 0, quad u_0 = a,quad q > 0, quad u_i > 0.$

Пусть при выполнении реальных вычислений с конечной длиной мантиссы на -м шаге возникла погрешность округления, и вычисления проводятся с возмущенным значением , тогда вместо $u_{i+1}$ получим $u_{i + 1}^M = q(u_i + delta_i) = u_{i + 1} + qdelta_i$ , т.е. $delta_{i + 1} = qdelta_i,quad i = 0,1,ldots$ .

Следовательно, если |q| > 1 , то в процессе вычислений погрешность, связанная с возникшей ошибкой округления, будет возрастать (алгоритм неустойчив). В случае погрешность не возрастает и численный алгоритм устойчив.

Список литературы

А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
http://www.mgopu.ru/PVU/2.1/nummethods/Chapter1.htm
http://www.intuit.ru/department/calculate/calcmathbase/1/4.html

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Источник

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

1 Введение
- 1.1 Постановка вопроса. Виды погрешностей
2 Виды мер точности
3 Предельные погрешности
4 Погрешности округлений при представлении чисел в компьютере
5 Погрешности арифметических операций
6 Погрешности вычисления функций
7 Числовые примеры
8 Список литературы
9 См. также

Введение

Постановка вопроса. Виды погрешностей

Виды мер точности

где tilde a – приближение к точному значению .
Относительная погрешность определяется формулой

$delta(tilde a)=frac{|tilde a-a|}{a}.$

имеем , следовательно, число имеет две верных значащих цифр (9 и 3).

В общем случае абсолютная погрешность должна удовлетворять следующему неравенству:

$Delta(tilde a)<0,5cdot10^{m-n+1} ,$

Относительная погрешность связана с количеством верных цифр приближенного числа соотношением:

$delta(tilde a)lefrac{Delta(tilde a)}{alpha_m}10^mlefrac{10^{m-n+1}}{alpha_m10^m}lefrac{1}{alpha_m10^{n-1}},$

где alpha_m — старшая значащая цифра числа.

Для двоичного представления чисел имеем $delta(tilde a)le2^{-n}$ .

Тот факт, что число tilde a является приближенным значением числа с абсолютной погрешностью , записывают в виде

причем числа tilde a и записываются с одинаковым количеством знаков после запятой, например, или $a=2,347pm2cdot10^{-3}$ .

Запись вида

означает, что число tilde a является приближенным значение числа с относительной погрешностью .

AX=F

характеризуется невязкой

Предельные погрешности

$D(a^*) = suplimits_{(t_1, ldots ,t_n) in Omega } left|{a(t_1, ldots ,t_n) - a^*}right| ,$

Предельной относительной погрешностью называется величина .

$a(t_1, ldots ,t_n) - a^* = sumlimits_{j = 1}^n gamma_j (alpha )(t_j - t_j^*),$

где $gamma_j (alpha ) = a^{prime}_{t_j}(t_1^* + alpha (t_1 - t_1^*), ldots ,t_n^* + alpha (t_n - t_n^*)), qquad 0 le alpha le 1$ .

Отсюда

$left|{a(t_1, ldots ,t_n) - a^*}right| le D_1 (a^*) = sumlimits_{j = 1}^n b_j Delta (t_j^*),$

где $b_j = suplimits_Omega left|{a^{prime}_{t_j}(t_1, ldots ,t_n)}right|$ .

$left|{a(t_1, ldots ,t_n) - a^*}right| le D_2 (a^*),$

где $D_2 (a^*) = sumlimits_{j = 1} left|{gamma_j (0)}right| Delta (t^*)$ .

Несложно показать, что:

— предельная погрешность суммы или разности равна сумме предельных погрешностей.
$delta (t_1^* cdots t_m^* cdot d_1^{* - 1} cdots d_m^{* - 1} ) = delta (t_1^* ) + ldots + delta (t_m^*) + delta (d_1^*) + ldots + delta (d_n^*)$ — предельная относительная погрешность произведения или частного приближенного равна сумме предельных относительных погрешностей.

Погрешности округлений при представлении чисел в компьютере

$a=underbrace{pm2^p}_{order}underbrace{left(frac{a_1}{2}+frac{a_2}{2^2}+dots+frac{a_t}{2^t}+frac{a_{t+1}}{2^{t+1}}+dotsright)}_{mantissa},$

где $a_j={0\1$ , — цифры мантиссы.
Пусть под запись мантиссы отводится t двоичных разрядов. Отбрасывая лишние разряды, получим округлённое число

$tilde a=pm2^pleft(frac{a_1}{2}+frac{a_2}{2^2}+dots+frac{a_t}{2^t}right).$

Абсолютная погрешность округления в этом случае равна

$a-tilde a=pm2^pleft(frac{a_{t+1}}{2^{t+1}}+frac{a_{t+2}}{2^{t+2}}+dotsright).$

Наибольшая погрешность будет в случае $a_{t+1}=1, qquad a_{t+2}=1,$ , тогда

$|a-tilde a|lepm2^pfrac{1}{2^{t+1}}underbrace{left(1+frac{1}{2}+frac{1}{2^2}+dotsright)}_{=2}=2^{p-t}.$

( 1 )

$frac{|a-tilde a|}{|a|}le2^{-t},$

Погрешности арифметических операций

где box — любая из арифметических операций, $|epsilon|le2^{-t}$ .

сумма приближенных чисел равна

где — абсолютные погрешности представления чисел.

Тогда абсолютная погрешность суммы равна

Относительная погрешность суммы нескольких чисел равна

( 2 )

$delta(S)=frac{Delta(S)}{S}=frac{a_1}{S}left(frac{Delta(a_1)}{a_1}right)+frac{a_2}{S}left(frac{Delta(a_2)}{a_2}right)+dots=frac{a_1delta(a_1)+a_2delta(a_2)+dots}{S},$

где — относительные погрешности представления чисел.

( 3 )

При другой последовательности действий погрешность будет другой:

где

При умножении и делении приближенных чисел складываются и вычитаются их относительные погрешности.

≅

с точностью величин второго порядка малости относительно delta .

Тогда .

Если $S=frac{a_1}{a_2}$ , то $Delta(S)=frac{a_1(1+delta_1)}{a_2(1+delta_2)}-frac{a_1}{a_2}=frac{a_1(delta_1-delta_2)}{a_2(1+delta_2)}approx frac{a_1}{a_2}(delta_1-delta_2), qquad delta(S)$ ≅

$delta_Sigma approx delta_{fl} quad sqrt{n},$

Погрешности вычисления функций

Рассмотрим трансформированную погрешность вычисления значений функций.

Абсолютная трансформированная погрешность дифференцируемой функции y=f(x) , вызываемая достаточно малой погрешностью аргумента , оценивается величиной .

Если f(x)>0 , то $delta(y)=frac{|f'(x)|}{f(x)}Delta(x)=left|(ln(f(x)))'right|cdotDelta(x)$ .

$Delta(y)=sumlimits_{i=1}^nleft|frac{partial f}{partial x_i}right|Delta(x_i)$

Если , то $delta(y)=sumlimits_{i=1}^nfrac{1}{f}cdotleft|frac{partial f}{partial x_i}right|cdotDelta(x_i)=sumlimits_{i=1}^{n}left|frac{partial l_n(f)}{partial x_i}right|Delta(x_i)$ .

$Delta(x)=frac{1}{|f'(x)|}Delta(y)$

$Delta(x_i)=frac{Delta(y)}{left|frac{partial f}{partial x_i}right|}qquad$

(погрешностью других аргументов пренебрегаем).

Если вклад погрешностей всех аргументов примерно одинаков, то применяют принцип равных влияний:

$Delta(x_i)=frac{Delta(y)}{nleft|frac{partial f}{partial x_i}right|},qquad i=overline{1,n}.$

Числовые примеры

Специфику машинных вычислений можно пояснить на нескольких элементарных примерах.

ПРИМЕР 1. Вычислить все корни уравнения

$x^4 - 4x^3 + 8x^2 - 16x + 15.underbrace{99999999}_8 = {(x - 2)}^4 - 10^{- 8} = 0.$

Точное решение задачи легко найти:

$(x - 2)^2 = pm 10^{- 4},$

$x_1= 2,01; x_2= 1,99; x_{3,4}= 2 pm 0,01i.$

ПРИМЕР 2. Решается задача Коши для обыкновенного дифференциального уравнения 2-го порядка:

Общее решение имеет вид:

$u(t) = 0,5[u(0) + u'(0)]e^t + 0,5[u(0) - u'(0)]e^{- t}.$

ПРИМЕР 3. Пусть необходимо найти решение обыкновенного дифференциального уравнения:

$stackrel{cdot}{u} = 10u,qquad u = u(t),\ u(t_0) = u_0,qquad t in [0,1].$

Соответственно, разность u* - u будет:

$u^* - u = (u_0^* - u_0)e^{10(t - t_0)}.$

$|{u^*(t) - u(t)}| le varepsilon.$

Очевидно, что:

$maxlimits_{t in [0,1]} |{u^*(t) - u(t)}| = |{u*(1) - u(1)}| = |{u_0^* - u_0}|e^{10(1 - t_0)}.$

Таким образом, требование к заданию точности начальных данных оказываются в $e^{10}$ раз выше необходимой точности результата решения задачи. Это требование, скорее всего, окажется нереальным.

Решение оказывается очень чувствительным к заданию начальных данных. Такого рода задачи называются плохо обусловленными.

ПРИМЕР 4. Решением системы линейных алгебраических уравнений (СЛАУ):

$left{ begin{array}{l} u + 10v = 11, \ 100u + 1001v = 1101; \ end{array} right.$

является пара чисел .

Изменив правую часть системы на 0,01 , получим возмущенную систему:

$left{ begin{array}{l} u + 10v = 11.01, \ 100u + 1001v = 1101; \ end{array} right.$

с решением , сильно отличающимся от решения невозмущенной системы. Эта система также плохо обусловлена.

В памяти машины эти же числа представляются в виде:

, причем

Тогда:

Относительная ошибка при вычислении разности будет равна:

$delta = frac{(u_M - v_M) - (u - v)}{(u - v)} = frac{(u_M - u) - (v_M - v)}{(u - v)} = frac{delta_M^u - delta_M^v}{(u - v)}.$

ПРИМЕР 6. Рассмотрим рекуррентное соотношение $u_{i+1} = qu_i, quad i ge 0, quad u_0 = a,quad q > 0, quad u_i > 0.$

Список литературы

А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
http://www.mgopu.ru/PVU/2.1/nummethods/Chapter1.htm
http://www.intuit.ru/department/calculate/calcmathbase/1/4.html

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Источник