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

Добавил:

Upload

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

Вуз:

Предмет:

Файл:

теория.pdf

Скачиваний:

179

Добавлен:

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

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

Источник

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

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

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

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

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня 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

Источник

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

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

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

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

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

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

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

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

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

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

Источник

Метод последовательных приближений
Исходное уравнение можно представить в виде x = φ (t). Например, можно выделить x из уравнения, а остальное перенести в правую часть.
Можно также выполнить следующее преобразование: x = x + cf (x), где с – произвольная постоянная. В этом случае φ (x) = x + cf (x). Задаются начальным приближением x [0], а последующие приближения определяют итерационной процедурой вида x [ k+1] = φ (x [ k ]), k = 0, 1, 2 … . Эта итерационная процедура сходится, если на отрезке [a, b], содержащем корень x*, а также все его последовательные приближения x [0], x [1], … x [k], выполнено условие │φ l (x) │ <1, сходимость будет тем быстрее, чем меньше по абсолютной величине значение производной φ l (x).
Метод последовательных приближений обладает тем важным преимуществом, что при его использовании не накапливаются ошибки вычислений. Ошибка вычислений эквивалентна ухудшению очередного приближения, а это может отразиться только на числе итераций, но не на точности результата.

Решения; Х+кореньХ+3кореньХ-2.5=0

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

Источник

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

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

Содержание

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

Введение

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

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

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

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

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

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

$Delta(tilde a)=|tilde a-a|,$

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

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

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

$9348=9cdot10^3+3cdot10^2+4cdot10^1+8cdot10^0,$

имеем $0,5cdot10^1<Delta(tilde a)<0,5cdot10^2$ , следовательно, число имеет две верных значащих цифр (9 и 3).

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

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

где $m$ — порядок (вес) старшей цифры, $n$ — количество верных значащих цифр.
В рассматриваемом примере $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$ является приближенным значением числа $a$ с абсолютной погрешностью $Delta(tilde a)$ , записывают в виде

$a=tilde apmDelta(tilde a),$

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

Запись вида

$a=tilde a(1pmdelta(tilde a))$

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

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

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

$AX=F$

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

$R=F-Atilde X,$

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

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

Пусть искомая величина $a$ является функцией параметров $t_1, ldots , t_n in Omega, qquad a*$ — приближенное значение $a$ . Тогда предельной абсолютной погрешностью называется величина

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

Предельной относительной погрешностью называется величина $D(a*)/| a*|$ .

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

$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 ( pm t_1^* pm , ldots , pm t_n^*) = Delta (t_1^* ) + ldots + Delta (t_n^* )$ — предельная погрешность суммы или разности равна сумме предельных погрешностей.
$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$ , не представимое в компьютере, подвергается округлению, т. е. заменяется близким числом $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={0\1$ , $qquad (j=1,2,...)$ — цифры мантиссы.
Пусть под запись мантиссы отводится 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}.$

Т.к. $|M|ge0,5$ , где $M$ — мантисса числа $a$ , то всегда $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},$

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

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

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

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

$fl(abox b)=abox b(1pmepsilon),$

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

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

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

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

$S=a_1+a_2+dots+a_n,$

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

$tilde S=a_1+Delta(a_1)+a_2+Delta(a_2)+dots+a_n+Delta(a_n),$

где $Delta(a_i), qquad i=1,2,...,n$ — абсолютные погрешности представления чисел.

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

$Delta(S)=Delta(a_1)+Delta(a_2)+dots+Delta(a_n).$

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

( 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},$

где $delta(a_i), qquad i=1,2,...,n$ — относительные погрешности представления чисел.

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

$min quad delta(a_k)ledelta(S)le max quad delta(a_k), qquad k=1,2,...,n, quad a_k>0.$

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

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

$S=x_1+x_2+x_3,$

$tilde S_1=(x_1+x_2)(1+delta_1),$

( 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_1=(x_3+x_2)(1+delta_1),$

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

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

$tilde S=tilde x_1+tilde x_2+tilde x_3,$

где $tilde x_1=x_1(1+delta_1)(1+delta_2), quad tilde x_2=x_2(1+delta_1)(1+delta_2), quad tilde x_3=x_3(1+delta_2).$

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

$S=a_1cdot a_2,$

$tilde S=a_1cdot a_2(1+delta(a_1))(1+delta(a_2))$ ≅ $a_1cdot a_2(1+delta(a_1)+delta(a_2)),$

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

Тогда $delta(S)=delta(a_1)+delta(a_2)$ .

Если $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_1-delta_2.$

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

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

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

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

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

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

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

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

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

Если $f(x_1,x_2,...,x_n)>0$ , то $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)$ дифференцируема и $f'(x)not=0$ :

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

Для функций многих переменных задача не имеет однозначного решения, необходимо ввести дополнительные ограничения. Например, если функция $y=f(x_1,x_2,...,x_n)$ наиболее критична к погрешности $Delta(x_i)$ , то:

$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-2)^4= 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$ в их задании приведет к появлению члена $delta e^t$ , который при больших значениях аргумента может существенно исказить решение.

ПРИМЕР 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_0) approx u_0^*$ , и на самом деле $u^*(t) = u_0^*e^{10(t - t_0)}$ .

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

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

Предположим, что необходимо гарантировать некоторую заданную точность вычислений $epsilon > 0$ всюду на отрезке $t in [0,1]$ . Тогда должно выполняться условие:

$|{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$ .

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

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

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

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

является пара чисел ${1, quad 1}$ .

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

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

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

ПРИМЕР 5. Рассмотрим методический пример вычислений на модельном компьютере, обеспечивающем точность $delta_M = 0,0005$ . Проанализируем причину происхождения ошибки, например, при вычитании двух чисел, взятых с точностью до третьей цифры после десятичной точки $u = 1,001,quad v = 1,002$ , разность которых составляет $Delta = |v_M - u_M| = 0,001$ .

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

$u_M = u(1 + delta_M^u), quad v_M = v(1 + delta_M^v)$ , причем $mid delta_M^umid le delta_M$ и $mid delta_M^vmid le delta_M.$

Тогда:

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

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

$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.$

Пусть при выполнении реальных вычислений с конечной длиной мантиссы на $i$ -м шаге возникла погрешность округления, и вычисления проводятся с возмущенным значением $u_i^M = u_i + delta_i$ , тогда вместо $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$ , то в процессе вычислений погрешность, связанная с возникшей ошибкой округления, будет возрастать (алгоритм неустойчив). В случае $mid qmid le 1$ погрешность не возрастает и численный алгоритм устойчив.

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

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

См. также

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

Источник

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

Ньютона

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

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

Метод Якоби

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

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

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

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

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

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

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

Содержание

Введение

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

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

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

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

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

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

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

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

См. также

А вот еще интересные материалы: