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

Есть
случаи, когда уравнение
(4.1)
можно заменить эквивалентным ему
уравнением

,
иначе

(4.2)

где
.

Выберем
некоторое нулевое приближение

и вычислим дальнейшие приближения по
формулам

,
n
= 0, 1, 2, … (4.3)

Очевидно,
если

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

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

,
(4.4)

где
точка 
лежит между точками

и
.
Поэтому, если всюду


q
< 1, то
отрезки

убывают не медленнее, чем члены
геометрической прогрессии со знаменателем
q
< 1,
и последовательность

сходится
при любом нулевом приближении (рис.
4.3 а,
в).
Если
|()|
>1,
то в силу непрерывности

и в некоторой окрестности корня
выполняется это неравенство; в этом
случае итерации не могут сходиться.
Если |()|
<
1,
но вдали от корня |
(x)|
>
1,
то итерации сходятся при условии, что
нулевое приближение выбрано достаточно
близко к корню; при произвольном нулевом
приближении сходимости может не быть.

Очевидно,
что чем меньше
q,
тем быстрее сходимость. Вблизи корня
асимптотическая сходимость определяется
величиной
|
()|
и
будет особенно быстрой при

()
= 0.
Значит, успех метода зависит от того,
насколько удачно выбрано (x).
Например, для извлечения квадратного
корня, т.е. решения уравнения х²=а
можно положить (x)=

или (x)
=

[x
+
]
и соответственно написать такие
итерационные процессы:

или
.
(4.5)

Первый
процесс вообще не сходится, а второй
сходится при любом
x₀>
0
и очень быстро, ибо 
()=
0.
Второй процесс используют при извлечении
корня на клавишных машинах.

Каков
практический критерий сходимости, т.
е. когда надо прекращать итерации
(4.2)?
Из
(4.3)
видно, что если ()
<
0,
то
итерации попеременно оказываются то
с одной, то с другой стороны корня
(рис
4.3, в,
г),
так что корень заключен в интервале
(х_n,
х_n₊₁).
Это
надежная, хотя несколько грубая оценка.
Но она не применима при

>
0,
когда итерации сходятся к корню монотонно
(рис 4.3, а,
б),
т. е. с одной стороны.

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

.
(4.6)

q
< 1
q >
1

₀
x₁
x₂

x₀
x₁
x₀

q
< 1 y
q
> 1

x ₀
x₂
x ₂
x₁
x
x₂x₂
x₁
x

в
г

Рис. 4.3. Графики
функции, иллюстрирующие сходимость
или расходимость: а,
в
– процедуры сходятся; б,
г
– расходятся

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

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

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

Источник

Материал из 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={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}.$

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

Таким образом, требование к заданию точности начальных данных оказываются в $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.$

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

ПРИМЕР 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

Источник

Простая итерация

Cтраница 2

Метод простой итерации для решения нелинейных уравнений заключается в следующем.
[17]

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

Метод простой итерации для решения нелинейных уравнений по существу является развитием метода простой итерации для одного уравнения.
[20]

Метод простых итераций во многих случаях расходится или имеет медленную сходимость. Существует ряд способов ускоряющих сходимость метода простых итераций.
[21]

Метод простых итераций состоит в следующем.
[22]

В методе простых итераций И может достигать неприемлемо больших значений, поэтому целесообразно ввести на И ограничение Ягр сверху. Методы Зейделя, Якоби, последовательной верхней релаксации ( ПВР) имеют аналогичный характер зависимости Я от Ц, хотя скорость сходимости у них часто оказывается несколько выше, чем в методе простых итераций.
[24]

В методе простой итерации в качестве итерационной матрицы выбирается В М, где I — единичная матрица; h — скалярная величина.
[25]

Применение метода простой итерации для решения системы (1.51) неэффективно, поскольку ликвидирует все преимущества неявных методов интегрирования из-за ограничений на шаг hm, значительно более сильных, чем в методе Ньютона.
[26]

Недостатки метода простых итераций частично устраняются в методе Ньютона. Суть этого метода заключается в следующем. Допустим, что два приближенных значения хк 1 н хк отличаются на малую величину Ах хк — хк.
[27]

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

В методе простых итераций на К — и итерации рассчитываются все элементы вектора Х, которые затем используется на K I — и итерации в качестве нового приближения. Сходимость методе можно ускорить, если рассчитанные значения неизвестных используются на этой же итерации для вычислений значений последующих неизвестных.
[29]

Рассмотренные свойства простых итераций служат важной основой для интерпретации численных результатов, полученных при решении сложных задач.
[30]

Страницы:

Источник

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

Аннотация

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

В данной курсовой работе рассмотрено 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);;.

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

Источник

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

Содержание

Введение

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

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

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

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

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

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

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

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

См. также

Простая итерация

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

Возможно, вам также будет интересно: